Il Practical Algorithm To Retrieve Information Coded In Alphanumeric Merkle Trie, o Patricia Merkle Trie è una struttura dati chiave-valore usatada Ethereum e particolarmente efficiente per il salvataggio e la verifica dell’integrità dell’informazione.
In questo post ne studieremo le caratteristiche.
Prima di procedere, ci conviene ripassare l’introduzione al Merkle Tree nella quale abbiamo chiarito il concetto di struttura ad albero creando un vocabolario condiviso di termini che useremo anche a breve.
Il nostro obiettivo primario è ora capire dove il Patricia Merkle Trie sia usato e soprattutto perché.
Devi sapere che rispetto a Bitcoin, Ethererum ha delle esigenze di archiviazione più sofisticate.
Come ricorderai, il Merkle Tree è perfetto per registrare oggetti statici e immutabili come le transazioni. Salvando la radice (Merke Tree Root) sulla blockchain e i dati grezzi off-chain, diamo la possibilità a chiunque di verificare in ogni momento l’integrità dei dati, attraverso la Merkle Proof, contenendo al contempo la quantità di dati salvati e condivisi sulla rete.
Questo funziona bene in Bitcoin mentre in Ethereum la situazione cambia. Innanzitutto dobbiamo distinguere due categorie di dati:
- dati permanenti (permanent data), riferiti alla transazione. Una volta eseguita le sue proprietà sono congelate nella blockchain.
- dati effimeri (ephemeral data), riferiti al bilancio degli indirizzi. Lo stato degli account cambia in ogni momento e nel dettaglio questi parametri vengono modificati costantemente: nonce, balance, storageRoot, codeHash
Ci serve allora una struttura dati che ci permetta la modifica dei valori, senza perdere i vantaggi dei Merke Tree.
Come? Potremmo fare ricordo a un Radix Tree
🎄 Radix Trie o Patricia Trie
Un Radix Trie, o albero radice anche noto come albero dei prefissi compatti, è una struttura dati ad albero usata per recuperare una stringa attraversando un ramo di nodi, ciascuno contenente dei valori che complessivamente concorrono a determinare la stringa originale.
È più semplice di quanto si pensi. Ti assicuro poi che se giochi 2 minuti con questo tool ti sarà tutto molto più chiaro.
In sintesi ogni parola è scissa in frammenti (nodi) sulla base di parole simili contenute nell’albero.
Recupera i frammenti e avrai la parola.
La fase di recupero è così caratteristica da essere inclusa nel nome: trie deriva dalla parola retrieval che ci ricorda per cosa sia ottimizzato un Patricia Trie. Salvo poi il fatto che tutti lo considerino un Patricia Tree. Piccoli dettagli che fanno la differenza.
Raggruppando chiavi associate tra loro, ottimizziamo la ricerca di una parola aumentando l’efficienza.
Questi alberi sono spesso usati per il routing degli indirizzi IP, mentre in Ethereum vengono combinati con i Merkle Trees per dare luogo ai Patricia Merkle Tries
Infatti Patricia Trie + Merkle Tree = Patricia Merkle Trie
Patricia Merkle Trie | Ethereum Block Header
Un Patricia Merkle Trie è dunque una struttura dati che registra coppie di chiavi-valore, al pari di una hash table, permettendoci però di verificare l’integrità dei dati (assicurando che non siano stati compromessi o modificati) e validare l’inclusione di una coppia chiave-valore. Inoltre, a differenza di una hash table non ci sono collisioni tra le chiavi.
Trattandosi di un argomento vasto e complesso, direi di proceder andando al concreto ed esaminando un blocco Ethereum, e nel dettaglio il suo Header: è qui che Patricia Merkle Trie è usato.
Lascia allora che guidi la tua attenzione su tre proprietà assolutamente rilevanti e presenti in ogni blocco:
- State Root: il root hash dello state trie
- Transaction Root: il root hash delle transazioni del blocco, registrate nel transaction trie
- Receipt Root: il root hash del transaction receipt trie
Aumentiamo l’ingrandimento.
State Trie
Per il momento è tutto.
Per aspera, ad astra.
Un caldo abbraccio, Andrea
Lo State Trie agisce da mapping tra un indirizzo e l’account state, un oggetto dato dalla combinazione di 4 proprietà: nonce, balance, storageRoot, codeHash.
È lo stato globale continuamente aggiornato dall’esecuzione di transazioni sulla rete. Anziché salvare l’intero oggetto, solamente il root hash dell’albero globale è incluso in un blocco minato dalla rete.
Transaction Trie
Il transaction trie registra le transazioni avvenute. Ha una peculiarità: una volta creato e incluso in un blocco (attraverso l’hash della radice) non viene mai modificato. Sfruttando il composer tool di alchemy puoi addirittura inviare una query per l’estrazione dati direttamente dal Transaction Trie.
Al suo interno sono registrati i valori di gas (limit e price), nonché l’eventuale quantità di base asset (ETH) trasferita oltre che al nonce dell’account che ha effetueffettuatoato la transazione.
Transaction Receipt Trie
Il Transaction Receipt Trie contiene il risultato di una transazione, in termini di gas effettivamente consumato gasUsed e gli eventuali logs, gli eventi emessi dallo smart contract con cui la transazione ha interagito. Anche in questo caso, una volta minato il transaction receipt trie non è mai modificato.
Per completezza, i dati grezzi sono salvati altrove, in particolari nodi archivio
Approfondimenti sul Patricia Merkle Trie
Per essere precisi i nodi di Ethereum fanno uso di un quarto albero, definito storage trie che contiene i dati persistenti degli smart contract. Per approfondire l’argomento consiglio la lettura dell’overview tecnica firmata da Vitalik Buterin in persona, ideatore e fondatore di Ethereum, sull’uso dei Merkle Trees.
In sintesi, i vantaggi primari dati dall’uso di un Patricia Merkle Trie sono:
- Verifica dati efficiente (data dalla natura ad albero di Merkle)
- Consentire ai light-client query più complesse
- Modificare rapidamente i valori e ricalcolare solamente una porzione dell’albero (in questo modo preveniamo alcuni attacchi di tip DDoS, o Distributed Denial of Service)
- Limitare la profondità dell’albero, che previene l’impiego di altri vettori DDoS.
- L’ordine degli aggiornamenti non influenza il root hash.
Un ulteriore grado di dettaglio in merito è disponibile al seguente link.
Un’ultima nota.
Può essere utile sapere che Ethereum sfrutta un formato di serializzazione noto come RLP, una forma assimilabile a un JSON. Viene usato per inviare dati da una macchina all’altra, ma anche per codificare tutte le entità nel radix tree.
Per il momento è tutto.
Per aspera, ad astra.
Un caldo abbraccio, Andrea
