Serializzazione a prefisso di lunghezza ricorsiva (RLP)

La serializzazione a prefisso di lunghezza ricorsiva (RLP) è ampiamente utilizzata nei client di esecuzione di Ethereum. L'RLP standardizza il trasferimento di dati tra i nodi in un formato efficiente in termini di spazio. Lo scopo dell'RLP è codificare array di dati binari nidificati in modo arbitrario, ed è il metodo di codifica principale utilizzato per serializzare gli oggetti nel livello di esecuzione di Ethereum. Lo scopo principale dell'RLP è codificare la struttura; a eccezione degli interi positivi, l'RLP delega la codifica di tipi di dati specifici (es. stringhe, float) a protocolli di ordine superiore. Gli interi positivi devono essere rappresentati in formato binario big-endian senza zeri iniziali (rendendo così il valore intero zero equivalente all'array di byte vuoto). Gli interi positivi deserializzati con zeri iniziali devono essere trattati come non validi da qualsiasi protocollo di ordine superiore che utilizzi l'RLP.

Maggiori informazioni nel Yellow Paper di Ethereum (Appendice B) (opens in a new tab).

Per utilizzare l'RLP per codificare un dizionario, le due forme canoniche suggerite sono:

• usare [[k1,v1],[k2,v2]...] con le chiavi in ordine lessicografico
• usare la codifica di livello superiore Patricia Tree come fa Ethereum

Definizione

La funzione di codifica RLP accetta un elemento. Un elemento è definito come segue:

• una stringa (ovvero, un array di byte) è un elemento
• un elenco di elementi è un elemento
• un intero positivo è un elemento

Ad esempio, tutti i seguenti sono elementi:

• una stringa vuota;
• la stringa contenente la parola "cat";
• un elenco contenente un numero qualsiasi di stringhe;
• e strutture dati più complesse come ["cat", ["puppy", "cow"], "horse", [[]], "pig", [""], "sheep"].
• il numero 100

Nota che nel contesto del resto di questa pagina, per 'stringa' si intende "un certo numero di byte di dati binari"; non vengono utilizzate codifiche speciali e non è implicita alcuna conoscenza del contenuto delle stringhe (salvo quanto richiesto dalla regola contro gli interi positivi non minimi).

La codifica RLP è definita come segue:

• Per un intero positivo, viene convertito nell'array di byte più corto la cui interpretazione big-endian è l'intero, e poi codificato come stringa secondo le regole sottostanti.
• Per un singolo byte il cui valore è nell'intervallo [0x00, 0x7f] (decimale [0, 127]), quel byte è la sua stessa codifica RLP.
• Altrimenti, se una stringa è lunga 0-55 byte, la codifica RLP consiste in un singolo byte con valore 0x80 (dec. 128) più la lunghezza della stringa, seguito dalla stringa. L'intervallo del primo byte è quindi [0x80, 0xb7] (dec. [128, 183]).
• Se una stringa è lunga più 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 formato binario, seguito dalla lunghezza della stringa, seguito dalla stringa. Ad esempio, una stringa lunga 1024 byte verrebbe codificata come \xb9\x04\x00 (dec. 185, 4, 0) seguita dalla stringa. Qui, 0xb9 (183 + 2 = 185) è il primo byte, seguito dai 2 byte 0x0400 (dec. 1024) che denotano la lunghezza della stringa effettiva. L'intervallo del primo byte è quindi [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 (ovvero, la lunghezza combinata di tutti i suoi elementi codificati in RLP) è lungo 0-55 byte, la codifica RLP consiste in un singolo byte con valore 0xc0 più la lunghezza del payload, seguito dalla concatenazione delle codifiche RLP degli elementi. L'intervallo del primo byte è quindi [0xc0, 0xf7] (dec. [192, 247]).
• Se il payload totale di un elenco è lungo più di 55 byte, la codifica RLP consiste in un singolo byte con valore 0xf7 più la lunghezza in byte della lunghezza del payload in formato binario, seguito dalla lunghezza del payload, seguito dalla concatenazione delle codifiche RLP degli elementi. L'intervallo del primo byte è quindi [0xf8, 0xff] (dec. [248, 255]).

In forma sintetica:

• p = payload
• n = lunghezza (numero di byte del payload)
• N = offset della lunghezza della lunghezza (seguono N+1 byte n)

Nel codice, questo è:

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 rappresentazione teorica degli insiemi (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. in base al primo byte (ovvero, il prefisso) dei dati di input e decodificando il tipo di dati, la lunghezza dei dati effettivi e l'offset;

2. in base al tipo e all'offset dei dati, decodificare i dati in modo corrispondente, rispettando la regola di codifica minima per gli interi positivi;

3. continuare a decodificare il resto dell'input;

Tra queste, le regole di decodifica dei tipi di dati e dell'offset sono le seguenti:

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

2. i dati sono una stringa se l'intervallo del primo byte è [0x80, 0xb7], e la stringa la cui lunghezza è uguale 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 è uguale al primo byte meno 0xb7 segue il primo byte, e la stringa segue la lunghezza della stringa;

4. i dati sono un elenco se l'intervallo del primo byte è [0xc0, 0xf7], e la concatenazione delle codifiche RLP di tutti gli elementi dell'elenco il cui payload totale è uguale al primo byte meno 0xc0 segue il primo byte;

5. i dati sono un elenco se l'intervallo del primo byte è [0xf8, 0xff], e il payload totale dell'elenco la cui lunghezza è uguale 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;

Nel codice, questo è:

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)
• Ethereum under the hood: 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)

Argomenti correlati

• Trie di Merkle Patricia