Arbres de Merkle

A block may contain thousands of transactions. How can a lightweight device verify that one specific transaction is included without downloading them all?

The answer is the Merkle tree — a structure that lets you prove membership with just a handful of hashes.

A Merkle tree (or hash tree) is a binary tree where:

• Each leaf is the hash of one transaction
• Each internal node is the hash of its two children combined
• The single top node is the Merkle root

Construction works bottom-up. Hash each transaction to form the leaves, then repeatedly hash pairs together until only one hash remains.

The Merkle root is a single hash that represents every transaction in the block. It is stored in the block header.

If even one transaction changes, the root changes — so the root acts as a compact fingerprint of the entire transaction set.

If a level has an odd number of nodes, the last node is usually duplicated so it can be paired.

This keeps the tree balanced and ensures every node has a sibling to hash with.

A Merkle proof is the small set of sibling hashes needed to recompute the root from a single leaf.

To prove tx2 is included, you only need the siblings along its path — not the other transactions themselves.

For N transactions, a Merkle proof needs only about log2(N) hashes.

For one million transactions, that is roughly 20 hashes instead of a million — a massive saving for light clients and mobile wallets.

Simplified Payment Verification clients download only block headers, not full blocks.

Using a Merkle proof from a full node, an SPV client can confirm a transaction is in a block without trusting that node blindly.

Because every transaction feeds into the Merkle root, altering any transaction produces a different root.

The header's root would no longer match the recomputed root, so the tampering is immediately exposed.

Merkle trees are used far beyond transaction lists. Ethereum uses a variant called a Merkle Patricia Trie to commit to the entire world state and to receipts.

Git, IPFS, and many databases also rely on Merkle structures for integrity.

The Merkle tree turns a large set of transactions into a single root hash while still allowing compact, verifiable membership proofs.

It is one of the most elegant data structures behind scalable, trustless verification.

Check your grasp of Merkle proofs.

You learned that:

• A Merkle tree hashes transactions in pairs up to a single root
• The Merkle root is a fingerprint stored in the header
• A Merkle proof needs only ~log2(N) hashes
• This enables efficient light clients and tamper detection

Next we dig into the hashing that powers all of this.