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)$:

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.