Il concetto di Merkle tree, o albero Merkle, è stato proposto nei primi anni ‘80 da Ralph Merkle – un informatico rinomato per il suo lavoro nell'ambito della
crittografia a chiave pubblica.
Un Merkle tree è una struttura usata per verificare in modo efficiente l'integrità dei dati in un insieme. Sono particolarmente interessanti nel contesto dei network
peer-to-peer, in cui i partecipanti devono condividere e validare informazioni in modo indipendente.
Le funzioni di hash sono al centro delle strutture Merkle tree, quindi raccomandiamo di leggere
Cos'è l'Hashing? prima di procedere.
Supponiamo di voler scaricare un file di grandi dimensioni. Con un
software open-source, in genere dobbiamo controllare che la hash del file scaricato corrisponda con quella resa pubblica dagli sviluppatori. Se corrisponde, sappiamo che il file sul nostro computer è esattamente lo stesso.
Se le hash non corrispondono, abbiamo un problema. O abbiamo scaricato un file dannoso camuffato dal software che volevamo, oppure non è stato scaricato correttamente e, quindi, non funzionerà. In quest'ultimo caso, probabilmente non saremo felici di aver dovuto aspettare tutto questo tempo per scaricare il file, solo per scoprire che dobbiamo riavviare il processo e sperare che non si corrompa di nuovo.
Se solo ci fosse un modo più semplice. Fortunatamente, qui entrano in gioco i Merkle tree. Con uno di questi, il tuo file verrebbe scomposto in frammenti. Nel caso di un file da 50GB, potresti dividerlo in cento parti, in modo che ognuna pesi 0,5GB. Dopodiché, verrebbe scaricato parte per parte. Questo è essenzialmente ciò che accade con i torrent.
In questo caso, la tua fonte avrà fornito una hash conosciuta come la Merkle root. Questa singola hash è una rappresentazione di ogni parte di dati che compone il tuo file, ma la Merkle root rende molto più semplice la verifica dei dati.
Per semplificare, facciamo un esempio in cui usiamo un file da 8GB scomposto in otto parti. Chiamiamo i vari frammenti da A a H. Ciascun frammento viene poi elaborato attraverso una funzione di hash, fornendo otto hash differenti.
Elaboriamo ciascuno dei nostri otto frammenti attraverso una funzione di hash per ottenere le loro hash.
Ok, ora abbiamo qualcosa che ha un po' più senso. Abbiamo la hash di tutti i frammenti, quindi se una di queste è difettosa lo scopriremo confrontandola con quella della fonte, giusto? Forse, ma questo metodo è anche incredibilmente inefficiente. Se il tuo file ha migliaia di frammenti, vorresti davvero creare hash per ogni singolo frammento e confrontare meticolosamente i risultati?
No. Invece prendiamo ogni coppia di hash, le combiniamo e creiamo una hash dell'insieme. Quindi creiamo una hash di hA + hB, hC + hD, hE + hF, e hG + hH. Il risultato finale sono quattro hash. Ora proseguiamo con un altro round di hashing e queste quattro diventano due. Infine, creiamo la hash delle due rimanenti per ottenere la nostra master hash – la Merkle root (o root hash).
La struttura assomiglia a un albero capovolto. Nella fila in basso, abbiamo le foglie, che vengono combinate per produrre i nodi e, in cima, la radice.
Ora abbiamo la Merkle root che rappresenta il file scaricato. Possiamo confrontare questa root hash con quella fornita dalla fonte. Se corrisponde, perfetto! Invece, se le hash sono diverse, possiamo essere sicuri che i dati sono stati modificati. In altre parole, uno o più frammenti hanno prodotto una hash differente. Quindi, qualsiasi piccola modifica dei dati ci darà una Merkle root totalmente diversa.
Per fortuna, abbiamo un modo pratico per controllare quale frammento è difettoso. Nel nostro caso, supponiamo sia hE. Iniziamo chiedendo a un peer le due hash che hanno prodotto la Merkle root (hABCD e hEFGH). Il nostro valore hABCD dovrebbe corrispondere al loro, visto che non ci sono errori in questo subtree, mentre hEFGH non corrisponderà, quindi sappiamo di dover controllare qui. Dopodiché richiediamo hEF e hGH e le confrontiamo con le nostre. hGH risulta corretto, quindi sappiamo che hEF è il nostro colpevole. Infine, confrontiamo le hash di hE e hF. Ora sappiamo che hE non è corretto, quindi possiamo scaricare di nuovo questo frammento.
Riassumendo il tutto, un Merkle tree si crea dividendo dati in diverse parti, le quali vengono poi elaborate in hash ripetutamente per formare la Merkle root. E' quindi possibile verificare se qualcosa è andato storto con un frammento di dati. Come vedremo nella prossima sezione, esistono anche altre interessanti applicazioni.
Vuoi iniziare con le criptovalute? Compra Bitcoin su Binance!
Ci sono diversi casi d'uso per i Merkle tree, ma in questo articolo ci concentreremo sulla loro importanza nelle
blockchain. I Merkle tree sono essenziali in
Bitcoin e molte altre criptovalute. Sono un componente integrale di ogni
blocco, possiamo trovarli nell'
header del blocco. Per ottenere le foglie del nostro albero, usiamo la hash della transazione (la
TXID) di ogni transazione inclusa nel blocco.
In questo caso, la Merkle root ha un paio di finalità. Diamo un'occhiata alle applicazioni nel mining di criptovalute e nella verifica delle transazioni.
Mining
Un blocco Bitcoin è composto da due parti. La prima parte è l'header del blocco, un segmento di dimensione fissa che contiene i
metadati per il blocco. La seconda parte è una lista di transazioni e presenta dimensioni variabili, ma tende ad essere molto più grande dell'header.
Per minare un blocco valido, i miner devono elaborare dati in hash ripetutamente per produrre un output che corrisponde a determinate condizioni. Possono fare trilioni di tentativi prima di trovarne uno. Con ogni tentativo, cambiano un numero casuale nell'header del blocco (la
nonce) per produrre un output differente, mentre il resto del blocco rimane lo stesso. Possono esserci migliaia di transazioni, e dovresti crearne l'hash ogni volta.
Una Merkle root semplifica notevolmente il processo. Quando inizi a fare mining, allinei tutte le transazioni che vuoi includere e costruisci un Merkle tree. Inserisci la root hash (32 byte) risultante nell'header del blocco. Quindi, quando fai mining, devi solo fare l'hashing dell'header del blocco, invece del blocco intero.
Questo processo funziona perché è a prova di manomissione. Concretamente stai sintetizzando tutte le transazioni del blocco in un formato compatto. Non puoi trovare un header del blocco valido e in seguito modificare la lista di transazioni, perché facendolo cambieresti la Merkle root. Quando il blocco viene inviato ad altri nodi, questi calcolano la root dalla lista di transazioni. Se non corrisponde a quella nell'header, rifiutano il blocco.
Verifica
C'è un'altra interessante proprietà delle Merkle root che possiamo sfruttare. Questa riguarda i light client (i nodi che non conservano una copia integrale della blockchain). Se stai eseguendo un nodo su un dispositivo con risorse limitate, non vuoi scaricare e creare hash di tutte le transazioni di un blocco. Quello che puoi fare piuttosto è semplicemente richiedere una Merkle proof – una prova fornita dal full node che dimostra che la tua transazione si trova in un particolare blocco. Questo processo è più comunemente indicato come Simplified Payment Verification, o SPV, ed è stato dettagliato da
Satoshi Nakamoto nella whitepaper di Bitcoin.
Per controllare hD, abbiamo solo bisogno delle hash mostrate in rosso.
Consideriamo lo scenario in cui vogliamo avere informazioni sulla transazione con TXID hD. Se ci viene fornito hC, possiamo calcolare hCD. Quindi, ci serve hAB per calcolare h ABCD. Infine, con hEFGH, possiamo controllare che la Merkle root risultante corrisponda a quella nell'header del blocco. In caso affermativo, questa è la prova che la transazione è stata inclusa nel blocco – sarebbe praticamente impossibile creare la stessa hash con dati differenti.
Nell'esempio riportato sopra, abbiamo dovuto creare solo tre hash. Senza una Merkle proof, avremmo dovuto farlo sette volte. Considerando che i blocchi di oggi contengono migliaia di transazioni, usare le Merkle proof ci fa risparmiare un sacco di tempo e risorse computazionali.
I Merkle tree si sono dimostrati molto utili in una serie di applicazioni informatiche – come abbiamo visto, sono incredibilmente importanti nelle blockchain. Nei sistemi distribuiti, i Merkle tree consentono una facile verifica delle informazioni senza inondare il network con dati inutili.
Senza i Merkle tree (e le Merkle root), i blocchi di
Bitcoin e altre
criptovalute sarebbero molto meno compatti di quanto lo sono oggi. E anche se i light client sono carenti sui fronti di privacy e sicurezza, le Merkle proof permettono agli utenti di controllare se le loro transazioni sono state incluse in un blocco con un impiego di risorse minimo.
