Cos'è un albero Merkle?
Il concetto di albero Merkle è stato proposto all’inizio degli anni ’80 da Ralph Merkle, un informatico famoso per il suo lavoro sulla crittografia a chiave pubblica.
Un albero Merkle è una struttura utilizzata per verificare in modo efficiente l'integrità dei dati in un set. Sono particolarmente interessanti nel contesto delle reti peer-to-peer, in cui i partecipanti devono condividere e convalidare in modo indipendente le informazioni.
Le funzioni hash sono al centro delle strutture ad albero Merkle, quindi ti consigliamo di dare un'occhiata a Cos'è l'hashing? prima di procedere.
Come funzionano gli alberi Merkle?
Supponiamo che tu voglia scaricare un file di grandi dimensioni. Con il software open source, in genere vorresti verificare che l'hash del file scaricato corrisponda a quello reso pubblico dagli sviluppatori. Se è così, sai che il file che hai sul tuo computer è esattamente uguale al loro.
Se gli hash non corrispondono, hai un problema. Hai scaricato un file dannoso mascherato da software oppure non è stato scaricato correttamente e, pertanto, non funzionerà. In quest'ultimo caso, probabilmente non sarai molto felice se dovessi aspettare un po' di tempo per il download del file. Ora devi riavviare il processo e sperare che non si corrompe nuovamente.
Se solo ci fosse un modo più semplice per farlo, pensi. Fortunatamente, è qui che entrano in gioco gli alberi Merkle. Con uno di questi, il tuo file sarebbe suddiviso in blocchi. Se fosse un file da 50 GB, potresti dividerlo in cento parti, in modo che ciascuna abbia una dimensione di 0,5 GB. Quindi, verrebbe scaricato pezzo per pezzo. Questo è essenzialmente ciò che fai quando scarichi file torrent.
In questo caso, la tua fonte ti avrà fornito un hash noto come radice Merkle. Questo singolo hash è una rappresentazione di ogni blocco di dati che costituisce il tuo file. Ma la radice Merkle rende molto più semplice la verifica dei dati.
Per semplificare, facciamo un esempio in cui utilizziamo un file da 8 GB suddiviso in otto parti. Chiama i diversi frammenti da A a H. Ogni frammento viene quindi passato attraverso una funzione hash, ottenendo otto hash diversi.
Passiamo ciascuno dei nostri otto frammenti attraverso una funzione hash per ottenere i relativi hash.
Ok, quindi abbiamo qualcosa che ha un po' più senso. Abbiamo l’hash di tutti i frammenti, quindi se uno è difettoso lo sapremo confrontandolo con quello della fonte, giusto? Forse, ma è anche incredibilmente inefficiente. Se il tuo file ha migliaia di frammenti, li eliminerai davvero tutti e confronterai meticolosamente i risultati?
No. Invece prenderemo ogni coppia di hash, li combineremo e poi li uniremo insieme. Quindi otteniamo hA + hB, hC + hD, hE + hF e hG + hH. Finiamo con quattro hash. Quindi eseguiamo un altro giro di hashing con questi per finire con due. Infine, eseguiamo l'hashing dei restanti due per ottenere il nostro hash principale: la radice Merkle (o root hash).
La struttura sembra un albero capovolto. Nella riga inferiore abbiamo le foglie, che si uniscono per produrre i nodi e, infine, la radice.
Ora abbiamo la radice Merkle che rappresenta il file che abbiamo scaricato. Possiamo confrontare questo hash root con quello fornito dalla fonte. Se corrisponde, perfetto! Ma se gli hash sono diversi possiamo essere sicuri che i dati sono stati modificati. In altre parole, uno o più frammenti hanno prodotto un hash diverso. Quindi qualsiasi leggera modifica dei dati ci darà una radice Merkle totalmente diversa.
Fortunatamente, esiste un modo pratico per verificare quale frammento è difettoso. Nel nostro caso, diciamo che è hE. Inizieresti chiedendo a un peer i due hash che hanno prodotto la radice Merkle (hABCD e hEFGH). Il tuo valore hBCD dovrebbe corrispondere al loro poiché non ci sono errori in quel sottoalbero. Ma hEFGH non lo farà, quindi sappi che devi controllare lì. Quindi richiedi hEF e hGH e li confronti con i tuoi. hGH sembrerà a posto, quindi sai che hEF è il nostro colpevole. Infine, confronti gli hash di hE e hF. Ora sai che hE non è corretto, quindi puoi scaricare nuovamente quel pezzo.
Riassumendo, un albero Merkle viene creato dividendo i dati in molti pezzi, che vengono poi sottoposti a hashing ripetutamente per formare la radice Merkle. Puoi quindi verificare in modo efficiente se qualcosa è andato storto con un dato. Come vedremo nella prossima sezione, ci sono anche altre applicazioni interessanti.
Vuoi iniziare con la criptovaluta? Acquista Bitcoin su Binance!
Perché le radici Merkle vengono utilizzate in Bitcoin?
Esistono alcuni casi d'uso per gli alberi Merkle, ma qui ci concentreremo sulla loro importanza nelle blockchain. Gli alberi Merkle sono essenziali in Bitcoin e in molte altre criptovalute. Sono parte integrante di ogni blocco e possono essere trovati nelle intestazioni dei blocchi. Per ottenere le foglie per il nostro albero, utilizziamo l'hash della transazione (il TXID) di ogni transazione inclusa nel blocco.
La radice Merkle ha un paio di scopi in questo caso. Diamo un'occhiata alle loro applicazioni nel mining di criptovaluta e nella verifica delle transazioni.
Estrazione
Un blocco Bitcoin è composto da due pezzi. La prima parte è l'intestazione del blocco, un segmento di dimensione fissa contenente i metadati per il blocco. La seconda parte è un elenco di transazioni la cui dimensione è variabile, ma tende ad essere molto più grande dell'intestazione.
I minatori devono eseguire ripetutamente l'hashing dei dati per produrre un output che soddisfi determinate condizioni per estrarre un blocco valido. Possono fare trilioni di tentativi prima di trovarne uno. Ad ogni tentativo, modificano un numero casuale nell'intestazione del blocco (il nonce) per produrre un output diverso. Ma gran parte del blocco rimane la stessa. Possono esserci migliaia di transazioni e dovresti comunque eseguirne l'hashing ogni volta.
Una radice Merkle semplifica notevolmente il processo. Quando inizi il mining, allinei tutte le transazioni che desideri includere e costruisci un albero Merkle. Inserisci l'hash root risultante (32 byte) nell'intestazione del blocco. Quindi, quando esegui il mining, devi solo eseguire l'hashing dell'intestazione del blocco, anziché dell'intero blocco.
Funziona perché è a prova di manomissione. Riassumi in modo efficace tutte le transazioni del blocco in un formato compatto. Non puoi trovare un'intestazione di blocco valida e successivamente modificare l'elenco delle transazioni, perché ciò cambierebbe la radice Merkle. Quando il blocco viene inviato ad altri nodi, calcolano la radice dall'elenco delle transazioni. Se non corrisponde a quello nell'intestazione, rifiutano il blocco.
Verifica
C’è un’altra proprietà interessante delle radici di Merkle che possiamo sfruttare. Questo riguarda i light client (nodi che non detengono una copia completa della blockchain). Se stai eseguendo un nodo su un dispositivo con risorse limitate, non vuoi scaricare e sottoporre ad hashing tutte le transazioni di un blocco. Quello che puoi fare invece è semplicemente richiedere una prova Merkle – prova fornita dal nodo completo che dimostra che la tua transazione si trova in un blocco particolare. Questo è più comunemente chiamato verifica semplificata dei pagamenti, o SPV, ed è stato dettagliato da Satoshi Nakamoto nel whitepaper Bitcoin.
Per controllare l'hD, abbiamo bisogno solo degli hash mostrati in rosso.
Consideriamo lo scenario in cui vogliamo conoscere informazioni sulla transazione il cui TXID è hD. Se ci viene fornito hC, possiamo elaborare hCD. Quindi, abbiamo bisogno di hAB per calcolare hABCD. Infine, con hEFGH, possiamo verificare che la radice Merkle risultante corrisponda a quella dell'intestazione del blocco. Se così fosse, sarebbe la prova che la transazione era inclusa nel blocco: sarebbe quasi impossibile creare lo stesso hash con dati diversi.
Nell'esempio sopra, abbiamo dovuto eseguire l'hashing solo tre volte. Senza una dimostrazione di Merkle, avremmo dovuto ripeterla sette volte. Poiché oggigiorno i blocchi contengono migliaia di transazioni, l’utilizzo delle prove Merkle ci fa risparmiare molto tempo e risorse informatiche.
Pensieri conclusivi
Gli alberi Merkle si sono rivelati estremamente utili in una serie di applicazioni informatiche: come abbiamo visto, sono incredibilmente preziosi nelle blockchain. Nei sistemi distribuiti, gli alberi Merkle consentono una facile verifica delle informazioni senza inondare la rete con dati non necessari.
Senza gli alberi Merkle (e le radici Merkle), i blocchi di Bitcoin e di altre criptovalute non sarebbero così compatti come lo sono oggi. E mentre i light client mancano sul fronte della privacy e della sicurezza, le prove Merkle consentono agli utenti di verificare se le loro transazioni sono state incluse in un blocco con un sovraccarico minimo.
