BitcoinDev 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.

Merkle Tree Structure

Merkle Tree Structure

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

The Merkle root is stored in the block header, providing a compact commitment to all transactions in the block.

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

The same double SHA-256 used in Merkle nodes can be tried in the Hash tool.

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

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