Serialização do prefixo de comprimento recursivo (RLP)

Última edição: @MCreimer(opens in a new tab), 19 de janeiro de 2024

A Serialização do prefixo de comprimento recursivo (RLP) é usado extensivamente nos clientes de execução Ethereum. RLP padroniza a transferência de dados entre nós em um formato eficiente em espaço. O objetivo do RLP é codificar arbitrariamente arrays de dados binários aninhados, e o RLP é o principal método de codificação usado para serializar objetos na camada de execução do Ethereum. O único propósito de RLP é codificar estrutura; codificação de tipos de dados específicos (por exemplo: strings, floats) é deixado para protocolos de ordem superior; mas inteiros de RLP positivos devem ser representados em forma binária big-endian sem zeros à esquerda (tornando assim o valor inteiro zero equivalente ao array de bytes vazio). Inteiros positivos desserializados com zeros à esquerda são tratados como inválidos. A representação de números inteiros do comprimento da string também deve ser codificada desta forma, bem como inteiros no payload.

Mais informações nas páginas amarelas Ethereum (Apêndice B)(opens in a new tab).

Para usar o RLP para codificar um dicionário, as duas formas canônicas são:

usar [[k1,v1],[k2,v2]...] com chaves em ordem lexicográfica
usar a codificação da Árvore Patricia de nível superior como Ethereum faz

Definição

A função de codificação RLP recebe um item. Um item é definido como abaixo：

uma string (ou seja, um byte array) é um item
uma lista de itens é um item

Por exemplo, todos os seguintes são itens:

uma string vazia;
a string que contém a palavra "cat";
uma lista contendo qualquer número de strings;
e uma estrutura de dados mais complexa, como ["cat", ["puppy", "cow"], "horse", [[]], "pig", [""], "sheep"].

Observe que, no contexto do resto desta página, "string" significa "um certo número de bytes de dados binários"; nenhuma codificação especial é usada e nenhum conhecimento sobre o conteúdo das strings está implícito.

A codificação RLP é definida da seguinte forma:

Para um único byte cujo valor está na faixa [0x00, 0x7f] (decimal [0, 127]), este byte é a sua própria codificação RLP.
Caso contrário, se uma string tem de 0 a 55 bytes de comprimento, a codificação RLP consiste em um único byte com valor 0x80 (dec. 128) mais o comprimento da string seguida pela string. O intervalo do primeiro byte é, portanto, [0x80, 0xb7] (dec. [128, 183]).
Se uma string tem mais de 55 bytes de comprimento, a codificação RLP consiste em um único byte com valor 0xb7 (dec. 183) mais o comprimento em bytes do comprimento da sequência de caracteres na forma binária, seguido pelo comprimento da string, seguido pela string. Por exemplo, uma string de 1024 bytes de comprimento seria codificada como \xb9\x04\x00 (dec. 185, 4, 0) seguida pela string. Aqui, 0xb9 (183 + 2 = 185) como o primeiro byte, seguido pelos 2 bytes 0x0400 (dec. 1024) que denotam o comprimento da string real. O intervalo do primeiro byte é, portanto, [0x80, 0xb7] (dec. [184, 191]).
Se o total de carga de uma lista (ou seja, o comprimento combinado de totos os seus itens com codificação RLP) tiver 0 a 55 bytes de comprimento, a codificação RLP consiste em um único byte com valor 0xc0 mais o comprimento da carga seguido da concatenação das codificações dos itens. O intervalo do primeiro byte é, portanto, [0x80, 0xb7] (dec. [192, 247]).
Se o payload total de uma lista tem mais de 55 bytes de comprimento, a codificação RLP consiste em um único byte com valor 0xf7 mais o comprimento em bytes do payload na forma binária, seguida pelo comprimento do payload, seguido pela concatenação das codificações RLP dos itens. O intervalo do primeiro byte é, portanto, [0x80, 0xb7] (dec. [248, 255]).

Em código, isto é:

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("input too long")
19
20def to_binary(x):
21    if x == 0:
22        return ''
23    return to_binary(int(x / 256)) + chr(x % 256)
Exibir tudo
 Copiar

Exemplos

a string "dog" = [ 0x83, 'd', 'o', 'g' ]
a lista [ "cat", "dog" ] = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]
a string vazia ('null') = [ 0x80 ]
a lista vazia = [ 0xc0 ]
o inteiro 0 = [ 0x80 ]
o inteiro codificado 0 ('\x00') = [ 0x00 ]
o inteiro codificado 15 ('\x0f') = [ 0x00 ]
o inteiro codificado 1024 ('\x04') = [ 0x82, 0x04, 0x00 ]
define a representação teórica(opens in a new tab) para três, [ [], [[]], [ [], [[]] ] ] = [ 0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc0, 0xc1, 0xc0 ]
a string "Lorem ipsum dolor sit amet, consectetur adipisicing elit" = [ 0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't' ]

Decodificação RLP

De acordo com as regras e o processo de codificação RLP, a entrada da decodificação RLP é considerada uma matriz de dados binários. O processo de decodificação do RLP é o seguinte:

de acordo com o primeiro byte (ou seja, o prefixo) dos dados de entrada e a decodificação do tipo de dados, o comprimento do dado em si e deslocamento;
de acordo com o tipo e o deslocamento de dados, decodificar os dados correspondentemente;
continue a decodificar o resto da entrada;

Entre elas, as regras de decodificação de tipos de dados e deslocamento são as seguintes:

os dados são uma string se a faixa do primeiro byte (por exemplo, prefixo) é [0x00, 0x7f], e a string é exatamente o primeiro byte;
o dado é uma string se o intervalo do primeiro byte é [0x80, 0xb7], e a string cujo comprimento é igual ao primeiro byte menos 0x80 segue o primeiro byte;
os dados são uma string se o intervalo do primeiro byte é [0xb8, 0xbf] e o comprimento da string cujo comprimento em bytes é igual ao primeiro byte menos 0xb7 segue primeiro byte, e a cadeia de caracteres segue o comprimento da string;
os dados são uma lista se o intervalo do primeiro byte é [0xc0, 0xf7], e a concatenação das codificações RLP de todos os itens da lista que a carga total é igual ao primeiro byte menos 0xc0 e segue o primeiro byte;
os dados são uma string se o intervalo do primeiro byte é [0xb8, 0xbf], e o payload total da lista cujo comprimento é igual ao primeiro byte menos 0xf7 segue o primeiro byte, e a concatenação das codificações RLP de todos os itens da lista segue o payload total da lista;

Em código, isto é:

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("input is 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("input does not conform to RLP encoding form")
35
36def to_integer(b):
37    length = len(b)
38    if length == 0:
39        raise Exception("input is null")
40    elif length == 1:
41        return ord(b[0])
42    return ord(substr(b, -1)) + to_integer(substr(b, 0, -1)) * 256
Exibir tudo
 Copiar

Leitura adicional

Árvore Patricia Merkle

back-to-top ↑