A Merkle tree is a data structure that efficiently summarizes and verifies large sets of data by recursively hashing pairs of items until a single root hash remains. In blockchains, it lets anyone prove a specific transaction is included in a block without downloading the entire block.
What Is a Merkle Tree?
2 min read
The short version
Imagine a sports tournament bracket, but instead of teams playing games, data items get hashed together in pairs. Each round produces half as many hashes until you're left with one champion hash at the top, the Merkle root. If any player (data item) was swapped, the entire bracket results would change.
How It Works
Construction: hash each transaction individually (leaves), then pair adjacent hashes and hash them together (branch nodes), repeat until one hash remains (the root). The Merkle root is stored in the block header. Verification: to prove transaction #7 is in a block of 1,000 transactions, you only need ~10 hashes (the "Merkle proof" or "authentication path") rather than all 1,000 transactions. The verifier hashes up the path and checks if it produces the known root. This is O(log n) efficiency, critical for light clients that can't download full blocks.
A Merkle proof for a light client
A block has 4,096 transactions. A light client wants to verify transaction #2,048 is included. The full node provides 12 hashes (log2(4096) = 12): the sibling hash at each level of the tree. The light client hashes transaction #2,048, combines it with its sibling hash, hashes the result, combines with the next level's sibling, and repeats 12 times. If the final result matches the Merkle root in the block header (which the light client already has), the transaction is provably included. Total data transferred: 12 × 32 bytes = 384 bytes, instead of the full block (~1.5 MB).
What People Get Wrong
Merkle trees are unique to blockchain
Merkle trees were invented in 1979 by Ralph Merkle and are used in Git, certificate transparency logs, file verification systems, and many non-blockchain applications.
You need the full tree to verify anything
The entire point is you don't. A Merkle proof (a path from leaf to root) is logarithmically small relative to the total data set.
The Merkle root changes if transaction order changes
Correct, and this is by design. It commits to both the content AND ordering of transactions in the block.
Keep Reading
Sources & Further Reading
- Bitcoin Developer Docs: Merkle Trees
Technical reference on how Bitcoin uses Merkle trees in block headers
- Ethereum Patricia Merkle Trie
How Ethereum extends Merkle trees for state proofs
Questions People Also Ask
- Where is the Merkle root stored?
- In the block header, a compact 80-byte structure (on Bitcoin) that includes the previous block hash, timestamp, difficulty, nonce, and the Merkle root summarizing all transactions in the block body.
- What happens if a transaction is modified?
- The leaf hash changes, which cascades up through every parent node to the root. The resulting root won't match the one in the block header, instantly revealing tampering.
- Do Ethereum and Bitcoin use the same Merkle tree?
- Bitcoin uses a simple binary Merkle tree for transactions. Ethereum uses a more complex structure (Merkle Patricia Trie) that also enables state proofs, proving account balances, not just transaction inclusion.