Recursive-length prefix (RLP) кодирование

Сериализация с помощью рекурсивной длинны префикса (RLP) обширно используется в клиентах сети Ethereum. RLP стандартизирует передачу данных между узлами в пространственно эффективном формате. Цель RLP - кодировать произвольное количество вложенных массивов двоичных данных. RLP - это метод первичной кодировки, используемый для сериализации объектов в исполнительном слое Ethereum. Основное предназначение RLP — кодировать структуру; за исключением положительных целых чисел, RLP делегирует кодирование определенных типов данных (например, строк, чисел с плавающей запятой) протоколам более высокого порядка. Положительные целые числа должны быть представлены в двоичном виде с прямым порядком байтов без ведущих нулей (таким образом, целочисленное значение ноль эквивалентно пустому байтовому массиву). Десериализованные положительные целые числа с ведущими нулями должны рассматриваться как недействительные любым протоколом более высокого порядка, использующим RLP.

Больше информации в Желтой книге Ethereum (Приложение B)opens in a new tab.

Для использования RLP при кодировании словаря предлагаются следующие две канонические формы:

• используйте [[k1,v1],[k2,v2]...] с ключами в лексикографическом порядке
• использовать более высокоуровневую кодировку Patricia Tree как Ethereum

Определение

Функция кодирования RLP принимает один из элементов. Элемент определяется следующим образом：

• строка (т. е. массив байтов) является элементом
• список элементов - элемент
• положительное целое число является элементом

Например, все следующие пункты - элементы:

• пустая строка;
• строка, содержащая слово "cat";
• список, содержащий любое количество строк;
• и более сложные структуры данных, такие как ["cat", ["puppy", "cow"], "horse", [[]], "pig", [""], "sheep"].
• число 100

Обратите внимание, что в контексте остальной части этой страницы «строка» означает «определенное количество байтов двоичных данных»; никакие специальные кодировки не используются и никакие сведения о содержании строк не подразумеваются (за исключением случаев, когда это требуется правилом, запрещающим неминимальные положительные целые числа).

Кодирование RLP определяется следующим образом:

• Для положительного целого числа оно преобразуется в кратчайший байтовый массив, интерпретация которого с прямым порядком байтов (big-endian) является целым числом, а затем кодируется как строка в соответствии с приведенными ниже правилами.
• Для одного байта, значение которого находится в диапазоне [0x00, 0x7f] (десятичное [0, 127]), этот байт является своей собственной RLP-кодировкой.
• В противном случае, если строка имеет длину 0–55 байтов, кодировка RLP состоит из одного байта со значением 0x80 (десятичное 128) плюс длина строки, за которой следует сама строка. Таким образом, диапазон первого байта: [0x80, 0xb7] (десятичное [128, 183]).
• Если строка длиннее 55 байтов, кодировка RLP состоит из одного байта со значением 0xb7 (десятичное 183) плюс длина в байтах длины строки в двоичной форме, за которой следует длина строки, а затем сама строка. Например, строка длиной 1024 байта будет закодирована как \xb9\x04\x00 (десятичное 185, 4, 0), за которой следует сама строка. Здесь 0xb9 (183 + 2 = 185) — это первый байт, за которым следуют 2 байта 0x0400 (десятичное 1024), которые обозначают длину фактической строки. Таким образом, диапазон первого байта: [0xb8, 0xbf] (десятичное [184, 191]).
• Если строка имеет длину 2^64 байтов или больше, ее нельзя закодировать.
• Если общая полезная нагрузка списка (т. е. общая длина всех его RLP-кодированных элементов) составляет 0–55 байт, кодировка RLP состоит из одного байта со значением 0xc0 плюс длина полезной нагрузки, за которой следует конкатенация RLP-кодировок элементов. Таким образом, диапазон первого байта: [0xc0, 0xf7] (десятичное [192, 247]).
• Если общая полезная нагрузка списка превышает 55 байт, кодировка RLP состоит из одного байта со значением 0xf7 плюс длина в байтах длины полезной нагрузки в двоичной форме, за которой следует длина полезной нагрузки, а затем — конкатенация RLP-кодировок элементов. Таким образом, диапазон первого байта: [0xf8, 0xff] (десятичное [248, 255]).

В коде это выражается как:

1def rlp_encode(input):
2    if isinstance(input,str):
3        if len(input) == 1 and ord(input) < 0x80:
4            return input
5        return encode_length(len(input), 0x80) + input
6    elif isinstance(input, list):
7        output = ''
8        for item in input:
9            output += rlp_encode(item)
10        return encode_length(len(output), 0xc0) + output
11
12def encode_length(L, offset):
13    if L < 56:
14         return chr(L + offset)
15    elif L < 256**8:
16         BL = to_binary(L)
17         return chr(len(BL) + offset + 55) + BL
18    raise Exception("слишком длинные входные данные")
19
20def to_binary(x):
21    if x == 0:
22        return ''
23    return to_binary(int(x / 256)) + chr(x % 256)
Показать все
Копировать

Примеры:

• строка "dog" = [ 0x83, 'd', 'o', 'g' ]
• список [ "cat", "dog" ] = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]
• пустая строка ('null') = [ 0x80 ]
• пустой список = [ 0xc0 ]
• целое число 0 = [ 0x80 ]
• байт '\x00' = [ 0x00 ]
• байт '\x0f' = [ 0x0f ]
• байты '\x04\x00' = [ 0x82, 0x04, 0x00 ]
• теоретико-множественное представлениеopens in a new tab числа три, [ [], [[]], [ [], [[]] ] ] = [ 0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0 ]
• строка "Lorem ipsum dolor sit amet, consectetur adipisicing elit" = [ 0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't' ]`

Декодирование RLP

В соответствии с правилами и процессами RLP кодирования, входными данными RLP декодирования является массив с бинарными данными. Процесс декодирования RLP следующий:

1. в соответствии с первым байтом (т. е. префиксом) входных данных и декодирования типа данных, длины фактических данных и смещения;

2. в соответствии с типом и смещением данных соответствующим образом декодируйте данные, соблюдая правило минимального кодирования для положительных целых чисел;

3. продолжить декодирование остальных входных данных;

Правила декодирования типов данных и смещения следующие:

1. данные являются строкой, если диапазон первого байта (т. е. префикса) — [0x00, 0x7f], и строка — это в точности сам первый байт;

2. данные являются строкой если значение первого байта (т.е. префикса) находится в промежутке [0x80, 0xb7] и последующей строкой, длина которой равно значению первого байта минус 0x80;

3. данные являются строкой, если значение первого байта (т.е. префикса) находится в промежутке [0xb8, 0xbf] и длина строки чья длина в байтах равна значению первого байта минус 0xb7 после первого байта и последующая строка;

4. данные являются списком, если значение первого байта находится в промежутке [0xc0, 0xf7], и конкатенация RLP кодирований всех элементов списка, следующего за первым байтом, равна значению первого байта минус 0xc0;

5. данные являются списком, если диапазон первого байта — [0xf8, 0xff], и общая полезная нагрузка списка, длина которого равна значению первого байта минус 0xf7, следует за первым байтом, и конкатенация RLP-кодировок всех элементов списка следует за общей полезной нагрузкой списка;

В коде это выражается как:

1def rlp_decode(input):
2    if len(input) == 0:
3        return
4    output = ''
5    (offset, dataLen, type) = decode_length(input)
6    if type is str:
7        output = instantiate_str(substr(input, offset, dataLen))
8    elif type is list:
9        output = instantiate_list(substr(input, offset, dataLen))
10    output += rlp_decode(substr(input, offset + dataLen))
11    return output
12
13def decode_length(input):
14    length = len(input)
15    if length == 0:
16        raise Exception("входные данные — null")
17    prefix = ord(input[0])
18    if prefix <= 0x7f:
19        return (0, 1, str)
20    elif prefix <= 0xb7 and length > prefix - 0x80:
21        strLen = prefix - 0x80
22        return (1, strLen, str)
23    elif prefix <= 0xbf and length > prefix - 0xb7 and length > prefix - 0xb7 + to_integer(substr(input, 1, prefix - 0xb7)):
24        lenOfStrLen = prefix - 0xb7
25        strLen = to_integer(substr(input, 1, lenOfStrLen))
26        return (1 + lenOfStrLen, strLen, str)
27    elif prefix <= 0xf7 and length > prefix - 0xc0:
28        listLen = prefix - 0xc0;
29        return (1, listLen, list)
30    elif prefix <= 0xff and length > prefix - 0xf7 and length > prefix - 0xf7 + to_integer(substr(input, 1, prefix - 0xf7)):
31        lenOfListLen = prefix - 0xf7
32        listLen = to_integer(substr(input, 1, lenOfListLen))
33        return (1 + lenOfListLen, listLen, list)
34    raise Exception("входные данные не соответствуют формату кодировки RLP")
35
36def to_integer(b):
37    length = len(b)
38    if length == 0:
39        raise Exception("входные данные — null")
40    elif length == 1:
41        return ord(b[0])
42    return ord(substr(b, -1)) + to_integer(substr(b, 0, -1)) * 256
Показать все
Копировать

Дополнительные материалы

• RLP в Ethereumopens in a new tab
• Ethereum изнутри: RLPopens in a new tab
• Coglio, A. (2020). Ethereum's Recursive Length Prefix in ACL2. arXiv preprint arXiv:2009.13769.opens in a new tab

Смежные темы

• Дерево Меркла — Патриции