Alberi di Merkle: integrità delle transazioni su larga scala

Un blocco Bitcoin contiene circa 2000 transazioni. Per dimostrare che la transazione T è inclusa senza scaricare tutte le 2000 transazioni, serve una prova compatta. Gli alberi di Merkle risolvono il problema: la dimensione della prova è O(log n) hash invece di O(n) transazioni.

Foglie: SHA256d (doppio SHA-256) di ogni transazione. Nodo padre: SHA256d(left_child_hash || right_child_hash). Ripetere fino a ottenere un'unica radice hash. Se il numero di nodi è dispari, duplicare l'ultimo nodo. La radice è la radice di Merkle memorizzata nell'intestazione del blocco (32 byte).

import hashlib def sha256d(x): return hashlib.sha256(hashlib.sha256(x).digest()).digest() def merkle_root(txids): if len(txids)%2: txids.append(txids[-1]) while len(txids)>1: txids=[sha256d(txids[i]+txids[i+1]) for i in range(0,len(txids),2)] return txids[0].hex()

Per dimostrare che la transazione T si trova nella posizione i, fornite gli hash dei nodi fratelli a ogni livello, dalla foglia di T fino alla radice (O(log n) hash). Il verificatore ricalcola la radice partendo da T e dal percorso dei fratelli. Se la radice calcolata corrisponde alla radice di Merkle nell'intestazione del blocco, la presenza di T è dimostrata.

1024 transazioni → la prova di Merkle consiste di 10 hash = 320 byte. Blocco completo = ~1 MB. I client SPV scaricano soltanto l'intestazione da 80 byte + la prova di Merkle da 320 byte per ogni transazione di interesse: risparmio di banda del 99,97% rispetto al download dell'intero blocco.

Se una transazione qualsiasi nell'albero cambia, cambia anche l'hash della relativa foglia e la modifica si propaga fino alla radice di Merkle. La radice alterata non corrisponde più a quella nell'intestazione del blocco, che è protetta dalla PoW. Qualsiasi modifica è rilevabile calcolando la radice a partire dalle transazioni.

Ethereum estende gli alberi di Merkle con le trie (Patricia Merkle Trie): una trie radix codificata con prefisso esadecimale, in cui ogni nodo è sottoposto a hashing tramite Merkle. Viene usata per: trie dello stato (saldi degli account), trie delle transazioni e trie delle ricevute. Consente di dimostrare in modo efficiente lo stato di un account senza disporre dei dati del nodo completo.

Una Merkle Mountain Range (MMR) è una struttura di Merkle append-only per dati simili a log. I nuovi elementi vengono aggiunti in coda; vengono mantenuti i picchi (radici di sottoalberi di dimensione potenza di 2). È utilizzata in Grin/MimbleWimble e ZCash per ottenere prove compatte ed efficienti su un log append-only.

Gli alberi Verkle sostituiscono gli alberi di Merkle nella roadmap di Ethereum (EIP-6800): usano impegni vettoriali (impegni polinomiali KZG) invece degli hash. La dimensione della prova è O(1) invece di O(log n) come negli alberi di Merkle. Ciò consente ai client stateless di verificare lo stato senza memorizzare l'intera trie.

Certificate Transparency (RFC 6962) usa un log di Merkle append-only: ogni certificato emesso da una CA è una foglia. Le prove di inclusione verificano che un certificato sia stato registrato. Le prove di consistenza verificano che il log sia rimasto append-only (senza eliminazioni o inserimenti). I produttori di browser verificano gli SCT tramite questo log.

Gli alberi Git (istantanee delle directory) sono alberi di Merkle: ogni nodo dell'albero calcola l'hash dei propri blob di file e dei propri sottoalberi. L'hash di un commit identifica in modo univoco lo stato dell'intera codebase. Questo spiega perché git checkout restituisce sempre esattamente gli stessi file.

Quanti hash sono necessari in una prova di Merkle per dimostrare l'inclusione in un albero con 1024 foglie?

Gli alberi di Merkle consentono prove di inclusione di dimensione O(log n). Bitcoin memorizza la radice di Merkle nelle intestazioni dei blocchi; i client SPV usano queste prove. Ethereum estende il concetto alle Patricia Merkle Trie. Gli alberi Verkle sostituiranno gli alberi di Merkle per ottenere prove O(1). Prossimo argomento: mining con Proof of Work e difficoltà.