Majority is not Enough: Bitcoin Mining is Vulnerable

4.1

State Probabilities

We analyze this state machine to calculate its probability distribution over the

state space. We obtain the following equations:























αp

0

= (1 − α)p

1

+ (1 − α)p

2

p

0

= (1 − α)p

1

αp

1

= (1 − α)p

2

∀k ≥ 2 : αp

k

= (1 − α)p

k+1

∞

k=0

p

k

+ p

0

= 1

(1)

Solving (

1

) (See our full report for details [

14

]), we get:

p

0

=

α − 2α

2

α(2α

3

− 4α

2

+ 1)

(2)

p

0

=

(1 − α)(α − 2α

2

)

1 − 4α

2

+ 2α

3

(3)

p

1

=

α − 2α

2

2α

3

− 4α

2

+ 1

(4)

∀k ≥ 2 : p

k

=

α

1 − α

k−1

α − 2α

2

2α

3

− 4α

2

+ 1

(5)

4.2

Revenue

The probability distribution over the state space provides the foundation for

analyzing the revenue obtained by the selfish pool and by the honest miners.

The revenue for finding a block belongs to its miner only if this block ends up

in the main chain. We detail the revenues on each event below.

(a) Any state but two branches of length 1, pools finds a block. The pool appends

one block to its private branch, increasing its lead on the public branch by

one. The revenue from this block will be determined later.

=⇒

or

=⇒

(b) Was two branches of length 1, pools finds a block. The pool publishes its

secret branch of length two, thus obtaining a revenue of two.

=⇒

=⇒

---

(c) Was two branches of length 1, others find a block after pool head. The pool

and the others obtain a revenue of one each — the others for the new head,

the pool for its predecessor.

=⇒

(d) Was two branches of length 1, others find a block after others’ head. The

others obtain a revenue of two.

=⇒

(e) No private branch, others find a block. The others obtain a revenue of one,

and both the pool and the others start mining on the new head.

(f) Lead was 1, others find a block. Now there are two branches of length one,

and the pool publishes its single secret block. The pool tries to mine on its

previously private head, and the others split between the two heads. Denote

by γ the ratio of others that choose the non-pool block.

The revenue from this block cannot be determined yet, because it depends

on which branch will win. It will be counted later.

=⇒

=⇒

(g) Lead was 2, others find a block. The others almost close the gap as the lead

drops to 1. The pool publishes its secret blocks, causing everybody to start

mining at the head of the previously private branch, since it is longer. The

pool obtains a revenue of two.

=⇒

=⇒

(h) Lead was more than 2, others win. The others decrease the lead, which

remains at least two. The new block (say with number i) will end outside

the chain once the pool publishes its entire branch, therefore the others

obtain nothing. However, the pool now reveals its i’th block, and obtains a

revenue of one.

=⇒

=⇒

---

We calculate the revenue of the pool and of the others from the state prob-

abilities and transition frequencies:

r

others

=

Case

(c)

p

0

· γ(1 − α) · 1 +

Case

(d)

p

0

· (1 − γ)(1 − α) · 2 +

Case

(e)

p

0

· (1 − α) · 1

(6)

r

pool

=

Case

(b)

p

0

· α · 2 +

Case

(c)

p

0

· γ(1 − α) · 1 +

Case

(g)

p

2

· (1 − α) · 2 +

Case

(h)

P [i > 2](1 − α) · 1

(7)

As expected, the intentional branching brought on by selfish mining leads

the honest miners to work on blocks that end up outside the blockchain. This, in

turn, leads to a drop in the total block generation rate with r

pool

+ r

others

< 1.

The protocol will adapt the mining difficulty such that the mining rate at the

main chain becomes one block per 10 minutes on average. Therefore, the actual

revenue rate of each agent is the revenue rate ratio; that is, the ratio of its

blocks out of the blocks in the main chain. We substitute the probabilities from

(

2

)-(

5

) in the revenue expressions of (

6

)-(

7

) to calculate the pool’s revenue for

0 ≤ α ≤

1

2

:

R

pool

=

r

pool

r

pool

+ r

others

= · · · =

α(1 − α)

2

(4α + γ(1 − 2α)) − α

3

1 − α(1 + (2 − α)α)

.

(8)

4.3

Simulation

To validate our theoretical analysis, we compare its result with a Bitcoin pro-

tocol simulator. The simulator is constructed to capture all the salient Bitcoin

mining protocol details described in previous sections, except for the cryptop-

uzzle module that has been replaced by a Monte Carlo simulator that simulates

block discovery without actually computing a cryptopuzzle. In this experiment,

we use the simulator to simulate 1000 miners mining at identical rates. A subset

of 1000α miners form a pool running the Selfish-Mine algorithm. The other min-

ers follow the Bitcoin protocol. We assume block propagation time is negligible

compared to mining time, as is the case in reality. In the case of two branches

of the same length, we artificially divide the non-pool miners such that a ratio

of γ of them mine on the pool’s branch and the rest mine on the other branch.

Figure

2

shows that the simulation results match the theoretical analysis.

4.4

The Effect of α and γ

When the pool’s revenue given in Equation

8

is larger than α, the pool will earn

more than its relative size by using the Selfish-Mine strategy. Its miners will

therefore earn more than their relative mining power. Recall that the expression

is valid only for 0 ≤ α ≤

1

2

. We solve this inequality and phrase the result in the

following observation:

Observation 1 For a given γ, a pool of size α obtains a revenue larger than its

relative size for α in the following range:

1 − γ

3 − 2γ

< α <

1

2

.

(9)

---