INDICE
1. Introduzione
2. Uno sguardo in parallelo a Bitcoin
3. Radix Trie
4. Patricia Merkle Trie
4.1 Utilità dei PMT in Ethereum
4.2 Utilità dell'intestazione del blocco Ethereum
4.3 Trie dello Stato di Ethereum
4.4 Trie delle transazioni Ethereum
4.5 Trie delle ricevute delle transazioni Ethereum
5. Conclusioni
Introduzione
Bitcoin fu la prima rete decentralizzata basata su blockchain che ha reso popolare l'uso degli alberi di Merkle per un tipo di inclusione scalabile delle transazioni.
Qualche anno più tardi, Ethereum entrò i campo schierando anch'esso gli alberi di Merkle ma, essendo un progetto completamente diverso per sua natura, fu scelta anche un'altra importante struttura di dati ad albero, con riferimento ad alcune delle sue esigenze di archiviazione dei dati.
Gli alberi utilizzati in Ethereum sappiamo che non sono dei semplici alberi di Merkle, e richiedono delle caratteristiche aggiuntive:
- L'albero deve essere facilmente modificabile, in quanto i dati contenuti in esso cambiano frequentemente;
- La radice dell'albero deve dipendere solo dai dati e non dall'ordine in cui gli aggiornamenti ad esso vengono fatti;
- L'albero deve avere una "profondità" limitata;
E la soluzione a queste funzionalità è il "Merkle Patricia trie", rivisitato e adattato all'infrastruttura Ethereum.
Dei Patricia Trie se ne parlava già nel lontano 1968: a pubblicare il paper all'epoca fu un certo Donald R. Morrison all'interno del Journal of the Association for Computing Machinery.
Ritorniamo ora per qualche momento sulla struttura di Bitcoin.
Uno sguardo in parallelo a Bitcoin
L'architettura di Bitcoin è "semplice": consiste in un libro mastro che tiene traccia delle transazioni utilizzando un modello UTXO.
Poiché Ethereum tiene traccia di una maggiore quantità di dati di stato, l'architettura dei blocchi è completamente diversa:
Perché ora siamo passati a questa architettura a blocchi, non stavamo parlando di alberi?
Perché questi blocchi contengono riferimenti alle strutture dati ad albero di cui stiamo parlando.
L'obiettivo è quello di mostrare prima l'architettura a blocchi e poter comparare e avere familiarità con tre delle proprietà fondamentali dei blocchi di Ethereum incluse nel diagramma qui sopra:
1) State Root,
2) Transaction Root,
3) Receipt Root - proprio come nell'ultima sezione abbiamo trattato il significato di merkleRootHash nel contesto di un blocco Bitcoin, ora esamineremo tre nuovi usi simili dell'albero in Ethereum.
Teniamo questo a mente, dopo ci torneremo!
Radix Trie o Patricia Trie
Il PATRICIA trie viene descritto come un albero che permette di conservare una serie di dati di tipo chiave - valore e poi di recuperarli in modo semplice ed efficiente.
La chiave indica il "percorso" da seguire per giungere alla foglia, la quale contiene il valore corrispondente.
Il PATRICIA Trie, per recuperare un valore stringa, percorre un ramo di nodi che memorizzano riferimenti associati (chiavi) e che insieme portano al valore finale, e che può essere quindi restituito.
I PATRICIA Tries presentano però una grande limitazione: sono inefficienti. Se si vuole memorizzare solo una coppia (chiave/ valore) in cui si trova il percorso (nel caso del trie di stato di Ethereum), lunga 64 caratteri 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 Patricia Merkle Trie risolve questo problema.
Come scrivevamo prima, Ethereum utilizza la struttura di dati radix trie (detta anche Patricia Trie o radix tree) ma solo per quei dati permanenti, e per i dati più effimeri e variabili combina questa struttura di dati con un albero di Merkle per creare un Patricia Merkle Trie (PMT).
Patricia Trie + Albero di Merkle = Patricia Merkle Trie (a volte pronunciato come tree, "albero", a volte come trie, "prova") 👀
CURIOSITA': Cosa significa Trie?
"Trie" deriva dalla parola "retrieval", ovvero recupero, con riferimento al modo ben ottimizzato con il quale i Patricia Merkle Tries riescono a recuperare dati all'interno di particolare strutture.
Ripetiamo: I patricia Merkle Tries sono spesso chiamati anche Patricia Merkle Trees 🎄.
Radix Trie o Patricia Trie
Una Patricia Merkle trie è una struttura dati che memorizza coppie chiave-valore, proprio come una tabella hash.
Inoltre, consente di verificare l'integrità dei dati e l'inclusione di una coppia chiave-valore.
I Patricia Merkle Trie raggruppano i nodi con valori simili nell'albero. In questo modo per esempio, la ricerca di "HELP" porta allo stesso percorso della ricerca di "HELLO" - essendo le prime tre lettere voci condivise di parole diverse.
È un'ottima soluzione per l'efficienza di spazio e delle operazioni di lettura/scrittura.
I PMT sono in pratica alberi di Merkle sotto steroidi: efficienti per la verifica dei dati, ma anche per la loro modifica.
E finalmente sveliamo l'arcano: perchè Patricia?
- P = Practical
- A = Algorithm
- T = To
- R = Retrieve
- I = Information
- C = Coded
- I = In
- A = Alphanumeric
Utilità dei PMT in Ethereum
Torniamo sui motivi per cui è stata scelto questo algoritmo.
In genere, esistono due tipi diversi di dati:
1) Permanenti
Una volta che si verifica una transazione, quel record viene sigillato per sempre.
Ciò significa che una volta individuata una transazione nel trie delle transazioni di un blocco, è possibile tornare allo stesso percorso più volte per recuperare lo stesso risultato.
2) Dati effimeri
Nel caso di Ethereum, gli stati dei conti cambiano continuamente! (Ad esempio, un utente riceve qualche ETH, interagisce con un contratto, ne consuma altri in gas fee ecc.)
Tra queste tipologie di dati figurano: nonce, balance, storageRoot, codeHash;
È logico che i dati permanenti, come le transazioni minate, e i dati effimeri, come i conti Ethereum (saldo, nonce, ecc.), debbano essere archiviati separatamente.
Gli alberi di Merkle, ancora una volta, sono perfetti per i dati permanenti.
I PMT sono perfetti per i dati effimeri, di cui Ethereum è estremamente ricco rispetto a Bitcoin (ecco perchè vi ho annoiato con il parallelismo con Bitcoin lol).
A differenza della cronologia delle transazioni, lo stato degli account di Ethereum deve essere aggiornato frequentemente. Il saldo-balance e il nonce dei conti vengono spesso modificati e, inoltre, vengono frequentemente inseriti nuovi account e rispettive chiavi in memoria, anch'esse frequentemente inserite e cancellate.
Intestazione del blocco Ethereum
L'intestazione del blocco contiene molti dati. L'intestazione del blocco è il risultato dell'hash di tutti gli elementi di dati contenuti in un blocco: una sorta di packaging di tutti i dati del blocco.
Se guardiamo il diagramma dell'architettura di Ethereum inserito all'inizio di questo post, l'intestazione del blocco finisce per fare da hash a tutte le proprietà dei dati del blocco. Esso include anche:
1) State Root: l'hash della radice del trie di stato;
2) Transactions Root: l'hash della radice delle transazioni del blocco;
3) Receipts Root: l'hash della radice del trie delle ricevute.
Trie dello Stato di Ethereum
Come mostrato nel diagramma qui sotto, il *trie di stato * di Ethereum funge da mappatura tra gli indirizzi e gli stati degli account.
Esso può essere visto come uno stato globale che viene costantemente aggiornato dall'esecuzione delle transazioni.
La rete Ethereum è un computer decentralizzato e lo state trie è considerato un disco rigido.
Tutte le informazioni sugli account sono memorizzate nello state trie globale ed è possibile recuperare le informazioni interrogandolo.
Esempio di conto
Come già detto, lo state trie è solo una mappatura che utilizza un indirizzo come chiave e lo stato del conto (nonce, saldo, ecc.) come valore restituito.
Questo è ciò che si ottiene da una richiesta JavaScript allo stato globale di Ethereum.
Solo un oggetto contenente alcuni dati! Questo è tutto ciò che è lo stato dell'account.
Essendo troppi i dati da memorizzare, si utilizza un hash radice.
Trie delle transazioni Ethereum
Il trie delle transazioni registra le transazioni in Ethereum. Una volta che il blocco è stato estratto, il trie delle transazioni non viene mai aggiornato.
Ogni transazione in Ethereum registra più elementi specifici per ogni transazione, come il prezzo del gas e il valore.
Esempio di transazione
Probabilmente lo avete visto attraverso servizi come Etherscan. Tutto ciò che questi servizi fanno è interrogare la blockchain di Ethereum per trovare i dati delle transazioni e poi indicizzarli in un visualizzatore di transazioni organizzato.
Si può anche provare a interrogare direttamente il trie delle transazioni usando strumenti esterni, come Alchemy Composer. Basterà prendere un hash casuale di tx e usare il metodo eth_getTransactionByHash: si otterrà una risposta molto simile all'oggetto nell'immagine qui sopra.
Trie delle ricevute delle transazioni Ethereum
Il trie delle ricevute delle transazioni registra le ricevute (i risultati) delle transazioni. I dati includono gasUsed e log (gli eventi emessi sono contenuti in questo trie).
Una volta che il blocco è stato estratto, il trie di ricezione delle transazioni non viene mai aggiornato. Un esempio qui sotto:
Conclusioni
Il diagramma sopra riportato è un'eccellente visualizzazione di come i Trie finiscono per essere impegnati in ogni blocco tramite il loro hash principale.
I dati grezzi sono memorizzati altrove in Ethereum, in particolare nei nodi di archiviazione.
Il diagramma dell'architettura a blocchi di Ethereum vi sembra meno minaccioso rispetto all'inizio? Se sì, bene! Abbiamo trattato, seppur velocemente, alcuni degli aspetti di livello più basso dell'archiviazione dei dati in Ethereum, e sono importantissimi! Non solo si ha una comprensione più olistica di Ethereum, ma si tratta di conoscenze applicabili a tutta l'informatica e persino alla fisica 🤯.
L'aspetto più importante di questa lezione è stato sicuramente capire perché queste strutture dati di basso livello sono usate da Ethereum:
a) ottimizzare lo spazio dei dati;
b) ottimizzare l'efficienza di lettura/scrittura;
Alcuni testi e letture per approfondire gli argomenti trattati:
Top comments (0)