Серіалізація за допомогою рекурсивного префікса довжини (RLP)

Серіалізація з префіксом рекурсивної довжини (RLP) широко використовується у виконавчих клієнтах Ethereum. RLP стандартизує передачу даних між вузлами у форматі, що заощаджує простір. Мета RLP — кодувати довільно вкладені масиви двійкових даних, і RLP є основним методом кодування, що використовується для серіалізації об'єктів у виконавчому рівні Ethereum. Основна мета RLP — кодувати структуру; за винятком додатних цілих чисел, RLP делегує кодування конкретних типів даних (наприклад, рядків, чисел з плаваючою комою) протоколам вищого порядку. Додатні цілі числа мають бути представлені у двійковій формі з порядком байтів від старшого до молодшого (big-endian) без початкових нулів (таким чином, ціле значення нуль еквівалентне порожньому масиву байтів). Десеріалізовані додатні цілі числа з початковими нулями повинні розглядатися як недійсні будь-яким протоколом вищого порядку, що використовує 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]).

У коді це виглядає так:

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 виглядає наступним чином:

1. відповідно до першого байта (тобто префікса) вхідних даних і декодування типу даних, довжини фактичних даних і зсуву;

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

3. продовжити декодування решти вхідних даних;

Серед них правила декодування типів даних та зсуву є наступними:

1. дані є рядком, якщо діапазон першого байта (тобто префікса) становить [0x00, 0x7f], і рядок — це точно сам перший байт;

2. дані є рядком, якщо діапазон першого байта становить [0x80, 0xb7], і рядок, довжина якого дорівнює першому байту мінус 0x80, слідує за першим байтом;

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

4. дані є списком, якщо діапазон першого байта становить [0xc0, 0xf7], а об’єднання RLP-кодувань усіх елементів списку, загальний обсяг корисного навантаження якого дорівнює першому байту мінус 0xc0, слідує за першим байтом;

5. дані є списком, якщо діапазон першого байта становить [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

Для подальшого читання

• RLP в Ethereum (opens in a new tab)
• Ethereum під капотом: RLP (opens in a new tab)
• Coglio, A. (2020). Рекурсивний префікс довжини Ethereum в ACL2. arXiv preprint arXiv:2009.13769. (opens in a new tab)

Пов'язані теми

• Дерево Патриції-Меркла