# 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

1.  **Data Blocks:** The actual data (e.g., transactions, file chunks) is at the bottom.
2.  **Leaf Nodes:** Hash of the data blocks. $H(Data_1)$.
3.  **Intermediate Nodes:** Hash of the concatenation of child hashes. $H(Hash_{Left} + Hash_{Right})$.
4.  **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:
1.  The data block $K$ itself.
2.  The Root Hash.
3.  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]]