Merkle trees

A Bitcoin block can contain several thousand transactions. How do you summarize them into a single small hash, while keeping the ability to prove that a specific transaction is in it, without downloading the whole block? The answer is an elegant structure: the Merkle tree.

The idea: hashing in pairs

We start from the transactions (the leaves of the tree). We compute the hash of each one, then we group these hashes two by two and hash each pair. We obtain half as many hashes. We repeat, level after level, until only one is left: the Merkle root.

                    Racine
                 H(H12 + H34)
                /            \
          H12                    H34
       H(H1+H2)               H(H3+H4)
        /     \                /     \
     H1        H2           H3        H4
     |         |            |         |
    Tx1       Tx2          Tx3       Tx4

Here H1 = H(Tx1), then H12 = H(H1 + H2), and finally Racine = H(H12 + H34). The root is a digest of all the transactions: changing any transaction changes its leaf hash, which propagates up to modify the root.

This root is stored in the block header (the small summary that is actually hashed to chain the blocks). The header stays tiny, regardless of the number of transactions.

The decisive advantage: the inclusion proof

The real power of the Merkle tree is the inclusion proof (Merkle proof). To convince someone that Tx3 really is in the block, you do not need to provide all the transactions: it is enough to give them the few hashes located on the path from Tx3 to the root.

Pour prouver que Tx3 est incluse, il faut fournir :
  - H4   (le frère de H3)
  - H12  (le frère de H34)
Le vérificateur calcule alors :
  H3   = H(Tx3)              (il a Tx3)
  H34  = H(H3 + H4)
  Rac. = H(H12 + H34)
puis compare Rac. à la racine de Merkle de l'en-tête.
Si elles coïncident : Tx3 est prouvée incluse.

The verifier only needed 2 hashes instead of the 4 transactions.

Why log(n)

The number of hashes to provide is the height of the tree. Since we halve the number of nodes at each level, this height is roughly log₂(n).

Number of transactions	Hashes in the proof
4	2
1 024	10
1 000 000	~20

For a million transactions, about twenty hashes are enough to prove inclusion. This is what allows "light" clients (SPV) to verify a transaction without storing the whole blockchain.

In summary

• A Merkle tree summarizes thousands of transactions by hashing in pairs down to a single hash: the Merkle root.
• This root is stored in the block header; modifying a transaction changes the root.
• The inclusion proof demonstrates that a transaction is present by providing only about log₂(n) hashes, without downloading the whole block.
• This is what makes light wallets possible, able to verify without storing everything.