Cryptography Essentials

Merkle Trees

Merkle Trees

Module 3 of Cryptography

What Is a Merkle Tree?

A Merkle tree (or hash tree) is a data structure where:

  • Leaf nodes contain hashes of data items
  • Parent nodes contain hashes of their children
  • The root hash commits to ALL data below
                    Root Hash
                   /          \
            Hash AB            Hash CD
           /      \           /      \
       Hash A    Hash B   Hash C    Hash D
          |         |        |         |
        Tx A      Tx B     Tx C      Tx D

The Power: Merkle Proofs

To prove Transaction C is in the block, you don't need all transactions.

You need:

  1. Hash C
  2. Hash D (sibling)
  3. Hash AB (uncle)

For N transactions:

  • Without Merkle tree: Need all N transactions
  • With Merkle tree: Need only log₂(N) hashes

Key Takeaways

  1. Merkle trees commit to data with a single hash (the root)
  2. Proofs are logarithmic - verify one item without all data
  3. Bitcoin uses Merkle trees for transaction lists
  4. Ethereum uses Merkle Patricia Tries for key-value state