Handling Odd Transaction Counts

A Merkle Tree is a binary tree, which means it expects nodes to be paired ($2, 4, 8, 16$). However, a Bitcoin block can contain any number of transactions (e.g., 3, 5, or 1,237).

1. The Duplication Rule

When a Merkle Tree has an odd number of nodes at any given level, Bitcoin handles it by duplicating the last node in the set to create a pair.

Example: A 3-Transaction Block

If we have transactions $TX_A, TX_B, TX_C$: 1. Leaf Level: $H_A, H_B, H_C$ (Odd count). 2. Duplication: $H_C$ is duplicated to create a pair ($H_C, H_C$). 3. Branch Level: * Pair 1: $H_{AB} = Hash(H_A + H_B)$ * Pair 2: $H_{CC} = Hash(H_C + H_C)$ 4. Root Level: Merkle Root $= Hash(H_{AB} + H_{CC})$.

2. Recursive Duplication

This duplication happens at every level of the tree where an odd number of nodes exists. If there were 5 transactions, the 5th would be duplicated to pair with itself at the first level, then that branch might need to be duplicated again at the next level.

3. The Implementation Detail

In the Bitcoin Core source code, this logic is found in consensus/merkle.cpp. It ensures that every transaction is always "accounted for" in the path, even if it has to be paired with itself.

4. Why Duplicate Instead of Null?

Duplicating the hash ensures that the tree remains "balanced" and that the hashing logic doesn't need to handle "empty" or "null" inputs, which could lead to edge cases or security vulnerabilities.

Transaction Count	Depth	Nodes Processed
1	0	1
2	1	3
3	2	7 (with duplication)
4	2	7

Next, we will discuss a famous vulnerability related to this duplication rule: Merkle Malleability.