I merkle tree sono una struttura dati creata con l'obiettivo di facilitare la verifica di grandi quantità di dati organizzati mettendoli in relazione attraverso varie tecniche crittografiche e di gestione delle informazioni.

Dinserisci qualsiasi blocco della rete Bitcoin troviamo una struttura chiamata "Merkle Tree".

Un albero Merkle è una struttura dati suddivisa in diversi livelli il cui scopo è metterli in relazione nodo con un'unica radice associata ad essi. Per ottenere ciò, ogni nodo deve essere identificato con un identificatore univoco (hash). Questi nodi iniziali, chiamati nodi figli (foglie), sono quindi associati a un nodo non superiore chiamato nodo genitore (ramo). Il nodo padre avrà un identificatore univoco risultante dall'hash dei suoi nodi figlio. Questa struttura si ripete fino a raggiungere il nodo radice o radice di Merkle (radice di Merkle), la cui impronta è associata a tutti i nodi dell'albero.

Grazie a questa struttura unica, gli alberi Merkle consentono di mettere in relazione una grande quantità di dati in un unico punto (Merkle Root). In questo modo, la verifica e la validazione di questi dati può diventare molto efficiente, dovendo verificare solo la Merkle Root invece dell'intera struttura.

Questo disegno è stato creato da Ralph Merkle, nell'anno 1979, al fine di accelerare il processo di verifica di grandi quantità di dati.

Come funziona un albero Merkle?

Un albero Merkle è una struttura che mette in relazione tutte le transazioni e le raggruppa tra coppie per ottenere un file Hash radice o "indirizzo radice ". Questo root hash è correlato a tutti gli hash dell'albero. Seleziona tutto transazioni di una rete sarebbe estremamente lento e inefficiente. Per questo motivo è stato implementato questo sistema. Poiché, se un hash viene modificato, tutti gli altri cambierebbero fino a raggiungere la radice (root hash). Ciò invaliderà l'autenticità delle informazioni per l'intero albero. È proprio questa funzione che consente agli alberi Merkels di fornire l'elevato livello di sicurezza che li caratterizza.

Per capire come funziona un albero Merkle in modo più approfondito, esamina il seguente esempio:

Immagina un blocco di dati che rechi un'impronta o un hash unico e irripetibile. Ciascuno di questi blocchi è organizzato in strati in quella che vedremmo come una struttura piramidale. Questi blocchi sono collegati a un livello superiore tramite questi hash. In questo modo, i blocchi superiori puntano sempre ai blocchi inferiori, ma la cosa più importante è che l'hash di questi blocchi superiori è il risultato della somma delle informazioni contenute nel nuovo blocco con l'hash del blocco precedente. In questo modo, mentre si continua a scalare, la stessa struttura viene ripetuta mentre tutti i blocchi sono collegati a un grande blocco di dati.

Il fatto che funzioni in questo modo fa sì che la modifica dell'hash di un blocco invalidi gli hash del resto dei blocchi. In questo modo il sistema facilita due cose. Innanzitutto, semplifica la verifica dei blocchi di dati. In secondo luogo, funge da meccanismo per prevenire la manomissione. Ciò è dovuto al fatto che questo meccanismo consente di rilevare le modifiche degli hash in ogni blocco di dati. Se viene rilevata una modifica, l'intero albero viene invalidato perché è stato alterato e i suoi dati non sono validi.

Esempio di un albero Merkle, Come realizzare un albero Merkle

Caratteristiche dell'albero di Merkle

Alcune delle caratteristiche più notevoli degli alberi di Merkle sono:

  1. Sono un mezzo efficiente per generare una struttura dati distribuita.
  2. Forniscono grande sicurezza e resistenza alle alterazioni dei dati.
  3. Consentono un alto livello di prestazioni di trasmissione dei dati in reti distribuite. Grazie a ciò, riducono la quantità di dati necessari per il suo corretto funzionamento.
  4. Sono computazionalmente poco costosi ed efficienti durante la creazione, l'elaborazione e la verifica delle informazioni.
  5. Consentono la "dissezione" per ricerche di verifica più veloci. Tutto questo, senza compromettere la sicurezza e la tracciabilità delle transazioni effettuate.
  6. Grazie alla funzione di "dissezione" sono anche in grado di risparmiare risorse di archiviazione.
  7. Offrono una grande adattabilità a diversi problemi del computer. Grazie a ciò, gli alberi Merkle sono stati ampiamente utilizzati in diversi sistemi. Ad esempio, software di database, file system, strutture a chiave pubblica, sistemi di controllo delle versioni, reti distribuite (P2P), tra gli altri.

Quanto sai, Cryptonuta?

Gli alberi Merkle da soli sono una soluzione perfetta per la verifica dei dati?

FALSO!

Sebbene gli alberi Merkle siano un potente strumento per la verifica dei dati, di per sé non garantiscono la sicurezza dei dati. È per questo motivo che gli sviluppatori della tecnologia blockchain e delle criptovalute si avvalgono di altri metodi di verifica che consentono di creare un totale consenso sul fatto che i dati siano davvero al sicuro e non siano stati alterati.

Utilizza oggi

Gli alberi di Merkle hanno attualmente un ampio numero di usi nei sistemi informatici e ne parleremo qui.

Tecnologia blockchain

L'uso degli alberi Merkle nella tecnologia blockchain è di vitale importanza. Grazie al suo utilizzo, il software client può scaricare l'intera cronologia della blockchain e verificarla a caldo. Il suo utilizzo, infatti, facilita il processo consentendo “fesso"(Prendi solo una parte della cronologia) la cronologia e riduci la dimensione del download.

Ad esempio, un utente che desidera installare un client Bitcoin non deve scaricare tutta la cronologia dalla blockchain. Invece, puoi ridurre il download a poche centinaia o migliaia di blocchi indietro. In questo modo, hai accesso a una versione più leggera della cronologia più adatta alle tue esigenze.

Contrariamente a quanto si potrebbe pensare, questo non toglie nulla alla sicurezza del cliente. Ebbene, grazie all'albero Merkle, è possibile scaricare uno specifico "root hash" e da lì iniziare a creare una cronologia. Poiché "root hash" è correlato ai blocchi precedenti, tutto ciò che devi fare è verificarlo. Per fare questo, puoi andare su una serie di nodi Bitcoin completi (con tutta la cronologia) e verificare che il "root hash" preso corrisponda. Avendo assoluto consenso su questo punto, il "root hash" è considerato valido. E da quel momento in poi, l'utente può utilizzare perfettamente il suo nuovo nodo client Bitcoin.

Sistemi di file

Un'altra utilità che possiamo vedere dagli alberi Merkle si riflette nei file system. Un file system è una struttura dati che un sistema operativo utilizza per tenere traccia dei file archiviati. Normalmente questa struttura viene applicata su un hard disk e anche all'interno delle schede di memoria che utilizzano i nostri smartphone.

Alcune di queste peculiari realizzazioni si avvalgono degli alberi Merkle al fine di gestire e garantire il corretto utilizzo dei dati memorizzati. Casi speciali di menzione in questo gruppo sono i file system ZFS y btrfs.

ZFS noto come Zettabyte File System, è considerato nel mondo dell'informatica come il miglior sistema di archiviazione. Le sue abilità superano di gran lunga i suoi avversari meglio conosciuti come NTFS, FAT, exFAT o ext3 / 4. È dotato di resistenza ai guasti, recupero e correzione degli errori, deduplicazione dei dati, replica, copia su scrittura (CoW) e alta scalabilità. Tutto ciò lo rende un'opzione perfetta per essere distribuito in ambienti critici. Progettato da Sun Microsystems e introdotto nel 2004, al momento è leader nei file system per computer.

Ma per ottenere questo ZFS ha uno strumento segreto al centro di tutto il suo codice: l'uso estensivo e intensivo di alberi di Merkle. Tutto questo per avere un sistema che consenta la rapida verifica dei dati memorizzati all'interno delle proprie strutture. Le sue proprietà di ripristino degli errori, deduplicazione, CoW (Copy-On-Write) e replica dipendono fortemente da questa tecnica, altrimenti comporterebbe un costo computazionale elevato che ne minerebbe i vantaggi.

Sistemi di controllo della versione

Un altro utilizzo degli alberi Merkle può essere visto nei sistemi di versioning del software, noti casi di Idiota y mutevole. Dei due, il più conosciuto in Git, lo stesso che abilita piattaforme come Gitlab y Github, ovvero lo sviluppo del kernel Linux, quest'ultimo è stato il primo progetto ad utilizzarlo in produzione, dal momento che il creatore di Git è Linus Torvalds.

L'utilizzo degli alberi Merkle in questo tipo di software è correlato al sistema di tracciamento delle modifiche all'interno del repository o dello spazio di lavoro in cui sono archiviati i file. In questo modo, ogni modifica apportata (nuovi blocchi di dati) passa attraverso un processo di hashing che, attraversando tutto il contenuto del repository, genera un hash univoco di detto spazio di lavoro, che si chiama commit.

Questo sistema di marcatura ci consente, ad esempio, di andare a un commit specifico per vedere quale fosse lo stato del codice del progetto in un determinato momento, mentre lo stato generale del progetto rimane intatto. Vedendolo in un modo più semplice, gli alberi di Merkle in Git ci permettono di creare una sorta di macchina del tempo, che ci permette di navigare attraverso i diversi commit del progetto, mantenendo i file e le loro modifiche come erano in quel particolare momento.

Un'utilità molto utile quando si progetta software in ambienti di lavoro distribuiti e ad alto traffico, come Linus Torvalds non ha mostrato nel suo grande progetto del kernel Linux.

  • Mercurial un CVS ben noto nell'informatica
  • GIT il CVS più conosciuto in ambito informatico