Recently a fix to the Bitcoin Merkle tree design weakness in the RSK’s bridge was built by making invalid SPV proofs whose internal hashes are valid Bitcoin transaction. While this solves the problem, it is by no means a “clean” solution: it creates false-negative cases (with very low probability) and it reduces verification efficiency.
While I was reviewing the code I came up with an idea to fix any Bitcoin SPV proof verifier by changing the member proof format. The new partial-Merkle-tree format can fix Bitcoin’s MERKLEBLOCK command to prevent rogue peers from attacking SPV peers using the weakness.
The old idea to soft-fork Bitcoin to invalidate 64-byte transactions is attractive, but also a coordination problem that could be avoided with this new proposal.
My idea is simple, and it’s not a fork, but a network protocol improvement.
Let A be the hash digest that must be combined with the hash digest B, such that the upper node hash is SHA256(SHA256(A | B)).
Therefore A = SHA256(SHA256(X)) and B = SHA256(SHA256(Y)), and X and Y are either Bitcoin transactions or other inner nodes.
Instead of storing A, the merkleblock structure should store a pre-image of A, or SHA256(X).
If the block only has the coinbase, nothing is done.
The pre-image change could be done to both left and right hashes, but it’s enough to do it to all left-side hashes that do not have children in the partial Merkle tree structure (let’s call them terminal hashes. to avoid confusion with leaf hashes).
Verifiers (SPV nodes) would apply a single SHA256() operation to the left-sided terminal hashes before combining them. The cost to the verifier is in the worse case only 33% more.
This basically limits the attacker’s ability to supply chosen-hash digests in order to build a transaction. Because the left side contains most of the previn hash, the attacker would need to brute-force a huge space (about 208 bits) in order to come up with a pre-image that maps to a owned previn. Meet-in-the-middle attacks would be expensive as UTXOs are not free.
The following figure exemplifies the construction. Normally, for a membership proof for transaction 4, the hashes N(0) and N(1,0) would need to be transmitted. With this new scheme, the intermediate hashes P(0) and P(1,0) (in red and circled) must be transmitted.
To implement this change, a new command MERKLEBLOCK2 could be implemented or the protocol version could be used to differentiate between the two modes of the MERKLEBLOCK command.
If the idea gets community support, I may write the BIP/code or invite anyone to do it. Last week I posted the idea in the bitcoin-dev mailing list but nobody cared to comment on it. It seems that bitcoiners are not fond of supporting lightweight SPV nodes now. The debate about SPV node security is still ongoing.
Bitslog 