In light of the back-and-forth about the recent Eyal and Sirer (“ES”) paper about Bitcoin mining, I want to take a step back and talk about what a careful analysis of Bitcoin mining dynamics would look like. (Here are some previous posts if you need backstory: 1 2 3 4 5.)
The key to a sound analysis of situations like this is to use game theory, a well established set of intellectual tools for thinking about strategic behavior in adversarial settings.
The ES paper makes two main claims that use language from game theory. First, they claim that their “selfish” strategy dominates the default “honest” Bitcoin mining strategy. Second, they claim that Bitcoin is not incentive compatible.
To understand why reasoning about games can be nonintuitive, consider the simple two-player game of rock-paper-scissors. A player, observing that rock wins against scissors, might think this implies that a rational player should always play rock or should never play scissors. Both conclusions are incorrect—in fact, a player who always plays rock will lose in the long run, as will a player who never plays scissors.
The fallacy here is thinking that if A wins against B, this implies that A is a better strategy than B. Game theory gets this right, capturing the informal concept of better strategy with a concept of domination that is defined so that A dominates B means that (1) there are situations where A is a better choice than B, and (2) no matter what the other players do, A is never a worse choice than B. Rock does not dominate scissors because although condition (1) is true, condition (2) is not true: when the other player chooses paper, rock is not a better choice than scissors.
The ES authors commit this fallacy when they say “we have shown that selfish mining dominates the honest Bitcoin protocol”. What their paper actually argues is that “selfish” wins against “honest”—which implies part (1) of the definition of dominates. They don’t try to show that part (2) is true—and part (2) is clearly not true because a small miner is better off being honest when everybody else is being honest.
So the first main claim of the ES paper—that “selfish” mining dominates honest Bitcoin mining—is incorrect.
The second important tool of game theory, which will speak to the second ES claim, is the concept of Nash equilibrium. This deals with the “What will he think I am thinking about what he thinks I am planning” difficulty in reasoning about complex games. Essentially, a Nash equilibrium is a situation in which, if all players’ strategies become known, no player wants to change their strategy in response to what the others are doing. A famous theorem showed that at least one equilibrium always exists in games like these.
In rock-paper-scissors, there is a unique Nash equilibrium in which each player randomly chooses their move, with each possible move being chosen with equal probability. In general, games can have multiple equilibria. (There is a body of theory that classifies equilibria and considers some more worthy than others; but that doesn’t really matter for us here.)
When the ES paper claims to have shown Bitcoin to be not incentive compatible, it’s not exactly clear what they mean. Three possibilities seem plausible. (1) There is no equilibrium in which all miners behave honestly. (2) There is an equilibrium in which some miners deviate from the honest protocol. (3) There is an equilibrium in which in ordinary users of Bitcoin cannot get transactions done.
The ES paper doesn’t seem to talk about equilibria, and its arguments don’t seem to come near to any of the three possible definitions.
For what it’s worth, Josh Kroll, Ian Davey, and I previously published a paper discussing equilibria in Bitcoin mining. We showed that there is an equilibrium in which all miners follow the standard honest protocol. We also showed that there are infinitely many other equilibria in which all miners behave identically to enforce a different set of “Bitcoin rules”. So in the model we used, we showed that definition (1) is not satisfied but definition (2) is satisfied. Our results don’t speak to definition (3).
But our model of the mining game differs from the ES paper’s model, so our results don’t carry over completely to their model. In the case where no individual miner controls more than 33.3% of mining power, our results do carry over to the ES paper’s model. And when one miner controls more than 50% of mining power, everyone agrees on what will happen.
So the open question, which our work (in a different model) doesn’t extrapolate to cover, and which the ES paper doesn’t address either, seem to be this: in the case where there is a miner controlling more than 33.3% of mining power but less than 50%, is there still an equilibrium in which all miners are honest? More research would be required to answer this question.
But the most important question about the dynamics of Bitcoin mining, which nobody has yet answered, is whether there is an equilibrium that can actually occur in which the Bitcoin economy can no longer function. This is the question that everyone would like to answer.
Here’s the bottom line on the ES paper, as I see it. The ES paper has provided value by describing and characterizing a strategy in which miners or pools withhold mined blocks in order to try to gain an advantage. This starts a useful conversation. But their bold claims about dominant strategies and incentive incompatibility are unsupported and sometimes incorrect. More progress will have to be made before we can understand what role if any the new mining strategies might play in practice.
Our response to this post is here:
http://hackingdistributed.com/2013/11/14/response-to-feedback-on-selfish-mining/
The whole talk about “equilibria” seems irrelevant to me. Of course there are all kinds of equilibria with all kinds of probabilities, but that’s not how you to cryptology and computer securty.
If a cryptographer wants to analize the security of a system, he always assumes the worst. He always assumes a strong and lucky adversary.
It does not help if there exist equilibria with everybody playing honest. To make a cryptographer happy, you actually have to positively prove that all equilibria with unhonest behavior are practically impossible, i.e. have a exponentially small probability.
>and part (2) is clearly not true because a small miner is better off being honest when everybody else is being honest.
Actually not. That is the whole point of that work. Even for small miner, the selfish-mine is the better strategy.
http://www.youtube.com/watch?v=oa1Ezq7e0MA
Here is the link for the documentary. Thanks for the article. I agree that your opponents are mistaken – I don’t feel Game theory is the way to show that, however.
“The key to a sound analysis of situations like this is to use game theory, a well established set of intellectual tools for thinking about strategic behaviour in adversarial settings.”
John Nash, who was central to conceiving of game theory, was a paranoid schizophrenic, who admitted his theories were far too simplistic to apply to the complex array of factors that influence human behaviour and character; from elementary genetics to our social, economic and even pre-natal environments.
I have to fundamentally disagree that game theory is a valid tool for evaluating human behaviour. It is at least far from the best. The social sciences, and the harder ‘Neuroscience’, are far more useful than the day dreams of paranoid economists and mathematicians.
It’s perhaps interesting as a point of discussion, but the solid tool of intellectual might it claims to be, is claimed by the mind of the ever expanding businessman, who sought a value system to justify their insatiable desire for more, leaving others will less. They found that in Adam Smith and the intellectuals of the English colonies of the Americas. The psychology of this greed is another incredibly complex, yet paradoxically simple can of worms, which we can partially trace back to the start of civilization and the beginnings of class society as a result of the discovery of agriculture.
I mean no offence but this was a difficult article to read. I found myself swamped in semantics. Equilibrium is a very intellectual sounding term, it sounds like some sort of mathematical perfection; a perfect balance of forces or power where desired behaviour is achieved.
But for some reason I find this language common only in the minds of those who have to a certain degree absorbed capitalist culture and economic theory, largely fueled upon assumptions about what they call ‘human nature’ – and being the descendants of highly violent, colonial societies (just look at the culture the Romans left behind in England – could it have anything to do with the flowering of the British Empire?)
If you’re interested in seeing where I’m going with this, please check out the (Surprisingly) fantastic BBC documentary by Adam Curtis called ‘The Trap’. The very first section analyses how John Nashes theories were leapt upon by political and economic powers seeking to validate their practices and export them around the world.
P.S – I bought into bitcoins because in a transitional sense, I believe a world in which we do not have to think about money may only be possible after money becomes debt free, and as abundant as it needs to be to fuel the trade of goods and services necessary to facilitate and promote a life economy, not a monetary economy where money is itself a commodity. Then perhaps we might realize that in a world of abundance we need not hoard a personal stash of resources and spend so much time and energy thinking of ourselves when we live in a reality requiring global cooperation for our collective survival. To survive war, climate change, pollution, cosmic events like asteroids, solar flares – we have to grow up and harness our capacity to cooperate.
I just hope Bitcoin doesn’t embed further in human culture the idea of separation and independence, ideas that game theory seems to solely promote – even reducing cooperation to simply a means to further ones own ends. Doing so is not shameful, but it is not the sole reason we cooperate. I dare say we could not explain it with such fickle things as words.
By the way, sorry for accidently posting twice. Also, I am a hothead and these ES fellows have really annoyed me. I looked at your paper and I think it is a useful analysis. There are many deeper issues to examine sure, but you have gotten this off to a positive start.
Thanks so much for voicing your concerns here. It makes me feel more optimistic.
Finally, yes, assuming that attacks negatively affect prices, the dynamic model generates conditions where a 51% attacker will continue to mine honestly (and probably do so while disguising the true extent of his holdings).
I thought about this two years ago and termed it a ‘benevolent monopoly.’ Since then we have actually seen the benevolent monopoly come to pass and intentionally enforce antitrust against itself.
The cooperative monopoly equilibrium breaks down if block reward subsidies get too low. The problem is that gains from imposing high monopoly fees persist even as subsidies fall. Proportionally, an attack multiplies income by a larger and larger factor over time.The subsidies are keeping people well-behaved, but this could change in the very long-run (say a decade or more).
This is the motivation behind the proof of stake coin, ppcoin. It does not encounter the same long-run theoretical problems. Are you interested in these things? Should I send you a pdf explaining the models underlying the conclusions above?
I agree that things get worse when the mining reward decreases beyond a certain point. For this reason, I think the rules will eventually be changed to freeze mining rewards at some level, as opposed to decreasing them to zero as currently planned.
I would be very interested in seeing a solid model of proof-of-stake.
I suspect that you are implying that someone holding 51% would attack. In the past, a single company (not a pool), but a single mining facility (ASICMINER) held 25%. They deliberately avoided holding the majority by selling off hardware they produced to third parties. They are based in China and I believe they could attack from this jurisdiction without any reason to fear legal reprisals.
As economists see it, the challenge of game theory is to develop models that predict real world behavior. Economists regularlt take game theoretic models to data. The standard approach is to estimate model parameters that minimize observed deviations from rationality. The models allow you to predict what will happen if some substantial change happens, e.g. two large car companies merge and decide how to adjust the set of cars they offer.
I feel like the objective of this line of research has been misguided. Companies have invested enough to mount a 51% attack, but chose not to, instead selling off the hardware. This tells us that bitcoin is incentive compatible, even if one guy has 51%. This falsifies any model which predicts that consolidated 51% holdings lead to a unique attack equilibrium. Attack could be one equilibrium (an surely is), but it cannot be the only equilibrium.
What’s the implication? We need to design models that are consistent with observed real world behavior. These models can help us identify real world security concerns. They can predict what may happen if a large unprecedented change occurs and whether the change poses a security risk. We do not need someone to tell us that bitcoin is irrational and that mining companies are foolishly leaving money on the table by not attacking. That’s been falsified already. Instead give us a model that explains why 51% attack opportunities are left on the table right now. Use the model to investigate future scenarios under which this could possibly change.
If you guys keep crying wolf, then when someone comes along with a credible analysis people will just ignore it.
That frustrates me.
I don’t think I can predict the practical implications of a mining monopoly with any confidence. I can see the argument that a mining monopolist might act like a rational parasite who extracts value from the host while taking care not to kill it. But I can also see the argument that people won’t want to participate in the Bitcoin economy if they know somebody has a doomsday device that can blow up the whole Bitcoin world at any time.
A mining monopoly creates uncertainty and risk for everybody, including the miners. So it seems sensible for a miner to avoid acquiring a monopoly, even if he can get one. Unless his goal is to destroy Bitcoin.
I would be interested in hearing about any model that is useful in understanding this situation.
Why do so many continue to participate in the US monetary system? It is run by a monopoly which engages in destructive activities. The only real barrier to leaving is that replacing it with another system would require an alternative framework to be in place.
With Bitcoin, the cost of switching is marginal; existing infrastructure would need only minor adjustments to support alternatives.
I think the focus on Bitcoin’s internal incentive structure needs to be directed outward.
What is the connection between the mining process and the Bitcoin economy? Given that there are already a large number of Bitcoins in circulation, there’s no immediately obvious reason why even a complete collapse of the mining process should necessarily cause any problems to the Bitcoin economy. Similarly, if I’m buying, trading or selling a Bitcoin, I don’t see why it would make any difference to me whether new Bitcoins are being distributed “fairly” or not.
What am I missing?
I suspect that you are implying that someone holding 51% would attack. In the past, a single company (not a pool), but a single mining facility (ASICMINER) held 25%. They deliberately avoided holding the majority by selling off hardware they produced to third parties. They are based in China and I believe they could attack from this jurisdiction without any reason to fear legal reprisals.
As economists see it, the challenge of game theory is to develop models that predict real world behavior. Economists regularlt take game theoretic models to data. The standard approach is to estimate model parameters that minimize observed deviations from rationality. The models allow you to predict what will happen if some substantial change happens, e.g. two large car companies merge and decide how to adjust the set of cars they offer.
I feel like the objective of this line of research has been misguided. Companies have invested enough to mount a 51% attack, but chose not to, instead selling off the hardware. This tells us that bitcoin is incentive compatible, even if one guy has 51%. This falsifies any model which predicts that consolidated 51% holdings lead to a unique attack equilibrium. Attack could be one equilibrium (an surely is), but it cannot be the only equilibrium.
What’s the implication? We need to design models that are consistent with observed real world behavior. These models can help us identify real world security concerns. They can predict what may happen if a large unprecedented change occurs and whether the change poses a security risk. We do not need someone to tell us that bitcoin is irrational and that mining companies are foolishly leaving money on the table by not attacking. That’s been falsified already. Instead give us a model that explains why 51% attack opportunities are left on the table right now. Use the model to investigate future scenarios under which this could possibly change.
If you guys keep crying wolf, then when someone comes along with a credible analysis people will just ignore it.
That frustrates me.
While mining is the only way that new bitcoins come into existence, the *real* purpose of mining is to confirm transactions and add them to the blockchain. If someone has 51% of the mining power, they control the blockchain, and effectively have the power to alter it at will, enabling them for example to spend the same bitcoins twice.
The original article wasn’t really about being able to increase bitcoin earnings by mining selfishly: it was claiming that it would be possible to control the blockchain with only 25% of the total mining power.