SPV Merkle proof malleability allows the maintainer to prove invalid transactions

Summary

By publishing specially crafted transactions on the Bitcoin blockchain, the SPV maintainer can produce seemingly valid SPV proofs for fraudulent transactions.

The issue was originally identified by Least Authority in the tBTC Bridge V2 Security Audit Report as Issue B: Bitcoin SPV Merkle Proofs Can Be Faked. A mitigation was believed to have been in place, but this turned out to contain an error, and the issue had not been effectively mitigated.

Details

This is achieved by creating a 64-byte transaction that the fraudulent transaction treats as a node in its merkle proof:

The attacker creates the malicious transaction E and calculates an unusual but valid transaction D, so that the last 32 bytes of D are a part of the merkle proof of E:

D = foo | hash256(E')
E' = bar | hash256(E)

foo and bar are arbitrary 32-byte values selected to facilitate this attack.

The attacker can then publish D and wait for it to be mined. A valid SPV proof for D can then be transformed into a proof for E by prepending bar and foo to the merkle proof, and changing the transaction index into one matching E's implied position in the merkle tree.

Calculating a suitable value for E' has been estimated to require between 2^60 to 2^81 operations. By contrast, the current Bitcoin hashrate is approximately 2^69. Thus the cost of performing the requisite brute-force is at most similar to, or possibly up to 1,000,000 times lower than, the cost of mining 6 Bitcoin blocks at the current difficulty.

Impact

The vulnerability does not enable the SPV maintainer to do anything they would not have been able to do otherwise. However, the ability to bypass the need to mine 6 blocks at the current difficulty makes abusing the SPV maintainer position significantly cheaper.

Patches

Adding the coinbase transaction and its merkle proof into the SPV proofs prevents this issue, by increasing the brute-force required to 2^224. If the length of the coinbase proof matches the length of the transaction proof, and both proofs are valid for the same header, we can trust that the exploit has not been abused for the transaction.

Workarounds

The trusted SPV maintainer position prevents this issue

References

Weaknesses in Bitcoin’s Merkle Root Construction

Leaf-Node weakness in Bitcoin Merkle Tree Design

SPV proof verification vulnerable to potential (but expensive to exploit) Merkle tree problem #192

tBTC Bridge V2 Security Audit Report