Serializzazione a prefisso di lunghezza ricorsiva (RLP)

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. Lo scopo principale dell'RLP è codificare la struttura; con l'eccezione degli interi positivi, l'RLP delega la codifica dei tipi di dati specifici (es.,stringhe, virgola mobile) a protocolli di ordine superiore. Gli interi positivi devono essere rappresentati in forma binaria big-endian senza zeri iniziali (rendendo il valore intero zero equivalente all'array di byte vuoto). Gli interi positivi deserializzati con zero iniziali devono essere trattati come non validi da qualsiasi protocollo di ordine superiore che utilizzi l'RLP.

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
• un intero posiitivo è 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"].
• il numero 100

Nota che, nel contesto del resto di questa pagina, 'stringa' significa "un certo numero di byte di dati binari"; non è utilizzata alcuna codifica speciale, e non è implicata alcuna conoscenza sul contenuto delle stringhe (tranne come richiesto dalla regola contro gli interi positivi non minimali).

La codifica RLP è definita come segue:

• Per un intero positivo, è convertito al più breve array di byte la cui interpretazione big-endian sia l'intero, quindi, e quindi codificato come una stringa secondo le seguenti regole.
• 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 una stringa è lunga 2^64 byte o più, potrebbe non essere codificata.
• Se il payload totale di un elenco (cioè la lunghezza combinata di tutti i suoi elementi codificati in RLP) è lunga da 0 a 55 byte, la codifica RLP consiste in un singolo byte dal valore 0xc0, più la lunghezza del payload, 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 ]
• il byte '\x00' = [ 0x00 ]
• il byte '\x0f' = [ 0x0f ]
• i byte '\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:

1. 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;

2. secondo il tipo e lo scostamento dei dati, decodificali di conseguenza, rispettando la regola di codifica minimale per gli interi positivi;

3. continua a decodificare il resto dell'input;

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

1. i dati sono una stringa se l'intervallo del primo byte (prefisso) è [0x00, 0x7f] e la stringa corrisponde esattamente al primo byte;

2. 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;

3. 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;

4. 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;

5. 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

• RLP in Ethereum(opens in a new tab)
• Dietro le quinte di Ethereum: RLP(opens in a new tab)
• Coglio, A. (2020). Prefisso di Lunghezza Ricorsiva di Ethereum in ACL2. arXiv preprint arXiv:2009.13769.(opens in a new tab)

Argomenti correlati

• Trie di Patricia Merkle