Destabilizing Bitcoin consensus with Purge Attacks

A few days ago, Mike Kelly asked me on Twitter (1) if reorganization attacks can lead to opportunistic double-spends and (2) if this poses a risk to Bitcoin. It’s a slightly complicated—but very interesting—question, so we will unpack it step by step.

Here is the TLDR:

1. Replace-By-Fee is a policy for replacing an existing transaction in a mempool (the “waiting area” for Bitcoin transactions.)
2. Transaction replacement can be used to double-spend merchants with a zero-confirmation policy (which is why zero-conf isn’t safe.)
3. In a reorg-attack, an attacker could replace blocks full of transactions with empty blocks, sending previously-confirmed transactions back into the mempools
4. In this scenario, anyone with a minimum of technical knowledge or access to public tools can opportunistically double-spend their transaction back to themselves.
5. We call an attack that aims to enable such widespread theft a Purge attack (as in the dystopian movie “The Purge”, where all crimes —including murder—are legal for one night every year.)
6. Purge attacks are an interesting form of sabotage attack that specifically tries to create discoordination incentives among Bitcoin users in dealing with the attack.

It all begins in the mempool.

1. The mempool

The mempool is a local database where each Bitcoin node stores valid transactions that wait to be included in the block.

Image: A mempool, Jochen Hoenicke

Nodes can see transactions in the network in different orders, so their view of unconfirmed transactions can differ from other nodes in the network. Bitcoin employs Nakamoto Consensus to synchronize the ledger state on all nodes, but strong consistency only kicks in after the first confirmations.

2. Fee bumping

Whenever users broadcast a transaction to the network, they participate in a first-price auction. By attaching a fee to their transaction, they hope miners will include it in a block. Rational miners tend to fill their blocks to the brim with the highest paying transactions because that gives them the most profit.

But unlike regular auctions, the blockspace market has a quirk: if a bid didn’t win the blockspace it was bidding for, it’s not withdrawn but automatically enters the next auction. That can be a big problem if the bid remains too low to be included, leaving the transaction (and the respective coins) stuck for a long time.

So users need a way to bump fees on an already published transaction. A useful side effect is that users can bid lower on their transaction fee rates because they always have the option to bump the fee later. That makes blockspace auctions more efficient.

Finally, fee bumping can be necessary to close payment channels, e.g. in the Lightning Network. Uncooperative closes have hard deadlines, and missing that deadline because of insufficient fees could result in a loss of funds for users.

Users can bump their transactions in three ways:

1. Child-Pays-For-Parent (CPFP)
2. Transaction accelerators
3. Replace-By-Fee (RBF)

We’ll briefly touch on the first two but then focus on Replace-By-Fee.

Child-Pays-For-Parent allows the receiving user to speed up a transaction if the sender has attached an insufficient fee. To do that, he broadcasts a secondary transaction that uses an output from the unconfirmed transaction as input and pays a larger-than-usual fee. If a miner wants the fee from the child transaction, whose validity depends on the inclusion of the parent transaction, he is now incentivized to include both. (For an example of a CPFP transaction, see here.)

Transaction accelerators are off-chain markets for confirming transactions that paid an insufficient fee in the on-chain market. These are typically offered by mining pools and exist in free as well as paid variants. A user can paste their transaction ID into the accelerator and then the mining pool will include it with higher priority. Since no signatures are necessary, they can be used by both the sender and the receiver, as well as anyone else (examples: ViaBTC and BTC.com.).

Image: ViaBTC’s transaction accelerator

3. Replacing transactions with RBF

Replace-By-Fee allows a user to create a replacement transaction that spends at least one of the same inputs as the stuck transaction but pays an additional fee. (If it spent none of the same inputs, it would be a separate transaction altogether.)

Apart from bumping the fee on a stuck transaction, transaction replacement is useful for power use-cases like iterative payment batching. While regular batching combines many payments into the same transaction and then publishes them, it’s equally possible to first publish a transaction and then iterate on the transaction by adding more inputs and outputs after it has been broadcast but before a miner has included it in a block.

Transaction replacement has a bit of an interesting history. While it was available in Bitcoin from the start, Satoshi later disabled it to close an attack vector on nodes in the network. A lack of rate-limiting allowed an attacker to flood the network with replacement transactions that did not even include a higher fee.

RBF was re-enabled in Bitcoin Core with Peter Todd’s BIP125 that solved both the spam-prevention and the incentive issues by requiring the replacement transaction to pay a higher fee than the original one.

However, the fact that it had been disabled in Bitcoin Core does not mean that RBF was not previously possible. RBF is a mempool policy that any node can choose for itself. It is completely unrelated to consensus rules.

Rational miners want to include the highest paying transactions, including replacement transactions, so it’s possible they had custom policies long before BIP125. To ensure they don’t miss any high-fee transactions, miners want to make sure they don’t cripple themselves by excluding transactions from their mempool that other miners include.

4. Impact on the safety of unconfirmed transactions

Replace-By-Fee has been a topic of contentious debate for years, between those who see unconfirmed (so-called “zero-conf”) transactions as inherently unsafe (One, Two, Three) and those who try to make them work anyway (Four, Five, Six). The latter group intends to make Bitcoin transactions faster so they can be used in commerce without the need for second layer technology.

How to double-spend with RBF? First, a user would make a transaction to a merchant who accepts zero-conf. After receiving the goods, they publish a second transaction that spends the same inputs to themself instead of to the merchant. Because it pays a higher fee to miners, the miner includes it in a block, making the previous transaction invalid.

The ability to replace one unconfirmed transaction with another plus the merchant’s willingness to accept unconfirmed transactions have allowed that user to double-spend, without controlling any hashrate at all. Users who want to double-spend generally have two options:

First, they can create a custom replacement transaction. I am not aware of a wallet that natively supports this, but savvy users can either write their own software or use one of many publicly available transaction construction tools and tutorials.

Image: A practical guide to crafting double-spend transactions with an open-source tool

Second, they can use a completely off-the-shelf wallet like Electrum with a bit of extra setup. In that case, the goal is to pay the merchant with a child transaction that spends the output of an unconfirmed parent transaction. After receiving the goods, the user can use RBF on the parent transaction to make the child invalid.

Given that practical guides for double-spending zero-conf transactions are widely available, how big is the problem in practice?

Bitcoin Cash is a network that actively encourages merchants to accept zero-conf transactions so their token can be used in commerce. doublespend.cash keeps track of successful and unsuccessful double-spend attempts. For December 2019, it counted 5500 attempted double-spends, of which roughly 900 (16%) have been successful.

Image: doublespend.cash keeps track of double-spend attempts on BCH.

So, in the grand scheme of things—BCH processes around ~1m transactions per month—double-spending is still very rare. While it is not clear how many of these transactions are with merchants, the problem does not seem prohibitive when compared to credit card fraud.

5. Can mempool policies prevent double-spending?

Replace-By-Fee is a policy that comes in a few different variants. One of them is First-Seen-Safe RBF, which requires the replacement transaction to spend to all the same outputs as the original transaction. Under this policy, double-spends are impossible because the original receiver still gets at least as much money as he did before.

However, recall that mempool policies are local in nature. Every miner can—and should—choose the policy that maximizes their own bottom line. So the effectiveness of this policy depends on how many miners adopt it voluntarily.

First-Seen-Safe also introduces new problems in non-double-spend scenarios, making it very unattractive in practice. Because all outputs are now seen as payments (how should the protocol know which payments are change?), they cannot be reduced into a slightly smaller output and a slightly higher fee. Instead, the user has to add an entirely new coin, which

• he might not have;
• increases the byte size of the transaction; and
• hurts privacy by linking more coins than necessary.

As a result, there is no way to prevent double-spends with RBF in the base scenario. Variants other than full RBF would have to be adopted by miners voluntarily, which is not incentive-compatible. Merchants can still accept zero-conf transactions and treat occasional double-spends as a cost of business—similar to credit card fraud today—but for any meaningful sum of money, they should wait for at least one confirmation.

6. Opportunistic double-spending

Most users and businesses in Bitcoin understand the risks of zero-conf transactions today. Those who use it anyway either trust their counterparty (because they are legally protected from theft) or accept the occasional theft as a cost of business. But what if there was an attack that allows anyone to double-spend their past transactions?

In a reorganization-attack, an attacker (typically—but not necessarily—with majority hashpower) replaces an existing blockchain with a heavier one. Since all nodes follow the heaviest chain, they switch to it automatically.

We have often talked about reorgs in the context of double-spends. In a double-spend attack, an attacker replaces one or several transactions from himself to a merchant with transactions from himself to himself.

What happens here technically is that the now-replaced transactions don’t just disappear, they go back into the waiting zone. Only in the case of a double-spend, the replaced transactions are no longer valid, because a new transaction has already spent their inputs. Thus, they are denied entry.

When an attacker replaces transactions without double-spending them, they stay valid and return to the mempool, where they can be picked up again by miners. So if you imagine an attacker who replaces the last 10 blocks full of transactions with empty blocks, then 10 blocks worth of transactions would return to the waiting zone.

Image: An attacker replaces the existing chain with a heavier, but empty chain. Previously confirmed transactions return to the mempool, where they can be double-spent by users.

If nothing else happens, these transactions eventually become part of the blockchain again. But in the meantime, a retroactive zero-conf policy is applied to the entire network.

Transactions that were previously confirmed and settled now have the same status as the deliberate zero-conf transactions we touched on earlier. As a result, users could double-spend any of these transactions the same way they could double-spend a regular zero-conf transaction – with the important difference that their counterparties did not prepare for this risk, so the stakes can be much, much higher.

I call such an attack a Purge attack because the attacker doesn’t (primarily) steal money himself, he makes theft legal in the network for a short period of time.

7. Introducing Purge attacks

When is a Purge attack a good idea?

I find unlikely we will see a Purge scenario in any attack where the attacker himself wants to double-spend. As more people are affected, both the range and likelihood of a response that is unfavorable for the attacker (e.g. manual rejection of a chain or even a PoW change) increases. For that reason, attackers who denominate their profits in BTC are incentivized to replay all unrelated transactions to prevent network disruption and the possibility of opportunistic double-spends.

It could, however, be an interesting form of sabotage attack, aiming to undermine trust in Bitcoin’s assurances e.g., the future finality of transactions. Possible attackers could include nation-states hostile to Bitcoin as well as terrorist organizations.

8. Purge attacks compared to other sabotage attacks

Image: A damaged tanker after a sabotage attack in the Gulf, AFP photo

The interesting part is how a Purge attack differs from other sabotage attacks like a full Denial-of-Service where an attacker mines only empty blocks. Sabotage attacks tend to cause a lot of collateral damage in a network, which many experts consider easier to deal with than less intrusive attacks.

Greg Maxwell, for example, has stated that he finds “[censorship] more concerning [than sabotage] because, since it targets a subset, it may be much harder to gain the political will to undertake a costly or risky fix […]”

Paul Sztorc has said that very intrusive attacks “would be a kind of “nuclear option” of mining, and [are] matched by the user’s nuclear option of changing the PoW algorithm. Because the miner’s option makes the network so unusable for users, users, in turn, have almost nothing to lose by changing the PoW. At least a PoW-change has a small chance of salvaging the network’s transaction-processing features.”

Both experts tend to give considerable thought to a concept called pre-coordination, which asks if the best response for defenders is a natural Schelling Point. If all users agree that a given response is necessary—e.g. a PoW change—then this option is easier to execute.

A Purge attack, other than a full DoS-attack, has the potential to disrupt that pre-coordination. By giving regular users a way to benefit from the destruction, the attacker creates discoordination in the community. As a result, there might be a less united front against the attacker, as any rollback of the chain would now require users to give up their double-spends.

You can imagine this as a way for the attacker to “pay off” a group of users and turning them into supporters. (Not unlike the mafia running a food bank in the neighborhood, or bank robbers throwing cash out the window of their flight car to win popular support.) This kind of alliance makes it harder for the honest users of the network to coordinate their response.

9. Preventing Purge attacks

The primary line of defense against Purge attacks is the same as against any other form of sabotage attack. Users want to maximize the amount of “forced damage” an attacker has to inflict on itself.

The self-damage is based on the amount of BTC-denominated assets on the attacker’s balance sheet. Given that mining operations are future block rewards pulled into the present, their market value is entirely based on the market value of the underlying Bitcoin network. An attack on the network would be an attack on their own balance sheet.

As a result, Bitcoin’s first wall of defense is the sum of its future block rewards. It represents the amount of money an attacker has to burn to sabotage Bitcoin. Experts currently disagree whether that wall of defense must be symmetric to Bitcoin’s network value or just high enough to discourage most attacks in practice.

Its second wall of defense is the strength of Bitcoin’s pre-coordination in the face of attack. A leaderless group of people can carry out an effective defense more easily if it is self-evident to most individuals what the right response ought to be.

Right after an attacker has released its empty chain, honest miners could also temporarily switch their mempool policy to prevent any double-spend attempts from entering. Depending on the price impact of each double-spend, they could decide to protect their long-term investment by leaving additional fees “on the table.” However, this assumes the attacker does not mine any user double-spend transactions himself, which may not hold in practice.

Finally, it’s not clear how many people would take up the attacker’s invitation to double-spend. Many transactions are additionally secured by legal recourse, repeat interactions between users and merchants, a lack of technical chops, or simply an unwillingness to steal. This is supported by the fact that more people could defraud merchants with credit card chargebacks at little risk to themselves, yet opt not to do it. On the other hand, even a small number of people can make a lot of noise if they are sufficiently motivated.

10. Conclusion

All in all, Purge attacks probably don’t constitute a bigger risk than other known forms of sabotage attacks, but represent an interesting spin where the attacker specifically targets the pre-coordination of defenders.

Virtually all attacks on cryptocurrencies so far had the goal to double-spend one or more miner transactions. In a double-spend attack, miners want to minimize collateral damage to minimize the risk of an unfavorable community response—the opposite of a sabotage attack.

There are two reasons why that might change in the future:

1. Cost: If the sum of future block rewards (sum of subsidy + fees) decreases, an attacker’s balance sheet could decrease.
2. Benefit: If Bitcoin grows in geopolitical importance, the incentive to sabotage the network could increase.

The further these two trends continue, the more attractive the cost/benefit ratio of sabotage attacks could become.