Merkle Tree

A Merkle tree (also called a binary hash tree) is a data structure used in blockchains to efficiently summarize and verify large datasets. Each leaf node contains a hash of a data block (a transaction), each non-leaf node contains a hash of its child nodes, and the root — the Merkle root — is a single hash representing all transactions in the entire block.

Bitcoin and Ethereum both use Merkle trees to organize transactions within each block. The Merkle root is stored in the block header, enabling Merkle proofs — mathematical proofs that a specific transaction is included in a block using only a small number of hashes (O(log n)) rather than requiring all transactions to be downloaded. This enables lightweight verification for SPV and light clients without downloading the entire blockchain.

Merkle Tree Structure

4 transactions in a block: Tx1, Tx2, Tx3, Tx4

Step 1: Hash each transaction (Bitcoin uses double SHA-256)
  H1 = SHA256(SHA256(Tx1)) = "abc..."
  H2 = SHA256(SHA256(Tx2)) = "def..."
  H3 = SHA256(SHA256(Tx3)) = "ghi..."
  H4 = SHA256(SHA256(Tx4)) = "jkl..."

Step 2: Hash pairs of child nodes
  H12 = SHA256(SHA256(H1 + H2)) = "mno..."
  H34 = SHA256(SHA256(H3 + H4)) = "pqr..."

Step 3: Hash to root
  Merkle Root = SHA256(SHA256(H12 + H34)) = "stu..."

Tree structure:
         Merkle Root (stu...)
        /                   \
  H12 (mno...)         H34 (pqr...)
  /        \            /        \
H1(abc)  H2(def)   H3(ghi)  H4(jkl)
  |          |         |         |
  Tx1       Tx2       Tx3       Tx4

Merkle Proof for Tx3 (prove Tx3 is in block):
  Provide:  H4, H12
  Verifier computes:
    H3    = hash(Tx3)              ← from the transaction itself
    H34   = hash(H3 + H4)         ← H4 provided
    Root  = hash(H12 + H34)       ← H12 provided
  If computed Root matches block header Root → Tx3 confirmed ✓
  Data required: 2 hashes (not all 4 transactions)

For a block with 4,096 transactions:
  Proof requires only 12 hashes — not 4,096
  For 1,000,000 transactions: ~20 hashes

Note on odd transaction counts: If a block contains an odd number of transactions, the last transaction hash is duplicated to form a pair — a known quirk of Bitcoin’s Merkle tree implementation.

Merkle Tree Applications

FAQ

Q: How do DeFi airdrops use Merkle trees?

Airdrops use Merkle trees to prove eligibility on-chain without storing all eligible addresses in the contract, which would be prohibitively expensive at scale. The protocol creates a Merkle tree of all eligible addresses and amounts, and the root is stored on-chain. Eligible users submit their address plus a Merkle proof — a small set of hashes. The contract verifies the proof against the stored root and, if valid, releases the claim. This enables gas-efficient verification of millions of eligible addresses with only a single 32-byte Merkle root stored on-chain.

Q: What is a Merkle Patricia Trie?

Ethereum uses a more complex variant called a Merkle Patricia Trie (MPT) — combining a Merkle tree (cryptographic hashing for integrity verification) with a Patricia trie (a prefix-compressed structure for efficient key-value lookup). Ethereum maintains three separate MPTs per block: the state trie (all account balances and contract storage), the transaction trie (all transactions in the block), and the receipt trie (transaction execution results and logs). This enables efficient state proofs — proving any account’s balance or any storage value at any historical block. Ethereum’s roadmap includes transitioning from MPTs to Verkle Trees, which produce even smaller proofs and enable stateless clients.

Q: How do Merkle proofs help light clients (SPV wallets)?

A light wallet — such as a mobile Bitcoin wallet — does not download the full blockchain, only block headers (80 bytes each). To verify a transaction is confirmed, it requests a Merkle proof from a full node: a small set of hashes proving the transaction is included in a specific block. For a Bitcoin block with thousands of transactions, this proof requires roughly 20 hashes instead of downloading all transactions. This allows transaction verification with kilobytes of data rather than gigabytes, enabling practical mobile crypto wallets.

Q: What happens if a Merkle tree has an odd number of leaves?

In Bitcoin’s implementation, if there is an odd number of transactions, the last transaction hash is duplicated so it can be paired and hashed. This is a known quirk of Bitcoin’s original Merkle tree design and has no security implications in practice, though it has been noted as inelegant by protocol researchers.

Q: How are Merkle trees different from Verkle trees?

Verkle trees are a proposed successor to Merkle Patricia Tries in Ethereum. They use vector commitments (based on elliptic curve cryptography) instead of hash-based commitments, producing dramatically smaller proofs. A Verkle proof for a large number of leaves can be a fraction of the size of an equivalent Merkle proof — a critical property for enabling stateless Ethereum clients that do not need to store the full state.

Related Terms

SHA-256 · Cryptographic Hash Function · Bitcoin · Ethereum · Light Client (SPV) · Airdrop · ZK Proof · Verkle Tree · Merkle Patricia Trie

UPay Tip: Merkle trees are why blockchain verification is efficient, not just theoretically complete. When you verify a transaction on Etherscan, you are effectively checking a Merkle proof. When you claim an airdrop by submitting an on-chain transaction, you are submitting a Merkle proof of your eligibility. When a mobile wallet confirms a Bitcoin payment without downloading the full chain, it is using SPV with Merkle proofs. Understanding Merkle trees helps you appreciate why blockchain verification is both cryptographically provable and practically efficient — you never need to download everything to verify anything.

Disclaimer: This content is for educational purposes only and does not constitute financial advice.