A Change to the MERKLEBLOCK command to protect from Leaf-Node weakness

We covered recently the Leaf-Node weakness and the different proposals that were discussed to address it.

Sergio Demian Lerner, from the RSK team and one of the participants in the discussion, went on presenting his idea for a new fix on his blog.

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.

To understand this weakness it is important to note that Bitcoin Merkle Tree does not distinguish inner nodes and leaf nodes but only determines the depth of the tree by the number of transactions in it.

Since inner nodes are 64 bytes long with no particular format, an attacker can send a 64 byte long transaction to the blockchain and force a vulnerable system (an SPV) to absorb the transaction as an inner node of the SPV’s tree.

Such an attacker can consequently tender a proof of payment of any transaction by providing an SPV proof that integrates an extra leaf node which extends the double transaction.

This is a weakness that compromises the security of SPV proofs and consequently SPV wallets. A recent fix to this weakness is the creation of invalid SPV proofs that have valid Bitcoin transactions as internal hashes. This solves the immediate problem but also creates “false-negative cases”, thus reducing verification efficiency.

The better fix being proposed is to change the member proof format of the SPV verifier (node), resulting in a new partial-merkle-tree format that can fix Bitcoin’s MERKLEBLOCK command to keep attackers from attacking vulnerable SPV peers.

For instance assuming A and B are hash digests that must be combined 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.

Rather than store A, the merkleblock structure should store a pre-image of A, or SHA256(X).

If the block only has the first initial transaction (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 hahes. to avoid confusion with leaf hashes).

Before combining A and B, SPV nodes then only need to apply a single SHA256() operation to the left-sided terminal hashes. This is a little expensive to the verifier but it costs a maximum of 33% more.

This action prevents the attacker from building a transaction and he would have to brute-force a huge space (~208 bits) to create a pre-image that matches the previn of the target because the left side holds most of the previn.

He may try a ”meet-in-the-middle attack” but this would be expensive and so it discourages peer attacks.

This idea fixes the weakness in transaction merkle tree and the problem with the initial fix.

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.

Its implementation would require implementation of a new command MERKLEBLOCK2 or the use of its protocol version to distinguish the two modes of the MERKLEBLOCK command.

Demian concludes that if the idea gets community support, he may write a BIP/code or invite people to do it.

Resources

Support us and the authors of this article by donating to the following address:

33MQg9hkHSvRqnqqDsxwskS6ivYXifGpan

Comments powered by Talkyard.