Question about identical txids/merkle tree in Developer guide

Question

I am new to the technical details about Bitcoin and has been reading Developer guide on bitcoin.org. I have a question about below contents mentioning merkle tree, identical txids.

I googled and searched here but seemed to be no answer.

Note: If identical txids are found within the same block, there is a possibility that the merkle tree may collide with a block with some or all duplicates removed due to how unbalanced merkle trees are implemented (duplicating the lone hash). Since it is impractical to have separate transactions with identical txids, this does not impose a burden on honest software, but must be checked if the invalid status of a block is to be cached; otherwise, a valid block with the duplicates eliminated could have the same merkle root and block hash, but be rejected by the cached invalid outcome, resulting in security bugs such as CVE-2012-2459.

I don't quite understand above contents. How would a merkle tree collide with a block? What do "collide" and “eliminate duplicates" mean ? identical txids either mean same transactions or duplicate txid in order to generate a merkle root. What does "cache the invalid status of a block" stand for ? How would this be rejected by the cached invalid outcome?

I would appreciate it if you could help me understand. Thanks!

Answer 1

It refers to a (practically impossible) edge case due to how unbalanced merkle trees work.

Let's say you manage to find two transactions with the same transaction ID, T1 and T2.

Now, let's build the merkle tree for a very simple block:

                 H(A, B)
                /       \
       A = H(CB,X)       B = H(T1,T2)
        /        \        /         \
       CB        X       T1         T2

Now, if you were to build the same merkle tree without T2, you have an unbalanced tree with only 3 leaves. To fix this, the last leaf is duplicated, as such:

                 H(A, B)
                /       \
       A = H(CB,X)       B = H(T1,T1)
        /        \        /         \
       CB        X       T1         T1

However, since T1 and T2 share a transaction hash, your merkle root actually ends up being identical to the tree with two separate transactions.

Since the merkle root is the same, the proof of work for a block containing T1 and T2 would also be valid for a block containing only T1.

Thus, if the first block is considered invalid by an honest node, when it sees a second block arrive with the same block header, it may dismiss it as invalid automatically based on the cached status on the original block's header, even though the second block does not contain T2, and is in effect a different, potentially valid, block.