Serializzazione a prefisso di lunghezza ricorsiva (RLP)

Ultima modifica: @GiorgioHerbie(opens in a new tab), Invalid DateTime

La serializzazione a prefisso di lunghezza ricorsiva (RLP) è usata ampiamente nei client d'esecuzione di Ethereum. L’RLP standardizza il trasferimento di dati tra nodi in un formato efficiente a livello di spazio. Lo scopo dell’RLP è codificare arbitrariamente gli insiemi di dati binari nidificati e l’RLP è il metodo di codifica principale usato per serializzare gli oggetti nel livello d'esecuzione di Ethereum. Il solo scopo dell’RLP è codificare la struttura; la codifica di tipi di dati specifici (es. stringhe, float) è lasciata a protocolli di ordine superiore; ma gli interi RLP positivi devono essere rappresentati in forma binaria big-endian senza zero iniziali (dunque rendendo il valore intero zero equivalente all'array di byte vuoto). Gli interi positivi deserializzati con zeri iniziali sono trattati come non validi. La rappresentazione integrale della lunghezza della stringa deve essere anch'essa codificata in questo modo, così come gli interi nel payload.

Per maggiori informazioni, consultare lo yellowpaper di Ethereum (Appendice B)(opens in a new tab).

Per usare l’RLP per codificare un dizionario, le due forme canoniche suggerite sono:

usare [[k1,v1],[k2,v2]...] con i tasti in ordine lessicografico
usare la codifica dell'Albero di Patricia di livello superiore come fa Ethereum

Definizione

La codifica RLP prende un elemento. Un elemento è definito come segue:

una stringa (ovvero insieme di byte) è un elemento
un elenco di elementi è un elemento

Ad esempio, tutti i seguenti sono elementi:

una stringa vuota;
la stringa contenente la parola "gatto";
un elenco contenente qualsiasi numero di stringhe;
e strutture di dati più complesse come ["gatto", ["cucciolo", "vacca"], "cavallo", [[]], "maiale", [""], "pecora"].

Nota che nel resto di questa pagina, “stringa” indica "un certo numero di byte di dati binari"; non è usata alcuna codifica speciale e non è richiesta implicitamente alcuna conoscenza sul contenuto delle stringhe.

La codifica RLP è definita come segue:

Per un singolo byte il cui valore è nell'intervallo [0x00, 0x7f] (decimale [0, 127]), quel byte è la propria codifica RLP.
Altrimenti, se una stringa è lunga da 0 a 55 byte, la codifica RLP consiste in un singolo byte con valore 0x80 (dec. 128) più la lunghezza della stringa seguita dalla stringa. L'intervallo del primo byte è dunque [0x80, 0xb7] (dec. [128, 183]).
Se una stringa è più lunga di 55 byte, la codifica RLP consiste in un singolo byte con valore 0xb7 (dec. 183) più la lunghezza in byte della lunghezza della stringa in forma binaria, seguita dalla lunghezza della stringa, seguita dalla stringa. Ad esempio, una stringa lunga 1024 byte sarebbe codificata come \xb9\x04\x00 (dec. 185, 4, 0), seguita dalla stringa. Qui, 0xb9 (183 + 2 = 185) come primo byte, seguito dai 2 byte 0x0400 (dec. 1024) che denotano la lunghezza della stringa effettiva. L'intervallo del primo byte è dunque [0xb8, 0xbf] (dec. [184, 191]).
Se il payload totale di una lista (es., la lunghezza combinata di tutti i suoi elementi codificata in RLP) è lungo da 0 a 55 byte, la codifica RLP consiste in un singolo byte con valore 0xc0, oltre alla lunghezza dell'elenco seguita dalla concatenazione delle codifiche RLP degli elementi. L'intervallo del primo byte è dunque [0xc0, 0xf7] (dec. [192, 247]).
Se il carico utile totale di un elenco è più lungo di 55 byte, la codifica RLP consiste in un singolo byte con valore oxf7, più la lunghezza in byte della lunghezza del payload in forma binaria, seguita dalla lunghezza del carico utile, seguita dalla concatenazione delle codifiche RLP degli elementi. L'intervallo del primo byte è dunque [0xf8, 0xff] (dec. [248, 255]).

In codice è:

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)
Mostra tutto
 Copia

Esempi

la stringa "dog" = [ 0x83, 'd', 'o', 'g' ]
l'elenco [ "cat", "dog" ] = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]
la stringa vuota (“null”) = [ 0x80 ]
l'elenco vuoto = [ 0xc0 ]
l'intero 0 = [ 0x80 ]
l'intero codificato 0 ('\x00') = [ 0x00 ]
l'intero codificato 15 ('\x0f') = [ 0x0f ]
l'intero codificato 1024 ('\x04\x00') = [ 0x82, 0x04, 0x00 ]
la data rappresentazione teorica(opens in a new tab) di tre, [ [], [[]], [ [], [[]] ] ] = [ 0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0 ]
la stringa "Lorem ipsum dolor sit amet, consectetur adipisicing elit" = [ 0xb8, 0x38, 'L', 'o', 'r', 'e', 'm', ' ', ... , 'e', 'l', 'i', 't' ]

Decodifica RLP

Secondo le regole e il processo della codifica RLP, l'input della decodifica RLP è considerato come un array di dati binari. Il processo di decodifica RLP è il seguente:

a seconda del primo byte (ovvero il prefisso) dei dati di input e decodificando il tipo di dati, la lunghezza dei dati effettivi e l'offset;
a seconda del tipo e l'offset dei dati, decodifica i dati di conseguenza;
continua a decodificare il resto dell'input;

Tra loro, le regole per decodificare i tipi di dati e offset sono le seguenti:

i dati sono una stringa se l'intervallo del primo byte (prefisso) è [0x00, 0x7f] e la stringa corrisponde esattamente al primo byte;
i dati sono una stringa se l'intervallo del primo byte è [0x80, 0xb7] e la stringa la cui lunghezza è pari al primo byte meno 0x80 segue il primo byte;
i dati sono una stringa se l'intervallo del primo byte è [0xb8, 0xbf] e la lunghezza della stringa la cui lunghezza in byte è pari al primo byte meno 0xb7 segue il primo byte, e la stringa segue la lunghezza della stringa;
i dati sono una lista se l'intervallo del primo byte è [0xc0, 0xf7] e la concatenazione delle codifiche RLP di tutti gli elementi della lista in cui il payload totale è uguale al primo byte meno 0xc0 segue il primo byte;
i dati sono una lista se l'intervallo del primo byte è [0xf8, 0xff] e il payload totale dell'elenco la cui lunghezza equivale al primo byte meno 0xf7 segue il primo byte e la concatenazione delle codifiche RLP di tutti gli elementi dell'elenco segue il payload totale dell'elenco;

In codice è:

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
Mostra tutto
 Copia

Letture consigliate

Trie di Patricia Merkle

back-to-top ↑