Сериализация с префиксом рекурсивной длины (RLP)

Редактировать страницу

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

Дополнительная информация доступна в желтой книге Эфириума (Приложение B) (opens in a new tab).

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

использовать [[k1,v1],[k2,v2]...] с ключами в лексикографическом порядке
использовать высокоуровневое кодирование дерева Патриции (Patricia Tree), как это делает Эфириум

Определение

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

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

Например, все нижеперечисленное является элементами:

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

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

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

Положительное целое число преобразуется в кратчайший массив байтов, интерпретация которого, использующая прямой порядок байтов, является этим целым числом, а затем кодируется как строка в соответствии с приведенными ниже правилами.
Для одного байта, значение которого находится в диапазоне [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]).

В краткой форме:

Диапазон	Байт 1	Байт 2	...	Байт 9	Байт 10	Значение
`0x00-0x7f`	`0ppppppp`					однобайтовая строка
`0x80-0xb7`	`10nnnnnn`	`pppppppp`	`...`			короткая строка (0-55 байтов)
`0xb8-0xbf`	`10111NNN`	`nnnnnnnn`	`...`	`nnnnnnnn`/`pppppppp`	`pppppppp`	длинная строка, N+1 байтов для длины, затем полезная нагрузка
`0xc0-0xf7`	`11nnnnnn`	`pppppppp`	`...`			короткий список (0-55 байтов)
`0xf8-0xff`	`11111NNN`	`nnnnnnnn`	`...`	`nnnnnnnn`/`pppppppp`	`pppppppp`	длинный список, N+1 байтов для длины, затем полезная нагрузка

p = полезная нагрузка
n = длина (количество байтов полезной нагрузки)
N = смещение длины длины (далее следуют N+1 байтов n)

В коде это выглядит так:

def rlp_encode(input):
    if isinstance(input,str):
        if len(input) == 1 and ord(input) < 0x80:
            return input
        return encode_length(len(input), 0x80) + input
    elif isinstance(input, list):
        output = ''
        for item in input:
            output += rlp_encode(item)
        return encode_length(len(output), 0xc0) + output

def encode_length(L, offset):
    if L < 56:
         return chr(L + offset)
    elif L < 256**8:
         BL = to_binary(L)
         return chr(len(BL) + offset + 55) + BL
    raise Exception("input too long")

def to_binary(x):
    if x == 0:
        return ''
    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 выглядит следующим образом:

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

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

данные являются строкой, если диапазон первого байта (т. е. префикса) составляет [0x00, 0x7f], и строка в точности совпадает с самим первым байтом;
данные являются строкой, если диапазон первого байта составляет [0x80, 0xb7], и строка, длина которой равна первому байту минус 0x80, следует за первым байтом;
данные являются строкой, если диапазон первого байта составляет [0xb8, 0xbf], и длина строки, длина которой в байтах равна первому байту минус 0xb7, следует за первым байтом, а сама строка следует за длиной строки;
данные являются списком, если диапазон первого байта составляет [0xc0, 0xf7], и конкатенация кодировок RLP всех элементов списка, общая полезная нагрузка которых равна первому байту минус 0xc0, следует за первым байтом;
данные являются списком, если диапазон первого байта составляет [0xf8, 0xff], и общая полезная нагрузка списка, длина которой равна первому байту минус 0xf7, следует за первым байтом, а конкатенация кодировок RLP всех элементов списка следует за общей полезной нагрузкой списка;

В коде это выглядит так:

def rlp_decode(input):
    if len(input) == 0:
        return
    output = ''
    (offset, dataLen, type) = decode_length(input)
    if type is str:
        output = instantiate_str(substr(input, offset, dataLen))
    elif type is list:
        output = instantiate_list(substr(input, offset, dataLen))
    output += rlp_decode(substr(input, offset + dataLen))
    return output

def decode_length(input):
    length = len(input)
    if length == 0:
        raise Exception("input is null")
    prefix = ord(input[0])
    if prefix <= 0x7f:
        return (0, 1, str)
    elif prefix <= 0xb7 and length > prefix - 0x80:
        strLen = prefix - 0x80
        return (1, strLen, str)
    elif prefix <= 0xbf and length > prefix - 0xb7 and length > prefix - 0xb7 + to_integer(substr(input, 1, prefix - 0xb7)):
        lenOfStrLen = prefix - 0xb7
        strLen = to_integer(substr(input, 1, lenOfStrLen))
        return (1 + lenOfStrLen, strLen, str)
    elif prefix <= 0xf7 and length > prefix - 0xc0:
        listLen = prefix - 0xc0;
        return (1, listLen, list)
    elif prefix <= 0xff and length > prefix - 0xf7 and length > prefix - 0xf7 + to_integer(substr(input, 1, prefix - 0xf7)):
        lenOfListLen = prefix - 0xf7
        listLen = to_integer(substr(input, 1, lenOfListLen))
        return (1 + lenOfListLen, listLen, list)
    raise Exception("input does not conform to RLP encoding form")

def to_integer(b):
    length = len(b)
    if length == 0:
        raise Exception("input is null")
    elif length == 1:
        return ord(b[0])
    return ord(substr(b, -1)) + to_integer(substr(b, 0, -1)) * 256