Merkle Tree
Cos’è un albero di Merkle?
Un albero Merkle è una struttura dati utilizzata nelle applicazioni informatiche. In bitcoin e altre criptovalute, gli alberi Merkle servono a codificare i dati blockchain in modo più efficiente e sicuro.
Sono anche denominati “alberi hash binari”.
Abbattere l’albero di Merkle
Nella blockchain di bitcoin, un blocco di transazioni viene eseguito attraverso un algoritmo per generare un hash, che è una stringa di numeri e lettere che può essere utilizzata per verificare che un dato insieme di dati sia lo stesso dell’insieme originale di transazioni, ma per non ottenere l’insieme originale di transazioni. Tuttavia, il software di Bitcoin non esegue l’intero blocco di dati delle transazioni, che rappresentano in media 10 minuti di transazioni, tramite la funzione hash contemporaneamente. Piuttosto, ogni transazione viene sottoposta ad hashing, quindi ogni coppia di transazioni viene concatenata e sottoposta ad hashing insieme, e così via fino a quando non c’è un hash per l’intero blocco. (Se è presente un numero dispari di transazioni, una transazione viene raddoppiata e il relativo hash viene concatenato con se stesso.)
Visualizzata, questa struttura assomiglia a un albero. Nel diagramma seguente, “T” indica una transazione, “H” un hash. Notare che l’immagine è molto semplificata; un blocco medio contiene oltre 500 transazioni, non otto.
Gli hash nella riga inferiore sono indicati come “foglie”, gli hash intermedi come “rami” e l’hash nella parte superiore come “radice”. La radice Merkle di un dato blocco è memorizzata nell’intestazione: ad esempio, la radice Merkle del blocco # 482819 è e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f71c8. La radice viene combinata con altre informazioni (la versione del software, l’hash del blocco precedente, il timestamp, l’obiettivo di difficoltà e il nonce) e quindi viene eseguita una funzione hash per produrre l’hash unico del blocco: 000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b089594 # 489528 nel caso del blocco. Questo hash non è effettivamente incluso nel blocco pertinente, ma in quello successivo; è distinto dalla radice di Merkle.
L’albero Merkle è utile perché consente agli utenti di verificare una transazione specifica senza scaricare l’intera blockchain (oltre 130 gigabyte a fine agosto 2017). Ad esempio, supponi di voler verificare che la transazione T D sia inclusa nel blocco nel diagramma sopra. Se hai l’hash di root (H ABCDEFGH ), il processo è come un gioco di sudoku: interroghi la rete su H D e restituisce H C, H AB e H EFGH. L’albero Merkle consente di verificare che tutto sia contabilizzato con tre hash: dato H AB, H C, H EFGH e la radice H ABCDEFGH, H D (l’unico hash mancante) deve essere presente nei dati.
Gli alberi Merkle prendono il nome da Ralph Merkle, che li ha proposti in un documento del 1987 intitolato ” Una firma digitale basata su una funzione di crittografia convenzionale “. Merkle ha anche inventato l’hashing crittografico.