How is the Leaf node weakness in Merkle Trees exploitable?

Question

Recently a weakness in leaf nodes of merkle trees was disclosed and it is claimed that this issue is exploitable to trick SPV nodes. How does the weakness make SPV nodes vulnerable to attack? What would an attacker do to exploit this attack?

Answer 1

In Bitcoin, inner nodes of the merkle tree are constructed by concatenating two 32 byte SHA256d hashes together. The resulting 64 byte value is hashed to get the next node in the tree. The leaf nodes are the transactions themselves. Merkle trees are used to prove that a transaction is part of a block as the merkle root is placed in the block header for the proof of work.

However, given just a merkle branch to prove a transaction's existence in a block (as SPV wallets need), it is impossible to distinguish which node in the branch is an inner node and which is a leaf node. Thus a special 64 byte transaction can be constructed which tricks SPV nodes into thinking it is actually an inner node of the tree and not a leaf node.

The last 32 bytes of that special transaction are constructed in such a way that it is also a valid hash of another fake transaction. Both the fake transaction and the last 32 bytes of the special transaction can be modified in order to brute force a transaction hash that is also valid as the last 32 bytes of the special transaction.

Once the special transaction is included in a block, the attacker can provide a fake proof to an SPV node that "proves" the fake transaction is part of the blockchain. This fake proof would be the legititmate merkle branch to the special transaction, but also includes the special transaction as if it were an inner node of the merkle tree and the fake transaction becomes the leaf node.

To protect against this attack, SPV nodes can simply verify that no inner nodes of a merkle branch are also valid transactions. Such an event is extremely unlikely, and such transactions are also non-standard so unlikely to be included in a block unless this specific attack were being performed.