Alberi di Patricia Merkle

Ultima modifica: , Invalid DateTime

Un Trie di Patricia Merkle fornisce una struttura di dati autenticata crittograficamente, utilizzabile per memorizzare tutte le coppie (chiave, valore) .

I Trie di Patricia Merkle sono completamente deterministici, quindi è garantito che un trie con le stesse coppie (chiave, valore) sia identico, fino all'ultimo byte. Ciò significa che hanno lo stesso hash di root, fornendo così il sacro graal dell'efficienza di O(log(n)) per inserimenti, ricerche ed eliminazioni. Inoltre, sono più semplici da comprendere e programmare rispetto ad alternative più complesse basate sul confronto, come gli alberi rosso-neri.

Prerequisiti

Per comprendere questa pagina è utile avere una conoscenza di base degli alberi di Merkle e della serializzazione.

Trie della radice di base

In un trie della radice di base, ogni nodo si presenta così:

1    [i0, i1 ... in, value]
2
3

Dove i0 ... in rappresenta i simboli dell'alfabeto (spesso binari o esadecimali), value è il valore terminale al nodo e i valori negli slot i0 ... in sono NULL o puntatori ad (nel nostro caso, hash di) altri nodi. Questo forma un'archiviazione di base (chiave, valore). Ad esempio, se sei interessato al valore correntemente mappato a dog nel trie, prima devi convertire dog in lettere dell'alfabeto (ottenendo 64 6f 67) e poi scendere dal trie seguendo il percorso, fino a trovare il valore. Dunque, prima dovresti cercare l'hash della radice in un DB flat chiave/valore per trovare il nodo di root del trie (che è un insieme di chiavi ad altri nodi), usando come chiave il valore all'indice 6 (cercando nel DB chiave/valore) per ottenere il nodo al livello inferiore successivo, poi dovresti selezionarne l'indice 4 per cercare il valore successivo, poi prendere l'indice 6 e così via, finché, una volta seguito il percorso: root -> 6 -> 4 -> 6 -> 15 -> 6 -> 7, dovresti leggere il valore che hai e restituire il risultato.

Esiste una differenza tra cercare qualcosa nel 'trie' e nel 'DB' flat chiave/valore sottostante. Entrambi definiscono degli schemi chiave/valori, ma il DB sottostante può effettuare una tradizionale ricerca di una chiave in 1 passaggio. Cercare una chiave nel trie richiede diverse ricerche DB sottostanti, per ottenere il valore finale descritto sopra. Facciamo riferimento a quest'ultimo come path, per eliminare ogni ambiguità.

Le operazioni di aggiornamento ed eliminazione per i trie di radice sono semplici e possono essere approssimativamente così definite:

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

La parte "Merkle" del trie della radice nasce dal fatto che, come puntatore al nodo, è usato un hash crittografico deterministico di un nodo (per ogni ricerca nel DB chiave/valore key == keccak256(rlp(value)), piuttosto che una qualche posizione della memoria a 32 o 64 bit, come potrebbe avvenire in un trie più tradizionale implementato in C. Questo fornisce una forma d'autenticazione crittografica alla struttura dei dati; se l'hash della radice di un dato trie è pubblicamente noto, allora chiunque può fornire una prova che il trie abbia un dato valore a un percorso specifico, fornendo gli hash di ogni nodo che si unisce a un valore specifico alla radice dell'albero. È impossibile per un utente malevolo fornire una prova di una coppia (percorso, valore) che non esiste, poiché l'hash della radice è basato in definitiva su tutti gli hash successivi, quindi, ogni modifica modificherebbe l'hash della radice.

Pur attraversando un percorso un nibble alla volta, come descritto sopra, gran parte dei nodi contiene un insieme di 17 elementi. Un indice per ogni possibile valore tenuto dal carattere esadecimale successivo (nibble) nel percorso e uno per detenere il valore di destinazione finale se il percorso è stato attraversato interamente. Questi nodi dell'array di 17 elementi sono detti nodi del branch.

Trie di Patricia Merkle

I trie della radice presentano però una grande limitazione: sono inefficienti. Se si vuole memorizzare solo una coppia (percorso, valore) in cui si trova il percorso (nel caso del trie di stato di Ethereum), lunga 64 caratteri (numero di nibble in bytes32), servirà oltre un kilobyte di spazio aggiuntivo per memorizzare un livello per carattere, e per ogni ricerca o eliminazione verranno eseguiti tutti i 64 passaggi. Il trie di Patricia risolve questo problema.

Ottimizzazione

I trie di Patricia Merkle risolvono il problema d'inefficienza aggiungendo una certa complessità aggiuntiva alla struttura dei dati. Un nodo in un trie di Patricia Merkle è uno dei seguenti:

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

Con i percorsi da 64 caratteri è inevitabile che dopo aver attraversato i primi pochi livelli del trie, si raggiunge un nodo privo di alcun percorso divergente per almeno parte del percorso. Sarebbe ingenuo richiedere che un nodo simile abbia valori vuoti in ogni indice (uno per ognuno dei 16 caratteri esadecimali), oltre all'indice di destinazione (accanto al nibble nel percorso). Al contrario, accorciamo la discesa configurando un nodo extension con la forma [ encodedPath, key ], in cui encodedPath contiene il "percorso parziale" per saltare avanti (usando la codifica compatta sopra descritta) e la key è per la prossima ricerca DB.

Nel caso di un nodo leaf, determinabile da un flag nel primo nibble di encodedPath, si verifica la suddetta situazione e anche il "percorso parziale" per saltare avanti completa la restante parte di un percorso. In questo caso, value è lo stesso valore di destinazione.

Questa ottimizzazione introduce però delle ambiguità.

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

Specifica: codifica compatta della sequenza esadecimale con terminatore facoltativo

Il flagging sia della lunghezza del percorso parziale rimanente, dispari o pari, sia del nodo leaf o estensione, come descritto sopra, risiede nel primo nibble del percorso parziale di qualsiasi nodo di 2 elementi. Il risultato è il seguente:

1char hex    bit    |    parziale tipo nodo     lungh percorso
2----------------------------------------------------------
3   0        0000    |       estensione              pari
4   1        0001    |       estensione              dispari
5   2        0010    |   terminazione (leaf)         pari
6   3        0011    |   terminazione (leaf)         dispari
7

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

1    def compact_encode(hexarray):
2        term = 1 if hexarray[-1] == 16 else 0
3        if term: hexarray = hexarray[:-1]
4        oddlen = len(hexarray) % 2
5        flags = 2 * term + oddlen
6        if oddlen:
7            hexarray = [flags] + hexarray
8        else:
9            hexarray = [flags] + [0] + hexarray
10        // hexarray ha ora una lunghezza pari, il cui primo nibble si compone dei flag.
11        o = ''
12        for i in range(0,len(hexarray),2):
13            o += chr(16 * hexarray[i] + hexarray[i+1])
14        return o
15
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'
9

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

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

Esempio di Trie

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

Per prima cosa, convertiamo sia i percorsi che i valori in bytes. Di seguito, le rappresentazioni reali dei byte per i percorsi sono denotate da <>, sebbene i valori siano mostrati ancora come stringhe, denotate da ", per maggiore facilità di comprensione (anch'essi, sarebbero in realtà bytes):

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

Ora, costruiamo un trie di questo tipo 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>, hashD ]
4    hashD:    [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
5    hashE:    [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coin' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]
6

Quando in un nodo si fa riferimento a un altro nodo, viene inserito H(rlp.encode(x)), dove H(x) = keccak256(x) if len(x) >= 32 else x e rlp.encode è la funzione di codifica RLP.

Nota che, aggiornando un trie, si deve memorizzare la coppia chiave/valore (keccak256(x), x) in una tabella di ricerca persistente se il nodo appena creato ha una lunghezza >= 32. Se invece il nodo è inferiore a questo valore, non è necessario memorizzare nulla, poiché la funzione f(x) = x è reversibile.

Trie in Ethereum

Tutti i trie di Merkle nel livello d'esecuzione di Ethereum usano un Trie di Patricia Merkle.

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

stateRoot
transactionsRoot
receiptsRoot

Trie di Stato

Esiste un trie di stato globale che si aggiorna nel tempo. In esso, un path è sempre: keccak256(ethereumAddress) e un value è sempre: rlp(ethereumAccount). Più nello specifico, un account di Ethereum è un insieme di 4 elementi di [nonce,balance,storageRoot,codeHash]. A questo punto, vale la pena di notare che questo storageRoot è la radice di un altro trie di Patricia:

Trie d'archiviazione

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

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

Il recupero di altri elementi in archiviazione è lievemente più impegnativo, poiché deve essere calcolata prima la posizione nel trie d'archiviazione. La posizione è calcolata come l'hash keccak256 dell'indirizzo e della posizione d'archiviazione, entrambi con padding di zeri a sinistra, fino a una lunghezza di 32 byte. Ad esempio, la posizione dei dati nello slot d'archiviazione 1 per l'indirizzo 0x391694e7e0b0cce554cb130d723a9d27458f9298 è:

In una console Geth, si può calcolare in questo modo:

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

Il path è dunque keccak256(<6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9>). Questo è ora utilizzabile per recuperare i dati dal trie d'archiviazione come sopra:

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

Trie delle transazioni

Esiste un trie delle transazioni distinto per ogni blocco, che memorizza ancora coppie (chiave, valore). Qui, un percorso è: rlp(transactionIndex) che rappresenta la chiave corrispondente a un valore determinato da:

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

Maggiori informazioni a riguardo si possono trovare nella documentazione EIP 2718(opens in a new tab).

Trie delle ricevute

Ogni blocco ha il proprio trie delle ricevute. Qui, un path è: rlp(transactionIndex). transactionIndex è il suo indice nel blocco estratto. Il trie delle ricevute non si aggiorna mai. Analogamente al trie delle transazioni, esistono ricevute correnti e legacy. Per interrogare una ricevuta specifica nel trie delle ricevute, servono l'indice della transazione nel suo blocco, il payload della ricevuta e il tipo di transazione. La ricevuta restituita può essere di tipo Receipt, definita come la concatenazione del transaction type e del transaction payload, oppure può essere di tipo LegacyReceipt, definito come rlp([status, cumulativeGasUsed, logsBloom, logs]).

Maggiori informazioni a riguardo si possono trovare nella documentazione EIP 2718(opens in a new tab).

Letture consigliate

Torna all’inizio ↑

Aiuta ad aggiornare questa pagina

Nessun bug qui!

Start here

Ethereum basics

Ethereum protocol