Merkle Proof
A million records, 1,048,576 of them because a power of two makes the arithmetic below easy to follow, hash into a single number. Nothing requires it: the panel further down carries an odd node up a level rather than padding, which is what a real tree does. To prove that one particular record is among them you are handed the record, that number, and about twenty hashes. You are never handed the other 1,048,575, and you never need them. Double the records and the proof grows by one hash, which is the whole reason this is worth having.
New to hashes as names? Start here
A hash turns any amount of data into a short fixed-size value, in a way that is cheap forwards and hopeless backwards, and where changing anything at all changes the result completely. Treat that value as the data's name.
Names of names is where this page starts. Hash two pieces of data, then hash the pair of hashes, and keep going until one value stands for everything underneath. Change one byte anywhere and every name above it changes, so that final value is a claim about the whole set. Checking that one thing belongs then costs a handful of hashes rather than the whole set.
Hard, not impossible
Nothing in this topic is unbreakable, and that is a claim about these machines rather than about cryptography. Each of them rests on an operation that is cheap in one direction and expensive in the other, and expensive means a number of steps so large that doing them costs more than the secret is worth. The one-time pad is the standing exception: it is not hard to break, it is impossible, and it is impractical for almost everything, which is why the rest of this topic buys difficulty instead.
That makes every claim here a claim with a date on it. Secure means secure for this long, against someone with this much to spend, assuming nobody finds a shortcut. The machines in this topic each rest on one of those one-way operations, and each is worth asking the same question about: what exactly would an attacker have to do, and how much of it.
The machine for this idea on its own is Diffie-Hellman, if you would rather press it than read about it.
Leaves, a root, a path of siblings, and a check that never sees the rest
1 The leaves, each one hashed
Every record is hashed once. Nothing is stored twice and nothing is sorted; this is the bottom row of the tree and it is simply the records, hashed.
| # | record | hash |
|---|---|---|
| 0 | record 0 | 37fa3178 |
| 1 | record 1 | 38fa330c |
| 2 | record 2 | 39fa34a0 |
| 3 | record 3 | 3afa3630 |
| 4 | record 4 | 3bfa37c4 |
| 5 | record 5 | 3cfa3958 |
| 6 | record 6 | 3dfa3ae8 |
| 7 | record 7 | 3efa3c7c |
2 Pairs hashed upward until one root is left
Adjacent hashes are hashed together, then those, and so on. Each level is half the size of the one below it, so a million leaves are twenty levels and the top is one number.
| level | hashes | first |
|---|---|---|
| 0 | 8 | 37fa3178 |
| 1 | 4 | b746b084 |
| 2 | 2 | 62ed25d4 |
| 3 | 1 | 40086870 |
- the root
- 40086870
- levels
- 4
3 A proof: one leaf, and the siblings along its path
To prove one leaf, you need the sibling at each level going up. That is the proof: one hash per level, and nothing else from the tree.
| level | side | hash |
|---|---|---|
| 0 | left | 3bfa37c4 |
| 1 | right | bf22e6ec |
| 2 | left | 62ed25d4 |
- hashes in the proof
- 3 hashes
- hashes in the whole tree
- 15
4 Checking it, having never seen the other leaves
The verifier hashes the record, combines it with each sibling in turn, and compares what comes out with the published root. It has seen exactly one leaf.
| step | what | running value |
|---|---|---|
| 1 | the leaf, hashed | 3cfa3958 |
| 2 | with the left sibling | 854d3f30 |
| 3 | with the right sibling | c12c68b0 |
| 4 | with the left sibling | 40086870 |
- does it match the root
- yes, it is the published root
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| every one of the 8 leaves proves itself against the same root | yes | each recomputed the published root from its own siblings alone |
| a changed record does not reach the root, so the proof refuses | yes | the walk ends at c29ea740 and the root is 40086870 |
| a real record with another record's proof is refused as well | yes | the siblings on the path are what bind the leaf to its position |
| doubling the records adds exactly one hash to the proof: 3, 4, 5, 6, 7 for 8, 16, 32, 64, 128 | yes | logarithmic, which is why a million records need about twenty |
| the proof carries 3 sibling hashes and not one other record | yes | a verifier is handed hashes; the other records never leave the prover |
Proving one record out of 8 took 3 hashes and the record itself. The verifier never saw the other 7. Double the records and the proof grows by exactly one.
What is real here, and what is not
The hash here is deliberately not a cryptographic one
It is FNV-1a in four lines, thirty-two bits, chosen so that every value on the page is eight characters instead of sixty-four and so that nobody could mistake this for something to use. A real Merkle tree uses SHA-256, and the hash is not the whole of it. RFC 6962 also separates the two cases before hashing: a leaf is SHA-256 of 0x00 followed by the record, an interior node is SHA-256 of 0x01 followed by its two children. Without that, an interior node's hash is a valid leaf hash and a proof for one can be replayed as a proof for the other. The encoding is part of the construction, and this page has neither: it could be forged in seconds by anybody who wanted to.
An odd node is carried up rather than duplicated
When a level has an odd number of hashes, the last one is promoted unchanged. Other implementations duplicate it and hash it with itself, and the difference matters: the duplicating convention has a known ambiguity where two different trees produce the same root. RFC 6962 specifies the carry-up form for exactly that reason, and that is what this does.
Proving membership is not proving anything else
A proof shows that a leaf is in a tree with a particular root. It says nothing about whether that root is the right one, who published it, when, or whether something was quietly removed. Those are the problems that transparency logs and blockchains exist to attack, and none of them is on this page.
1979 is the thesis, not a paper anybody read at the time
Merkle's tree construction is in his 1979 Stanford PhD thesis, Secrecy, Authentication, and Public Key Systems, and in a patent filed the same year. The paper most people cite, A Certified Digital Signature, was submitted to CRYPTO '79 and published in 1990, eleven years later. So 1979 dates the work rather than its arrival, and a reader who goes looking for a 1979 publication will not find the familiar one.
Sources
- R. Merkle, A Certified Digital Signature, from Merkle's own site, dated 1979 there. Submitted to CRYPTO '79 and published in 1990; the tree itself is in his 1979 Stanford thesis. The tree, and the argument for proving one leaf without the rest.
- B. Laurie, A. Langley and E. Kasper, Certificate Transparency, RFC 6962, 2013, for the odd-node convention this page follows and for the domain separation it does not: section 2.1 defines a leaf hash as SHA-256 of 0x00 followed by the entry and an interior node as SHA-256 of 0x01 followed by its children.
- Logical Art, the studio this belongs to.