B++ Logo
Feedback

Merkle Trees

Merkle trees are a fundamental data structure in Bitcoin that enable efficient verification of transaction inclusion in blocks. They provide cryptographic proof that specific transactions are part of a block without downloading the entire block. The structure is named after Ralph Merkle, who invented it in 1979; Satoshi cited the concept in the Bitcoin whitepaper. A Merkle tree (also called a hash tree) is a binary tree where:

  • Leaves: Hash of individual transactions
  • Internal nodes: Hash of child nodes
  • Root: Single hash representing all transactions
Merkle Tree:

        Root Hash
       /        \
    HashAB     HashCD
    /    \      /    \
 HashA  HashB HashC  HashD
   |      |      |      |
  Tx1    Tx2    Tx3    Tx4

How It Works

Construction

  1. Hash each transaction: Create leaf nodes
  2. Pair and hash: Combine pairs, hash result
  3. Repeat: Continue until single root hash
  4. Store root: Root hash goes in block header

Verification

To prove transaction inclusion:

  1. Request Merkle path: Get hashes needed to reconstruct path
  2. Reconstruct path: Hash from transaction to root
  3. Compare roots: Match against block header root

Code Examples

Building a Merkle Tree

SPV (Simplified Payment Verification)

Merkle trees enable SPV clients:

SPV Client:
1. Downloads block headers only (~80 bytes each)
2. Requests Merkle proof for specific transaction
3. Verifies proof without full block
4. Confirms transaction inclusion

Merkle Proof

To prove Tx2 is in block:
├── Hash of Tx2 (leaf)
├── Hash of Tx1 (sibling)
├── Hash CD (parent sibling)
└── Root hash (from block header)

Verification:
1. Hash(Tx2) = leaf hash
2. Hash(Hash(Tx1) + Hash(Tx2)) = Hash AB
3. Hash(Hash AB + Hash CD) = Root
4. Root matches block header ✓

Block Header

Merkle root is stored in block header:

Block Header (80 bytes):
├── Version (4 bytes)
├── Previous Block Hash (32 bytes)
├── Merkle Root (32 bytes) ← Merkle tree root
├── Timestamp (4 bytes)
├── Difficulty Target (4 bytes)
└── Nonce (4 bytes)

Benefits

Efficiency

  • Compact proofs: Small Merkle paths vs. full blocks
  • Fast verification: Logarithmic complexity
  • Bandwidth savings: SPV clients need minimal data

Security

  • Cryptographic integrity: Any change breaks root hash
  • Tamper detection: Modified transactions invalidate root
  • Trustless verification: No need to trust third parties

Resources