Why Selfish Mining Is More Dangerous Than You Think

Table of Links

Abstract and 1. Introduction

1.1 Related Work

2. Preliminaries

   2.1 System Model

   2.2 Selfish Mining Objective

   2.3 Markov Decision Processes

3. Selfish Mining Attack

   3.1 Overview

   3.2 Formal Model

   3.3 Formal Analysis

   3.4 Key Features and Limitations

4. Experimental Evaluation

5. Conclusion, Acknowledgments, and References

A. NAS Mining Objectives

B. Efficient Proof Systems

C. Proof of Theorem 3.1

3.2 Formal Model

We now formally model our selfish mining attack as an MDP. Recall, an MDP M = (𝑆, 𝐴, 𝑃, 𝑠0) is an ordered tuple where 𝑆 is a finite set of states, 𝐴 is a finite set of actions overloaded to specify for each state 𝑠 ∈ 𝑆 the set of available actions 𝐴(𝑠) ⊆ 𝐴, 𝑃 : 𝑆 × 𝐴 → D (𝑆) is a probabilistic transition function, and 𝑠0 ∈ 𝑆 is the initial state. Hence, in order to formally model our attack as an MDP, we need to define each of these four objects.

Model parameters. Our MDP model uses as a basis the System Model that we defined in Section 2.2. Thus, it is parameterized by the parameters 𝑝 and 𝛾, but also by three additional parameters specific the selfish mining attack itself. We use N to denote the set of all positive integers:

• Relative resource of the adversary. 𝑝 ∈ [0, 1] denotes the fraction of resources in the blockchain owned by the adversary.

• Switching probability. 𝛾 ∈ [0, 1] denotes the probability of an honest miner switching to a newly revealed adversarial chain that is of the same length as the main chain.

• Attack depth. 𝑑 ∈ N denotes the depth of the adversary’s attack on the chain, i.e. the number of last blocks on the main chain on which the adversary mines private forks.

• Forking number. 𝑓 ∈ N denotes the number of private forks that the adversary creates at each of the last 𝑑 public blocks.

• Maximal fork length. 𝑙 ∈ N denotes the maximal private fork length. Introducing this parameter ensures that our MDP model consists of finitely many states, which is necessary since existing mean-payoff MDP solvers are applicable to finite state MDPs [18, 20]. We discuss the implications of this in Section 3.4.

MDP definition. We define the MDP M = (𝑆, 𝐴, 𝑃, 𝑠0) as follows:

• States. The state space is defined via

i.e. each state is defined as a triple (C, O, type) where C defines the current blockchain configuration (i.e. topology) up to depth 𝑑, O specifies who owns each block in the main chain up to depth 𝑑 (honest miners or the adversary), and type specifies whether the parties are still mining or some party has mined a new block and is supposed to add it to the blockchain. In particular:

– For each 1 ≤ 𝑖 ≤ 𝑑 and 1 ≤ 𝑗 ≤ 𝑓 , we use C [𝑖, 𝑗] to denote the length of the 𝑗-th private fork mined by the adversary at the depth 𝑖 block on the main chain. Each private fork has length at most 𝑙, so we impose that each 𝐶[𝑖, 𝑗] ∈ {0, . . . ,𝑙 }.

– For each 1 ≤ 𝑖 < 𝑑, we use O [𝑖] to denote who owns the block at depth 𝑖 in the main chain. In particular, O [𝑖] = honest if the block is owned by honest miners and O [𝑖] = adversary if the block is owned by the adversary.

– Finally, type specifies whether a new block to be added to the blockchain is still being mined in which case we set type = mining, or if some party has generated the proof and gets to add a new block in which case we set type = honest and type = adversary, respectively.

• Actions. The action space is defined via

Intuitively, mine prescribes that the adversary should not release any private forks and should simply continue mining new blocks. On the other hand, release𝑖,𝑗,𝑘 prescribes that the adversary should publish the first 𝑘 blocks of the 𝑗-th private fork mined on the block at depth 𝑖 in the main chain. The set of available actions at each MDP state 𝑠 = (C, O, type) is defined as follows:

– If type = mining, then 𝐴(𝑠) = {mine}.

– If type ∈ {honest, adversary}, then 𝐴(𝑠) = {mine} ∪ {release𝑖,𝑗,𝑘 | 𝑘 ≤ C [𝑖, 𝑗]}, where the condition 𝑘 ≤ C [𝑖, 𝑗] simply ensures that the length of the published part of the private fork cannot exceed the total length of the private fork.

• Transition Function. Finally, we define the transition function 𝑃 : 𝑆 × 𝐴 → D (𝑆). Let 𝑠 = (C, O, type) and 𝑎 ∈ 𝐴(𝑠) be an action available in 𝑠:

– If type = mining, then we must have 𝑎 = mine as the only available action. The next state in the MDP is chosen probabilistically, based on who mines the next block and where. Recall, the honest miners own 1−𝑝 fraction of resources in the blockchain and are mining on the main chain only, whereas the adversary owns 𝑝 fraction of resources but mines on at most 𝑑 · 𝑓 private forks. Note that the adversary will concurrently mine on top of each private fork starting at public blocks up to depth 𝑑 in the main chain, as well as on top of each public block up to depth 𝑑 at which not all 𝑓 private works were initiated. Hence:

– If type = honest and 𝑎 = release𝑖,𝑗,𝑘 , then the adversary publishes the first 𝑘 blocks of the 𝑗-th private fork mined on the block at depth 𝑖 in the main chain. Hence, the next MDP state is determined by the chain which gets accepted as the main chain by honest miners. If the newly published fork is strictly longer than the main chain, the honest miners accept it as the new main chain with probability 1. Otherwise, if the main chain and the published fork have the same length, then a “race” between the chains happens and the published fork becomes the main chain with switching probability 𝛾. Hence:

where C′ and C′′ are defined as the previous case. Note that if the published fork and the main chain are of the same length, the race cannot happen as the last block was mined by the adversary and enough time has passed for all the miners to receive the public chain