Merkle Patricia Trie

Lo stato di Ethereum (la totalità di tutti gli account, i saldi e i contratti intelligenti) è codificato in una versione speciale della struttura dati nota generalmente in informatica come Albero di Merkle (Merkle Tree). Questa struttura è utile per molte applicazioni nella crittografia perché crea una relazione verificabile tra tutti i singoli pezzi di dati intrecciati nell'albero, risultando in un singolo valore radice (root) che può essere utilizzato per dimostrare cose sui dati.

La struttura dati di Ethereum è un 'Merkle-Patricia Trie modificato', chiamato così perché prende in prestito alcune caratteristiche di PATRICIA (Practical Algorithm To Retrieve Information Coded in Alphanumeric), e perché è progettato per un efficiente recupero (retrieval) dei dati degli elementi che compongono lo stato di Ethereum.

Un trie Merkle-Patricia è deterministico e crittograficamente verificabile: l'unico modo per generare una radice di stato è calcolarla da ogni singolo pezzo dello stato, e due stati identici possono essere facilmente dimostrati tali confrontando l'hash radice e gli hash che vi hanno portato (una prova di Merkle). Al contrario, non c'è modo di creare due stati diversi con lo stesso hash radice, e qualsiasi tentativo di modificare lo stato con valori diversi risulterà in un hash radice di stato diverso. Teoricamente, questa struttura fornisce il 'Santo Graal' dell'efficienza O(log(n)) per inserimenti, ricerche ed eliminazioni.

Nel prossimo futuro, Ethereum prevede di migrare a una struttura Verkle Tree, che aprirà molte nuove possibilità per futuri miglioramenti del protocollo.

Prerequisiti

Per comprendere meglio questa pagina, sarebbe utile avere una conoscenza di base di hash (opens in a new tab), alberi di Merkle (opens in a new tab), trie (opens in a new tab) e serializzazione (opens in a new tab). Questo articolo inizia con una descrizione di un albero radix (opens in a new tab) di base, per poi introdurre gradualmente le modifiche necessarie per la struttura dati più ottimizzata di Ethereum.

Trie radix di base

In un trie radix di base, ogni nodo si presenta come segue:

1    [i_0, i_1 ... i_n, value]

Dove i_0 ... i_n rappresentano i simboli dell'alfabeto (spesso binario o esadecimale), value è il valore terminale nel nodo, e i valori negli slot i_0, i_1 ... i_n sono NULL o puntatori a (nel nostro caso, hash di) altri nodi. Questo forma un archivio (chiave, valore) di base.

Supponiamo di voler utilizzare una struttura dati ad albero radix per persistere un ordine su un insieme di coppie chiave-valore. Per trovare il valore attualmente mappato alla chiave dog nel trie, dovresti prima convertire dog in lettere dell'alfabeto (ottenendo 64 6f 67), e poi scendere nel trie seguendo quel percorso fino a trovare il valore. Ovvero, inizi cercando l'hash radice in un DB chiave/valore piatto per trovare il nodo radice del trie. È rappresentato come un array di chiavi che puntano ad altri nodi. Useresti il valore all'indice 6 come chiave e lo cercheresti nel DB chiave/valore piatto per ottenere il nodo di un livello inferiore. Poi sceglieresti l'indice 4 per cercare il valore successivo, poi l'indice 6, e così via, finché, una volta seguito il percorso: root -> 6 -> 4 -> 6 -> 15 -> 6 -> 7, cercheresti il valore del nodo e restituiresti il risultato.

C'è una differenza tra cercare qualcosa nel 'trie' e nel 'DB' chiave/valore piatto sottostante. Entrambi definiscono disposizioni chiave/valore, ma il DB sottostante può eseguire una tradizionale ricerca in 1 passaggio di una chiave. Cercare una chiave nel trie richiede molteplici ricerche nel DB sottostante per arrivare al valore finale descritto sopra. Riferiamoci a quest'ultimo come a un percorso (path) per eliminare l'ambiguità.

Le operazioni di aggiornamento ed eliminazione per i trie radix possono essere definite come segue:

1    def update(node_hash, path, value):
2        curnode = db.get(node_hash) if node_hash else [NULL] * 17
3        newnode = curnode.copy()
4        if path == "":
5            newnode[-1] = value
6        else:
7            newindex = update(curnode[path[0]], path[1:], value)
8            newnode[path[0]] = newindex
9        db.put(hash(newnode), newnode)
10        return hash(newnode)
11
12    def delete(node_hash, path):
13        if node_hash is NULL:
14            return NULL
15        else:
16            curnode = db.get(node_hash)
17            newnode = curnode.copy()
18            if path == "":
19                newnode[-1] = NULL
20            else:
21                newindex = delete(curnode[path[0]], path[1:])
22                newnode[path[0]] = newindex
23
24            if all(x is NULL for x in newnode):
25                return NULL
26            else:
27                db.put(hash(newnode), newnode)
28                return hash(newnode)
Mostra tutto

Un albero Radix "Merkle" è costruito collegando i nodi utilizzando digest di hash crittografici generati in modo deterministico. Questo indirizzamento basato sul contenuto (nel DB chiave/valore key == keccak256(rlp(value))) fornisce una garanzia di integrità crittografica dei dati memorizzati. Se l'hash radice di un dato trie è noto pubblicamente, chiunque abbia accesso ai dati foglia sottostanti può costruire una prova che il trie include un dato valore in un percorso specifico fornendo gli hash di ciascun nodo che unisce un valore specifico alla radice dell'albero.

È impossibile per un utente malintenzionato fornire una prova di una coppia (percorso, valore) che non esiste poiché l'hash radice si basa in ultima analisi su tutti gli hash sottostanti. Qualsiasi modifica sottostante cambierebbe l'hash radice. Puoi pensare all'hash come a una rappresentazione compressa delle informazioni strutturali sui dati, protetta dalla protezione della pre-immagine della funzione di hashing.

Ci riferiremo a un'unità atomica di un albero radix (ad es., un singolo carattere esadecimale o un numero binario a 4 bit) come a un "nibble". Durante l'attraversamento di un percorso un nibble alla volta, come descritto sopra, i nodi possono riferirsi al massimo a 16 figli ma includono un elemento value. Pertanto, li rappresentiamo come un array di lunghezza 17. Chiamiamo questi array di 17 elementi "nodi ramo" (branch nodes).

I trie radix hanno una limitazione principale: sono inefficienti. Se si desidera memorizzare un'associazione (percorso, valore) in cui il percorso, come in Ethereum, è lungo 64 caratteri (il numero di nibble in bytes32), avremo bisogno di oltre un kilobyte di spazio extra per memorizzare un livello per carattere, e ogni ricerca o eliminazione richiederà tutti i 64 passaggi. Il trie Patricia introdotto di seguito risolve questo problema.

Ottimizzazione

Un nodo in un Merkle Patricia trie è uno dei seguenti:

NULL (rappresentato come stringa vuota)
branch (ramo) Un nodo di 17 elementi [ v0 ... v15, vt ]
leaf (foglia) Un nodo di 2 elementi [ encodedPath, value ]
extension (estensione) Un nodo di 2 elementi [ encodedPath, key ]

Con percorsi di 64 caratteri è inevitabile che, dopo aver attraversato i primi livelli del trie, si raggiunga un nodo in cui non esiste alcun percorso divergente per almeno una parte della discesa. Per evitare di dover creare fino a 15 nodi NULL sparsi lungo il percorso, abbreviamo la discesa impostando un nodo extension della forma [ encodedPath, key ], dove encodedPath contiene il "percorso parziale" per saltare in avanti (utilizzando una codifica compatta descritta di seguito), e la key serve per la successiva ricerca nel DB.

Per un nodo leaf, che può essere contrassegnato da un flag nel primo nibble dell'encodedPath, il percorso codifica tutti i frammenti di percorso del nodo precedente e possiamo cercare direttamente il value.

Questa ottimizzazione, tuttavia, introduce ambiguità.

Quando si attraversano percorsi in nibble, potremmo ritrovarci con un numero dispari di nibble da attraversare, ma poiché tutti i dati sono memorizzati in formato bytes, non è possibile distinguere tra, ad esempio, il nibble 1 e i nibble 01 (entrambi devono essere memorizzati come <01>). Per specificare la lunghezza dispari, il percorso parziale è preceduto da un flag.

Specifica: Codifica compatta di sequenza esadecimale con terminatore opzionale

La segnalazione sia della lunghezza del percorso parziale rimanente dispari vs. pari sia del nodo foglia vs. estensione come descritto sopra risiede nel primo nibble del percorso parziale di qualsiasi nodo a 2 elementi. Risultano in quanto segue:

carattere esadecimale	bit	tipo di nodo parziale	lunghezza del percorso
0	0000	estensione	pari
1	0001	estensione	dispari
2	0010	terminante (foglia)	pari
3	0011	terminante (foglia)	dispari

Per la lunghezza del percorso rimanente pari (0 o 2), seguirà sempre un altro nibble di "riempimento" (padding) 0.

1    def compact_encode(hexarray):
2        term = 1 if hexarray[-1] == 16 else 0
3        if term:
4            hexarray = hexarray[:-1]
5        oddlen = len(hexarray) % 2
6        flags = 2 * term + oddlen
7        if oddlen:
8            hexarray = [flags] + hexarray
9        else:
10            hexarray = [flags] + [0] + hexarray
11        # hexarray ora ha una lunghezza pari il cui primo nibble rappresenta i flag.
12        o = ""
13        for i in range(0, len(hexarray), 2):
14            o += chr(16 * hexarray[i] + hexarray[i + 1])
15        return o
Mostra tutto

Esempi:

1    > [1, 2, 3, 4, 5, ...]
2    '11 23 45'
3    > [0, 1, 2, 3, 4, 5, ...]
4    '00 01 23 45'
5    > [0, f, 1, c, b, 8, 10]
6    '20 0f 1c b8'
7    > [f, 1, c, b, 8, 10]
8    '3f 1c b8'

Ecco il codice esteso per ottenere un nodo nel Merkle Patricia trie:

1    def get_helper(node_hash, path):
2        if path == []:
3            return node_hash
4        if node_hash == "":
5            return ""
6        curnode = rlp.decode(node_hash if len(node_hash) < 32 else db.get(node_hash))
7        if len(curnode) == 2:
8            (k2, v2) = curnode
9            k2 = compact_decode(k2)
10            if k2 == path[: len(k2)]:
11                return get(v2, path[len(k2) :])
12            else:
13                return ""
14        elif len(curnode) == 17:
15            return get_helper(curnode[path[0]], path[1:])
16
17    def get(node_hash, path):
18        path2 = []
19        for i in range(len(path)):
20            path2.push(int(ord(path[i]) / 16))
21            path2.push(ord(path[i]) % 16)
22        path2.push(16)
23        return get_helper(node_hash, path2)
Mostra tutto

Esempio di Trie

Supponiamo di volere un trie contenente quattro coppie percorso/valore ('do', 'verb'), ('dog', 'puppy'), ('doge', 'coins'), ('horse', 'stallion').

Per prima cosa, convertiamo sia i percorsi che i valori in bytes. Di seguito, le rappresentazioni effettive in byte per i percorsi sono indicate da <>, sebbene i valori siano ancora mostrati come stringhe, indicati da '', per una più facile comprensione (anche loro, in realtà, sarebbero bytes):

1    <64 6f> : 'verb'
2    <64 6f 67> : 'puppy'
3    <64 6f 67 65> : 'coins'
4    <68 6f 72 73 65> : 'stallion'

Ora, costruiamo un tale trie con le seguenti coppie chiave/valore nel DB sottostante:

1    rootHash: [ <16>, hashA ]
2    hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, [ <20 6f 72 73 65>, 'stallion' ], <>, <>, <>, <>, <>, <>, <>, <> ]
3    hashB:    [ <00 6f>, hashC ]
4    hashC:    [ <>, <>, <>, <>, <>, <>, hashD, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
5    hashD:    [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coins' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]

Quando un nodo è referenziato all'interno di un altro nodo, ciò che viene incluso è keccak256(rlp.encode(node)), se len(rlp.encode(node)) >= 32 altrimenti node dove rlp.encode è la funzione di codifica RLP.

Nota che quando si aggiorna un trie, è necessario memorizzare la coppia chiave/valore (keccak256(x), x) in una tabella di ricerca persistente se il nodo appena creato ha una lunghezza >= 32. Tuttavia, se il nodo è più corto, non è necessario memorizzare nulla, poiché la funzione f(x) = x è reversibile.

Trie in Ethereum

Tutti i trie di Merkle nel livello di esecuzione di Ethereum utilizzano un Merkle Patricia Trie.

Dall'intestazione di un blocco ci sono 3 radici da 3 di questi trie.

stateRoot
transactionsRoot
receiptsRoot

Trie di Stato

Esiste un trie di stato globale, e viene aggiornato ogni volta che un client elabora un blocco. In esso, un percorso è sempre: keccak256(ethereumAddress) e un valore è sempre: rlp(ethereumAccount). Più specificamente, un account Ethereum è un array di 4 elementi di [nonce,balance,storageRoot,codeHash]. A questo punto, vale la pena notare che questo storageRoot è la radice di un altro trie patricia:

Trie di Archiviazione

Il trie di archiviazione è dove risiedono tutti i dati del contratto. Esiste un trie di archiviazione separato per ogni account. Per recuperare i valori in posizioni di archiviazione specifiche a un dato indirizzo, sono richiesti l'indirizzo di archiviazione, la posizione intera dei dati memorizzati nell'archiviazione e l'ID del blocco. Questi possono poi essere passati come argomenti a eth_getStorageAt definito nell'API JSON-RPC, ad es., per recuperare i dati nello slot di archiviazione 0 per l'indirizzo 0x295a70b2de5e3953354a6a8344e616ed314d7251:

curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x0", "latest"], "id": 1}' localhost:8545
{"jsonrpc":"2.0","id":1,"result":"0x00000000000000000000000000000000000000000000000000000000000004d2"}

Il recupero di altri elementi nell'archiviazione è leggermente più complesso perché la posizione nel trie di archiviazione deve prima essere calcolata. La posizione è calcolata come l'hash keccak256 dell'indirizzo e della posizione di archiviazione, entrambi riempiti a sinistra con zeri fino a una lunghezza di 32 byte. Ad esempio, la posizione per i dati nello slot di archiviazione 1 per l'indirizzo 0x391694e7e0b0cce554cb130d723a9d27458f9298 è:

1keccak256(decodeHex("000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"))

In una console Geth, questo può essere calcolato come segue:

1> var key = "000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"
2undefined
3> web3.sha3(key, {"encoding": "hex"})
4"0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9"

Il percorso è quindi keccak256(<6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9>). Questo può ora essere utilizzato per recuperare i dati dal trie di archiviazione come prima:

curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9", "latest"], "id": 1}' localhost:8545
{"jsonrpc":"2.0","id":1,"result":"0x000000000000000000000000000000000000000000000000000000000000162e"}

Nota: lo storageRoot per un account Ethereum è vuoto per impostazione predefinita se non è un account di contratto.

Trie delle Transazioni

Esiste un trie delle transazioni separato per ogni blocco, che memorizza nuovamente coppie (chiave, valore). Un percorso qui è: rlp(transactionIndex) che rappresenta la chiave che corrisponde a un valore determinato da:

1if legacyTx:
2  value = rlp(tx)
3else:
4  value = TxType | encode(tx)

Maggiori informazioni su questo possono essere trovate nella documentazione dell'EIP 2718 (opens in a new tab).

Trie delle Ricevute

Ogni blocco ha il proprio trie delle Ricevute. Un percorso qui è: rlp(transactionIndex). transactionIndex è il suo indice all'interno del blocco in cui è stato incluso. Il trie delle ricevute non viene mai aggiornato. Similmente al trie delle Transazioni, ci sono ricevute attuali e legacy. Per interrogare una ricevuta specifica nel trie delle Ricevute, sono richiesti l'indice della transazione nel suo blocco, il payload della ricevuta e il tipo di transazione. La ricevuta restituita può essere di tipo Receipt che è definita come la concatenazione di TransactionType e ReceiptPayload o può essere di tipo LegacyReceipt che è definita come rlp([status, cumulativeGasUsed, logsBloom, logs]).

Maggiori informazioni su questo possono essere trovate nella documentazione dell'EIP 2718 (opens in a new tab).

Merkle Patricia Trie

Prerequisiti

Trie radix di base