Tuesday, November 12, 2013

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*1018 FLOPS. The supercomputer currently ranked #1 is capable of nearly 34*1015 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.


Nick Krabbenhoeft said...

This is just a thought, but is there a possibility of adapting the ASIC mining hardware for running checksums for LOCKSS boxes and other digital preservation checksumming activities? And would it relate to the FAWN arrays you've been talking about. I'm still trying to wrap my head around this space.

David. said...

At 3AM today Ghash.io had 45% of the mining power. It was dangerously close to a majority, and amply enough to execute the attack described above even with the proposed fix. 7 hours later it was down to 38%, presumably because miners left in response to the news. But equally, this shows that a flash mob could easily be arranged to get Ghash.io to a majority of the mining power and control in a very short time.

David. said...

Nick, sorry this response fell through the cracks.

Absent an architecture like DAWN, the constraint on integrity checking is normally I/O bandwidth, which Bitcoin mining hardware would not help, rather than hash speed, which it presumably would.

David. said...

Aaron Sankin at the Daily Dot has an accessible discussion of the history of Bitcoin mining.

David. said...

A Bitcoin vulnerability called Transaction Malleability identified in 2011 last week turned into a big problem when it was discovered that Mt. Gox, the leading Bitcoin exchange, had not applied the necessary defenses. Andreas Antonopoulos at O'Reilly praised the community's response as an example.

"While the exchanges resumed operations, they did so with systems strengthened against this and variants of this type of attack. The attack continued but the systems were no longer vulnerable to fraud or even delays from the confusing traffic. In essence, the entire ecosystem of bitcoin exchanges just got a bit more resilient, a bit more robust and a bit more resistant to attacks. Bitcoin demonstrated anti-fragility.

There will be more nuisance attacks. During each attack, the media will confuse access for trust and write hyperbolic headlines proclaiming the end of the currency. Soon after, the bitcoin network and ancillary services will learn, adapt, thwart and become more resilient. Like the Internet, over time, crypto-currency networks such as bitcoin will get stronger and stronger, as each attack increases resilience by training the distributed immune system of an anti-fragile network."

However, he may be too optimistic. First, there is a botnet in the wild called Pony that has stolen 700K credentials for digital currencies, including Bitcoin.

Second, Mt. Gox has shut down, trapping user's Bitcoins and the Japanese authorities are refusing to intervene. There are suggestions that "744,408 BTC are missing due to malleability-related theft which went unnoticed for several years". That's over $350M if you believe current exchange rates.

David. said...

Another exchange is attacked, $610K in Bitcoins stolen, the exchange bankrupted. Customers should have read "Flexcoin's Terms of Service page, which notes that the company (what's left of it) is not liable for lost Bitcoin."

Apparently, Mt.Gox lost about $450M in Bitcoin and owes $63.8M in old-fashioned money.

David. said...

Ben Thompson has an interesting post which ends up talking about the externalities of the relentless push for more compute power for Bitcoin mining.

He writes: "which ultimately means Bitcoin effectively uses electricity as a release valve for inflation, compounding the externalities that accompany power production. For what it’s worth, the structure of Bitcoin dictates that the price continue to rise, presuming it remains a viable currency. That price, though, is not free, and no one asked me if I were willing to pay."

David. said...

The prediction at the end of the post is coming true. Bloomberg reports:

"Drawn by the virtual currency’s jump in value last year, digital prospectors have turned the mining industry into an arms race as they buy expensive computing equipment and gobble up electricity. While that worked well as long as bitcoin’s value kept rising, smaller players are now being crowded out by bigger competition, high utility bills and declining prices."

Gradually, the economies of scale you need to make money mining Bitcoin are concentrating mining power in fewer and fewer hands. I believe this centralizing tendency is a fundamental problem for all incentive-compatible P2P networks, but given the ES vulnerability, it is a real problem for Bitcoin. After all, the decentralized, distributed nature of Bitcoin was supposed to be its most attractive feature.

David. said...

More on the need for custom mining hardware from Simon Rockman at The Register.

David. said...

Defenses against the Selfish-Mine attack have become somewhat beside the point, as Ghash.io has, for extended periods of time, has had an absolute majority of the network's hashing power. The prediction in this comment above came true. So, the idea that Bitcoin is a decentralized currency is no long valid. It is a currency controlled by the people behind Ghash.io.