# Fully Automated Selfish Mining Analysis in Efficient Proof Systems
Blockchains

Krishnendu Chatterjee  0000-0002-4561-241X<EMAIL_ADDRESS>IST
AustriaAustria ,  Amirali Ebrahimzadeh  0000-0002-9887-4341
<EMAIL_ADDRESS>Sharif University of TechnologyIran ,  Mehrdad
Karrabi  0009-0007-5253-9170<EMAIL_ADDRESS>IST AustriaAustria ,
Krzysztof Pietrzak  0000-0002-9139-1654<EMAIL_ADDRESS>IST
AustriaAustria ,  Michelle Yeo  0009-0001-3676-4809<EMAIL_ADDRESS>National
University of SingaporeSingapore and  Đorđe Žikelić  0000-0002-4681-1699
<EMAIL_ADDRESS>Singapore Management UniversitySingapore

(2024; 2024)

###### Abstract.

We study selfish mining attacks in longest-chain blockchains like Bitcoin, but
where the proof of work is replaced with efficient proof systems – like proofs
of stake or proofs of space – and consider the problem of computing an optimal
selfish mining attack which maximizes expected relative revenue of the
adversary, thus minimizing the chain quality. To this end, we propose a novel
selfish mining attack that aims to maximize this objective and formally model
the attack as a Markov decision process (MDP). We then present a formal
analysis procedure which computes an $\epsilon$-tight lower bound on the
optimal expected relative revenue in the MDP and a strategy that achieves this
$\epsilon$-tight lower bound, where $\epsilon>0$ may be any specified
precision. Our analysis is fully automated and provides formal guarantees on
the correctness. We evaluate our selfish mining attack and observe that it
achieves superior expected relative revenue compared to two considered
baselines.

In concurrent work [Sarenche FC’24] does an automated analysis on selfish
mining in _predictable_ longest-chain blockchains based on efficient proof
systems. Predictable means the randomness for the challenges is fixed for many
blocks (as used e.g., in Ouroboros), while we consider _unpredictable_
(Bitcoin-like) chains where the challenge is derived from the previous block.

Blockchain, Formal Methods, Efficient Proof Systems, Selfish Mining, Markov
Decision Process

††copyright: acmcopyright††journalyear: 2024††doi:
XXXXXXX.XXXXXXX††conference: ACM Symposium on Principles of Distributed
Computing; June 17–21, 2024; Nantes, France††isbn:
978-1-4503-XXXX-X/18/06††ccs: Security and privacy Logic and
verification††ccs: Security and privacy Cryptanalysis and other attacks††ccs:
Security and privacy Distributed systems security††journalyear:
2024††copyright: rightsretained††conference: ACM Symposium on Principles of
Distributed Computing; June 17–21, 2024; Nantes, France††booktitle: ACM
Symposium on Principles of Distributed Computing (PODC ’24), June 17–21, 2024,
Nantes, France††doi: 10.1145/3662158.3662769††isbn: 979-8-4007-0668-4/24/06

##  1\. Introduction

#### Bitcoin.

Blockchain protocols were proposed as a solution to achieve consensus over
some states (e.g., financial transactions) in a distributed and permissionless
(i.e., everyone can participate in securing the chain) setting. Participants
in blockchain protocols add data into blocks, which are then appended to the
blockchain with some probability that depends on the underlying consensus
protocol. The earliest and most commonly adopted consensus protocol is proof
of work (PoW), which also forms the basis of the Bitcoin blockchain protocol
(Nakamoto, 2008).

Proof of work. The parties that maintain a PoW blockchain like Bitcoin are
called miners. The general idea is that in order to add a block to the chain,
the miners derive a computationally hard but easily verifiable puzzle from the
tip of the chain. To add a block to the chain, this block must contain a
solution to this puzzle. This mechanism ensures that attacking the chain, in
particular rewriting past blocks in a double spending attack, is
computationally very expensive. In Bitcoin, the puzzle is a hashcash style PoW
(Back, 1997), with parameters being a difficulty level $D$ and a global hash
function (e.g., SHA256). A newly generated block can only be added to the
chain if the hash of the new block, the previous block, the miner’s public key
and some nonce give a value that is less than the current difficulty $D$. To
mine a block in Bitcoin, miners will continuously generate different nonces
and hash them until they find a nonce that passes the threshold. The lucky
miner that first finds a block broadcasts it across the network, where other
miners can easily verify the validity of the nonce. The Bitcoin protocol
specifies that miners should always work towards extending the longest chain
they are aware of, hence such chains are called “longest-chain blockchains”.
An alternative approach is chains based on Byzantine Fault Tolerance like
Algorand (Chen and Micali, 2019) where randomly rotating committees approve
blocks to be added.

Efficient proof systems. As an alternative to PoW, several other consensus
protocols based on efficient proof systems have been proposed (David et al.,
2017; Park et al., 2018; Cohen and Pietrzak, 2023). Generally, we say a “proof
of X” is efficient if computing a proof for a random challenge is very cheap
assuming one has the resource X. The most popular and best investigated
efficient proofs are Proofs of Stake (PoStake) as e.g., used in Ouroboros
(David et al., 2017) or post-merge Ethereum. Here the coins recorded in the
blockchain are the resource. Another proposal of an actual physical resource
are Proofs of Space (PoSpace) (Dziembowski et al., 2015), where the resource
is disk-space. The first proposal for a PoSpace based chain was Spacemint
(Park et al., 2018). The first deployed chain was the Chia network (Cohen and
Pietrzak, 2023), it uses PoSpace in combination with verifiable delay
functions (VDFs) to address some security challenges, and thus is referred to
as a Proofs of Space and Time (PoST) based chain. See Appendix B for more
details of blockchains based on efficient proof systems that we consider in
our work.

Selfish mining. There are various security properties we want from longest-
chain blockchains, the most important ones being persistence and liveness
(Garay et al., 2015). Informally, persistence means that entries added to the
chain will remain there forever, while liveness means that the chain remains
available. A less obvious requirement is fairness, in the sense that a party
that contributes a $p$ fraction of the resource (hashing power in PoW, space
in PoST, staked coins in PoStake) should contribute a $p$ fraction of the
blocks, and thus get a $p$ fraction of the rewards.

It was first observed in (Eyal and Sirer, 2018) that Bitcoin is not fair in
this sense due to _selfish mining_ attacks. In selfish mining, attackers mine
blocks but occasionally selectively withhold these (so the honest miners
cannot mine on top of those) to later release them, overtaking the honest
chain and thus orphaning honest blocks. In doing so, the attackers can reduce
the _chain quality_ of the blockchain (Eyal and Sirer, 2018), this measure
quantifies the fraction of blocks contributed by an adversarial miner.

Although the analysis of selfish mining and its impact on chain quality is
well-studied in Bitcoin and other PoW-based blockchains (Eyal and Sirer, 2018;
Sapirshtein et al., 2016; Zur et al., 2020; Hou et al., 2021), a thorough
analysis of optimal selfish mining attacks in blockchains based on efficient
proof systems is difficult due the fact that the computational cost of
generating proofs is low in these systems. This gives rise to several issues
that in the PoStake setting are generally referred to as the “nothing-at-
stake” (NaS) problem. 111We will slightly abuse terminology in our work and
continue to use the terms “mining” and “miners” from PoW-based chains also
when discussing chains based on efficient proof systems even though when using
PoStake this is sometimes referred to as “proposing” and “proposers” (but it
is not coherent, some works like (Ferreira and Weinberg, 2021; Ferreira et
al., 2022) use mining) while in PoSpace it was suggested to use the term
“farming” and “farmers”.

The security vs predictability dilemma. Assume one would naïvely replace PoW
in Bitcoin with an efficient proof system like PoStake. As computing proofs is
now cheap, an adversarial miner can try to extend blocks at different depths
(not just on the tip of the longest chain), growing private trees at each
depth. If they manage to create a tree of depth $d$ that starts less than $d$
blocks deep in the public chain, releasing the longest path in this tree will
force the honest miners to switch to this path. Such “tree growing” attacks
can be prevented by diverting from Bitcoin-like protocols, and instead of
using the block at depth $i$ to derive the challenge for the block at depth
$i+1$, one uses some fixed randomness for a certain number of consecutive
blocks. Unfortunately, this creates a new security issue as an adversary can
now predict when in the future they will be able to create blocks (Brown-Cohen
et al., 2018; Bagaria et al., 2022). We note that this approach is used in the
PoStake-based Ouroboros (David et al., 2017) chain, where one only creates a
fresh challenge every five days. An extreme in the other direction is the
PoSpace-based Spacemint (Park et al., 2018) chain or an early proposal of the
PoST-based Chia chain (Cohen and Pietrzak, 2019) which, like Bitcoin, derive
the challenge from the previous block (the deployed Chia design (Cohen and
Pietrzak, 2023) uses a fresh challenge every 10 minutes, or 32 blocks).

Limitations of previous analyses. The persistence, i.e., security against
_double spending_ attacks, in predictable (Ouroboros-like) and unpredictable
(Bitcoin-like) longest-chain blockchains is pretty well understood (Bagaria et
al., 2022). In particular, using the “tree growing” attack outlined above, an
adversary can “amplify” its resources in an unpredictable protocol by a factor
of $e\approx 2.72$. Thus, security requires that the adversary controls less
than $\frac{1}{1+e}\approx 0.269$ fraction of the total resources. In a
predictable protocol, it is sufficient for the adversary to have
$<\frac{1}{2}$ of the resource. This is better, but being predictable opens
new attack vectors like bribing attacks. Unfortunately, the security of
blockchain protocols based on efficient proof systems in the face of _selfish
mining_ attacks is a lot less understood. In particular, previous analyses in
this area suffer mainly from two limitations:

  1. (1)

(Model) Although there have also been some very recent works analysing
_selfish mining_ attacks in blockchains based on efficient proof systems
(Cohen and Pietrzak, 2023; Wang et al., 2019; Fan and Zhou, 2017; Ferreira and
Weinberg, 2021; Hou et al., 2021; Sarenche et al., 2024), these analyses so
far have only focused on predictable protocols.

  2. (2)

(Methodology) Furthermore, they either consider different adversarial
objectives (Cohen and Pietrzak, 2023; Wang et al., 2019; Fan and Zhou, 2017;
Ferreira and Weinberg, 2021) or use deep reinforcement learning to obtain
selfish mining strategies (Hou et al., 2021; Sarenche et al., 2024). However,
deep reinforcement learning only empirically maximizes the objective and does
not provide _formal guarantees_ on the quality (lower or upper bound) of
learned strategies.

Our approach. In this work, we present the first analysis of selfish mining in
unpredictable longest-chain blockchains based on efficient proof systems.
Recall that in such chains the challenge for each block is determined by the
previous block. At each time step, the adversary has to decide whether to mine
new blocks or to publish one of their private forks which is longer than the
public chain. Our analysis is concerned with finding the optimal sequence of
mining and fork reveal actions that the adversary should follow in order to
maximize the expected relative revenue (i.e., the ratio of the expected
adversarial blocks in the main chain when following a given strategy compared
to the total number of blocks in the chain). Note that this is a challenging
problem. Since at each time step the adversary can choose between mining new
blocks and publishing any of its private chains, the strategy space of the
adversary is exponential in the number of privately mined forks which makes
the manual formal analysis intractable.

To overcome this challenge, we model our selfish mining attack as a finite-
state Markov Decision Process (MDP) (Puterman, 1994). We then present a formal
analysis procedure which, given a precision parameter $\epsilon>0$, computes

  * •

an $\epsilon$-tight lower bound on the optimal expected relative revenue that
a selfish mining strategy in the MDP can achieve, and

  * •

a selfish mining strategy achieving this $\epsilon$-tight lower bound.

At the core of our formal analysis procedure lies a reduction from the problem
of computing an optimal selfish mining strategy under the expected relative
revenue objective to computing an optimal strategy in the MDP under a mean-
payoff objective for a suitably designed reward function. While we defer the
details on MDPs and mean-payoff objectives to Section 2, we note that solving
mean-payoff finite-state MDPs is a classic and well-studied problem within the
formal methods community for which efficient (polynomial-time) algorithms
exist (Puterman, 1994; Filar and Vrieze, 2012) and there are well-developed
tools that implement them together with further optimizations (Hensel et al.,
2022; Kwiatkowska et al., 2011). These algorithms are fully automated and
provide formal guarantees on the correctness of their outputs, and the formal
analysis of our selfish mining attack naturally inherits these desirable
features.

Contributions. Our contributions can be summarized as follows:

  1. (1)

We study selfish mining in unpredictable efficient proof systems blockchain
protocols where the adversary’s goal is to maximize expected relative revenue
and thus minimize chain quality.

  2. (2)

We propose a novel selfish mining attack that optimizes the expected relative
revenue in unpredictable blockchain protocols based on efficient proof
systems. We formally model the attack as an MDP.

  3. (3)

We present a formal analysis procedure for our selfish mining attack. Given a
precision parameter $\epsilon>0$, our formal analysis procedure computes an
$\epsilon$-tight lower bound on the optimal expected relative revenue in the
MDP together with a selfish mining strategy that achieves it. The procedure is
fully automated and provides formal guarantees on its correctness.

  4. (4)

Our formal analysis is flexible to changes in system model parameter values.
For instance, it allows us to tweak system model parameters and study their
impact on the optimal expected relative revenue that selfish mining can
achieve in a fully automated fashion and without the need to develop novel
analyses for different parameter values. This is in stark contrast to formal
analyses whose correctness is proved manually, see Section 3.4 for a more
detailed discussion.

  5. (5)

We implement the MDP model and the formal analysis procedure and
experimentally evaluate the quality of the expected relative revenue achieved
by the computed selfish mining strategy. We compare our selfish mining attack
to two baselines: (1) honest mining strategy and (2) a direct extension of the
PoW selfish mining strategy of (Eyal and Sirer, 2018) to the setting of
blockchains based on efficient proof systems. Our experiments show that our
selfish mining strategy achieves higher expected relative revenue compared to
the two baselines.

A Remark on the Model. While the selfish mining attacks analyzed in this paper
apply to PoStake, PoSpace and PoST based longest-chain blockchains, they
capture PoST better than PoStake and PoSpace as we will shortly outline now.
Due to the use of VDFs, PoST is “strongly unpredictable” in the sense that a
miner cannot predict when they will be able to extend any block, while PoStake
and PoSpace are “weakly unpredictable” in the sense that a miner can predict
when they will find blocks on top of their own (but not other) blocks.
Moreover, in PoST a malicious miner must run a VDF on top of every block they
try to extend, while in PoStake or PoSpace this comes basically for free. The
class of selfish mining attacks analyzed in this paper does not exploit “weak
unpredictability” (a necessary assumption for PoST, but not PoStake or
PoSpace) and, to be able to give automated bounds, we also assume a bound on
the number of blocks one tries to extend, which is a realistic assumption for
PoST (as each block requires a VDF) but less so for PoSpace or PoStake.

###  1.1. Related Work

#### Selfish mining in Bitcoin.

One of the motivations behind the initial design of Bitcoin and other PoW
blockchain systems is fairness. That is, a miner controlling $p\in[0,1]$
proportion of resources should generate blocks at the rate of $p$. This led to
the initial analysis claiming Bitcoin is fair when the total resource $p$
owned by adversarial miners is bounded from above by $\frac{1}{2}$ (Garay et
al., 2015). Nevertheless, (Eyal and Sirer, 2018) outlined an attack called
“selfish mining” in Bitcoin which shows that even for $p<\frac{1}{2}$ it is
possible to generate blocks at a rate strictly greater than $p$, implying that
Bitcoin is inherently “unfair”. The attack secretly forks the main chain and
mines blocks in a private, unannounced chain. These blocks are only revealed
when the private chain is longer than the main chain, thus forcing the honest
miners to switch from the main chain to the private chain. This causes the
honest miners to waste their computational resources on the now shorter public
chain. It is shown in (Eyal and Sirer, 2018) that due to selfish mining, the
largest amount of adversarial resources that can be tolerated while ensuring
the security of Bitcoin is $\frac{1}{3}$ in the optimistic setting where
honest miners propagate their blocks first, and $\frac{1}{4}$ if both honest
and adversarial miners propagate their blocks first with equal probability.

NaS selfish mining. NaS selfish mining can be studied under several different
adversarial objectives, see Appendix A for a thorough discussion and
comparison of these objectives. The objective we consider in our work is the
expected relative revenue of the adversary, which is also considered in the
analysis of (Sarenche et al., 2024) for PoStake. There have been earlier
analyses that consider several other objectives, however. The works of (Wang
et al., 2019) and (Cohen and Pietrzak, 2023) studied the probability of an
adversarial coalition overtaking the honest chain and showed respectively that
under this objective, the largest fraction of adversarial resources that can
be tolerated in PoStake based blockchains is $\frac{1}{1+e}\approx 0.269$, and
between $\frac{1}{1+e}<p<\frac{1}{2}$ for Chia, a PoST-based blockchain. The
work of (Fan and Zhou, 2017) studied selfish mining strategies in PoStake
blockchains under the objective of finding strategies that give the
adversarial coalition a larger payoff compared to following the honest
strategy. They showed that the expected advantage of the adversary when
growing a private tree from the genesis block is $e$ times larger than the
expected revenue of following the honest strategy, implying that the maximum
fraction of adversarial resource that can be tolerated to be secure under this
strategy and objective is $\frac{1}{e}\approx 0.37$.

Optimal selfish mining strategies. There have been some works that go beyond
proposing and analysing specific selfish mining strategies to actually
claiming the _optimality_ of these strategies. The work of (Sapirshtein et
al., 2016) modelled the Bitcoin protocol as an MDP and proposed a method using
binary search to solve it approximately in order to find an optimal selfish
mining strategy. (Zur et al., 2020) improved the search method in (Sapirshtein
et al., 2016), resulting in a method that finds an optimal strategy but with
an order of magnitude less computation. (Hou et al., 2021) and (Sarenche et
al., 2024) use deep reinforcement learning to automate discovery of attack
strategies in Bitcoin and Nakamoto-PoStake, respectively, but without
guarantees on optimality. Finally, (Ferreira et al., 2022) suggested modelling
mining strategies in PoStake as an MDP and using an MDP solver to find optimal
selfish mining strategies. However, due to the infinite size of their MDP,
finding even an approximately optimal solution is undecidable.

##  2\. Preliminaries

###  2.1. System Model

We define a formal model for blockchain systems which we will consider
throughout this work. The model describes how block mining proceeds and is
parametrized by several parameters. Different parameter value instantiations
then give rise to formal models for blockchains based on PoW, PoStake, or PoST
protocols. We assume the miners in the blockchain protocol are either
adversarial or honest. Honest miners all follow a prescribed protocol, whereas
the adversarial miners work (i.e. pool resources) together in a coalition.

System model. We assume that block mining proceeds in discrete time steps, as
in many discrete-time models of PoW (Pass et al., 2017; Gazi et al., 2020) and
PoStake (David et al., 2017) protocols. For a miner that owns a fraction
$p\in[0,1]$ of the total resources in the blockchain and that can mine up to
$k>0$ blocks at any given time step, we define $(p,k)$-mining as follows: the
probability of mining a block at the given time step is proportional to
$p\cdot k$, and the maximum number of blocks which are available for mining is
$k$. One can think of $k$ as some further constraints on the number of blocks
a miner can mine on at any given point in time, e.g. due to the number of VDFs
they own in PoST. Hence, $(p,1)$-mining corresponds to mining in PoW based
blockchains, $(p,k)$-mining for $k<\infty$ to mining in PoST based blockchains
with $k$ VDFs, and $(p,\infty)$-mining to mining in PoStake based blockchains.

Adversarial and broadcast model. Let $p\in[0,1]$ denote the fraction of
resources in the chain owned by the adversarial coalition. We assume the
adversarial coalition participates in $(p,k)$-mining, and the honest miners
participate in $(1-p,1)$-mining, where the only block the honest miners mine
on at any time step is the most recent block on the longest public chain. When
there is a tie, i.e., two longest chains are gossiped through the network, the
honest miners will mine on the chain which is gossiped to them first. In such
situations, $\gamma\in[0,1]$ denotes the switching probability, i.e., the
probability of honest miners switching to the adversary’s chain.

###  2.2. Selfish Mining Objective

#### Chain quality.

Chain quality is a measure of the number of honest blocks in any consecutive
segment of the blockchain. A blockchain protocol is said to satisfy
$(\mu,\ell)$-chain quality if for any segment of the chain of length $\ell$,
the fraction of honest blocks in that segment is at least $\mu$ (Garay et al.,
2015).

Selfish mining objective. Let $\sigma$ denote an adversarial mining strategy.
The selfish mining objective we analyse in our work is the _expected relative
revenue_ of the adversary. Formally, let $\textsc{revenue}_{\mathcal{A}}$ and
$\textsc{revenue}_{\mathcal{H}}$ denote the number of adversarial and honest
blocks in the main chain respectively. The expected relative revenue (ERRev)
of the adversary under strategy $\sigma$ is defined as

$\texttt{ERRev}(\sigma)=\mathbb{E}^{\sigma}\Big{[}\frac{\textsc{revenue}_{\mathcal{A}}}{\textsc{revenue}_{\mathcal{A}}+\textsc{revenue}_{\mathcal{H}}}\Big{]}$

Note that the chain quality of the blockchain under an adversarial mining
strategy $\sigma$ is simply $1-\texttt{ERRev}(\sigma)$, hence our selfish
mining objective captures the expected change in the chain quality.

###  2.3. Markov Decision Processes

As mentioned in Section 1, we will reduce the problem of computing optimal
selfish mining strategies for the expected relative revenue objective to
solving MDPs with mean-payoff objectives. In what follows, we recall the
necessary notions on MDPs and formally define the mean-payoff objectives. For
a finite set $X$, we use $\mathcal{D}(X)$ to denote the set of all probability
distributions over $X$.

Markov decision process. A Markov Decision Process (MDP) (Puterman, 1994) is a
tuple $\mathcal{M}=(S,A,P,s_{0})$ where

  * •

$S$ is a finite set of states, with $s_{0}\in S$ being the initial state,

  * •

$A$ is a finite set of actions, overloaded to specify for each state $s\in S$
the set of available actions $A(s)\subseteq A$, and

  * •

$P:S\times A\rightarrow\mathcal{D}(S)$ is a transition function, prescribing
to each $(s,a)\in S\times A$ a probability distribution over successor states.

A strategy in $\mathcal{M}$ is a recipe to choose an action given a history of
states and actions, i.e. it is a function $\sigma:(S\times A)^{\ast}\times
S\rightarrow\mathcal{D}(A)$. In general, strategy can use randomization and
memory. A positional strategy uses neither randomization nor memory, i.e. it
is a function $\sigma:S\rightarrow A$. We denote by $\Sigma$ and $\Sigma^{p}$
the set of all strategies and all positional strategies in $\mathcal{M}$.
Given a strategy $\sigma$, it induces a probability measure
$\mathbb{P}^{\sigma}[\cdot]$ in $\mathcal{M}$ with an associated expectation
operator $\mathbb{E}^{\sigma}[\cdot]$.

Mean-payoff objective. A reward function in $\mathcal{M}$ is a function
$r:S\times A\times S\rightarrow\mathbb{R}$ which to each state-action-state
triple prescribes a real-valued reward. Given an MDP $\mathcal{M}$, a reward
function $r$ and a strategy $\sigma$, we define the mean-payoff of $\sigma$
with respect to $r$ via

$\texttt{MP}(\sigma)=\mathbb{E}^{\sigma}\Big{[}\liminf_{N\rightarrow\infty}\frac{\sum_{n=1}^{N}r_{n}}{N}\Big{]},$

where $r_{n}=r_{n}(s_{n},a_{n},s_{n+1})$ is the reward incurred at step $n$.

The mean-payoff MDP problem is to compute the maximal mean-payoff that a
strategy in the MDP can achieve. A classic result in MDP analysis is that
there always exists a positional strategy $\sigma^{\ast}$ that achieves
maximal mean-payoff in the MDP, i.e. there is $\sigma^{\ast}\in\Sigma^{p}$
such that
$\texttt{MP}(\sigma^{\ast})=\max_{\sigma\in\Sigma^{p}}\texttt{MP}(\sigma)=\sup_{\sigma\in\Sigma}\texttt{MP}(\sigma)$
(Puterman, 1994). Furthermore, the optimal positional strategy and the mean-
payoff that it achieves can be efficiently computed in polynomial time
(Puterman, 1994; Filar and Vrieze, 2012).

##  3\. Selfish Mining Attack

###  3.1. Overview

#### Motivation.

In order to motivate our selfish mining attack, we first recall the classic
selfish mining attack strategy in Bitcoin (Eyal and Sirer, 2018). Recall, the
goal of the selfish mining strategy is to mine a private chain that overtakes
the public chain (see Figure 1(a)). Selfish miners secretly fork the main
chain and mine privately, adding blocks to a private, unannounced chain. These
blocks are only revealed when the length of the private chain catches up with
that of the main chain, forcing the honest miners to switch from the main to
the private chain and waste computational resources. While in PoW blockchains
each party mines on one block, in blockchains based on efficient proof systems
parties can mine on multiple blocks due to ease of generating proofs. Our
selfish mining attack exploits this observation by creating multiple private
forks concurrently.

(a) Classic selfish mining attack in Bitcoin.

(b) An illustration of our selfish mining attack with depth $d=4$ and $f=2$.
Green boxes denote the main chain and white boxes denote potential blocks that
can be mined under attack strategy.

Outline of the attack. Our selfish mining attack proceeds with the adversary
creating several private forks at different blocks in the main chain, see
Figure 1(b) for an illustration. Rather than forking on the most recent block
alone, the adversary creates up to $f$ forks on each of the last $d$ blocks on
the main chain. Here, $f$ and $d$ are parameters of the attack where $f$ is
the number of forks created at each public block and $d$ represents the depth
of the adversary’s attack on the chain. One can view $d$ as the persistence
parameter of the blockchain, which represents the depth at which earlier
blocks are practically guaranteed to remain in the main chain (Garay et al.,
2015). At each time step, the adversary can either perform a

  1. (1)

mining action, i.e. attempt to mine a new block, or

  2. (2)

fork reveal action, i.e. publicly announce one of the private forks whose
length is greater than or equal to that of the main chain.

Deciding on the optimal order of mining and fork reveal actions that the
adversary should perform at each time step towards maximizing its expected
relative revenue is a highly challenging problem. This is because, at each
time step, the party to mine the next block is chosen probabilistically (see
our System Model in Section 2.2), and the process results in a system with an
extremely large number of states. For any given precision parameter
$\epsilon>0$, our analysis will provide both an _$\epsilon$ -optimal strategy_
among selfish mining strategies that the adversary can follow, together with
the _exact value_ of the expected relative revenue guaranteed by this
strategy.

Formal model of the attack. The goal of our analysis is to find an optimal
selfish mining strategy which maximizes the expected relative revenue of the
adversary. Note that this is a sequential decision making problem, since the
optimal strategy under the above selfish mining setting must at every decision
step optimally choose whether to perform a mining or a fork release action.
Hence, in order to analyze this problem, in Section 3.2 we formally model our
problem as an MDP. The state space of the MDP consists of all possible
configurations of the main chain and private forks with the initial state
corresponding to the time step at which the selfish mining attack is
initiated. The action space of the MDP consists of the mining action as well
as one fork release action for each private fork whose length is greater than
or equal to that of the main chain. Finally, the probabilistic transition
function of the MDP captures the probabilistic process that generates and
determines ownership (honest or adversarial) of new blocks to be added to the
blockchain, as well as the process of determining the new main chain whenever
the adversary publishes one or more private forks of equal length.

Formal analysis of the attack. Recall, the objective of our selfish mining
attack is to maximize the expected relative revenue of the adversary. To do
this, in Section 3.3 we define a class of reward functions in the MDP
constructed in Section 3.2. We show that, for any $\epsilon>0$, we can compute
an $\epsilon$-optimal selfish mining strategy in the MDP and the exact value
of the expected relative revenue that it guarantees by solving the mean-payoff
MDP with respect to a reward function belonging to the class of constructed
reward functions. We solve mean-payoff MDPs by using off-the-shelf tools as
mentioned in Section 2.3. Our analysis yields a fully automated method for
computing $\epsilon$-optimal strategies and values of the expected relative
revenue that provides formal guarantees on the correctness of its results.

###  3.2. Formal Model

We now formally model our selfish mining attack as an MDP. Recall, an MDP
$\mathcal{M}=(S,A,P,s_{0})$ is an ordered tuple where $S$ is a finite set of
states, $A$ is a finite set of actions overloaded to specify for each state
$s\in S$ the set of available actions $A(s)\subseteq A$, $P:S\times
A\rightarrow\mathcal{D}(S)$ is a probabilistic transition function, and
$s_{0}\in S$ 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 $p$ and
$\gamma$, but also by three additional parameters specific the selfish mining
attack itself. We use $\mathbb{N}$ to denote the set of all positive integers:

  * •

Relative resource of the adversary. $p\in[0,1]$ denotes the fraction of
resources in the blockchain owned by the adversary.

  * •

Switching probability. $\gamma\in[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. $d\in\mathbb{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. $f\in\mathbb{N}$ denotes the number of private forks that the
adversary creates at each of the last $d$ public blocks.

  * •

Maximal fork length. $l\in\mathbb{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 (Hensel et al., 2022; Kwiatkowska et al.,
2011). We discuss the implications of this in Section 3.4.

MDP definition. We define the MDP $\mathcal{M}=(S,A,P,s_{0})$ as follows:

  * •

States. The state space is defined via

$\begin{split}S=\Big{\\{}(\mathcal{C},\mathcal{O},\textsc{type})\,\Big{|}\,&\mathcal{C}\in\\{0,\dots,l\\}^{d\times
f},\mathcal{O}\in\\{\textsc{honest},\textsc{adversary}\\}^{d-1},\\\
&\textsc{type}\in\\{\textsc{mining},\textsc{honest},\textsc{adversary}\\}\Big{\\}},\end{split}$

i.e. each state is defined as a triple
$(\mathcal{C},\mathcal{O},\textsc{type})$ where $\mathcal{C}$ defines the
current blockchain configuration (i.e. topology) up to depth $d$,
$\mathcal{O}$ specifies who owns each block in the main chain up to depth $d$
(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\leq i\leq d$ and $1\leq j\leq f$, we use $\mathcal{C}[i,j]$ to
denote the length of the $j$-th private fork mined by the adversary at the
depth $i$ block on the main chain. Each private fork has length at most $l$,
so we impose that each $C[i,j]\in\\{0,\dots,l\\}$.

    * –

For each $1\leq i<d$, we use $\mathcal{O}[i]$ to denote who owns the block at
depth $i$ in the main chain. In particular, $\mathcal{O}[i]=\textsc{honest}$
if the block is owned by honest miners and $\mathcal{O}[i]=\textsc{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 $\textsc{type}=\textsc{mining}$, or if
some party has generated the proof and gets to add a new block in which case
we set $\textsc{type}=\textsc{honest}$ and $\textsc{type}=\textsc{adversary}$,
respectively.

  * •

Initial State. Initial state
$s_{0}=(\mathcal{C}_{0},\mathcal{O}_{0},\textsc{type}_{0})$ corresponds to the
time step at which the selfish mining attack is initiated. Hence, we set
$\mathcal{C}_{0}=[0]^{d\times f}$ since the length of each private fork is
initially $0$, $\mathcal{O}_{0}=[\textsc{honest}]^{d}$ and
$\textsc{type}_{0}=\textsc{mining}$.

  * •

Actions. The action space is defined via

$A=\\{\textsc{mine}\\}\cup\Big{\\{}\textsc{release}_{i,j,k}\,\Big{|}\,1\leq
i\leq d,1\leq j\leq f,1\leq k\leq l\Big{\\}}.$

Intuitively, mine prescribes that the adversary should not release any private
forks and should simply continue mining new blocks. On the other hand,
$\textsc{release}_{i,j,k}$ prescribes that the adversary should publish the
first $k$ blocks of the $j$-th private fork mined on the block at depth $i$ in
the main chain. The set of available actions at each MDP state
$s=(\mathcal{C},\mathcal{O},\textsc{type})$ is defined as follows:

    * –

If $\textsc{type}=\textsc{mining}$, then $A(s)=\\{\textsc{mine}\\}$.

    * –

If $\textsc{type}\in\\{\textsc{honest},\textsc{adversary}\\}$, then
$A(s)=\\{\textsc{mine}\\}\cup\\{\textsc{release}_{i,j,k}\,|\,k\leq\mathcal{C}[i,j]\\}$,
where the condition $k\leq\mathcal{C}[i,j]$ 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 $P:S\times
A\rightarrow\mathcal{D}(S)$. Let $s=(\mathcal{C},\mathcal{O},\textsc{type})$
and $a\in A(s)$ be an action available in $s$:

    * –

If $\textsc{type}=\textsc{mining}$, then we must have $a=\textsc{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-p$ fraction of resources in the blockchain and are mining on the main chain
only, whereas the adversary owns $p$ fraction of resources but mines on at
most $d\cdot f$ private forks. Note that the adversary will concurrently mine
on top of each private fork starting at public blocks up to depth $d$ in the
main chain, as well as on top of each public block up to depth $d$ at which
not all $f$ private works were initiated. Hence:

      * *

Denote by $\sigma$ the total number of blocks that the adversary is mining on.
For each $1\leq i\leq d$ and $1\leq j\leq f$, if the $j$-th private fork on
the public block at depth $i$ in the main chain is not empty, adversary mines
a new block on it and the MDP moves to
$s_{\textsc{adv}}^{i,j}=(\mathcal{C}^{\prime},\mathcal{O},\textsc{adversary})$
with probability

$P(s,a)(s_{\textsc{adv}}^{i,j})=\frac{p}{1-p+p\cdot\sigma}.$

Here, $\mathcal{C}^{\prime}$ coincides with $\mathcal{C}$ on all entries
except $\mathcal{C}^{\prime}[i,j]=\min\\{\mathcal{C}[i,j]+1,l\\}$, where the
new block is found on top of the $j$-th private fork on the block at depth
$i$. The minimum ensures that new block is not added if the length of the fork
would exceed $l$.

Moreover, if at least one private fork on the public block at depth $i$ in the
main chain is empty, adversary mines a block on it to start a new private fork
and the MDP moves to
$s_{\textsc{adv}}^{i,j^{\ast}}=(\mathcal{C}^{\prime\prime},\mathcal{O},\textsc{adversary})$
with probability $\frac{p}{1-p+p\cdot\sigma}$, where $j^{\ast}$ is the
smallest index of a private fork that is currently empty at the depth $i$
public block and $\mathcal{C}^{\prime\prime}$ coincides with $\mathcal{C}$ on
all entries except $\mathcal{C}^{\prime\prime}[i,j^{\ast}]=1$.

      * *

Honest miners add a new block to the main chain and the MDP moves to state
$s_{\textsc{honest}}=([0]^{f}\cdot\mathcal{C}[1:d-1],[\textsc{honest}]\cdot\mathcal{O}[1:d-2],\textsc{honest})$
with probability

$P(s,a)(s_{\textsc{honest}})=\frac{1-p}{1-p+p\cdot\sigma}.$

where $\sigma$ is as defined above. We use $[0]^{f}\cdot\mathcal{C}[1:d-1]$ to
denote the $d\times f$ matrix whose first column consists of zeros
(representing empty private forks on the newly added block) and the remaining
columns are the first $d-1$ columns of $\mathcal{C}$. Similarly,
$[\textsc{honest}]\cdot\mathcal{O}[1:d-2]$ denotes the vector whose first
component is honest corresponding to the new block, followed by the first
$d-2$ components of $\mathcal{O}$.

    * –

If $\textsc{type}\neq\textsc{mining}$ but $a=\textsc{mine}$, then the
adversary continues mining new blocks and the MDP moves to
$s_{\textsc{mine}}=(\mathcal{C},\mathcal{O},\textsc{mining})$ with probability

$P(s,a)(s_{\textsc{mine}})=1.$

    * –

If $\textsc{type}=\textsc{honest}$ and $a=\textsc{release}_{i,j,k}$, then the
adversary publishes the first $k$ blocks of the $j$-th private fork mined on
the block at depth $i$ 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 $\gamma$. Hence:

      * *

If the published fork is longer than the main chain, the honest miners switch
to the fork and the MDP moves to
$s_{\textsc{accept}}=(\mathcal{C}^{\prime}\cdot[0]^{(min(d,k)-1)\times
f}\cdot\mathcal{C}^{\prime\prime},[\textsc{adversary}]^{min(d-1,k)}\cdot\mathcal{O}[k+1:d-1],\textsc{mining})$
with probability

$P(s,a)(s_{\textsc{accept}})=1.$

Here, $\mathcal{C}^{\prime}$ is a $(1\times f)$-dimensional vector with $0$
entries except that $\mathcal{C}^{\prime}[1,1]=\mathcal{C}[i,j]-k$. So, the
adversary keeps the part of the published private fork consisting of the last
$\mathcal{C}[i,j]-k$ blocks that have not been revealed. On the other hand,
$\mathcal{C}^{\prime\prime}$ coincides with $\mathcal{C}[k+1:d]$ on all
entries except that $\mathcal{C}^{\prime\prime}[i,j]=0$. Hence, the adversary
keeps and continues mining on all usable private forks, with one new private
fork of initial length $0$ being created to replace the published fork. Note,
$\mathcal{O}[k+1:d-1]$ and $\mathcal{C}[k+1:d]$ are empty if $k+1>d-1$ and
$k+1>d$, respectively.

      * *

Otherwise, if the published fork and the main chain are of the same length, a
race happens and honest miners switch to the published fork with probability
$\gamma$. and the new block will be mined by adversary with probability $p$.
So, the MDP moves to
$s_{\textsc{accept}}=(\mathcal{C}^{\prime}\cdot[0]^{(min(d,k)-1)\times
f}\cdot\mathcal{C}^{\prime\prime},[\textsc{adversary}]^{min(d-1,k)}\cdot\mathcal{O}[k+1:d-1],\textsc{mining})$
with probability

$P(s,a)(s_{\textsc{accept}})=\gamma,$

where $\mathcal{C}^{\prime}$ and $\mathcal{C}^{\prime\prime}$ are as above,
and moves to $s_{\textsc{reject}}=(\mathcal{C},\mathcal{O},\textsc{mining})$
with probability

$P(s,a)(s_{\textsc{reject}})=1-\gamma.$

    * –

Finally, if $\textsc{type}=\textsc{adversary}$, $a=\textsc{release}_{i,j,k}$
and the published private fork is longer than the main chain, the MDP moves to
$s_{\textsc{accept}}=(\mathcal{C}^{\prime}\cdot[0]^{(min(d,k)-1)\times
f}\cdot\mathcal{C}^{\prime\prime},[\textsc{adversary}]^{min(d-1,k)}\cdot\mathcal{O}[k+1:d-1],\textsc{mining})$
with probability

$P(s,a)(s_{\textsc{accept}})=1.$

where $\mathcal{C}^{\prime}$ and $\mathcal{C}^{\prime\prime}$ 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.

###  3.3. Formal Analysis

#### Goal of the analysis.

We now show how to compute the optimal expected relative revenue together with
an adversarial strategy achieving it in the MDP $\mathcal{M}=(S,A,P,s_{0})$,
up to an arbitrary precision parameter $\epsilon>0$. Formally, for each
strategy $\sigma$ in $\mathcal{M}$, let

$\texttt{ERRev}(\sigma)=\mathbb{E}^{\sigma}\Big{[}\frac{\textsc{revenue}_{\mathcal{A}}}{\textsc{revenue}_{\mathcal{A}}+\textsc{revenue}_{\mathcal{H}}}\Big{]}$

be the expected relative revenue under adversarial strategy $\sigma$, i.e. the
relative ratio of the number of blocks accepted on the main chain belonging to
the adversary and to honest miners. Moreover, let

$\texttt{ERRev}^{\ast}=\sup_{\text{strategy }\sigma\text{ in
}\mathcal{M}}\texttt{ERRev}(\sigma)$

be the optimal expected relative revenue that an adversarial strategy can
attain. Given a precision parameter $\epsilon>0$, our goal is to compute

  1. (1)

a lower bound
$\overline{\texttt{ERRev}}\in[\texttt{ERRev}^{\ast}-\epsilon,\texttt{ERRev}^{\ast}]$,
and

  2. (2)

a strategy $\overline{\sigma}$ in $\mathcal{M}$ such that
$\texttt{ERRev}(\overline{\sigma})\in[\texttt{ERRev}^{\ast}-\epsilon,\texttt{ERRev}^{\ast}]$.

We do this by defining a class of reward functions in the MDP $\mathcal{M}$
and showing that, for any value of the precision parameter $\epsilon>0$, we
can compute the above by solving the mean-payoff MDP with respect to a reward
function belonging to this class. Our analysis draws insight from that of
(Sapirshtein et al., 2016), which considered selfish mining in PoW blockchains
and also reduced reasoning about expected relative revenue to solving mean-
payoff MDPs with respect to suitably defined reward functions. However, in
contrast to (Sapirshtein et al., 2016), we consider selfish mining in
efficient proof systems in which the adversary can mine on multiple blocks,
meaning that our design of reward functions and the analysis require
additional care.

Reward function definition. The key challenge in designing the reward function
is that the main chain and the blocks on it may change whenever the adversary
publishes a private fork. Hence, we design the reward function to incur
positive (resp. negative) reward whenever a block owned by the adversary
(resp. honest miners) is accepted at the depth strictly greater than $d$ in
the main chain. Since the adversary only mines and publishes private forks
mined on blocks up to depth $d$ in the main chain, this means that blocks
beyond depth $d$ are guaranteed to remain on the main chain.

Formally, for each $\beta\in[0,1]$, we define $r_{\beta}:S\times A\times
S\rightarrow\mathbb{R}$ to be a reward function in $\mathcal{M}$ which to each
state-action-state triple $(s,a,s^{\prime})$ assigns the reward:

  * •

$1-\beta$, for each block belonging to the adversary accepted at depth greater
than $d$ as a result of performing the action;

  * •

$-\beta$, for each block belonging to honest miners accepted at depth greater
than $d$ as a result of performing the action.

This definition can be formalized by following the same case by case analysis
as in the definition of the transition function in Section 3.2. For the
interest of space, we omit the formal definition. For each $\beta$ and
strategy $\sigma$ in the MDP, let $\texttt{MP}_{\beta}(\sigma)$ be the mean-
payoff under $\sigma$ with respect to the reward function $r_{\beta}$, and let
$\texttt{MP}_{\beta}^{\ast}=\sup_{\sigma}\texttt{MP}_{\beta}(\sigma)$. Note
that, since for each state-action-state triple the value of the reward
$r_{\beta}(s,a,s^{\prime})$ is monotonically decreasing in $\beta\in[0,1]$, we
have that $\texttt{MP}_{\beta}^{\ast}$ is also monotonically decreasing in
$\beta\in[0,1]$.

Formal analysis. Our formal analysis is based on the following theorem. For
clarity of exposition, we defer the proof of the theorem to Appendix C . For
every $\epsilon>0$, the theorem shows how to relate the optimal expected
relative revenue in the MDP and $\epsilon$-optimal strategies to the optimal
mean-payoff and $\epsilon$-optimal strategies under the reward function
$r_{\beta}$ for a suitably chosen value of $\beta$.

###### Theorem 3.1.

We have $\texttt{MP}^{\ast}_{\beta^{\ast}}=0$ if and only if
$\beta^{\ast}=\texttt{ERRev}^{\ast}$. Moreover, if $\epsilon>0$ and
$\beta\in[\texttt{ERRev}^{\ast}-\epsilon,\texttt{ERRev}^{\ast}]$, then for any
strategy $\sigma$ such that
$\texttt{MP}_{\beta}(\sigma)=\texttt{MP}^{\ast}_{\beta}$ we have
$\texttt{ERRev}(\sigma)\in[\texttt{ERRev}^{\ast}-\epsilon,\texttt{ERRev}^{\ast}]$.

Algorithm 1 Formal analysis procedure

Input Precision parameter $\epsilon>0$, MDP parameters $p,d,f,l,\gamma$

$\mathcal{M}\leftarrow$ MDP constructed as in Section 3.2

$\beta_{\text{low}},\beta_{\text{up}}\leftarrow 0,1$

while $\beta_{\text{up}}-\beta_{\text{low}}\geq\epsilon$ do

$\beta\leftarrow(\beta_{\text{low}}+\beta_{\text{up}})/2$

$\texttt{MP}_{\beta}^{\ast},\sigma_{\beta}\leftarrow$ solve mean-payoff MDP
$\mathcal{M}$ with reward $r_{\beta}$

if $\texttt{MP}_{\beta}^{\ast}<0$ then

$\beta_{\text{up}}\leftarrow\beta$

else

$\beta_{\text{low}}\leftarrow\beta$

end if

end while

$\overline{\texttt{ERRev}}\leftarrow\beta_{\text{low}}$

$\overline{\sigma}\leftarrow$ solve mean-payoff MDP $\mathcal{M}$ with reward
$r_{\beta_{\text{low}}}$

Return Expected relative revenue $\overline{\texttt{ERRev}}$, strategy
$\overline{\sigma}$

Following Theorem 3.1, we compute $\overline{\texttt{ERRev}}$ and
$\overline{\sigma}$ for a given precision $\epsilon>0$ as follows. Algorithm 1
shows the pseudocode of our formal analysis. The algorithm performs binary
search in $\beta\in[0,1]$ in order to find a value of $\beta$ for which
$\beta\in[\texttt{ERRev}^{\ast}-\epsilon,\texttt{ERRev}^{\ast}]$. In each
iteration of the binary search, the algorithm uses an off-the-shelf mean-
payoff MDP solver to compute the optimal mean-payoff
$\texttt{MP}^{\ast}_{\beta}$ and a strategy $\sigma_{\beta}$ attaining it.
Upon binary search termination, we have
$\texttt{ERRev}^{\ast}\in[\beta_{\text{low}},\beta_{\text{up}}]$, since
$\texttt{MP}^{\ast}_{\beta}$ is a monotonically decreasing function in $\beta$
and since $\texttt{MP}^{\ast}_{\beta^{\ast}}=0$ if and only if
$\beta^{\ast}=\texttt{ERRev}^{\ast}$ by the first part of Theorem 3.1. Hence,
as the binary search terminates when
$\beta_{\text{up}}-\beta_{\text{low}}<\epsilon$, we conclude that
$\overline{\texttt{ERRev}}=\beta_{\text{low}}\in[\texttt{ERRev}^{\ast}-\epsilon,\texttt{ERRev}^{\ast}]$.
Moreover, since $\overline{\sigma}$ is optimal for the mean-payoff objective
with reward $r_{\beta_{\text{low}}}$ and since
$\beta_{\text{low}}\in[\texttt{ERRev}^{\ast}-\epsilon,\texttt{ERRev}^{\ast}]$,
by the second part of Theorem 3.1 we have
$\texttt{ERRev}(\overline{\sigma})\in[\texttt{ERRev}^{\ast}-\epsilon,\texttt{ERRev}^{\ast}]$.

###### Corollary 3.2 (Correctness of the analysis).

Let $\epsilon>0$. Suppose that Algorithm 1 returns a value
$\overline{\texttt{ERRev}}$ and a strategy $\overline{\sigma}$ in
$\mathcal{M}$. Then, we have
$\overline{\texttt{ERRev}},\texttt{ERRev}(\overline{\sigma})\in[\texttt{ERRev}^{\ast}-\epsilon,\texttt{ERRev}^{\ast}]$.

###### Corollary 3.3 (Formal lower bound).

Suppose that Algorithm 1 returns a value $\overline{\texttt{ERRev}}$ and a
strategy $\overline{\sigma}$. Then, there exists a selfish mining attack in
the blockchain that achieves the expected relative revenue of at least
$\overline{\texttt{ERRev}}$.

###  3.4. Key Features and Limitations

#### Key features.

The key features of our selfish mining attack and formal analysis are as
follows:

  1. (1)

Fully automated analysis. Manual (i.e. non-automated) analysis of optimal
selfish mining attacks is already challenging and technically involved for PoW
blockchains, where the adversary only grows a single private fork (Eyal and
Sirer, 2018). Hence, it would be even more difficult and potentially
intractable in blockchains based on efficient proof systems. By modelling our
selfish mining attack as an MDP and reducing the analysis to solving mean-
payoff MDPs, we leverage existing methods for formal analysis of MDPs to
obtain a fully automated analysis procedure, thus avoiding the necessity for
tedious manual analyses.

  2. (2)

Formal guarantees on correctness. Our analysis provides formal guarantees on
the correctness of its output. Again, this is achieved by formally reducing
our problem to solving mean-payoff MDPs for which exact algorithms with formal
correctness guarantees are available (Hensel et al., 2022; Kwiatkowska et al.,
2011).

  3. (3)

Flexibility of the analysis. Our analysis is agnostic to the values of system
model and attack parameters and it is flexible to their changes. Hence, it
allows us to tweak the parameter values and study their impact on the optimal
expected relative revenue, while preserving formal guarantees on the
correctness. To illustrate the flexibility, observe that:

     * •

If the attack depth $d$, forking number $f$ or maximal fork length $l$ of the
attack change, then both the state space and the action space of the MDP
change.

     * •

If the relative resource of the adversary $p$ or the switching probability
$\gamma$ change, then the transition function of the MDP changes.

     * •

As we show in our experiments in Section 4, a change in any of these parameter
values results in a change in the optimal expected relative revenue that the
adversary can achieve.

The flexibility of our analysis is thus a significant feature, since it again
avoids the need for tedious manual analyses for different parameter values
that give rise to different MDPs.

Limitations. While our formal analysis computes an optimal selfish mining
strategy in the MDP up to a desired precision, note that there still exist
selfish mining attacks that do not correspond to any strategy in our MDP
model. Hence, the strategy computed by our method is optimal only with respect
to the subclass of strategies captured by the MDP model. There are two key
reasons behind the incompleteness of our MDP model:

  1. (1)

Bounded forks. In order to ensure finiteness of our MDP model, we impose an
upper bound $l$ on the maximal length of each private fork. This means that
the adversary cannot grow arbitrarily long private forks. Since the
probability of the adversary being able to grow extremely long private forks
is low, we believe that this limitation does not significantly impact the
expected relative revenue of selfish mining strategy under this restriction.

  2. (2)

Disjoint forks vs fork trees. Our attack grows private forks on different
blocks in the main chain. However, rather than growing multiple disjoint
private forks, a more general class of selfish mining attacks would be to
allow growing private trees. We stick to disjoint private forks in order to
preserve computational efficiency of our analysis, since allowing the
adversary to grow private trees would result in our MDP states needing to
store information about each private tree topology, which would lead to a huge
blow-up in the size of the MDP. In contrast, storing disjoint private forks
only requires storing fork lengths, resulting in smaller MDP models.

We conclude by noting that, while our formal analysis is incomplete due to
considering a subclass of selfish mining attacks, the formal guarantees
provided by our analysis still ensure that we compute a true lower bound on
the expected relative revenue that a selfish mining attack achieves.

##  4\. Experimental Evaluation

We implement the MDP model and the formal analysis procedure presented in
Section 3 and perform an experimental evaluation towards answering the
following research questions (RQs):

  1. RQ1

What is the expected relative revenue that our selfish mining strategy
achieves? How does it compare to direct extensions of classic selfish mining
attacks on PoW blockchains (Eyal and Sirer, 2018) or to mining honestly?

  2. RQ2

How do different values of the System Model parameters impact the expected
relative revenue that our selfish mining attack can achieve? The System Model
parameters include the relative resource of the adversary $p\in[0,1]$ and the
switching probability $\gamma\in[0,1]$.

(a) $\gamma=0$

(b) $\gamma=0.25$

(c) $\gamma=0.5$

(d) $\gamma=0.75$

(e) $\gamma=1$

Figure 2. Comparison of expected relative revenue ERRev as a function of
adversarial resource achieved by our attack and the baselines for different
values of $\gamma$.

Baselines. To answer these RQs, we compare our selfish mining attack against
two baselines:

  1. (1)

Honest mining strategy. This is the strategy extending only the leading block
of the main chain.

  2. (2)

Single-tree selfish mining attack. This is the attack strategy that exactly
follows the classic selfish mining attack in Bitcoin proposed in (Eyal and
Sirer, 2018), however it grows a private tree fork rather than a private
chain. Analogously as in (Eyal and Sirer, 2018), the adversary publishes the
private tree whenever the length of the main chain catches up with the depth
of the private tree. We omit the formal model of this baseline due to space
limitations. We also use this baseline to empirically evaluate how severe is
the second limitation discussed in Section 3.4.

Experimental setup. We perform an experimental comparison of our attack and
the two baselines for the values of the adversarial relative resource
$p\in[0,0.3]$ (in increments of $0.01$) and the switching probability
$\gamma\in\\{0,0.25,0.5,0.75,1\\}$. As for the parameters of each selfish
mining attack:

  * •

For our selfish mining attack, we set the maximal length of private forks
$l=4$ and consider all combinations
$(d,f)\in\\{(1,1),(2,1),(2,2),(3,2),(4,2)\\}$ of the values of the attack
depth $d$ and the forking number $f$.

  * •

For the single-tree selfish mining attack baseline, we set the maximal depth
of the private tree $l=4$ to match our maximal private fork length, and the
maximal width of the private tree $f=5$.

All experiments were run on Ubuntu 20, 2.80GHz 11th Gen Intel(R) Core(TM)
i7-1165G7 CPU, 16 GB RAM, and 16 GB SWAP SSD Memory. For solving mean-payoff
MDPs, we use the probabilistic model checker Storm (Hensel et al., 2022), a
popular MDP analysis tool within the formal methods community222 Refer to our
github repository for our implementation details:
https://github.com/mehrdad76/Automated-Selfish-Mining-Analysis-in-EPS-
Blockchains .

Attack Type |  Parameters |  Time (s)
---|---|---
Our Attack |  $d=1,f=1$ |  3.8
Our Attack |  $d=2,f=1$ |  5.4
Our Attack |  $d=2,f=2$ |  61.7
Our Attack |  $d=3,f=2$ |  2295.3
Our Attack |  $d=4,f=2$ |  77761.7
Single-tree Selfish Mining |  $f=5$ |  2406.8
Table 1. Runtimes for various attack types and parameter settings and
$\gamma=0.5$.

Results. Table 1 shows the runtimes of both our selfish mining attack as well
as the single-tree selfish mining attack given various parameter settings and
for a fixed switching parameter of $\gamma=0.5$. We only show timings for
$\gamma=0.5$ as we found the runtimes of our experiments to be very similar
across all $\gamma$ parameter settings. As can be seen from Table 1,
increasing the depth of the attack increases the runtime of our evaluation by
an order of magnitude due to the exponential increase in state space.

Experimental results are shown in Figure 2, showing plots for each
$\gamma\in\\{0,0.25,0.5,0.75,1\\}$. As we can see from the plots, our selfish
mining attack consistently achieves higher expected relative revenue ERRev
than both baselines for each value of $\gamma$, except when $d=1$ and $f=1$.
Indeed, already for $d=2$ and $f=1$ when the adversary grows a single private
fork on the first two blocks in the main chain, our attack achieves higher
ERRev than both baselines. This shows that growing private forks at two
different blocks already provides a more powerful attack than growing a much
larger private tree at a single block. Hence, our results indicate that
growing disjoint private forks rather than trees is not a significant
limitation, justifying our choice to grow private forks towards making the
analysis computationally tractable.

The attained ERRev grows significantly as we increase $d$ and $f$ and allow
the adversary to grow more private forks. In particular, for $d=4$, $f=2$, and
relative adversarial resource $p=0.3$, our attack achieves ERRev that is
larger by at least $0.2$ than that of both baselines, for all values of the
switching probability $\gamma$. This indicates a significant advantage of
selfish mining attacks in efficient proof systems blockchains compared to PoW,
as the ability to simultaneously grow multiple private forks on multiple
blocks translates to a much larger ERRev. Our results suggest that further
study of techniques to reduce the advantage of the adversary when mining on
several blocks is important in order to maintain reasonable chain quality for
efficient proof systems blockchains.

Finally, we notice that larger $\gamma$ values correspond to larger ERRev in
our strategies. This is expected, as larger $\gamma$ values introduce bias in
the likelihood of the adversarial chain becoming the main chain. This is most
pertinently observed in the case of $d=f=1$: since $d=f=1$ corresponds to a
strategy that only mines a private block on the leading block in the main
chain, the only way to deviate from honest mining is to withhold a freshly
mined block and reveal it together with the occurrence of a freshly mined
honest block. As we can see in the plots, for $\gamma<0.5$ the achieved ERRev
of the strategy with $d=f=1$ corresponds to that of honest mining and the two
lines in plots mostly overlap, whereas this strategy only starts to pay off
for $\gamma>0.5$ and for the proportion of resource $p>0.25$. Altogether, this
suggests that further and careful analysis of the control of the adversary
over the broadcast network as well as the fork choice breaking rule is
necessary.

Key takeaways. The key takeaways of our experimental evaluation are as
follows:

  * •

Our selfish mining attack achieves significantly higher ERRev than both
baselines, reaching up to $0.2$ difference in ERRev. Thus, our results
strongly suggest that growing private forks at multiple blocks is much more
advantageous than growing all forks on the first block in the main chain.

  * •

Our results suggest that growing private trees rather than disjoint private
forks would not lead to a significant improvement in the adversary’s ERRev.
Hence, the second limitation of our attack discussed in Section 3.4 does not
seem to be significant.

  * •

Our results suggest that enhancing security against selfish mining attacks in
efficient proof system blockchains requires further and careful analysis of
the control that the adversary has over the broadcast system. In particular,
for large values of the switching probability $\gamma$, even the simplest
variant of our attack with $d=1$ and $f=1$ starts to pay off when $p>0.25$.

##  5\. Conclusion

We initiated the study of optimal selfish mining strategies for unpredictable
blockchain protocols based on efficient proof systems. To this end, we
considered a selfish mining objective corresponding to changes in chain
quality and proposed a novel selfish mining attack that aims to maximize this
objective. We formally modeled our attack as an MDP strategy and we presented
a formal analysis procedure for computing an $\epsilon$-tight lower bound on
the optimal expected relative revenue in the MDP and a strategy that achieves
it for a specified precision $\epsilon>0$. The procedure is fully automated
and provides formal guarantees on the correctness of the computed bound.

We believe that our work opens several exciting lines for future research. We
highlight two particular directions. First, our formal analysis only allows us
to compute lower bounds on the expected relative revenue that an adversary can
achieve. A natural direction of future research would be to consider computing
upper bounds on the optimal expected relative revenue for fixed resource
amounts. Second, as discussed in Section 3.4, our formal analysis only
computes $\epsilon$-tight lower bounds on the expected relative revenue by
following a strategy in our MDP model. However, our model in Section 3.2
introduces assumptions such as growing private forks instead of trees and
bounding the maximal length of each fork for tractability purposes. It would
be interesting to study whether these assumptions could be relaxed while still
providing formal correctness guarantees.

###### Acknowledgements.

This work was supported in part by the ERC-2020-CoG 863818 (FoRM-SMArt) grant
and the MOE-T2EP20122-0014 (Data-Driven Distributed Algorithms) grant.

## References

  * (1)
  * eth (2022) 2022\.  https://ethereum.org/en/roadmap/merge/.
  * Back (1997) Adam Back. 1997\.  Hashcash.  http://hashcash.org/.
  * Bagaria et al. (2022) Vivek Kumar Bagaria, Amir Dembo, Sreeram Kannan, Sewoong Oh, David Tse, Pramod Viswanath, Xuechao Wang, and Ofer Zeitouni. 2022\.  Proof-of-Stake Longest Chain Protocols: Security vs Predictability. In _Proceedings of the 2022 ACM Workshop on Developments in Consensus, ConsensusDay 2022, Los Angeles, CA, USA, 7 November 2022_ , Jorge M. Soares, Dawn Song, and Marko Vukolic (Eds.). ACM, 29–42.  https://doi.org/10.1145/3560829.3563559
  * Boneh et al. (2018) Dan Boneh, Joseph Bonneau, Benedikt Bünz, and Ben Fisch. 2018.  Verifiable Delay Functions.  _IACR Cryptol. ePrint Arch._ (2018), 601.  https://eprint.iacr.org/2018/601
  * Brown-Cohen et al. (2018) Jonah Brown-Cohen, Arvind Narayanan, Christos-Alexandros Psomas, and S. Matthew Weinberg. 2018\.  Formal Barriers to Longest-Chain Proof-of-Stake Protocols.  _CoRR_ abs/1809.06528 (2018).  arXiv:1809.06528 http://arxiv.org/abs/1809.06528
  * Chen and Micali (2019) Jing Chen and Silvio Micali. 2019.  Algorand: A secure and efficient distributed ledger.  _Theor. Comput. Sci._ 777 (2019), 155–183.
  * Cohen and Pietrzak (2019) Bram Cohen and Krzysztof Pietrzak. 2019.  The chia network blockchain.  https://docs.chia.net/assets/files/Precursor-ChiaGreenPaper-82cb50060c575f3f71444a4b7430fb9d.pdf
  * Cohen and Pietrzak (2023) Bram Cohen and Krzysztof Pietrzak. 2023.  Chia Greenpaper.  https://docs.chia.net/green-paper-abstract
  * David et al. (2017) Bernardo Machado David, Peter Gazi, Aggelos Kiayias, and Alexander Russell. 2017.  Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of-stake protocol.  _IACR Cryptol. ePrint Arch._ (2017), 573.  http://eprint.iacr.org/2017/573
  * Dziembowski et al. (2015) Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Pietrzak. 2015.  Proofs of Space. In _Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II_ _(Lecture Notes in Computer Science, Vol. 9216)_ , Rosario Gennaro and Matthew Robshaw (Eds.). Springer, 585–605.  https://doi.org/10.1007/978-3-662-48000-7_29
  * Eyal and Sirer (2018) Ittay Eyal and Emin Gün Sirer. 2018.  Majority is not enough: bitcoin mining is vulnerable.  _Commun. ACM_ 61, 7 (2018), 95–102.  https://doi.org/10.1145/3212998
  * Fan and Zhou (2017) Lei Fan and Hong-Sheng Zhou. 2017.  iChing: A Scalable Proof-of-Stake Blockchain in the Open Setting (or, How to Mimic Nakamoto’s Design via Proof-of-Stake).  _IACR Cryptol. ePrint Arch._ (2017), 656.  http://eprint.iacr.org/2017/656
  * Ferreira et al. (2022) Matheus V. X. Ferreira, Ye Lin Sally Hahn, S. Matthew Weinberg, and Catherine Yu. 2022.  Optimal Strategic Mining Against Cryptographic Self-Selection in Proof-of-Stake. In _EC_. ACM, 89–114.
  * Ferreira and Weinberg (2021) Matheus V. X. Ferreira and S. Matthew Weinberg. 2021.  Proof-of-Stake Mining Games with Perfect Randomness. In _EC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021_ , Péter Biró, Shuchi Chawla, and Federico Echenique (Eds.). ACM, 433–453.  https://doi.org/10.1145/3465456.3467636
  * Filar and Vrieze (2012) Jerzy Filar and Koos Vrieze. 2012.  _Competitive Markov decision processes_.  Springer Science & Business Media.
  * Garay et al. (2015) Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. 2015\.  The Bitcoin Backbone Protocol: Analysis and Applications. In _EUROCRYPT (2)_ _(Lecture Notes in Computer Science, Vol. 9057)_. Springer, 281–310.
  * Gazi et al. (2020) Peter Gazi, Aggelos Kiayias, and Alexander Russell. 2020\.  Tight Consistency Bounds for Bitcoin. In _CCS_. ACM, 819–838.
  * Hensel et al. (2022) Christian Hensel, Sebastian Junges, Joost-Pieter Katoen, Tim Quatmann, and Matthias Volk. 2022\.  The probabilistic model checker Storm.  _Int. J. Softw. Tools Technol. Transf._ 24, 4 (2022), 589–610.  https://doi.org/10.1007/s10009-021-00633-z
  * Hou et al. (2021) Charlie Hou, Mingxun Zhou, Yan Ji, Phil Daian, Florian Tramèr, Giulia Fanti, and Ari Juels. 2021.  SquirRL: Automating Attack Analysis on Blockchain Incentive Mechanisms with Deep Reinforcement Learning. In _NDSS_. The Internet Society.
  * Kwiatkowska et al. (2011) Marta Z. Kwiatkowska, Gethin Norman, and David Parker. 2011\.  PRISM 4.0: Verification of Probabilistic Real-Time Systems. In _CAV_ _(Lecture Notes in Computer Science, Vol. 6806)_. Springer, 585–591.
  * Nakamoto (2008) Satoshi Nakamoto. 2008\.  Bitcoin: A peer-to-peer electronic cash system.  https://bitcoin.org/bitcoin.pdf.
  * Norris (1998) James R Norris. 1998\.  _Markov chains_.  Number 2. Cambridge university press.
  * Park et al. (2018) Sunoo Park, Albert Kwon, Georg Fuchsbauer, Peter Gazi, Joël Alwen, and Krzysztof Pietrzak. 2018.  SpaceMint: A Cryptocurrency Based on Proofs of Space. In _Financial Cryptography_ _(Lecture Notes in Computer Science, Vol. 10957)_. Springer, 480–499.
  * Pass et al. (2017) Rafael Pass, Lior Seeman, and Abhi Shelat. 2017.  Analysis of the Blockchain Protocol in Asynchronous Networks. In _EUROCRYPT (2)_ _(Lecture Notes in Computer Science, Vol. 10211)_. 643–673.
  * Pietrzak (2019) Krzysztof Pietrzak. 2019\.  Simple Verifiable Delay Functions. In _ITCS_ _(LIPIcs, Vol. 124)_. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 60:1–60:15.
  * Puterman (1994) Martin L. Puterman. 1994\.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_.  Wiley.
  * Sapirshtein et al. (2016) Ayelet Sapirshtein, Yonatan Sompolinsky, and Aviv Zohar. 2016\.  Optimal Selfish Mining Strategies in Bitcoin. In _Financial Cryptography_ _(Lecture Notes in Computer Science, Vol. 9603)_. Springer, 515–532.
  * Sarenche et al. (2024) Roozbeh Sarenche, Svetla Nikova, and Bart Preneel. 2024\.  Deep Selfish Proposing in Longest-Chain Proof-of-Stake Protocols. In _Financial Cryptography and Data Security_.
  * Wang et al. (2019) Xuechao Wang, Govinda M. Kamath, Vivek Kumar Bagaria, Sreeram Kannan, Sewoong Oh, David Tse, and Pramod Viswanath. 2019.  Proof-of-Stake Longest Chain Protocols Revisited.  _CoRR_ abs/1910.02218 (2019).
  * Wesolowski (2018) Benjamin Wesolowski. 2018\.  Efficient verifiable delay functions.  _IACR Cryptol. ePrint Arch._ (2018), 623.  https://eprint.iacr.org/2018/623
  * Zur et al. (2020) Roi Bar Zur, Ittay Eyal, and Aviv Tamar. 2020.  Efficient MDP Analysis for Selfish-Mining in Blockchains. In _AFT_. ACM, 113–131.

##  Appendix 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 (Wang et al., 2019;
Cohen and Pietrzak, 2023) (see Figure 5). 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 (Fan and Zhou, 2017) (see Figure
5). 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.

The final objective, “long-term selfish mining”, considered is directly
related to attacking the chain quality of the underlying blockchain. Under
this objective, the adversary’s reward is not measured by the total number of
adversarial blocks on the main chain, but the _relative_ number of adversarial
blocks on the main chain. Figure 5 illustrates the difference between simply
maximising the total reward as per objective $2$ and the relative reward. In
the top chain in Figure 5, the adversary’s total reward is $4$ which is larger
than the total reward of $3$ in the bottom chain. However, the relative reward
of the adversary in the top chain is $\frac{2}{3}$ which is smaller than the
relative reward of $1$ in the bottom chain. Note that the chain quality and
the relative reward sum up to $1$, thus maximising the relative reward
minimises the chain quality.

Figure 3.  The top chain shows adversarial (red) and honest (green) miners
extending the public chain. The bottom chain shows adversarial miners growing
a private chain to overtake the public chain.

Figure 4.  The chains show the reward of the adversary when following the
honest strategy and when growing a private chain to overtake the public chain.

Figure 5. The chains show the reward of the adversary and chain quality of the
chain when all users mine honestly and when the adversary grows a private
chain.

##  Appendix 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 $p\in[0,1]$ fraction of
stake is elected with probability proportionate to $p$. Examples of longest-
chain blockchains based on PoStake are Ouroboros (David et al., 2017) and
post-merge Ethereum (eth, 2022).

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 (Cohen and Pietrzak, 2023) use both PoSpace
challenges as well as verifiable delay functions (Boneh et al., 2018;
Pietrzak, 2019; Wesolowski, 2018) (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.

##  Appendix C Proof of Theorem 3.1

See 3.1

###### Proof.

Before we prove the theorem, we start by making several observations and
introducing additional notation. The proof assumes familiarity with basic
notions of Markov chains and MDPs, for which we refer the reader to (Norris,
1998; Puterman, 1994). First, we observe that every strategy in the MDP
$\mathcal{M}=(S,A,P,s_{0})$ gives rise to an ergodic Markov chain. To see
this, observe that the initial state $s_{0}$ is reached with positive
probability from any other state in the MDP, since honest miners with positive
probability mine and add new blocks to the main chain for $d$ consecutive time
steps upon which the MDP would return to the initial state $s_{0}$.

Next, we define two auxiliary reward functions in the MDP $\mathcal{M}$:

  * •

$r^{H}:S\times A\times S\rightarrow\mathbb{R}$, which incurs reward $1$ for
each honest miner’s block accepted at depth $>d$ upon the action.

  * •

$r^{A}:S\times A\times S\rightarrow\mathbb{R}$, incurs reward $1$ for each
adversary’s block accepted at depth $>d$ upon the action.

For each integer $n\geq 1$, denote by $r^{A}_{n}$ and $r^{H}_{n}$ the rewards
incurred at the $n$-th step in the MDP. Since the expected relative revenue is
defined as the expected ratio of the revenues of the adversary and the total
revenue of all parties, for every strategy $\sigma$ we have

$\texttt{ERRev}(\sigma)=\mathbb{E}^{\sigma}\Big{[}\liminf_{N\rightarrow\infty}\frac{\sum_{n=1}^{N}r^{A}_{n}}{\sum_{n=1}^{N}r^{A}_{n}+r^{H}_{n}}\Big{]}.$

On the other hand, for each $\beta\in[0,1]$ we have
$r_{\beta}=r^{A}-\beta\cdot(r^{H}+r^{A})$.

Finally, for each $N\geq 1$, let $R^{A}_{N}=(\sum_{n=1}^{N}r^{A}_{n})/N$ and
$R^{H}_{N}=(\sum_{n=1}^{N}r^{H}_{n})/N$. Then $0\leq R^{H}_{N},R^{A}_{N}\leq
l$ for each $N\geq 1$, where $l$ is the maximal length of a private fork. This
is because, at every time step up to $l$ new blocks can be accepted in the
main chain at the depth greater than $d$. Hence, since the MDP $\mathcal{M}$
under every strategy gives rise to an ergodic Markov chain and since we showed
that $R^{A}_{N}$ and $R^{H}_{N}$ are bounded, it follows from the Strong Law
of Large Numbers for Markov chains (Norris, 1998, Theorem 1.10.2) that under
every MDP strategy the limits $\lim_{N\rightarrow\infty}R^{A}_{N}$ and
$\lim_{N\rightarrow\infty}R^{H}_{N}$ exist and almost-surely converge to some
value. Moreover, we also have
$\lim_{N\rightarrow\infty}(R^{A}_{N}+R^{H}_{N})\geq\delta>0$ almost-surely,
where $\delta=\frac{1-p}{1-p+p\cdot d\cdot f}$. To see this, recall from
Section 3.2 that at every time step the probability of an honest miner adding
a new block to the main chain and thus either $r^{H}_{n}=1$ or $r^{A}_{n}=1$
with probability $\delta=\frac{1-p}{1-p+p\cdot d\cdot f}$.

We are now ready to prove the theorem. To prove the first part of the theorem
claim, observe that for each $\beta\in[0,1]$ and for each strategy $\sigma$ we
have

(1)
$\begin{split}\texttt{MP}_{\beta}(\sigma)&=\mathbb{E}^{\sigma}\Big{[}\liminf_{N\rightarrow\infty}\frac{\sum_{n=1}^{N}r^{A}_{n}-\beta\cdot(r^{H}_{n}+r^{A}_{n})}{N}\Big{]}\\\
&=\mathbb{E}^{\sigma}\Big{[}\liminf_{N\rightarrow\infty}R^{A}_{N}-\beta\cdot(R^{H}_{N}+R^{A}_{N})\Big{]}\\\
&=\mathbb{E}^{\sigma}\Big{[}\lim_{N\rightarrow\infty}R^{A}_{N}-\beta\cdot(R^{H}_{N}+R^{A}_{N})\Big{]},\end{split}$

where the last limit exists since $\lim_{N\rightarrow\infty}R^{A}_{N}$ and
$\lim_{N\rightarrow\infty}R^{A}_{N}+R^{H}_{N}$ both exist and are almost-
surely finite. Hence, $\texttt{MP}_{\beta}(\sigma)=0$ if and only if
$\mathbb{E}^{\sigma}[\lim_{N\rightarrow\infty}R^{A}_{N}-\beta\cdot(R^{H}_{N}+R^{A}_{N})]=0$.
Since $\lim_{N\rightarrow\infty}(R^{A}_{N}+R^{H}_{N})\geq\delta>0$ almost-
surely, we may divide the expression in the expectation by
$R^{A}_{N}+R^{H}_{N}$ to get that $\texttt{MP}_{\beta}(\sigma)=0$ if and only
if

$\texttt{ERRev}(\sigma)=\mathbb{E}^{\sigma}\Big{[}\lim_{N\rightarrow\infty}\frac{R^{A}_{N}}{R^{H}_{N}+R^{A}_{N}}\Big{]}=\beta.$

Thus, we have
$\texttt{MP}^{\ast}_{\beta}=\sup_{\sigma}\texttt{MP}_{\beta}(\sigma)=0$ if and
only if

$\beta=\sup_{\sigma}\mathbb{E}^{\sigma}\Big{[}\lim_{N\rightarrow\infty}\frac{R^{A}_{N}}{R^{A}_{N}+R^{H}_{N}}\Big{]}=\texttt{ERRev}^{\ast},$

which concludes the proof of the first part of the theorem claim.

To prove the second part of the theorem claim, let $\epsilon>0$,
$\beta\in[\texttt{ERRev}^{\ast}-\epsilon,\texttt{ERRev}^{\ast}]$ and suppose
that $\sigma$ is a strategy such that
$\texttt{MP}_{\beta}(\sigma)=\texttt{MP}^{\ast}_{\beta}$. We need to show
$\texttt{ERRev}(\sigma)\in[\texttt{ERRev}^{\ast}-\epsilon,\texttt{ERRev}^{\ast}]$.

Since $\beta\leq\texttt{ERRev}^{\ast}$ and since $\texttt{MP}^{\ast}_{x}$ is a
monotonically decreasing function in $x\in[0,1]$, we have that
$\texttt{MP}_{\beta}(\sigma)=\texttt{MP}^{\ast}_{\beta}\geq\texttt{MP}^{\ast}_{\texttt{ERRev}^{\ast}}=0$,
by the first part of the theorem. Analogously as in eq. (1), we get

$\texttt{MP}_{\beta}(\sigma)=\mathbb{E}^{\sigma}\Big{[}\lim_{N\rightarrow\infty}R^{A}_{N}-\beta\cdot(R^{H}_{N}+R^{A}_{N})\Big{]}\geq
0.$

Then, since $\lim_{N\rightarrow\infty}(R^{A}_{N}+R^{H}_{N})\geq\delta>0$
almost-surely, we may divide the expression in the expectation by
$R^{A}_{N}+R^{H}_{N}$ to get

$\mathbb{E}^{\sigma}\Big{[}\lim_{N\rightarrow\infty}\frac{R^{A}_{N}}{R^{A}_{N}=R^{H}_{N}}-\beta\Big{]}\geq
0.$

and thus $\texttt{ERRev}(\sigma)\geq\beta$. Thus, as
$\beta\in[\texttt{ERRev}^{\ast}-\epsilon,\texttt{ERRev}^{\ast}]$, we conclude
that
$\texttt{ERRev}(\sigma)\in[\texttt{ERRev}^{\ast}-\epsilon,\texttt{ERRev}^{\ast}]$,
as desired (where $\texttt{ERRev}(\sigma)\leq\texttt{ERRev}^{\ast}$ follows by
the definition of $\texttt{ERRev}^{\ast})$. ∎