TL;DR: un merkle tree è una struttura dati ad albero che riassume un grande insieme di dati in un singolo hash, chiamato merkle root. In Bitcoin ogni blocco contiene un merkle tree che riassume tutte le transazioni del blocco: la merkle root occupa 32 byte dell’intestazione del blocco (80 byte totali). Grazie a questa struttura è possibile dimostrare che una transazione è inclusa in un blocco con poche centinaia di byte, senza scaricare l’intero blocco. Il concetto è stato descritto da Ralph Merkle, che lo brevettò nel 1979.
Un merkle tree (o hash tree) è una struttura dati ad albero utilizzata per riassumere e verificare in modo efficiente l’integrità di grandi insiemi di dati. Prende il nome da Ralph Merkle, l’informatico che brevettò il concetto nel 1979.
In Bitcoin il merkle tree è un componente fondamentale: ogni blocco della blockchain ne contiene uno, che organizza tutte le transazioni del blocco e le riassume in un singolo hash di 32 byte, la merkle root.
Cos’è un merkle tree?
Un merkle tree è un albero binario costruito con funzioni di hash. Le “foglie” alla base dell’albero sono gli hash dei singoli dati (in Bitcoin, gli identificativi delle transazioni). Ogni livello superiore si ottiene concatenando le coppie di hash del livello inferiore e calcolando l’hash del risultato, fino ad arrivare a un unico hash in cima: la merkle root.
Il vantaggio è duplice:
- Compressione: migliaia di transazioni vengono rappresentate da un solo hash di 32 byte.
- Verificabilità: per dimostrare che un dato appartiene all’insieme è sufficiente fornire un piccolo numero di hash intermedi (la merkle proof), senza trasmettere l’intero insieme.
Se anche un solo bit di una transazione cambia, cambia il suo hash, cambiano tutti gli hash intermedi sul percorso e cambia la merkle root: la manomissione è immediatamente rilevabile.
Come funziona un merkle tree? Esempio passo-passo
Immaginiamo un blocco con quattro transazioni: A, B, C e D.
- Si calcola l’hash di ogni transazione: H(A), H(B), H(C), H(D). In Bitcoin la funzione usata è SHA-256 applicata due volte (double SHA-256).
- Si accoppiano gli hash e si calcola l’hash di ogni coppia: H(AB) = hash di H(A)+H(B); H(CD) = hash di H(C)+H(D).
- Si ripete il procedimento sull’ultimo livello: la merkle root è l’hash di H(AB)+H(CD).
Per dimostrare che la transazione C è inclusa nel blocco bastano due hash: H(D) e H(AB). Chi verifica calcola H(C), lo combina con H(D) per ottenere H(CD), combina H(CD) con H(AB) e controlla che il risultato coincida con la merkle root contenuta nell’intestazione del blocco. Questo percorso si chiama merkle proof (o merkle path).
Il numero di hash necessari cresce in modo logaritmico: per un blocco con oltre 2.000 transazioni bastano circa 11-12 hash, poche centinaia di byte. Se il numero di transazioni è dispari, l’ultimo hash viene duplicato e accoppiato con se stesso.
Come Bitcoin usa il merkle tree
La merkle root nell’intestazione del blocco
Ogni blocco Bitcoin è composto da un’intestazione (block header) di 80 byte e dal corpo con le transazioni. L’intestazione contiene sei campi: la versione, l’hash del blocco precedente, la merkle root, il timestamp, il target di difficoltà e il nonce.
La merkle root è quindi l’unico “riassunto” delle transazioni che entra nell’intestazione. Quando i miner cercano un hash valido per il blocco, lavorano solo sugli 80 byte dell’intestazione: la merkle root garantisce che quell’intestazione sia indissolubilmente legata all’elenco esatto delle transazioni incluse. Modificare una transazione a posteriori richiederebbe di ricalcolare la merkle root e quindi di rifare la proof of work del blocco e di tutti i blocchi successivi.
SPV e merkle proof: verificare senza scaricare tutto
Il merkle tree è ciò che rende possibile la Simplified Payment Verification (SPV), descritta da Satoshi Nakamoto nella sezione 8 del whitepaper di Bitcoin. Un client SPV (come molti wallet mobile) non scarica l’intera blockchain: scarica solo le intestazioni dei blocchi, 80 byte ciascuna.
Per verificare di aver ricevuto un pagamento, il client chiede a un nodo completo la merkle proof della transazione: pochi hash che collegano la transazione alla merkle root di un’intestazione già in suo possesso. Se il percorso torna, la transazione è inclusa in quel blocco, e i blocchi minati successivamente ne confermano la profondità. Tutto questo senza dover scaricare e validare centinaia di gigabyte di dati.
Dove si usano i merkle tree oltre Bitcoin?
I Merkle tree sono utilizzati in diverse applicazioni, tra cui:
- File system: vengono utilizzati per verificare l’integrità dei file all’interno di un file system distribuito come InterPlanetary File System (IPFS).
- Database system: vengono utilizzati per rilevare incoerenze tra le repliche di interi database NoSQL come Apache Cassandra e Amazon DynamoDB.
- Version control system: alcuni dei sistemi di version control più diffusi come Git e Mercurial utilizzano i Merkle tree per gestire le versioni dei file e delle directory.
Domande frequenti
Cos’è la merkle root?
È l’hash alla cima del merkle tree, che riassume tutte le transazioni di un blocco in 32 byte. In Bitcoin è uno dei sei campi dell’intestazione del blocco.
Chi ha inventato il merkle tree?
L’informatico statunitense Ralph Merkle, che brevettò il concetto nel 1979. La struttura è precedente a Bitcoin ed è usata in molti altri sistemi.
A cosa serve il merkle tree in Bitcoin?
Lega in modo crittografico l’elenco delle transazioni all’intestazione del blocco e permette di dimostrare l’inclusione di una transazione con una merkle proof, senza trasmettere l’intero blocco.
Cos’è una merkle proof?
È l’insieme di hash intermedi che collega una transazione alla merkle root. Per un blocco con migliaia di transazioni bastano circa una dozzina di hash.
Cosa significa SPV?
Simplified Payment Verification: il metodo, descritto nel whitepaper di Bitcoin, con cui un wallet leggero verifica i pagamenti scaricando solo le intestazioni dei blocchi e richiedendo merkle proof ai nodi completi.
