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.
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):
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: