Profitable Manipulations of Cryptographic Self-Selection are Statistically Detectable

BY KEYHUNTER 05.03.2025
Profitable Manipulations of Cryptographic Self-Selection are Statistically Detectable

Cryptographic Self-Selection is a common primitive underlying leader-selection for Proof-of-Stake blockchain protocols. The concept was first popularized in Algorand [CM19], who also observed that the protocol might be manipulable. [FHWY22] provide a concrete manipulation that is strictly profitable for a staker of any size (and also prove upper bounds on the gains from manipulation).

Separately, [YSZ23, BW24] initiate the study of undetectable profitable manipulations of consensus protocols with a focus on the seminal Selfish Mining strategy [ES14] for Bitcoin’s Proof-of-Work longest-chain protocol. They design a Selfish Mining variant that, for sufficiently large miners, is strictly profitable yet also indistinguishable to an onlooker from routine latency (that is, a sufficiently large profit-maximizing miner could use their strategy to strictly profit over being honest in a way that still appears to the rest of the network as though everyone is honest but experiencing mildly higher latency. This avoids any risk of negatively impacting the value of the underlying cryptocurrency due to attack detection).

We investigate the detectability of profitable manipulations of the canonical cryptographic self-selection leader selection protocol introduced in [CM19] and studied in [FHWY22], and establish that for any player with $\alpha < \frac{3-\sqrt{5}}{2} \approx 0.38$ fraction of the total stake, every strictly profitable manipulation is statistically detectable. Specifically, we consider an onlooker who sees only the random seed of each round (and does not need to see any other broadcasts by any other players). We show that the distribution of the sequence of random seeds when any player is profitably manipulating the protocol is inconsistent with any distribution that could arise by honest stakers being offline or timing out (for a natural stylized model of honest timeouts).

1 Introduction

Since Nakamoto introduced Bitcoin in 2008, blockchain technology has made a significant impact on digital transactions by establishing a decentralized system in which transactions are validated through consensus among peers, rather than by a central authority. This innovation, while popularizing decentralized currencies, has also brought to light substantial challenges, particularly the extensive computational and energy demands of its proof-of-work (PoW) consensus mechanism. Notably, the energy consumption associated with Bitcoin mining exceeds that of many countries, raising significant environmental concerns. Furthermore, the necessity for large-scale mining hardware introduces considerable centralization risks to cryptocurrencies [AW19], many of which are inherently designed to be decentralized.

In response to these challenges, the blockchain community has been exploring Proof of Stake (PoS), which has been implemented in many prominent cryptocurrencies (e.g. Ethereum, Algorand, Cardano). In each round, PoS selects block leaders (who get to propose a block to be included) based on the stake, reducing energy usage and aiming to prevent Sybil attacks by randomly assigning leadership chances proportionally to coin holdings. However, the leader selection process in PoS presents additional challenges. For example, the pseudorandomness resulting from PoW is in some sense “external” to the blockchain (the next miner is selected proportionally to their computational power, independently, and nothing in the blockchain itself can influence this). Replicating this property in PoS blockchains has proved challenging without trusting an external randomness beacon (which is often a non-starter in blockchain applications, whose entire purpose is to remove the need for such trust).\footnote{To slightly elaborate on this point: trusting a centralized external randomness beacon (such as NIST) is certainly a non-starter, because NIST then has control over the block producers. One could instead have an external distributed process to generate random numbers independent of this blockchain. But if this blockchain has monetary value, then securely implementing that distributed process is its own challenge. The story is getting more subtle with Verifiable Delay Functions that might act as a cryptographic external randomness beacon, although their security assumptions are hardware-based and not as battle-tested as standard cryptography, so there will always be a desire for solutions based on standard cryptography.}

On the other hand, pseudorandom numbers generated using the blockchain itself can often be predicted by the miners, opening up the possibility of profitable deviations [BNPW19].

One promising idea in addressing the leader selection challenge is cryptographic self-selection, initially proposed by Algorand [CM19]. Cryptographic self-selection is a protocol to select a block-proposer for round $r + 1$ as a function of communication during round $r$. We overview Algorand’s canonical proposal shortly, and briefly note here that it is known to admit profitable deviations for arbitrarily small participants [FHWY22].\footnote{This is in contrast to block-witholding manipulations in PoW longest-chain protocols [SSZ16, KKKT16, ES14], although alternate strategic manipulations of some PoW protocols are profitable for arbitrarily small miners [FKKP19, GS19, YSZ23].}

We subsequently discuss cryptographic self-selection in further detail, but at this point merely wish to note that: (a) nonmanipulable randomness sources are a major open problem within the blockchain community, due to applications for PoS, (b) these problems are important to both researchers [BNPW19, CM19, FW21, FHWY22] and practitioners [AR20], and (c) the particular approach initially proposed in [CM19] is a canonical testbed due to its elegance and simplicity (which we overview shortly).

Separately, recent work of [YSZ23, BW24] propose a novel concern for profitable manipulations: detectability. Specifically, while it may be challenging to \textit{trace} a strategic manipulation to a particular actor in a permissionless system, profitable manipulations would likely be detectable. This observation serves as a basis to mitigate concerns with profitable manipulations in practice – perhaps the manipulator will earn moderate additional cryptocurrency via manipulation, but its detection may cause the value of these tokens to tank when measured in USD. Their work highlights that detectability of strategic manipulations plays a significant role in their usability in practice – undetectable deviations avoid the risk of devaluing the underlying cryptocurrency, while detectable ones can be disincentivized through outside-the-model means.

Our paper lies at the intersection of these two agendas: we investigate the detectability of profitable manipulations in cryptographic self-selection. Surprisingly, our main result finds that for any participant with less than ( \frac{3 – \sqrt{5}}{2} \approx 0.38 ) fraction of the total stake, all profitable manipulations of Algorand’s canonical cryptographic self-selection protocol are statistically detectable.

We now provide additional context and details for our result.

Leader Selection in PoS Blockchains. PoS consensus protocols typically take one of two forms: they may be a longest-chain protocol, or a Byzantine Fault Tolerant (BFT)-based protocol. Both formats are well-represented in practice, and Ethereum is in some sense a hybrid of the two. In a longest-chain protocol, strategic manipulations are more straight-forward – they typically come by inducing forks, and causing the attacker to have their own blocks represent a greater fraction of blocks in the longest chain [ES14, SSZ16, KKKT16, BNPW19, FW21]. Manipulations of BFT-based protocols are more subtle. BFT-based protocols proceed one block at a time, reaching a strong consensus on block ( r ) and finalizing it forever before getting to work on block ( r + 1 ). As such, these protocols are nonmanipulable at the per-block level (unless the attacker has sufficient stake to cause significantly more damage by violating consensus entirely). Instead, these protocols typically have a randomly-selected “leader” dictate the contents of the block and the per-round BFT protocol aims to reach consensus on the leader’s block. But, these protocols still need an effective method to select a leader for each round independently and proportional to their stake.

Fortunately for mechanism designers, leader selection protocols are often modular components of the broader blockchain protocol, and can be studied in isolation from the (significantly more complex) BFT protocols that handle per-round consensus.

Algorand’s Canonical Leader Cryptographic Self-Selection. [CM19] propose an elegant leader selection protocol, which we describe for simplicity in the case where each account holds the same number of coins (we rigorously overview their protocol in the general case in Section 2, but omit the generalization now in the interest of clarity). First, pick a uniformly random seed, ( Q_1 ), for round one. Then in round ( r ), ask each account holder ( i ) to first digitally sign ( Q_r ) and then hash(^5) their digital signature to get a credential ( \text{Cred}_r^i ). Whoever broadcasts the smallest credential is the leader for round ( r ).

Their protocol has several desirable properties. First, assuming that every player honestly digitally signs and hashes in each round (and that the hash function behaves like a random oracle),

4 This is not to say that tracing strategic manipulations is impossible – indeed, law enforcement regularly traces attacks in permissionless systems: link.

5 The formal concept is a Verifiable Random Function, which we define in Section 2.1. Intuitively, the hash is a uniformly random number drawn specifically for player ( i ) in a manner that no other player can precompute (because they can’t digitally sign on behalf of player ( i )).

the leader in each round is indeed a uniformly random coin, independent of all previous rounds. Second, it is not predictable too far into the future: because player ( i ) cannot digitally sign on behalf of player ( j ), player ( i ) has absolutely no idea what seed might result next round (if another player is the leader). Finally, the manner in which it can possibly be manipulated is extremely structured: the only strategies available to a player are to broadcast or not broadcast their credentials.

Still, their protocol is not perfect – ([\text{CM19}]) already acknowledge that it might be manipulable, and ([\text{FHWY22}]) establish a strictly profitable strategy for arbitrarily small players. ([\text{FHWY22}])’s strategy is fairly simple, and we overview it in Section 4.

Detecting Strategic Behavior in Cryptographic Self-Selection. How would one detect that a participant is strategically manipulating a protocol? In PoW longest-chain protocols, ([\text{BW24}]) propose to look at the pattern of forks – strategic behavior often results in long runs of consecutive forks whereas routine latency instead would result in independently distributed forks. This particular detection method is not applicable to a BFT-based protocol, as BFT-based protocols have no forks once a block is finalized.

In the spirit of ([\text{BW24}]), we aim to detect strategies using the minimal amount of information possible, and in particular we only use information that is available to anyone following the blockchain. Specifically, anyone following the blockchain must know who is the leader of round ( r ) and must know their credential ( \text{Cred}_r^i ) that proves they are the leader.

If every participant in the network were honest, and there were ( n ) coins in the network, we would expect in a given round that the winning credential is distributed according to the minimum of ( n ) independent draws of the Hash function. So across a large number of rounds, an observer could check the sequence of winning credentials and see if they empirically match i.i.d. draws of the minimum of ( n ) independent draws of the Hash function.

This is perhaps too strong of an assumption on honest parties, however. In particular, it assumes either that every single coin is online and participating in the protocol or that the observer otherwise knows that exactly (say) ( k ) coins are online. An observer instead might know that there exists some number ( k ) of online coins participating in the protocol, but not know ( k ). Then, they would expect to see sequences of credentials that empirically match i.i.d. draws from the minimum of ( k ) independent draws of the Hash function, for some ( k ).

So consider an attacker who controls multiple accounts. They can selectively refrain from broadcasting in round ( r ) (and might benefit from doing so, if another account will win round ( r ) anyway and their chosen credential gives them a better shot of winning round ( r + 1 )), but doing so will skew the distribution of round ( r )’s credential larger and the distribution of round ( r + 1 )’s credential smaller. This is profitable, but when done naively detectable (we analyze ([\text{FHWY22}])’s particularly simple strategy, which follows from this intuition, in Section 3). The challenge for the attacker is whether it is possible to profit (by biasing their winning credential to be lower in some rounds), without being detectable (by biasing the winning credential in other rounds to be higher).

Our main result shows that this is impossible: for any ( \alpha < \frac{3 – \sqrt{5}}{2} \approx 0.38,6 ) and any participant with an ( \alpha ) fraction of the total stake, any strategy that leads a ( > \alpha ) fraction of the rounds produces a distribution over sequences of winning credentials that is not consistent with any number of online honest coins.(^7)

(^6)Note, for example, that an adversary with ( \alpha > \frac{3 – \sqrt{5}}{2} > 1/3 ) of the stake could alternatively directly violate the underlying consensus protocol, which would do significantly more damage than a strategic manipulation.

(^7)Like most prior work (e.g. ([\text{KKKT16, BNPW19, FW21, BW24}])), we consider an attacker who does not have excessively strong network connectivity – see Section 3 for the formal setup.

Finally, one might even consider having a fixed $k$ of online coins to be too stringent of a null hypothesis – perhaps the number of active coins fluctuates from round to round. We also establish that our main result degrades smoothly in the deviation an observer is comfortable attributing to honest-but-occasionally-offline behavior. If the observer believes the online coins to fluctuate within $1 \pm \delta$ of an unknown baseline, and the true online coins indeed fluctuate within $1 \pm \delta$ of some ground truth baseline, undetectable manipulations lead at most an additional $2\delta$ fraction of rounds.

Roadmap and Discussion. We study the detectability of strategic manipulations in cryptographic self-selection, Algorand’s canonical leader selection protocol \cite{CM19}. We establish that any profitable deviation is detectable, and also quantitatively extend our results to even further relaxed null hypotheses of what might result from honest-but-offline behavior.

Detectability of profitable manipulations is a desirable property of consensus protocols, as it provides an outside-the-model avenue to deter deviant behavior. While \cite{BW24} derive profitable, undetectable deviations from longest-chain PoW consensus protocols, we instead show that cryptographic self-selection admits no profitable manipulations. Our work now establishes that some canonical protocols admit undetectable profitable deviations while others do not, and further motivates detectability of profitable manipulations as a standard question to be asked of novel consensus protocols.

In Section 1.1, we overview related work in further detail. In Section 2 and Section 3 we overview our model and our statistical detection methods in significantly more detail. Section 4 overviews the profitable strategy of \cite{FHWY22} through the lens of detectability in order to familiarize the reader with the techniques. Section 5 formally states and proves our main result and its robust extension.

1.1 Related Work

Detection of Strategic Attacks in Proof-of-Work Protocols. Several methods of detecting selfish mining in proof-of-work protocol have been proposed. \cite{CAJR20} presents a heuristic to detect selfish mining based on changes in the height of forks in a blockchain network and their simulation result implies a connection between the presence of selfish mining attack and higher rate of forks, with a mean height of higher than 2.

\cite{LCT22} proposes a statistical test for each miner based on the null hypothesis that under honest mining, the probability of observing two successive blocks mined by the same miner is given by type II binomial distribution of order 2, and the presence of selfish mining will cause deviation from such distribution, causing a higher probability of observing successive blocks mined by the same miner. The authors conduct empirical tests on five cryptocurrencies based on Proof-of-Work—Bitcoin, Litecoin, Ethereum, Monacoin and Bitcoin Cash and claim to be the first research work that reveals the presence of selfish mining in real cryptocurrency systems, although they acknowledge that other reasons can also lead to abnormal successive block discovery rates. We further note that their detection method relies on knowing which addresses or wallets are controlled by the same user, while our detection scheme does not rely on such knowledge.

Other works such as \cite{WLL+21} use neural networks that achieve good accuracy of detecting selfish mining on simulated datasets.

In contrast to these detection methods, \cite{BW24} proves the existence of a statistically undetectable and strictly profitable selfish mining strategy for miners with 38.2% of the total hash rate.

Under this strategy, the attacker hides their block with carefully constructed probabilities such that the eventual structure of the blockchain under this selfish mining attack has the same distribution as the structure of the blockchain constructed by only honest miners with a different latency parameter. Thus statistical tests that only look at the pattern of the blockchain itself such as fork heights cannot detect their attack.

Strategic Manipulation of Consensus Protocols. Following seminal work of [ES14], there is now a long body of work studying strategic manipulations in consensus protocols [ES14, SSZ16, KKKT16, CKWN16, GS19, FKKP19, FW21, FHWY22, YTZ22, YSZ23, BW24]. These works are all thematically related to ours in that we also study strategic manipulation of consensus protocols. Of these, only [FHWY22] bears any technical similarities, as the others all study longest-chain variants.

In terms of motivating cryptographic self-selection, [BNPW19] establish that longest-chain variants with fully-internal pseudorandomness are all vulnerable to a selfish-mining-style attack based on predicting future randomness.

Research works on the detection of strategic attacks mostly focus on the longest-chain Proof-of-Stake protocols such as [NMRP20]. To the best of our knowledge, our work is the first to propose a detection method for manipulating leader selection protocols in BFT-based blockchains.

Relevant Proof-of-Stake Protocols in Practice. Several large blockchains employ Proof-of-Stake over Proof-of-Work, and there is not yet convergence on a dominant consensus paradigm. For example, Cardano [KRDO17] uses a longest-chain variant considered in [BNPW19], Algorand uses cryptographic self-selection [GHM+17, CM19] considered in [FHWY22] (although Algorand seems to have since updated their leader selection to induce a round robin aspect – every ( k ) rounds, the winner’s credential sets the seeds for the subsequent ( k ) rounds. See [GHM+17].), and Ethereum uses a hybrid of the two (although manipulations of Ethereum are much closer to manipulations of cryptographic self-selection than of longest-chain protocols – see here). In terms of relevance for practice, our results (a) highlight a desirable property of [CM19]’s original cryptographic self-selection that is desirable in practice, and (b) serve as a canonical example to highlight manners in which a protocol might avoid undetectable profitable deviations.

2 Model and Preliminaries

2.1 Proof-of-Stake Consensus Protocols with Finality

Proof-of-stake protocols with finality look more like classical Consensus algorithms from Distributed Systems than Bitcoin’s Longest-Chain protocol. That is, these protocols repeatedly run a secure consensus algorithm to agree on a block of authorized transactions, add this block of transactions to the ledger, and proceed. Unlike the Longest-Chain protocol, these blocks are added to the ledger and remain in the ledger forever. In order to maintain security guarantees, the consensus algorithm for each block is often complex.

To mitigate this complexity (both computational, communication, and conceptual), many protocols select a leader ( \ell_t ) who plays a special role in the consensus protocol. Intuitively, all participants try to copy the leader’s proposed block. Similarly to a Longest-Chain protocol, the leader ( \ell_t ) dictates the contents of the block. That is, the contents of Block ( t ) are fully dictated by the leader ( \ell_t ), just like in a Longest-Chain protocol (and the only difference is how consensus is reached so that the rest of the network agrees on what block was indeed dictated). As a result, we model the payoff of players to be the probability of being a block leader, since Thus, being the block leader is the only way where players could gain profits (either from block rewards or MEV).

In order to mitigate grinding attacks, the leader-selection protocol typically needs to ensure that when participants are behaving honestly, the probability that each participant (or pool of participants) gets to be the leader in each round is proportional to each participant’s stake (hence the name “proof-of-stake”). Moreover, there should be limited room for a participant to gain extra profit by deviating from the protocol.

Cryptographic self-selection (used by Algorand ([CM19, GHM^{+}17])) is an elegant solution for the leader-selection protocol, which does not rely on the existence of frequent and high quality randomness beacon to generate a random seed for each round. Instead, it uses information about the previous rounds to generate a seed for the current round. We now briefly describe the protocol and the parts that are relevant for constructing a statistical detection method of strategic deviation from the protocol. The reader could refer to ([FHWY22, CM19]) for a more detailed description of the protocol and encryption schemes.

There are two key components to the cryptographic self-selection protocol: Verifiable Random Functions (VRFs) and balanced scoring functions.

Definition 2.1 (Verifiable Random Function (VRF) ([MRV99])). A Verifiable Random Function is a public-key cryptographic function that generates public key and secret key pairs, denoted ((sk, pk)), and efficiently evaluates an input (x) using a function (f_{sk}) that is dependent on the secret key. The function produces an output (y) and a proof of correctness, which can be verified efficiently by anyone who has the public key. The following security properties are guaranteed:

  • Pseudorandomness: Given the public key (pk) and a sequence of input-output pairs ((x_1, y_1), \ldots, (x_n, y_n)) with their corresponding proofs, it is computationally infeasible to predict (y = f_{sk}(x)) for any (x \neq x_1, \ldots, x_n) without the secret key (sk). In fact, the distribution of (y) looks indistinguishable from the uniform distribution on ([0, 1]).
  • Unique Provability: For any input (x), there is exactly one output (y) that can be verified as the correct computation of (f_{sk}(x)).

A balanced scoring function takes in the pseudorandom output generated from the VRF associated with an account (i.e. parametrized by the account’s secret key) and the amount of stake in that account, and yields a score. The account with the minimum score is selected as the leader. A balanced scoring function always selects a leader proportional to the account’s stake assuming the outputs of the VRFs are truly random. In particular, this implies that splitting one’s stake between multiple accounts and/or merging stake with another entity does not impact the probability of being selected as the minimum. This forms the basis for selecting a leader-selection protocol that selects leaders independently in each round proportional to their stake.

Definition 2.2 (Balanced Scoring Function ([FHWY22])). A scoring function (S(\cdot, \cdot)) takes as input a credential (X_i) and a quantity of stake (\alpha_i) and outputs a score (S(X_i, \alpha_i)). A scoring function is balanced if for all (n) and all player stakes (\alpha_1, \ldots, \alpha_n),

[ \Pr_{X_1, \ldots, X_n \leftarrow U([0,1])} \left[ \arg\min_{i \in [n]} S(X_i, \alpha_i) = j \right] = \frac{\alpha_j}{\sum_{i=1}^{n} \alpha_i}. ]

Proposition 2.3 ([FGH+24]). Let ( S(\cdot, \cdot) ) be any balanced scoring function. Then, for all ( n \in \mathbb{N} ) and ((\alpha_i){1 \leq i \leq n}), the random variables ( S(X, \sum{i=1}^{n} \alpha_i) ) and ( \min_{1 \leq i \leq n} { S(X_i, \alpha_i) } ) are identically distributed for ( X, X_1, \ldots, X_n \sim U([0, 1]) ).

Definition 2.4 (Cryptographic Self-Selection Protocol (CSSP), [FHWY22]). The Cryptographic Self-Selection Protocol (CSSP) operates as follows:

  1. Each account ( i ), with stake ( \alpha_i ), sets up a VRF ( f_{sk_i}(\cdot) ) with a pair of secret key and public key ((sk_i, pk_i)). Participants agree on some Balanced Scoring Function ( S(\cdot, \cdot) ).
  2. ( Q_r ) denotes the seed used during round ( r ). ( Q_1 ) is a uniformly random draw from ([0, 1]), and ( Q_r ) will be determined during round ( r-1 ) (see below).
  3. In round ( r ), each account ( i ) computes their credential ( Cred^r_i = f_{sk_i}(Q_r) ) using their VRF ( f_{sk_i} ). Each account-holder should broadcast their credential (this is not enforced – an account-holder may choose not to broadcast, if desired).
  4. The leader ( \ell_r ) is the account-holder ( i ) who broadcasts the credential with the lowest score ( S(Cred^r_i, \alpha_i) ).
  5. The seed for the next round, ( Q_{r+1} ), is set as the credential of the leader of round ( r ), namely ( Cred^r_{\ell_r} ).

The actions of a player (who may control multiple accounts) in round ( r ) of a CSSP are simply to decide which (if any) of their credentials to broadcast. The payoff to player ( i ) is the fraction of rounds in which they are the leader. Formally, if ( L_p(r) ) is the indicator variable for whether an account controlled by player ( p ) is the leader in round ( r ), then the payoff to player ( p ) is ( \lim\inf_{r \to \infty} \sum_{r’ \leq r} L_p(r’) / r ).

CSSP is a formalization of the leader-selection protocol initiated by Algorand [CM19]. Note that leader-selection is but one aspect of a Proof-of-Stake protocol (the core of the protocol is reaching consensus on the block proposed by the leader). Fortunately, the leader-selection protocols are modular, and can be studied in isolation from the (significantly more complex) consensus algorithms that use them.

2.2 Strategic Play in CSSP

Studies of strategic manipulation in consensus protocols first and foremost aim to understand whether one should expect strategic players to choose to be honest. As such, the overwhelming majority of prior work considers a single strategic player against a profile of honest players. [FHWY22] establish that this single strategic player is not incentivized to be honest, and we ask whether a strategy that realizes these gains is always detectable. In concurrent and independent work, [FGH+24] establish tight bounds on the profitability of manipulations. They do not consider detectability, and therefore the work is orthogonal to ours.

In a CSSP, honest behavior corresponds to broadcasting all credentials in every round. A strategic player may selectively choose which credentials to broadcast in each round. It should initially seem counterintuitive that strategic behavior is profitable – hiding a credential in round ( r ) certainly cannot help a player win round ( r ). However, hiding a credential in round ( r ) might help a player win round ( r’ > r ) by influencing the seed ( Q_{r’} ).

Consider a CSSP parameterized by $\alpha$, the fraction of stake controlled by the strategic player, and $\beta \in [0, 1]$, the network connectivity strength of the strategic player. The strategic player is called $\beta$-strong if it learns $\beta$ fraction of the credentials broadcast by the honest players before they must broadcast themselves. Specifically, $\beta = 1$ represents a player that learns all credentials of the honest players before they broadcast (because they are extremely well-connected in the network) and $\beta = 0$ represents a player that learns none of the credentials of the honest players.

\cite{FHWY22} make refinement of the strategy space of the CSSP game by showing that any strategy of the strategic player is equivalent to a strategy that only broadcasts at most one credential per round, splits their stake into as many accounts as possible, and considers only two honest players $B$ and $C$, the former with $\beta(1-\alpha)$ fraction of the stake, and the latter with $(1-\beta)(1-\alpha)$ fraction of the stake. Their proof shows that for any strategy $s$ in CSSP, you can find another strategy $s’$ in the refined strategy space with the same payoff. Since our focus is on both the profitability and detectability of a strategy, we need to show that such refinement also preserves the detectability of a strategy. Our detection methods (will be introduced in Section 5) only assume an access to the broadcast credential with the minimum score (i.e. the leader’s credential) in each round. Thus two strategies that induce the same minimum broadcast credential in each round are either both detectable or both undetectable. Since for any undetectable strategy $s$ in CSSP, there is also an undetectable strategy $s’$ in the refined strategy space, by having $s’$ broadcast the same credential in each round as the minimum credential that $s$ broadcasts (and broadcasts none if $s$ broadcasts none), it is without loss of generality to consider only refined strategies from now on. The refined strategy space is described below:

Definition 2.5 (Refined CSSP, \cite{FHWY22}). The strategic player first splits their stake in as many account as possible. This set of accounts, denoted as $A$, is then fixed for all rounds. In each round $r$ of CSSP, the strategic player:

  1. Is aware of the seed $Q_r$ and the honesty of player $B$ and $C$.
  2. Has access to the credential $\text{Cred}_r^B$ of honest player $B$, but not to the credential $\text{Cred}_r^C$ of honest player $C$. The player only knows the fact that $\text{Cred}_r^C$ is distributed uniformly on $[0, 1]$.
  3. Can compute credentials $\text{Cred}_r^i$ and scores $S(\text{Cred}_r^i, \alpha_i)$ for accounts $i \in A$, and can compute the score $S(\text{Cred}_r^B, \beta(1-\alpha))$.
  4. For each $\ell \in A \cup {B}$, can imagine that perhaps $Q_{r+1} = \text{Cred}_r^\ell$, and then pre-computes hypothetical credentials $\text{Cred}_r^{i+1}$ for each $i \in A$ in case we were to have $\ell_r = \ell$.
  5. Can extend this pre-computation to any round $k$ and sequence of accounts $i_0, \ldots, i_k$ (with $i_0 \in A \cup {B}$ and $i_\ell \in A$ for $0 < \ell \leq k$), and compute $\text{Cred}r^{i+k}$ based on the hypothetical possibility that $\ell_r + \ell_l = i\ell$ for each $l \in {0, \ldots, k-1}$.
  6. Selects an account $i^* \in A$ and broadcasts its credential $\text{Cred}_r^{i^*}$, or chooses not to broadcast any credential.

The Refined CSSP is the precise mathematical game we study, for a particular balanced scoring function $S$. In addition, Proposition 2.6 implies that the game induced by CSSP is the same for any balanced scoring function used in the protocol. They further imply that if we have a statistical detection method for strategic behavior under one CSSP protocol using a particular balanced scoring function ( S ), we can apply the same detection method to a variant of the protocol using another balanced scoring function ( S’ ). Therefore, undetectable profitable strategies exist for any leader-selection protocol based on Algorand’s cryptographic self-selection if and only if they exist in the Refined CSSP for any particular ( S ) of our choosing.

Proposition 2.6 ([FHWY22, FGH+24]). The game induced by CSSP with a balanced scoring function is independent of the particular balanced scoring function used. Formally, for two distinct balanced scoring functions ( S, S’ ), the games induced by CSSP are identical. Specifically, for all players ( i ), there is a bijective mapping ( f ) from strategies of player ( i ) in the CSSP with ( S ) to strategies of player ( i ) in the CSSP with ( S’ ), where all players broadcast the same set of credentials in each round. For all ( i ), the payoff to player ( i ) in the CSSP with ( S ) under strategy profile ( s ) is exactly the same as the payoff to ( i ) in the CSSP with ( S’ ) under strategy profile ( \langle f_i(s_i) \rangle ).

To simplify our analysis, we choose ( S(X, \alpha) := -\ln(X)/\alpha ), which induces an exponential distribution with rate ( \alpha ), i.e., when ( X ) is drawn from ( U([0,1]) ), ( S(X, \alpha) ) is drawn from ( \text{Exp}(\alpha) ). The exponential distribution has the nice property that for a set of random variables ( X_1, \ldots, X_n ) drawn from ( \text{Exp}(\alpha_1), \ldots, \text{Exp}(\alpha_n) ) respectively, the minimum score ( \min_{i \in [n]} X_i ) is distributed according to ( \text{Exp}(\sum_{i=1}^{n} \alpha_i) ). This implies that if the total sum of active stakes is 1 and all players are honest, then the minimum score broadcast is distributed according to ( \text{Exp}(1) ). Additionally, Lemma C.3 and Lemma C.4 imply that the scoring function is a balanced scoring function, and therefore by Proposition 2.6 there is a bijective mapping from strategies of player ( i ) in the CSSP game with balanced scoring function ( S’ ) and strategies of player ( i ) in the CSSP game with balanced scoring function ( S = -\ln(X)/\alpha ), which achieves the same outcome (i.e., the same leader is selected each round) and the same profit for player ( i ). Thus if we can detect any profitable strategy under scoring function ( S ), we can use the same method to detect a profitable strategy under scoring function ( S’ ) since the same strategy is also profitable under ( S ). It is therefore without loss of generality to assume ( S(X, \alpha) = -\ln(X)/\alpha ) for all the analysis that follows. Appendix C contains all the relevant properties of an exponential distribution that we will employ to detect strategic deviation.

3 Statistical Detection Methods for Strategic Deviations

Our paper concerns detection of strategic manipulations in CSSP, so we must first clarify what information is available to the onlooker who wishes to distinguish between the case when all participants are honest (but perhaps suffer latency issues), or a strategic player is manipulating the protocol.

We consider the minimal amount of information necessary for an onlooker just to follow the state of the blockchain: the credentials of the leader from each round.(^8) We will show that this information alone suffices to detect any profitable manipulation in case the strategic player has ( \beta = 0 ).

Before continuing, we briefly note that the ( \beta = 0 ) case corresponds to a “poorly connected” attacker who cannot learn the broadcasts of other players before deciding their own. This matches

(^8)Note that the detection method of [BW24] is tailored to Longest-Chain protocols and in particular looks at the distribution of orphans. As there are no orphans in consensus protocols with finality, we need a fundamentally different detection method.

Useful information for enthusiasts:

Contact me via Telegram: @ExploitDarlenePRO