Contenuti
Cos'è un albero Merkle?
Come funzionano gli alberi Merkle?
Perché le radici Merkle vengono utilizzate in Bitcoin?
Estrazione
Verifica
Considerazioni conclusive
Cos'è un albero Merkle?
L'idea di un albero Merkle è nata all'inizio degli anni '80 da Ralph Merkle, uno scienziato informatico noto soprattutto per il suo lavoro nel campo della crittografia a chiave pubblica.
Un albero Merkle è una struttura utilizzata per verificare in modo efficace l'integrità dei dati in un determinato set di dati ed è particolarmente importante nel contesto delle reti peer-to-peer in cui i partecipanti devono condividere e verificare le informazioni in modo indipendente.
Le funzioni hash sono una parte essenziale delle strutture ad albero Merkle, quindi consigliamo di leggere l'articolo intitolato Cos'è l'hash? Prima di continuare a leggere questo articolo.
Come funzionano gli alberi Merkle?
Supponiamo che tu voglia scaricare un file di grandi dimensioni. Nel caso del software open source, in genere ti consigliamo di verificare che il valore hash del file scaricato corrisponda al valore reso pubblicamente disponibile dagli sviluppatori. Se lo sono, allora sai che il file che hai sul tuo computer corrisponde al loro.
Se i valori hash non corrispondono, allora hai un problema. O hai scaricato un file malware che si spaccia per il programma oppure il download non è riuscito, quindi non funziona. Se il download non va a buon fine, probabilmente non sarai contento se dovrai aspettare un po' prima che il file venga scaricato. Dovrai quindi ricominciare il processo da capo e sperare che questa volta vada bene.
Potresti pensare in questo caso se solo ci fosse un modo più semplice per farlo. Fortunatamente, è qui che entra in gioco l'albero Merkle. Utilizzando questo albero, il file viene diviso in parti. Se la dimensione del file è 50 GB, potresti essere in grado di dividerlo in 100 parti, ciascuna di 0,5 GB, e scaricarlo pezzo per pezzo. Questo è fondamentalmente ciò che fai quando usi file torrent.
In questo caso, l'origine del file ti fornirà un valore hash noto come radice Merkle. Questo singolo valore è una rappresentazione di ogni dato che costituisce il tuo file, ma la radice Merkle rende molto più semplice la verifica dei dati.
Per semplificare, esamineremo questo esempio in cui utilizziamo un file da 8 GB diviso in 8 parti e etichetteremo queste diverse parti con le lettere dalla A alla H. Quindi ciascuna parte passerà attraverso una funzione hash, risultando in 8 diversi valori hash.
Passeremo ciascuna delle otto parti attraverso una funzione hash per ottenere i relativi valori hash.
Bene, ora abbiamo qualcosa che ha un po' più senso. Abbiamo i valori hash di tutte le parti, quindi se una di queste è sbagliata, lo saprai confrontandola con il valore hash di origine, giusto? Forse, ma anche questo è estremamente inefficiente. Se il file è composto da migliaia di parti, le partizionerai davvero tutte e poi confronterai i risultati con tanta attenzione?
No, prenderemo invece ciascuna coppia di valori hash, li sommaremo e poi li eseguiremo l'hashing insieme. Quindi, eseguiamo l'hashing hA + hB, hC + hD, hE + hF e hG + hH in modo da ottenere 4 valori hash, quindi eseguiamo un altro ciclo di hashing per questi valori, raggiungendo infine 2 valori hash. Infine, eseguiamo l'hashing dei restanti due valori per ottenere il valore hash principale: la radice Merkle (o valore hash radice).
La struttura si presenta come un albero rovesciato, dove nell'ultima fila abbiamo le foglie che si uniscono per produrre i nodi ed eventualmente la radice.
Ora abbiamo la radice Merkle che rappresenta il file che abbiamo scaricato. Questo valore hash root può essere confrontato con quello fornito dalla fonte e, se corrispondono, bene! Ma se i valori di hash sono diversi, questo ci dà la certezza che i dati sono stati modificati, cioè una o più parti hanno prodotto un valore di hash diverso, quindi ogni semplice modifica ai dati ci darà una radice di Merkle completamente diversa .
Fortunatamente, esiste un modo semplice per tutti noi per verificare quale parte è sbagliata. In questo caso, diciamo che questa parte è hE. Innanzitutto, chiedi a un peer i due valori hash che hanno prodotto la radice Merkle (hABCD e hEFGH). Il tuo valore hBCD dovrebbe corrispondere al suo poiché non sono presenti errori in questo sottoalbero. Ma questo non si applica al valore hEFGH, quindi dovresti controllare questo valore. Quindi richiedi i valori hEF e hGH e confrontali con i tuoi valori. Scoprirai che il valore hGH va bene e poi ti renderai conto che il valore hEF è la ragione del problema. Infine, confronterai i valori hash di hE e hF e ora sai che hE non è corretto, quindi puoi scaricare nuovamente questo frammento.
In breve, un albero Merkle viene creato dividendo i dati in più parti, che vengono poi sottoposte ad hashing in modo iterativo per formare una radice Merkle. È quindi possibile verificare in modo efficace se si è verificato un errore con un dato. Come vedremo nella prossima sezione, ci sono anche altre applicazioni interessanti.
Vuoi iniziare a fare trading in valute digitali? Acquista subito Bitcoin (BTC) 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 di grande importanza per Bitcoin e altre criptovalute. Rappresenta un componente importante di ciascun blocco, poiché si trova nelle partizioni di archiviazione dei blocchi. Per accedere alle foglie dell'albero, utilizziamo l'hash della transazione (ID transazione) di ciascuna transazione nel blocco.
In questo caso, la radice Merkle serve ad alcuni scopi e di seguito esamineremo le sue applicazioni nel mining di criptovaluta e nella verifica delle transazioni.
Estrazione mineraria
Un blocco Bitcoin è composto da due parti, la prima parte è la partizione di archiviazione del blocco, che è una parte di dimensioni fisse che contiene i metadati per il blocco. La seconda parte è un elenco di transazioni di dimensione variabile, ma solitamente è molto più grande della partizione di archiviazione a blocchi.
I minatori devono eseguire ripetutamente l'hashing dei dati per produrre un output che soddisfi le condizioni specifiche per l'estrazione di un blocco valido. Possono fare trilioni di tentativi prima di trovare un blocco corretto. A ogni tentativo, modificano un numero casuale nella sezione di archiviazione del blocco (il codice privato) per produrre un output diverso. Tuttavia, gran parte della massa rimane la stessa. Il numero di transazioni può arrivare a migliaia di transazioni e dovrai eseguirne l'hashing ogni volta.
La radice Merkle rende il processo molto più semplice, quando inizi il mining, metti in fila tutte le transazioni che desideri includere e crei un albero Merkle. Quindi inserisci il valore hash root risultante (32 byte) nella partizione di archiviazione a blocchi. Quindi, durante l'estrazione, tutto ciò che devi fare è eseguire l'hashing della partizione di archiviazione dei blocchi anziché dell'intero blocco.
Questo metodo funziona perché non può essere manomesso, riassumendo efficacemente tutte le transazioni dei blocchi in un formato compatto. E non è possibile trovare una partizione di archiviazione a blocchi valida e quindi modificare l'elenco delle transazioni in un secondo momento perché ciò cambierebbe la radice Merkle. Quando il blocco viene inviato ad altri nodi, calcola la radice dall'elenco delle transazioni e, se non corrisponde a quanto menzionato nella sezione di archiviazione dei blocchi, il blocco viene rifiutato.
Verifica
C'è un'altra proprietà interessante delle radici di Merkle di cui possiamo trarre vantaggio. Questa funzionalità è importante per il software dei nodi semplici (nodi che non trasportano la copia completa della catena blockchain). Se stai eseguendo un nodo su una macchina con risorse limitate, non vuoi scaricare e sottoporre ad hashing tutte le transazioni del blocco, puoi invece richiedere una prova Merkle, una prova fornita dall'intero nodo che dimostra che si è verificata una transazione esiste in un blocco specifico. Questo viene spesso definito verifica semplificata dei pagamenti (SPV) ed è stato spiegato in dettaglio da Satoshi Nakamoto nel rapporto tecnico di Bitcoin.
Per verificare hD abbiamo bisogno solo dei valori hash mostrati in rosso.
Consideriamo, ad esempio, uno scenario in cui vogliamo conoscere informazioni su una transazione con ID transazione hD. Se il valore hC è a nostra disposizione, possiamo trovare hCD. Quindi abbiamo bisogno di hAB per calcolare hABCD. Infine, nel caso di hEFGH, possiamo verificare che la radice Merkle risultante corrisponda a quella nella partizione di archiviazione a blocchi. Se corrisponde, ciò è la prova che la transazione esisteva nel blocco, poiché sarebbe quasi impossibile generare lo stesso valore hash con dati diversi.
Nell'esempio precedente, dovevamo eseguire l'hash solo tre volte e, senza la dimostrazione di Merkle, avremmo dovuto eseguirlo 7 volte. Poiché oggi i blocchi contengono migliaia di transazioni, l'utilizzo della prova di Merkle consente di risparmiare molto tempo e risorse informatiche.
Considerazioni conclusive
Gli alberi Merkle si sono rivelati estremamente utili in una serie di applicazioni informatiche e, come abbiamo visto, sono di enorme importanza per le blockchain. Nei sistemi distribuiti, gli alberi Merkle semplificano la verifica delle informazioni senza inondare la rete con un torrente di dati non necessari.
Senza gli alberi Merkle (e le radici Merkle), i blocchi di Bitcoin e altre criptovalute non sarebbero così piccoli come lo sono oggi. Mentre i semplici software contrattuali mancano di privacy e sicurezza, la prova di Merkle consente agli utenti di verificare se le loro transazioni sono entrate in un blocco con costi minimi.