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.
Even though blocks are not fungible, the ES strategy is still unstable. In the paper they only address the situation with one dishonest pool, but someone could use the dishonest pool’s strategy against the dishonest pool, hiding blocks from them until the right time. What’s good for the goose is good for the gander.
You say that Fair-weather miner dominates versus ES-miner, because the Fair-weather can choose to switch from one group (ES-miner) or the ordinary miners. This strategy dominates because ES-miners exist. If ES-miners don’t exist, and you can only choose to be ordinary, then you earn less than trying to be ES-miner.
Ergo, neither is stable a coalition of ES-miners, nor it’s stable a coalition of ordinary miners. Conclusion: the protocol is yet unstable.
Ed and all proponents of Bitcoin; I would have to say Bitcoin is VERY BROKEN! But by design. Everything you said here about how Bitcoin works tells me it doesn’t work. It would not be a monetary system that I would want to participate in. I already had many doubts myself; but to learn in this article that a person’s mining efforts can simply be “ignored” and are worthless simply because someone else can mine bigger or faster is ridiculous.
If one goes back to the gold standard to compare mining; if I am a single miner that happens upon just even one nugget of gold; that gold is still valued equal in weight as a group of miners that have equipment that can mine traces of gold from the earth and smelt it together to create bricks of gold far outweighing my own. By my own nugget retains it’s value, it doesn’t just simply be “ignored” because someone else can mine faster than me.
Regardless if the ES-attack works or not; the system is totally broken if some people get left with nothing simply because someone else did more. That is a monetary system that would impoverish the 99.9999% instead of just the 99% that the U.S. Economy is already working to impoverish.
Further analogy. If I am a gold miner and yet I come across a diamond, that diamond itself isn’t worthless even if the entire rest of the mining world is only mining for gold. Can one even choose which “block” they are mining on, and be able to tell which “chain” is the longest?
Whether one can “choose” the block they are on I don’t know, but from other things I have read it appears by some factor miners end up on the wrong fork without a “choice” in the matter. It seems to me that they would suffer for naught. You mentioned the idea of forks before and while my mind can’t remember the detail but I do remember having many concerns about the idea of forks; but to learn that all forks are just discarded makes no sense to me at all.
Perhaps I am just not a “scientist” and just don’t understand this whole idea, but everything I read about Bitcoin just makes me want to stay far far away.
Someone told me that you (Felten) claimed somewhere that honest mining could only be a focal point, but not a unique dynamic equilibrium. This is right.
It is the same as the dynamic nuclear game. War and peace are both subgame perfect equilibria. That doesn’t mean that they are equally likely.
Yes, that’s in a paper by Josh Kroll, Ian Davey, and me, from the 2013 Workshop on Economics of Information Security. http://www.weis2013.econinfosec.org/papers/KrollDaveyFeltenWEIS2013.pdf
Do you have any comment on the dynamic game issue?
The fact that Eyal and Sirer have modeled this as a one-off game rather than as repeated play is quite remarkable. The condition for a repeated game is that the same individuals play the game more than once. This is clearly satisfied here. The set of participating miners does not change substantially each day, week, or even month. Under the repeated game scenario, cooperation is clearly a subgame perfect equilibrium.
In economics, my own field, the authors’ modelling decision would not be acceptable. We have a generally agreed upon framework for handling games where participants hold iliquid capital equipment, so the problem is quite familiar.
If I was to highlight the results in the dynamic game on arxiv would anyone care? My concern is that computer scientists would see this as a subjective modelling choice. Economists would see this as an unambiguous error.
I expected everyone to jump on this error immediately, but it didn’t happen. Would computer scientists see this as a subjective modelling choice? My guess is that computer scientists do not usually think about games where participants hold capital goods that can fluctuate in value. So what is obvious for me, may be non-obvious for computer scientists.
Is it worthwhile posting a formal comment on this paper? I believe that ES perceive me as a disciplinary outsider and thus unworthy of response. In particular they have nothing obvious to gain from responding to me. How could I best voice my concerns about their research?
Do you understand what I am saying? I am worried that it may be too difficult to communicate economic concepts to computer scientists.
Feel free to delete my comment above. I have yet to actually have a computer scientist respond to anything I say, so I have become quite irate. I would really like your help in this matter.
Cunicula, I feel your pain. The nice thing about this forum is they even usually retain rants and do not moderate them out (perhaps taking out obvious trolls from time to time), but yet, I too write quite commonly and really never see a response even to my direct questions.
No matter, at least it is likely other readers are reading whether the authors respond or not. I have found that the authors on this forum usually respond to people who of a like-minded about education. [That is, at one point I did receive a response from Ed, until I ranted about why I felt college was really not all it was cracked-up to be [realizing my post would be frowned upon by a Princeton group (CITP)]; and since then I can’t remember a response from Ed or any other author on here.] But my mind is just as valid as any “college grad” in my analysis of facts that I know and the experiences I have.
You are an economist you say? I am a computer specialist have very little knowledge about economy but I do have a good knowledge of personal economics (personal finance) and the games of the financial world. I am also no where near a “scientist” so my knowledge of computers is not scientific in thought, but analytical in actual functionality. Hence I couldn’t answer your question as to how Computer Scientists would see your argument for a dynamic and repeated play model; and would be pleasantly surprised to see Ed respond.
But, in my own analysis putting my experience and knowledge together and really the whole Bitcoin thing to me makes no sense at all; except that perhaps it “[Is] simply a game for rich young boys to play[.]”
And framing in the analogy of game play I respond to your comment on games and strategy: I think I understand your perspective. The ES authors [or rather I didn’t read their paper this time, so I should clarify, my understanding of Ed’s understanding of the ES authors] apparently chose to present that one could play the Bitcoin mining game by secretly building their own tower and then at the right time unveil their accomplishment of a higher tower steeling the thunder as well as the validity of the other team’s tower and thus causing everyone to move to their tower [but then they seem to leave off everything after that]. Ed suggests why the team members on ES wouldn’t stay on the team in the first place. And other commentators on here all seem to make it about a tower building game.
You come from the perspective of a chess game rather than a tower building game, that of recognizing that the game is played with strategy and played many times over and over. At least that is what I take from the talk of “one-off” compared to “dynamic” and “repeated play.”
My experience not being in economics or computer science, but in how games are played, and I too would think that a chess (dynamic, repeated play) game would make more sense as a model to frame the idea of it being hackable by distinguishing teams. However, I can’t say that is true for Bitcoin, because this article especially but also other things I have read about Bitcoin appears more to be a tower building game than a chess game (where there is one main tower, and any other towers that happen along the way [unless they can grow bigger than the main tower] mean nothing–and hence it is only a single team game unless someone hacks it); and as such it’s a game I wouldn’t want to play. Now chess is a game I like to play; and if the Bitcoin mining game was more like chess than towers, I would bet your analysis a much better one than ES or anyone commenting on ES for or against their ideas.
But it all depends on the game that is really being played, and Bitcoin may not be a game of economics [your field] despite it purporting to be a monetary system; but I question (as I quoted) “Is it simply a game for rich young boys to play?” It appears Bitcoin and it’s associated “mining” isn’t about economics at all; but it is about computer scientists new idea of a way to create a belief in money [see one of Ed’s earliest posts on Bitcoin], and hence funnel power of money to themselves. Thus making it not a game of economics, but a game of power.
Here is some insight. The authors of this paper are unfamiliar with dynamic games.
They analyze bitcoin as a one-off game.
Analyze nuclear war as a one-off simultaneous move game and you get world destruction as the only possible result.
Analyze a setting where people have repeated opportunities to launch nukes at each other and you get world peace as the most likely result. (Though war is still a possible equilibrium.)
Why the difference? Once the game is played over and over again, retaliation becomes a threat. You can now use “If you hit me, then I will hit you back.” as a strategy. This is retaliation.
The ignorant computer scientists behind this so-called research do not allow for retaliation as a strategy. They assume that you cannot play strategies like “If you hit me, then I will hit you back.” Instead you have to pick between “I will always hit people” or “I will never hit people.” That I will always hit people is the better of these to options comes as no surprise.
If these bozos were running the world we would have seen a nuclear winter long ago. All because of a mathematical error, LOL.
If you want some notes on how the problem is done properly, see below.
http://www.scribd.com/doc/1823…
Looks like the authors respond to the idea of a defecting selfish miner by stating that such a strategy could be prevented by not giving out solved blocks to the selfish miners, only hashes?
Jim,
They do make that argument, but they don’t explain why that would change the bottom-line result of my analysis. In fact, paying for work in the usual way that pools do, rather than giving rewards for finding blocks, doesn’t change the result of my analysis.
To begin I am novice to this topic. First, this just sounds like an issue for miners so what difference does it make for the currency? Or could they cancel transactions retroactively? Next the real issue does not have to do with profit but possibility. Is this possible because there is another group called the FED a private bank that also ‘mines’ 85 billion dollars a month and they have an incentive to engage in this attack if it destroys bitcoin.
I don’t see how fair-weather mining is feasible.
“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.”
Successful blocks are not fungible; they pay out to a specific pool. A pool participant works on hashes for a specific pool, and they generally receive a share of the award proportional to the work they’ve done for that pool. Without that property, mining pools as they operate today could not work; anyone who found a block would simply hoard it and not share the block’s 25 BTC with the rest of the pool.
A miner can certainly split its mining effort between two pools, ES and ordinary. It can even switch its effort around dynamically according to who is ahead. But even so, the miner’s expected payout is proportional to the work it has done for each pool. Intuitively, such a miner can be modeled as two separate participants, one on the ES team and one on the ordinary team.
If the ES team is large enough to have an unfair expected return, then a fair-weather miner will see more benefit from the work he does for the ES pool than from the work he does for the ordinary pool. His incentive is to put all his work into the ES pool.
Patrick,
There is another possibility: the fair-weather miner can mine blocks for himself (without a pool) when he is doing ordinary mining. If he does this, while getting an effort-based payout when he is mining on the ES side, he still comes out ahead.
Dear Ed,
You mention “another possibility”, that the fair-weather miner could potentially use some resources to mine for themselves and that they potentially can still come out ahead. However, this break away block’s reward would be addressed to the fairweather miner, and it would only be in their incentive to work at the end of the pool block chain which may not be publicly released yet. By the time the fairweather miner’s block is ready to be released, it would have been subsequently been superceded by more blocks in the hidden pool’s chain. These blocks would nullify the reward that the fair-weather miner had attributed to himself… and thus eradicating his incentive to break away from the selfish pool.
This is ignoring Gordon Mohr’s comments that the miners in the pool could be required to share proof of attempt information to keep them in rank and file.
Best regards
Daniel.
No honor among thieves…
Cartel members have a propensity to cheat. A cartel, if successful raises the price of its product, simultaneously increasing the incentive to cheat. OPEC members have been guilty of this for decades.
I don’t know if fair-weather mining is technically possible but the psychology is spot on.
Great/concise explanation. So the question now is, can the ES-pool construct a payout scheme (that’s not solely-dependent on hashes contributed, but also when it was contributed) such that it is more profitable to mine on the ES pool than the ordinary pools during the period when ES is not ahead.
For example, if I were a ES pool owner, I wouldn’t give the rewards for the 1st hidden block to the extra hashrate contributed after that block was found.
mrkent,
You can try to devise an algorithm that works. Whether that is possible, and whether the honest miners would then have a counter-counter-measure that frustrates your new algorithm, remain to be seen. But in any case, it’s clear that ES-mining is not a dominant strategy—contrary to the ES paper’s claim.
Correction: If the ES pool only provides getwork(), a miner can’t fair-weather mine.
If the ES pool uses getblocktemplate(), a fair weather miner can know whether the ES pool is ahead or not, and use that knowledge to fairweather mine.
But also, the ES-cartel will demand its members supply near-answers (“shares”) just as with other pools, which prove the members’ relative contribution to the cartel’s preferred problem. So a cartel-member can’t really fair-weather mine: they are constantly proving their participation, in order to remain a proportionate pool/cartel-member.
I think there is another huge problem: detectability.
There are two major cases: the ES pool gets a block and no lead, so it releases its block when it sees the normal miners get a block (relying on a fast broadcast so it wins the race with the non ES block), and the ES pool gets a lead and releases when its lead is almost challenged.
The first case the ES blocks are easily rejected unless the ES miner also controls a huge amount of the Bitcoin block broadcast network, enough to block or greatly slow the population of non-ES miner blocks (not just speed ITS block):
Since the blocks have timestamps, the other pool servers, rather than choosing the first-block seen in a conflict, or choosing randomly (ES’s suggestion), the other pool servers look at the delta between the block’s timestamp and when it arrived, and use the shortest delta between block timestamp and arrival when two block arrive in close succession, which with very high probability means rejecting the ES block.
Thus unless the ES server gets a 2 block lead out of the gate, their work is wasted. So a ES miner needs a significant fraction of mining power to even TRY this attack with “chose lowest delta” operating on the other pool servers.
The second case is that the ES server gets a 2 block lead, and attempts to maintain it until the public is close to catching up. Publishing this will require broadcasting SEVERAL ‘stale’ blocks, where the received time is very different (~10 minutes) from the timestamp in the block. Blockchain.info and other P2P monitors will quickly see and record this. You can’t stealthily ES mine.
And far from rational miners joining an ES pool, rational miners socially are likely to REJECT the ES pool. An ES pool represents a direct threat to Bitcoin, and therefore any ‘gain’ by mining with the ES pool’s greater payout are offset by the probability that an ES mining pool destroys the value of BitCoin altogether.
Although the fair weather strategy doesn’t work: A miner working on a pool server doesn’t actually have sufficient information to determine whether the ES pool or a normal pool is ahead, since the Getwork() protocol gives just a hash to generate a collision on, you can’t tell what block you are actually working on.
Gavin Andreesen (lead Bitcoin developer) on the same topic:
https://bitcoinfoundation.org/blog/?p=310