Tralasciando la parte della rete, potremmo dire che Ethereum è una macchina a stati dove le transazioni modificano gli stati sulla rete Ethereum. Uno stato può essere espresso come una coppia chiave-valore. Anche se ci sono diversi modi di rappresentare una coppia chiave-valore, la specifica di Ethereum definisce il Modified Merkle Patricia Trie (a.k.a MPT) come metodo per salvare gli stati.
Fondamentalmente, MPT è una combinazione di Patricia trie e Merkle tree, con alcune ottimizzazioni aggiuntive che si adattano alle caratteristiche di Ethereum. Quindi, una comprensione del Patricia trie e dell’albero di Merkle dovrebbe precedere la comprensione di MPT.
Patricia trie è una struttura di dati che è anche chiamata albero dei prefissi, albero radix o trie. Il trie usa una chiave come percorso in modo che i nodi che condividono lo stesso prefisso possano anche condividere lo stesso percorso. Questa struttura è più veloce nel trovare i prefissi comuni, è semplice da implementare e richiede poca memoria. Perciò, è comunemente usata per implementare le tabelle di routing, sistemi che sono usati in macchine con basse specifiche come il router.
Merkle Tree
Merkle tree è un albero di hash. I nodi foglia immagazzinano dati. I nodi padre contengono l’hash dei loro figli e il valore hash della somma degli hash dei loro figli. Poiché tutti i nodi tranne i nodi foglia contengono un hash, l’albero di Merkle è anche conosciuto come un albero hash.
Scoprendo se due diversi nodi hanno gli stessi dati o no può essere fatto in modo efficiente con l’albero di Merkle. Si deve prima confrontare il valore Top Hash dei due nodi. Se sono uguali, allora i due nodi hanno gli stessi dati. Per esempio, se guardate l’immagine sopra, quando ci sono quattro nodi (L1, L2, L3, L4), dovete solo controllare se hanno lo stesso Top Hash o no. Se il Top Hash è diverso e volete sapere quali dati sono diversi, dovreste confrontare Hash 0 con Hash1 e controllare quale ramo è diverso. Così facendo, alla fine scoprirai quali dati sono diversi.
Merkle Patricia Trie
Nel MPT, così come nell’albero di Merkle, ogni nodo ha un valore hash. L’hash di ogni nodo è deciso dal valore di hash sha3 del suo contenuto. Questo hash è anche usato come chiave che si riferisce al nodo. Go-ethereum usa levelDB e Parity usa rocksDB per memorizzare gli stati. Sono archivi chiave-valore. Le chiavi e i valori salvati nello storage non sono i valori-chiave dello stato Ethereum. Il valore che viene memorizzato nello storage è il contenuto del nodo MPT mentre la chiave è l’hash di questo nodo.
I valori-chiave dello stato Ethereum sono usati come percorsi sul MPT. Il nibble è l’unità utilizzata per distinguere i valori chiave nel MPT, quindi ogni nodo può avere fino a 16 rami. Inoltre, dal momento che un nodo ha un proprio valore, un nodo ramo è un array di 17 elementi composto da 1 valore del nodo e 16 rami.
Un nodo che non ha un nodo figlio è chiamato nodo foglia. Un nodo foglia è composto da due elementi: il suo percorso e il suo valore. Per esempio, diciamo che la chiave “0xBEA” contiene 1000 e la chiave “0xBEE” contiene 2000. Allora, ci dovrebbe essere un nodo ramo con il percorso “0xBE”, e, sotto quel nodo, due nodi foglia con due percorsi (“0xA” e “0xE”) saranno attaccati.
Nel MPT, c’è un altro tipo di nodi oltre ai nodi ramo e i nodi foglia. Sono i nodi di estensione. Un nodo di estensione è un nodo ottimizzato del nodo ramo. Nello stato di Ethereum, molto spesso, ci sono nodi di ramo che hanno solo un nodo figlio. Questa è la ragione per cui l’MPT comprime i nodi ramo che contengono un solo figlio in nodi estensione che hanno un percorso e l’hash del figlio.
Siccome sia il nodo foglia che il nodo estensione sono un array di due elementi, dovrebbe esserci un modo per distinguere questi due diversi nodi. Per fare questa distinzione, l’MPT aggiunge un prefisso al percorso. Se il nodo è una foglia e il percorso consiste di un numero pari di nibble, si aggiunge 0x20 come prefisso. Se il percorso consiste di un numero dispari di nibble, si aggiunge 0x3 come prefisso. Se il nodo è un nodo di estensione e il percorso consiste di un numero pari di nibble, si aggiunge 0x00 come prefisso. Se consiste di un numero dispari di nibble, si dovrebbe aggiungere 0x1 come prefisso. Poiché il percorso che consiste in un numero dispari di nibble riceve un nibble come prefisso e il percorso che consiste in un numero pari di nibble riceve due nibble come prefisso, un percorso è sempre espresso come un byte.
(Per la versione originale coreana, clicca qui)