Albero di Merkle
In crittografia e informatica, un albero hash o albero di Merkle è un albero in cui ogni nodo foglia è etichettato con l'hash crittografico di un blocco di dati e ogni nodo non foglia è etichettato con l'hash crittografico delle etichette dei suoi nodi figli. Gli alberi hash consentono una verifica efficiente e sicura dei contenuti di grandi strutture di dati. Gli alberi hash sono una generalizzazione di elenchi di hash e catene di hash.
Dimostrare che un nodo foglia è una parte di un dato albero hash binario richiede il calcolo di un numero di hash proporzionale al logaritmo del numero di nodi foglia dell'albero; questo contrasta con gli elenchi hash, dove il numero è proporzionale al numero di nodi foglia stesso.
Il concetto di albero hash prende il nome da Ralph Merkle, che lo brevettò nel 1979.
Utilizzi[modifica | modifica wikitesto]
Gli alberi hash possono essere utilizzati per verificare qualsiasi tipo di dati archiviati, gestiti e trasferiti tra computer. Possono aiutare a garantire che i blocchi di dati ricevuti da altri peer in una rete peer-to-peer vengano ricevuti intatti e inalterati, anche per verificare che gli altri peer non mentano e inviino blocchi falsi.
Gli alberi hash vengono utilizzati nella crittografia basata su hash . Gli alberi hash vengono utilizzati anche nei file system IPFS, Btrfs e ZFS[1] (per contrastare il degrado dei dati[2]); Protocollo Dat; Protocollo Apache Wave;[3] Sistemi di controllo di revisione distribuiti Git e Mercurial; il sistema di backup Tahoe-LAFS; Zeronet; le reti peer-to-peer Bitcoin ed Ethereum; il quadro per la trasparenza dei certificati; e una serie di sistemi NoSQL come Apache Cassandra, Riak e Dynamo .[4] È stato suggerito di utilizzare alberi hash in sistemi informatici affidabili.
L'implementazione iniziale di Bitcoin degli alberi Merkle di Satoshi Nakamoto applica la fase di compressione della funzione hash in misura eccessiva, che viene mitigata utilizzando Fast Merkle Trees.
Panoramica[modifica | modifica wikitesto]
Un albero hash è un albero di hash in cui le foglie sono hash di blocchi di dati, ad esempio, un file o un insieme di file. I nodi più in alto nell'albero sono gli hash dei rispettivi figli. Ad esempio, nell'immagine hash 0 è il risultato dell'hashing della concatenazione di hash 0-0 e hash 0-1 . Cioè, hash 0 = hash (hash (0-0) + hash (0-1)) dove + denota concatenazione.
La maggior parte delle implementazioni dell'albero hash sono binarie (due nodi figlio sotto ogni nodo) ma possono anche usare molti più nodi figlio sotto ogni nodo.
Di solito, per l'hashing viene utilizzata una funzione hash crittografica come SHA-2. Se l'albero hash deve solo proteggere da danni involontari, è possibile utilizzare checksum non protetti come CRC.
Nella parte superiore di un albero hash c'è un hash superiore (o hash radice o hash principale ). Prima di scaricare un file su una rete p2p, nella maggior parte dei casi l'hash superiore viene acquisito da una fonte attendibile, ad esempio un amico o un sito Web noto per avere buoni consigli sui file da scaricare. Quando l'hash superiore è disponibile, l'albero hash può essere ricevuto da qualsiasi fonte non attendibile, come qualsiasi peer nella rete p2p. Quindi, l'albero hash ricevuto viene confrontato con l'hash superiore attendibile e se l'albero hash è danneggiato o falso, verrà provato un altro albero hash da un'altra fonte finché il programma non ne trova uno che corrisponde all'hash superiore.[5]
La differenza principale rispetto a un elenco hash è che un ramo dell'albero hash può essere scaricato al momento e l'integrità di ogni ramo può essere verificata immediatamente, anche se l'intero albero non è ancora disponibile. Ad esempio, nell'immagine, l'integrità del blocco dati L2 può essere verificata immediatamente se l'albero contiene già hash 0-0 e hash 1 eseguendo l'hashing del blocco dati e combinando iterativamente il risultato con hash 0-0 e poi hash 1 e infine confrontando il risultato con l' hash superiore. Allo stesso modo, l'integrità del blocco dati L3 può essere verificata se l'albero ha già hash 1-1 e hash 0. Questo può essere un vantaggio poiché è efficiente suddividere i file in blocchi di dati molto piccoli in modo che solo i blocchi piccoli debbano essere scaricati nuovamente se vengono danneggiati. Se il file con hash è molto grande, un tale albero hash o l'elenco hash diventa molto grande. Ma se è un piccolo ramo dell'albero può essere scaricato rapidamente, può essere verificata l'integrità del ramo e quindi si può iniziare il download dei blocchi di dati.
Second preimage attack[modifica | modifica wikitesto]
La radice hash Merkle non indica la profondità dell'albero, consentendo un second preimage attack in cui un utente malintenzionato crea un documento diverso dall'originale che ha la stessa radice hash Merkle. Per l'esempio precedente, un utente malintenzionato può creare un nuovo documento contenente due blocchi di dati, dove il primo è hash 0-0 + hash 0-1 e il secondo è hash 1-0 + hash 1-1.
Una semplice correzione è definita nel Certificate Transparency: quando si calcolano gli hash dei nodi foglia, viene anteposto un byte 0x00 ai dati hash, mentre 0x01 viene anteposto quando si calcolano gli hash dei nodi interni.[5] Limitare la dimensione dell'albero hash è un prerequisito di alcune prove di sicurezza formali e aiuta a rendere alcune prove più strette. Alcune implementazioni limitano la profondità dell'albero utilizzando prefissi di profondità dell'albero hash prima degli hash, quindi qualsiasi catena hash estratta è definita valida solo se il prefisso diminuisce ad ogni passaggio ed è ancora positivo quando viene raggiunta la foglia.
Tiger tree hash[modifica | modifica wikitesto]
Il Tiger tree hash è una forma ampiamente utilizzata di hash tree. Utilizza un albero hash binario (due nodi figlio sotto ogni nodo), di solito ha una dimensione del blocco dati di 1024 byte e utilizza l'hash Tiger.
Gli hash dell'albero della tigre sono utilizzati nei protocolli di condivisione di file P2P Gnutella, Gnutella2 e Direct Connect e in applicazioni di condivisione di file come Phex, BearShare, LimeWire, Shareaza, DC ++ e Valknut.
Esempio[modifica | modifica wikitesto]
Base32 : R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ
URN : urn:tree:tiger:R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ
magnet : magnet:?xt=urn:tree:tiger:R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ
Note[modifica | modifica wikitesto]
- ^ Copia archiviata, su Jeff Bonwick's Blog. URL consultato il 19 maggio 2021 (archiviato dall'url originale il 6 maggio 2017).
- ^ Likai Liu, likai.org, http://lifecs.likai.org/2014/06/bitrot-resistance-on-single-drive.html.
- ^ Copia archiviata, su Google Wave Protocol. URL consultato il 9 marzo 2017 (archiviato dall'url originale il 28 settembre 2013).
- ^ Adam Marcus, aosabook.org, http://www.aosabook.org/en/nosql.html.«When a replica is down for an extended period of time, or the machine storing hinted handoffs for an unavailable replica goes down as well, replicas must synchronize from one another. In this case, Cassandra and Riak implement a Dynamo-inspired process called anti-entropy. In anti-entropy, replicas exchange Merkle trees to identify parts of their replicated key ranges which are out of sync. A Merkle tree is a hierarchical hash verification: if the hash over the entire keyspace is not the same between two replicas, they will exchange hashes of smaller and smaller portions of the replicated keyspace until the out-of-sync keys are identified. This approach reduces unnecessary data transfer between replicas which contain mostly similar data.»
- ^ a b (EN) B. Laurie, A. Langley e E. Kasper, Certificate Transparency, in IETF, June 2013, pp. RFC6962, DOI:10.17487/rfc6962.
Voci correlate[modifica | modifica wikitesto]
Collegamenti esterni[modifica | modifica wikitesto]
- (EN) US4309569, United States Patent and Trademark Office, Stati Uniti d'America.
- Formato Tree Hash EXchange (THEX)
