BR Academy
Intro to Blockchain: How It Works and Why It Matters
0%
Exit course
Blocks, Hashes, and Cryptography·Lesson 7 of 25·12 min

Merkle Trees and Proof

The Concept

A block can hold thousands of transactions. Putting all of them directly into the header would make it huge and slow to hash repeatedly (a problem for consensus, Module 5). A Merkle tree solves this by compressing an arbitrarily large list of transactions into one small, fixed-size hash — the Merkle root — while still letting anyone prove any single transaction was included.

Here's how it's built, using the hashing properties from the previous lesson:

  1. Hash each individual transaction. These become the "leaves" of the tree.
  2. Pair up the leaf hashes and hash each pair together, producing a new, smaller layer of hashes.
  3. Repeat — pair up this new layer, hash each pair — until only one hash remains. That final hash is the Merkle root.

Because of the avalanche effect, if a single transaction anywhere in the original list is altered, its leaf hash changes, which changes the hash of the pair it belongs to, which changes the hash of the pair above that, cascading all the way up to a completely different Merkle root. So the block header can store just one 64-character hash and still cryptographically represent — and detect any tampering within — potentially thousands of transactions.

This structure also enables light verification: proving a specific transaction was included in a block without downloading every other transaction. You only need the "sibling" hashes along the path from your transaction's leaf up to the root (a "Merkle proof") — a handful of hashes instead of the entire block body. This is how lightweight wallets and mobile apps can verify a payment without storing the full blockchain.

Merkle proofs matter beyond mobile wallets, too. Many "Layer-2" scaling systems (mentioned in the history lesson) periodically post a single Merkle root to the main chain summarizing thousands of off-chain transactions, and rely on the same proof structure to let any user challenge a fraudulent summary by producing a Merkle proof that contradicts it. The pattern repeats throughout blockchain design: compress a large, ever-growing dataset into one small commitment, and give anyone a cheap way to prove facts about that dataset without re-downloading all of it. Once you recognize a Merkle tree, you'll see the same shape in rollup fraud proofs, in lightweight mobile wallets, and even in some non-blockchain systems like certificate transparency logs that browsers use to detect fraudulent website certificates.

It helps to be explicit about what a Merkle proof does and doesn't prove. It proves that a specific transaction's hash was one of the leaves that produced a given, already-trusted Merkle root — nothing more. It does not, by itself, prove that root is the correct root for a real, valid block; the verifier still needs to trust (or separately check) that the root came from a block header the network actually accepted. In practice, light clients combine Merkle proofs with the block header chain itself (Module 2's "Anatomy of a Block" and the immutability lesson that follows) to get both guarantees at once: the header chain establishes which blocks are real and accepted, and the Merkle proof establishes which transactions are inside a specific one of those real blocks.

The efficiency gain scales dramatically with size. For a block of 4 transactions, a Merkle proof needs only 2 sibling hashes. For a block of 1,024 transactions, a Merkle proof needs only 10 sibling hashes — because each layer of the tree halves the number of hashes, so the proof size grows logarithmically (with the number of doublings) rather than linearly (with the number of transactions). This is why a phone with limited storage can still cryptographically verify a single payment occurred inside a block containing thousands of other people's unrelated transactions, without ever downloading those other transactions.

Worked Example

Take four transactions: A, B, C, D.

  1. Hash each: hash(A), hash(B), hash(C), hash(D).
  2. Pair and hash: hash(hash(A) + hash(B)) → call it AB; hash(hash(C) + hash(D)) → call it CD.
  3. Final pair: hash(AB + CD) → this is the Merkle root.

Now suppose transaction B is altered after the fact. hash(B) changes completely (avalanche effect), which changes AB, which changes the final root. Transactions A, C, and D haven't changed, but the root has changed anyway — because the root depends on every leaf. Anyone comparing the new root against the one recorded in the block header immediately sees a mismatch and rejects the altered data.

Exercise

Using the same 4-transaction tree (A, B, C, D → AB, CD → Root), suppose transaction D is the one that gets altered instead of B. Write out, step by step, which intermediate hash changes first, which pair-hash changes next, and confirm whether the final root changes. Then answer: does altering A, B, C, or D ever leave the Merkle root unchanged? Why or why not, based on the pairing structure?

Finally, if this block instead held 1,024 transactions, how many sibling hashes would a Merkle proof need to prove transaction D's inclusion? Use the logarithmic relationship described in the Concept section to answer, showing your reasoning.

Recap

  • A Merkle tree repeatedly pairs and hashes transactions until a single Merkle root represents the entire set.
  • Changing any one transaction anywhere in the block changes the root, so integrity of thousands of transactions is provable with one small hash.
  • Merkle proofs let someone verify a single transaction's inclusion using only a handful of sibling hashes, without downloading the whole block — the basis of light-client verification.

Resources

← How Hashing Works Why Blockchain Is Immutable →