Серіалізація з рекурсивним префіксом довжини (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]).

У стислій формі:

• 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 відбувається так:

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 в Етеріумі (opens in a new tab)
• Етеріум зсередини: RLP (opens in a new tab)
• Coglio, A. (2020). Ethereum's Recursive Length Prefix in ACL2. arXiv preprint arXiv:2009.13769. (opens in a new tab)

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

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