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.