Tutto quello che devi sapere sugli alberi di Merkle

Un albero di Merkle, dal nome dello scienziato Ralph Merkle, o albero di hash, è una formazione di dati basata su hash utilizzata in crittografia e informatica.

Ricordi quello che hai imparato sulle funzioni di hash nella Lezione 19 della sezione Intermedia della Bitpanda Academy? Le funzioni di hash vengono utilizzate per uniformare la lunghezza dei contenuti, per renderli sicuri e per identificare le transazioni all'interno di una blockchain. 

Che cos'è un albero di Merkle?

Nella rete Bitcoin, gli alberi di Merkle vengono utilizzati per la verifica dei dati. Tale metodo è efficiente perché vengono utilizzati degli hash invece di un file di informazioni completo. Un albero di Merkle è un albero di valori con hash, come illustrato nell'immagine seguente:

Che cos'è un albero di Merkle?

Le caselle blu in basso, ovvero "m0", "m1", "m2" e "m3", rappresentano i dati. Questi dati "m" non sono considerati parte dell'albero di Merkle. Ora, se il valore contenuto in tale casella, indicato con la lettera "m" minuscola, viene sottoposto ad hashing, otterrai un valore con hash, indicato nella casella gialla in alto con la lettera "M" maiuscola. 

Nodo radice e nodi foglia

Le caselle gialle nell'infografica rappresentano i "nodi foglia" e indicano i dati che sono stati sottoposti ad hashing. I due valori "M0" e "M1" vengono sommati, come indicato dal segno "+", e sottoposti ad hashing insieme, come rappresentato nel riquadro grigio scuro qui sopra; il risultato è un altro valore con hash contenente i "valori dei nodi figli". Infine, questi valori vengono sommati e sottoposti ad hash, ottenendo un'unica "radice", chiamata anche "radice di Merkle". 

I due nodi sotto un nodo padre sono i relativi "nodi figli". 

L'hash principale è l'hash più alto nella struttura dati basata su hash. Ciò che è importante per noi è la relazione con Bitcoin, dove questa radice fa parte dell'intestazione del blocco. Assicura che le transazioni siano presenti.

Un albero di Merkle utilizza un tipo speciale di terminologia descrittiva per descrivere le relazioni tra nodi e livelli di nodi, come quelli utilizzati durante il processo di verifica semplificata dei pagamenti (SPV).

Un nodo che contiene i valori dei due nodi sottostanti è il "padre" di questi due nodi. Se ogni nodo ha al massimo due "nodi figli", o "figli", si parla di albero hash binario. 

I due nodi sotto un nodo padre sono i relativi "nodi figli". Un nodo figlio vicino a un altro nodo figlio è il "fratello" di quel nodo figlio. Tutti i nodi in basso che non hanno "figli" sono chiamati "nodi foglia" e si trovano sullo stesso livello.

Il motivo, come puoi vedere, è che l'albero di hash è una struttura ad albero, in cui ogni nodo foglia costituisce un hash di un blocco di dati. Di solito, gli alberi di Merkle utilizzano una struttura ad albero binario, ma è possibile utilizzare anche un livello di output superiore. L'impostazione di un albero di Merkle perfetto prevede che il numero di foglie sia sempre 2n, con il valore "n" pari a 1, 2, 3 ecc. Ogni nodo ha due "nodi figli" oppure nessuno.

Albero di Merkle: nodo radice, nodo, nodo foglia 

Come vengono utilizzati gli alberi di Merkle nella tecnologia blockchain e perché?

Nella rete Bitcoin, tutte le transazioni all'interno di un blocco vengono riassunte in un albero di Merkle, producendo una sorta di impronta digitale dell'intero insieme di transazioni. In questo modo un utente è in grado di verificare se una transazione è inclusa o meno in un blocco.

Tutti i nodi della struttura ad albero dell'albero di Merkle sono rappresentazioni parziali dei dati sottoposti ad hash sottostanti. 

A questo punto forse ti chiederai perché è necessario un albero di hash per effettuare tale verifica. Non sarebbe possibile fare l'hash di tutti i messaggi (i dati originali), mettere i valori con hash in un'unica stringa e ottenere il valore dell'hash principale in questo modo? Perché gli alberi di Merkle semplificano le cose?

Il problema della fiducia

Immagina la vita senza alberi di Merkle. Al posto della radice Merkle, dovremmo memorizzare un hash di tutte le transazioni della blockchain nell'intestazione del blocco. Ciò significa che per verificare una sola transazione, dovresti scaricare i dati di tutte le transazioni. 

Gli alberi di Merkle riducono la quantità di dati necessari per la verifica. Supponiamo che Susanna voglia dimostrare a Giovanni che la transazione "m6" non è stata alterata. Giovanni potrebbe ottenere l'hash radice da una fonte affidabile e verificare che effettivamente sia così. 

Se Susanna e Giovanni procedessero senza alberi di Merkle, Susanna dovrebbe fornire a Giovanni tutte le transazioni con hash per dimostrare che la transazione "m6" non è stata alterata. Un albero di Merkle offre un modo migliore per effettuare tale verifica. Anche in questo caso, Giovanni ottiene la radice da una fonte di cui si fida. Questa volta, se Susanna vuole dimostrare che "m6" non è stata alterata, deve solo inviare il messaggio e i quattro valori con hash (mostrati in viola) a Giovanni, come indicato nel grafico sottostante: 

Albero di Merkle 

Tutti i nodi della struttura ad albero dell'albero di Merkle sono rappresentazioni parziali dei dati sottoposti ad hash sottostanti. Le foglie dell'albero di Merkle sono hash delle singole transazioni. 

Verifica delle incongruenze

Nelle reti distribuite e peer-to-peer come la blockchain di Bitcoin, gli stessi dati esistono su ogni computer della rete peer-to-peer. Ogni volta che la blockchain viene modificata attraverso l'aggiunta di una transazione, le modifiche si riflettono simultaneamente su tutti i computer dell'intera rete.

Giovanni può ora ricostruire la parte dell'albero di Merkle che è rilevante per trovare la radice di Merkle. Può usarlo per verificare i valori con hash provenienti da una fonte non attendibile. Se l'hash radice ricostruito corrisponde al valore dell'hash radice della fonte attendibile, può accettare la transazione. È più facile, e altrettanto sicuro, ricreare una porzione di un albero di Merkle che verificare i dati a fronte di tutti i dati con hash.

In sintesi, l'utilizzo di un albero di Merkle per la verifica delle incongruenze accelera notevolmente il processo di convalida, poiché solo gli hash e i file non ancora completi vengono inviati in rete, rendendo il processo più pratico e occupando molto meno spazio nella memoria di un computer.