Engineering Atlas › System Design Fundamentals

Comparing data quickly with Merkle trees

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

Building the tree

Split the data into ordered blocks: file chunks, key ranges, log entries, or transactions. Each leaf is H(block). Each internal node is H(left || right), the hash of its two children's hashes concatenated. Repeat until one hash remains. With a cryptographic hash such as SHA-256, nobody can find a different set of blocks with the same root.

Two details matter in practice. First, domain separation: certificate transparency hashes leaves as H(0x00 || data) and internal nodes as H(0x01 || left || right), so a crafted leaf can never be confused with an internal node. RFC 6962 defined this in 2013; RFC 9162 (CT version 2.0, 2021) formally obsoletes it but keeps the same tree hash (RFC 9162). Second, odd counts: when a level has an odd number of nodes, some designs duplicate the last one. Bitcoin does this, and it let two different transaction lists produce the same root, a flaw tracked as CVE-2012-2459 (Bitcoin wiki). The CT RFCs instead split n items at the largest power of two smaller than n, giving an unbalanced but unambiguous tree.

Inclusion proofs

To prove block i is in a tree with root R, send the sibling hash at every level on the path from leaf i to the root. The verifier hashes the block, combines it with each sibling in the right order, and checks the result equals R. For a million leaves that is 20 hashes, 640 bytes with SHA-256. The verifier needs only to trust the root, which is small enough to sign, publish, or pin.

Certificate transparency also uses consistency proofs, showing that a later root extends an earlier one without rewriting history. Clients keep old tree heads, so they can check that no old record was altered or reordered without re-reading the log (transparency.dev).

Comparing replicas (anti-entropy)

Two replicas each build a tree whose leaves hash the rows in fixed sub-ranges of the key space. They exchange roots; if they match, the replicas are identical. Otherwise they recurse only into mismatching children and stream just the differing leaf ranges. Network cost is proportional to the differences times the tree depth, not to data size.

Dynamo introduced this for background repair, keeping one tree per key range on each node, and Cassandra and Riak use it too. The cost moves to building the tree, which reads and hashes every row. Dynamo's paper names the other cost: when a node joins or leaves, many key ranges change and their trees must be rebuilt (DeCandia et al., section 4.7).

Content addressing

Git, IPFS, and container images generalise the tree to a DAG: objects are named by the hash of their contents, so identical content is stored once and a commit hash pins a whole file tree.

Down the stack

Layer 1The contract

With a collision-resistant hash, two equal roots mean equal data, and any change anywhere changes the root. An inclusion proof convinces anyone holding a trusted root that an item is at a given position, using log2(n) hashes. A tree comparison finds every differing leaf range while transferring a number of hashes proportional to the differences times the depth. None of this says anything about which replica is correct; the repair policy decides that.

Layer 2The mechanism

In Cassandra, nodetool repair starts a session per token range. The coordinator asks each replica to build a Merkle tree over its data for the range, hashing rows into leaves, and compares the returned trees pairwise. Replicas then stream the mismatching ranges to each other. Plain nodetool repair is incremental by default and covers only data written since the last incremental repair; --full covers everything (Cassandra repair docs). Tree size is bounded by memory, not a fixed depth: repair_session_space defaults to 1/16 of the heap (cassandra.yaml). Repair used to need an external scheduler; Cassandra 6.0 adds a built-in one, backported to 5.0.8 and off by default (Auto Repair).

Git's tree object is a concrete Merkle node: a header tree <size>\0, then entries of <mode> <name>\0 followed by the 20-byte binary SHA-1 of the child (or 32 bytes in SHA-256 repositories), stored zlib-compressed under .git/objects/. Git plans to make SHA-256 the default for new repositories in Git 3.0, which has no release date, citing practical SHA-1 attacks (Git BreakingChanges). Certificate Transparency logs publish a Signed Tree Head containing the tree size, a timestamp, the SHA-256 root, and a signature, and serve get-proof-by-hash and get-sth-consistency endpoints for inclusion and consistency proofs. Newer logs use the Static CT API instead: the same hashes, but published as cacheable "tiles" of 256 hashes from which clients compute proofs themselves (C2SP). Chrome and Safari now accept these logs, still alongside at least one classic RFC 6962 log (Let's Encrypt).

Layer 3The machine

Hashing is fast relative to disks. SHA-256 runs at roughly 400 to 500 MB/s per core in software and 1.5 to 2 GB/s with the SHA extensions on modern x86 and ARM cores, so building a tree over 2 TB is bound by how fast you are willing to read the disk, not by hashing. That read competes with live traffic for IOPS and page cache, which is why repairs are throttled.

Memory and network are small by comparison. A tree with 2^20 leaves of 32 bytes is 32 MB per range, and only mismatching paths are exchanged. Verifying a 20-step proof is 20 hashes of 65-byte inputs, a few microseconds. Streaming is the expensive part: Cassandra 4.0 added zero-copy streaming that sends whole SSTable files with kernel-level copies instead of re-serialising rows, cutting CPU per streamed byte.

Why it's built this way

  1. Comparing data directly means moving it, so replicas compare hashes instead.
  2. One hash over everything only says "different", so hashes are arranged in a tree to localise the difference in log n steps.
  3. Building leaves requires reading every byte, so trees are built in scheduled, throttled validation passes.
  4. Leaf size trades memory against overstreaming, so systems tune depth and repair sub-ranges more often instead of building ever-larger trees.

Diagram

flowchart TD
    R["Root = H(H12 + H34)"] --> A["H12 = H(H1 + H2)"]
    R --> B["H34 = H(H3 + H4)"]
    A --> L1["H1 = H(block 1)"]
    A --> L2["H2 = H(block 2)"]
    B --> L3["H3 = H(block 3)"]
    B --> L4["H4 = H(block 4)"]
    P["Proof for block 3: H4, H12"] --> B

Worked example

A Cassandra-style cluster stores 2 TB per replica, about 4 billion rows of roughly 500 bytes. A weekly repair must bring three replicas back in sync after hinted handoff and read repair have missed some writes.

Each replica builds a Merkle tree per token range with depth 15: 32,768 leaves. Each leaf covers about 122,000 rows. Building requires reading all 2 TB; at a sustained 200 MB/s of spare disk bandwidth that is close to 3 hours per replica, which is why repair is scheduled and throttled. The finished tree is 32,768 leaves times 32 bytes, about 1 MB, plus internal nodes, so exchanging trees costs a few MB.

Suppose 1,000 rows differ, scattered randomly. Up to 1,000 leaves mismatch. Each mismatching leaf means the whole 122,000-row range is streamed, about 61 MB, so 1,000 leaves stream roughly 61 GB to fix 500 KB of real differences. This is overstreaming, a known operational pain of coarse trees.

The fixes all reduce the range per leaf: deeper trees (depth 20 gives about 4,000 rows per leaf, so about 2 GB streamed, but 32 times the tree memory), repairing smaller sub-ranges one at a time, or incremental repair that only covers data written since the last repair. Running repair more often also helps, because fewer differences accumulate between runs.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Merkle tree comparisonBandwidth proportional to differences, works between untrusted partiesBuilding requires reading all data; coarse leaves overstreamLarge replicas that are mostly in sync
Full data transfer or checksum per rowSimple, exactTransfers or compares everythingSmall datasets, or a fresh replica
Change log / CDC replayShips only changes, cheapNeeds a durable, complete log; gaps are invisibleYou already have a reliable replication log
Inclusion proofs with signed rootClients verify items without trusting the serverRoot must be distributed and trusted out of bandTransparency logs, verifiable downloads

Pitfalls in production

Leadership lens

Check yourself

  1. Why does comparing two replicas with Merkle trees cost bandwidth proportional to the differences rather than the data size?

    Show answer

    Matching subtrees are pruned as soon as their hashes agree, so only paths leading to differing leaves are explored, each costing a handful of hashes per level.

  2. Why does RFC 6962 hash leaves and internal nodes with different prefixes?

    Show answer

    Without separation, an attacker could present an internal node's two child hashes as if they were a leaf's data, producing a different dataset with the same root.

  3. A proof for one item in a tree of a billion leaves has how many hashes, and why so few?

    Show answer

    About 30, because each level halves the remaining leaves and the proof needs only one sibling per level.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →