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

[SergioDemianLerner]

In 2018 I reported a bug in Bitcoin that affects automated systems receiving SPV proofs. The cost of the attack is high (about 2^70 initial double-SHA256 operations, and then 2^40 operations per attack), so I don't consider this a real problem now, but it could be in the future.

Both keep-network tBTC and interlay PolkaBTC, which are using summa-tx forks, would be vulnerable to this attack.

You can read more about the problem here: https://bitslog.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-tree-design/

The easiest solution to the problem is presented here:
https://bitslog.com/2018/08/21/simple-change-to-the-bitcoin-merkleblock-command-to-protect-from-leaf-node-weakness-in-transaction-merkle-tree/

Basically the idea is to send the SHA256 pre-image of left-sided transaction hashes, instead of the transaction hash itself.

Verification would look something like this (untested code):

for (uint i = 0; i < nodes; i++) {
            bytes32 _next = _proof.index(i * 32, 32);
            if (_idx % 2 == 1) {
                _current = _merkleStep(singleSha256(_next), _current);
            } else {
                _current = _merkleStep(_current, _next);
            }
            _idx >>= 1;
        }

Another simpler solution is to test each inner node and abort if it's a valid transaction, but there is a false-positive probability of about 2^26 that a random 64-byte chunk has the format of a valid Bitcoin transaction (but a very weird anyone-can-spend transaction).
So a more efficient solution could be that the prover has to show the left pre-image only in the case that the inner node has:

• input count == 1
• output count == 1
• output script size + input script size = 4 (stored a fixed positions)
• prevout index < 2^17
• nSequence highest bit set.

[prestwich]

Thanks for filling an issue. We were aware of this, and decided it was safe to leave as-is for now, but didn't document the decision. It's on my list for remediation and I'll leave this open until we can get back to it 👌

[nud3l]

@prestwich did you come to a conclusion on the issue and if/how you decided to resolve it?

[prestwich]

this code is no longer maintained