Joint post with Andrew Miller, University of Maryland.
Bitcoin is broken, claims a new paper by Cornell researchers Ittay Eyal and Emin Gun Sirer. No it isn’t, respond Bitcoiners. Yes it is, say the authors. Our own Ed Felten weighed in with a detailed analysis, refuting the paper’s claim that a coalition of “selfish miners” will grow in size until it controls the whole currency. But this has been disputed as well.
In other words, the jury is still out. But something has been lost in all the noise about the grandiose statements — on their way to getting to their strong claim, the authors make a weaker and much more defensible argument, namely that selfish miners can earn more than their fair share of mining revenue. This is in fact a novel and interesting result, with potentially serious consequences.
The well-known argument — never proven, but taken on intuitive faith — that a minority of miners can’t control the network is a special case of a more general assumption: that a coalition of miners with X% of the network’s hash power can make no more than X% of total mining revenues. Eyal and Sirer argue that this is false [1].
If X% is more than 1/3, the authors’ argument is self-contained and relatively easily verifiable, and we believe that it will hold up to scrutiny [2]. This is already a concern, but maybe it’s hard for deviant mining coalitions of such size to materialize. Things get more interesting when X% is less than a third. Here the argument for the deviant strategy relies on the attacker having a good “network position:” running a large number of Bitcoin nodes that flood the peer-to-peer messaging layer and manage to fool honest nodes about what the attacker is trying to do.
Here’s the thing: this is the first time a serious issue with Bitcoin’s consensus mechanism has exploited the peer-to-peer aspect of the system. This is a problem for our ability to reason about Bitcoin. The cryptography in Bitcoin is considered solid. We also have some ability to model and write equations about miners’ incentives and behavior. Based on this, we thought we had strong reasons to believe that “X% of miners can earn no more than X% of mining revenue.”
But if network position can make a difference to the attacker’s prospects, all such bets are off. Weaknesses that depend on the attacker creating “sybil” nodes in the network are in a very different category. Bitcoin’s P2P network is “open to the public.” Nodes can come and go as they please, and are not expected to identify themselves. Running a Bitcoin node means being willing to accept connections from strangers. This makes it problematic to apply existing theoretical models to analyze the security of Bitcoin.
It is definitely possible to make the messaging layer of the network more resistant to Sybil attacks. First, Bitcoin allows users to declare other nodes as trusted, effectively forming a “friendnet“, if they were willing to take the effort to do so. Another possibility is to require that potential peer nodes solve a puzzle, similar to the proof-of-work mechanism used for mining rewards [3]. 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.
The security of Bitcoin is frequently portrayed as cryptographic in nature, and economic arguments are sometimes invoked. But so far, a third factor has proven to be at least as important: the responsiveness of the developer community. Perhaps in the future, the theoretical underpinnings will be much more clearly understood, diminishing the need for frequent software and protocol updates in response to potential crises. Alternately, perhaps “Bitcoin will require the emergence of governance structures … to cope with longer-term structural challenges” as Kroll, Davey and Felten argued in a recent paper.
In summary, here is the current state of our knowledge:
-
The assumption that X% of the hashpower cannot earn more than X% of the revenue is almost certainly not true, once X% exceeds 33.3%.
-
Network vulnerabilities could potentially make this threshold much smaller. We don’t know for sure yet.
-
Even with an optimal network, and for mining coalitions between 0 and 1/3 of hashpower, we have no proof that honest mining is the most profitable strategy. Even if the paper’s “selfish mining” strategy turns out not to work in this case, it is possible that another strategy exists.
-
Given an adversarial mining strategy, can a coalition form around it? This is an orthogonal question that awaits a definitive answer.
-
Regardless of its other merits, it is likely that this paper will necessitate stronger sybil defenses, and this will further underscore the degree to which Bitcoin’s security currently depends on the actions of its volunteer custodians.
[1] There is another assumption necessary for the standard Bitcoin security argument: no investment of X% of the money spent on mining can achieve more than X% of the hashpower. The paper does not challenge this assumption, however.
[2] Members of the Bitcoin community have already created simulations that seem to confirm this aspect of the paper’s claims https://bitcointalk.org/index.php?topic=326559.0.
[3] Bitcoin developer Greg Maxwell has proposed an efficient “proof-of-storage” puzzle suitable for this purpose https://bitcointalk.org/index.php?topic=310323.0.
Despite game-theoretic results, prisoners don’t always defect, ultimatum-givers don’t always set their offer at (0 + epsilon), and ultimatum-receivers don’t accept every positive offer.
While the Eyal-Sirer paper is clearly valuable for its analysis of strategic mining with some rigor, I predict its ultimate impact will be to remind people that lots of other, harder-to-analyze factors dominate in real systems.
Mining pools have been operating for years in a trench-warfare environment. Their profit-maximizing, statistically-savvy operators have already faced DDoS, computational DoS, ruthless anonymous competition, treacherous participants (‘block withholding attacks’), rational and irrational ‘pool-hoppers’, discriminatory block- and transaction-propagation, black-hat hacking, and other kinds of network glitches and software bugs.
Based on my observation of pool evolution, dating back to a few months of my own solo and pool mining back in 2011, I suspect that the major pools have already encountered, tried, and folk-remediated not just ‘selfish mining’, but other gaming that academic analysis won’t discover for another few years.
After all, the 1st discussion of a similar ‘mining cartel attack’ in the Bitcoin forums dates back to December 2010. But the forums aren’t likely to show the state-of-the-art. Pool operators don’t have an academics’ incentive to formalize models and publish results. Defending quietly, via ad-hoc and non-public action, avoids educating or encouraging either the original attackers or copycats.
Against that potential “street-level” reality, the authors’ confident pronouncements of imminent doom come off as patronizing and naive. For example:
* “You heard it here first: now is a good time to sell your Bitcoins” (tweeted just before the paper announcement, when Bitcoin was at USD$210)
* “[Our recommended] 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.” (from the paper)
Having now read the paper, I’ll go over some major blind spots below. I’ll follow Felton in referring to the paper’s attack as “ES-mining”, rather than “selfish-mining”. (‘Selfish’ vs. ‘honest’ as a terminology is prematurely conclusory and reductionist. I assume all participants are self-interested, but have varied values and are already practicing diverse strategies beyond a simple two-type model.)
(1) *No backtesting.* The authors make the strong claim that ES-mining is a profitable strategy and imminent risk. But there have been large, well-funded, profit-seeking mining groups in operation for years, highly motivated to independently discover and implement this strategy. Pool operators watch their performance versus expectations very closely, and regularly seek advantage over rivals in features, payouts, and policies.
Further, ES-mining would leave public evidence, in the rates of orphaned blocks, consecutive block-batches from certain pools, and skews in block timestamps.
But have the authors looked for such evidence? The possibility seems waved off with a single sentence: “To the best of our knowledge, so far such pools have been benign and followed the protocol.” But historical pool competition has not been “benign” and strictly by-the-book, and the idea this strategy would sit undiscovered and untried, even after described in sketch form in the forums nearly three years ago, is hard to believe.
(2) *No consideration of costs.* The paper includes a section on ‘revenues’ (4.2), but none on ‘costs’. In ES-mining, “while both honest and selfish parties waste some resources, the honest miners waste proportionally more”. Holding difficulty constant, whatever increase in proportionate revenues ES-mining yields its practitioners comes with larger electricity/rent costs. (Even holding physical plant constant: the network as a whole will generate fewer main-chain blocks, in the presence of ES-mining, for same amount of wall-clock time.) The magnitude of this cost increase, for the ES-miner, relative to the gain will determine whether ES-mining is profitable at the outset. Difficulty adjustment changes the analysis – resetting the revenue rate in the attacker’s favor – but if the strategy requires initial losses, it becomes harder to bootstrap.
There will be other costs to ES-mining, especially as it grows. Moreso than other pools, it must obscure its ‘wins’, recruit hashpower in secret, and enforce sanctions against those who contribute hashpower only when it is ahead, or leak its motivations to the public. It must somehow prove to its own members that it is not underpaying them, even while attracting them with its proven ability to underpay the outside world – a difficult proposition technically and socially. Clandestine discipline is costly, perhaps super-linearly.
And that’s before detection and retaliation. Simple uncoordinated tit-for-tat strategies by other miners may be sufficient for mutual deterrence. Slow-delivering blocks to any parts of the network that seem to lag or batch blocks, or biasing against pools (or all ‘unknown’ sources) when they often orphan others’ blocks, will drive up ES-miner costs. Given the real-world phenomenon of “altruistic punishers”, it is insufficient to model just ED-miners and the simplistically, uniformly ‘honest’ remainder. Motivated-enforcers will improvise multiple strategies, and incur larger losses, to enforce norms until they see abuse subsiding. As a result, no simple modeling of immediate payoffs can predict a ‘phase transition’ or ‘collapse’ of the whole system.
More analysis is worthwhile, for sure, but looking only at the proportion of revenue, and ignoring profit net of increased costs – periodic/variable costs, strategy overhead, and retaliations – is insufficient to pronounce an “imminent danger”.
(3) *Shaky gamma assumptions.* If a pool’s real-world gamma is a function of its size, rather than the paper’s often-assumed 1/2 or conjectured-to-be-achievable (via Sybil attacks) near-1, the feasibility thresholds drop. If the gamma already varies dynamically based on other pools’ self-defense, perhaps dropping to near 0 when shenanigans are suspected, then the authors’ recommended fix of nudging it *up* towards 1/2, by randomization, could make things worse.
Taken together, these are symptoms of trusting a clean abstract model moreso than empirical system behavior. There’s nothing wrong with clean abstract models, unless you mistake them for a ground truth whose predictions require emergency action – “sell Bitcoins now”, “take measures immediately or face collapse”.
Such prescriptions are premature; more real-world observation makes sense instead. If and when evidence of unchecked ES-mining arrives – and it should be obvious if it does – there will be plenty of time, and ideas, for countermeasures.
Ha, googling your name, I see that you have an undergraduate economics degree. This has allowed you to progress farther along the road to common sense then other participants in this debate.
Now, if I could just send everyone else back to school we wouldn’t have game theory accidents like this.
When competing miners discover different blocks why not just disallow both blocks? Then the attack won’t work right? Then just don’t allow mining until the system is not under attack?
What you are suggesting is a lethal protocol change. The change would mean potentially that the blockchain could be disrupted by a rogue miner: say the head block is number n. The rogue miner would simply publish a block after an honest miner and before a new block is attached to n+1. The honest miner would have wasted its computation efforts and the block chain length would be stuck at n. I doubt that your suggested change will be adopted ;O)
Your comments on attackers din’t want to break the network is wrong, thay may want exacy that. Government, for example, to avoid an uncintrollable currency
Then they (the Govenrment ??) did not have to wait for the selfish mine strategy: they might as well go directly for the 51% attack. That’s precisely why honest miners (with a vested interest in the long term value of bitcoin) will not follow the selfish mine strategy. Also because the rewards of the selfish mine strategy do not offset the loss in value of the bitcoins.
For counter-measures against the 51% attack, try checkpoints: the Govenrment spends big tax payer money (through secret services of course) to disrupt the network for a few hours or even days. Then Snowden leaks the information.Then its election day and…
Maybe thats why we have not seen a 51% attack yet.
Any way the paper is the most interesting challenge to conventionnal wisdom about bitcoin network security.
ultimately there is the economic argument: such an attack would destroy the network’s value. it would be suicide for the attackers.
I wouldn’t put it that starkly, but you highlight an important point: any ‘attack’ which pays-out in bitcoins also incents the attackers to keep the overall ecosystem safe, in order to run the attack as long as possible, prevent the rapid adoption of countermeasures, and maintain the resale value of their bitcoin loot.
To the extent that those most likely to have the insight and skills to launch the attack are bitcoin enthusiasts, they also may have a long-term interest in the system’s health (perhaps via long-term bitcoin holdings and assets – like specialized mining hardware – whose value is correlated with bitcoin). That also moderate their interest in short-term profit-maximization versus health of the system.
So like other parasites, ES-miners don’t want to kill the host… and might even wind up trying to provide other commensal benefits. Or to switch from biology to political economy: they’re ‘stationary bandits’.
You might be interested in this if you haven’t seen it yet. In the dynamic repeated game (which you are implicitly and correctly invoking by discussing a short- and long-run; a static game doesn’t have these concepts), there are subgame perfect equilibria where only cooperation occurs (in fact an infinite set of these equilibria exist [folk theorem]). As long as we are operating on one of these equilibria, a rational actor will never engage in selfish mining.
http://www.scribd.com/doc/182399858/Cunicula-s-game-theory-primer-pdf
The authors develop screwy conclusions by adopting a one-off framework where there is no repeat play. Taken litereally, there mining process is like this:
1) I purchase a hash, choose a mining strategy, and mine with that hash.
3) If I find a block, then I instantaneously sell it for USD value.
4) I exit the game.
In this setting, I do not care at all about the future because I am only playing the game once. If miners play the game more than once, i.e. they hash two or more times, then the game becomes dynamic and repeated, and the authors game theoretic analysis is no longer valid (because it assumes away repeated play, quite absurdly).
Cunicula,
I responded to you on an earlier post, trying to read these sequentially not having visited this site for a while. This post from you, does sure up my own thinking regards to what you are saying about the different models; so I am sure I understand what at least you are talking about. You also cleared up for me what the “after that” is ES’s position, after building the bigger tower [see my post to Ed’s article Nov. 7 for my analogy] the subversive players exit the game with a payout in another monetary system.
Ahh; and yes, in that case, we need to understand psychology here. Those with a know how to do it, will they really be “bitcoin enthusiasts” as Gordon presumes? Or, will they be power hungry trolls from another economic model entering the bitcoin mining for their own sake? And that is where all the questions on the Cornell paper or even any other possible “adversarial mining strategy” must focus. Can bitcoiners truly presume everyone playing the game has the game itself as their motivator [as chess players do]? Or, is there a chance that some playing the game are game hackers.
And I suggest that a presumption of hackers is a valid presumption which is ES’s position; thus making at least their model of a one-off game a valid model. Whether the model is that 51% of the players are hackers, 33.3% are hackers, or less, it still centers around the question, are any game hackers playing?
So long as Bitcoins can be traded like any other currency to any other recognized currency in the world (be it US Dollars or Chinese Renminbi [where I see the world more likely going toward]) there is a heavy incentive for adversarial mining that is NOT bitcoin enthusiastic. In other words there is a high possibility there will be those who enter the game simply to win it once and then leave with all the power granted to them in another economic currency. They may even enter the game a second or third time etc.; but it will always be only to the extent that they can profit with power in another economic domain. My knowledge of psychology tells me there WILL be game hackers if they find that they can profit; that leaves the questions as only how many hackers does it take to profit, and can they coalesce together, and as such be successful at their hacking attempt.
Of course, it also sures up my mind on the bitcoin enthusiasts themselves; they are also hackers, they are economic hackers, they are playing a game of trying to get their own work to be more profitable by pushing their own currency compared to other global curacies. Bitcoin mining truly is “a game for rich young boys to play.”