Che cos'è un albero di Merkle?

Breve riassunto

✔️ Un Merkle tree divide i dati, crea valori hash di questi dati e li unisce in una struttura ad albero, consentendo verifiche e trasferimenti efficienti.

✔️ Inventato da Ralph Merkle, il Merkle tree è un diagramma ad albero utilizzato per l'integrità dei dati.

✔️ Gli alberi di Merkle sono ampiamente utilizzati nelle tecnologie blockchain come Bitcoin ed Ethereum, dove aiutano a convalidare le transazioni e a ridurre il carico di dati.

Cos'è un Merkle tree?

Il concetto di Merkle tree è stato inventato dal matematico americano Ralph Merkle e brevettato nel 1979. Quindi l'ex cancelliere tedesco non ha nulla a che fare con esso. È stato descritto nel paper "A certified digital signature".

Nel nome Merkle tree, l'ultima parte sta per albero. Non a caso, si tratta di un diagramma ad albero, o modello di ramificazione, in cui più rami conducono a un ramo principale. È simile al modello di ramificazione di un albero genealogico.

Un altro nome del Merkle tree è hash tree. Un hash è un derivato algoritmico di un input, cioè è possibile ricavare un hash (derivato) da, ad esempio, una parola (input) per mezzo di un certo sistema di algoritmi.

Un sistema molto noto è SHA (Secure Hash Algorithm) 256. Si tratta di ricavare un hash di 256 bit da un dato input. Il risultato (output) diventa una stringa di 64 cifre e lettere.

Un tipico derivato dell'hash SHA 256:

"Anycoindirect" ha come output quando si esegue SHA 256:

98948d20dc70322d424ea5bbf37970e20b6aafa90c498116779ea964042c2c64

"anycoindirect" ha come output:

a730a577d61512581afdd9c74e68abb2c43b0f7db3c70a92583464277b7abc81

Puoi notare che una sola lettera maiuscola cambia già tutto. Da hashish come questo, viene creato un albero. Proprio come a Natale, giusto?

Come funziona un Merkle tree?

Supponiamo che tu voglia inviare un messaggio o un file a qualcun altro, ma che non voglia che altri possano vederlo. Potrebbe trattarsi di informazioni segrete, come una password, ma anche di condividere un file con informazioni importanti. In questo caso, puoi utilizzare SHA 256 per crittografare il messaggio.

Un messaggio viene diviso in pezzi e trasformato in un hash. Ogni hash appare nell'albero, con la radice in cima all'albero. Questo è il messaggio o il file completo. Un grande vantaggio è che il messaggio può essere diviso in piccoli pezzi, il che significa che i file più grandi non devono essere consegnati interamente da un singolo computer e possono essere consegnati molto più velocemente.

L'albero viene costruito dal basso verso l'alto, proprio come avviene con Bittorrent. Ognuno ha una piccola parte del file (reti peer to peer) e alla fine dell'utente finale tutti i piccoli pezzi vengono rimessi insieme, dopodiché l'albero è di nuovo completo. L'utente finale può quindi calcolare con il suo Merkle tree se tutti i pezzi sono originali (gli hash che possono essere calcolati devono corrispondere alla sua tabella).

La radice ha un risultato specifico, quindi se la conosci, sai anche se il messaggio o il file sono originali. In caso contrario, verrà effettuato un nuovo tentativo di ricevere l'originale. Se la radice e l'output coincidono nel tuo caso, hai ricevuto le informazioni corrette.

Sopra abbiamo spiegato come creare un hash. Nel diagramma ad albero, alcuni di questi output vengono uniti e inseriti in un nuovo hash utilizzando lo stesso metodo. Quindi, man mano che si arriva in cima all'albero, sempre più informazioni appariranno in un hash superiore. Fino a quando non si arriva in cima e si uniscono tutti gli hash dell'albero in un unico hash, dopodiché si è pronti a inviare le informazioni.

Al destinatario del messaggio viene comunicata la radice dell'albero e inizia a scaricare i rami, gli hash. Questi rami possono provenire da più fonti. Dopodiché inizia a ricostruire tutti gli hash dell'albero. Ogni parte dell'albero deve essere corretta; se non lo è, l'albero principale non è corretto, ma attraverso la ricostruzione può determinare quale parte non è corretta. A quel punto, di solito, cerca di scaricare di nuovo l'intero albero.

Poiché questi Merkle tree lavorano con dati binari, vengono anche chiamati alberi binari.

A cosa servono i Merkle tree in crypto?

Ora che sai che per verificare la correttezza di un hash è sufficiente conoscere l'albero radice, potresti immaginare che esistano sistemi che ne fanno uso.

Un'importante blockchain che ne fa uso è Bitcoin. In questa blockchain, molte informazioni devono essere elaborate in un blocco. Meno informazioni si devono controllare e inserire in un blocco, meglio è.

Poiché un Merkle tree può aggregare una grande quantità di dati in un unico numero, è molto utile per la costruzione di un blocco.

Supponiamo che tu abbia elaborato 200 transazioni come Miner negli ultimi 10 minuti (un nuovo blocco viene aggiunto alla rete Bitcoin ogni 10 minuti circa). Il Merkle tree si mette al lavoro per ridurre tutte queste transazioni in un unico albero radice.

I validatori della rete Bitcoin devono tenere traccia dello stato della blockchain, convalidare le transazioni e aggiungere nuove monete. Se devono verificare la correttezza di una sola sequenza, non solo sono molto più veloci, ma il blocco è anche molto più piccolo. Se il 51% di questi Miner concorda sulla correttezza dell'albero principale, il blocco può essere aggiunto.

L'hash dell'albero radice viene inserito all'inizio del blocco successivo, in modo che tutti i Miner conoscano il valore dell'hash del blocco precedente. Così, quando creano un nuovo blocco, impostano l'intero stato della rete con un'unica stringa di cifratura. Poi vengono aggiunte nuove transazioni, che seguono lo stesso processo e così via. Se l'albero radice non è corretto, ad esempio perché ci sono dei record errati, anche i Miner non sono d'accordo e iniziano a cercare un Merkle tree con l'albero radice corretto. Anche Ethereum utilizza un albero di Merkle, ma ovviamente ha inventato qualcosa di speciale: il Merkle tree.

Se le reti non utilizzassero i Merkle tree, tutti i dati dovrebbero essere trasmessi e puoi immaginare cosa significherebbe per la velocità, per non parlare della sicurezza.