Merkle Trees

A Merkle tree is a binary hash tree. Leaves are transaction hashes or other data commitments. Pairs of child hashes are concatenated and hashed to create parent nodes. That process repeats until one root remains. The root changes if any committed leaf changes, so a small root value can represent the integrity of a large set.

Bitcoin places a Merkle root in each block header to commit the header to the block's transactions.

Take four transaction hashes: A, B, C, and D. Hash A with B to form AB, hash C with D to form CD, then hash AB with CD to form the root. With eight leaves, one more tree level is added. The number of leaves can grow dramatically while a proof for one leaf only needs the sibling hash at each level.

This hierarchy is why Merkle trees support efficient verification without transmitting the entire data set.

A balanced binary tree with 1,024 leaves has 10 levels because 2^10 equals 1,024. An inclusion proof therefore needs roughly one sibling hash per level—about 10 hashes instead of 1,023 other transactions. Doubling the set adds only one additional proof level.

This logarithmic scaling is useful for light-client and data-commitment designs where bandwidth is limited.

A Merkle proof shows that a piece of data belongs to the set committed by a root. It does not prove that the transaction was authorized, that the block obeys consensus rules, or that the chain containing the block is canonical. Those are separate checks.

A malicious party can also build a perfectly consistent Merkle tree over false data. The tree proves consistency with the commitment, not truth about the outside world.

Bitcoin uses Merkle trees to commit to block transactions. Ethereum uses Merkle-Patricia trie structures for authenticated state and other commitments. Modern systems also use sparse Merkle trees and related authenticated data structures.

The common idea is compact commitment plus efficient proof, but proof format and security assumptions depend on the structure.

A Merkle tree compresses many individual commitments into one root while preserving efficient membership proofs. Begin with hashes of the underlying records as leaves. Pair neighboring hashes, concatenate each pair in a protocol-defined order, and hash again. Repeat until one root remains. A verifier who already trusts that root does not need the full dataset to check one leaf; the verifier needs the leaf plus the sibling hash at each level along the path to the root.

For a balanced binary tree containing many leaves, the proof grows roughly with the logarithm of the number of leaves. That is the crucial scalability property. Doubling the dataset does not double the number of hashes needed for one inclusion proof.

The proof is only as meaningful as the root commitment and the protocol rules used to build the tree. A Merkle proof does not independently tell a verifier that the block itself is canonical, finalized, or honestly produced. It only proves that a particular leaf is consistent with a particular committed root under the stated hashing rules. Similarly, changing one committed transaction changes hashes along its branch and therefore the root, absent a successful cryptographic collision. This makes silent alteration detectable, but consensus is still needed to decide which root the network accepts.

1. Starting from eight transaction hashes, describe the steps used to obtain one Merkle root.

2. Why does an inclusion proof need sibling hashes along a path rather than the entire tree?

3. What happens to the Merkle root if one committed transaction changes?

4. What does a valid Merkle proof prove, and what does it not prove about consensus or finality?

5. Why is logarithmic proof size useful for light clients?

6. Correct this statement: “A Merkle proof proves that a transaction is finalized on the canonical chain.”