The design of Bitcoin Merkle trees reduces the security of SPV clients

This article describes a weakness in the design of Bitcoin Merkle trees that reduces the security of SPV (Simple Payment Verification) clients. By exploiting the weakness, an attacker can simulate a payment of arbitrary amount to a victim using a SPV wallet, and trick the victim into accepting it as valid (a “Fake Transaction Attack” or FTA). Most SPV wallets are vulnerable to the FTA, as well as automated non-fully validating systems that accept SPV proofs to release funds, such as the Blockstream Elements sidechain in non-federated mode and the RSK Bridge contract. However automated systems are at higher risk than standard SPV wallets.

The weakness was discovered in August 2017, by RSK’s Chief Scientist, Sergio Demian Lerner, but it was known to members of the Bitcoin Core team before that time, according to personal communications between Sergio and the Bitcoin Core team.

This article provides only a high-level explanation of the weakness and it refers to Sergio Lerner’s article for more technical details. The motivation for this article is that it affects the RSK’s Bridge contract.

The Problem ¹ : Bitcoin Merkle trees do not explicitly differentiate between inner nodes and leaf nodes. Because Bitcoin Merkle tree inner nodes have no strict format, an attacker can submit a transaction that has the exact length of an inner node (64 bytes) to the blockchain and force a victim to interpret this transaction as an inner node (this transaction is referred to as a dual transaction/node below.) The attacker can then provide a proof that extends the dual transaction/node, and a proof for any payment that the attacker wishes.

The Fake Transaction Attack ²: The detailed steps required for the attack to succeed are described in Sergio’s article. Although the steps are beyond the scope of this article, it is interesting to note that the attacker is required to brute-force the transaction data in such a way that it appears to have been part of the blockchain’s history and that it appears to carry the BTC value that the attacker desires. In addition, the attacker should brute-force a new transaction with an ID that matches the second half of the dual transaction/node. More specifically, the 64-byte Bitcoin transaction which consists of two 32-byte chunks, should be brute-forced by the attacker in a particular order: the second chunk of the transaction initially and the first chunk of the transaction afterwards. As explained in Sergio’s article, the total number of bits that need to be brute-forced is 72, that correspond to 72 bits for the brute-forcing of the second chunk of the dual transaction/node and 40 bits that correspond to the brute forcing of the first chunk of the dual transaction/node.

Potential Targets: Normal SPV wallets can be tricked by attacks that are much less expensive than the FTA. For example, the combination of a network sybil attack, a double-spend transaction and the private mining of confirmation blocks. Therefore SPV wallets are generally only used for low value payments and the risk of the FTA targeting SPV wallets is low. However, an automated SPV system that process highly valuable payments may be far more exposed to the FTA, since it needs to base its security on longer confirmation periods (e.g. 100 blocks). As the cost of the FTA is independent on the number of confirmation blocks, the existence of the FTA renders most automated SPV systems insecure. However, performing the FTA requires a significant monetary investment and significant computational resources while simple solutions, which do not have to be soft- or hard-forks, can prevent the attack.

The Cost: The technology required to build a custom ASIC that performs the brute-forcing required for this attack is very similar to that used in Bitcoin miners. A state-of-the-art Bitcoin miner reaches 14 TH/s and costs $1,300 USD, and an attacker who buys 1,000 such miners, investing $1.3 million, can scan the 72-bit space in 4 days. An additional $1-$10 million for ASIC chip design and tape-out may be required, depending on the node density, but if the attacker owns a chip that can accomplish a programmed pattern match search, the cost of the design/tapeout is saved.
Furthermore, the attacker needs to own at least 2³⁶-1 satoshis, or approximately 687 BTC, in order to brute-force the amount of the dual transaction/node to any value below 687 BTC. The Bitcoin used will not be lost because the attacker will be a miner and can collect the transaction fees, consume the transaction output and recover all the funds. However creating an anyone-can-spend output and a high-fee transaction would put an attacker at risk that another miner reverts the blockchain to re-mine the block and collect the fee and/or the output. The attacker will have to mine several blocks in-private (selfish-mining) to prevent rollbacks and, if the attacker is not in collusion with 51% of the miners, then this may cost the attacker millions in rented hashing power. But if the attacker is colluding with 51% of the miners there will not be an additional cost. The attack can be profitable therefore, if the attacker can cheat one or more users for at least $1.3 million.

The Remedies: There are several remedies to this weakness that range from a simple check that can be performed by an SPV client, to soft-fork and hard-fork modifications. Sergio’s article describes the full range of solutions but just three of them are described here:

• Since there are no 64-byte Bitcoin transactions that pass standard checks and since the probability of a random 64-byte data chunk being a syntactically-valid Bitcoin transaction is overwhelmingly low, SPV clients can flag any node (either internal or leaf) that represents a valid 64-byte transactions as an attack and refuse to accept the associated SPV proof.
• A soft-fork would require all blocks that have transactions of 64 bytes in size to become invalid.
• A hard-fork would introduce a prefix to internal nodes of the Merkle tree and a different prefix for transaction IDs. A similar solution has been implemented by Ripple and in RSK.

Conclusion: A weakness in the design of Bitcoin Merkle trees reduces the security of SPV clients. By exploiting the weakness, an attacker can provide a proof that a fake payment is indeed valid and force a victim to make such a payment. Although most SPV wallets are vulnerable to this attack, systems that automatically accept SPV proofs, such as the Blockstream Elements sidechain in non-federated mode and the RSK Bridge contract, are a greater potential targets. However, simple checks can be implemented to prevent such attacks. Soft-fork or hard-fork modifications could also be introduced.

—————————————————————————————————————————————-

1 It is interesting to note that since this attack forces SPV wallets to interpret a transaction as a node, it can be considered complementary to an attack that forces SPV wallets to interpret a node as a transaction, as first described by Andrew Miller in his security audit of Ethereum’s BTC relay.

2 The same vulnerability allows an attacker to fork the Bitcoin blockchain in two without reconciliation, however this attack costs 2240 double SHA2 operations, so the attack is impractical. See Sergio’s article for more details.