Is my copy the same as yours?
You download a large file in thousands of pieces from strangers. Or two database servers hold what should be identical copies of a billion rows. Or you want to confirm one transaction is part of a block containing thousands.
In each case the question is the same: is this data exactly what it should be? Comparing it all byte by byte is slow, and sometimes impossible because you do not have the other copy.
A Merkle tree answers the question with a handful of small numbers.
The ingredient: a hash
A cryptographic hash function turns any amount of data into a short, fixed-length fingerprint.
- The same data always gives the same fingerprint.
- Change a single bit and the fingerprint changes completely.
- It is not feasible to find two different pieces of data with the same fingerprint.
So two fingerprints that match mean, for all practical purposes, that the data matches.
For one file, one fingerprint is enough. A Merkle tree is what you build when there are many pieces and you want to check them individually.
Building the tree
Split the data into blocks and hash each one
These fingerprints are the leaves, the bottom row.
Pair them up and hash each pair
Join two fingerprints and hash the result. That gives one fingerprint that stands for both.
Repeat on each new row
Each row is half the size of the one below.
Stop when one fingerprint is left
That is the root. It depends on every block.
- changed
- the block being proved, and its path
- the three fingerprints sent as proof
Start. Eight blocks of data along the bottom: files, or transactions, or chunks of a download.
Change one byte, and the root changes
In the second part of the animation, one block is altered. Follow what happens.
Its fingerprint changes. That fingerprint was an input to its parent, so the parent changes. And its parent. All the way up to the root.
So the root is a fingerprint of the entire data set. If two parties have the same root, they have the same data. If the roots differ, something is different somewhere.
And you can find where quickly. Compare the two children of the root. One matches and one does not. Go down the one that does not, and compare its children. Each step halves the search. With a million blocks, about 20 comparisons lead straight to the block that differs.
Example
Two servers, a billion rows
Two copies of a database should be identical. Each server builds a Merkle tree over its rows and they exchange roots.
Same root: done. One short number confirmed a billion rows.
Different roots: they walk down the tree together and exchange only the parts that differ. A few thousand rows travel over the network, not a billion.
Proving one block belongs
The third part of the animation is the most surprising use.
You hold one block and you trust the root, which you got from a reliable source. Someone you do not trust claims your block is part of that data set. Can they prove it without sending you everything else?
Yes. They send only the fingerprints of the siblings along the path from your block up to the root. In the demo, three of them.
- Hash your block.
- Combine it with the first sibling and hash. That gives the parent.
- Combine that with the second sibling and hash.
- And again with the third.
- Compare what you have with the trusted root.
If it matches, the block is genuine. Nobody can fake the proof, because that would require finding different data with the same fingerprint.
| Blocks | Fingerprints needed for a proof |
|---|---|
| 8 | 3 |
| 1,024 | 10 |
| 1,000,000 | 20 |
| 1,000,000,000 | 30 |
The proof grows by one fingerprint each time the data doubles. Proving one item in a billion takes 30 small numbers.
Where you will meet it
- Version control. Git names every file, folder and commit by the hash of its contents. A folder's hash depends on the hashes inside it, so one commit id pins down the whole project.
- Peer-to-peer downloads. Each piece is checked against the tree as it arrives, so a bad piece from an untrusted peer is caught immediately.
- Blockchains. A block header stores one Merkle root for all its transactions. A phone can verify that a payment is included using a short proof, without downloading the block.
- Distributed databases. Copies compare trees to find and repair the rows that have drifted apart.
- Certificate logs. Public, append-only records of issued certificates use Merkle trees so anyone can check nothing was removed.
Key takeaways
- A hash is a short fingerprint of data. Any change to the data changes it.
- A Merkle tree hashes blocks, then hashes pairs of hashes, up to a single root.
- The root is a fingerprint of everything: change any block and the root changes.
- Two trees can be compared from the top down to find exactly which blocks differ.
- One block can be proved to belong using only the sibling hashes on its path: 20 for a million blocks.