Skip to content

Merkle Trees#

A merkle tree data structure is a binary tree of hashes: every leaf is a hash of a data block, every internal node is a hash of its two children, and the root hash commits to the entire dataset. Change one byte in any leaf and the root changes, which is why Git, Dynamo, Bitcoin, and IPFS all use them.

flowchart TB
  Root["root = H(H12, H34)"]
  H12["H12 = H(H1, H2)"]
  H34["H34 = H(H3, H4)"]
  H1["H1 = H(block A)"]
  H2["H2 = H(block B)"]
  H3["H3 = H(block C)"]
  H4["H4 = H(block D)"]
  A[block A] --> H1
  B[block B] --> H2
  C[block C] --> H3
  D[block D] --> H4
  H1 --> H12
  H2 --> H12
  H3 --> H34
  H4 --> H34
  H12 --> Root
  H34 --> Root

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    class A,B,C,D datastore;
    class H1,H2,H3,H4,H12,H34 service;
    class Root client;
Merkle (hash) tree with leaves hashing data blocks and internal nodes hashing their children
Source: Wikimedia Commons. CC BY-SA / public domain.

To prove block B belongs to the tree, you only need to ship H1, H34, and the root. That is O(log N) proof size for a tree of N leaves. Two replicas can compare their root hashes; if they differ, they recursively descend the tree to find exactly which blocks need repair, an idea that lives at the heart of Dynamo-style anti-entropy.

Problem statement (interviewer prompt)

Two replicas in a Dynamo-style key-value store may have diverged after a partition. Design a structure that lets them detect and repair only the keys that differ, with O(log N) proof and bandwidth. Then explain why Git, Bitcoin, and IPFS reuse the same shape.

A merkle tree (Ralph Merkle, 1979) is a complete binary tree where:

  • Each leaf stores H(block_i) for some cryptographic hash H (SHA-256, BLAKE3, etc.).
  • Each internal node stores H(left_child || right_child).
  • The single root hash is a fingerprint of the whole dataset.

Construction#

flowchart BT
  L1["H(D1)"]
  L2["H(D2)"]
  L3["H(D3)"]
  L4["H(D4)"]
  L5["H(D5)"]
  L6["H(D6)"]
  L7["H(D7)"]
  L8["H(D8)"]
  N12["H(L1||L2)"]
  N34["H(L3||L4)"]
  N56["H(L5||L6)"]
  N78["H(L7||L8)"]
  M14["H(N12||N34)"]
  M58["H(N56||N78)"]
  R["Root H(M14||M58)"]
  L1 --> N12
  L2 --> N12
  L3 --> N34
  L4 --> N34
  L5 --> N56
  L6 --> N56
  L7 --> N78
  L8 --> N78
  N12 --> M14
  N34 --> M14
  N56 --> M58
  N78 --> M58
  M14 --> R
  M58 --> R

    classDef leaf fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef inner fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef root fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    class L1,L2,L3,L4,L5,L6,L7,L8 leaf;
    class N12,N34,N56,N78,M14,M58 inner;
    class R root;

If the number of leaves is not a power of two, duplicate the last leaf (Bitcoin's choice) or use sparse merkle trees. Sparse merkle trees are easier to reason about, harder to make compact.

Inclusion proof (the killer feature)#

To prove D3 is in a tree with root R, send only the sibling path:

proof = [ H(D4), N12, M58 ]

verify:
  h = H(D3)
  h = H(h || H(D4))   # N34
  h = H(N12 || h)     # M14
  h = H(h || M58)     # Root
  assert h == R

Size: log2(N) hashes. For one billion leaves, that is 30 hashes (~1 KB with SHA-256).

import hashlib

def H(x): return hashlib.sha256(x).digest()

def merkle_root(blocks):
    layer = [H(b) for b in blocks]
    while len(layer) > 1:
        if len(layer) % 2 == 1:
            layer.append(layer[-1])  # duplicate last
        layer = [H(layer[i] + layer[i+1]) for i in range(0, len(layer), 2)]
    return layer[0]

def inclusion_proof(blocks, idx):
    layer = [H(b) for b in blocks]
    proof = []
    while len(layer) > 1:
        if len(layer) % 2 == 1:
            layer.append(layer[-1])
        sibling = idx ^ 1
        proof.append((layer[sibling], idx & 1))
        layer = [H(layer[i] + layer[i+1]) for i in range(0, len(layer), 2)]
        idx //= 2
    return proof

def verify(block, proof, root):
    h = H(block)
    for sibling, is_right in proof:
        h = H(sibling + h) if is_right else H(h + sibling)
    return h == root

Use case 1: Dynamo-style anti-entropy#

sequenceDiagram
  participant A as Replica A
  participant B as Replica B
  A->>B: my range root = R_A
  B->>A: my range root = R_B
  Note over A,B: R_A != R_B, divergence somewhere
  A->>B: my left subtree root = L_A
  B->>A: my left subtree root = L_B
  Note over A,B: left matches, descend right
  A->>B: my right.left root = ...
  Note over A,B: recurse until matching leaves
  B->>A: send keys that differ

Each replica builds a merkle tree over its key range. To repair, two nodes exchange root hashes, then recursively descend whichever subtrees differ. Bandwidth is proportional to the number of changed keys, not the size of the dataset.

This is exactly how DynamoDB, Cassandra, Riak, and ScyllaDB run repair / anti-entropy.

Use case 2: Git commit graph#

Every Git object is content-addressed by its SHA-1 (now SHA-256) hash:

  • A blob is H(file content).
  • A tree is H(list of (name, mode, blob_or_tree_hash)).
  • A commit is H(tree_hash, parent_hash(es), author, message).

Cloning a repo is a merkle-tree sync: the client says "I have commit X", the server sends the closure of objects reachable from HEAD that the client lacks. Branches are merkle-DAG pointers.

Use case 3: Bitcoin and blockchain#

A Bitcoin block header contains a merkle root of all transactions in the block.

+--------------+
| version      |
| prev_hash    |  <- chains to parent block (merkle DAG)
| merkle_root  |  <- root of tx tree
| timestamp    |
| difficulty   |
| nonce        |
+--------------+

Light clients (SPV) download only headers; to verify "my transaction is in the chain," the full node ships a 12-hash merkle proof against the header. That is SPV: secure mobile wallets without 600 GB of state.

Use case 4: BitTorrent v2 and IPFS#

BitTorrent v2 and IPFS chunk files into ~256 KB pieces, hash each, and build a merkle tree. The root is the content identifier (CID). Anyone can verify any piece against any peer's claim. Content-addressing means the same file from any host has the same CID, and tampering is detectable mid-download.

Use case 5: Tamper-evident audit logs#

Certificate Transparency logs, Trillian, Sigstore, and most "transparency log" implementations append entries and re-hash. Auditors get inclusion proofs ("entry X is at index 17,234, here are the 26 sibling hashes"). The root is signed and gossiped, so the log cannot rewrite history without detection.

Range proofs and verifiable maps#

  • Range proof: prove that everything between leaf i and leaf j is present, with O(log N) hashes for the boundary plus the leaves themselves.
  • Sparse merkle tree: leaves are indexed by 256-bit keys; empty leaves use a known constant hash. Used for blockchain state and verifiable key-value maps.
  • Verkle trees: use vector commitments to shrink proof size further; coming to Ethereum.

Pitfalls#

  • Second-preimage attack: if leaves and internal nodes use the same hash domain, an attacker can swap an internal hash for a leaf. Fix: prefix leaves with 0x00, internals with 0x01 (RFC 6962 / Certificate Transparency).
  • Duplicate-last-leaf attack (Bitcoin CVE-2012-2459): odd leaf duplication can allow two different trees to share a root. Fix: also commit to the count, or use unbalanced canonical trees.
  • Salt and length-prefix to avoid hash collisions on variable-length inputs.

Quick reference#

Definition#

Binary tree of hashes. Leaves = H(block). Internal node = H(left || right). Single root commits to entire dataset.

Properties#

  • One-bit change in any leaf changes the root
  • Inclusion proof size: O(log N) hashes
  • Verification: O(log N) hash operations
  • Append-only variants enable consistency proofs (CT, Trillian)

Inclusion proof#

  • Send sibling hashes along the path from leaf to root
  • Verifier rehashes upward, compares to known root

Use cases#

  • Dynamo anti-entropy: replicas swap roots, recursively descend diverging subtrees, repair only changed keys
  • Git: blobs, trees, commits all merkle-DAG nodes; clone is merkle sync
  • Bitcoin: block header stores tx merkle root; SPV proofs ~12 hashes
  • IPFS / BitTorrent v2: chunk file, merkle root = content ID
  • Certificate Transparency: append-only log, inclusion + consistency proofs
  • Sigstore / Trillian: tamper-evident audit logs

Variants#

  • Sparse merkle tree: 256-bit keyed leaves, empty constant; verifiable KV map
  • Verkle tree: vector commitments, shorter proofs; Ethereum roadmap
  • Append-only / consistency: prove old root is a prefix of new root

Hash functions#

  • SHA-256 (Bitcoin, CT, Git modern)
  • SHA-1 (Git legacy, deprecated)
  • BLAKE3 (modern, faster)

Pitfalls#

  • Second-preimage attack: domain-separate leaves vs internals (RFC 6962: 0x00 / 0x01 prefix)
  • Bitcoin duplicate-last-leaf CVE-2012-2459: commit to count or use canonical unbalanced shape
  • Variable-length inputs: length-prefix to avoid collisions

Complexity#

  • Build: O(N) hash ops, O(N) space
  • Inclusion proof: O(log N) size and verification
  • Range proof: O(log N + k) for k items
  • Update one leaf: O(log N) rehashes on the path

Refs#

  • Ralph Merkle 1979 thesis
  • RFC 6962 - Certificate Transparency
  • Amazon Dynamo paper (anti-entropy section)
  • Bitcoin paper (Section 7, SPV)

FAQ#

What is a Merkle tree?#

A Merkle tree is a binary tree of hashes where every leaf hashes a data block and every parent hashes its children. The root hash commits to the entire dataset.

Why are Merkle trees used in distributed systems?#

Two replicas can compare just their root hashes. If different, they recurse only into divergent subtrees, repairing exactly the differing blocks in O(log N) work.

What is a Merkle proof?#

A Merkle proof is the sibling hashes along the path from a leaf to the root. With it, a verifier with the root can confirm a single block belongs to the tree.

How does Git use Merkle trees?#

Git represents commits, trees, and blobs as content-addressed objects identified by their SHA-1 hash, forming a Merkle DAG where a commit hash fixes the entire history.

Where else are Merkle trees used?#

Dynamo and Cassandra use them for anti-entropy. Bitcoin and Ethereum use them in block headers. IPFS and certificate transparency logs use them for verifiable storage.

  • Consistent Hashing: the partition layer that decides which keys each merkle tree covers
  • Hinted Handoff: the live repair mechanism that complements merkle anti-entropy sweeps
  • CRDTs: when you need conflict-free convergence without a coordinator