Albero di Merkle

Accoppia gli hash delle transazioni, calcola l'hash di ogni coppia e ripeti finché resta un solo hash. Quel valore unico finisce nell'intestazione del blocco, e dimostrare che una transazione appartiene a esso richiede solo gli hash lungo un percorso: undici, 352 byte, per un blocco che contiene 2.000 pagamenti. È per questo che un wallet su smartphone può verificare che i tuoi bitcoin sono arrivati senza scaricare il blocco.

Come funziona

Un albero di Merkle trasforma una lista in una piramide calcolando l'hash degli elementi vicini a coppie, livello per livello, finché resta un solo hash.

Le foglie sono gli ID delle transazioni nell'ordine in cui il miner le ha inserite. Bitcoin combina ogni coppia concatenando i due valori di 32 byte ed eseguendo SHA-256 sul risultato due volte. Quando un livello contiene un numero dispari di voci, l'ultima viene accoppiata con una copia di se stessa, il che mantiene semplice l'algoritmo e una volta ha causato problemi reali: la vulnerabilità catalogata come CVE-2012-2459, divulgata a maggio 2012 e corretta lo stesso mese, sfruttava quella duplicazione per costruire un blocco che ai nodi risultava non valido anche se le transazioni sottostanti erano corrette.

Il vantaggio è logaritmico. Raddoppiare il numero di transazioni aggiunge un livello, non un hash per transazione. Un blocco con 1.024 pagamenti richiede dieci hash per dimostrare l'appartenenza, 320 byte. Quattromilanovantasei ne richiedono dodici, 384 byte. Chi verifica la prova ricalcola il percorso verso l'alto e confronta il risultato con la radice di cui si fida già dall'intestazione, e non c'è modo di falsificare un percorso senza rompere SHA-256.

Nulla di tutto questo nasce con bitcoin. Ralph Merkle descrisse la costruzione nella domanda di brevetto che divenne il brevetto US 4.309.569, depositata nel 1979 e concessa a gennaio 1982. Il whitepaper cita il suo lavoro e assegna all'albero due usi: eliminare le transazioni spese dai blocchi vecchi per risparmiare spazio su disco, nella sezione 7, e consentire a un client di verificare un pagamento conservando solo le intestazioni, nella sezione 8.

Dove lo vedi

Gli alberi di Merkle compaiono ovunque un sistema debba dimostrare che un elemento appartiene a un insieme grande senza inviare l'insieme.

Dentro bitcoin, ogni intestazione di blocco porta la cima di uno di questi alberi. Un nodo ricostruisce l'albero dalle transazioni ricevute e rifiuta il blocco se il risultato non coincide. Bitcoin Core espone il meccanismo direttamente: gettxoutproof produce una prova serializzata che una transazione è stata inclusa in un blocco, e verifytxoutproof ne verifica una, il che è un modo pratico per fornire a qualcuno la prova di un pagamento senza dargli un wallet.

Altrove in bitcoin, Taproot ne costruisce un secondo: le condizioni di spesa alternative di un output Taproot sono disposte ad albero, così rivelare il ramo usato non svela nulla dei rami non usati. Fuori da bitcoin, la stessa forma è alla base della cronologia dei commit di Git, dei registri di Certificate Transparency che individuano certificati web emessi in modo improprio e dei controlli di integrità dei dati del filesystem ZFS.

Per chi usa un wallet la conseguenza visibile è piccola e utile. Un client leggero che conserva qualche decina di megabyte di intestazioni può confermare che la tua transazione è in un blocco specifico, a una profondità specifica, e ottiene una risposta falsa solo se qualcuno ha prodotto proof of work valido su una catena falsa, il che costa denaro reale.

Albero di Merkle vs radice di Merkle

L'albero di Merkle è la struttura di lavoro; la radice di Merkle è l'unico valore che resta dopo. Un nodo costruisce l'intera piramide in memoria mentre valida un blocco e poi la scarta, conservando solo i 32 byte finiti in cima, perché tutto ciò che sta sotto può essere rigenerato dalle transazioni. Quando un explorer ti mostra un campo chiamato radice di Merkle, quello è il superstite. Nessuno conserva l'albero, e nessuno deve farlo.