Merkle tree

In three days, from 13 to 16 October 2026, 64 of the 4224 files in this site’s code changed. How do you find them without comparing all the files one by one? Git stores each directory as a listing of its contents and gives it a name: the hash of that listing. If something inside the directory changed, its listing changed, and so did its name; if not, the name is the same. Below are two real snapshots of this site’s repository. Descend from the root: a directory with the same hash need not be opened.

Five root directories, five comparisons, and all five differ: in three days work went on everywhere. But already at the second level most things match, and behind each matching directory are hundreds of files that need not be looked at. In all, the descent compares 758 hashes of 4703 and finds all 64 files: 30 changed, 32 new and 2 deleted. This is how git diff between commits works, and why it is instant even in huge repositories.

The idea

Lay the data out in the leaves of a tree, and write in each leaf the hash of its data, and in each internal node the hash of its children’s hashes. The root is then a fingerprint of the whole set: a cryptographic hash cannot be steered so that two different sets give the same root. Two properties make the tree useful. Comparing roots tells whether the copies match entirely; descending only into differing subtrees finds the differences. And to prove that a particular leaf is in a set with a known root, the hashes of the neighbours on the path from the leaf to the root are enough, one per level.

An ordinary checksum of a file is a fingerprint too, but it answers only “yes or no”. The tree answers in more detail: where exactly things differ and how to prove that an element is in place without sending the rest. The price is storing the hashes of the nodes, about as many as there are leaves.

Why it cannot be forged

Hence the soundness of an inclusion proof: to present, for someone else’s leaf, a path that converges to the real root, one would have to find a collision on at least one level. For SHA-256 nobody has managed it. Git still uses SHA-1 by default, for which a collision was constructed in 2017, and since version 2.29 it can store a repository on SHA-256.

A proof of log n hashes

Take all 4222 files of the new snapshot and build a binary tree over them, as in RFC 6962, the standard for certificate transparency logs. To prove that a file is in the tree, the neighbours on the path to the root suffice: at each level, the hash of the subtree ours joins with. Choose any file. The bars above the list show which ranges of files these neighbours cover: together with the file itself they cover all 4222.

The proof has 13 hashes: ⌈log₂ 4222⌉. The verifier needs not a single file other than the one being checked, only these 13 numbers and the root, which it knows in advance. Switch on “forge the file”: one letter of the identifier changes, and at every level a different hash comes out, right up to the root. Note the top level: the neighbour on the right is files 4097–4222, only 126 of them. In RFC 6962 the left subtree always takes the largest power of two less than the number of leaves, here 4096, and the right one the rest, so the tree is incomplete, and checking a proof must take this into account. The second problem at the end of the article is about exactly this.

Why a leaf and a node need different prefixes

In RFC 6962 the hash of a leaf is SHA-256(0x00 ‖ data), and the hash of a node SHA-256(0x01 ‖ left ‖ right). Without prefixes the tree can be fooled. An internal node is the hash of 64 bytes, the two hashes of its children. If a leaf were hashed the same way, these 64 bytes could be presented as “leaf data”: the hash would be the same as the node’s, and a proof for a smaller tree, without the bottom level, would converge to the real root. The verifier would believe the set contains a “leaf” of two hashes that nobody put there. Different prefixes make the hashes of leaves and nodes incomparable.

A similar trouble happened in Bitcoin. There, on a level with an odd number of nodes the last node is duplicated, and because of this two different lists of transactions, with the last transaction repeated and without, give the same root. In 2012 this was described as the vulnerability CVE-2012-2459: a node that received a corrupted variant of a block considered the genuine block with the same root invalid too. Incomplete levels must be defined so that different sets of leaves cannot give the same tree; the RFC 6962 rule, unequal subtrees with no duplication, is built exactly that way.

Code

The program reads the same two snapshots of the site’s code. First the top-down comparison, as in git, counting comparisons. Then a binary tree per RFC 6962 over the files of the new snapshot, a proof for routes/web.php and its check, honest and with a forged file.

The check follows RFC 9162 almost word for word. It knows only the leaf number and the tree size, and from them decides at each level whether the neighbour is on the left or the right. The subtlest part is the last subtree of an incomplete level: it has no neighbour on the right and rises higher unchanged. The root 70268604… matches what the scene above shows: there the hashes were computed by your browser, here by Python and Go.

What it costs

Building is O(n) hashings: n leaves and n − 1 internal nodes. An inclusion proof is O(log n) hashes, and checking it as many hashings. Changing one leaf recomputes only its path to the root, O(log n). Comparing two copies with d differences compares O(d log n) pairs of hashes: each difference drags a path from the root behind it, and the shared upper parts of the paths are compared once. If everything differs, there are 2n − 1 comparisons, more than simply comparing the leaves, so the tree pays off when differences are few.

In git a node is not binary but a whole directory: comparing a directory of a hundred files costs a hundred comparisons. So the descent over our two snapshots cost 758 comparisons, while a binary tree over the same files costs 423; that is the first problem. But a path in git is shorter: directories here are seven levels deep, and a binary tree thirteen.

Where it works

Git. A file’s identifier is the hash of its contents, a directory’s the hash of the listing of its files and subdirectories, a commit’s the hash of the root directory, the parents and the message. One byte in the history cannot be replaced without changing all the identifiers above it, and so a commit identifier guarantees the whole content of the repository at that moment.

Certificate transparency logs. Certificate authorities record every certificate issued for HTTPS in public logs, Merkle trees per RFC 6962 (since 2021, RFC 9162). A browser can check that a certificate is in a log with a few dozen hashes, and monitors can check that the log is only appended to and loses nothing.

Blockchains. A Bitcoin block header holds the root of the tree of its transactions. A light client that does not store whole blocks needs only the headers and the path from its transaction to the root; this is how “simplified payment verification” is described in Satoshi Nakamoto’s 2008 paper.

Databases. In Amazon Dynamo (2007) and Apache Cassandra replicas reconcile data with Merkle trees over key ranges: first the roots, then only the differing subtrees. The less has diverged, the less has to be sent.

History

Ralph Merkle invented hash trees in 1979 to build digital signatures from nothing but a hash function. A one-time signature can be made from hashes, but each only for one message; the tree makes it possible to publish one root and sign thousands of messages, attaching the path to the root to each signature. He received a patent on this method in 1982. Merkle signatures long remained a curiosity, but now they are coming back: hash-based signatures resist quantum computers, and the SPHINCS+ standard, adopted by NIST in 2024 as SLH-DSA, is built on a Merkle tree.

Problems

In the first problem you have to count how many hash comparisons reconciling two replicas will take, and the tests include the same two snapshots of the site’s code. In the second, check an inclusion proof, including for trees of 10¹⁸ leaves, where going “by the bits of the index” goes wrong on the last subtrees.