PureLottery: Fair Leader Election without Decentralized Random Number Generation

Given n participants, leader election (LE) is the process of designating one of them as the leader or coordinator. LE is ubiquitous in distributed computing and blockchain and has a wide variety of applications ranging from lotteries to proof-of-stake (PoS) protocols and decentralized autonomous organizations (DAOs). In a blockchain setting, we normally require our LE protocol to be decentralized, lead to a consensus about the elected leader, and be fair, i.e. elect each participant with the same probability $1 /n.$ Traditional blockchain LE solutions reduce the problem to decentralized uniform sampling from the set $\{1,2, \ldots, n\}.$ This reduction leads to approaches which are either vulnerable to manipulation, or fail to guarantee fairness, or require inefficient procedures such as verifiable delay functions (VDFs) and publicly-verifiable secret sharing (PVSS), thus making them gas-inefficient and costly when implemented as smart contracts.In this work, we observe that fair leader election can be achieved without explicit decentralized random number generation (RNG). In other words, the intuition behind our work is that RNG is a strictly harder problem than LE. This is because every LE participant is assumed to prefer to be chosen as the leader, e.g. the participant prefers to win the lottery or be the miner for the next PoS block. Thus, they will refrain from actions that would reduce their chance of being selected. This game-theoretic incentive can be exploited to design much simpler protocols for LE in comparison to RNG, by ensuring that dishonest behavior can only reduce the winning chances of the participant.Specifically, we propose PureLottery, a protocol inspired by single-elimination knockout tournaments in sports such as football. We show that PureLottery selects the winner uniformly at random and provides strong game-theoretic guarantees to incentivize honest behavior. PureLottery is also strongly bias-resistant in the sense that every honest participant is guaranteed to win the lottery with probability at least $1 /n$, even if an adversary controls all of the other $n -1$ players. In other words, dishonest behavior will never increase an adversary’s chances of being elected, even if the adversary controls all but one of the participants. Finally, PureLottery is a simple protocol that can be efficiently implemented as a smart contract and uses a small amount of gas in practice. We provide an open-source implementation of the protocol, dedicated to the public domain with no copyright.