Serialización de prefijo de longitud recursiva (RLP)

La serialización de prefijo de longitud recursiva (RLP) se utiliza ampliamente en los clientes de ejecución de Ethereum. El RLP estandariza la transferencia de datos entre nodos en un formato de uso de espacio eficiente. El propósito de RLP es codificar matrices anidadas arbitrariamente de datos binarios, y RLP es el método de codificación principal utilizado para serializar objetos en la capa de ejecución de Ethereum. El propósito principal de RLP es codificar estructuras, con la excepción de enteros positivos, RLP delega la codificación de tipos de datos específicos (p. ej., strings, floats) a protocolos de mayor orden. Los enteros positivos deben representarse en forma binaria big-endian sin ceros iniciales (lo que hace que el valor entero cero sea equivalente a la matriz de bytes vacía). Los enteros positivos deserializados con ceros iniciales deben ser tratados como no válidos por cualquier protocolo de alto orden que utilice RLP.

Consulte más información en La hoja amarilla de Ethereum (Apéndice B)(opens in a new tab).

Para usar RLP para codificar un diccionario, las dos formas canónicas sugeridas son:

• usar [[k1,v1],[k2,v2]...] con claves en orden lexicográfico
• usar la codificación de Patricia Tree de nivel superior como lo hace Ethereum

Definición

La función de codificación RLP toma un elemento. Un elemento se define de la siguiente manera：

• una cadena (es decir, una matriz de bytes) es un elemento
• una lista de elementos es un elemento
• un entero positivo es un elemento

Por ejemplo, todos los siguientes son elementos:

• una cadena vacía;
• la cadena que contiene la palabra "gato";
• una lista que contiene cualquier número de cadenas;
• y estructuras de datos más complejas como ["gato", ["cachorro", "vaca"], "caballo", [[]], "cerdo", [""], "oveja"].
• el número 100

Nótese que, en el contexto del resto de esta página, "string" se refiere a "cierta cantidad de bytes de datos binarios"; no se usan codificaciones especiales ni se implica conocimiento del contenido de las strings (excepto según lo requiera la regla contra enteros positivos no mínimos).

La codificación RLP se define de la siguiente manera:

• En el caso de un entero positivo, se lo convierte al array de bytes más corto cuya interpretación big endian es el entero y luego se codifica como una string según las reglas siguientes.
• Para un solo byte cuyo valor esté en el rango [0x00, 0x7f] (decimal [0, 127]), ese byte es su propia codificación RLP.
• De lo contrario, si una cadena tiene una longitud de 0-55 bytes, la codificación RLP consta de un solo byte con el valor 0x80 (dec. 128) más la longitud de la cadena seguida de la cadena. Por lo tanto, el rango del primer byte es [0x80, 0xb7] (dec. [128, 183]).
• Si una cadena tiene más de 55 bytes de largo, la codificación RLP consta de un solo byte con el valor 0xb7 (dec. 183) más la longitud en bytes de la longitud de la cadena en forma binaria, seguida de la longitud de la cadena, seguida de la cadena. Por ejemplo, una cadena de 1024 bytes de largo se codificaría como \xb9\x04\x00 (dec. 185, 4, 0) seguido de la cadena. Aquí, 0xb9 (183 + 2 = 185) como el primer byte, seguido de los 2 bytes 0x0400 (dec. 1024) que denotan la longitud de la cadena real. El rango del primer byte es, por lo tanto, [0xb8, 0xbf] (dec. [184, 191]).
• Si una string tiene una longitud mayor o igual a 2^64 bytes, no puede ser codificada.
• Si la carga útil total de una lista (es decir, la longitud combinada de todos sus elementos codificados con RLP) es de 0-55 bytes, la codificación RLP consta de un solo byte con un valor 0xc0 más la longitud de la lista, seguida de la concatenación de las codificaciones RLP de los elementos. Por lo tanto, el rango del primer byte es [0xc0, 0xf7] (dec. [192, 247]).
• Si la carga útil total de una lista tiene más de 55 bytes de longitud, la codificación RLP consta de un solo byte con un valor 0xf7 más la longitud en bytes de la longitud de la carga útil en forma binaria, seguida de la longitud de la carga útil, seguida de la concatenación de las codificaciones RLP de los elementos. Por lo tanto, el rango del primer byte es [0xf8, 0xff] (dec. [248, 255]).

En el código, esto es:

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)
Mostrar todo
 Copiar

Ejemplos

• la cadena "dog" = [ 0x83, 'd', 'o', 'g' ]
• la lista [ "cat", "dog" ] = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]
• la cadena vacía ("null") = [ 0x80 ]
• la lista vacía = [ 0xc0 ]
• el entero 0 = [ 0x80 ]
• el byte '\x00' = [ 0x00 ]
• el byte '\x0f' = [ 0x0f ]
• los bytes '\x04\x00' = [ 0x82, 0x04, 0x00 ]
• la representación teórica de conjunto(opens in a new tab) de tres, [ [], [[]], [], [[]] ] ] = [ 0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0 ]
• la cadena "Lorem ipsum dolor sit amet, consectetur adipisicing elit" = [ 0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't' ]

Decodificación RLP

De acuerdo con las reglas y el proceso de codificación RLP, la entrada de la decodificación RLP se considera una matriz de datos binarios. El proceso de decodificación RLP es el siguiente:

1. de acuerdo con el primer byte (es decir, el prefijo) de los datos de entrada y la decodificación del tipo de datos, la longitud de los datos reales y el desplazamiento;

2. de acuerdo con el tipo y offset de datos, decodificar los datos según corresponda, respetando la regla de codificación mínima para enteros positivos;

3. continuar decodificando el resto de la entrada.

Entre ellos, las reglas de decodificación de tipos de datos y desplazamiento son las siguientes:

1. los datos son una cadena si el rango del primer byte (es decir, el prefijo) es [0x00, 0x7f], y la cadena es exactamente el primer byte en sí;

2. los datos son una cadena si el rango del primer byte es [0x80, 0xb7], y la cadena cuya longitud es igual al primer byte menos 0x80 sigue al primer byte;

3. los datos son una cadena si el rango del primer byte es [0xb8, 0xbf], y la longitud de la cadena cuya longitud en bytes es igual al primer byte menos 0xb7 sigue al primer byte, y la cadena sigue la longitud de la cadena;

4. los datos son una lista si el rango del primer byte es [0xc0, 0xf7], y la concatenación de las codificaciones RLP de todos los elementos de la lista cuya carga útil total es igual al primer byte menos 0xc0 sigue al primer byte;

5. los datos son una lista si el rango del primer byte es [0xf8, 0xff], y la carga útil total de la lista cuya longitud es igual al primer byte menos 0xf7 sigue al primer byte, y la concatenación de las codificaciones RLP de todos los elementos de la lista sigue la carga útil total de la lista;

En el código, esto es:

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
Mostrar todo
 Copiar

Más información

• RLP en Ethereum(opens in a new tab)
• Ethereum bajo el capó: RLP(opens in a new tab)
• Coglio, A. (2020). Prefijo de longitud recursiva de Ethereum en ACL2. arXiv preprint arXiv:2009.13769.(opens in a new tab)

Temas relacionados

• Patricia merkle trie