Constructing the Merkle Tree: Mathematical Proofs and Transaction Root Generation

A block header cannot hold megabytes of raw transaction data; it is strictly constrained to an 80-byte memory space. To cryptographically bind an arbitrary number of transactions to this tiny header, Bitcoin utilizes a binary Merkle Tree.

This guide details the mathematical pairing equations, leaf replication rules for odd transaction counts, and the logarithmic efficiency of Merkle validation audits.

1. What is a Merkle Tree?

A Merkle Tree is a binary cryptographic tree constructed by recursively pairing and hashing transaction identifiers (TXIDs) until a single 32-byte hash remains: the Merkle Root. This root is saved directly inside the 80-byte block header.

 THE BINARY MERKLE TREE LAYOUT

 [ Merkle Root (H_ABCD) ]
 ▲
 ┌─────────────────────┴─────────────────────┐
 │ │
 [ Hash AB (H_AB) ] [ Hash CD (H_CD) ]
 ▲ ▲
 ┌───────┴───────┐ ┌───────┴───────┐
 │ │ │ │
 [ Tx A ] [ Tx B ] [ Tx C ] [ Tx D ]
 (Coinbase Tx) (TXID) (TXID) (TXID)

• Leaf Nodes: The bottom tier of the tree. These represent the raw transaction hashes (TXIDs) ordered sequentially.

• The Coinbase Rule: Leaf 0 (Tx A above) must always represent the block's Coinbase Transaction.

• Internal Parent Nodes: Intermediary hashes generated by combining child hashes.

• Root Node: The single 32-byte top-level hash. Altering a single bit of any transaction in the block will cascade up the tree, completely changing the Merkle Root hash and invalidating the block header.

2. Mathematical Pairing and Odd Leaf Duplication

Let's define a block containing $N$ transactions, represented by leaf hashes $L_0, L_1, L_2, \dots, L_{N-1}$.

The Pairing Function

Any parent node $H_P$ is computed by concatenating its left child $H_L$ and right child $H_R$ and applying a double-SHA256 hash:

$$H_P = \text{SHA256}\Big(\text{SHA256}\big(H_L \parallel H_R\big)\Big)$$

Where $\parallel$ represents raw byte concatenation.

The Odd Leaf Duplication Rule

If a tree level contains an odd number of nodes, the final node does not have a partner. To resolve this, the odd node is paired with itself:

$$\text{If } H_K \text{ is odd: } \quad H_{\text{Parent}} = \text{SHA256}\Big(\text{SHA256}\big(H_K \parallel H_K\big)\Big)$$

 ODD TRANSACTION COUNT DUPLICATION

 [ Merkle Root ]
 ▲
 ┌─────────────────────┴─────────────────────┐
 │ │
 [ Parent Hash AB ] [ Parent Hash CC ]
 ▲ ▲
 ┌───────┴───────┐ ┌───────┴───────┐
 │ │ │ │
 [ Tx A ] [ Tx B ] [ Tx C ] [ Tx C ]
 (TXID) (TXID) (TXID) (Duplicate Hash)

Note: The transaction $Tx_C$ is not duplicated in the actual block data; only its hash is duplicated in memory during the Merkle root calculation.

3. Logarithmic Audit Efficiency (SPV Clients)

The primary benefit of a Merkle Tree is that it allows Simplified Payment Verification (SPV) light clients to verify that a transaction is included in a block without downloading the entire blockchain or block data.

To verify Transaction $A$, an SPV client only needs:

1. The 80-byte block header (containing the validated Merkle Root).

2. The transaction $Tx_A$.

3. The Merkle Audit Path (the sibling hashes along the path from $Tx_A$ to the root).

The Math:

For a block containing $10,000$ transactions:

• Instead of downloading all 10,000 transactions (approx. $5\text{ MB}$ of data), the client only needs the Merkle Path containing: $$\log_2(10,000) \approx 14 \text{ sibling hashes}$$

• This represents only $14 \times 32\text{ bytes} = \mathbf{448\text{ bytes}}$ of data!

• The client hashes $Tx_A$ with the first sibling, hashes that result with the next sibling, and so on. If the final calculated hash matches the Merkle Root in the block header, the transaction is mathematically proven to be valid and included in the block.