Heads up: posts on this site are drafted by Claude and fact-checked by Codex. Both can still get things wrong — read with care and verify anything load-bearing before relying on it.
why → how

Why Merkle trees are everywhere

A hash tree that lets you prove one tiny piece of a giant dataset is correct without re-downloading the whole thing — the trick that quietly underpins Git, Bitcoin, IPFS, and certificate transparency.

Data intro Apr 29, 2026 · updated Aug 25, 2026 · 11 min read
On this page

The picture version

Five pictures for a reader who has never hashed anything. The prose below fills in the seams the pictures skip.

1 · The problem

Check that part of 90 GB is right, without reading 90 GB.

a 90 GB install, already on your disk only this sliver actually changed two impossible-sounding jobs, in 30 seconds: find it, then trust it Which pieces are stale? And are the new bytes the right ones? Both answered without re-reading the install — or trusting the server.
The launcher works out which slivers are out of date and satisfies itself the downloaded bytes are genuine, in seconds. That install is the running example: a big pile of data, split into chunks, where somebody needs to check just part of it.

2 · The build

Fingerprint each chunk, then keep fingerprinting the fingerprints.

one fingerprint per chunk of the install the root one value standing for the entire install
Every chunk gets a fingerprint, every neighbouring pair is combined into a parent fingerprint, and the process repeats until one value remains. That root is a summary of the whole dataset — and it is the only thing anyone needs to have agreed on in advance.

3 · Why the top value is worth anything

Change one chunk anywhere and the change climbs all the way up.

one byte edited here and the root is different So agreeing on one short value pins down every byte underneath it.
A single altered byte changes its chunk’s fingerprint, which changes its parent’s, all the way to the top. Two people who agree on the root are agreeing about the entire dataset, without having exchanged any of it.

4 · The payoff

To prove one chunk belongs, you send a handful of fingerprints — not the data.

the chunk you care about the three you actually send recompute up to here and compare Double the data and the proof grows by one fingerprint, not by double.
You ship the chunk plus the neighbour’s fingerprint at each level on the way up, and anyone can recompute the root and compare. The number of fingerprints grows with the depth of the tree rather than the amount of data, which is why the check stays cheap as the pile grows.

5 · Keep this card

The whole thing on one index card.

a Merkle tree = fingerprint every chunk + keep fingerprinting the fingerprints in pairs ∴ one value at the top stands for all of it Comparing two trees also tells you where they differ — matching branches can be skipped whole, which is how the launcher found the stale sliver so fast
Picture to keep: a knockout tournament bracket run backwards — each chunk is a competitor, every match combines two names into one, and the single name at the top summarises the whole draw. To prove your competitor was in it you don’t list every entrant; you name the opponent at each round on the way up, and anyone can replay those matches and check they reach the same champion.

Why it exists

You launch a game you haven’t played in months. The launcher announces a 400 MB update to a 90 GB install, downloads it in two minutes, then sits there for thirty seconds saying verifying. Two things just happened that sound impossible next to each other: it worked out which slivers of 90 GB were stale without re-reading 90 GB, and it convinced itself the bytes it just pulled off a stranger’s server were the right ones — again without re-reading 90 GB. That install is the running example for this post: a big pile of data, split into chunks, that somebody needs to check part of.

Strip the launcher away and there are two awkward questions underneath:

  1. Has any of it changed?
  2. Can I prove this one specific piece is part of it, to someone who doesn’t have the rest?

The dumb answer to (1) is “hash the whole thing.” That works, and it means re-reading 90 GB to notice that one chunk moved. The dumb answer to (2) is “send the whole thing and let them hash it.” Also correct, also a non-starter when “the whole thing” is the entire Bitcoin chain and “someone” is a phone.

Ralph Merkle’s 1979 thesis (Secrecy, Authentication, and Public Key Systems, Stanford) proposed a clean trick: hash the data in pieces, then hash the hashes pairwise up a tree until one hash remains — the root. The root summarises the whole dataset in one fixed-size fingerprint. To prove a specific leaf belongs under that root, you need only the O(log n) sibling hashes along the path from that leaf to the top — around a kilobyte even for a tree with billions of leaves.

That’s the entire idea. Everything else — Git’s content-addressed object graph, Bitcoin’s SPV proofs, IPFS content addressing, BitTorrent piece verification, certificate transparency, ZFS’s checksum hierarchy, Cassandra’s replica-comparison repair — is what happens when different fields rediscover that the answer to “trust this slice of a big thing” is shaped like a tree of hashes.

Why it matters now

Two present-day pressures keep pushing this primitive into more places.

Datasets keep growing faster than the network and memory used to check them. Verifying a multi-terabyte model checkpoint, a container image, or a monorepo by re-hashing all of it is wasteful when almost none of it moved. A Merkle tree turns “does this match?” into a patch-shaped check: change one leaf and only the log n nodes on its path need re-hashing, so comparing two versions means walking down from the roots and stopping wherever the hashes already agree.

And more systems need to be verifiable by someone who doesn’t trust whoever sent the data. A light wallet on a phone can’t store the whole chain. A browser can’t store every issued TLS cert, but wants assurance that certificates for a domain have been publicly logged. A peer pulling model weights out of a swarm can’t trust any single seeder. In every case the move is identical: get the root from somewhere you already trust — a signed block header, a signed log head, a manifest fetched over HTTPS — then check each piece against it with a tiny inclusion proof.

If you’ve ever wondered why so many unrelated systems converged on “and there’s a Merkle root in the header,” that’s why. It’s the cheapest way to make part of something checkable without shipping the whole.

The short answer

Merkle tree = binary tree + hash of children at every internal node

Picture to keep: a knockout tournament bracket run backwards. Each chunk of data is a competitor at the bottom; every match combines two names into one; the single name at the top summarises the whole draw. To prove your competitor was in the tournament, you don’t list every entrant — you name the opponent at each round on the way up, and anyone can replay those matches and check they reach the same champion.

You hash each chunk of data into a leaf hash. You hash each pair of sibling hashes into their parent. You repeat until one hash remains — the root, a fingerprint of the entire dataset; any change anywhere bubbles up and changes it. To prove a leaf is in the tree, you ship the leaf plus the sibling hash at each level on its path to the root — log₂ n hashes — and the verifier recomputes the root.

How it works

Build it from the failure, one constraint at a time. The 90 GB install is split into chunks L0..L7 (eight is small enough to draw; a real one has millions).

Naive attempt: hash the whole install into one digest. Compare digests with the server and you know instantly whether anything changed. Why it breaks: it’s a yes/no about 90 GB. It cannot tell you which chunk moved, so a one-byte difference means re-downloading everything — and computing it means re-reading everything.

Fix: hash each chunk separately and publish the list. Now you can compare chunk by chunk and download only the ones that differ. Why it breaks: the list is as long as the data is chunky — millions of hashes, tens of megabytes, and you have to fetch and trust all of it before you can check one chunk. A phone verifying one transaction in a blockchain is in exactly this bind.

Fix: hash the hashes, pairwise, until one is left. Now there is a single value at the top that commits to every chunk, and — this is the part that isn’t obvious — you can verify any one chunk against it without holding the others:

                        ROOT = H(H01_23, H45_67)
                       /                        \
              H01_23 = H(H01,H23)        H45_67 = H(H45,H67)
              /          \                /            \
       H01=H(h0,h1)  H23=H(h2,h3)   H45=H(h4,h5)   H67=H(h6,h7)
        /    \         /    \         /    \         /    \
       h0    h1       h2    h3       h4    h5       h6    h7
        |     |        |     |        |     |        |     |
       L0    L1       L2    L3       L4    L5       L6    L7

Each h_i = H(L_i) for some cryptographic hash H (SHA-256 in Bitcoin, in Certificate Transparency, and in Git’s newer object format; Git’s classic and still-dominant format uses SHA-1, which is broken for adversarial collisions but remains in use). The tree is balanced and binary in the textbook version; real systems get fancier (more on the seams below).

Inclusion proof for L5: to convince someone who only knows ROOT — say a peer who has your game’s manifest but none of its chunks — that L5 is the fifth chunk, you send:

  1. L5 itself.
  2. h4 (its sibling).
  3. H67 (the sibling of H45).
  4. H01_23 (the sibling of H45_67).

The verifier computes h5 = H(L5), then H45 = H(h4, h5), then H45_67 = H(H45, H67), then ROOT' = H(H01_23, H45_67), and checks ROOT' == ROOT. If H is collision-resistant, the only way to forge that match is to find a hash collision — i.e., the proof’s security reduces to the hash function’s.

For a tree with n leaves, the proof is ⌈log₂ n⌉ hashes. A billion leaves with SHA-256 is 30 hashes — about 960 bytes. Three lines of arithmetic, a kilobyte on the wire, and a phone can check one transaction against a chain it will never store. That’s what makes light clients viable.

Updates are also O(log n). Change one leaf and only the log n nodes on its path to the root need rehashing. That’s what makes incremental Git commits cheap, and what lets BitTorrent and IPFS verify individual chunks as they arrive in any order — including your game update, where the verifying step re-hashes the chunks that changed and walks the affected paths, not the 90 GB that didn’t move.

The seams — where the textbook picture is misleading:

You started with Merkle tree = binary tree + hash of children at every internal node. What did this post add? — + the sibling path. The tree alone gets you a fingerprint, which any plain hash of the whole file would also give you. It’s the fact that a leaf’s path to the root is only log n hashes wide that turns a fingerprint into a proof you can hand to a phone — and it’s why the launcher can verify a 400 MB patch against a 90 GB install without reading the install.

Going deeper