SPV verifier may accept Merkle proofs for Bitcoin transactions not in the chain #285

The Bitcoin Merkle tree construction is such that an inner node of the tree may correspond to a valid serialization of a 64-byte transaction. This can be used to trick a node into believing that a block has less transaction than it has (that a row of the tree are actually its leaves). This can also be used to trick an SPV verifier into accepting a Merkle proof for a transaction that was not included in the block, by getting a specific 64-byte transaction included in the block such as it may be interpreted as an inner node of a deeper tree.

Suhas Daftuar gave a good explanation of the issue in this writeup sent to the bitcoin-dev mailing list. The TL;DR in the context of this project is that an attacker may, with significant but not impractical bruteforce, craft a 64-byte transaction which can be re-interpreted as an inner-node in a Merkle tree to fake an inclusion proof of an arbitrarily sized transaction one level deeper.

Here is a graph which illustrates this issue that i stole from @SergioDemianLerner's blog post on the topic. In this picture T is the 64-byte transaction that can be re-interpreted to fake an inclusion proof of R, which is itself not part of the block.

The final-spv crate in this project implements an SPV verifier with no mitigation in place for this attack. It is my understanding that BitVM is primarily used to implement bridges to side-systems and therefore the impact of accepting a proof of inclusion for a transaction not actually included in the Bitcoin blockchain may be critical.

Fortunately, there exists a number of possible mitigations. The most common one being to request a Merkle proof for the coinbase transaction in addition, and checking that both Merkle proofs have an equal depth. This is because the attack leveraging 64-byte transactions involves a transaction that is one level deeper than all other transaction, as demonstrated by the above picture. Another approach could be to verify that no inner node in the Merkle proof correspond to a valid Bitcoin transaction serialization, as there is negligible probability that this would happen normally. There may be other approaches as well. @SergioDemianLerner may have suggestions on the topic, being familiar with both this issue and BitVM.

Pinging also @ekrembal who told me the Citrea bridge was vulnerable too and therefore may have input on the best approach here.