Albero Merkle

Albero Merkle o Albero di Hash è un albero in cui ogni nodo foglia è etichettato con un blocco di dati e ogni nodo non foglia è etichettato con l’hash crittografico delle etichette dei suoi nodi figlio. Gli alberi di hash consentono una verifica efficiente e sicura del contenuto di grandi strutture dati. Gli alberi di Hash sono una generalizzazione di liste di hash e catene di hash.

Dimostrando che un nodo foglia è una parte di un dato albero di hash binario richiede di calcolare un numero di hash proporzionali al logaritmo del numero di nodi foglia dell’albero; questo contrasta con gli elenchi di hash, in cui il numero è proporzionale al numero di nodi foglia stessa.

Il concetto di alberi di hash prende il nome da Ralph Merkle che lo brevettò nel 1979.

Albero Merkle di Bitcoin

Gli alberi di hash possono essere utilizzati per verificare ogni tipo di dati memorizzati, gestiti, e trasferiti nel e tra i computer. Attualmente, l’uso principale degli alberi di hash è quello di assicurarsi che i blocchi di dati ricevuti da altri peer in una rete peer-to-peer siano ricevuti intatti e inalterati, e anche per verificare che gli altri peer non mentano e inviano blocchi falsi. Suggerimenti sono stati fatti per utilizzare alberi di hash in sistemi di calcolo attendibili. Gli alberi di hash sono utilizzati anche nella crittografia basata su hash.

Gli alberi di hash sono utilizzati nei system di file IPFS, Btrfs e ZFS, protocollo BitTorrent, protocollo Dat, protocollo Apache Wave, sistemi di controllo di revisione distribuiti Git e Mercurial, il sistema di backup Tahoe-LAFS, le reti peer-to-peer Bitcoin ed Ethereum, il framework di trasparenza dei certificati e un certo numero di sistemi NoSQL come Apache Cassandra, Riak e Dynamo.

L’implementazione iniziale di bitcoin di alberi Merkle applica la fase di compressione della funzione hash in misura eccessiva, che viene mitigata utilizzando alberi Merkle veloci.

Recensione di Albero Merkle

Un albero di hash è un albero in cui le foglie sono hash di blocchi di dati in, per esempio, un file o un insieme di file. I nodi più in alto nell’albero sono gli hash dei loro rispettivi figli. Per esempio, nell’immagine di hash 0 è il risultato di hash, la concatenazione di hash 0-0 e hash 0-1. Cioè, hash 0 = hash (hash 0-0 + hash 0-1 ) dove + denota la concatenazione.

La maggior parte delle implementazioni di alberi sono binari (due nodi figlio sotto ogni nodo) ma possono altrettanto usare molti più nodi figlio sotto ogni nodo.

Di solito, una funzione di hash crittografico come SHA-2 viene utilizzata per l’hashing. Se l’albero hash deve solo proteggere da danni involontari, è possibile utilizzare checksum molto meno sicuri come i CRC.

Nella parte superiore di un albero di hash c’è un hash superiore. Prima di scaricare un file su una rete p2p, nella maggior parte dei casi hash superiore viene acquisito da una fonte attendibile, ad esempio un amico o un sito Web che è noto per avere buone raccomandazioni di file da scaricare. Quando hash superiore è disponibile, l’albero di hash può essere ricevuto da qualsiasi fonte non attendibile, come qualsiasi peer nella rete P2P. Quindi, l’albero di hash ricevuto viene controllato rispetto al hash superiore attendibile e, se l’albero di hash è danneggiato o falso, verrà provato un altro albero di hash da un’altra fonte fino a quando il programma non ne troverà uno che corrisponda all’hash superiore.

La differenza principale da una lista di hash è che un ramo dell’albero di hash può essere scaricato alla volta e l’integrità di ciascun ramo può essere controllata immediatamente, anche se l’intero albero non è ancora disponibile. Per esempio, nell’immagine, l’integrità del blocco dati 2 può essere verificata immediatamente se l’albero contiene già hash 0-0 e hash 1 eseguendo hash del blocco dati e combinando iterativamente il risultato con hash 0-0 e quindi hash 1 e confrontando infine il risultato con hash superiore. Allo stesso modo, l’integrità del blocco dati 3 può essere verificata se l’albero ha già hash 1-1 e hash 0. Questo può essere un vantaggio poiché è efficiente dividere i file in blocchi di dati molto piccoli in modo che solo i piccoli blocchi debbano essere scaricati nuovamente se vengono danneggiati. Se il file hash è molto grande, un tale albero di hash o un elenco di hash diventa abbastanza grande. Ma se si tratta di un albero, un piccolo ramo può essere scaricato rapidamente, è possibile controllare l’integrità del ramo e quindi avviare il download di blocchi di dati.

Secondo Attacco Preimage

La radice di hash non indica la profondità dell’albero, consentendo un secondo attacco preimage in cui un utente malintenzionato crea un documento diverso dall’originale che ha la stessa radice di hash. Per l’esempio precedente, un utente malintenzionato può creare un nuovo documento contenente due blocchi di dati, in cui il primo è hash 0-0 + hash 0-1, e il secondo è hash 1-0 + hash 1-1.

Una semplice correzione è definita nella trasparenza dei certificati: quando si elaborano gli hash dei nodi foglia, un byte 0x00 viene anteposto ai dati hash, mentre 0x01 viene anteposto quando si elaborano gli hash dei nodi interni. Limitare la dimensione dell’albero è un prerequisito di alcune prove di sicurezza formali e aiuta a rendere più strette alcune prove. Alcune implementazioni limitano la profondità dell’albero usando i prefissi di profondità dell’albero hash prima degli hash, quindi qualsiasi catena di hash estratta è definita valida solo se il prefisso diminuisce ad ogni passaggio ed è ancora positivo quando viene raggiunta la foglia.

Tiger Hash

L’albergo di tiger hash è una forma ampiamente utilizzata di albero. Utilizza un albero di hash binario (due nodi figlio sotto ogni nodo), di solito ha una dimensione del blocco dati di 1024 byte e utilizza hash Tiger.

Gli hash Tiger sono utilizzati nei protocolli di condivisione file Gnutella, Gnutella2 e Direct Connect P2P e in applicazioni di condivisione file come Phex, BearShare, LimeWire, Shareaza, DC++ e Valknut.

Esempio del Albero di Hash

Base32 #RFC 4648 Base32 alfabeto:

RBOEI7UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

Uniform Resource Name (URN):

urn: tree: tiger: RBOEI7UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

Schema di Magnet URI:

magnet: ?xt=urn: tree: tiger: RBOEI7UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ