365 Architect

02 — Merkle Trees

The Basic Idea

A Merkle tree is a binary tree where:

  • Leaves are the hash values of individual items
  • Internal nodes are the hash of their two children's hashes combined
  • The root is a single hash that commits to ALL leaves
                    Root Hash
                   /         \
              Hash(A+B)     Hash(C+D)
              /       \     /       \
           Hash(A)  Hash(B) Hash(C)  Hash(D)
             |        |       |        |
             A        B       C        D

Key Properties

Property What it means Why it matters
Commitment The root is a fixed-size fingerprint of all data You can "promise" a set of data without revealing it
Verification To check if X is in the tree, you only need log₂(N) hashes Efficient membership proofs
Tamper detection Changing any leaf changes the root Any modification is detectable
Incremental Can add leaves and update the root efficiently Suitable for streaming data

Membership Proof

To prove that item C is in the tree, you only need:

  • Hash(C) itself
  • Hash(D) — the sibling of Hash(C)
  • Hash(A+B) — the sibling of Hash(C+D)

The verifier computes:

Hash(C) + Hash(D) → Hash(C+D)
Hash(C+D) + Hash(A+B) → Root Hash

Compare to the known root. Match? Then C was in the tree.

Only 2 hashes needed instead of 4 — for a tree of 1,000,000 items, only ~20 hashes needed.

Why Merkle Trees for Signatures?

The Problem with One-Time Signatures

A one-time signature (OTS) key can sign exactly one message securely. If you reuse it, an attacker can combine signatures to forge new ones.

Naive solution: Generate a million OTS keys, put all their public keys in a massive list, and sign the list with a master key.

Problem: The verifier needs the entire list (megabytes) to check a signature.

The Merkle Tree Solution

  1. Generate 2h2^h OTS key pairs (for tree height hh).
  2. Put all 2h2^h OTS public keys as leaves of a Merkle tree.
  3. The Merkle root is the long-term public key (tiny: 32 bytes).
  4. To sign: pick an unused OTS key, sign the message, and include:
    • The OTS signature
    • The Merkle path (log₂(2^h) = h hashes) proving the OTS public key is in the tree

Result: The verifier checks:

  • The OTS signature is valid
  • The OTS public key is in the tree (using the Merkle path)
  • The tree root matches the long-term public key

All with just hh hashes!

Example: XMSS (eXtended Merkle Signature Scheme)

XMSS uses a single Merkle tree of height hh:

  • Public key: Merkle root (32 bytes)
  • Private key: All OTS key pairs + index of next unused key
  • Signature: OTS signature + Merkle path (~h × 32 bytes)
  • Maximum signatures: 2h2^h
Tree height (h) Maximum signatures Signature overhead
10 1,024 ~320 B
16 65,536 ~512 B
20 1,048,576 ~640 B

Problem: XMSS is stateful — you must track which keys have been used. Lose the state, and you might reuse a key (catastrophic).

Scaling to Billions: The Hypertree

SLH-DSA solves the stateful problem and scales to virtually unlimited signatures using a hypertree — a tree of trees.

See the next article: 05 — The Hypertree.

Resources

  • Merkle, "A certified digital signature" (1989), CRYPTO — Original Merkle tree paper
  • Buchmann et al., "XMSS — A practical forward secure signature scheme based on minimal security assumptions" (2011), PQCrypto
  • Hülsing et al., "XMSS: Extended Hash-Based Signatures" (2018), RFC 8391
★★★★★
Share on LinkedIn