Back to Notes

Merkle Trees

The Problem It Solves

Two replicas are supposed to hold the same data (see [[Database Replication & Sharding]], [[Distributed Key-Value Store]]) but may have silently drifted apart — a missed write, a dropped hint, a bug. To fix this you need anti-entropy: periodically compare replicas and repair divergence. The naive way — transfer and compare every single key/value between two replicas — is O(n) data movement over the network, for datasets that might be terabytes, just to find a handful of actually-differing keys. A Merkle tree turns "find what's different" into an O(log n) comparison instead.

The Structure

A Merkle tree is a hash tree: leaves are hashes of data blocks; every internal node is the hash of its children's hashes; the root is a single hash summarizing the entire dataset.

flowchart TD
    Root["Root Hash<br/>H(H12 + H34)"]
    H12["H12<br/>H(H1 + H2)"]
    H34["H34<br/>H(H3 + H4)"]
    H1["H1 = hash(block A)"]
    H2["H2 = hash(block B)"]
    H3["H3 = hash(block C)"]
    H4["H4 = hash(block D)"]
    Root --> H12
    Root --> H34
    H12 --> H1
    H12 --> H2
    H34 --> H3
    H34 --> H4

If any byte in any leaf block changes, that leaf's hash changes, which changes its parent's hash, which changes the root — a single root-hash comparison between two replicas tells you instantly whether they're identical or different, without transferring any actual data.

Building One (Python)

import hashlib

def _hash(data: bytes) -> str:
    return hashlib.sha256(data).hexdigest()

class MerkleTree:
    def __init__(self, blocks: list[bytes]):
        self.leaves = [_hash(b) for b in blocks]
        self.levels = [self.leaves]
        self._build()

    def _build(self) -> None:
        level = self.leaves
        while len(level) > 1:
            if len(level) % 2 == 1:
                level = level + [level[-1]]          # duplicate last node if odd count
            next_level = [
                _hash((level[i] + level[i + 1]).encode())
                for i in range(0, len(level), 2)
            ]
            self.levels.append(next_level)
            level = next_level

    @property
    def root(self) -> str:
        return self.levels[-1][0]

Using It for Anti-Entropy Repair

The actual algorithm, once two replicas each hold a Merkle tree over the same key ranges:

def find_divergent_ranges(tree_a: MerkleTree, tree_b: MerkleTree) -> list[int]:
    """Returns leaf indices where the two trees disagree, without comparing raw data."""
    if tree_a.root == tree_b.root:
        return []   # identical — done in O(1), zero data transferred

    # Walk down level by level, only descending into subtrees whose hash differs.
    diverging_leaf_indices = []
    _compare_level(tree_a.levels, tree_b.levels, len(tree_a.levels) - 1, 0, diverging_leaf_indices)
    return diverging_leaf_indices

def _compare_level(levels_a, levels_b, level_idx, node_idx, out):
    if levels_a[level_idx][node_idx] == levels_b[level_idx][node_idx]:
        return   # this whole subtree matches — prune it, don't descend further
    if level_idx == 0:
        out.append(node_idx)   # reached a leaf that actually differs
        return
    _compare_level(levels_a, levels_b, level_idx - 1, node_idx * 2, out)
    _compare_level(levels_a, levels_b, level_idx - 1, node_idx * 2 + 1, out)

Why this is O(log n) instead of O(n): only subtrees whose hash actually differs get descended into — a matching subtree hash means every leaf beneath it is provably identical (a hash collision aside), so the entire branch is pruned from comparison in one step. In the worst case (every leaf differs) this degrades to O(n), but the realistic case for anti-entropy — a handful of keys drifted out of millions — is exactly the case where most subtrees match and get pruned immediately, leaving only a tiny number of leaf-level comparisons and only those specific differing keys need their actual data transferred/repaired.

Real-World Usage

  • Cassandra / DynamoDB-style stores: nodetool repair builds Merkle trees per replica over token ranges and compares them to find and stream only the divergent ranges — this is the concrete mechanism behind the anti-entropy step referenced in [[Consistent Hashing]] and [[Distributed Key-Value Store]].
  • Git: commit history is a Merkle DAG — each commit's hash depends on its tree's hash, which depends on file blob hashes; this is why changing any file transitively changes every commit hash after it, and why comparing two commits' hashes instantly tells you if the entire history matches.
  • Bitcoin/blockchain: each block's Merkle root summarizes all transactions in the block — a light client can verify one transaction is included using a small Merkle proof (the sibling hashes on the path to the root) without downloading every transaction.

Interview Drills

  1. Why can comparing just the two root hashes tell you whether two replicas are identical, without transferring any data? — Every leaf's hash is folded upward into its parent, and ultimately into the root — any single-byte difference anywhere in the dataset changes its leaf hash, which cascades up and changes the root hash. Two different root hashes prove the datasets differ somewhere; two matching root hashes prove they're identical (modulo the astronomically unlikely case of a hash collision).
  2. Two replicas have 10 million keys with exactly 3 keys out of sync. Why is a Merkle tree comparison so much cheaper than a full scan here? — At each level, only subtrees with a mismatched hash need to be descended into — a matching subtree hash proves every leaf beneath it is identical, so it's pruned from further comparison entirely. With only 3 divergent keys among 10 million, the vast majority of subtrees match at a high level and get pruned immediately — the algorithm ends up doing roughly O(log n) work to isolate the 3 actual differences, not O(n).
  3. What has to be true about how two replicas build their Merkle trees for a root-hash comparison to be meaningful at all? — Both trees must be built over the same partitioning of the data into leaves (the same key ranges/blocks in the same order) — comparing root hashes from trees built over different groupings would report "different" even for identical underlying data, since the hash computation itself depends on how the data was chunked into leaves.

Cross-links

[[Consistent Hashing]] · [[Distributed Key-Value Store]] · [[Database Replication & Sharding]]