RightSignal

Cryptography from zero · 10 of 111 / 3

Merkle trees

The concept

How one 32-byte hash can vouch for a million files

A Merkle tree hashes data in pairs, level by level, until one hash is left: the root. If you trust the root, you can check any single piece using only a handful of hashes, not the whole dataset.

Take four chunks A, B, C, D. Hash each one to get hA, hB, hC, hD (the leaves). Then hash pairs together: hAB = H(hA ‖ hB) and hCD = H(hC ‖ hD), where ‖ means 'stuck end to end'. Finally root = H(hAB ‖ hCD).

To check chunk C, you need only hD and hAB, called the proof (or audit path). Hash C to get hC, combine it with hD to get hCD, then combine that with hAB to get a root. If it matches the trusted root, C is genuine.

What it’s forTells you how many hashes someone must send to prove one piece belongs to the tree.

proof size = ⌈log₂ n⌉ hashes

n: number of pieces (leaves) in the tree
log₂ n: how many times you can halve n before reaching 1, i.e. the tree's height
⌈ ⌉: round up to a whole number

What it givesA proof that grows by just one hash each time the data doubles.

8 chunks: log₂ 8 = 3 hashes in the proof
1,048,576 chunks: log₂ 2²⁰ = 20 hashes
20 × 32-byte SHA-256 hashes = 640 bytes of proof

Cryptography from zero · 10 of 112 / 3

Merkle trees

Real-life use case

Bitcoin phone wallets confirm a payment without the whole blockchain

Every Bitcoin block header stores the Merkle root of all the transactions in that block. A light wallet keeps only the small block headers, not the hundreds of gigabytes of full blocks.

To confirm your payment in a block of about 4,000 transactions, the wallet fetches it plus a proof of about 12 hashes (2¹² = 4,096). It rehashes up the tree and compares the result with the root in its stored header.

Certificate Transparency, the public logs of website certificates from the previous lessons, works the same way: each log is a Merkle tree, so anyone can get a short proof that a given certificate is really in the log.

Cryptography from zero · 10 of 113 / 3

Merkle trees

How it helps

Each hash up the tree locks in everything beneath it

Because every parent hash covers both children, the root depends on every byte of every chunk. Change chunk C by one bit and hC changes, so hCD changes, so the root changes.

To pass a fake C' off as genuine, an attacker would need some level where different inputs give the same hash: a collision. A good hash function makes that infeasible, so a short proof is as convincing as downloading everything.

The one thing you must get from a trusted source is the root, for example signed by the publisher or buried in a Bitcoin header. If an attacker could also hand you the root, they could simply build their own tree.

Your RightSignal

Topics in News

How one 32-byte hash can vouch for a million files

Bitcoin phone wallets confirm a payment without the whole blockchain

Each hash up the tree locks in everything beneath it

Got it?