Table of Links Abstract and 1. Introduction Abstract and 1. Introduction 1.1 Related Work 1.1 Related Work Preliminaries
2.1 System Model
2.2 Selfish Mining Objective
2.3 Markov Decision Processes


Selfish Mining Attack
3.1 Overview
3.2 Formal Model
3.3 Formal Analysis
3.4 Key Features and Limitations


Experimental Evaluation


Conclusion, Acknowledgments, and References Preliminaries
2.1 System Model
2.2 Selfish Mining Objective
2.3 Markov Decision Processes Preliminaries 2.1 System Model 2.1 System Model 2.2 Selfish Mining Objective 2.2 Selfish Mining Objective 2.3 Markov Decision Processes 2.3 Markov Decision Processes Selfish Mining Attack
3.1 Overview
3.2 Formal Model
3.3 Formal Analysis
3.4 Key Features and Limitations Selfish Mining Attack 3.1 Overview 3.1 Overview 3.2 Formal Model 3.2 Formal Model 3.3 Formal Analysis 3.3 Formal Analysis 3.4 Key Features and Limitations 3.4 Key Features and Limitations Experimental Evaluation Experimental Evaluation Experimental Evaluation Conclusion, Acknowledgments, and References Conclusion, Acknowledgments, and References Conclusion, Acknowledgments, and References A. NAS Mining Objectives A. NAS Mining Objectives B. Efficient Proof Systems B. Efficient Proof Systems C. Proof of Theorem 3.1 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: Model parameters. • Relative resource of the adversary. 𝑝 ∈ [0, 1] denotes the fraction of resources in the blockchain owned by the adversary. • Relative resource of 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. • Switching probability • 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. • Attack depth. • Forking number. 𝑓 ∈ N denotes the number of private forks that the adversary creates at each of the last 𝑑 public blocks. • Forking number • 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. • Maximal fork length. MDP definition. We define the MDP M = (𝑆, 𝐴, 𝑃, 𝑠0) as follows: MDP definition • States. The state space is defined via States 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 Actions 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 𝑠: • Transition Function – 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 Authors:
(1) Krishnendu Chatterjee, IST Austria, Austria (krishnendu.chatterjee@ist.ac.at);
(2) Amirali Ebrahimzadeh, Sharif University of Technology, Iran (ebrahimzadeh.amirali@gmail.com);
(3) Mehrdad Karrabi, IST Austria, Austria (mehrdad.karrabi@ist.ac.at);
(4) Krzysztof Pietrzak, IST Austria, Austria (krzysztof.pietrzak@ist.ac.at);
(5) Michelle Yeo, National University of Singapore, Singapore (mxyeo@nus.edu.sg);
(6) Ðorđe Žikelić, Singapore Management University, Singapore (dzikelic@smu.edu.sg). Authors: Authors: (1) Krishnendu Chatterjee, IST Austria, Austria (krishnendu.chatterjee@ist.ac.at); (2) Amirali Ebrahimzadeh, Sharif University of Technology, Iran (ebrahimzadeh.amirali@gmail.com); (3) Mehrdad Karrabi, IST Austria, Austria (mehrdad.karrabi@ist.ac.at); (4) Krzysztof Pietrzak, IST Austria, Austria (krzysztof.pietrzak@ist.ac.at); (5) Michelle Yeo, National University of Singapore, Singapore (mxyeo@nus.edu.sg); (6) Ðorđe Žikelić, Singapore Management University, Singapore (dzikelic@smu.edu.sg). This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Why Selfish Mining Is More Dangerous Than You Think

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

5 Ways to Measure Privacy Risks in Text Data

This Study Uses Markov Models to Break Blockchain Fairness

A Model for Blockchain Mining Under Adversarial Conditions

Modeling Selfish Mining with Markov Decision Processes

The Math Behind Selfish Mining and Reward Allocation

5 Ways to Measure Privacy Risks in Text Data

This Study Uses Markov Models to Break Blockchain Fairness

A Model for Blockchain Mining Under Adversarial Conditions

Modeling Selfish Mining with Markov Decision Processes

The Math Behind Selfish Mining and Reward Allocation

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps