What is a Merkle tree?

How do you check that a transaction is in a block without downloading all of its transactions? Think of a folder full of receipts: we want to confirm that one particular receipt belongs to its contents without photocopying the entire folder.

The process starts with hashes, the digital “fingerprints” of data. In a typical binary Merkle tree, each transaction corresponds to a hash. The hashes are combined in pairs, and a new hash is computed from each pair. The process repeats, level by level, until a single final fingerprint is left: the Merkle root.

Imagine four transactions, A, B, C and D. The fingerprints of A and B produce a combined fingerprint, and so do those of C and D. The two results are combined into the root. If A changes, its fingerprint changes too, affecting the entire path up to the root.

Why it matters

To check that A is included, all we need is the hash of B and the combined hash of C and D. Together with A and the correct order of combination, they let us recompute the root. This small set of data is called a Merkle proof. As the tree grows, the proof stays much smaller than the full data set.

In Bitcoin, the root of the transactions is included in the block header. That way, an app can check that a transaction is included in a specific block without downloading all of its contents. We see this data efficiency as a key advantage for apps with limited storage or connectivity.

What to watch out for

A Merkle proof proves inclusion in a specific data set, not that the transaction is valid or final. You also need to know that you are comparing against the correct, trustworthy root.

Likewise, when an exchange uses Merkle trees in a Proof of Reserves audit, confirming that your balance is included in a snapshot doesn’t by itself prove that all of its liabilities have been disclosed or that it holds sufficient assets.