Bitcoin isn’t so broken after all

There has been a lot of noise in the Bitcoin world this week about a new paper by Ittay Eyal and Emin Gun Sirer (“ES” for short) of Cornell, which claims that Bitcoin mining is vulnerable to attack. In a companion blog post, Sirer says unequivocally that “bitcoin is broken.” Let me explain why I disagree.

This post has three parts. First, I’ll give some necessary background on how Bitcoin works. Second, I’ll explain the essence of the ES attack. Third, I’ll explain a serious flaw in the logic of the ES paper and why, as a result, the ES attack is not nearly as scary as they indicate.

Part I: Bitcoin background

First, some necessary background on how Bitcoin works. Bitcoin relies on a public ledger that records all transactions in the system. The ledger is represented in a public data structure called the block chain which (as the name implies) is a chain of blocks, each block containing a bunch of transactions along with a link to the previous block in the chain. If you have the block at the end of the chain (i.e. the newest block in the chain), then you can follow the chain backward to the beginning of Bitcoin history, giving you a complete record of all transactions that have ever occurred. (There is some cryptographic verification of blocks.)

New blocks are created by mining, a process in which participants (“miners”) race to solve cryptographic search problems. Whoever solves the search problem first gets to create a new block. As a reward, the winning miner gets to add to the new block a special transaction that pays 25 new Bitcoins (worth about $6500 at current exchange rates) to himself. These mining rewards create an incentive for people to spend resources on mining.

Although I have spoken of a block “chain,” the chain can have branch points (or “forks”) where a single block has two (or more) blocks that claim to come after it in the chain. By convention, whenever there are two branches of a fork to choose from, participants treat the longest branch as the authoritative one. Shorter branches are ignored. Notice that miners have an incentive to try to extend the branch that will end up being longest, because they want their 25 Bitcoin mining rewards to be on the authoritative chain. (A miner who extends a losing branch will find his “reward” worthless because transactions not on the authoritative chain are ignored.)

It has long been known that if a single miner (or a coordinated cartel) controls more than half of the total mining power, then they can be a mining “dictator” and any branch they choose will eventually become the authoritative one, because the dictator, having more mining capacity than everyone else combined, can add new blocks to their chosen branch so fast that no other branch can keep up. But, short of this “51% attack” the conventional wisdom has been that miners’ incentive is to always try to extend the longest branch. (Josh Kroll, Ian Davey, and I published a paper examining this claim and concluding that things are a bit more complicated; but the differences won’t matter for us here.)

Part 2: The ES attack

With that background in place, let’s look at the argument made in the ES paper. (For brevity, I’ll talk about the case they call gamma=0, but my analysis extends to the other cases as well.) ES describe a mining strategy, which I’ll call ES-mining, and they argue that an ES-miner, or a cartel of ES-miners, who control more than 33.3% of mining power can capture a disproportionate share of the mining rewards.

Essentially, ES-miners engage in a series of races against the ordinary miners. The ES-miners build a secret chain of blocks which they hope will grow longer than the ordinary block chain. If it does get longer, then the ES-miners can publish their (previously secret) chain, and it will become authoritative. In the race, the ES-miners have the disadvantage that they have (by assumption) less mining power than the ordinary miners; but the ES-miners have the advantage of knowing how long their secret chain is. By cleverly choosing when to end the race (either by winning or by abandoning the secret chain and restarting the race from the current end-of-chain), the ES-miners create a situation where the block chain sometimes forks causing blocks to be left behind on a losing branch (or “orphaned”), but it turns out that a block made by an ES-miner is less likely to be orphaned than one made by an ordinary miner. The result is that ES-miners have a disproportionate share of their blocks survive in the long-run authoritative chain, therefore they get a disproportionate share of the mining reward. (See the ES paper if you want more details.)

Part 3: Flaws in the ES Analysis

The analysis in the ES paper has some flaws. The most serious flaw, perhaps, is that, contrary to their claims, a coalition of ES-miners would not be stable, because members of the coalition would have an incentive to cheat on their coalition partners, by using a strategy that I’ll call fair-weather mining.

Recall that in the ES attack, a team of ES-miners is racing against a team of ordinary miners, to see who can create a longer block chain. A fair-weather miner pretends to be part of the coalition of ES-miners, but in fact secretly switches teams so that mines for the ES-mining team if that team is ahead in the race, and it mines for the ordinary mining team otherwise. It turns out that every block that the fair-weather miner creates is guaranteed to end up on the winning chain. So the fair-weather miner does better (i.e. gets a better reward) than it could get by playing exclusively on either team.

Because a fair-weather miner always gets a better reward than an ES-miner, every member of an ES-mining team will have an incentive to switch over to fair-weather mining. As a result, a coalition of ES-miners is not stable. In short, a coalition of ES-miners cannot form and will not survive.

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.

There’s a lot more to say about the ES paper, and I’ll probably have more posts about it. For one thing, even if a coalition of ES-miners isn’t possible, can a single ES-miner do damage? Such questions will have to wait—this is already the longest post ever on Freedom to Tinker.