Merkle Trees
A Merkle Tree (or Hash Tree) is a tree structure in which every leaf node is labeled with the cryptographic hash of a data block, and every non-leaf node is labeled with the cryptographic hash of the labels of its child nodes.
1. The Core Concept
Merkle Trees allow for efficient and secure verification of the contents of large data structures. They are fundamental to how blockchains and distributed systems ensure data integrity.
- Root Hash (Merkle Root): The single hash at the top of the tree. If this hash matches, the entire dataset is valid.
- Tamper Proof: If a single bit of data changes in a leaf, the hash changes. This change propagates up the tree, changing the parent hash, all the way to the Root Hash.
2. Structure
- Data Blocks: The actual data (e.g., transactions, file chunks) is at the bottom.
- Leaf Nodes: Hash of the data blocks. $H(Data_1)$.
- Intermediate Nodes: Hash of the concatenation of child hashes. $H(Hash{Left} + Hash{Right})$.
- Root Node: The final hash representing the whole tree.
3. Merkle Proofs (Verification)
The main benefit of a Merkle Tree is that you can prove a specific data block belongs to the tree without downloading the entire tree.
To verify data block $K$, you only need:
- The data block $K$ itself.
- The Root Hash.
- The "Merkle Path" (the sibling hashes needed to climb up the tree).
Complexity: $O(\log n)$. To verify one item in a list of $N$ items, you only need $\log_2 N$ hashes.
4. Use Cases
Blockchain (Bitcoin, Ethereum)
Blockchains use Merkle Trees to summarize all transactions in a block.
- Light Clients: A mobile wallet doesn't download the 500GB blockchain. It just downloads the headers (Root Hashes). If it needs to verify a transaction, it asks a full node for the Merkle Path.
Git
Git uses a variation of Merkle Trees to store the state of your project.
- If a file changes, its hash changes.
- The directory hash changes.
- The commit hash changes. This ensures the integrity of the entire history.
Distributed Databases (Cassandra, DynamoDB)
Used for Anti-Entropy (synchronization).
- Nodes compare Merkle Trees of their data.
- If Root Hashes match, data is in sync.
- If they differ, they traverse down to find exactly which buckets differ, minimizing the data sent over the network.
programming/hash-tables programming/distributed-systems programming/git-version-control