Table of Links
Abstract and 1. Introduction
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
A. NAS Mining Objectives
B. Efficient Proof Systems
C. Proof of Theorem 3.1
A NAS MINING OBJECTIVES
Adversarial mining strategies in blockchains based on efficient proof systems can be analysed with respect to several adversarial goals. Here, we outline three such goals: double spending, short and long term selfish-mining.
The first objective is double spending, where one considers the probability of an adversarial chain overtaking the public, honest chain [8, 29] (see Figure 3). Here the goal of the adversary is to rapidly and secretly grow a sufficiently long private chain such that this private chain eventually overtakes the honest chain, this way removing a presumably confirmed transaction. What “sufficiently” long means depends on the confirmation time in the chain, e.g., in Bitcoin one generally assumes a transaction that is six blocks deep in the chain to be confirmed.
The second objective, “short-term selfish mining”, considered eschews the goal of overtaking the honest chain completely and focuses simply on finding an adversarial mining strategy that is more profitable for the adversary rather than following the stipulated mining protocol [12] (see Figure 4). The profitability of an adversarial mining strategy under this objective is measured by the total number of adversarial blocks on the main chain. Like in the analyses of selfish mining strategies under the first objective, analyses of strategies under this second objective also focus on finding the largest fraction of adversarial resources the blockchain can tolerate in order to be secure under such adversarial strategies.
B EFFICIENT PROOF SYSTEMS
Proof of stake. PoStake is a block leader election protocol where a leader is selected with probability proportionate to the amount of stake (i.e., coins) they hold in the ledger at the selection time. Thus, a user with 𝑝 ∈ [0, 1] fraction of stake is elected with probability proportionate to 𝑝. Examples of longest-chain blockchains based on PoStake are Ouroboros [9] and post-merge Ethereum [1].
Proofs of space and time. Proof of Space (PoSpace) is a protocol between a prover and a verifier whereby the prover stores some data and, upon a challenge from the verifier, has to return a solution to the challenge that involves reading a small portion of the data. The consensus protocol of blockchains based on PoST [8] use both PoSpace challenges as well as verifiable delay functions [4, 25, 30] (VDFs). VDFs are functions that are inherently sequential to compute but the correctness of computation is efficiently verifiable. As such, the process of mining blocks in such blockchains depends not
only on the amount of space allocated to compute PoSpace challenges, but also on the amount of VDFs to compute VDF challenges.
Authors:
(1) Krishnendu Chatterjee, IST Austria, Austria ([email protected]);
(2) Amirali Ebrahimzadeh, Sharif University of Technology, Iran ([email protected]);
(3) Mehrdad Karrabi, IST Austria, Austria ([email protected]);
(4) Krzysztof Pietrzak, IST Austria, Austria ([email protected]);
(5) Michelle Yeo, National University of Singapore, Singapore ([email protected]);
(6) Ðorđe Žikelić, Singapore Management University, Singapore ([email protected]).
