Tuesday, June 15, 2021

Mempool Flooding

In Unstoppable Code? I discussed Joe Kelly's suggestion for how governments might make it impossible to transact Bitcoin by mounting a 51% attack using seized mining rigs. That's not the only way to achieve the same result, so below the fold I discuss an alternative approach that could be used alone or in combination with Kelly's concept.

The Lifecycle Of The Transaction

The goal is to prevent transactions in a cryptocurrency based on a permissionless blockchain. We need to understand how transactions are supposed to work in order to establish their attack surface:
  • Transactions transfer cryptocurrency between inputs and outputs identified by public keys (or typically hashes of the keys).
  • The input creates a proposed transaction specifying the amount for each output, and a miner fee, then signs it with their private key.
  • The proposed transaction is broadcast to the mining pools, typically by what amounts to a Gossip Protocol.
  • Mining pools validate the proposed transactions they receive and add them to a database of proposed transactions, typically called the "mempool".
  • When a mining pool starts trying to mine a block, they choose some of the transactions from their mempool to include in it. Typically, they choose transactions (or sets of dependent transactions) that yield the highest fee should their block win.
  • Once a transaction is included in a winning block, or more realistically in a sequence of winning blocks, it is final.

Attack Surface

My analysis of the transaction lifecycle's attack surface may well not be complete, but here goes:
  • The security of funds before a proposed transaction depends upon the private key remaining secret. The DarkSide ransomware group lost part of their takings from the Colonial Pipeline compromise because the FBI knew the private key of one of their wallets.
  • The gossip protocol makes proposed transactions public. A public "order book" is necessary because the whole point of a permissionless blockchain is to avoid the need for trust between particpants. This leads to the endemic front-running I discussed in The Order Flow, and which Naz automated (see How to Front-run in Ethereum).
  • The gossip protocol is identifiable traffic, which ISPs could be required to block.
  • The limited blocksize and fixed block time limit the rate at which transactions can leave the mempool. Thus when the transaction demand exceeds this rate the mempool will grow. Mining pools have limited storage for their mempools. When the limit is reached mining pools will drop less-profitable transactions from their mempools. Like any network service backed by a limited resource, the mempool is vulnerable to a Distributed Denial of Service (DDoS) attack.
  • Each mining pool is free to choose transactions to include in the blocks they try to mine at will. Thus a transaction need not appear in the mempool to be included in a block. For example, mining pools' own transactions or those of their friends could avoid the mempool, the equivalent of "dark pools" in equity markets.
  • Once a transaction is included in a mined block, it is vulnerable to a 51% attack.

Flooding The Mempool

Source
Lets focus on the idea of DDoS-ing the mempool. As John Lewis of the Bank of England wrote in 2018's The seven deadly paradoxes of cryptocurrency:
Bitcoin has an estimated maximum of 7 transactions per second vs 24,000 for visa. More transactions competing to get processed creates logjams and delays. Transaction fees have to rise in order to eliminate the excess demand. So Bitcoin’s high transaction cost problem gets worse, not better, as transaction demand expands.
Worse, pending transactions are in a blind auction to be included in the next block. Because users don't know how much to bid to be included, they either overpay, or suffer a long delay or possibly fail completely. The graph shows this effect in practice. As the price of Bitcoin crashed on May 18th and HODL-ers rushed to sell, the average fee per transaction spiked to over $60.

The goal of the attack is to make victims' transactions rare, slow and extremely expensive by flooding the mempool with attackers' transactions. Cryptocurrencies have no intrinsic value, their value is determined by what the greater fool will pay. If HODL-ers find it difficult and expensive to unload their HODL-ings, and traders find it difficult and expensive to trade, the "price" of the currency will decrease. This attack isn't theoretical, it has already been tried. For example, in June 2018 Bitcoin Exchange Guide reported:
What appears to be happening is a bunch (possibly super spam) of 1 satoshi transactions (smallest unit in bitcoin) which will put a decent stress test if sustained. Some are saying near 4,500 spam transactions and counting.
This is obviously not an effective attack. There is no incentive for the mining pools to prefer tiny unprofitable transactions over normal user transactions. Unless it were combined with a 51% attack, an effective flooding attack needs to incentivize mining pools who are not part of the attack to prefer the attackers' transactions to those of victims. The only way to do this is to make the attacker's transactions more profitable, which means they have to come with large fees.

If a major government wanted to mount a flooding attack on, for example, Bitcoin they would need a lot of Bitcoin as ammunition. Fortunately, at least the US government has seized hundreds of millions of dollars of cryptocurrencies:
Mr. Raimondi of the Justice Department said the Colonial Pipeline ransom seizure was the latest sting operation by federal prosecutors to recoup illicitly gained cryptocurrency. He said the department has made “many seizures, in the hundreds of millions of dollars, from unhosted cryptocurrency wallets” used for criminal activity.
If they needed more, they could always hack one of the numerous vulnerable exchanges.

With this ammunition the government could generate huge numbers of one-time addresses and huge numbers of valid transactions among them with fees large enough to give them priority. The result would be to bid up the Bitcoin fee necessary for victim transactions to get included in blocks. It would be hard for mining pools to identify the attackers' transactions, as they would be valid and between unidentifiable addresses. As the attack continued this would ensure that:
  • The minimum size of economically feasible transactions would increase, restricting trading to larger and larger HODL-ers, or to exchanges.
  • The visible fact that Bitcoin was under sustained, powerful attack would cause HODL-ers to sell for fiat or other cryptocurrencies. This would depress the "price" of Bitcoin, as the exchanges would understand the risk that the attack would continue and further depress the price.
  • Mining pools, despite receiving their normal rewards plus increased fees in Bitcoin, would suffer reduction of their income in fiat terms.
  • Further, the mining pools need transactions to convert their rewards and fees to fiat to pay for power, etc. With transactions scarce and expensive, and reduced fiat income, the hash rate would decline, making a 51% attack easier.

How Feasible Are Flooding Attacks?

Back on May 18th, as the Bitcoin "price" crashed to $30K, its blockchain was congested and average fees spiked to $60. Clearly, the distribution of fees would have been very skewed, with a few fees well above $60 and most well below; the median fee was around $26. Fees are measured in Satoshi, 10-8 of a BTC, so at that time the average fee was 60 / 3*104 BTC or 2*105 Satoshi. Lets assume that ensuring that no transactions with less than 2*105 Satoshi as a fee succeed is enough to keep the blockchain congested.

Lets assume that when the Feds claim to have seized hundreds of millions of dollars of cryptocurrencies they mean $5*108 or 5*108/3*104 BTC or 1.67*1012 Satoshi. That would be enough to pay the 2*105 Satoshi for 6*107 transactions. At 6 transaction/second that would keep the blockchain congested for nearly 116 days or nearly 4 months. In practice, the attack would last much longer, since the attackers could dynamically adjust the fees they paid to keep the blockchain congested as, inevitably, the demand for transactions from victims declined as they realised it was futile.

Ensuring that almost no victim transactions succeeded for 4 months would definitely greatly reduce the BTC "price". Thus the 16,700 BTC the mining pools would have earned in fees, plus the 104,400 BTC they would have earned in block rewards during that time would be worth much less than the $3.6B they would represent at a $30K "price". Funding the mining pools is a downside of this attack, but the increment is only about 14% in BTC terms, so likely to be swamped by the decrease in fiat terms.

Potential Defenses

Blockchain advocates argue that one of the benefits of the decentralization they claim for the technology is "censorship resistance". This is a problem for them because defending against a mempool flooding attack requires censorship. The mining pools need to identify and censor (i.e. drop) the attackers' transactions. Fortunately for the advocates, the technology is not actually decentralized (3-4 mining pools have dominated the hash rate for the last 7 years), so does not actually provide "censorship resistance". The pools could easily conspire to implement the necessary censorship. Unfortunately for the advocates, the attackers would be flooding with valid transactions offering large fees, so the pools would find it hard to, and not be motivated to, selectively drop them.

16,700 BTC is only about half of Tesla's HODL-ings, so it would be possible for a whale, or a group of whales, to attempt to raise the cost of the attack, or equivalently reduce its duration, by mounting a simultaneous flood themselves. The attackers would respond by reducing their flood, since the whales were doing their job for them. This would be expensive for the whales and wouldn't be an effective defense.

Since it is possible for mining pools to include transactions in blocks they mine, and the attack would render the mempool effectively useless, one result of the attack would be to force exchanges and whales to establish "dark pool" type direct connections to the mining pools, allowing the mining pools to ignore the mempool and process transactions only from trusted addresses. This would destroy the "decentralized" myth, completing the transition of the blockchain into a permissioned one run by the pools, and make legal attacks on the exchanges an effective weapon. Also, the mining pools would be vulnerable to government-controlled "trojan horse" exchanges, as the bad guys were to ANOM encrypted messaging.

Conclusion

If my analysis is correct, if would be feasible for a major government to mount a mempool flooding attack that would seriously disrupt, but not totally destroy Bitcoin and, by extension other cryptocurrencies. The attack would amplify the effect of using seized mining power as I discussed on Unstoppable Code?. Interestingly, the mempool flooding attack is effective irrespective of the consensus mechanism underlying the cryptocurrency. It depends only upon a public means of submitting transactions.

No comments: