The Bitcoin vulnerability

Last month I wrote a ten-year retrospective of some of the ideas underlying the LOCKSS anti-entropy protocol in our SOSP paper, relating them to recent work on securing SSL communications. This month Ittay Eyal and Emin Gun Sirer (ES) published an important paper describing a vulnerability in Bitcoin. There are two similarities between this attack and the stealth modification attack we examined in that paper:

• The attack involves a conspiracy in which the members strategically switch between good and bad behavior. The defense involves randomizing the behavior of the peers. The general lesson is that predictable behavior by honest peers is often easy to exploit.
• The attack involves deploying an army of Sybil peers that appear legitimate but are actually under the control of the conspiracy. The defense involves making peer operations expensive using a proof-of-work technique. The general lesson is that peer reputations cheaply acquired are worth what they cost.

Follow me below the fold for the details.

One of the key ideas of the LOCKSS system was to decentralize custody of content to protect against powerful adversaries' attempts to modify it. Governments and other powerful actors have a long history of censorship and suppression of inconvenient content. A centralized archive system allows them to focus their legal, technical or economic power on a single target. One of the key ideas of the Bitcoin system was to decentralize control of a currency to protect against powerful adversaries' attempts to control and manipulate it. Governments and other powerful actors have a long history of manipulating currencies in their own interests.

The lack of a central locus of control provides peer-to-peer (P2P) systems such as Bitcoin and LOCKSS with robust defenses against many forms of attack that would succeed against a centralized system. Attackers are forced to conform to the basic structure of the P2P protocol, since that is their only way to get peers they don't control to do what the attackers want. Effective attacks require a conspiracy among a group of peers, and the goal of protocol design is to ensure that a successful conspiracy must involve a large proportion of the peer population.

In our paper we showed how a conspiracy of malign peers could attempt to modify the consensus of a network of LOCKSS boxes from a good to their preferred bad version of some content without being detected. The malign peers would communicate amongst themselves and strategically switch between voting with the good and bad versions of the content depending upon whether malign peers were a majority or a minority among the sample of peers included in polls called by loyal peers. The polls in which they are a majority allow them to convince the loyal peer to switch to the bad version. The probability of this attack succeeding rises the greater the proportion of malign peers in the total population.

In ES's attack on Bitcoin, malign peers similarly conspire to switch between concealing and revealing their activities, and thereby gain advantage over the loyal peers. How does their attack work? First, some background is needed [un-linked quotes from the ES paper]:

Central to Bitcoin’s operation is a global, public log, called the blockchain, that records all transactions between Bitcoin clients. The security of the blockchain is established by a chain of cryptographic puzzles, solved by a loosely-organized network of participants called miners. Each miner that successfully solves a cryptopuzzle is allowed to record a set of transactions, and to collect a reward in Bitcoins. The more mining power (resources) a miner applies, the better are its chances to solve the puzzle first. This reward structure provides an incentive for miners to contribute their resources to the system, and is essential to the currency’s decentralized nature.

Much of the attraction of Bitcoin as a currency lies in its decentralized nature and thus its supposed immunity to manipulation. The risk is:

By construction, if a set of colluding miners comes to command a majority of the mining power in the network, the currency stops being decentralized and becomes controlled by the colluding group. Such a group can, for example, prohibit certain transactions, or all of them.

Currently, the mining power in use is over 48*10¹⁸ FLOPS. The supercomputer currently ranked #1 is capable of nearly 34*10¹⁵ FLOPS, so an adversary would need over 700 of them to control the blockchain. Even though miners actually use custom silicon rather than general purpose computers, control would be a stretch even for a major government that saw Bitcoin as a threat.

It was believed that the Bitcoin protocol is incentive-compatible:

the best strategy of a rational minority pool is to be honest, and a minority of colluding miners cannot earn disproportionate benefits by deviating from the protocol

Thus in order to control the blockchain a conspiracy must involve a majority of the mining power, and thus reap a majority of the benfits. It is true that Bitcoin miners do form cooperating pools, whose members share the Bitcoins that are the reward for their joint effort. The reason is that a reward is delivered once every 10 minutes. Since there are a very large number of miners, each individual miner can expect a (rather large) reward only infrequently. It is rational for miners to join pools if they prefer, as most would, much smaller rewards much more frequently. Joining an honest pool does not increase the expected long-term reward; it does greatly reduce the variance of the expected reward in any reasonable time interval.

ES show that the Bitcoin protocol is not incentive-compatible by describing:

a strategy that can be used by a minority pool to obtain more revenue than the pool’s fair share, that is, more than its ratio of the total mining power.

They call the strategy Selfish-Mine. A malign pool needs to achieve a threshold fraction of the mining power to gain unfair rewards. Once it attains the threshold, it will continue to grow, because the reward for contributing mining power to it is greater than can be achieved by contributing power to an honest pool (see Fig. 2). Not merely that, but:

For a pool running the Selfish-Mine strategy, the revenue of each pool member increases with pool size for pools larger than the threshold.

Existing members have an incentive to recruit more. Once the malign pool grows to a majority of the mining power, it controls the blockchain and the currency is no longer decentralized; it is controlled by the malign pool manager. The threshold depends on a parameter, which the current protocol sets to 1. Fig. 3 shows the relationship between this parameter and the threshold size beyond which a malign pool gains unfair rewards. Currently:

a pool of any size can benefit by running Selfish-Mine.

The current protocol is thus unstable; any adoption of Selfish-Mine will result in loss of Bitcoin's decentralized nature:

Note that [this] does not immediately imply that the value of a Bitcoin drops to 0. The controlling entity will have an incentive to accept most transactions, if only to reap their fees, and because if it mines all Bitcoins, it has strong motivation that they maintain their value. An analysis of a Bitcoin monopolist’s behavior is beyond the scope of this paper, but we believe that a currency controlled by a single entity may deter many of Bitcoin’s clients.

Thus, all that a powerful actor would need to do to take control of the blockchain would be to allocate enough compute power to create a malign pool bigger that the threshold, then recruit miners to join it. These co-opted miners would provide the majority of the mining power needed for control.

The fix that ES propose is to randomize a choice that miners must make when they discover competing branches of the blockchain:

Specifically, when a miner learns of competing branches of the same length, it should propagate all of them, and choose which one to mine on uniformly at random.

instead of, as currently:

The Bitcoin protocol prescribes that when a miner knows of multiple branches of the same length, it mines and propagates only the first branch it received.

ES show that this change to the behavior of loyal clients raises the parameter value to 1/2, changing the minimum size at which a malign pool obtains unfair returns to 1/4 of the mining power. However:

The Bitcoin system [is] immune to Selfish-Mine if there are no pools above the threshold size. Since the threshold is near 0 with the current protocol, this is not the case. Miners who value the health of the currency should therefore immediately implement our suggested change to the Bitcoin protocol. However, even with our proposed fix that raises the threshold to 25%, the outlook is bleak: there already exist pools whose mining power exceeds the 25% threshold ... Miners should therefore break off from large pools until no pool exceeds the threshold size ... These measures must be taken immediately, since if at any time a single pool exceeds threshold it can execute Selfish-Mine, causing a phase transition where rational miners will want to join that pool, leading to a collapse.

Over the last 4 days, the BTC Guild had 30% and GHash.IO had 24% of the mining power.

Ed Felten argues that the same incentives that lead miners to join a malign pool will cause them to strategically defect from the pool when the private information that they have as members of the pool shows there is an opportunity to profit. Ed writes:

There is a certain poetic justice in this result. ES-miners plan to deviate from the normal agreement that miners should always mine the longest chain. They do this in the hope of extracting extra revenue. But the coalition of ES-miners is itself destroyed because its members secretly deviate from the ES-mining strategy. And the result is that the system returns to normal mining. ES-miners can’t agree to cheat, because it’s too easy for them to cheat on that agreement.

It seems to me that ES have anticipated a somewhat similar attack:

A possible line of defense against selfish mining pools is for counter-attackers to infiltrate selfish pools and to expose their secret blocks for the honest miners. However, selfish pool managers can selectively reveal blocks to subsets of the members in the pool, and quickly identify and expel nodes that leak information.

This isn't free. Selectivity would reduce the efficiency of the malign pool, and thus raise the threshold and reduce the benefits enjoyed by malign pool miners, but it isn't clear by how much in practice. And given that defectors can choose to leak when the malign pool has the greatest edge, the prospect of detection may not be enough to deter. See, for an analogous example, the case of the Wee Forest Folk that we cited in our SOSP paper.

In a subsequent post to the same blog, Arvind Narayanan and Andrew Miller focus on another aspect of the ES attack, its technique for biasing Bitcoin's messaging mechanism to their ends:

It is definitely possible to make the messaging layer of the network more resistant to Sybil attacks. ... Another possibility is to require that potential peer nodes solve a puzzle, similar to the proof-of-work mechanism used for mining rewards. The Bitcoin developers have been taking this issue seriously, and it is likely that they will quickly deploy defenses to shore up the P2P layer against attacks.

This is similar to "effort-balancing", another concept from our SOSP paper, in which we made the Sybil attack expensive by requiring enough proof-of-work to make requesting a vote from a peer more expensive than computing the requested vote.

The larger point is that P2P systems are often vulnerable to conspiracies that share information among the minority of malign peers, enabling them to make strategic choices that subvert the normal operation of the protocol so as to achieve malign goals. The ES attack on Bitcoin and the "stealth modification" attack in our SOSP paper are conspiracies of this kind. Randomizing the behavior of peers, as in the ES defense and the sampled voting technique of the SOSP paper, can be valuable in reducing the effectiveness with which the conspiracy can apply its secret knowledge.

Note that another, more directly economic threat to Bitcoin looms:

Another extreme block solve rate, leading to another ~ 50% increase in difficulty. I think most miners are going to have trouble making enough to pay for electricity soon.