Leaf-Node weakness in Bitcoin Merkle Tree Design

[nud3l]

Describe the bug
The Bitcoin protocol has a flaw when validating consensus in SPV mode. There is a potential type confusion between Merkle tree middle and leaf nodes. This can lead to two kinds of attacks: leaf transactions that are incorrectly parsed as middle nodes, and middle nodes that are incorrectly parsed as transactions. The vulnerability was made public and analyzed in this post: https://bitslog.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-tree-design/

To Reproduce
It seems that InterBTC has no protection against the Bitcoin vulnerability of considering a transaction to be a middle node, creating a vulnerability in the bridge. The cost of the attack is estimated in 2^70 hashing operations, which is very high, but not prohibitive. In fact, if the attacker can peg-in tens of million of dollars in fake BTCs, and then peg-out real BTCs, the cost of pre-processing may be minor, specially for well-funded hacking groups. For comparison, the Bitcoin network performs 2^70 hashes every 10 seconds, and 1% of the Bitcoin hashing network performs 2^70 operations in only 15 minutes. Since we don't have the resources to perform the pre-processing, we can't demonstrate an exploit for this vulnerability in the InterBTC flaw. However, code inspection of the InterBTC code shows no protection measure against this attack.

Since the impact on interBTC is dependent on the economic damage on the system, we first need to determine potential damage. This is where it gets a little bit tricky. Technically, all of the iBTC in the system is currently at risk. However, we would argue that unless the exploit is economically feasible, the likelihood of the exploit is low. When assessing whether or not the exploit is profitable, it is important to note that a transaction is required per vault. The maximum amounts they could steal in a single transaction are currently:

• Max. damage if we consider iBTC issuable in a single request: Interlay: 19.567 BTC Kintsugi: 0.368 BTC
• Max. damage if we consider iBTC redeemable in a single request: Interlay: 18.24 BTC Kintsugi: 5.831 kBTC

So the maximum amount an attacker could steal with one transaction is less than 20 BTC. It is difficult to estimate the cost it would take to run this exploit - we'd have to make some assumptions. However, if we use this estimate: the total amount of iBTC stored in the vaults is currently 66 iBTC, which is probably similar to the cost of the attack pre-processing; then the cost is more than the potential gain of running the exploit. On top of that, if we understand correctly, there is the significant amount of bitcoin that the attacker needs to hold, plus the hashing power needed to produce a bitcoin block as a miner. Taking all of this into account, it seems to us that the attack is not currently economically feasible.

As such, we would argue that the current economic damage is zero.

Workaround
A mitigation for this attack is to limit issue, redeem, and replace requests and execution to at most 20 Bitcoin per request.

Expected behavior
The code should check that no tree node in the Merkle tree is a valid Bitcoin transaction. The Rootstock sidechain is protected from this attack by checking that no tree node built during the Merkle tree inclusion proof is a valid Bitcoin transaction. The code for this check can be found here: https://github.com/rsksmart/bitcoinj-thin/blob/ab624f09a77e48e04542a06d4a392c952b86aff2/src/main/java/co/rsk/bitcoinj/core/PartialMerkleTree.java#L230