# Computing Optimal Manipulations in Cryptographic Self-Selection Proof-of-
Stake Protocols

Matheus V. X. Ferreira<EMAIL_ADDRESS>0000-0002-7695-026X
University of VirginiaCharlottesvilleVAUSA ,  Aadityan Ganesh
<EMAIL_ADDRESS>0009-0000-3567-8178 Princeton
UniversityPrincetonNJUSA ,  Jack Hourigan<EMAIL_ADDRESS>0000-0001-7744-795X University of PennsylvaniaPhiladelphiaPAUSA ,  Hannah Huh
<EMAIL_ADDRESS>0009-0008-6237-3685 Princeton UniversityPrincetonNJUSA ,
S. Matthew Weinberg<EMAIL_ADDRESS>0000-0001-7744-795X Princeton
UniversityPrincetonNJUSA and  Catherine Yu<EMAIL_ADDRESS>0009-0007-4605-2964 Princeton UniversityPrincetonNJUSA

(2024)

###### Abstract.

Cryptographic Self-Selection is a paradigm employed by modern Proof-of-Stake
consensus protocols to select a block-proposing “leader.” Algorand (Chen and
Micali,, 2019) proposes a canonical protocol, and Ferreira et al., (2022)
establish bounds $f(\alpha,\beta)$ on the maximum fraction of rounds a
strategic player can lead as a function of their stake $\alpha$ and a network
connectivity parameter $\beta$. While both their lower and upper bounds are
non-trivial, there is a substantial gap between them (for example, they
establish $f(10\%,1)\in[10.08\%,21.12\%]$), leaving open the question of how
significant of a concern these manipulations are. We develop computational
methods to provably nail $f(\alpha,\beta)$ for any desired $(\alpha,\beta)$ up
to arbitrary precision, and implement our method on a wide range of parameters
(for example, we confirm $f(10\%,1)\in[10.08\%,10.15\%]$).

. Methodologically, estimating $f(\alpha,\beta)$ can be phrased as estimating
to high precision the value of a Markov Decision Process whose states are
countably-long lists of real numbers. Our methodological contributions involve
(a) reformulating the question instead as computing to high precision the
expected value of a distribution that is a fixed-point of a non-linear
sampling operator, and (b) provably bounding the error induced by various
truncations and sampling estimations of this distribution (which appears
intractable to solve in closed form). One technical challenge, for example, is
that natural sampling-based estimates of the mean of our target distribution
are _not_ unbiased estimators, and therefore our methods necessarily go beyond
claiming sufficiently-many samples to be close to the mean.

blockchain, cryptocurrency, proof-of-stake, cryptography, strategic mining,
provably correct estimations, fixed point estimations

††ccs: Theory of computation Algorithmic game theory and mechanism
design††ccs: Security and privacy Cryptanalysis and other
attacks††journalyear: 2024††copyright: rightsretained††conference: The 25th
ACM Conference on Economics and Computation; July 8–11, 2024; New Haven, CT,
USA††booktitle: The 25th ACM Conference on Economics and Computation (EC ’24),
July 8–11, 2024, New Haven, CT, USA††doi: 10.1145/3670865.3673602††isbn:
979-8-4007-0704-9/24/07

##  1\. Introduction

Blockchain protocols have attracted significant interest since Bitcoin’s
initial development in 2008 (Nakamoto,, 2008), and several parallel research
agendas and developments arose in that time. This paper lies at the
intersection of two of these agendas: (a) strategic manipulability of
consensus protocols, and (b) the return of Byzantine Fault Tolerant
(BFT)-style consensus protocols via Proof-of-Stake (PoS). We briefly elaborate
on both stories below, before discussing our contributions.

Manipulating Consensus Protocols. Initially following Nakamoto’s whitepaper,
Bitcoin and related blockchain protocols were studied through a classical
security lens: some fraction of participants were honest, others were
malicious, and the goal of study was to determine the extent to which a
malicious actor can compromise security with a particular fraction of the
computational power in the network. For example, Nakamoto’s whitepaper already
derives that with $51\%$ of the computational power, a malicious actor could
completely undermine Bitcoin’s consensus protocol. However, the seminal work
of Eyal and Sirer, (2014), now referred to as “Selfish Mining”, identified a
fundamentally different cause for concern: an attacker with $34\%$ of the
computational power could manipulate the protocol in a way that does not
violate consensus, but earns that attacker a $>34\%$ fraction of the mining
rewards.111Earlier work of (Babaioff et al.,, 2012) introduces the strategic
manipulation aspects of the Bitcoin protocol, although the style of
manipulation in (Eyal and Sirer,, 2014) became more mainstream for subsequent
work. This agenda has exploded over the past decade, and there is now a vast
body of work considering strategic manipulation of consensus protocols (e.g.
Eyal and Sirer,, 2014; Kiayias et al.,, 2016; Sapirshtein et al.,, 2016;
Carlsten et al.,, 2016; Tsabary and Eyal,, 2018; Goren and Spiegelman,, 2019;
Fiat et al.,, 2019; Brown-Cohen et al.,, 2019; Zur et al.,, 2020; Ferreira and
Weinberg,, 2021; Ferreira et al.,, 2022; Yaish et al.,, 2022, 2023; Bahrani
and Weinberg,, 2023).

These works study _several_ different classes of protocols, and _several_
avenues for manipulation: some study Proof-of-Work protocols while others
study Proof-of-Stake, some study block withholding deviations while others
manipulate timestamps, some focus on profitability denoted in the underlying
cryptocurrency while others consider the impact of manipulation on that
cryptocurrency’s value. There are many important angles to this agenda, many
of which are cited by practitioners as key motivating factors in design
choices.222For example, EIP-1559. The primary goal of this agenda is to
understand _under what conditions is it in every participant’s interest to
follow the prescribed consensus protocol?_ That is, these works generally do
not focus on understanding complex equilibria with multiple strategic players
(and instead immediately consider it a failure of the protocol when it is not
being followed), and instead seek to understand whether the strategy profile
where all agents follow the protocol constitutes a Nash Equilibrium. That is,
we seek to understand whether being honest is the best response when everyone
else in the network is honest.

BFT-based Proof-of-Stake Protocols. As Bitcoin’s popularity surged, the energy
demands required to secure it comparably soared, and estimates place its
global energy consumption at comparable levels to countries the size of
Australia. This motivated discussions over alternate technologies that could
still be permissionless and Sybil-resistant, and Proof-of-Stake emerged as a
viable alternative. While Proof-of-Work protocols select participants to
produce blocks proportional to their computational power, Proof-of-Stake
protocols do so proportional to the fraction of underlying cryptocurrency they
own. Initial Proof-of-Stake protocols predominantly followed the longest-chain
consensus paradigm of Bitcoin (Daian et al.,, 2016; Kiayias et al.,, 2017),
but modern proposals now look more like classical consensus algorithms from
distributed computing (Gilad et al.,, 2017; Chen and Micali,, 2019).
Specifically, BFT-based protocols run a consensus algorithm, one block at a
time, in order to reach consensus on a single block. Once consensus is
reached, the block is finalized and consideration of the next block begins.

While Bitcoin still uses a longest-chain Proof-of-Work consensus protocol, and
some large Proof-of-Stake cryptocurrencies such as Cardano still use longest-
chain protocols (Kiayias et al.,, 2017), BFT-based protocols are now quite
mainstream and are implemented, for example, in Algorand (Gilad et al.,, 2017;
Chen and Micali,, 2019) and Ethereum.333Ethereum does maintain some longest-
chain aspect to its protocol, but the key role that validators play make the
protocol closer to BFT-based consensus.

Manipulating BFT-based Proof-of-Stake Protocols. In practice, there is no
‘dominant’ BFT-based protocol, and different cryptocurrencies each seem to
have their own protocol. However, there are some unifying themes. Most BFT-
based protocols have the concept of a _leader_ in each round, and the
consensus goal of each round is for everyone to agree on the leader’s proposed
block. Leader selection is challenging, though: it should be done proportional
to stake, but in a way that neither relies on a trusted external source of
randomness nor is manipulable by participants. This has proved to be quite
challenging, and to-date there are no nonmanipulable proposals without
heavyweight cryptography (such as Multi-Party Computation or Verifiable Delay
Functions). While the underlying consensus protocols are often both complex
and completely nonmanipulable (without sufficient stake to simply subvert
consensus in the first place), the leader selection protocols are more
vulnerable, and can be studied independently of the supported consensus
protocol.

Algorand’s initial proposal serves as a canonical process of study due to its
elegance. The initial seed $Q_{1}$ is a uniformly drawn random number. Then,
in each round $t$ with seed $Q_{t}$, every wallet digitally signs the
statement $(Q_{t},c)$ for every coin $c$ they own, hashes it,444We will
elaborate on this rigorously in Section 2.2. The role of the digital signature
is simply to get a signature unique to the owner of coin $c$ that no other
player can predict, and the role of the hash function is to turn this into a
uniformly drawn random number from $[0,1]$. and broadcasts the hash as their
credential $\operatorname{\textsc{Cred}}^{c}_{t}$. The holder of the coin with
the lowest credential is the leader, and their winning credential becomes the
seed $Q_{t+1}$ for round $t+1$. This elegant protocol has several desirable
properties (for example, it is not vulnerable to any form of ‘stake grinding’
to influence next round’s seed – you can either broadcast your credential or
not),555The live Algorand protocol seems to have recently pivoted from their
initial proposal to a leader-selection protocol that has the winning
credential of every $k^{th}$ round set the seeds for the next $k$ rounds. but
Chen and Micali, (2019) acknowledge that it may still be manipulable by
cleverly choosing not to broadcast credentials, and Ferreira et al., (2022)
indeed establish that any size staker has such a profitable manipulation.

To get brief intuition for a profitable manipulation, imagine that an attacker
controls $10\%$ of the coins. Perhaps they are also well-enough connected in
the network so that they can choose which credentials of their own to
broadcast in round $t$ as a function of other participants’ credentials (this
corresponds to $\beta=1$ – in general, the adversary is $\beta$-well-connected
if they see a $\beta$ fraction of honest credentials before broadcasting their
own). Such an attacker might be in a position where they own (say) the three
lowest credentials. In this case, the adversary could look one round ahead and
determine which of these round-$t$-winning credentials gives them the best
chance of winning round $t+1$, and broadcast only that credential. This
particularly simple manipulation, termed the One-Lookahead strategy in
Ferreira et al., (2022), is strictly profitable for any sized staker. While
strictly better than honest, this strategy does not reap enormous profits:
even with $10\%$ stake, a $1$-well-connected staker can lead at most $10.08\%$
rounds. On the other hand, the only previous upper bounds derived on the
maximum gains come from a loose analysis of an omniscient adversary who not
only sees the credentials of honest wallets in round $t$, but can predict
their future digital signatures to know exactly which hypothetical future
rounds they’d win. This results in an upper bound of $21.12\%$ on the maximum
possible rounds led by a $10\%$ staker. Needless to say, the level of concern
that would arise from a $10\%$ staker who is able to slightly increase their
staking rewards by less than $1\%$ to $10.08\%$ is vastly different than what
would arise from a $10\%$ staker who can more than double their staking
rewards to $21.12\%$.

Our Contributions. Using both theoretical and computational tools, we
precisely nail down the manipulability of Algorand’s canonical leader
selection protocol. That is, we design computational methods to compute, for
any fraction of stake $\alpha$ and network connectivity parameter $\beta$ that
an attacker might have,666We define the network connectivity formally in
Section 3.1. the maximum fraction of rounds the attacker can lead (assuming
other players are honest). We rigorously bound the error in our methods – some
bounds hold with probability one (due to discretization, truncation, etc.)
while others hold with high probability (due to sampling). We consider this
methodology to be our main contribution. We also make the following adjacent
contributions:

  * •

We implement our computational procedure in Rust, and run it across several
personal laptops and university clusters. We plot several of our findings in
Section 5 (and future researchers can run our code to even higher precision,
if desired). For example, we close the gap on the maximum profit of a
$1$-well-connected $10\%$ staker from $[10.08\%,21.12\%]$ to
$[10.08\%,10.15\%]$. We produce several plots in Section 5 demonstrating our
results in comparison to prior bounds.

  * •

One conclusion drawn from our simulations is that the gains from manipulation
are quite small. For example, we confirm that $1$-well-connected $10\%$ staker
can lead at most $10.15\%$ of all rounds. A $0$-well-connected $10\%$ staker
can lead at most $10.09\%$ of the rounds. Even a $0$-well-connected $20\%$
staker can lead at most $20.21\%$ of the rounds. This suggests that, while
supralinear rewards are always a cause for concern as a potential centralizing
force among stakers, the situation is unlikely to be catastrophic.

  * •

A second conclusion drawn from our simulations is $\beta$ plays a significant
role in the magnitude of profitability. For example, a $0$-well-connected
$20\%$ staker can lead at most $20.21\%$ of the rounds, while there exists a
strategy for a $1$-well-connected $20\%$ staker that leads at least $20.68\%$
of the rounds – a $320\%$ amplification in the marginal gains.

  * •

Beyond our provably accurate computational methodology, we also provide two
analytical results of independent interest.

    * –

We improve (Ferreira et al.,, 2022)’s analysis of the omniscient adversary,
and in particular describe a recursive formulation that achieves an
arbitrarily good approximation to the precise profit of an optimal omniscient
adversary. This appears in Section 3.3.

    * –

Finally, we prove one conjecture and disprove another of Ferreira et al.,
(2022) characterizing “Balanced Scoring Functions.” Balanced Scoring Functions
are a tool used in leader selection to replace computing a digital-signature-
then-hash per coin with computing a digital-signature-then-hash per wallet (in
order to appropriately weight the hash before taking the minimum amongst all
credentials). We state this result in Section 2.1.

As a whole, our results significantly improve our understanding of
manipulating the canonical leader selection protocol first introduced in
Algorand (Chen and Micali,, 2019). First, while supralinear rewards are always
a cause for concern, the maximum achievable profits are at quite a small order
of magnitude. Second, our results highlight the pivotal role that $\beta$
plays in the rate of supralinear rewards. This suggests that protocol
designers may wish to invest in augmentations to bring $\beta$ closer to
zero.777One such possibility is to broadcast credentials using commit-reveal:
players make a large deposit along with a cryptographic commitment to their
credential, and unlock their deposit only upon revealing it. Methodologically,
our approach provides a blueprint for how similar leader selection protocols
(such as Ethereum’s) might be analyzed.

###  1.1. Very Brief Technical Highlight

We defer full details to our technical sections, but give a brief overview of
the key technical challenges here. The optimal strategy can be phrased as a
Markov Decision Process (MDP), and in some sense the obvious approach is to
“write down the MDP and solve it.” Unfortunately, states in our MDP are
countably long lists of real numbers. That is, a state corresponds to (a) the
list of credentials the attacker has in this round, but also (b) for each of
those credentials $i$, and each other wallet $j$ controlled by the adversary,
the credential wallet $j$ would provide the next round if wallet $i$ wins this
round (which can be computed as the seed for the next round is simply a
digital signature plus hash of its credential $i$), and moreover (c) for each
of those pairs of credentials $(i,j)$, and each other wallet $k$ controlled by
the adversary, the credential wallet $k$ would provide two rounds from now if
credential $i$ wins this round and credential $j$ wins the next round, and (d)
so on.

A first step is to truncate this countably long list of real numbers to (a)
look only $T<\infty$ rounds in the future, (b) store only $k<\infty$
credentials per round, and (c) discretize each credential to a multiple of
$\varepsilon>0$. These steps can all be done with provable upper bounds on the
error they induce. However, even with $k=8$ and $T=15$, states still
correspond to a list of $8^{15}$ multiples of $\varepsilon$, and is clearly
intractable.

Instead, our key idea is to reformulate the question as finding the
distribution of future rewards that an optimal strategist receives. That is,
consider the process of sampling a state for the attacker (a list of
credentials for this round, hypothetical future credentials, etc.), and ask
what future reward the attacker would get when playing optimally. If we can
compute this distribution of rewards $D$, then its expected value is exactly
the number we seek. We define an operator $\Theta(\cdot)$ that takes as input
samples from some distribution $F$ and produces samples from the distribution
$\Theta(F)$, and establish that $D$ is a fixed point of $\Theta(\cdot)$.

Again, the process now appears straight-forward: start from any distribution,
and iterate $\Theta(\cdot)$ until it stabilizes. This is indeed our approach,
and the remaining challenge is to account for sampling error. Essentially, we
are looking for $\mathbb{E}[\Theta^{15}(F)]$ for some simple initial
distribution $F$, and instead of computing $\Theta(\cdot)$ at each stage we’ll
take an empirical estimate $\hat{\Theta}(\cdot)$ instead. This appears ripe
for a Chernoff plus union bound to bound the error due to sampling, except
that $\mathbb{E}[\hat{\Theta}(\cdot)]$ is not an unbiased estimator for
$\mathbb{E}[\Theta(\cdot)]$. So even establishing that we take sufficiently
many samples to be close to the process’s expected value does not guarantee we
are close to $\mathbb{E}[\Theta^{15}(F)]$. Instead, at each round we both
inflate (resp. deflate) our empirical $\hat{\Theta}^{i}(F)$ so that we know it
stochastically dominates (resp. is stochastically dominated by)
$\Theta^{i}(F)$ using a variant of the DKW inequality (Dvoretzky et al.,,
1956).

We share this to give the reader a sense of the technical developments
necessary to analyze this particular Markov Decision Process, and ways in
which it differs from more common MDPs.

###  1.2. Related Work

Manipulating Leader Selection Protocols. Chen and Micali, (2019) propose the
Algorand leader selection protocol, and acknowledge that it may be
manipulable. They also prove an upper bound on the fraction of rounds an
adversary can win after being honest in the previous round. Ferreira et al.,
(2022) provide a strategy that is strictly profitable for all $\beta$-well-
connected $\alpha$-sized stakers, and upper bound the attainable profit of an
omniscient adversary who can predict future digital signatures of honest
players. We provide provably accurate computational methodology to nail the
optimal manipulability up to arbitrary precision (and implement our algorithms
and draw conclusions from the results). In concurrent and independent work,
(Cai et al.,, 2024) establish that any strictly profitable manipulation of our
same leader selection protocol is statistically detectable (that is, an
onlooker who sees only the seeds of each round can distinguish whether someone
is profitably manipulating the protocol from when all players are honest but
sometimes offline). This work is orthogonal to ours, but also provides an
argument that solid defenses against manipulation exist (we argue that the
manipulations are not particularly profitable, they argue that they are always
detectable).

Manipulating Consensus Protocols. We have already briefly cited a subset of
the substantial body of work studying profitable manipulations of consensus
protocols (Bahrani and Weinberg,, 2023; Brown-Cohen et al.,, 2019; Carlsten et
al.,, 2016; Eyal and Sirer,, 2014; Ferreira et al.,, 2022; Ferreira and
Weinberg,, 2021; Fiat et al.,, 2019; Goren and Spiegelman,, 2019; Kiayias et
al.,, 2017; Sapirshtein et al.,, 2016; Tsabary and Eyal,, 2018; Yaish et al.,,
2023, 2022). Of these, (Brown-Cohen et al.,, 2019; Ferreira and Weinberg,,
2021) also study Proof-of-Stake protocols, but longest-chain variants (and
therefore have minimal technical overlap). Sapirshtein et al., (2016) bears
some technical similarity, as they are the unique prior work that finds
optimal manipulations (in Bitcoin’s Proof-of-Work), and they also use
computational tools with theoretical guarantees. We also use a lemma of theirs
to reduce from maximizing the fraction of rounds won to maximizing reward in a
linear MDP. Still, there is minimal technical overlap beyond these. For
example, their problem can be phrased as a Markov Decision Process with
countably-many states (i.e. a state in their setup is of the form “how many
hidden blocks do you have?”, which is an integer), and therefore the key steps
in their provable guarantees are truncations. In comparison, we’ve noted that
our problem is a Markov Decision Process with uncountably many states, and
therefore the two MDPs have minimal overlap.888This is also perhaps expected,
as there is little technical similarity between creating forks in a longest-
chain protocol and manipulating credentials in a leader-selection protocol.

##  2\. Preliminaries

###  2.1. Primitives

In this section, we review various cryptographic primitives required to
construct a cryptographic self-selection protocol. Since our model is
identical, we use notations identical to Ferreira et al., (2022). We begin by
discussing a tool central to many Proof-of-Stake protocols– verifiable random
functions. Verifiable random functions are useful in enabling a source of
randomness endogenous to the blockchain for the leader election protocol.

###### Definition 0 (Ideal Verifiable Random Function (Ideal VRF)).

An ideal verifiable random function satisfies the following properties:

  1. (1)

Setup: There is an efficient randomized generator that can produce a pair
$(sk,pk)$ of a secret key and a public key that characterizes the instance
$f_{sk}(\cdot)$.

  2. (2)

Private computability: For a string $x$, there exists an efficient algorithm
to compute the encryption $f_{sk}(x)$ of $x$ with the knowledge of $sk$.

  3. (3)

Perfect randomness: Without the knowledge of $sk$, the random variables
$f_{sk}(x)$ and $f_{sk}(y)$ are distributed i.i.d. over $U[0,1]$. In
particular, the random variable $f_{sk}(x)\sim U[0,1]$ even with the knowledge
of $\big{(}(y_{i},f_{sk}(y_{i}))\big{)}_{1\leq i\leq m}$ such that $y_{i}\neq
x$ for all $1\leq i\leq m$.

  4. (4)

Verifiability: Verifying the claim $y=f_{sk}(x)$ can be done efficiently
conditioned on the knowledge of $pk$ and a proof $V_{x}$, even if $sk$ remains
unknown. Generating a proof $V_{x}$ such that a verifier confirms equality
when $y\neq f_{sk}(x)$ is impossible.

An ideal VRF allows the holder of the secret key $sk$ (through property 3) to
provably generate a random number, i.e, show that the random number was
generated through a prescribed process. However, it is impossible to construct
an ideal VRF whose outputs are _statistically indistinguishable_ from
$U[0,1]$. On the other hand, it is possible to construct a VRF whose outputs
are _computationally indistinguishable_ from $U[0,1]$. For the sake of
simplicity, we proceed with an Ideal VRF instead of computational – this
results in only a negligible difference.

###### Example 0 (VRFs through digital signatures).

Let $\sigma$ be a digital signature scheme with a public key, secret key pair
$(pk,sk)$ and let $h$ be a hash function. Then, $h(\sigma_{sk}(\cdot))$ is a
verifiable random function. $y=h(\sigma_{sk}(x))$ can be computed efficiently
with the knowledge of $sk$. With a proof $V_{x}=\sigma_{sk}(x)$,
$y=h(\sigma_{sk}(x))$ can be verified as follows- verify that (i) the proof
$V_{x}=\sigma_{sk}(x)$ with the public key $pk$ and $x$ and (ii) verify
$y=h(V_{x})$.

Next, we proceed to discuss balanced scoring functions that enable electing a
leader proportional to its stake.

###### Definition 0 (Balanced Scoring Functions).

A scoring rule $S:[0,1]\times\mathbb{R}\xrightarrow{}[0,1]$ is balanced if:

  1. (1)

For $X\sim U[0,1]$, the distribution of $S(X,\alpha)$ has no point masses for
all $\alpha\in[0,1]$

  2. (2)

For all $n\in\mathbb{N}$ and $\big{(}\alpha_{i}\big{)}_{1\leq i\leq
n}\in\mathbb{R}^{n}_{\geq 0}$,

$Pr_{X_{1},\dots,X_{n}\sim U[0,1]}\Big{(}\arg\min_{1\leq i\leq
n}\\{S(X_{i},\alpha_{i})\\}=j\Big{)}=\frac{\alpha_{j}}{\sum_{i=1}^{n}\alpha_{i}}$

At a high level, a fair leader selection to elect a wallet with probability
proportional to its stake can be conducted by choosing the wallet with the
smallest score, while VRFs provide the source for the random variable $X_{i}$
for a wallet $i$.

Ferreira et al., (2022) conjecture that $S(X,\sum_{i=1}^{n}\alpha_{i})$ and
$\min_{1\leq i\leq n}\\{S(X,\alpha_{i})\\}$ are identically distributed for
all balanced scoring functions $S$, $n\in\mathbb{N}$ and
$\alpha_{1},\dots,\alpha_{n}\in\mathbb{R}_{\geq 0}$999They also claim that
$S(X,\alpha)$ is continuous in $\alpha$. We provide a counterexample to their
claim. However, Theorem 1 shows that $Pr(S(X,\alpha)\geq s)$ is continuous in
$\alpha$. See Appendix A for a detailed discussion on scoring functions..
Intuitively, their conjecture claims an adversary with a total stake
$\sum_{i=1}^{n}\alpha_{i}$ cannot increase the probability of a smaller score
and thus, the probability of getting elected by splitting their stake as
$\big{(}\alpha_{i}\big{)}_{1\leq i\leq n}$ across $n$ different wallets. We
settle their conjecture.

###### Theorem 4.

Let $S(X,\alpha)$ be any balanced scoring function. Then, for all
$n\in\mathbb{N}$ and $\big{(}\alpha_{i}\big{)}_{1\leq i\leq n}$, the random
variables

$S(X,\sum_{i=1}^{n}\alpha_{i})\text{ and }\min_{1\leq i\leq
n}\\{S(X_{i},\alpha_{i})\\}$

are identically distributed for $X,X_{1},\dots,X_{n}\sim U[0,1]$.

The proof of Theorem 4 and further details on scoring functions are deferred
to Appendix A.

###  2.2. Cryptographic Self-Selection

We are now ready to describe a cryptographic self-selection protocol.

###### Definition 0 (Cryptographic Self-Selection Protocol $A$ (CSSPA);
Ferreira et al.,, 2022).

A Cryptographic Self-Selection Protocol $A$ is the following:

  1. (1)

Every wallet $i$ sets up an instance of an ideal VRF with public key, secret
key pair $(pk_{i},sk_{i})$ prior to round $1$. Wallet $i$ holds a stake
$\alpha_{i}$.

  2. (2)

$Q_{t}$ denotes the seed of round $t$. The seed $Q_{1}$ for the initial round
is computed through an expensive multi-party computation and is distributed
according to $U[0,1]$.

  3. (3)

In each round $t$, the user with wallet $i$ computes its credential
$\operatorname{\textsc{Cred}}^{i}_{t}:=f_{sk_{i}}(Q_{t})$.

  4. (4)

Each user can choose either to broadcast its credential or remain silent. Any
credential broadcast by a user is received by all other users101010We assume
this to focus on the relevant aspects of the paper and is consistent in prior
work that focuses on incentives (Carlsten et al.,, 2016; Eyal and Sirer,,
2014; Ferreira and Weinberg,, 2021; Ferreira et al.,, 2019; Sapirshtein et
al.,, 2016; Kiayias et al.,, 2016; Bahrani and Weinberg,, 2023).

  5. (5)

The wallet with the smallest score
$S(\operatorname{\textsc{Cred}}^{i}_{t},\alpha_{i})$ amongst all broadcasted
credentials is elected the leader $\ell_{t}$ for round $t$.

  6. (6)

The seed for round $t+1$,
$Q_{t+1}=\operatorname{\textsc{Cred}}^{\ell_{t}}_{t}$, the credential of the
winner of round $t$. All wallets learn the seed $Q_{t+1}$.

Importantly, note that the blockchain cannot be forked in the CSSPA as in the
case with many BFT-based consensus protocols including Algorand.

We consider strategic manipulations rather than network security attacks, and
so the action space of users is restricted to distributing their stakes across
multiple wallets and choosing between broadcasting and remaining silent for
each of its wallet, as opposed to a network partition attack. An honest player
keeps its stake in a single wallet and always broadcasts its credential.
Conditioned on all players in the network being honest, observe that the
probability of a wallet with stake $\alpha_{j}$ getting elected equals the
probability that wallet $i$ has the smallest score, which happens with a
probability proportional to $\alpha_{i}$.

We discuss choosing an explicit balanced scoring function for our model.
Ferreira et al., (2022) argue that the game induced by the CSSPA is
independent of the choice of the scoring function and show a bijection between
the strategies of a strategic player in the games induced by two different
scoring functions that preserve the player’s rewards (Definition 2). We choose
the logarithmic scoring function defined below.

###### Definition 0 (Logarithmic Scoring Function).

For $X\in[0,1]$ and $\alpha\in\mathbb{R}_{\geq 0}$,

$S_{\ln}(X,\alpha)=\begin{cases}\infty&\text{when }\alpha=0\\\ 0&\text{when
}X=0,\alpha\neq 0\\\ \frac{-\ln X}{\alpha}&\text{otherwise}\end{cases}$

###### Definition 0 (Exponential Distribution).

The exponential distribution $\operatorname{exp}(\alpha)$ with rate $\alpha$
is the distribution with a cumulative density function (CDF)
$F(x,\alpha)=1-e^{-\alpha\,x}$ and a probability density function (pdf)
$f(x,\alpha)=\alpha e^{-\alpha\,x}$.

###### Lemma 0 (Lemma 2.1 from Ferreira et al.,, 2022).

$S_{\ln}(X,\alpha)$ is distributed according to $\operatorname{exp}(\alpha)$
when $X\sim U[0,1]$.

For notational convenience, we denote $S_{\ln}$ by $S$ unless mentioned
otherwise.

Consider a user distributing their stake $\alpha$ equally across $n$ wallets
for $n\xrightarrow{}\infty$. The scores of each wallet is distributed
according to $\operatorname{exp}(\tfrac{\alpha}{n})$. It is well-known that
the minimum of $n$ i.i.d random variables drawn from
$\operatorname{exp}(\theta)$ is distributed according to
$\operatorname{exp}(n\,\theta)$ (see Appendix A from Ferreira et al.,, 2022,
for example). Therefore, the minimum score over all wallets of the user is
distributed as per $\operatorname{exp}(\alpha)$. The following describes the
distribution of the $i\textsuperscript{th}$-smallest score amongst the $n$
wallets.

###### Lemma 0 (Lemma 4.3 from Ferreira et al.,, 2022).

Let $\big{(}X_{i}\big{)}_{i\in\mathbb{N}}$ be exponentially distributed i.i.d
random variables such that $\min_{i\in\mathbb{N}}\\{X_{i}\\}$ is distributed
according to $\operatorname{exp}(\alpha)$. Let $Y_{i}$ be the random variable
denoting the $i\textsuperscript{th}$-smallest value in
$\big{(}X_{i}\big{)}_{i\in\mathbb{N}}$. Then,
$\big{(}Y_{i}\big{)}_{i\in\mathbb{N}}$ is distributed according to the
following random process:

$Y_{1}\xleftarrow{}\operatorname{exp}(\alpha)\text{ and
}Y_{i+1}\xleftarrow{}Y_{i}+\operatorname{exp}(\alpha)$

We have the prerequisites to study the actions of a strategic player in the
CSSPA in place.

##  3\. Model

###  3.1. The Adversarial Game and Reward

In a network consisting of honest stakers, we study a single strategic
adversary whose rewards are proportional to the fraction of rounds it is
elected to propose a block. Conditioned on the stake the adversary holds in
the system, we want to estimate the optimal marginal utility gained by the
adversary from being strategic. We adopt the adversarial model described in
Ferreira et al., (2022), which we review below.

We define the space of strategies available to the adversary. We abuse
notation to denote the cryptographic self-selection protocol, the game played
by the adversary and the space of strategies available to the adversary by
CSSPA.

###### Definition 0 ($\operatorname{CSSPA}(\alpha,\beta)$).

In $\operatorname{CSSPA}(\alpha,\beta)$, the network consists of three players
— the adversary with stake $\alpha$, and two honest players $B$ and $C$ with
stakes $\beta\,(1-\alpha)$ and $(1-\beta)(1-\alpha)$ respectively.Prior to
round $1$, the adversary learns the values of $\alpha$, $\beta$ and that $B$
and $C$ are honest. For $n\xrightarrow{}\infty$, the adversary distributes its
stake into a set $A$ of $n$ wallets, each containing a stake
$\tfrac{\alpha}{n}$. The adversary makes the following decisions in round $t$:

  1. (1)

The adversary learns the seed $Q_{t}$ of round $t$.

  2. (2)

The adversary computes the credentials $\operatorname{\textsc{Cred}}^{i}_{t}$
for all wallets $i\in A$.

  3. (3)

Further, the adversary learns the credentials
$\operatorname{\textsc{Cred}}^{B}_{t}$ of player $B$. The adversary knows that
the credential of player $C$ is drawn from
$\operatorname{exp}((1-\beta)\,(1-\alpha))$ but does not learn
$\operatorname{\textsc{Cred}}^{C}_{t}$.

  4. (4)

For any $r\geq 0$ and
$(i_{t},i_{t+1},\dots,i_{t+r})\in\big{(}A\cup\\{B\\}\big{)}\times A^{r}$, the
adversary precomputes the credentials
$\operatorname{\textsc{Cred}}^{i_{t+r^{\prime}}}_{t+r^{\prime}}$ for $1\leq
r^{\prime}\leq r$ assuming $i_{t+\hat{r}}$ is elected to lead in round
$t+\hat{r}$ for all $0\leq\hat{r}<r^{\prime}$.

  5. (5)

The adversary either remains silent or broadcasts the credential of a wallet
$i\in A$.

The following discussion throws light on bullet 4 of Definition 1. Before
broadcasting any credential in round $t$, the adversary observes the
credentials of its own wallets and the credential of $B$. All credentials
$\operatorname{\textsc{Cred}}^{i}_{t}$ for $i\in A\cup\\{B\\}$ observed by the
adversary are potential seeds for round $t+1$. Assuming one of these
credentials as a hypothetical seed, the adversary can compute the credentials
$\operatorname{\textsc{Cred}}^{i}_{t+1}$ for all of its wallets $i\in A$.
These hypothetical credentials are themselves potential seeds for round $t+2$.
More generally, the adversary can precompute all possible future credentials
of its wallets, assuming the precomputed credentials keep becoming the seed
for successive rounds.

$\beta$ denotes the network connectivity of the adversary. The stake of $C$,
and therefore the probability of $C$ having a small score and being selected,
decreases with $\beta$. Thus, for large values of $\beta$, it is much more
unlikely for a credential not precomputed by the adversary, namely
$\operatorname{\textsc{Cred}}^{C}_{t}$, to become the seed $Q_{t+1}$ for the
next round. Since both $B$ and $C$ have non-negative stakes, $\beta\in[0,1]$.

Remember that the honest strategy collects all stake into a single wallet and
broadcasts the credential of the wallet each round. We assume both $B$ and $C$
play the honest strategy. We normalize the total stake to $1$ and as a
consequence, use the stake and the fraction of stake held in a wallet
interchangeably.

###### Definition 0 (Reward of a Strategy).

For a strategy $\pi$ describing the actions taken by the adversary in each
round of $\operatorname{CSSPA}(\alpha,\beta)$, let the Bernoulli random
variable $X_{t}(\alpha,\beta;\pi)$ be $1$ if the adversary is elected in round
$t$ and $0$ otherwise. Then, the expected reward

$\operatorname{Rew}(\alpha,\beta;\pi)=\mathbb{E}\Big{[}\lim\inf_{T\xrightarrow{}\infty}\frac{\sum_{t=1}^{T}X_{t}(\alpha,\beta;\pi)}{T}\Big{]}$

equals the fraction of rounds led by the adversary in expectation over the
outcomes of the VRFs in each round.

When clear from the context, we drop the parameters $\alpha$ and $\beta$ and
denote $\operatorname{Rew}(\alpha,\beta;\pi)$ and $X_{t}(\alpha,\beta;\pi)$ by
$\operatorname{Rew}(\pi)$ and $X_{t}(\pi)$.

The above model of the CSSPA appears quite restrictive in more than one aspect
– the adversary can broadcast at most one credential, the adversary cannot
strategically distribute its stake into multiple accounts prior to round $1$,
and there are only two honest players in the network. In Appendix B, we recap
a very general model of $\operatorname{CSSPA}(\alpha,\beta)$ discussed in
Ferreira et al., (2022) and their results showing that the above restricted
version of the CSSPA has the same optimal adversarial reward as the more
general version.

###  3.2. Biased Seeds and Stopping Times

We aim to estimate the reward
$\operatorname{Rew}(\pi)=\mathbb{E}\Big{[}\lim\inf_{T\xrightarrow{}\infty}\frac{\sum_{t=1}^{T}X_{t}(\pi)}{T}\Big{]}$
the adversary wins by playing a strategy $\pi$. A tractable closed-form
expression for $X_{t}(\pi)$ is hard to find and computing its expected values
for all $1\leq t\leq\infty$ is infeasible. Therefore, it becomes imperative to
find a round $\tau$ such that the expected adversarial reward can be estimated
without computing the expected value of $X_{\tau+r}(\pi)$ for any $r>0$. We
call such a round $\tau$ a stopping time. The expected adversarial reward has
a much simpler expression in terms of stopping times.

###### Lemma 0 (Lemma 4.1 from Ferreira et al.,, 2022).

Suppose the strategy $\pi$ has an expected finite stopping time $\tau$ in
$\operatorname{CSSPA}(\alpha,\beta)$. Then,

$\operatorname{Rew}(\pi)=\frac{\mathbb{E}[\sum_{t=1}^{\tau}X_{t}(\pi)]}{\mathbb{E}[\tau]}$

where $\tau$ is a random variable denoting a stopping time.

Suppose we reach a round $\tau+1$ such that the adversary is indifferent
between the current seed $Q_{\tau+1}$ and a fresh draw from $U[0,1]$. We say
such a seed $Q_{\tau+1}$ is _unbiased_. The adversary’s rewards from the
rounds following $\tau+1$ is similar to restarting
$\operatorname{CSSPA}(\alpha,\beta)$ from round $1$, whose initial seed
$Q_{1}$ is drawn from $U[0,1]$ (in practise, this is done through an expensive
multi-party computation and is not susceptible to manipulation). The expected
adversarial reward can be computed by estimating only the distributions of
$X_{1}(\pi),X_{2}(\pi),\dots,X_{\tau}(\pi)$ and thus, $\tau$ is a stopping
time.

For an arbitrary round $t$, it is hard to determine whether the seed $Q_{t+1}$
is unbiased and whether $t$ is a stopping time. We define forced stopping
times so that they are much easier to identify. In the next few paragraphs, we
motivate forced stopping times through an example adversarial strategy.

For a stake $\alpha$ and a random seed $Q_{t}$ in round $t$, the probability
that the adversary gets elected is at most $\alpha$. However, the adversary
could have multiple wallets whose scores are smaller than the score of the
honest wallets $B$ and $C$. When $\beta=1$, the adversary knows the smallest
honest score and that broadcasting the credentials of any of its wallets with
a smaller score would ensure an adversarial wallet getting elected in round
$t$. It is convenient to explicitly christen these candidate adversarial
wallets.

###### Definition 0 (Potential Winners and Adversarial Potential Winners).

In round $t$ with seed $Q_{t}$, let $\hat{W}(Q_{t})$ be the set of all
adversarial wallets with a score less than that of $B$. Then, $\hat{W}(Q_{t})$
is the set of adversarial potential winners and
$W(Q_{t})=\hat{W}(Q_{t})\cup\\{B\\}$ is the set of potential winners in round
$t$.

Out of these adversarial potential winners, the adversary can choose to
broadcast the one that optimizes its future rewards, which can be estimated by
computing hypothetical seeds for the rounds following round $t$ (see bullet 4
from Definition 1). The adversary can also choose to sacrifice the current
round and remain silent if the future rewards from the honest wallet $B$
getting elected more than compensates for losing round $t$.

Suppose a seed $Q_{\tau+1}$ is realized for which the adversary has not
computed any hypothetical future seeds. At the instant in which $Q_{\tau+1}$
is realized, the adversary is indifferent between $Q_{\tau+1}$ and a fresh
draw from $U[0,1]$ and thus, $Q_{\tau+1}$ is unbiased. Now, consider a round
$\tau$ in which the smallest score either belongs to $B$ or $C$. The first
time the adversary learns the honest credential with the smallest score, the
adversary would have pre-computed neither the credential nor any hypothetical
future credentials following the honest credential since computing them would
require the secret key of the honest wallet with the smallest score. The
adversary cannot thwart $\operatorname{\textsc{Cred}}^{B}_{\tau}$ or
$\operatorname{\textsc{Cred}}^{C}_{\tau}$ from becoming the seed $Q_{\tau+1}$.
Thus, the seed $Q_{\tau+1}$ is unbiased and round $\tau$ is a stopping time.
We call such stopping times as forced stopping times. Forced stopping times
are easy to identify since we only have to ensure that the smallest score does
not belong to an adversarial wallet.

###### Definition 0 (Forced Stopping Time).

Let $i$ be the wallet with the smallest score in round $\tau$. $\tau$ is a
forced stopping time if $i\not\in A$.

###### Lemma 0 (Lemma 4.2 from Ferreira et al.,, 2022).

If $\tau$ is a forced stopping time, $\tau$ is a stopping time.

We will use $\tau$ to denote the first forced stopping time of the adversary.
We will only consider forced stopping times (and not any ‘unforced’ stopping
times) for the remainder of the paper. Because of this and for convenience, we
abuse notation and refer to forced stopping times plainly as stopping times.

###  3.3. The Omniscient Adversary

As a warm up, we look at the omniscient adversary studied by Ferreira et al.,
(2022) that is stronger than the adversary in
$\operatorname{CSSPA}(\alpha,\beta)$ in the following aspects:

  * •

$\beta=1$. Further, for any $r\geq 0$ and
$(i_{t},i_{t+1},\dots,i_{t+r})\in\big{(}A\cup\\{B\\}\big{)}^{r+1}$, the
adversary pre-computes the credentials
$\operatorname{\textsc{Cred}}^{i_{t+r^{\prime}}}_{t+r^{\prime}}$ for $1\leq
r^{\prime}\leq r$ assuming $i_{t+\hat{r}}$ is elected to lead in round
$t+\hat{r}$ for all $0\leq\hat{r}<r^{\prime}$. In other words, the omniscient
adversary can precompute hypothetical future credentials even when $B$ is
elected to be the leader.

  * •

$X_{t}=1$ for all rounds $t<\tau$, i.e., the omniscient adversary is rewarded
to delay the first stopping time, even if it entails being elected only for a
very small fraction of rounds. By Lemma 3, the omniscient reward

$\operatorname{Rew}^{\operatorname{OMNI}}(\pi)=\frac{\mathbb{E}[\sum_{t=1}^{\tau}X_{t}(\pi)]}{\mathbb{E}[\tau]}=\frac{\mathbb{E}[\tau-1]}{\mathbb{E}[\tau]}=1-\frac{1}{\mathbb{E}[\tau]}$

Similar to the adversary in $\operatorname{CSSPA}(\alpha,\beta)$, we define
$\tau$ to be a stopping time for the omniscient adversary if the set of
adversarial potential winners $\hat{W}$ for round $\tau$ is empty. We defer
our discussions on the omniscient adversary to Appendix C. We summarize our
findings in Theorem 7.

###### Theorem 7.

For the omniscient adversary with stake $\alpha$, there exists a constant
$\kappa\approx 0.38$ such that,

  1. (1)

for $\alpha>\kappa$, there exists a strategy $\pi$ such that
$\mathbb{E}[\tau]$ is unbounded and
$\operatorname{Rew}^{\operatorname{OMNI}}(\pi)=1$, and,

  2. (2)

for $\alpha\leq\kappa$ and any strategy $\pi$,
$\mathbb{E}[\tau]\leq\tfrac{1-3\alpha+3\alpha^{2}-3\alpha^{3}}{(1-3\alpha+\alpha^{2})(1-\alpha+\alpha^{2})}$
and
$\operatorname{Rew}^{\operatorname{OMNI}}(\pi)\leq\alpha\cdot\big{(}\tfrac{1-2\alpha+\alpha^{2}-\alpha^{3}}{1-3\alpha+3\alpha^{2}-3\alpha^{3}}\big{)}$.

We also show a non-closed form upper bound on the optimal omniscient rewards
that can be made tight up to an arbitrarily small additive error. The plots
comparing our upper bounds to Ferreira et al., (2022) can be found in Figure 4
in Appendix C.

The following results on the size of potential winners and first stopping time
of the omniscient adversary would be bootstrapped further to get upper bounds
on the optimal rewards of the actual adversary in
$\operatorname{CSSPA}(\alpha,\beta)$.

###### Lemma 0 (Corollary 4.1 from Ferreira et al.,, 2022).

For a random seed $Q_{t}\sim U[0,1]$ and $i^{*}\geq 0$, the probability
$Pr(|W_{t}(Q_{t})|=i^{*}+1)$ of the adversary having exactly $i^{*}+1$
potential winners equals $\alpha^{i^{*}}\,(1-\alpha)$.

###### Lemma 0.

For the omniscient adversary with stake $\alpha<\kappa$, $Pr(\tau>0)=1$ and
$Pr(\tau>1)=\alpha$. For $T\geq 2$,

$Pr(\tau>T)\leq\alpha^{2}\cdot\tfrac{2-2\alpha+\alpha^{2}}{1-\alpha+\alpha^{2}}\cdot\big{(}\alpha\cdot\tfrac{2-\alpha}{1-\alpha}\big{)}^{T-2}\text{.}$

##  4\. Estimating the Optimal Adversarial Reward

We proceed to designing simulations that estimate the expected adversarial
reward from playing a strategy $\pi$ in $\operatorname{CSSPA}(\alpha,\beta)$.
We find the optimal adversarial strategy in
$\operatorname{CSSPA}(\alpha,\beta)$ quite complex to describe. We reformulate
$\operatorname{CSSPA}(\alpha,\beta)$ such that a succinct description of the
optimal adversarial strategy becomes possible. Then, we propose a simulation
that computes the adversary’s optimal reward precisely but requires an
infinite run-time. We describe a sequence of modifications to the simulation
that trades off run-time for precision to get provable bounds on the
adversary’s optimal rewards.

###  4.1. A Linear Version of $\operatorname{CSSPA}(\alpha,\beta)$

Optimizing the adversarial reward
$\operatorname{Rew}(\pi)=\tfrac{\mathbb{E}[\sum_{t=1}^{\tau}X_{t}(\pi)]}{\mathbb{E}[\tau]}$
depends on maintaining a balance between getting a myopic gain in the reward
by winning the election in the current round and a long-term gain through
delaying the first stopping time. This inherent trade-off between the short-
term and long-term gains of actions in $\operatorname{CSSPA}(\alpha,\beta)$
makes both describing the optimal adversarial strategy and simulating it hard.
We reformulate $\operatorname{CSSPA}(\alpha,\beta)$ through an approach
similar to Sapirshtein et al., (2016) that allows the adversary to myopically
optimize its reward without having to worry about long-term consequences.

We introduce an entry fee $\lambda$ in $\operatorname{CSSPA}(\alpha,\beta)$
that the adversary is charged to participate in each round and consider the
total adversarial reward instead of the rate at which the adversary is
elected.

###### Definition 0 ($\operatorname{LinearCSSPA}(\alpha,\beta,\lambda)$).

In $\operatorname{LinearCSSPA}(\alpha,\beta,\lambda)$, the network consists of
three players- the adversary with stake $\alpha$, two honest players $B$ and
$C$ with stakes $\beta\,(1-\alpha)$ and $(1-\beta)\,(1-\alpha)$ respectively.
Prior to round $1$, the adversary learns the values of $\alpha$, $\beta$, the
entry fee $\lambda$ and that $B$ and $C$ are honest. For
$n\xrightarrow{}\infty$, the adversary distributes its stake into a set $A$ of
$n$ wallets, each containing a stake $\tfrac{\alpha}{n}$. The adversary makes
the following decisions in round $t$:

  1. (1)

The adversary pays an entry fee $\lambda$.

  2. (2)

The adversary learns the seed $Q_{t}$ of round $t$.

  3. (3)

The adversary computes the credentials $\operatorname{\textsc{Cred}}^{i}_{t}$
for all wallets $i\in A$. Further, the adversary learns the credentials
$\operatorname{\textsc{Cred}}^{B}_{t}$. The adversary knows that the
credential of player $C$ is drawn from
$\operatorname{exp}((1-\beta)\,(1-\alpha))$ but does not learn
$\operatorname{\textsc{Cred}}^{C}_{t}$.

  4. (4)

For any $r\geq 0$ and
$(i_{t},i_{t+1},\dots,i_{t+r})\in\big{(}A\cup\\{B\\}\big{)}\times A^{r}$, the
adversary precomputes the credentials
$\operatorname{\textsc{Cred}}^{i_{t+r^{\prime}}}_{t+r^{\prime}}$ for $1\leq
r^{\prime}\leq r$ assuming $i_{t+\hat{r}}$ is elected to lead in round
$t+\hat{r}$ for all $0\leq\hat{r}<r^{\prime}$.

  5. (5)

The adversary either remains silent or broadcasts the credential of a wallet
$i\in A$.

  6. (6)

The game terminates if either $B$ or $C$ have scores smaller than all wallets
$i\in A$, i.e, a stopping time is reached.

###### Definition 0 (Reward of a Strategy).

For a strategy $\pi$ played by the adversary in
$\operatorname{LinearCSSPA}(\alpha,\beta,\lambda)$, let the Bernoulli random
variable $X_{t}(\pi)$ be $1$ if the adversary is elected in round $t$ and $0$
otherwise. The adversary earns an expected reward

$\operatorname{Rew}^{\operatorname{Lin}}(\pi)=\mathbb{E}\big{[}\sum_{t=1}^{\tau}(X_{t}(\pi)-\lambda)\big{]}$

We conclude the discussion by relating the rewards $\operatorname{Rew}(\pi)$
in $\operatorname{CSSPA}(\alpha,\beta)$ and
$\operatorname{Rew}^{\operatorname{Lin}}(\pi)$ in
$\operatorname{LinearCSSPA}(\alpha,\beta,\lambda)$.

###### Theorem 3.

For an entry fee $\lambda$ and a strategy $\pi$,
$\operatorname{Rew}^{\operatorname{Lin}}(\pi)>0$ (resp.
$\operatorname{Rew}^{\operatorname{Lin}}(\pi)<0$) if and only if
$\lambda<\operatorname{Rew}(\pi)$ (resp. $\lambda>\operatorname{Rew}(\pi)$).
Further, $\operatorname{Rew}^{\operatorname{Lin}}(\pi)=0$ when
$\lambda=\operatorname{Rew}(\pi)$.

A standard binary search would locate the value of $\lambda$ such that
$\operatorname{Rew}^{\operatorname{Lin}}(\pi)=0$, in which case,
$\operatorname{Rew}(\pi)=\lambda$. We defer the proof to Appendix D.

###  4.2. The Ideal Simulation

$\operatorname{LinearCSSPA}(\alpha,\beta,\lambda)$ has a recursive structure
that we exploit while designing simulations to estimate
$\operatorname{Rew}^{\operatorname{Lin}}(\pi)$ of a strategy $\pi$. In some
round $t$, by broadcasting the credential
$\operatorname{\textsc{Cred}}^{i}_{t}$ of a wallet $i\in A$ and winning the
election (or remaining silent and letting $B$ with credential
$\operatorname{\textsc{Cred}}^{B}_{t}$ win), the adversary induces an instance
of $\operatorname{LinearCSSPA}(\alpha,\beta,\lambda)$ with an initial seed
$Q_{0}=\operatorname{\textsc{Cred}}^{i}_{t}$. If the adversary recursively
”knew” the expected future reward $r_{i}$ that it would get from broadcasting
$\operatorname{\textsc{Cred}}^{i}_{t}$ for each adversarial potential winner
$i$ and the reward $r_{0}$ from letting $B$ win, the adversary can decide its
actions just based on
$\vec{r}=\big{(}r_{i}\big{)}_{i\in\mathbb{N}\cup\\{0\\}}$ and the scores
$\vec{c}=\big{(}c_{i}\big{)}_{i\in\mathbb{N}\cup\\{0\\}}$ of the wallets in
$A\cup\\{B\\}$111111This is not entirely true. The adversary can still play
strategies based on the credentials and rewards from previous rounds. However,
given that the adversary’s goal is to optimize the total rewards earned across
rounds, such strategies can be safely ignored. As we will see, the optimal
strategy can be codified in this language.. Of course, the adversary always
runs the risk of the current round being a stopping time, in which case, the
total future rewards earned by the adversary equals zero.

Let $\operatorname{D}^{\pi}$ be the distribution of rewards the adversary
achieves by playing the strategy $\pi$ in
$\operatorname{LinearCSSPA}(\alpha,\beta,\lambda)$. We are interested in
estimating the expected reward $\mathbb{E}_{s\sim\operatorname{D}^{\pi}}[s]$.
We do so by constructing the CDF of $\operatorname{D}^{\pi}$ in
$\text{AddLayer}(\alpha,\beta,\lambda,\pi,\operatorname{D}^{\pi})$ by sampling
from $\operatorname{D}^{\pi}$ infinitely many times. This can be done by
setting up infinitely many ‘induced-instances’ of
$\operatorname{LinearCSSPA}(\alpha,\beta,\lambda)$. For each of these induced-
instances:

  1. (1)

For each $i\geq 1$, we sample the $i\textsuperscript{th}$ smallest score
$c_{i}$ amongst all adversarial wallets using Lemma 9:

$c_{1}\xleftarrow{}\operatorname{exp}(\alpha),c_{i}\xleftarrow{}c_{i-1}+\operatorname{exp}(\alpha)$

  2. (2)

For each $i\geq 1$, we sample the reward $r_{i}$ earned from broadcasting the
credential of the adversarial wallet with the $i\textsuperscript{th}$ smallest
score from the distribution $\operatorname{D}^{\pi}$.

  3. (3)

We compute the adversarial reward in expectation over the reward $r_{0}$ from
letting $B$ win, the scores $c_{0}$ and $c_{-1}$ of $B$’s and $C$’s wallets
respectively by simulating the behaviour of $\pi$ for scores
$\vec{c}=\big{(}c_{i}\big{)}_{i\in\mathbb{N}\cup\\{0\\}}$ and rewards
$\vec{r}=\big{(}r_{i}\big{)}_{i\in\mathbb{N}\cup\\{0\\}}$.

Estimating the adversarial reward reduces to finding a fixed-point
$\operatorname{D}^{\pi}$ to
$\text{AddLayer}(\alpha,\beta,\lambda,\pi,\operatorname{D}^{\pi})$.

$\text{AddLayer}(\alpha,\beta,\lambda,\pi,\operatorname{D}^{\pi})$: (1) For
$1\leq\ell\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}n_{t}=\infty}$.
(a) $\text{DrawAdv}(\alpha,\operatorname{D}^{\pi})$: • Sample $\vec{r}_{-0}$:
Draw
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}k=\infty}$
rewards $r_{1},r_{2},\dots,r_{k}$ i.i.d from $\operatorname{D}^{\pi}$. •
Sample $\vec{c}_{-0}$: Draw
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}k=\infty}$
scores $c_{1},c_{2},\dots,c_{k}$ of adversarial wallet as follows. Draw
$c_{1}\xleftarrow{}\operatorname{exp}(\alpha)$ and
$c_{i+1}\xleftarrow{}c_{i}+\operatorname{exp}(\alpha)$ (a fresh sample for
each $i$) for $1\leq i\leq k-1$. For convenience, set $c_{k+1}=\infty$. •
Return $(\vec{r}_{-0},\vec{c}_{-0})$. (b)
$\text{sample}(\alpha,\beta,\lambda,\vec{c}_{-0},\vec{r}_{-0},\pi,\operatorname{D}^{\pi})$:
Simulate the action of the strategy $\pi$ in the current round given
$\operatorname{D}^{\pi}$, $\vec{r}_{-0}$ and $\vec{c}_{-0}$. Return the reward
$s_{\ell}$ in expectation over the reward $r_{0}$ from letting $B$ win, $B$’s
score $c_{0}$ and $C$’s score $c_{-1}$. (2) Return $\operatorname{D}^{\pi}$ to
be the uniform distribution over $\\{s_{1},s_{2},\dots,s_{n_{t}}\\}$.
$\text{Simulate}(\alpha,\beta,\lambda,\pi)$: (1) Compute a fixed-point
$\operatorname{D}^{\pi}$ to
$\text{AddLayer}(\alpha,\beta,\lambda,\pi,\operatorname{D}^{\pi})$. (2) Return
$\mathbb{E}_{s\sim\operatorname{D}^{\pi}}[s]$.

See Section I.2 for a summary of the notations and functions used in the
simulations.

###  4.3. The Optimal Solution

We describe the optimal strategy $\pi^{\operatorname{OPT}}$ in the recursive
language introduced in Section 4.2. Let
$\operatorname{D}^{\operatorname{OPT}}=\operatorname{D}^{\pi^{\operatorname{OPT}}}$
be the distribution of rewards from playing $\pi^{\operatorname{OPT}}$. At a
start of a round $t$, the adversary learns the scores $\vec{c}$ of wallets in
$A\cup\\{B\\}$ and rewards $\vec{r}$ from remaining silent and from
broadcasting the credential of each wallet in $A$. We use $\vec{c}_{-0}$ and
$\vec{r}_{-0}$ to denote the scores $\big{(}c_{i}\big{)}_{i\in\mathbb{N}}$ and
rewards $\big{(}r_{i}\big{)}_{i\in\mathbb{N}}$ associated with the wallets in
$A$. Re-index the adversary’s wallets (and therefore, $\vec{c}_{-0}$ and
$\vec{r}_{-0}$) in increasing order of its scores. Let
$i^{*}(\vec{c}):=|\\{i>0|c_{i}\leq c_{0}\\}|$ be the number of adversarial
potential winners.

We compare the expected future rewards of all possible actions the adversary
can take at the start of round $t$.

  1. (1)

Suppose the adversary abstains from broadcasting. It earns a reward $r_{0}$
unless a stopping time is reached, which happens either when
$i^{*}(\vec{c})=0$ or when $C$ has a score
$c_{-1}\sim\operatorname{exp}((1-\beta)\,(1-\alpha))$ smaller than the score
$c_{0}$ of $B$. The probability of $C$ having a larger score than $c_{0}$
equals $e^{-c_{0}\,(1-\beta)\,(1-\alpha)}$. Thus, the expected reward from
remaining silent equals
$e^{-c_{0}\,(1-\beta)\,(1-\alpha)}r_{0}\cdot\mathbbm{1}(i^{*}(\vec{c})\neq
0)$. We define

$h(c_{0},r_{0}):=e^{-c_{0}\,(1-\beta)\,(1-\alpha)}r_{0}$

  2. (2)

From broadcasting the credential of an adversarial potential winner $i$ with
score $c_{i}$ and future reward $r_{i}$, the adversary earns a reward $1$ from
getting elected in the current round and thus, a total reward $(1+r_{i})$.
This, once again, is subject to the current round not being a stopping time.
The current round is not a forced stopping time if $C$ has a score larger than
$c_{i}$, which happens with probability $e^{c_{i}\,(1-\beta)\,(1-\alpha)}$,
and if $i^{*}(\vec{c})\neq 0$. The adversary has a potential winner $i$ and
$i^{*}(\vec{c})$ is at least $1$ as a consequence. Hence, the expected reward
from broadcasting the credential of $i$ equals
$e^{c_{i}\,(1-\beta)\,(1-\alpha)}\,(1+r_{i})$. The adversary can broadcast the
credential of the wallet that maximizes its reward to earn

$g(c_{0},\vec{c}_{-0},\vec{r}_{-0})=\max_{i\leq
i^{*}(\vec{c})}\\{e^{-c_{i}\,(1-\beta)\,(1-\alpha)}(1+r_{i})\\}$

The adversary also pays an entry fee $\lambda$. Between remaining silent and
broadcasting its best credential, the adversary wins

$\begin{split}\max\\{h(c_{0},r_{0})&\mathbbm{1}(i^{*}(\vec{c})\neq
0),g(c_{0},\vec{c}_{-0},\vec{r}_{-0})\\}-\lambda\\\
&=\max\\{h(c_{0},r_{0})\mathbbm{1}(i^{*}(\vec{c})\neq
0),g(c_{0},\vec{c}_{-0},\vec{r}_{-0})\mathbbm{1}(i^{*}(\vec{c})\neq
0)\\}-\lambda\\\
&=\max\\{h(c_{0},r_{0}),g(c_{0},\vec{c}_{-0},\vec{r}_{-0})\\}\mathbbm{1}(i^{*}(\vec{c})\neq
0)-\lambda\end{split}$

While using the future rewards from round $t$ to compute the optimal action to
take in round $t-1$, the adversary will not know the values $c_{0}$ and
$r_{0}$ since $B$ does not broadcast $\operatorname{\textsc{Cred}}^{B}_{t}$
until the start of round $t$. The adversary can only compute the future
rewards from playing an action in expectation over $c_{0}$ and $r_{0}$. With
this in mind, we construct $\operatorname{D}^{\operatorname{OPT}}$ to be the
distribution of (future) rewards in expectation over $c_{0}$ and $r_{0}$.
Given $\vec{c}_{-0}$ and $\vec{r}_{-0}$, we implement a sampling procedure
$\text{sample}(\alpha,\beta,\lambda,\vec{c}_{-0},\vec{r}_{-0},\pi^{\operatorname{OPT}},\operatorname{D}^{\operatorname{OPT}})$
by setting the $\ell^{\text{th}}$ sample $s_{\ell}$ to be

$\mathbb{E}_{c_{0}\sim\operatorname{exp}((1-\beta)\,(1-\alpha)),r_{0}\sim\operatorname{D}^{\operatorname{OPT}}}[\max\\{h(c_{0},r_{0}),g(c_{0},\vec{c}_{-0},\vec{r}_{-0})\\}\mathbbm{1}(i^{*}(\vec{c})\neq
0)]-\lambda$

Finding a fixed-point $\operatorname{D}^{\operatorname{OPT}}$ for
$\text{AddLayer}(\alpha,\beta,\lambda,\pi^{\operatorname{OPT}},\operatorname{D}^{\operatorname{OPT}})$
seems intractable and we resort to heuristic methods instead. One natural
heuristic would be to begin at the point-mass distribution
$\operatorname{D}^{\operatorname{OPT}}_{0}$ at $0$ and iterate infinitely many
times to get the sequence
$\big{(}\operatorname{D}^{\operatorname{OPT}}_{t}\big{)}_{t\in\mathbb{N}\cup\\{0\\}}$
of distributions satisfying
$\operatorname{D}^{\operatorname{OPT}}_{t+1}=\text{AddLayer}(\alpha,\beta,\lambda,\pi^{\operatorname{OPT}},\operatorname{D}^{\operatorname{OPT}}_{t})$.
We end this section by summarizing the challenges in executing the above
heuristic.

$\text{AddLayer}(\alpha,\beta,\lambda,\pi^{\operatorname{OPT}},\operatorname{D}^{\operatorname{OPT}}_{t-1})$:
(1) For
$1\leq\ell\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}n_{t}=\infty}$.
(a) $\text{DrawAdv}(\alpha,\operatorname{D}^{\operatorname{OPT}}_{t-1})$: •
Sample $\vec{r}_{-0}$: Draw
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}k=\infty}$
rewards $r_{1},r_{2},\dots,r_{k}$ i.i.d from
$\operatorname{D}^{\operatorname{OPT}}_{t-1}$. • Sample $\vec{c}_{-0}$: Draw
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}k=\infty}$
scores $c_{1},c_{2},\dots,c_{k}$ of adversarial wallet as follows. Draw
$c_{1}\xleftarrow{}\operatorname{exp}(\alpha)$ and
$c_{i+1}\xleftarrow{}c_{i}+\operatorname{exp}(\alpha)$ (a fresh sample for
each $i$) for $1\leq i\leq k-1$. For convenience, set $c_{k+1}=\infty$. •
Return $(\vec{r}_{-0},\vec{c}_{-0})$. (b)
$\text{sample}(\alpha,\beta,\lambda,\vec{c}_{-0},\vec{r}_{-0},\pi^{\operatorname{OPT}},\operatorname{D}^{\operatorname{OPT}}_{t-1})$:
Return sample $s_{\ell}$ equal to
$\begin{split}&\mathbb{E}_{c_{0}\sim\operatorname{exp}(\beta\,(1-\alpha)),r_{0}\sim\operatorname{D}^{\operatorname{OPT}}_{t-1}}\big{[}\max_{0\leq
i\leq
i^{*}(\vec{c})}\\{e^{-c_{i}\cdot(1-\beta)\cdot(1-\alpha)}\,(r_{i}+\mathbbm{1}(i\neq
0))\\}\cdot\mathbbm{1}(i^{*}(\vec{c})\neq 0)\big{]}-\lambda\end{split}$ (2)
Return $\operatorname{D}^{\operatorname{OPT}}_{t}$ to be the uniform
distribution over $\\{s_{1},s_{2},\dots,s_{n_{t}}\\}$.
$\text{Simulate}(\alpha,\beta,\lambda,\pi^{\operatorname{OPT}})$: (1)
Initialize $\operatorname{D}^{\operatorname{OPT}}_{0}$ to be the point-mass
distribution at $0$. (2) For $1\leq
t\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}T=\infty}$:
(a)
$\operatorname{D}^{\operatorname{OPT}}_{t}=\text{AddLayer}(\alpha,\beta,\lambda,\pi^{\operatorname{OPT}},\operatorname{D}^{\operatorname{OPT}}_{t-1})$.
(3) Return $\mathbb{E}_{s\sim\operatorname{D}^{\operatorname{OPT}}_{T}}[s]$.

  1. (1)

The iterated-point heuristic does not guarantee convergence. Even if the
iteration converges, there could be a multitude of fixed-points and the
iteration could converge to a distribution that is not the optimal reward.

  2. (2)

We run $\text{AddLayer}(\alpha,\beta,\lambda,\pi^{\operatorname{OPT}},\cdot)$
$T=\infty$ many times. In each execution of
$\text{AddLayer}(\alpha,\beta,\lambda,\pi^{\operatorname{OPT}},\cdot)$, the
adversary can pick one of $k=\infty$ actions– one each for broadcasting
credentials of wallets $i\in A$ and one for staying silent.
$\pi^{\operatorname{OPT}}$ compares the rewards of each of these actions
before making a decision.

  3. (3)

Given a distribution $\operatorname{D}_{t}$, we compute
$\text{AddLayer}(\alpha,\beta,\lambda,\pi^{\operatorname{OPT}},\operatorname{D}_{t})$
by constructing $n_{t}=\infty$ samples. As we will see in Section 4.4.3, the
simulation is not even an unbiased estimator of the reward
$\mathbb{E}_{s\sim\operatorname{D}^{\operatorname{OPT}}_{T}}[s]$ once we
constrain $n_{t}$ to be finite.

  4. (4)

The sample $s_{\ell}$ is constructed by computing the reward in expectation
over $B$’s score $c_{0}$ and reward $r_{0}$ from remaining silent. This
involves calculating a double integral. The integrals can be calculated in
finite-time by approximating them by a Riemann sum. However, even a polynomial
run-time would not be practical due to the sheer number of samples we
construct. We require a linear run-time.

###  4.4. Moving from Ideal to Practical

####  4.4.1. Convergence of the Iterated-Point Heuristic

We discuss the natural variant
$\operatorname{LinearCSSPA}(\alpha,\beta,\lambda,T)$ that terminates after $T$
rounds if a stopping time has not been reached yet. We will argue that the
distribution of optimal rewards
$\big{(}\operatorname{D}^{\operatorname{OPT}}_{T}\big{)}_{T\in\mathbb{N}\cup\\{0\\}}$
satisfies the same recursion as the iterated-point heuristic on
$\text{AddLayer}(\alpha,\beta,\lambda,\pi^{\operatorname{OPT}},\cdot)$ and
converges to $\operatorname{D}^{\operatorname{OPT}}$ as
$T\xrightarrow{}\infty$.

When $T=0$, the game terminates even before it starts and the adversary gets a
total reward zero. Thus, $\operatorname{D}^{\operatorname{OPT}}_{0}$ is the
point-mass on zero, identical to the initial point of the iterated-point
heuristic. $t$ rounds before termination, by broadcasting the credential
$\operatorname{\textsc{Cred}}^{i}_{-t}$ of a wallet $i\in A$ ($i=B$ if the
adversary remains silent), the adversary induces an instance of
$\operatorname{LinearCSSPA}(\alpha,\beta,\lambda,t-1)$ with an initial seed
$Q_{0}=\operatorname{\textsc{Cred}}^{i}_{-t}$. Thus, if the adversary
recursively knew the rewards
$r_{i}\sim\operatorname{D}^{\operatorname{OPT}}_{t-1}$ from each potential
winner $i$, the adversary would broadcast the credential (or stay silent) that
would maximize its reward from the last $t-1$ rounds. This is the same
operation performed by
$\text{AddLayer}(\alpha,\beta,\lambda,\pi^{\operatorname{OPT}},\cdot)$ on
$\operatorname{D}^{\operatorname{OPT}}_{t-1}$. By induction, the distribution
of rewards $\operatorname{D}^{\operatorname{OPT}}_{t}$ equals the reward
distribution
$\text{AddLayer}(\alpha,\beta,\lambda,\pi^{\operatorname{OPT}},\operatorname{D}^{\operatorname{OPT}}_{t-1})$
output by the $t\textsuperscript{th}$ iteration of the iterated-point method.

As $T\xrightarrow{}\infty$, the distribution of rewards $T$ rounds before
termination and $T-1$ rounds before termination are identical. This is
equivalent to claiming $\operatorname{D}^{\operatorname{OPT}}_{T}$ as
$T\xrightarrow{}\infty$ approaches the reward distribution
$\operatorname{D}^{\operatorname{OPT}}$. Thus, the iterated-point method
converges and converges to the correct distribution of rewards.

####  4.4.2. Infinite Rounds and Credentials

Let $\operatorname{LinearCSSPA}(\alpha,\beta,\lambda,T)$ be the variant of
$\operatorname{LinearCSSPA}(\alpha,\beta,\lambda)$ terminating after round
$T$. $\text{Simulate}(\alpha,\beta,\lambda,\pi^{\operatorname{OPT}})$ loops
infinitely to construct the distribution of adversarial rewards in
$\operatorname{LinearCSSPA}(\alpha,\beta,\lambda,T)$ as
$T\xrightarrow{}\infty$. Further, for each round of the simulation,
$\text{DrawAdv}(\alpha,\operatorname{D}^{\operatorname{OPT}}_{t})$ samples a
score and a reward for each of the infinite wallets the adversary operates. We
revisit $\operatorname{CSSPA}(\alpha,\beta)$ and argue that terminating
$\operatorname{CSSPA}(\alpha,\beta)$ after $T$ rounds and constraining the
adversary to broadcasting the credentials of a wallet only if it is amongst
the $k$ smallest scores in $A$ does not cause a significant drop in the
adversary’s optimal reward. Once established, we can estimate the reward from
playing $\pi^{\operatorname{OPT}}_{T,k}$, the optimal strategy in
$\operatorname{CSSPA}(\alpha,\beta)$ that terminates after $T$ rounds and
never uses a score outside the $k$ smallest scores in $A$, instead of
estimating the reward from $\pi^{\operatorname{OPT}}$.

We abuse notation to describe the optimal strategy of the adversary in
$\operatorname{CSSPA}(\alpha,\beta)$ as $\pi^{\operatorname{OPT}}$ and its
reward distribution by $\operatorname{D}^{\operatorname{OPT}}$. We say the
adversary is $k$-scored if the adversary is constrained to either stay silent
or broadcast a credential amongst its wallets with the $k$ smallest scores.

###### Theorem 4.

For $\alpha\leq 0.29$ and a $k$-scored adversary, the difference in the
expected rewards between playing $\pi^{\operatorname{OPT}}$ and
$\pi^{\operatorname{OPT}}_{T,k}$ in $\operatorname{CSSPA}(\alpha,\beta)$
satisfies

$0\leq|\operatorname{Rew}(\pi^{\operatorname{OPT}})-\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,k})|\leq\alpha^{2}\cdot\tfrac{2-2\alpha+\alpha^{2}}{1-\alpha+\alpha^{2}}\cdot[\alpha\cdot\tfrac{2-\alpha}{1-\alpha}]^{T-2}+\alpha^{k}$

We defer the proof to Appendix E.

We estimate the $k$-scored adversary’s optimal reward in
$\operatorname{LinearCSSPA}(\alpha,\beta,\lambda,T)$ and binary search over
$\lambda$ to estimate the adversarial reward
$\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,k})$ in
$\operatorname{CSSPA}(\alpha,\beta)$. We can then upper bound and lower bound
the optimal reward $\operatorname{Rew}(\pi^{\operatorname{OPT}})$ by

$\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,k})\leq\operatorname{Rew}(\pi^{\operatorname{OPT}})\leq\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,k})+\alpha^{2}\cdot\tfrac{2-2\alpha+\alpha^{2}}{1-\alpha+\alpha^{2}}\cdot[\alpha\cdot\tfrac{2-\alpha}{1-\alpha}]^{T-2}+\alpha^{k}$

We abuse notation as usual and call the $k$-scored adversary’s optimal
strategy in $\operatorname{LinearCSSPA}(\alpha,\beta,\lambda,T)$ as
$\pi^{\operatorname{OPT}}_{T,k}$. Let
$\operatorname{D}^{\operatorname{OPT}}_{T,k}$ be our estimate of the
distribution of rewards from playing $\pi^{\operatorname{OPT}}_{T,k}$. We
modify the simulation to terminate after $T$ rounds and bake the $k$-scored
adversary into
$\text{AddLayer}(\alpha,\beta,\lambda,\pi^{\operatorname{OPT}}_{T,k},\cdot)$.

$\text{AddLayer}(\alpha,\beta,\lambda,k,\pi^{\operatorname{OPT}}_{T,k},\operatorname{D}^{\operatorname{OPT}}_{t-1,k})$:
(1) For
$1\leq\ell\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}n_{t}=\infty}$.
(a) $\text{DrawAdv}(\alpha,\operatorname{D}^{\operatorname{OPT}}_{t-1,k})$: •
Sample $\vec{r}_{-0}$: Draw $k$ rewards $r_{1},r_{2},\dots,r_{k}$ i.i.d from
$\operatorname{D}^{\operatorname{OPT}}_{t-1}$. • Sample $\vec{c}_{-0}$: Draw
$k$ scores $c_{1},c_{2},\dots,c_{k}$ of adversarial wallet as follows. Draw
$c_{1}\xleftarrow{}\operatorname{exp}(\alpha)$ and
$c_{i+1}\xleftarrow{}c_{i}+\operatorname{exp}(\alpha)$ (a fresh sample for
each $i$) for $1\leq i\leq k-1$. For convenience, set $c_{k+1}=\infty$. •
Return $(\vec{r}_{-0},\vec{c}_{-0})$. (b)
$\text{sample}(\alpha,\beta,\lambda,\vec{c}_{-0},\vec{r}_{-0},\pi^{\operatorname{OPT}}_{T,k},\operatorname{D}^{\operatorname{OPT}}_{t-1,k})$:
Return sample $s_{\ell}$ (2) Return
$\hat{\operatorname{D}}^{\operatorname{OPT}}_{t,k}$ to be the uniform
distribution over $\\{s_{1},s_{2},\dots,s_{n_{t}}\\}$.
$\text{TruncatedSimulate}(\alpha,\beta,\lambda,T,k,\pi^{\operatorname{OPT}}_{T,k})$:
(1) Initialize $\operatorname{D}^{\operatorname{OPT}}_{0,k}$ to be the point-
mass distribution at $0$. (2) For $1\leq t\leq T$: (a)
$\operatorname{D}^{\operatorname{OPT}}_{t,k}=\text{AddLayer}(\alpha,\beta,\lambda,k,\pi^{\operatorname{OPT}}_{T,k},\operatorname{D}^{\operatorname{OPT}}_{t-1,k})$.
(3) Return $\mathbb{E}_{s\sim\operatorname{D}^{\operatorname{OPT}}_{T,k}}[s]$.

####  4.4.3. Constructing Infinitely many Samples for
$\text{AddLayer}(\alpha,\beta,\lambda,k,\pi^{\operatorname{OPT}}_{T,k},\cdot)$

We address the infinite run-time for
$\text{AddLayer}(\alpha,\beta,\lambda,k,\pi^{\operatorname{OPT}}_{T,k},\cdot)$
from constructing infinitely many samples to perfectly describe the CDF of its
output. For an input distribution $\operatorname{D}_{0}$, we want to
approximate the sequence of distributions
$\big{(}\operatorname{D}_{t}\big{)}_{0\leq t\leq T}$ such that
$\operatorname{D}_{t}:=\text{AddLayer}(\alpha,\beta,\lambda,k,\pi^{\operatorname{OPT}}_{T,k},\operatorname{D}_{t-1})$
while constructing only finitely many samples for each of them. In Section
F.1, we discuss the challenges from using the most natural technique to bound
the error from estimation in our simulations– Chernoff bounds or McDiarmid’s
inequality followed by a union bound. Even more importantly, we also find that
the estimator that arises from constructing finite number of samples might not
even be unbiased (Section F.2).

We tackle the above challenges by maintaining two distributions,
$\overline{\operatorname{D}}_{t}$ that dominates $\operatorname{D}_{t}$ and
$\underline{\operatorname{D}}_{t}$ that is dominated by
$\operatorname{D}_{t}$. We sketch our method for constructing an empirical
distribution that is dominated by the true distribution. Suppose for a
sufficiently large number of samples, we can guarantee that, for all values
$r$, the quantile $\tilde{q}$ in the empirical distribution constructed by
sampling $n$ times and the quantile $q$ in the true distribution satisfy
$\tilde{q}\in[q-\delta,q+\delta]$. Dropping the $\delta$ smallest (strongest)
quantiles and replacing them with $\delta n$ samples of the infimum of the
true distribution would give us a new estimated distribution that is dominated
by the true distribution. We call this process deflation. We will compute
$\underline{\operatorname{D}}_{t}$ by first computing
$\text{AddLayer}(\alpha,\beta,\lambda,k,\pi^{\operatorname{OPT}}_{T,k},\underline{\operatorname{D}}_{t-1})$
and then deflating the outcome by a suitable parameter $\delta$. By a
straightforward induction, $\underline{\operatorname{D}}_{t}$ is dominated by
$\operatorname{D}_{t}$.

We can construct $\overline{\operatorname{D}}_{t}$ from
$\overline{\operatorname{D}}_{t-1}$ through an analogous inflation procedure.
However, the error in the estimated reward due to inflation is much larger
than the error due to deflation. An inflated reward with a quantile
$\tilde{q}\in[0,\delta]$ is much more likely to be chosen by an adversary,
since the adversary picks its optimal future rewards). This leaves a bigger
impact on the estimated reward and influences the rewards in successive rounds
too. This differs from deflate since a deflated reward with a quantile
$\tilde{q}\in[1-\delta,1]$ is very likely to be ignored by the adversary since
the reward from a different wallet is likely to be higher. To mitigate the
strong credentials from drifting the estimated reward far way from
$\mathbb{E}_{s\sim\operatorname{D}_{t}}[s]$, we perform a more nuanced
inflation procedure.

$\text{Deflate}(n,\gamma,\operatorname{D},t):$ Given an input $D$ drawn
uniformly from $n$ samples, (1) Delete the largest
$n\cdot\sqrt{\tfrac{\ln\gamma^{-1}}{2n}}$ samples from $D$ (2) Append
$n\cdot\sqrt{\tfrac{\ln\gamma^{-1}}{2n}}$ copies of $-\lambda$ to
$\operatorname{D}$ $\text{Inflate}(n,\gamma,\omega,\operatorname{D},t)$: Given
an input $D$ drawn uniformly from $\big{(}s_{\ell}\big{)}_{1\leq\ell\leq n}$
(in descending order), (1) Delete the smallest
$n\cdot\sqrt{\tfrac{\ln\gamma^{-1}}{2n}}$ samples from $\operatorname{D}$ (2)
Append $\omega n$ copies of $t\,(1-\lambda)$ to $\operatorname{D}$ (3) For
$1\leq\ell<\frac{n}{\omega\,n}\cdot\sqrt{\tfrac{\ln\gamma^{-1}}{2n}}$: •
Append $\omega n$ copies of $s_{\ell}$

###### Theorem 5.

Let
$\text{TruncatedSimulate}(\alpha,\beta,\lambda,T,k,\pi^{\operatorname{OPT}}_{T,k},\gamma,\omega)$
output an upper bound $\overline{\operatorname{D}}_{T,k}$ and a lower bound
$\underline{\operatorname{D}}_{T,k}$. Then,

  1. (1)

With probability at least $1-T\,\Big{(}\gamma+\tfrac{e^{-\omega
n}}{\omega}\,\sqrt{\tfrac{\ln\gamma^{-1}}{2n}}\Big{)}$,
$\mathbb{E}_{s\sim\overline{\operatorname{D}}_{T,k}}[s]\geq\mathbb{E}_{s\sim\operatorname{D}^{\operatorname{OPT}}_{T,k}}[s]$.

  2. (2)

With probability at least $1-T\,\gamma$,
$\mathbb{E}_{s\sim\underline{\operatorname{D}}_{T,k}}[s]\leq\mathbb{E}_{s\sim\operatorname{D}^{\operatorname{OPT}}_{T,k}}[s]$.

We defer the proof to Section F.3.

Our estimate is not precisely equal to
$\operatorname{D}^{\operatorname{OPT}}_{T,k}$ and to differentiate the two, we
denote our estimation of $\operatorname{D}^{\operatorname{OPT}}_{T,k}$ by
$\hat{\operatorname{D}}^{\operatorname{OPT}}_{T,k}$. We update the simulations
to contain inflate and deflate.

$\text{FiniteSampleAddLayer}(\alpha,\beta,\lambda,k,t,n,\pi^{\operatorname{OPT}}_{T,k},\gamma,\omega,\hat{\operatorname{D}}^{\operatorname{OPT}}_{t-1,k})$:
(1) For $1\leq\ell\leq n$. (a)
$\text{DrawAdv}(\alpha,\hat{\operatorname{D}}^{\operatorname{OPT}}_{t-1,k})$.
(b)
$\text{sample}(\alpha,\beta,\lambda,\vec{c}_{-0},\vec{r}_{-0},\pi^{\operatorname{OPT}}_{T,k},\hat{\operatorname{D}}^{\operatorname{OPT}}_{t-1,k})$:
Return sample $s_{\ell}$ (2)
$\tilde{\operatorname{D}}^{\operatorname{OPT}}_{t,k}$ be the uniform
distribution over $\big{(}s_{\ell}\big{)}_{1\leq\ell\leq n}$ (in descending
order) (3) Inflate while computing the upper bound and deflate while computing
the lower bound. •
$\text{Deflate}(n,\gamma,\tilde{\operatorname{D}}^{\operatorname{OPT}}_{t,k},t):$
(a) Delete the largest $n\cdot\sqrt{\tfrac{\ln\gamma^{-1}}{2n}}$ samples from
$\tilde{\operatorname{D}}^{\operatorname{OPT}}_{t,k}$ (b) Append
$n\cdot\sqrt{\tfrac{\ln\gamma^{-1}}{2n}}$ copies of $-\lambda$ to
$\tilde{\operatorname{D}}^{\operatorname{OPT}}_{t,k}$ •
$\text{Inflate}(n,\gamma,\omega,\tilde{\operatorname{D}}^{\operatorname{OPT}}_{t,k},t)$:
(a) Delete the smallest $n\cdot\sqrt{\tfrac{\ln\gamma^{-1}}{2n}}$ samples from
$\tilde{\operatorname{D}}^{\operatorname{OPT}}_{t,k}$ (b) Append $\omega n$
copies of $t\,(1-\lambda)$ to
$\tilde{\operatorname{D}}^{\operatorname{OPT}}_{t,k}$ (c) For
$1\leq\ell<\frac{n}{\omega\,n}\cdot\sqrt{\tfrac{\ln\gamma^{-1}}{2n}}$: –
Append $\omega n$ copies of $s_{\ell}$ (4) Return
$\hat{\operatorname{D}}^{\operatorname{OPT}}_{t,k}$ to be the uniform
distribution over $\\{s_{1},s_{2},\dots,s_{n_{t}}\\}$.
$\text{TruncatedSimulate}(\alpha,\beta,\lambda,T,k,\pi^{\operatorname{OPT}}_{T,k},\gamma,\omega)$:
(1) Initialize $\hat{\operatorname{D}}^{\operatorname{OPT}}_{0,k}$ to be the
point-mass distribution at $0$. (2) For $1\leq t\leq T$: (a)
$\hat{\operatorname{D}}^{\operatorname{OPT}}_{t,k}=\text{FiniteSampleAddLayer}(\alpha,\beta,\lambda,k,t,n,\pi^{\operatorname{OPT}}_{T,k},\gamma,\omega,\hat{\operatorname{D}}^{\operatorname{OPT}}_{t-1,k})$.
(3) Return
$\mathbb{E}_{s\sim\hat{\operatorname{D}}^{\operatorname{OPT}}_{T,k}}[s]$.

####  4.4.4. Computing Expectations

In this section, we tackle the final challenge of needing to compute integrals
accurately while constructing the sample $s_{\ell}$. This involves computing a
double integral, one over the score $c_{0}$ of $B$ and the reward $r_{0}$ from
staying silent. Naively integrating over the reward distribution from the
previous round described by $n$ samples would result in a run-time of
$\Omega(n)$ for each of the $n$ samples, and consequently $\Omega(n^{2})$ for
simulating one round. Even though this is $\textsc{Poly}(n)$, it still turns
out to be intractable to run for the extremely large number of samples we
expect to handle each round. Instead, we aim to reduce the run-time to
$\tilde{O}(n)$.

To begin with, observe that for each sample $s_{\ell}$, we are drawing $k$
scores for the wallets of the $k$-scored adversary. Thus, we end up with a
run-time of $\Omega(k\cdot n)$ no matter what we do. Any additional compute
that we perform for each sample is only going to increase the order of the
run-time. Thus, our aim is to run as much pre-compute as possible before even
constructing the first sample, and minimize the number of fresh computations
needed to be performed with each sample. We get a practical run-time through a
combination of pre-computes and by computing the integrals involved with
taking expectations over $r_{0}$ and $c_{0}$ as a discrete sum. We defer the
details to Appendix G. Note that we introduce two parameters $\epsilon$ and
$\eta$ that reflect the precision to which we discretize the distributions
constructed during the simulations and the precision to which we approximate
the two integrals. We do all our pre-computations through the function
$\text{Precompute}(\hat{\operatorname{D}}_{,}\epsilon,\eta,t)$.

###### Lemma 0.

$\text{Precompute}(\hat{\operatorname{D}},\epsilon,\eta,t)$ terminates in
$O(\frac{t}{\epsilon\,\eta})$ time.

$\text{TruncatedSimulate}(\alpha,\beta,\lambda,T,k,\pi^{\operatorname{OPT}}_{T,k},\gamma,\omega,\epsilon,\eta)$
in Section I.1 reflects the updates in terms of the precomputations. Section
I.1 also compiles the changes made to the simulations across various stages
and presents a summary.

###### Lemma 0.

A single execution of
$\text{TruncatedSimulate}(\alpha,\beta,\lambda,T,k,\pi^{\operatorname{OPT}}_{T,k},\gamma,\omega,\epsilon,\eta)$
terminates in time $O(Tkn+\tfrac{T^{2}}{\epsilon\,\eta})$.

###  4.5. Locating the Optimal Expected Reward and the Optimal Adversarial
Strategy

Remember that the end goal of the simulations is to compute the optimal reward
for an adversary playing $\operatorname{CSSPA}(\alpha,\beta)$. We denote the
optimal $k$-scored adversarial strategy in
$\operatorname{LinearCSSPA}(\alpha,\beta,\lambda,T)$ by
$\pi^{\operatorname{OPT}}_{T,k}(\lambda)$ and in
$\operatorname{CSSPA}(\alpha,\beta)$ that terminates in $T$ rounds by
$\pi^{\operatorname{OPT}}_{T,k}$. Let
$\operatorname{Rew}^{\operatorname{Lin}}_{\lambda}(\pi)$ be the expected
reward from playing $\pi$ in
$\operatorname{LinearCSSPA}(\alpha,\beta,\lambda,T)$. Remember that
$\operatorname{Rew}(T)$ is the expected reward from playing $\pi$ in
$\operatorname{CSSPA}(\alpha,\beta)$. By Theorem 3,
$\operatorname{Rew}^{\operatorname{Lin}}_{\lambda}(\pi^{\operatorname{OPT}}_{T,k})\geq
0$ iff $\lambda\leq\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,k})$ with
equality holding precisely when
$\lambda=\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,k})$. To estimate
$\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,k})$, we run
$\text{TruncatedSimulate}(\alpha,\beta,\lambda,T,k,\pi^{\operatorname{OPT}}_{T,k}(\lambda),\gamma,\omega,\epsilon,\eta)$
and binary search over $\lambda$ until the expected reward output by the
simulation is approximately zero. More precisely, we search for $\lambda$ such
that the expected values of the upper bound
$\overline{\operatorname{D}}_{T,k}(\lambda)$ and the lower bound
$\underline{\operatorname{D}}_{T,k}(\lambda)$ are slightly larger and slightly
smaller than zero. However, the binary search could potentially output any
$\lambda$ such that
$\operatorname{Rew}^{\operatorname{Lin}}_{\lambda}(\pi^{\operatorname{OPT}}_{T,k}(\lambda))\approx
0$ even if $\lambda$ is far off from
$\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,k})$. Such an error will
become all the more likely given that the simulations only produce an interval
$\big{[}\mathbb{E}_{s\sim\overline{\operatorname{D}}_{T,k}(\lambda_{1})}[s],\mathbb{E}_{s\sim\underline{\operatorname{D}}_{T,k}(\lambda_{1})}[s]\big{]}$
such that
$\operatorname{Rew}^{\operatorname{Lin}}_{\lambda}(\pi^{\operatorname{OPT}}_{T,k}(\lambda))$
lies in this interval, instead of exactly computing the rewards. The following
theorem rules out such scenarios.

###### Theorem 8.

Let
$\text{TruncatedSimulate}(\alpha,\beta,\lambda_{1},T,k,\pi^{\operatorname{OPT}}_{T,k}(\lambda_{1}),\gamma,\omega,\epsilon,\eta)$
output the upper bound and lower bound distributions
$\overline{\operatorname{D}}_{T,k}(\lambda_{1})$ and
$\underline{\operatorname{D}}_{T,k}(\lambda_{1})$ respectively, such that
$\mathbb{E}_{s\sim\overline{\operatorname{D}}_{T,k}(\lambda_{1})}[s]-\mathbb{E}_{s\sim\underline{\operatorname{D}}_{T,k}(\lambda_{1})}[s]\leq\delta$.
Suppose for some
$r\in\Big{[}\mathbb{E}_{s\sim\overline{\operatorname{D}}_{T,k}(\lambda_{1})}[s],\mathbb{E}_{s\sim\underline{\operatorname{D}}_{T,k}(\lambda_{1})}[s]\Big{]}$,
$|r-\operatorname{Rew}^{\operatorname{Lin}}_{\lambda_{2}}(\pi^{\operatorname{OPT}}_{T,k}(\lambda_{2}))|\leq\zeta\text{.}$
Then, $|\lambda_{1}-\lambda_{2}|\leq\zeta+\delta$ with probability at least
$1-\Big{(}2\,T\,\gamma+T\,\tfrac{e^{-\omega
n}}{\omega}\,\sqrt{\tfrac{\ln\gamma^{-1}}{2n}}\Big{)}$.

We defer the proof to Section H.1. By locating the optimal adversarial reward
(approximately), we also uncover a very succinct description of the
adversary’s (near) optimal strategy, which we describe in Section H.2.

##  5\. Simulation Results

Below, we summarize the results from our simulations. In Figure 1, we compare
the bounds from previous works against our results. We see that our bounds on
the adversarial rewards of both the omniscient adversary (blue) and the actual
adversary in $\operatorname{CSSPA}(\alpha,\beta)$ (green) is significantly
tighter than the bound for the omniscient adversary from Ferreira et al.,
(2022) (orange). The bounds plotted in Figure 1 is empirical, and are not
provably correct, since we did not inflate samples when constructing the
reward distributions. However, they are fairly representative of the scale of
the marginal rewards the adversary achieves from being strategic. For
instance, even with an extremely large stake of $0.2$, we get the marginal
rewards to be in the range $[0.0068,0.0078]$ (for a simulation with deflated
and inflated sampling), which is not considerable. Further, observe that the
rewards from the $1$-lookahead strategy (red), which is much more tractable
than the optimal strategy to describe and compute, is already close to the
optimal adversarial reward. In Figure 2, we plot the marginal rewards of the
adversary against its stake for various values of $\beta$. Observe that the
network connectivity $\beta$ plays an important role in the rewards and the
adversary has significant gains for larger values of $\beta$. For instance, at
$\alpha=0.2$ the marginal utility when $\beta=1$ is at least $0.0068$ (from a
simulation constructed from deflated sampling) and at most $0.0021$ (from a
simulation constructed from inflated sampling) when $\beta=0$. Finally, Figure
3 compares the adversary’s marginal rewards as a function of $\beta$ for a
stake $\alpha=0.25$, once again, highlighting the role of connectivity in
strategic manipulation in blockchain protocols.

$1\cdot 10^{-2}$$5\cdot
10^{-2}$$0.1$$0.15$$0.2$$0.25$$0$$0.05$$0.1$$0.15$$0.2$$0.25$$0.3$$0.35$$0.4$Stake
$\alpha$Marginal reward $\operatorname{Rew}(\pi^{\operatorname{OPT}})-\alpha$
Figure 1. Marginal reward vs adversarial stake. Legend: orange–upper bound
from Ferreira et al.,, 2022; blue– tight upper bound for the omniscient
adversary; green– un-inflated simulated upper bound for $\beta=1$; red– reward
from the $1$-lookahead strategy in Ferreira et al.,, 2022.
$0$$0.05$$0.1$$0.15$$0.2$$0.25$$0.3$$0$$0.002$$0.004$$0.006$$0.008$$0.01$$0.012$$0.014$$0.016$$0.018$$0.02$Stake
$\alpha$Marginal reward $\operatorname{Rew}(\pi^{\operatorname{OPT}})-\alpha$
Figure 2. Marginal reward vs adversarial stake. Legend: brown– un-inflated
simulated upper bounds for $\beta=1$; red– un-inflated simulated upper bounds
for $\beta=0.5$; blue– un-inflated simulated upper bounds for $\beta=0$.
$0$$0.2$$0.4$$0.6$$0.8$$1$0.0020.0040.0060.0080.010.0120.014Connectivity
parameter $\beta$Marginal reward
$\operatorname{Rew}(\pi^{\operatorname{OPT}})-\alpha$ Figure 3. Marginal
reward vs network connectivity. Legend: orange– un-inflated simulated upper
bound for $\alpha=0.25$, blue– un-deflated simulated lower bound for
$\alpha=0.25$

## References

  * Babaioff et al., (2012) Babaioff, M., Dobzinski, S., Oren, S., and Zohar, A. (2012).  On bitcoin and red balloons.  In Faltings, B., Leyton-Brown, K., and Ipeirotis, P., editors, Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012, Valencia, Spain, June 4-8, 2012, pages 56–73. ACM.
  * Bahrani and Weinberg, (2023) Bahrani, M. and Weinberg, S. M. (2023).  Undetectable selfish mining.  CoRR, abs/2309.06847.
  * Brown-Cohen et al., (2019) Brown-Cohen, J., Narayanan, A., Psomas, A., and Weinberg, S. M. (2019).  Formal barriers to longest-chain proof-of-stake protocols.  In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019., pages 459–473.
  * Cai et al., (2024) Cai, L., Liu, J., Weinberg, S. M., and Zhao, C. (2024).  Profitable manipulations of cryptographic self-sortition are statistically detectable.  In In submission to the 25th ACM Conference on Economics and Computation.
  * Carlsten et al., (2016) Carlsten, M., Kalodner, H. A., Weinberg, S. M., and Narayanan, A. (2016).  On the instability of bitcoin without the block reward.  In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016, pages 154–167.
  * Chen and Micali, (2019) Chen, J. and Micali, S. (2019).  Algorand: A secure and efficient distributed ledger.  Theor. Comput. Sci., 777:155–183.
  * Daian et al., (2016) Daian, P., Pass, R., and Shi, E. (2016).  Snow white: Provably secure proofs of stake.  IACR Cryptology ePrint Archive, 2016:919.
  * Dvoretzky et al., (1956) Dvoretzky, A., Kiefer, J., and Wolfowitz, J. (1956).  Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator.  The Annals of Mathematical Statistics, pages 642–669.
  * Eyal and Sirer, (2014) Eyal, I. and Sirer, E. G. (2014).  Majority is not enough: Bitcoin mining is vulnerable.  In Financial Cryptography and Data Security, pages 436–454. Springer.
  * Ferreira et al., (2022) Ferreira, M. V. X., Hahn, Y. L. S., Weinberg, S. M., and Yu, C. (2022).  Optimal strategic mining against cryptographic self-selection in proof-of-stake.  In Pennock, D. M., Segal, I., and Seuken, S., editors, EC ’22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022, pages 89–114. ACM.
  * Ferreira and Weinberg, (2021) Ferreira, M. V. X. and Weinberg, S. M. (2021).  Proof-of-stake mining games with perfect randomness.  In Biró, P., Chawla, S., and Echenique, F., editors, EC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021, pages 433–453. ACM.
  * Ferreira et al., (2019) Ferreira, M. X., Weinberg, S. M., Huang, D. Y., Feamster, N., and Chattopadhyay, T. (2019).  Selling a single item with negative externalities.  In The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019, pages 196–206.
  * Fiat et al., (2019) Fiat, A., Karlin, A., Koutsoupias, E., and Papadimitriou, C. H. (2019).  Energy equilibria in proof-of-work mining.  In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019., pages 489–502.
  * Gilad et al., (2017) Gilad, Y., Hemo, R., Micali, S., Vlachos, G., and Zeldovich, N. (2017).  Algorand: Scaling byzantine agreements for cryptocurrencies.  In Proceedings of the 26th Symposium on Operating Systems Principles, Shanghai, China, October 28-31, 2017, pages 51–68. ACM.
  * Goren and Spiegelman, (2019) Goren, G. and Spiegelman, A. (2019).  Mind the mining.  In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019., pages 475–487.
  * Kiayias et al., (2016) Kiayias, A., Koutsoupias, E., Kyropoulou, M., and Tselekounis, Y. (2016).  Blockchain mining games.  In Proceedings of the 2016 ACM Conference on Economics and Computation, EC ’16, Maastricht, The Netherlands, July 24-28, 2016, pages 365–382.
  * Kiayias et al., (2017) Kiayias, A., Russell, A., David, B., and Oliynykov, R. (2017).  Ouroboros: A provably secure proof-of-stake blockchain protocol.  In Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part I, pages 357–388.
  * Massart, (1990) Massart, P. (1990).  The tight constant in the dvoretzky-kiefer-wolfowitz inequality.  The annals of Probability, pages 1269–1283.
  * McDiarmid et al., (1989) McDiarmid, C. et al. (1989).  On the method of bounded differences.  Surveys in combinatorics, 141(1):148–188.
  * Nakamoto, (2008) Nakamoto, S. (2008).  Bitcoin: A peer-to-peer electronic cash system.
  * Sapirshtein et al., (2016) Sapirshtein, A., Sompolinsky, Y., and Zohar, A. (2016).  Optimal selfish mining strategies in bitcoin.  In Financial Cryptography and Data Security - 20th International Conference, FC 2016, Christ Church, Barbados, February 22-26, 2016, Revised Selected Papers, pages 515–532.
  * Tsabary and Eyal, (2018) Tsabary, I. and Eyal, I. (2018).  The gap game.  In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, October 15-19, 2018, pages 713–728.
  * Yaish et al., (2023) Yaish, A., Stern, G., and Zohar, A. (2023).  Uncle maker: (time)stamping out the competition in ethereum.  In Meng, W., Jensen, C. D., Cremers, C., and Kirda, E., editors, Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS 2023, Copenhagen, Denmark, November 26-30, 2023, pages 135–149. ACM.
  * Yaish et al., (2022) Yaish, A., Tochner, S., and Zohar, A. (2022).  Blockchain stretching & squeezing: Manipulating time for your best interest.  In Pennock, D. M., Segal, I., and Seuken, S., editors, EC ’22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022, pages 65–88. ACM.
  * Zur et al., (2020) Zur, R. B., Eyal, I., and Tamar, A. (2020).  Efficient mdp analysis for selfish-mining in blockchains.  In Proceedings of the 2nd ACM Conference on Advances in Financial Technologies, pages 113–131.

##  Appendix A Characterizing Balanced Scoring Functions

We begin the discussion on balanced scoring functions by proving Theorem 4.

###### Proof of Theorem 4.

Let $\alpha=\sum_{i=1}^{n}\alpha_{i}$, $U$ be the random variable denoting
$S(X,\alpha)$. Let $V_{1}^{i},\dots,V_{\Gamma}^{i}$ be $\Gamma$ independent
copies of $S(X_{i},\alpha_{i})$ and $V_{j}$ denote the random variable
$\min\\{V_{j}^{1},\dots,V_{j}^{n}\\}$.

From the definition of a balanced scoring function,

$Pr\Big{(}\min_{1\leq j\leq\Gamma,1\leq i\leq
n}\\{S(X,\alpha),S(X_{i}^{j},\alpha_{i})\\}=S(X,\alpha)\Big{)}=\frac{\alpha}{(\Gamma+1)\,\alpha}=\frac{1}{(\Gamma+1)}$

Here, we use $X_{i}^{j}$ to denote the random variable copy of $X_{i}$
corresponding to $V_{j}$ (i.e, the copy that determines $V_{j}^{i}$).
Rephrasing,

$\begin{split}\frac{1}{\Gamma+1}&=Pr\Big{(}U\leq
V_{j}^{1},\dots,V_{j}^{n}\text{ for all }1\leq j\leq\Gamma\Big{)}\\\
&=Pr\Big{(}U\leq V_{1},\dots,V_{\Gamma}\Big{)}\\\ &=Pr\Big{(}U\leq
V_{1},\dots,V_{\Gamma}\Big{)}\end{split}$

We move to the quantile space of the i.i.d. variables
$V_{1},\dots,V_{\Gamma}$. Let $F$ be the CDF of $V_{i}$ and let the quantile
$q_{i}$ be the random variable given by $V_{i}=F^{-1}(1-q_{i})$. Thus, the
random variables $q_{1},\dots,q_{n}$ satisfy $q_{i}=1-F(V_{i})$. Note that
$q_{i}\sim U[0,1]$. Let $q_{0}$ be the random variable denoting $1-F(U)$,
distributed according to the distribution $G$ with a density function $g$.
Since $F(\cdot)$ is an increasing function, $1-F(\cdot)$ is decreasing, and,

$\begin{split}\frac{1}{\Gamma+1}&=Pr(U\leq V_{1},\dots,V_{n})\\\
&=Pr(q_{0}\geq q_{1},\dots,q_{n})\\\
&=\int_{0}^{1}\Big{(}\Pi_{i=1}^{\Gamma}Pr(q_{i}\leq
q_{0})\Big{)}g(q_{0})\,dq_{0}\\\
&=\int_{0}^{1}q_{0}^{\Gamma}g(q_{0})\,dq_{0}\\\ &=\mathbb{E}_{q_{0}\sim
G}[q_{0}^{\Gamma}]\end{split}$

The third equality follows since $q_{i}\sim U[0,1]$ for $1\leq i\leq\Gamma$.
From the above, we know that the $\Gamma\textsuperscript{th}$ moment of the
distribution $G$ equals $\frac{1}{\Gamma+1}$ which is the
$\Gamma\textsuperscript{th}$ moment of $U[0,1]$. $U[0,1]$ has a well-defined
moment generating function and thus, any distribution with the same moments as
the uniform distribution is the uniform distribution.

Thus, $q_{0}=1-F(U)\sim U[0,1]$, the same as $1-F(V_{i})$ and thus, $U$ is
distributed identically to $V_{1},\dots,V_{\Gamma}$. In other words,
$S(X,\sum_{i=1}^{n}\alpha_{i})\text{ and }\min_{1\leq i\leq
n}\\{S(X_{i},\alpha_{i})\\}$ are identically distributed. ∎

We characterize all “different” balanced scoring rules in Theorem 1.

###### Theorem 1.

Let $S$ be a balanced scoring function. Then, the distribution of $S(X,1)$ for
$X\sim U[0,1]$ uniquely determines the distribution of $S(X,\alpha)$ for all
$\alpha\geq 0$. In particular, $Pr(S(X,\alpha)\geq s)=Pr(S(X,1)\geq
s)^{\alpha}$.

To prove Theorem 1, we require the following intuitive corollary of Theorem 4:
for a user with stake $\alpha$, we expect the user’s probability of getting a
large score (and, thus not get elected) to decrease with an increase in the
stake.

###### Corollary 0.

Let $S$ be a balanced scoring function. Then, $Pr(S(X,\alpha)\geq s)$ is
monotonically non-increasing in $\alpha$.

###### Proof.

For $\alpha,\epsilon\geq 0$,

$\begin{split}Pr(S(X,\alpha+\epsilon)\geq
s)&=Pr\Big{(}\min\\{S(X_{1},\alpha),S(X_{2},\epsilon)\\}\geq s\Big{)}\\\ &\leq
Pr(S(X,\alpha)\geq s)\end{split}$

∎

The following lemma characterizes the set of all ”different” balanced scoring
functions.

###### Proof of Theorem 1.

We show the claim in three steps.

  1. (1)

$\alpha\in\mathbb{N}\cup\\{0\\}$. Then, by Theorem 4,

$Pr(S(X,\alpha)\geq s)=Pr\big{(}\min_{1\leq i\leq\alpha}\\{S(X_{i},1)\\}\geq
s\big{)}=Pr(S(X,1)\geq s)^{\alpha}$

  2. (2)

$\alpha\in\mathbb{Q}_{\geq 0}$. Let $\alpha=\tfrac{p}{q}$ for natural numbers
$p$ and $q(\neq 0)$. Then, by Theorem 4,

$Pr(S(X,p)\geq s)=Pr\big{(}\min_{1\leq i\leq q}\\{S(X_{i},\frac{p}{q})\\}\geq
s\big{)}=Pr(S(X,\frac{p}{q})\geq s)^{q}$

From the previous case, $Pr(S(X,p)\geq s)=Pr(S(X,1)\geq s)^{p}$ and thus,
$Pr(S(X,\frac{p}{q})\geq s)=Pr(S(X,1)\geq s)^{\frac{p}{q}}$.

  3. (3)

$\alpha\in\mathbb{R}_{\geq 0}$. Let
$\big{(}\alpha_{i}\big{)}_{i\in\mathbb{N}}$ be a sequence of rational numbers
converging to $\alpha$. Then,

$\lim_{i\xrightarrow{}\infty}Pr(S(X,\alpha_{i})\geq
s)=\lim_{i\xrightarrow{}\infty}Pr(S(X,1)\geq s)^{\alpha_{i}}=Pr(S(X,1)\geq
1)^{\alpha}$

If we show that $Pr(S(X,\cdot)\geq s)$ is continuous, then we can conclude
$Pr(S(X,\alpha)\geq s)=Pr(S(X,1)\geq s)^{\alpha}$. By Corollary 2,
$Pr(S(X,a))$ is monotone non-increasing in $a$. Thus, for
$\alpha_{1},\alpha_{2}\in\mathbb{Q}$ and $\alpha\in[\alpha_{1},\alpha_{2}]$,

$Pr(S(X,1)\geq s)^{\alpha_{1}}=Pr(S(X,\alpha_{1})\geq s)\geq
Pr(S(X,\alpha)\geq s)\geq Pr(S(X,\alpha_{2})\geq s)=Pr(S(X,1)\geq
s)^{\alpha_{2}}$

For the sequences of rationals $\big{(}\alpha_{1}^{i}\big{)}_{i\in\mathbb{N}}$
such that $\alpha_{1}^{i}<\alpha$ and
$\big{(}\alpha_{2}^{i}\big{)}_{i\in\mathbb{N}}$ satisfying
$\alpha_{2}^{i}>\alpha$, both converging to $\alpha$

$Pr(S(X,1)\geq s)^{\alpha_{1}^{i}}\geq Pr(S(X,\alpha)\geq s)\geq Pr(S(X,1)\geq
s)^{\alpha_{2}^{i}}$

As $i\xrightarrow{}\infty$, both $Pr(S(X,1)\geq s)^{\alpha_{1}^{i}}$ and
$Pr(S(X,1)\geq s)^{\alpha_{2}^{i}}$ converge to $Pr(S(X,1)\geq s)^{\alpha}$.
Thus, $Pr(S(X,\alpha)\geq s)=Pr(S(X,1)\geq s)^{\alpha}$.

∎

Ferreira et al., (2022) conjectured that all balanced scoring functions
$S(X,\alpha)$ are continuous in $\alpha$. Even though $Pr(S(X,\alpha)\geq s)$
is continuous in $\alpha$ (Theorem 1), $S(X,\alpha)$ need not be continuous in
$\alpha$.

###### Example 0.

Consider

$S(X,\alpha)=\begin{cases}\tfrac{-\ln X}{\alpha}&\text{if }\tfrac{-\ln
X}{\alpha}\leq 3\\\ \tfrac{-\ln X}{\alpha}+1&\text{if }\tfrac{-\ln
X}{\alpha}>3\end{cases}$

It can be easily verified that $S(X,\alpha)$ is indeed a balanced scoring
function. However, $S(X,\alpha)$ is not continuous in $\alpha$.

##  Appendix B A More General $\operatorname{CSSPA}(\alpha,\beta)$

In this section, we review the general version of
$\operatorname{CSSPA}(\alpha,\beta)$ defined in Ferreira et al., (2022).

###### Definition 0 ($\operatorname{CSSPA}(\alpha,\vec{\alpha},\beta)$).

In $\operatorname{CSSPA}(\alpha,\vec{\alpha},\beta)$, the network consists of
the adversary with stake $\alpha$ and honest players with stakes given by
$\vec{\alpha}$. Prior to round $1$, the adversary learns the values of
$\alpha,\vec{\alpha}$ and $\beta$ and that the network apart from the
adversary is honest. For a choice $n\geq 1$, the adversary distributes its
stake arbitrarily over a set $A$ of $n$ wallets. The adversary makes the
following decisions in round $t$:

  1. (1)

The adversary learns the seed $Q_{t}$ of round $t$.

  2. (2)

The adversary computes the credentials $\operatorname{\textsc{Cred}}^{i}_{t}$
for all wallets $i\in A$. The adversary chooses a subset of honest players $B$
with total stake at most $\beta\,(1-\alpha)$ and learns the credentials
$\operatorname{\textsc{Cred}}^{i}_{t}$ for all $i\in B$. For all wallets $i\in
C$, the adversary knows that $\operatorname{\textsc{Cred}}^{i}_{t}$ will be
drawn independently from $\operatorname{exp}(\alpha_{i})$.

  3. (3)

For any $r\geq 0$ and $(i_{t},i_{t+1},\dots,i_{t+r})\in\big{(}A\cup
B\big{)}\times A^{r}$, the adversary precomputes the credentials
$\operatorname{\textsc{Cred}}^{i_{t+r^{\prime}}}_{t+r^{\prime}}$ for $1\leq
r^{\prime}\leq r$ assuming $i_{t+\hat{r}}$ is elected to lead in round
$t+\hat{r}$ for all $0\leq\hat{r}<r^{\prime}$.

  4. (4)

The adversary either remains silent or broadcasts the credentials of some
subset $A_{t}$ of the adversarial wallets $A$.

From the above definition of
$\operatorname{CSSPA}(\alpha,\vec{\alpha},\beta)$, Ferreira et al., (2022)
make a series of refinements that lead to $\operatorname{CSSPA}(\alpha,\beta)$
without compromising on the adversarial reward.

###### Lemma 0 (Observation 3.2 from Ferreira et al.,, 2022).

For any $\alpha,\vec{\alpha},\beta$, define $\vec{\alpha}^{\prime}$ to have
two honest players with stakes $\alpha_{1}=\beta\,(1-\alpha)$ and
$\alpha_{2}=(1-\beta)\,(1-\alpha)$ respectively. For any strategy $\pi$ in
$\operatorname{CSSPA}(\alpha,\vec{\alpha},\beta)$, there exists a strategy
$\pi^{\prime}$ in $\operatorname{CSSPA}(\alpha,(\alpha_{1},\alpha_{2}),\beta)$
such that
$\operatorname{Rew}(\alpha,(\alpha_{1},\alpha_{2}),\beta;\pi^{\prime})=\operatorname{Rew}(\alpha,\vec{\alpha},\beta;\pi)$.

###### Lemma 0 (Lemma 3.1 from Ferreira et al.,, 2022).

Let $\pi$ be a strategy in
$\operatorname{CSSPA}(\alpha,(\alpha_{1},\alpha_{2}),\beta)$ where the
adversary splits its stake into $n$ wallets. Then there exists a strategy
$\pi^{\prime}$ such that the adversary divides its stake into $2n$ wallets and
$\operatorname{Rew}(\pi^{\prime})\geq\operatorname{Rew}(\pi)$.

###### Lemma 0 (Observation 3.1 from Ferreira et al.,, 2022).

For any strategy $\pi$ in
$\operatorname{CSSPA}(\alpha,(\alpha_{1},\alpha_{2}),\beta)$ that distributes
the adversarial stake across $n$ wallets, there exists an adversarial strategy
$\pi^{\prime}$ that also distributes the stake across the same number of
wallets, broadcasts the credential of at most one wallet in $A$ and results in
exactly the same leaders as $\pi$, thereby getting the same reward as $\pi$.

The following conclusion is straightforward from the above lemmas.

###### Theorem 5.

The optimal adversarial reward in
$\operatorname{CSSPA}(\alpha,\vec{\alpha},\beta)$ is at most the optimal
adversarial reward in $\operatorname{CSSPA}(\alpha,\beta)$ for all
$\alpha,\vec{\alpha}$ and $\beta$.

##  Appendix C The Omniscient Adversary

Ferreira et al., (2022) abstract the game faced by an omniscient adversary
into a Galton-Watson branching process. The branching process maintains a tree
with nodes corresponding to possible choices the adversary can make across
rounds. A node $\operatorname{\textsc{Cred}}^{i_{t}}_{t}$ in level $t$ of the
tree corresponds to a potential winner $i_{t}$ in round $t$ for some sequence
of leaders $i_{1},i_{2},\dots,i_{t-1}$ with credentials
$\operatorname{\textsc{Cred}}^{i_{1}}_{1},\operatorname{\textsc{Cred}}^{i_{2}}_{2},\dots,\operatorname{\textsc{Cred}}^{i_{t-1}}_{t-1}$
in the first $t-1$ rounds. A node
$\operatorname{\textsc{Cred}}^{i_{t+1}}_{t+1}$ in level $t+1$ is a child of
$\operatorname{\textsc{Cred}}^{i_{t}}_{t}$ if $i_{t+1}$ belongs to the set of
potential winners $W_{t+1}(Q_{t+1})$ assuming $i_{t}$ gets elected in round
$t$ and $Q_{t+1}=\operatorname{\textsc{Cred}}^{i_{t}}_{t}$. By Lemma 8, the
probability that a node will have exactly $i^{*}+1$ children equals
$\alpha^{i^{*}}\,(1-\alpha)$. If node
$\operatorname{\textsc{Cred}}^{i_{t}}_{t}$ at level $t$ has exactly one child
$\operatorname{\textsc{Cred}}^{i_{t+1}}_{t+1}$ in the choice tree, this
corresponds to the adversarial potential winners $\hat{W}_{t+1}(Q_{t+1})$
being empty for $Q_{t+1}=\operatorname{\textsc{Cred}}^{i_{t}}_{t}$, which
signifies a stopping time. The tree stops branching at
$\operatorname{\textsc{Cred}}^{i_{t}}_{t}$.

The height $\tau$ of the choice tree corresponds to the sequence of leaders
$i_{1},\dots,i_{\tau}$ that causes the maximum delay in the first stopping
time $\tau$. We show upper bounds on the expected height $\tau$ of the choice
tree.

###### Definition 0 (Omniscient Choice Tree).

The omniscient choice tree $\Gamma$ is built by the following stochastic
process:

  1. (1)

Level $0$ contains the root $q_{0}$ of the tree $\Gamma$.

  2. (2)

For each node $q$ at level $t\geq 0$, $q$ has $i^{*}+1$ children with
probability $\alpha^{i^{*}}\,(1-\alpha)$ for all $i^{*}\geq 0$.

  3. (3)

A node stops branching if it is the only child of its parent.

  4. (4)

$\Gamma$ becomes extinct at height $\tau$ when all nodes at level $\tau$ have
stopped branching.

###  C.1. Extinction of the Choice Tree

Let $E_{t}$ be the event that the choice tree does not terminate on or before
round $t$, i.e, $\tau>t$, and $\overline{E}_{t}$ be its complement. Let
$e_{t}$ and $\overline{e}_{t}=1-e_{t}$ be the probabilities of $E_{t}$ and
$\overline{E}_{t}$ respectively. Indeed $e_{0}=1$ and $\overline{e}_{0}=0$. We
compute a recursive relation between $e_{t-1}$ and $e_{t}$.

###### Lemma 0.

The probabilities $\big{(}e_{t}\big{)}_{t\in\mathbb{N}\cup\\{0\\}}$ satisfy
$e_{0}=1$ and

$e_{t}=\frac{\alpha(2-\alpha)e_{t-1}-\alpha(1-\alpha)e_{t-1}^{2}}{(1-\alpha)+\alpha
e_{t-1}}$

for all $t\geq 1$.

###### Proof.

We establish a recursion on
$\big{(}\overline{e}_{t}\big{)}_{t\in\mathbb{N}\cup\\{0\\}}$ instead. Let
$W_{q}$ be a random variable denoting the number of children of a node
$q\in\Gamma$ and $h_{q}$ be the height of the sub-tree below $q$.

$\overline{E}_{t}$ is the event that the choice tree goes extinct before or as
soon as reaching a height $t$ from the root $q_{0}$. This occurs when either
$|W_{q_{0}}|=1$ and the game ends in the first round or every child $q_{j}$ of
$q_{0}$ satisfies $h_{q_{j}}\leq t-1$ for $1\leq j\leq|W_{q_{0}}|$. Hence,

(1)
$\overline{e}_{t}=Pr(|W_{q_{0}}|=1)+\sum_{i^{*}=1}^{\infty}Pr(|W_{q_{0}}|=i^{*}+1)\times
Pr(\bigcup_{1\leq j\leq i^{*}+1}(h_{q_{j}}\leq t-1)||W_{q_{0}}|=i^{*}+1)$

The evolution of the choice tree under distinct nodes are independent and
identically distributed random processes. Therefore,

$\begin{split}Pr(\bigcup_{1\leq j\leq i^{*}+1}(h_{q_{j}}\leq
t-1)||W_{q_{0}}|=i^{*}+1)&=Pr(h_{q}\leq t-1)^{i^{*}+1}\\\
&=\overline{e}_{t-1}^{i^{*}+1}\end{split}$

The probability that $|W_{q_{0}}|$ equals $i^{*}+1$ equals
$\alpha^{i^{*}}\,(1-\alpha)$ (by Definition 1).

Plugging all of the above into Equation 1,

$\begin{split}\overline{e}_{t}&=(1-\alpha)+\sum_{i^{*}=1}^{\infty}\alpha^{i^{*}}\,(1-\alpha)\times\overline{e}_{t-1}^{i^{*}+1}\\\
&=(1-\alpha)+\frac{\alpha(1-\alpha)\overline{e}_{t-1}^{2}}{1-\alpha\overline{e}_{t-1}}\end{split}$

Substituting $\overline{e}_{t}=1-e_{t}$ and $\overline{e}_{t-1}=1-e_{t-1}$
completes the proof. ∎

Lemma 9 is a direct consequence of Lemma 2.

###### Proof of lemma 9.

We know $e_{0}=1$. $e_{1}$ and $e_{2}$ can be computed recursively to be equal
to $\alpha$ and
$\alpha^{2}\cdot\tfrac{2-2\alpha+\alpha^{2}}{1-\alpha+\alpha^{2}}$
respectively.

We induct on $t$ for $t\geq 3$. Let
$e_{t}\leq\alpha^{2}\cdot\tfrac{2-2\alpha+\alpha^{2}}{1-\alpha+\alpha^{2}}\cdot\big{(}\alpha\cdot\tfrac{2-\alpha}{1-\alpha}\big{)}^{t-2}$.
Then,

$\begin{split}e_{t+1}&=\frac{\alpha(2-\alpha)e_{t}-\alpha(1-\alpha)e_{t}^{2}}{(1-\alpha)+\alpha
e_{t}}\\\ &\leq\big{(}\alpha\cdot\tfrac{2-\alpha}{1-\alpha}\big{)}e_{t}\\\
&\leq\big{(}\alpha\cdot\tfrac{2-\alpha}{1-\alpha}\big{)}\times\alpha^{2}\cdot\tfrac{2-2\alpha+\alpha^{2}}{1-\alpha+\alpha^{2}}\cdot\big{(}\alpha\cdot\tfrac{2-\alpha}{1-\alpha}\big{)}^{t-2}\\\
&=\alpha^{2}\cdot\tfrac{2-2\alpha+\alpha^{2}}{1-\alpha+\alpha^{2}}\cdot\big{(}\alpha\cdot\tfrac{2-\alpha}{1-\alpha}\big{)}^{t-1}\end{split}$

∎

###  C.2. Proof of Theorem 7

Let $\pi^{\operatorname{OMNI}}$ denote the optimal strategy for the omniscient
adversary that broadcasts the credentials of the wallets in the longest path
in $\Gamma$ starting at the root $q_{0}$.

###### Lemma 0.

There exists a constant $\kappa\approx 0.38$ such that expected first stopping
time $\mathbb{E}[\tau]$ of $\pi^{\operatorname{OMNI}}$ is unbounded for all
$\alpha>\kappa$. The optimal reward
$\operatorname{Rew}^{\operatorname{OMNI}}(\pi^{\operatorname{OMNI}})$ for the
omniscient adversary equals $1$.

###### Proof.

Denote the smaller root of $1-3x+x^{2}$ by $\kappa\approx 0.38$. Choose an
arbitrary
$\delta\in\big{(}0,-\tfrac{1-3\alpha+\alpha^{2}}{\alpha\,(2-\alpha)}\big{)}$.
Since the larger root of $1-3x+x^{2}$ is greater than $1$, the interval is
non-degenerate for all $\kappa\leq\alpha\leq 1$.

Suppose we show $e_{t}\geq\delta$ for all $t\geq 0$. Then,

$\mathbb{E}[\tau]=\sum_{t=0}^{\infty}e_{t}\geq\sum_{t=0}^{\infty}\delta$

which is unbounded, as needed.

We will prove $e_{t}\geq\delta$ by induction on $t$. Indeed,
$e_{0}=1\geq\delta$. Suppose that $e_{t-1}\geq\delta$.

$\begin{split}e_{t}&=\frac{\alpha(2-\alpha)e_{t-1}-\alpha(1-\alpha)e_{t-1}^{2}}{(1-\alpha)+\alpha
e_{t-1}}\\\
&\geq\frac{\alpha(2-\alpha)\delta-\alpha(1-\alpha)\delta^{2}}{(1-\alpha)+\alpha\delta}\\\
&=\delta\cdot\Big{(}\frac{\alpha(2-\alpha)-\alpha(1-\alpha)\delta}{(1-\alpha)+\alpha\delta}\Big{)}\\\
&\geq\delta\end{split}$

The inequality in the second line holds since $e_{t}$ is monotonously
increasing in $e_{t-1}$. For the choice of $\delta$,
$\Big{(}\frac{\alpha(2-\alpha)-\alpha(1-\alpha)\delta}{(1-\alpha)+\alpha\delta}\Big{)}\geq
1$ (follows by simple rearrangement) and the last inequality follows.

Since $\mathbb{E}[\tau]$ is unbounded,

$\operatorname{Rew}^{\operatorname{OMNI}}(\pi^{\operatorname{OMNI}})=1-\frac{1}{\mathbb{E}[\tau]}=1$

∎

###### Lemma 0.

Let $\kappa\approx 0.38$ be the smaller root of $1-3x+x^{2}$. For a stake
$\alpha\leq\kappa$, the expected first stopping time $\mathbb{E}[\tau]$ of the
optimal adversarial strategy $\pi^{\operatorname{OMNI}}$ is at most
$\tfrac{1-3\alpha+3\alpha^{2}-3\alpha^{3}}{(1-3\alpha+\alpha^{2})\,(1-\alpha+\alpha^{2})}$.
The optimal adversarial reward
$\operatorname{Rew}^{\operatorname{OMNI}}(\pi^{\operatorname{OMNI}})$ is at
most
$\alpha\cdot\big{(}\tfrac{1-2\alpha+\alpha^{2}-\alpha^{3}}{1-3\alpha+3\alpha^{2}-3\alpha^{3}}\big{)}$.

###### Proof.

From Lemma 9, $e_{0}=1$, $e_{1}=\alpha$ and
$e_{t}\leq\alpha^{2}\cdot\tfrac{2-2\alpha+\alpha^{2}}{1-\alpha+\alpha^{2}}\cdot\big{(}\alpha\cdot\tfrac{2-\alpha}{1-\alpha}\big{)}^{t-2}$.

$\begin{split}\mathbb{E}[\tau]&=\sum_{t=0}^{\infty}e_{t}\\\ &\leq
1+\alpha+\sum_{t=2}^{\infty}\alpha^{2}\cdot\tfrac{2-2\alpha+\alpha^{2}}{1-\alpha+\alpha^{2}}\cdot\big{(}\alpha\cdot\tfrac{2-\alpha}{1-\alpha}\big{)}^{t-2}\\\
&=\tfrac{1-3\alpha+3\alpha^{2}-3\alpha^{3}}{(1-3\alpha+\alpha^{2})\,(1-\alpha+\alpha^{2})}\end{split}$

Further,

$\operatorname{Rew}^{\operatorname{OMNI}}(\pi^{\operatorname{OMNI}})=1-\frac{1}{\mathbb{E}[\tau]}\leq\alpha\cdot\big{(}\tfrac{1-2\alpha+\alpha^{2}-\alpha^{3}}{1-3\alpha+3\alpha^{2}-3\alpha^{3}}\big{)}$

∎

Lemma 3 and Lemma 4 conclude the proof of Theorem 7.

###### Remark 1.

Ferreira et al., (2022) show that
$\mathbb{E}[\tau]\leq\tfrac{1-\alpha}{1-3\alpha+\alpha^{2}}$ and
$\operatorname{Rew}^{\operatorname{OMNI}}(\pi^{\operatorname{OMNI}})\leq\alpha\cdot\tfrac{2-\alpha}{1-\alpha}$.
The bounds for both $\mathbb{E}[\tau]$ and
$\operatorname{Rew}^{\operatorname{OMNI}}(\pi^{\operatorname{OMNI}})$ in Lemma
4 are tighter. See Figure 4 for a comparison between the two bounds.

Lemma 2 gives an explicit method to compute $e_{t}$ for all
$t\in\mathbb{N}\cup\\{0\\}$ and thus, $\mathbb{E}[\tau]$ and
$\operatorname{Rew}^{\operatorname{OMNI}}(\pi^{\operatorname{OMNI}})$.
However, we believe $e_{t}$ does not admit a closed form solution. Instead,
for a sufficiently large $T_{\delta}$ such that
$\mathbb{E}[\tau]-\sum_{t=0}^{T_{\delta}}e_{t}<\delta$, we compute
$\big{(}e_{t}\big{)}_{0\leq t\leq T_{\delta}}$ and
$\sum_{t=0}^{T_{\delta}}e_{t}$ to get a tight bound on $\mathbb{E}[\tau]$ up
to an additive error $\delta$.

###### Lemma 0.

For $\alpha<0.38$, $\delta=10^{-7}$ and $T_{\delta}=3000$,

$\mathbb{E}[\tau]-\sum_{t=0}^{T_{\delta}}e_{t}<\delta\text{.}$

###### Proof.

$\begin{split}\mathbb{E}[\tau]-\sum_{t=0}^{T_{\delta}}e_{t}&=\sum_{t=T_{\delta}+1}^{\infty}e_{t}\\\
&\leq\sum_{t=T_{\delta}+1}^{\infty}\alpha^{2}\cdot\tfrac{2-2\alpha+\alpha^{2}}{1-\alpha+\alpha^{2}}\cdot\big{(}\alpha\cdot\tfrac{2-\alpha}{1-\alpha}\big{)}^{t-2}\\\
&=\alpha^{2}\cdot\tfrac{2-2\alpha+\alpha^{2}}{1-\alpha+\alpha^{2}}\cdot\tfrac{1-\alpha}{1-3\alpha+\alpha^{2}}\cdot\big{(}\alpha\cdot\tfrac{2-\alpha}{1-\alpha}\big{)}^{T_{\delta}-1}\end{split}$

The inequality follows from Lemma 9. We will verify that
$\alpha^{2}\cdot\tfrac{2-2\alpha+\alpha^{2}}{1-\alpha+\alpha^{2}}\cdot\tfrac{1-\alpha}{1-3\alpha+\alpha^{2}}\cdot\big{(}\alpha\cdot\tfrac{2-\alpha}{1-\alpha}\big{)}^{T_{\delta}-1}<10^{-7}$
for $\alpha=0.38$. Since the above expression is monotonically increasing in
$\alpha$, we have $\mathbb{E}[\tau]-\sum_{t=0}^{T_{\delta}}e_{t}<10^{-7}$ for
all $\alpha\leq 0.38$. Substituting $T_{\delta}=3000$, we have
$\big{(}\alpha\cdot\tfrac{2-\alpha}{1-\alpha}\big{)}^{T_{\delta}-1}<10^{-9}$
and
$\alpha^{2}\cdot\tfrac{2-2\alpha+\alpha^{2}}{1-\alpha+\alpha^{2}}\cdot\tfrac{1-\alpha}{1-3\alpha+\alpha^{2}}<37$.
Combining the two inequalities, we get the required result. ∎

The optimal omniscient reward satisfies

$\operatorname{Rew}^{\operatorname{OMNI}}(\pi^{\operatorname{OMNI}})=1-\frac{1}{\mathbb{E}[\tau]}\leq
1-\frac{1}{\sum_{t=0}^{3000}e_{t}+10^{-7}}$

We plot the non-closed form bound thus obtained in Figure 4.

Figure 4. Omniscient adversarial reward vs adversarial stake. The blue line
maps the reward of the honest strategy while the red curve maps the upper
bound on the omniscient adversarial reward from Ferreira et al., (2022). The
yellow and the green curve are the non-closed form upper bound and the upper
bound in Theorem 7 respectively. The non-closed form upper bound is tight up
to an additive error of $10^{-7}$.

###  C.3. A Restricted Omniscient Adversary

The omniscient adversary discussed in Section 3.3 is rewarded solely for
delaying the first stopping time and might be elected in only a small fraction
of rounds despite the game having a large first stopping time. In this
section, we consider a restricted omniscient adversary that can precompute
future credentials of $B$, but is not rewarded for rounds in which $B$ is
elected the leader ($X_{t}(\pi)=1$ only if the leader $i$ of round $t$ is a
wallet in $A$).

###### Theorem 6.

There exists a constant $\phi$ such that $\kappa\approx
0.38\leq\phi\leq\frac{1}{2}$ and a strategy $\pi$ for the restricted
omniscient adversary with stake $\alpha>\phi$ such that
$\operatorname{Rew}(\pi)=1$.

To prove Theorem 6, we consider an omniscient adversary with
$\alpha\geq\frac{1}{2}$ and much more constraints than the restricted
omniscient adversary that can achieve a reward $1$. The restricted omniscient
adversary that gets a better reward than its constrained counterpart will also
get a reward $1$ when $\alpha\geq\frac{1}{2}$.

We consider a greedy omniscient adversary that always broadcasts a credential
whenever the set of adversarial potential winners is non-empty. The greedy
omniscient adversary never lets $B$ to be elected the leader before the first
stopping time $\tau$. Therefore, for a strategy $\pi$, $X_{t}(\pi)=1$ for all
$1\leq t<\tau$ and $\operatorname{Rew}(\pi)=1-\tfrac{1}{\mathbb{E}[\tau]}$.

Since $B$ is never elected the leader before the first stopping time, the node
corresponding to $\operatorname{\textsc{Cred}}^{B}_{t}$ in the omniscient
choice tree $\Gamma$ does not branch and have children. Apart from not
branching at $\operatorname{\textsc{Cred}}^{B}_{t}$, the branching process
governing $\Gamma$ is identical to the omniscient adversary.

###### Definition 0 (Greedy Omniscient Choice Tree).

The greedy omniscient choice tree $\Gamma$ is built by the following
stochastic process:

  1. (1)

Level $0$ contains the root $q_{0}$ of the tree $\Gamma$.

  2. (2)

For each node $q$ not of the form $\operatorname{\textsc{Cred}}^{B}_{t}$ at
level $t\geq 0$, $q$ has $i^{*}+1$ children with probability
$\alpha^{i^{*}}\,(1-\alpha)$ for all $i^{*}\geq 0$.

  3. (3)

A node stops branching if it is of the form
$\operatorname{\textsc{Cred}}^{B}_{t}$.

  4. (4)

$\Gamma$ becomes extinct at height $\tau$ when all nodes at level $\tau$ have
stopped branching.

Observe that if a node $q$ is the only child of its parent
$\operatorname{\textsc{Cred}}^{i}_{t}$, then the adversarial potential winner
set with $Q_{t+1}=\operatorname{\textsc{Cred}}^{i}_{t}$ is empty and
therefore, $q$ must be of the form $\operatorname{\textsc{Cred}}^{B}_{t+1}$.
The extinction condition requiring a node to stop branching if it is the only
child of its parent is implicit from bullet 3 of Definition 7.

Let $E_{t}^{\prime}$ be the event that $\Gamma$ does not become extinct on or
before stage $t$ and let $e_{t}^{\prime}$ be its probability.

###### Lemma 0.

The probabilities $\big{(}e_{t}^{\prime}\big{)}_{t\in\mathbb{N}\cup\\{0\\}}$
satisfy $e_{0}^{\prime}=1$ and

$e_{t}^{\prime}=\frac{\alpha e_{t-1}^{\prime}}{(1-\alpha)+\alpha
e_{t-1}^{\prime}}$

for all $t\geq 1$.

###### Lemma 0.

For stake $\alpha>\frac{1}{2}$, the expected first stopping time
$\mathbb{E}[\tau]$ of optimal greedy omniscient strategy
$\pi^{\operatorname{OMNI}}$ is unbounded. The adversary receives a reward $1$
by playing $\pi^{\operatorname{OMNI}}$.

The proofs are almost identical to their counterparts Lemma 2 and Lemma 3 of
the omniscient adversary and we skip repeating them here.

###### Proof of Theorem 6.

The restricted omniscient adversary is weaker than the omniscient adversary.
For stake $\alpha<\kappa$, the omniscient adversary receives a reward $<1$ and
the restricted omniscient adversary cannot do better.

For $\alpha>\frac{1}{2}$, the greedy omniscient adversary receives a reward
$1$ and the restricted omniscient adversary being stronger, will also get a
reward $1$.

Thus, the infimum over all $\alpha$ such that the restricted omniscient
adversary receives a reward $1$ lies in the range $[\kappa,\frac{1}{2}]$. ∎

##  Appendix D Proof of Theorem 3

For a strategy $\pi$ in $\operatorname{CSSPA}(\alpha,\beta)$, the expected
adversarial reward in the linear version of
$\operatorname{CSSPA}(\alpha,\beta)$ equals

$\begin{split}\mathbb{E}[\sum_{t=1}^{\tau}X_{t}(\pi)]-\lambda\cdot\mathbb{E}[\tau]&=\Big{(}\frac{\mathbb{E}[\sum_{t=1}^{\tau}X_{t}(\pi)]}{\mathbb{E}[\tau]}-\lambda\Big{)}\cdot\mathbb{E}[\tau]\\\
&=\big{(}\operatorname{Rew}(\pi)-\lambda\big{)}\cdot\mathbb{E}[\tau]\end{split}$

where $\operatorname{Rew}(\pi)$ is the expected adversarial reward from
playing $\pi$ in $\operatorname{CSSPA}(\alpha,\beta)$. If
$\lambda>\operatorname{Rew}(\pi)$ ($\lambda<\operatorname{Rew}(\pi)$), the
adversary earns a negative (positive) reward in the linear version of
$\operatorname{CSSPA}(\alpha,\beta)$. Importantly, if
$\lambda=\operatorname{Rew}(\pi)$, the expected adversarial reward in the
linear $\operatorname{CSSPA}(\alpha,\beta)$ is exactly zero.

##  Appendix E Proof of Theorem 4

We prove the theorem in two steps. Let
$\operatorname{CSSPA}(\alpha,\beta,T,k)$ be the variant of the
$\operatorname{CSSPA}(\alpha,\beta)$ with a $k$-scored adversary that
terminates after $T$ rounds. We first bound the difference between the optimal
reward in the $\operatorname{CSSPA}(\alpha,\beta)$ and the optimal reward in
$\operatorname{CSSPA}(\alpha,\beta,T,\infty)$ followed by bounding the
difference between the optimal rewards in
$\operatorname{CSSPA}(\alpha,\beta,T,\infty)$ and
$\operatorname{CSSPA}(\alpha,\beta,T,k)$.

Remember that $\pi^{\operatorname{OPT}}_{T,k}$ is the optimal strategy of the
$k$-scored adversary in $\operatorname{CSSPA}(\alpha,\beta,T,k)$ and
$\pi^{\operatorname{OPT}}$ is the fully functional adversary’s strategy in
$\operatorname{CSSPA}(\alpha,\beta)$.

###  E.1. Loss in Reward from Terminating after $T$ Rounds

In this section, we bound the optimal reward of an $\infty$-scored adversary
in $\operatorname{CSSPA}(\alpha,\beta,T,\infty)$ and the optimal CSSPA reward.
For convenience, we will abuse notation and write
$\mathbb{E}[\operatorname{Rew}(\cdot)]$ for $\operatorname{Rew}(\cdot)$ in
Section E.1 and Section E.2.

###### Lemma 0.

For $\alpha\leq\kappa\approx 0.38$,

$0\leq\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}})-\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\infty})]\leq\alpha^{2}\cdot\tfrac{2-2\alpha+\alpha^{2}}{1-\alpha+\alpha^{2}}\cdot[\alpha\cdot\tfrac{2-\alpha}{1-\alpha}]^{T-2}$

###### Proof.

The left hand side is easy to see. $\pi^{\operatorname{OPT}}_{T,\infty}$ is a
valid strategy in $\operatorname{CSSPA}(\alpha,\beta)$. The optimal strategy
$\pi^{\operatorname{OPT}}$ is only going to yield a better reward.

We proceed to the right hand side. As usual, let $\tau$ denote the first
stopping time of $\pi^{\operatorname{OPT}}$ in
$\operatorname{CSSPA}(\alpha,\beta)$. Let $\operatorname{Rew}_{T}(\pi)$ be the
reward of playing a strategy till time $T$ and terminating.

$\begin{split}\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}})]&=Pr(\tau\leq
T)\,\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}})|\tau\leq
T]+Pr(\tau>T)\,\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}})|\tau>T]\\\
&=Pr(\tau\leq
T)\,\mathbb{E}[\operatorname{Rew}_{T}(\pi^{\operatorname{OPT}})|\tau\leq
T]+Pr(\tau>T)\times\\\ &\hskip
42.67912pt\mathbb{E}[\operatorname{Rew}_{T}(\pi^{\operatorname{OPT}})+\\{\operatorname{Rew}(\pi^{\operatorname{OPT}})-\operatorname{Rew}_{T}(\pi^{\operatorname{OPT}})\\}|\tau>T]\\\
&=\mathbb{E}[\operatorname{Rew}_{T}(\pi^{\operatorname{OPT}})]+Pr(\tau>T)\,\mathbb{E}[\\{\operatorname{Rew}(\pi^{\operatorname{OPT}})-\operatorname{Rew}_{T}(\pi^{\operatorname{OPT}})\\}|\tau>T]\\\
&\leq\mathbb{E}[\operatorname{Rew}_{T}(\pi^{\operatorname{OPT}}_{T,\infty})]+Pr(\tau>T)\\\
&=\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\infty})]+Pr(\tau>T)\end{split}$

Conditioned on the stopping time being at most $T$, there is no difference
between playing $\pi^{\operatorname{OPT}}$ and playing
$\pi^{\operatorname{OPT}}$ only till time $T$ and terminating. Thus,
$\operatorname{Rew}(\pi^{\operatorname{OPT}})$ can be equated to
$\operatorname{Rew}_{T}(\pi^{\operatorname{OPT}})$ in the first equation.
Observe that $\operatorname{Rew}_{T}(\pi^{\operatorname{OPT}}_{T,\infty})$
yields a better reward than any strategy that recommends termination after $T$
rounds. In particular,
$\mathbb{E}[\operatorname{Rew}_{T}(\pi^{\operatorname{OPT}}_{T,\infty})]\geq\mathbb{E}[\operatorname{Rew}_{T}(\pi^{\operatorname{OPT}})]$.
Further,
$0\leq\operatorname{Rew}(\pi^{\operatorname{OPT}}),\operatorname{Rew}_{T}(\pi^{\operatorname{OPT}})\leq
1$ and therefore,
$\mathbb{E}[\\{\operatorname{Rew}(\pi^{\operatorname{OPT}})-\operatorname{Rew}_{T}(\pi^{\operatorname{OPT}})\\}|\tau>T]\leq
1$. Combining the above, we get the first inequality. The last equality
follows since $\pi^{\operatorname{OPT}}_{T,\infty}$ anyways recommends
terminating before round $T$ and therefore
$\operatorname{Rew}_{T}(\pi^{\operatorname{OPT}}_{T,\infty})=\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\infty})$.

The lemma follows by bounding $Pr(\tau>T)$ by
$\alpha^{2}\cdot\frac{2-2\alpha+\alpha^{2}}{1-\alpha+\alpha^{2}}\cdot[\alpha\cdot\frac{2-\alpha}{1-\alpha}]^{T-2}$
from Lemma 9. ∎

###  E.2. Loss in Reward for a $k$-Scored Adversary

We bound the difference between the optimal rewards in
$\operatorname{CSSPA}(\alpha,\beta,T,\infty)$ and
$\operatorname{CSSPA}(\alpha,\beta,T,k)$.

###### Lemma 0.

For $\alpha\leq 0.29$,

$0\leq\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\infty})]-\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,k})]\leq\alpha^{k}$

We first show that the probability of an adversary ever having $k$ adversarial
potential winners is at most $\alpha^{k}$. Once this is established, the proof
is similar to the bound on the rewards in $\operatorname{CSSPA}(\alpha,\beta)$
and $\operatorname{CSSPA}(\alpha,\beta,T,\infty)$.

###### Lemma 0.

Let $\alpha\leq 0.29$. The probability that the adversary never encounters a
round with at least $k$ adversarial potential winners before the first
stopping time in $\operatorname{CSSPA}(\alpha,\beta)$ is at least
$1-\alpha^{k}$.

###### Proof.

Consider an omniscient adversary whose sole purpose is to encounter a round
with at least $k+1$ adversarial potential winners. Let $E$ be the event that
the adversary never encounters such a round and $e=Pr(E)$. Clearly, the
probability of the real adversary never encountering such a round is only
larger.

Consider a round $t$ where $\hat{W}$ is the random set of adversarial
potential winners. $E$ happens precisely when

  1. (1)

the current round is a stopping time $(\tau=t)$, or

  2. (2)

$|\hat{W}|\leq k$ and none of the potential winners (including $B$) lead to a
future round with at least $k+1$ adversarial potential winners.

Thus,

$Pr(E)=Pr(\tau=t)+\sum_{i^{*}=1}^{k}Pr(|\hat{W}|=i^{*})\times Pr(E)^{i^{*}+1}$

$Pr(\tau=t)=1-\alpha$ and $Pr(|\hat{W}|=i^{*})=\alpha^{i^{*}}\cdot(1-\alpha)$
(by Lemma 8). Plugging them in,

$e=(1-\alpha)+\sum_{i^{*}=1}^{k}(1-\alpha)\cdot\alpha^{i^{*}}e^{i^{*}+1}$

Let $\nu=\alpha\,e$. The above can be rewritten as

(2)
$\begin{split}\nu&=\alpha(1-\alpha)+(1-\alpha)\nu^{2}\sum_{i=0}^{k-1}\nu^{i}\\\
&=\alpha(1-\alpha)+(1-\alpha)\nu^{2}\frac{1-\nu^{k}}{1-\nu}\end{split}$

The goal is to locate the root of the above equation. We show that the root
$\nu=\alpha\,e$ is at least $\alpha-\alpha^{k+1}$ in Section E.3. Thus, $e\geq
1-\alpha^{k}$, establishing the claim. ∎

###### Proof of Lemma 2.

Similar to Lemma 1, the left hand side of the inequality is straightforward.
The $\infty$-scored adversary’s reward is only larger than that of the
$k$-scored adversary. Thus,
$0\leq\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\infty})]-\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,k})]$.

Let $E$ be the event that the adversary does not see more than $k$ adversarial
potential winners till the $\tau$ in
$\operatorname{CSSPA}(\alpha,\beta,T,\infty)$, and let $\overline{E}$ be its
complement. Let $\pi^{\operatorname{OPT}}_{T,\leq k}$ be the strategy that
copies $\pi^{\operatorname{OPT}}_{T,\infty}$ until the adversary encounters
$k+1$ adversarial potential winners and then terminates. Observe that
conditioned on $E$, $\pi^{\operatorname{OPT}}_{T,\infty}$ and
$\pi^{\operatorname{OPT}}_{T,\leq k}$ are identical. Thus,

$\begin{split}\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\infty})]&=Pr(E)\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\infty})|E]+Pr(\overline{E})\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\infty})|\overline{E}]\\\
&=Pr(E)\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\leq
k})|E]+Pr(\overline{E})\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\leq
k}))+(\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\infty})-\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\leq
k})|\overline{E}]\\\
&=\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\leq
k})]+Pr(\overline{E})\mathbb{E}[(\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\infty})-\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\leq
k})|\overline{E}]\end{split}$

$\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\leq k})]$ is only
smaller than the $k$-scored adversary’s optimal reward
$\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,k})]$. Further,
$0\leq\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\infty}),\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\leq
k})\leq 1$. Hence,

$\begin{split}\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\infty})]&=\mathbb{E}[\operatorname{Rew}(\pi^{\operatorname{OPT}}_{T,\leq