Two lists, one root: the duplicated-leaf ambiguity (CVE-2012-2459)

Bitcoin’s Merkle tree pairs an odd node with a copy of itself. So the lists [a, b, c] and [a, b, c, c] have the same root. In 2012 this let an attacker send a block with a duplicated transaction: nodes rejected it as invalid and remembered its hash as bad, so they later refused the valid block with the same hash. The bug was fixed by checking for the duplication.

What to look for

Bitcoin’s convention gives one root to two different lists. blockchainkit’s tree promotes odd nodes instead and binds the leaf count into the root, so every list has its own root.

The history behind this experiment: Breakthroughs in Authenticated Data Structures. See Exercises: ledgers and data structures for a worked solution to the exercise.

One root, two lists

import matplotlib.pyplot as plt

import blockchainkit as bk

honest = [b"coinbase", b"pay Bob", b"pay Carol"]
mutated = honest + [b"pay Carol"]
assert bk.structures.bitcoin_merkle_root(honest) == bk.structures.bitcoin_merkle_root(mutated)
assert bk.structures.MerkleTree(honest).root != bk.structures.MerkleTree(mutated).root
print("Bitcoin convention:", bk.structures.bitcoin_merkle_root(honest).hex()[:16], "for both lists")

Bitcoin convention: 3b6459144d8e0db1 for both lists

How many sizes are affected?

ambiguous = []
for n in range(1, 40):
    leaves = [bytes([i]) for i in range(n)]
    ambiguous.append(
        bk.structures.bitcoin_merkle_root(leaves)
        == bk.structures.bitcoin_merkle_root(leaves + leaves[-1:])
    )
assert ambiguous == [n % 2 == 1 and n > 1 for n in range(1, 40)]
fig, ax = plt.subplots(figsize=(8, 2.8))
ax.bar(range(1, 40), ambiguous, color="#dc2626")
ax.set(
    xlabel="number of leaves n",
    yticks=[0, 1],
    yticklabels=["distinct", "same root"],
    title="Is [..., x] confusable with [..., x, x]?",
)
fig.tight_layout()

Exercise

The plot shows the ambiguity for every odd n above 1 (a single leaf is never paired). Find a length-6 list whose Bitcoin-style root equals that of a length-8 list. (Hint: duplicate a whole pair.) Why does binding the count rule out all such cases?