Response to Feedback on Selfish Mining

bitcoin security selfish-mining November 14, 2013 at 09:45 AM Ittay Eyal and Emin Gün Sirer

It has been approximately a week since we made our paper on selfish mining public. In this blog post, we'd like to answer a large number of the quick reactions we've heard en masse. (Previous discussions are here [1] [2] [3] [4]).

Before we do that, let's recap what our paper did:

it outlined an attack on the Bitcoin mining process,
it showed that attackers participating in this attack can earn revenues in excess of their fair share,
it characterized conditions under which the attack will be successful as a function of attacker power (alpha), and the amount of control the attacker exerts over block propagation in the network (gamma),
it showed that the attacker will profit, even with no Sybils, with no control over block propagation, and while losing every block race in the network, if he commands a pool with more than 33% of the total mining power,
it showed that an attacker with strong control over block propagation will profit regardless of his pool size,
it showed that once a successful attacker emerges, the system dynamics reward fresh nodes for joining ranks with the attacker,
it suggested one fix, at the protocol level, for ensuring that selfish mining with power less than 25% will not succeed.

Response to Felten

Ed Felten raises issues in a blog post on a game-theoretic treatment of Bitcoin [5]:

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.

This summary of our contributions is incomplete and therefore misleading. And these claims do not appear in our paper; they appear in a distinct and separate blog post. The distinction is important, because the implied assumptions are different in each context.

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”... So the first main claim of the ES paper—that “selfish” mining dominates honest Bitcoin mining—is incorrect.

The blog post implicitly assumes that the strategy space is confined to "honest" and "selfish" miners, the topic of the blog post. With the strategy space confined to those two behaviors, selfish mining dominates the honest Bitcoin protocol.

Felten is correct in that there could well be unknown other strategies that could change this relationship. With the strategy space unbounded, we do not know if selfish dominates honest. Felten offers no such strategy, however.

Independent of the blog post, our paper is precise in its claims; it spells out its assumptions and the consequences of its findings clearly. Felten disagrees with the implicit scope of our blog post, and is casting this disagreement as if it were a weakness of our paper.

A small miner is better off being honest when everybody else is being honest.

This is false. For high gamma, a small (low alpha) miner is better off being selfish if everyone is honest. This means that honest mining is not a Nash equilibrium.

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.

The Kroll, Davey and Felten (KDF) paper provides a formalization of the Bitcoin game, but implicitly ignores a class of attacks based on block witholding. It, therefore, erroneously concludes that honest mining is a Nash equilibrium in the real system.

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.

If the system does not function, no one would play. Equilibriums with zero players are not particularly interesting.

But their bold claims about dominant strategies and incentive incompatibility are unsupported and sometimes incorrect.

Point #2 above addresses dominant strategies and Point #3 addresses incentive incompatibility. It would be interesting to take the framework in the KDF paper, amend that model in light of our findings, and reexamine their result that honest mining is a Nash equilibrium.

Response to Other Commenters

You model the behavior of the system as if it were Prisoner's Dilemma; let me tell you why this is wrong.

The phrase prisoner's dilemma does not appear in our paper, so this claim needs to be further documented before we can evaluate it.

Bitcoin mining is an iterative game and a reactive strategy will punish the selfish miners.

There is no indication at the moment that there would be any punishment for selfish miners. Whether reaching 51% is a punishment for the attacker depends on assumptions about the attacker and the attack aftermath.

If everyone engaged in selfish mining, they would cancel each other out.

Our paper does not address what happens when multiple pools employ the selfish strategy. But if all pools were selfish, the blockchain would not make forward progress for large periods of time, while selfish groups hoard their blocks. Then, perhaps, depending on the profit-taking strategy of the selfish miners and their relative sizes, it would take erratic large steps forward. Such erratic behavior would not bode well for the users who want to transact in the currency.

Crossing over the 50% boundary is such a drastic event that, upon passing that boundary, I predict the following will happen.

The 50% line is indeed a drastic event. Once crossed, what happens next depends entirely on one's assumptions about the identities of the actors and their overall goals. Because these scenarios are so dependent on assumptions, we'd rather focus our attention on techniques that will keep the system far away from this point.

We'd love to see properly formulated, comprehensive treatments on this topic.

Crossing over the 50% boundary is such a drastic event that, upon getting close to that boundary, I predict the following will happen.

We'd rather focus on techniques that will keep the system far away from this boundary, but we'd love to see properly formulated, comprehensive treatments on this topic as well.

Loss of decentralization is a catastrophic event for the currency, akin to the day after nuclear war, and no one would want to do this because it would crash their own investment. It's analogous to mutual assured destruction.

This assumes that all the participants are vested in the long-term well-being of the currency. A strong currency system cannot rely on the good intentions of its participants. Currencies are attacked all the time by actors with disruptive goals. Such actors may be aided by rational, short-term profiteers. A robust currency would have well-characterized properties, such as a well-defined threshold below which attackers are guaranteed not to succeed, to provide strong assurance to its users.

Bitcoin personalities would manually detect and take currently-unspecified-but-sure-to-be-invented measures against any selfish mining.

Perhaps. And that would be nice if it happened. But a robust cryptocurrency would derive its properties from the fundamental protocol, not from operational bandaids or from the actions of a centralized board.

Response from Bitcoin Developers

Here are some excerpts from the Bitcoin developers' discussion forums:

From: Gavin Andresen <gavinandresen@gmail.com>
Date: Thu, 7 Nov 2013 14:56:56 +1000

> P.S: If any large pools want to try this stuff out, give me a shout. You
> have my PGP key - confidentiality assured.
>

If I find out one of the large pools decides to run this 'experiment' on
the main network, I will make it my mission to tell people to switch to a
more responsible pool.

We applaud Gavin Andresen for his diligent stance against selfish mining.

Date: Wed, 6 Nov 2013 23:33:10 -0500
From: Peter Todd <pete@petertodd.org>

Anyway, my covert suggestion that pools contact me was more to hopefully
strike fear into the people mining at a large pool and get them to
switch to a small one. :) If everyone mined solo or on p2pool none of
this stuff would matter much... but we can't force them too yet.

This is a very prudent reaction. Smaller mining pools are in regular users' best interests.

Meta-Responses to Non-Questions

Your paper does not examine ...

Correct (probably, without seeing what's in the ellipsis). The paper addresses only the points it sets out to address, and leaves many interesting questions to future work.

Bitcoin is at $400 USD, you failed to bring it down!

We are Bitcoin supporters and have been working to strengthen the system. We believe that the system can be patched to provide strong guarantees against selfish mining, and we have offered one patch at the protocol level. Overall, we are genuinely thrilled to see the strong buy-in to the system.

You computer scientists don't know anything about game-theory.

We beg to differ on behalf of our discipline. These kinds of remarks are unlikely to yield an interesting discussion.

You <noun-phrase>! You don't know anything about <technical term>.

One of the early research efforts in sentiment analysis was the Smokey system by Ellen Spertus, which discovered that the "you <noun-phrase>!" construct, known as a noun apposition, tended to mark Internet flames. Research results, if incorrect, can be demonstrated to be false without resort to flaming, ad hominems or uttering profanities. We encourage you to point out, and improve on, perceived and/or real flaws in our paper.

I have a thought and I plastered it all over your blog in different comments. Repeatedly. Please respond.

This behavior is indistinguishable from spam. Please refrain. Express your rebuttal, if you have one, concisely just once, and we will address the points that bear merit.