Merkle trees, from git to Certificate Transparency

Ralph Merkle came up with the hash tree in 1979, the year I was born, and I used it more or less daily for a decade before I knew it had a name. Every git commit builds one. So does every Bitcoin block, and so does every certificate log that your browser trusts without telling you. It’s one of those ideas that’s small enough to explain on a napkin and still turns up in places that have nothing to do with each other, so I wanted to write it down properly, with pictures.

The whole idea

Take some data and cut it into pieces, say eight chunks of a file, or eight transactions, or eight certificates. Hash each piece. Now pair the hashes up and hash each pair together, so eight hashes become four. Pair those and hash again, four become two, and then one. That last hash is the root, and it’s a fingerprint of everything underneath it. Change one byte in one chunk, and that chunk’s hash changes, which changes its parent, which changes its parent, all the way up.

So far that’s not much better than hashing the whole thing in one go. A single SHA-256 of the file would also change if a byte changed. The tree is useful in two other ways.

The first is that you can prove a piece is in the set without handing over the set. If I have the root, and you want to convince me that chunk 3 is part of it, you send me chunk 3 plus the hashes of its siblings on the way up, and I recompute the path myself.

With eight leaves that’s three hashes. With a million it’s 20, and with a billion it’s 30, because the proof is one hash per level and a tree with n leaves is about log₂ n levels deep. At 32 bytes per SHA-256 hash, proving one item out of a billion costs you under a kilobyte. That’s the property everything below relies on.

The second is that two trees can find out where they differ without comparing everything. If two roots match, done, nothing to do. If they don’t, compare the two children of the root. Whichever side matches, you can ignore, and you go down the side that doesn’t. If only one leaf differs you find it in log n steps instead of comparing every leaf.

git

Git is the one most programmers touch, although git doesn’t call it a Merkle tree and it’s really a DAG, since a commit can have two parents. Every file’s contents is stored as a blob, named by its hash. A directory is a tree object, which is a list of names, modes and the hashes of the blobs and subtrees inside it, so its hash covers everything under it. A commit points at one root tree and at its parent commits, and the commit’s own hash covers all of that. You can walk it by hand:

$ git cat-file -p HEAD
tree 61c3b7e0…
parent 9fceb02d…
author …

$ git cat-file -p 61c3b7e0
100644 blob a3c1f2e9…    README.md
040000 tree 7d1e0b4a…    src

(Hashes shortened, obviously.)

That shared subtree is why git is fast at things that look like they should be slow. To diff two commits, git compares their root trees, and any entry whose hash is identical on both sides gets skipped without being opened. In a big monorepo where you changed two files, a diff touches a few dozen objects, not the hundred thousand in the checkout. The same thing makes storage cheap, since an unchanged directory is just a 20-byte pointer to an object that already exists.

It’s also why a commit hash is a promise about the entire history. If I tell you a commit ID and you check it out and it hashes right, you have exactly the tree I had and exactly the history behind it, down to the byte. That’s only as strong as the hash, which is why the SHA-1 collision made git people nervous, and why git 2.29 shipped experimental SHA-256 repositories in October. I haven’t tried one yet, and as far as I can tell none of the hosting services support them, so it’s an experiment for now.

Databases that repair themselves

Dynamo-style databases (Cassandra, Riak, and Amazon’s original Dynamo paper) keep several copies of each piece of data on different nodes, and those copies drift. A write goes to two of three replicas because the third was restarting, or a hint gets lost. Every so often you want to find the differences and fix them, which is called anti-entropy repair, and you’d rather not ship terabytes between nodes to do it.

So each replica builds a Merkle tree over its key range, the leaves being hashes of ranges of keys, and the two nodes exchange trees top-down. Matching subtrees get skipped. The ranges at the bottom that don’t match are the only data that gets streamed. Cassandra’s nodetool repair does exactly this, and if you’ve ever run it on a big cluster you’ll know the tree-building is still not free, it has to read everything to hash it, but the network part is small. (If you read Designing Data-Intensive Applications, this is in the replication chapter. It slots in next to consistent hashing, which decides which nodes own which keys in the first place.)

ZFS uses the same idea for a different reason. Every block pointer carries the checksum of the block it points to, so the checksums form a tree up to the uberblock, and a disk that silently returns the wrong data gets caught when the checksum one level up doesn’t match. The disk can’t vouch for itself, its parent vouches for it.

Bitcoin

I covered the block structure a few years ago. The Merkle root in the 80-byte header is a tree over every transaction in the block, and it’s what lets a phone wallet check that a payment made it into a block without downloading the block. It gets the headers, and asks a full node for the path from its transaction up to the root. Satoshi describes this in section 8 of the paper as simplified payment verification.

Bitcoin’s tree has one oddity worth knowing about: when a level has an odd number of hashes, it duplicates the last one to make a pair. That means two different lists of transactions can produce the same root (a list ending in X, and the same list with X repeated), which turned into a real denial-of-service bug, CVE-2012-2459, where a node could be tricked into marking a valid block as invalid. It was fixed, but it’s a good example of how the fiddly details of the tree matter as much as the hash.

Certificate Transparency

This is my favorite use, and the newest of the bunch to become mandatory.

The problem it solves goes like this. Any of the hundred-odd certificate authorities your browser trusts can issue a certificate for any domain, including yours, and for most of the history of the web you’d only find out if someone happened to notice it being used. When DigiNotar was compromised in 2011, the forged Google certificate was caught because Chrome had Google’s keys pinned and a user in Iran posted about the warning. Without that bit of luck, who knows how long it would have run.

Certificate Transparency, which came out of Google and is written up in RFC 6962 from 2013, says: fine, CAs can issue whatever they want, but every certificate has to be published in public, append-only logs, and browsers won’t accept a certificate that can’t show it was logged. Chrome has required that for every publicly trusted certificate issued since the end of April 2018, and Apple followed with its own policy. A log hands back a signed promise to include the certificate (the SCT) and that gets embedded in the certificate itself, or sent during the TLS handshake.

The log is a Merkle tree, with certificates as leaves, in the order they arrived. The tree only grows to the right. That gives you two kinds of proof.

An inclusion proof is the picture above. A browser, or anyone, can ask the log for the path from a certificate to the current root and check it, and it’s a few hundred bytes even for the biggest logs.

A consistency proof is the cleverer one. The log publishes a signed root every so often (a signed tree head). If last week the tree had 1,000,000 entries and root A, and today it has 1,050,000 entries and root B, the log can prove with a log-sized handful of hashes that the first million entries under B are exactly the same entries that were under A. In other words, nothing was edited or removed, only appended. If a log ever shows two different people two different histories, the signed tree heads plus a failed consistency proof are evidence of it, signed by the log’s own key. Auditors and monitors keep pulling these proofs, and a log that can’t produce one is in a lot of trouble.

CT does nothing to stop a bad certificate being issued. What it does is make it very hard to issue one quietly. Monitors (crt.sh is the one I use, and there are services that will email you) watch the logs for your domains and tell you when a new certificate appears.

The first time I set up one of those alerts at work, I got an email within a week about a certificate for one of our subdomains from a CA we’d never used. It wasn’t an attack. The agency that ran our marketing site had pointed a subdomain at their own hosting a year earlier and their host had got a certificate for it automatically. Perfectly legitimate, and completely absent from the certificate list we’d built when we rotated everything after Heartbleed. I’d been fairly proud of that list. CT knew more about our certificates than we did.

One detail people get wrong

If you write your own Merkle tree, and it’s a nice afternoon exercise, the leaf hash and the interior hash need to be different functions. RFC 6962 does it by prefixing a byte: a leaf is SHA-256(0x00 || data) and an interior node is SHA-256(0x01 || left || right).

Without that, an interior node’s input is just 64 bytes, two hashes glued together, and nothing stops someone from presenting those 64 bytes as if they were a leaf. Then a tree with four leaves and a tree with two “leaves” (which are really the two interior hashes) have the same root, and a proof about one can be passed off as a proof about the other. It’s the same family of problem as Bitcoin’s duplicated-leaf bug. The prefix byte costs nothing and makes the two kinds of node impossible to confuse, and I’d do it even in code that never leaves the building.*

* “It never leaves the building” is how a fair amount of the worst code I’ve maintained got started, so I’ve stopped believing it.