Why the Cornell paper on Bitcoin mining is important

    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.