Majority is not Enough: Bitcoin Mining is Vulnerable

design “addresses the incentive problems most expeditiously,” while Bitcoin tu-

torials for the general public hint at incentives designed to align participants’

and the system’s goals [

27

]. More formally, Kroll, Davey and Felten’s work [

19

]

provides a game-theoretic analysis of Bitcoin, without taking into account block

withholding attacks such as selfish mining, and argues that the honest strategy

constitutes a Nash equilibrium, implying incentive-compatibility.

Our work shows that the real Bitcoin protocol, which permits block with-

holding and thereby enables selfish mining-style attacks, does not constitute an

equilibrium. It demonstrates that the Bitcoin mining system is not incentive

compatible even in the presence of an honest majority. Over 2/3 of the par-

ticipants need to be honest to protect against selfish mining, under the most

optimistic of assumptions.

A distinct exception from this common wisdom is a discussion of maintaining

a secret fork in the Bitcoin forums, mostly by users

3

btchris, ByteCoin, mtgox,

and RHorning [

28

]. The approach, dubbed the Mining Cartel Attack, is inferior

to selfish mining in that the cartel publishes two blocks for every block published

by the honest nodes. This discussion does not include an analysis of the attack

(apart from a brief note on simulation results), does not explore the danger of

the resulting pool dynamics, and does not suggest a solution to the problem.

The influential work of Rosenfeld [

30

] addresses the behavior of miners in the

presence of different pools with different rewards. Although it addresses revenue

maximization for miners with a set mining power, this work is orthogonal to

the discussion of Selfish Mining, as it centers around the pool reward system.

Both selfish pools and honest pools should carefully choose their reward method.

Since a large-enough selfish pool would earn more than its mining power, any

fair reward method would provide more reward to its miners, so rational miners

would choose it over an honest pool.

Recent work [

4

] addresses the lack of incentives for disseminating transactions

between miners, since each of them prefers to collect the transaction fee himself.

This is unrelated to the mining incentive mechanism we discuss.

A widely cited study [

29

] examines the Bitcoin transaction graph to analyze

client behavior. The analysis of client behavior is not directly related to our work.

The Bitcoin blockchain had one significant bifurcation in March 2013 due to

a bug [

2

]. It was solved when the two largest pools at the time manually pruned

one branch. This bug-induced fork, and the one-off mechanism used to resolve it,

are fundamentally different from the intentional forks that Selfish-Mine exploits.

In a block withholding attack, a pool member decreases the pool revenue by

never publishing blocks it finds. Although it sounds similar to the strategy of

Selfish-Mine, the two are unrelated, as our work that deals with an attack by

the pool on the system.

Various systems build services on top of the Bitcoin global log, e.g., improved

coin anonymity [

22

], namespace maintenance [

24

] and virtual notaries [

16

,

3

].

These services that rely on Bitcoin are at risk in case of a Bitcoin collapse.

3

In alphabetical order

---

8

Discussion

We briefly discuss below several points at the periphery of our scope.

System Collapse The Bitcoin protocol is designed explicitly to be decentralized.

We therefore refer to a state in which a single entity controls the entire currency

system as a collapse of Bitcoin.

Note that such a collapse does not immediately imply that the value of a

Bitcoin drops to 0. The controlling entity will have an incentive to accept most

transactions, if only to reap their fees, and because if it mines all Bitcoins, it has

strong motivation that they maintain their value. It may also choose to remain

covert, and hide the fact that it can control the entire currency. An analysis of a

Bitcoin monopolist’s behavior is beyond the scope of this paper, but we believe

that a currency that is de facto or potentially controlled by a single entity may

deter many of Bitcoin’s clients.

Detecting Selfish Mining There are two telltale network signatures of selfish

mining that can be used to detect when selfish mining is taking place, but neither

are easy to measure definitively.

The first and strongest sign is that of abandoned (orphaned) chains, where

the block race that takes place as part of selfish mining leaves behind blocks

that were not incorporated into the blockchain. Unfortunately, it is difficult to

definitively account for abandoned blocks, as the current protocol prunes and

discards such blocks inside the network. A measurement tool that connects to

the network from a small number of vantage points may miss abandoned blocks.

The second indicator of selfish mining activity is the timing gap between

successive blocks. A selfish miner who squelches an honest chain of length N with

a chain of length N + 1 will reveal a block very soon after its predecessor. Since

normal mining events should be independent, one would expect block discovery

times to be exponentially distributed. A deviation from this distribution would

be suggestive of mining activity. The problems with this approach are that it

detects only a subset of the selfish miner’s behavior (the transition from state 2 to

state 0 in the state machine), the signature behavior occurs relatively rarely, and

such a statistical detector may take a long time to accrue statistically significant

data.

Measures and Countermeasures Although miners may choose to collude in a

selfish mining effort, they may prefer to hide it in order to avoid public criticism

and countermeasures. It is easy to hide Selfish-Mine behavior, and difficult to

ban it. A selfish pool may never reveal its size by using different Bitcoin addresses

and IP addresses, and by faking block creation times. The rest of the network

would not even suspect that a pool is near a dangerous threshold.

Moreover, the honest protocol is public, so if a detection mechanism is set

up, a selfish pool would know its parameters and use them to avoid detection.

For instance, if the protocol was defined to reject blocks with creation time

below a certain threshold, the pool could publish its secret blocks just before

this threshold.

---

A possible line of defense against selfish mining pools is for counter-attackers

to infiltrate selfish pools and expose their secret blocks for the honest miners.

However, selfish pool managers can, in turn, selectively reveal blocks to subsets

of the members in the pool, identify spy nodes through intersection, and expel

nodes that leak information.

Thieves and Snowballs Selfish mining poses two kinds of danger to the Bitcoin

ecosystem: selfish miners reap disproportionate rewards, and the dynamics favor

the growth of selfish mining pools towards a majority, in a snowball effect. The

system would be immune to selfish mining if there were no pools above the

threshold size. Yet, since the current protocol has no guaranteed lower bound

on this threshold, it cannot automatically protect against selfish miners.

Even with our proposed fix that raises the threshold to 25%, the system

remains vulnerable: there already exist pools whose mining power exceeds the

25% threshold [

26

], and at times, even the 33% theoretical hard limit. Responsi-

ble miners should therefore break off from large pools until no pool exceeds the

threshold size.

Responsible Disclosure Because of Bitcoin’s decentralized nature, selfish min-

ing can only be thwarted by collective, concerted action. There is no central

repository, no push mechanism and no set of privileged developers; all protocol

modifications require public discussion prior to adoption. In order to promote a

swift solution and to avoid a scenario where some set of people had the benefit

of selective access, we published a preliminary report [

14

] and explained both

the problem and our suggested solution in public forums [

13

].

9

Conclusion

Bitcoin is the first widely popular cryptocurrency with a broad user base and

a rich ecosystem, all hinging on the incentives in place to maintain the criti-

cal Bitcoin blockchain. Our results show that Bitcoin’s mining protocol is not

incentive-compatible. We presented Selfish-Mine, a mining strategy that enables

pools of colluding miners that adopt it to earn revenues in excess of their min-

ing power. Higher revenues can lead new miners to join a selfish miner pool,

a dangerous dynamic that enables the selfish mining pool to grow towards a

majority. The Bitcoin system would be much more robust if it were to adopt

an automated mechanism that can thwart selfish miners. We offer a backwards-

compatible modification to Bitcoin that ensures that pools smaller than 1/4 of

the total mining power cannot profitably engage selfish mining. We also show

that at least 2/3 of the network needs to be honest to thwart selfish mining; a

simple majority is not enough.

Acknowledgements We are grateful to Raphael Rom, Fred B. Schneider, Eva

Tardos, and Dror Kronstein for their valuable advice on drafts of this paper, as

well as our shepherd Rainer B¨

ohme for his guidance.

---

References

1. andes: Bitcoin’s kryptonite: The 51% attack.

https://bitcointalk.org/index.php?topic=12435

(June 2011)

2. Andresen, G.: March 2013 chain fork post-mortem. BIP 50,

https://en.bitcoin.it/wiki/BIP_50

,

retrieved Sep. 2013

3. Araoz, M.: Proof of existence.

http://www.proofofexistence.com/

, retrieved Sep. 2013

4. Babaioff, M., Dobzinski, S., Oren, S., Zohar, A.: On Bitcoin and red balloons. In: ACM Con-

ference on Electronic Commerce. pp. 56–73 (2012)

5. Barber, S., Boyen, X., Shi, E., Uzun, E.: Bitter to better, how to make Bitcoin a better currency.

In: Financial Cryptography and Data Security, pp. 399–414. Springer (2012)

6. Bitcoin community: Bitcoin source.

https://github.com/bitcoin/bitcoin

, retrieved Sep. 2013

7. Bitcoin community: Protocol rules.

https://en.bitcoin.it/wiki/Protocol_rules

, retrieved

Sep. 2013

8. Bitcoin

community:

Protocol

specification.

https://en.bitcoin.it/wiki/Protocol_

specification

, retrieved Sep. 2013

9. bitcoincharts.com: Bitcoin network.

http://bitcoincharts.com/bitcoin/

, retrieved Nov. 2013

10. blockchain.info: Bitcoin market capitalization.

http://blockchain.info/charts/market-cap

, re-

trieved Jan. 2014

11. Chaum, D.: Blind signatures for untraceable payments. In: Crypto. vol. 82, pp. 199–203 (1982)

12. Decker, C., Wattenhofer, R.: Information propagation in the Bitcoin network. In: IEEE P2P

(2013)

13. Eyal,

I.,

Sirer,

E.G.:

Bitcoin

is

broken.

http://hackingdistributed.com/2013/11/04/

bitcoin-is-broken/

(2013)

14. Eyal, I., Sirer, E.G.: Majority is not enough: Bitcoin mining is vulnerable. arXiv preprint

arXiv:1311.0243 (2013)

15. Felten, E.W.: Bitcoin research in Princeton CS.

https://freedom-to-tinker.com/blog/felten/

bitcoin-research-in-princeton-cs/

(November 2013)

16. Kelkar, A., Bernard, J., Joshi, S., Premkumar, S., Sirer, E.G.: Virtual notary.

http://

virtual-notary.org/

, retrieved Sep. 2013

17. King, S.: Primecoin: Cryptocurrency with prime number proof-of-work.

http://primecoin.org/

static/primecoin-paper.pdf

(2013)

18. King, S., Nadal, S.: PPCoin: Peer-to-peer crypto-currency with proof-of-stake.

https://archive.

org/details/PPCoinPaper

(2012)

19. Kroll, J.A., Davey, I.C., Felten, E.W.: The economics of Bitcoin mining or, Bitcoin in the

presence of adversaries. In: Workshop on the Economics of Information Security (2013)

20. Lee, T.B.: Four reasons Bitcoin is worth studying.

http://www.forbes.com/sites/timothylee/

2013/04/07/four-reasons-bitcoin-is-worth-studying/2/

(April 2013)

21. Litecoin Project: Litecoin, open source P2P digital currency.

https://litecoin.org

, retrieved

Sep. 2013

22. Miers, I., Garman, C., Green, M., Rubin, A.D.: Zerocoin: Anonymous distributed e-cash from

Bitcoin. In: IEEE Symposium on Security and Privacy (2013)

23. Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system (2008)

24. Namecoin Project: Namecoin DNS – DotBIT project.

https://dot-bit.org

, retrieved Sep. 2013

25. Narayanan,

A.,

Miller,

A.:

Why

the

Cornell

paper

on

Bitcoin

mining

is

im-

portant.

https://freedom-to-tinker.com/blog/randomwalker/why-the-cornell-paper-on-bitcoin-

mining-is-important/

(November 2013)

26. Neighborhood

Pool

Watch:

October

27th

2013

weekly

pool

and

network

statis-

tics.

http://organofcorti.blogspot.com/2013/10/october-27th-2013-weekly-pool-and.html

, re-

trieved Oct. 2013

27. Pacia, C.: Bitcoin mining explained like you’re five: Part 1 – incentives.

http://chrispacia.

wordpress.com/2013/09/02/bitcoin-mining-explained-like-youre-five-part-1-incentives/

(September 2013)

28. RHorning, mtgox, btchris, ByteCoin: Mining cartel attack.

https://bitcointalk.org/index.php?

topic=2227

(December 2010)

29. Ron, D., Shamir, A.: Quantitative analysis of the full Bitcoin transaction graph. In: Financial

Cryptography. pp. 6–24 (2013)

30. Rosenfeld,

M.:

Analysis

of

Bitcoin

pooled

mining

reward

systems.

arXiv

preprint

arXiv:1112.4980 (2011)

31. Swanson, E.: Bitcoin mining calculator.

http://www.alloscomp.com/bitcoin/calculator

, re-

trieved Sep. 2013

32. Vishnumurthy, V., Chandrakumar, S., Sirer, E.G.: Karma: A secure economic framework for

peer-to-peer resource sharing. In: Workshop on Economics of Peer-to-Peer Systems (2003)

33. Wikipedia: List of cryptocurrencies.

https://en.wikipedia.org/wiki/List_of_cryptocurrencies

,

retrieved Oct. 2013

34. Yang, B., Garcia-Molina, H.: PPay: Micropayments for peer-to-peer systems. In: Proceedings

of the 10th ACM conference on Computer and communications security. pp. 300–310. ACM

(2003)

---

Document Outline

•  Majority is not Enough:  Bitcoin Mining is Vulnerable