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(α, β) on the maximum fraction of rounds a strategic player can lead as a function of their stake α and a network connectivity parameter β. While both their lower and upper bounds are non-trivial, there is a substantial gap between them (for example, they establish f(10%, 1) ∈ [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(α, β) for any desired (α, β) up to arbitrary precision, and implement our method on a wide range of parameters (for example, we confirm f(10%, 1) ∈ [10.08%, 10.15%]).

Cryptographic Self-Selection is a subroutine used to select a leader for modern proof-of-stake consensus protocols. In cryptographic self-selection, each round r has a seed Qr. In round r, each account owner is asked to digitally sign Qr, hash their digital signature to produce a credential, and then broadcast this credential to the entire network. A publicly-known function scores each credential in a manner so that the distribution of the lowest scoring credential is identical to the distribution of stake owned by each account. The user who broadcasts the lowest-scoring credential is the leader for round r, and their credential becomes the seed Qr+1. Such protocols leave open the possibility of manipulation: a user who owns multiple accounts that each produce low-scoring credentials in round r can selectively choose which ones to broadcast in order to influence the seed for round r+1. Indeed, the user can pre-compute their credentials for round r+1 for each potential seed, and broadcast only the credential (among those with low enough score to be leader) that produces the most favorable seed.