One hash that vouches for a million things

I have now written this structure four times in this blog without ever explaining it properly. It's the thing that makes a git commit name your entire working tree in twenty bytes. It's the merkle_root field in a Bitcoin block header, and the reason a phone can verify a payment against 700 GB it doesn't have. It's what the stateRoot in an Ethereum header is the root of. Each time I described the bit I needed and moved on.

So: the whole thing, once. A Merkle tree is one sentence applied recursively — a node's name is the hash of its children's names — and everything people find remarkable about it is a consequence rather than a feature. Tamper evidence is a consequence. Cheap updates are a consequence. Proofs the size of a logarithm are a consequence.

Two things make this worth a post rather than a paragraph. The first is that the consequences are genuinely surprising and you can feel them by dragging a slider. The second is less comfortable: the version almost everybody draws is broken. Not the hash function, which is fine — the structure. There is a forgery below that you can watch succeed against an honest root, and a one-byte fix that has been standardized since 2013 and is still missing from most explanations. Bitcoin has a different structural bug, which is now consensus and can never be removed.

Nothing here is a mockup. Every hash is a real SHA-256 computed in your browser, truncated to four bytes so a node fits on screen. The proof engine is property-tested against every leaf of every tree size up to 33, in all three of the shapes below, and both attacks are executed rather than described.

01 · The obvious thing, and why it isn't enough

You have a list of things and you want one short value that commits to all of them — so that later, anybody holding that value can tell whether the list changed.

The obvious answer is to concatenate everything and hash it. That works, and it has two problems that only show up at scale. Change one item and you rehash everything, because the hash function has no idea which part moved. And to convince somebody a single item is in there, you have to send them the entire list so they can redo the hash themselves. Both costs are linear in the size of the set, which is fine for ten items and absurd for a million.

The fix is to stop hashing one flat thing. Pair the items, hash each pair; pair those hashes, hash again; keep going until one hash is left. Call it the root. Edit a leaf and watch which nodes have to change:

Things worth watching for:

• Exactly one path lights up. Edit any leaf and the recomputation is the leaf, its parent, its grandparent, up to the root — log₂ n nodes. Every other subtree keeps its exact hash. That is precisely what lets git reuse an untouched directory's tree object byte for byte, and what lets an Ethereum block rewrite a few hundred trie nodes instead of a hundred million accounts.
• The root changes for any edit, and never predictably. Change one character of one leaf and the root is completely different, because the change has to climb through a hash at every level. There is no way to nudge a leaf and leave the root alone — that would be a hash collision.
• Drag the scale slider. At 2³⁰ leaves — a billion — an edit rehashes 31 nodes and a proof is 30 hashes. The structure is doing the same three lines of work at every size; only the depth moves, and depth grows like a logarithm.

02 · The payoff: proving one thing without sending everything

That last number is the one that matters, so let's spend a figure on it. Suppose I have the root and nothing else, and you want to convince me that a particular item is in your set. You don't send me the set. You send me the item, and the sibling hash at each level on its way up — one per level. I recompute the climb myself and check where I land.

Click any leaf, then break the proof:

Things worth watching for:

• The amber nodes travel; the dim ones never leave the prover's disk. For twelve leaves that's four hashes, 128 bytes. Drag the scale row: a million leaves costs twenty hashes, a billion costs thirty. The proof grows with the logarithm of the set, which is about as close to free as anything in computing gets.
• A proof is a computation, not a claim. There's no signature on it and nobody to trust. You re-run the fold; either it lands on the root you already had or it doesn't. Tamper with one sibling byte and the divergence starts immediately and never recovers, because every level above is downstream of the corruption.
• The verifier learns almost nothing else. It sees log n hashes and cannot recover a single other item from them. That's what makes this deployable between mutually suspicious parties: proving membership leaks the path, not the set.

This one mechanism is Bitcoin's SPV, Certificate Transparency's inclusion proof, and the "I have this chunk" message in every BitTorrent-shaped protocol. It's also, in a different costume, how Ethereum's eth_getProof hands you an account balance you can check against a block header.

03 · The odd node, and a bug that is now permanent

Now the first uncomfortable part, and it starts with a question that sounds like an implementation detail: what do you do when a level has an odd number of nodes? The last one has no partner. Something must happen to it.

Three real systems made three different choices, and only one of them is broken:

Things worth watching for:

• Bitcoin duplicates, and duplication collides. Hashing the lonely node with itself means the list [a, b, c] and the list [a, b, c, c] produce the same root — the figure computes both. A "commitment" that two different lists satisfy is not a commitment to the list.
• That collision is CVE-2012-2459, and it was a real denial of service. An attacker takes a valid block, duplicates trailing transactions to keep the root identical, and relays it. A node rejects the malformed copy — a repeated transaction is a double-spend — but caches the block hash as invalid, and then rejects the honest block when it arrives. Bitcoin Core still carries the workaround, because the rule itself is unfixable: every block since 2009 validates under it.
• The other two have nothing to fix. Haber and Stornetta's 1993 design carries the lonely node up untouched, so nothing is ever hashed twice. RFC 6962 refuses to pair level-by-level at all: it splits the list at the largest power of two below its length and recurses, which gives every leaf count exactly one tree shape. Switch strategies and watch the collision disappear.

The general lesson outlives Merkle trees: if two different inputs can produce the same output, you do not have a commitment, no matter how strong the hash is. The weakness was never in SHA-256.

04 · The forgery hiding in the standard diagram

Now the part that should bother you, because it applies to the tree you would build if you followed any of the diagrams in section 01 — including mine.

In the naive construction a leaf's hash is H(data) and an internal node's hash is H(left ‖ right). Look at those two for a second. They are both just "SHA-256 of some bytes." Nothing in either output records which kind of thing was hashed.

So take any internal node and concatenate its two children's hashes. That's 64 bytes. Present those 64 bytes as leaf data. Its leaf hash is H(those 64 bytes), which is exactly the internal node's hash — and now a completely honest proof, using real siblings and a real path, proves that a value which was never in your set is in your set.

Watch it succeed, then switch on the fix:

Things worth watching for:

• The forged proof is not forged. Every sibling in it is genuine, every hash on the path is real, and the root it reaches is the honest root. The attack doesn't break any hash; it exploits the fact that the tree cannot tell "this was committed as data" from "these two hashes happened to be adjacent."
• The fix is one byte. RFC 6962 hashes leaves as H(0x00 ‖ data) and internal nodes as H(0x01 ‖ left ‖ right). Now a leaf hash can never equal an internal hash — the impersonation stops type-checking. Toggle it and the same forgery is rejected.
• Bitcoin doesn't have this hole, for an accidental reason. Its leaves are always exactly 32-byte transaction ids, and an internal node is a hash of 64 bytes, so the sizes never line up in the required way. It's a structural accident rather than a defence, and it couldn't add a prefix now if it wanted to.

This is the standard second-preimage attack on unprefixed Merkle trees, and it's the reason "domain separation" is a phrase worth knowing: a hash is a commitment to bytes, and making it a commitment to a shape takes deliberate work.

05 · Proving something is not there

Everything so far proves presence. The opposite question turns out to be much harder, and a plain Merkle tree simply cannot answer it. Ask a Bitcoin node to prove a transaction is not in a block and there is no proof it can construct — the tree commits to what's in it and says nothing about what isn't.

Unless you sort first. Sort the leaves before building, and absence becomes provable: show the two committed neighbours the value would have to sit between, prove both are in the tree, and show they're adjacent. There is nowhere left for it to hide.

Things worth watching for:

• Two inclusion proofs and an adjacency claim. That's the entire construction. The bracketing values do the work: if carla and diego are next to each other in the committed order, nothing sorts between them.
• Sorting is not free. The order becomes part of the commitment, so inserting in the middle shifts positions and an append stops being an append. That's the trade, and it's why the append-only structures in the next section deliberately don't sort.
• This is why Ethereum's state is a trie, not a list. The Merkle Patricia Trie is keyed, so an absent account is a missing path rather than a bracketed gap — a different solution to the same problem, and the reason eth_getProof can prove an account has no balance.

06 · The other proof nobody mentions

There is a second kind of proof, it answers a genuinely different question, and it is the one holding up the certificate infrastructure of the web.

An inclusion proof says my thing is in the log. Notice what it doesn't say. A dishonest log can answer that truthfully for you while quietly deleting somebody else's entry, or while showing a different log to different people. Inclusion is a statement about one item; it is not a statement about the log's integrity.

A consistency proof is. It answers: is today's log the same log as yesterday's, only longer? You keep yesterday's root — 32 bytes — and the server hands you a handful of subtree hashes that fold into both roots. If the log rewrote or dropped anything, no such set of hashes exists.

Things worth watching for:

• The same nodes fold two ways. Once into the root you already trusted, once into the root you're being offered. Both have to land, using the same hashes — that's what makes "append-only" checkable by a client storing 32 bytes and no history.
• Rewrite or drop an entry and it fails immediately. Not "looks suspicious" — the arithmetic doesn't close, and the figure reports which of the two roots the fold missed.
• This is Certificate Transparency, and you rely on it constantly. Every certificate for every site you visit is published to public append-only logs; browsers require the proof. RFC 6962 specifies both proof types because you genuinely need both, and it's why a CT auditor keeps old roots instead of trusting the newest one.

It's worth naming what this buys, by contrast. Git has no consistency proof: a force-push rewrites history, and the only defence is that somebody notices their local copy disagrees. Bitcoin gets the same guarantee by making rewrites cost electricity. Certificate Transparency gets it for the price of a logarithm, because its log is a Merkle tree and mathematics is cheaper than mining.

07 · The same structure, four costumes

Once you can see it, the shape is everywhere, and the variations are all answers to "what are the leaves and how do you find one?"

system	leaves	shape	what the root commits to
git	files and directories	n-ary DAG, named by path	your entire working tree
Bitcoin	transaction ids	binary, unsorted, duplicating	one block's transactions
Ethereum	account rows	16-way radix trie, keyed	the whole world state
Certificate Transparency	certificates	binary, RFC 6962 split	every certificate ever logged

Git's is a Merkle DAG rather than a tree — identical subtrees are the same object, so the structure shares nodes and the "tree" quietly becomes a graph. That's not a variation on the idea, it's the idea taken seriously: if a node's name is the hash of its content, then two identical directories are the same directory, and deduplication happens whether you planned it or not. IPFS is the same observation applied to the internet.

Ethereum's is the most different: it crosses a Merkle tree with a radix trie so you can look leaves up by key rather than by position, which is what makes proving an account's balance possible at all.

08 · What's next

The compressed model: a Merkle tree is the recursive application of this node's name is the hash of its children's names. From that one rule you get tamper evidence (any change climbs to the root), cheap updates (only one path is rewritten, everything else is shared), inclusion proofs the size of a logarithm, and — if you sort, or key — proofs of absence. Add a second proof type and you also get append-only, checkable by a client that stores 32 bytes.

The honest edges, in one place. My hashes are SHA-256 truncated to four bytes so a node fits on screen; truncation weakens nothing being taught here but would be catastrophic in production, where you want the full 32 for collision resistance. My trees are in-memory, model no deletion, and the CT figure renders a shape that is really a recursion. The forgery in section 04 is the textbook second-preimage attack and it targets my own naive construction on purpose. And I have said "Bitcoin can never fix this" a few times; what I mean precisely is that the rule is consensus-critical — changing it would invalidate every block ever mined, which is a different kind of impossible from "hard."

Where this shows up, if you want to keep pulling:

• What happens inside .git?: the same cascade, with directories as the leaves and git cat-file as the debugger
• A blockchain is a git repo with a hard problem: the merkle_root field, and block 57055's three transactions demonstrating the odd-node wart on real data
• The blockchain is a log file: a real payment proved against a real header in four hashes
• Ethereum's entire state fits in 32 bytes: what happens when you give the tree a keyboard
• Bloom filters: the other structure this blog kept using without explaining — the one that answers "maybe"

Same promise as always: it's hashes all the way up, and you can recompute every one of them.