Un Merkle tree è una struttura dati ad albero, utilizzata per riassumere e verificare in modo efficiente l’integrità di grandi set di dati.
Un Merkle tree è una parte fondamentale del protocollo Bitcoin. All’interno di qualsiasi blocco della blockchain di Bitcoin è presente un Merkle tree.
Il concetto di Merkle Tree prende il nome da Ralph Merkle, che lo brevettò nel 1979.
Il Merkle tree viene utilizzato per organizzare molteplici transazioni in un unico blocco, permettendo una verifica efficiente e sicura del contenuto delle transazioni.
Aiuta a ridurre la quantità di dati da conservare, trasmettere e controllare per la validazione delle transazioni, garantendo allo stesso tempo l’integrità e la sicurezza dei dati.
Un Merkle Tree fa uso di hash e combinazioni di hash per garantire l’immutabilità di un dato e per permettere una verifica a posteriori veloce ed economica.
Come funziona un Merkle Tree?
I seguenti passaggi ne descrivono il funzionamento:
1. Ogni transazione in un blocco ha un identificatore univoco chiamato hash.
2. Le transazioni vengono accoppiate, i due hash delle transazioni vengono combinati e viene fatto l’hash del risultato. Tale processo crea un nuovo hash derivante dall’unione dei singoli hash delle due transazioni.
3. Questo processo continua verso l’alto dell’albero (accoppiando e facendo l’hash delle coppie di hash), fino a che non si finisce con un solo hash, conosciuto come Merkle Root.
4. La Merkle Root viene quindi inserita nell’intestazione del blocco insieme ad altre informazioni, come l’hash del blocco precedente. Ciò consente a chiunque di verificare che una transazione sia inclusa in un determinato blocco costruendo un percorso dalla transazione alla radice, noto come Merkle proof o Merkle path.
Altri casi d’uso oltre Bitcoin
I Merkle tree sono utilizzati in diverse applicazioni, tra cui:
- File system: vengono utilizzati per verificare l’integrità dei file all’interno di un file system distribuito come InterPlanetary File System (IPFS).
- Database system: vengono utilizzati per rilevare incoerenze tra le repliche di interi database NoSQL come Apache Cassandra e Amazon DynamoDB.
- Version control system: alcuni dei sistemi di version control più diffusi come Git e Mercurial utilizzano i Merkle tree per gestire le versioni dei file e delle directory.
