Merkle Trees and Block Validation

A single Bitcoin block can contain thousands of transactions, representing megabytes of data. If a mobile phone wallet had to download and verify every transaction in every block just to check if it received a payment, it would run out of storage and battery in a matter of days.

Satoshi Nakamoto solved this problem by integrating a computer science structure called a Merkle Tree (invented by Ralph Merkle in 1979) into the block design.

---

🌳 Anatomy of a Merkle Tree

A Merkle Tree is a binary tree of cryptographic hashes. In Bitcoin, it is constructed from the bottom up, starting with the raw transactions inside a block.

Let’s trace how a tree is built for a block containing four transactions: $T_A, T_B, T_C,$ and $T_D$.

                     [ Merkle Root ] (Stored in Header)
                            ▲
                            │
               ┌────────────┴────────────┐
               │                         │
           [ Hash_AB ]               [ Hash_CD ]
               ▲                         ▲
               │                         │
         ┌─────┴─────┐             ┌─────┴─────┐
         │           │             │           │
     [ Hash_A ]  [ Hash_B ]    [ Hash_C ]  [ Hash_D ]
         ▲           ▲             ▲           ▲
         │           │             │           │
       [ Tx_A ]    [ Tx_B ]      [ Tx_C ]    [ Tx_D ]

Step 1: Hash the Leaves

First, each individual transaction is hashed using double SHA-256: $$\text{Hash}_A = \text{SHA-256}(\text{SHA-256}(\text{Tx}_A))$$ $$\text{Hash}_B = \text{SHA-256}(\text{SHA-256}(\text{Tx}_B))$$ $$\text{Hash}_C = \text{SHA-256}(\text{SHA-256}(\text{Tx}_C))$$ $$\text{Hash}_D = \text{SHA-256}(\text{SHA-256}(\text{Tx}_D))$$

Step 2: Combine and Hash Sibling Pairs

Next, the sibling hashes are concatenated and hashed together to produce parent hashes: $$\text{Hash}{AB} = \text{SHA-256}(\text{SHA-256}(\text{Hash}_A + \text{Hash}_B))$$ $$\text{Hash}{CD} = \text{SHA-256}(\text{SHA-256}(\text{Hash}_C + \text{Hash}_D))$$

(Note: If a block contains an odd number of transactions, the final transaction hash is concatenated with a copy of itself to form an even pair.)

Step 3: Hash to the Root

This pairing process is repeated up the tree until only one single hash remains at the top. This is the Merkle Root: $$\text{Merkle Root} = \text{SHA-256}(\text{SHA-256}(\text{Hash}{AB} + \text{Hash}{CD}))$$

This single 32-byte hash is what is written into the Block Header.

---

⚡ The Power of SPV: $O(\log N)$ Validation

The genius of the Merkle Tree lies in Simplified Payment Verification (SPV). An SPV wallet (on a smartphone) only has the 80-byte block headers. It does not download the transactions.

Suppose you want to verify that your transaction ($\text{Tx}_B$) was indeed included in a block. You request a Merkle Proof (Merkle Path) from a full node.

To prove that $\text{Tx}_B$ is valid, the full node does not send you the other 3,000 transactions. It only sends you: 1. Your transaction $\text{Tx}_B$ (from which you compute $\text{Hash}_B$). 2. The matching sibling hashes along the branch: $\text{Hash}_A$ and $\text{Hash}_{CD}$.

  Step 1: Compute Hash_B from Tx_B.
  Step 2: Combine Hash_A + Hash_B to compute Hash_AB.
  Step 3: Combine Hash_AB + Hash_CD to compute the Merkle Root.
  Step 4: Check if your calculated Merkle Root matches the Merkle Root in the header.

If the roots match, it is mathematically impossible for $\text{Tx}_B$ to not be inside that block.

The Scaling Math

By using Merkle Trees, verification complexity drops from linear $O(N)$ to logarithmic $O(\log N)$:

Number of Transactions ($N$)	Legacy Full Download	Merkle Path Hashes Required
16	16 transactions	4 hashes
256	256 transactions	8 hashes
4,096	4,096 transactions	12 hashes
65,536	65,536 transactions	16 hashes

For a block with 4,096 transactions, an SPV client only needs to download 12 hashes (384 bytes) instead of downloading and parsing 4,096 transactions (approx. 2 Megabytes). This allows Bitcoin to scale to billions of lightweight mobile devices.