Merkle Proof
A million records — 1,048,576 of them, since the tree wants a power of two — hash into a single number. 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.
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
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 security argument rests entirely on that choice: this one could be forged in seconds by anybody who wanted to. You can see the weakness in the table without being told: “record 0” through “record 6” hash to values that count upward in their first byte, because only the last character of the input differs and FNV-1a barely moves for that. A cryptographic hash is judged on doing the opposite.
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.