Computing Optimal Manipulations in Cryptographic Self-Selection Proof-of-Stake Protocols
Matheus V. X. Ferreira, Aadityan Ganesh, Jack Hourigan, Hannah Huh, Seth Matthew Weinberg, Catherine C. Yu · 2024
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%]).