Albero di Merkle

Un albero di Merkle (Merkle tree, proposto da Ralph Merkle nel 1979) è una struttura dati ad albero binario in cui ogni nodo foglia contiene l’hash crittografico di un dato, e ogni nodo interno contiene l’hash dei propri nodi figli:

$H_{\text{parent}} = H(H_{\text{left}} \| H_{\text{right}})$

La radice dell’albero — la Merkle root — è un singolo hash che sintetizza crittograficamente l’intero insieme di dati sottostante. Qualsiasi modifica a un singolo dato foglia produce una cascata di hash diversi fino alla radice, rendendo la manomissione immediatamente rilevabile da chi conosce la Merkle root autentica.

Verifica efficiente con Merkle Proof

Il vantaggio principale degli alberi di Merkle rispetto al semplice hash dell’intero dataset è la possibilità di produrre una Merkle proof: la prova crittografica che un dato specifico appartiene all’insieme richiede solo $O(\log n)$ hash (i nodi fratelli lungo il percorso dalla foglia alla radice), invece di trasmettere l’intero dataset di $n$ elementi.

Esempio con 8 foglie $d_0 \ldots d_7$: per provare che $d_2$ appartiene all’insieme, bastano 3 hash — $H_3$, $H_{01}$, $H_{4567}$ — con i quali il verificatore può ricostruire la radice e confrontarla con quella nota.

Applicazioni

Bitcoin e blockchain: ogni blocco contiene la Merkle root di tutte le transazioni incluse. I client leggeri (SPV) possono verificare che una transazione sia nel blocco con soli $O(\log n)$ hash, senza scaricare l’intero blocco. La catena di hash tra blocchi — dove ogni blocco include l’hash del precedente — forma una struttura analoga che garantisce l’immutabilità della storia.

Git: i commit di Git sono organizzati come alberi di Merkle. Ogni commit punta a un tree object che contiene hash dei blob (file) e dei subtree. Due repository che condividono la stessa Merkle root per un commit hanno esattamente gli stessi contenuti — è la base del sistema di distribuzione e verifica di Git.

Certificate Transparency: i log CT sono Merkle tree append-only. Chiunque può verificare che un certificato sia nel log con una Merkle proof, e che nessuna voce sia stata rimossa o modificata (proprietà di append-only verificabile).

Sistemi di file distribuiti (IPFS, BitTorrent): i file di grandi dimensioni vengono suddivisi in chunk, organizzati come albero di Merkle. Il download può avvenire in parallelo da fonti multiple: ogni chunk viene verificato singolarmente rispetto alla Merkle root prima di essere accettato, rendendo impossibile la distribuzione di chunk corrotti o malevoli.

Database e storage: i database distribuiti (Cassandra, DynamoDB, etcd) usano alberi di Merkle per sincronizzare in modo efficiente repliche divergenti: confrontando le Merkle root, poi scendendo nell’albero solo dove i nodi differiscono, si individuano in $O(\log n)$ confronti le discrepanze invece di comparare l’intero dataset.