Leader Election from Randomness Beacons and Other Strategies

Leader election in a blockchain setting aims to select the participant who will determine the next block to be appended to the blockchain. Typically, one validator is chosen per slot from the set of validators and gets the right to extend the chain with a new block in that slot. (We assume that validators keep accurate time and agree on the current slot number.) In this article we explore strategies for randomized leader election in consensus protocols. (For more on randomness generally, see our earlier article, Public Randomness and Randomness Beacons, where we looked into stand-alone protocols for generating publicly verifiable and unpredictable randomness.) 

Electing honest and active leaders is crucial for the healthy growth of the chain. Malicious validators should not be able to bias the leader election process to make themselves leaders more frequently. Otherwise, the production of blocks could fall into the hands of parties who can censor transactions or halt the blockchain altogether. In longest-chain-style consensus protocols, a leader producing an invalid block (or no block at all) could cause the chain to temporarily fork. In BFT-style consensus protocols, a bad leader triggers a view-change subprotocol that will incur a communication overhead. 

The committee election alternative

Committee election is a related problem, where the goal is to select a uniformly random subset of the validators of some fixed size k. This functionality is useful in its own right because subcommittees are often needed in blockchain settings to reduce the validator set size to make consensus run faster (among many examples are Algorand’s sortition and Ethereum’s committee selection). But committee election is also useful for leader election, allowing the validators to avoid re-running a leader election protocol if the elected leader fails to show up. If, instead of a leader, a committee is elected with a fixed ordering, the second committee member can become leader if the first is not available. 

In a leader election protocol, the leaders should be unpredictable. If an attacker learns who the upcoming leader is, it might launch a Denial of Service (DoS) attack on them to prevent them from publishing a block. The attacker could then take down the next leader and so on, bringing the blockchain to a halt. Unpredictability might also be strengthened to ensure the validator itself does not learn when it is going to lead, which might be important for bribery prevention.

The leader election process should have the following three properties:

• Fairness: each honest validator has a probability of 1/N to be elected from a set of N validators (a relaxed notion of game-theoretic fairness allows building leader election even in the presence of a malicious majority albeit with a non-constant lower bound on the number of rounds).
• Unpredictability: the adversary does not learn the next leader until some time T prior to the leader announcing the next block.
• Uniqueness: exactly one leader is chosen in each slot.

Secret leader election

Secret leader election is an unpredictable election with T = 0. In this process, the leader is not known to anybody until it publishes the block. This eliminates the window for a DoS attack completely: before the leader reveals itself, the attacker does not know whom to attack, making its best strategy a random guess. And after the leader publishes its block, it is too late to attack because the leader has already fulfilled its responsibility to the protocol.

The notion of “after the leader publishes its block” is actually a simplification though, because  we don’t have instantaneous broadcast in the real world. An attacker with a strong network position might notice a leader broadcasting a block first and be able to quickly corrupt the leader, create a different block, and front-run the original broadcast.

While this is a very strong attacker model, defenses have been proposed against it. Algorand proposed the erasures model, in which the leader is actually able to erase the key necessary for signing the block in its slot before broadcasting it, so it really is too late to attack by the time the leader takes any public action. Thaddeus Dryja, Quanquan C. Liu, and, Neha Narula, three researchers from the MIT Media Lab, proposed that the leader compute a VDF on its block before broadcasting, ensuring that an adaptive attacker cannot construct an alternate valid block in time to have it accepted for the desired slot.

Other election methods 

The simplest leader election process is round-robin, where leaders are elected in deterministic order. Despite this approach being predictable and thus being prone to DoS attacks, it is suitable for permissioned systems where the validators have good DoS protection.

A leader can also be elected using an output of an external randomness beacon, if one is available and trusted to be secure. Unfortunately, it is tricky for the consensus participants to run a distributed randomness beacon (DRB) protocol themselves, since these typically assume a notion of reliable broadcast or consensus, which in its turn requires leader election again, introducing  a circular dependency.

Current leader election in Ethereum is a good case study. Each new leader computes a Verifiable Randomness Function (VRF) output (a BLS signature on the epoch number) and XORs the value into the mix. The value of the mix at the end of epoch i defines the leaders and the subcommittees for the duration of epoch i+2. Leaders and their schedule are predictable one epoch in advance (currently ~6.4 min). The protocol is prone to fairness attacks, as the last leader may choose to publish or withhold their contribution to the mix and thus influence the result of the next elections by one bit. If the last  k leaders collude, they may introduce k  bits of bias and make the election of malicious users more likely. The Ethereum Foundation is actively working on more advanced techniques for  leader election that we discuss below.

VRF-based leader election

Another approach, pioneered by Algorand, is a VRF-based leader election, which involves each validator privately computing a VRF output and checking whether the output falls below a threshold. This procedure already filters out most of the validators, since the threshold is chosen such that falling below it is unlikely. The few remaining validators reveal their VRF outputs, and the one with the lowest VRF value is elected. This approach achieves perfect unpredictability (or secrecy), but it does not guarantee uniqueness. Some of the validators might not receive messages from all of the potential leaders and might assume the wrong leader won the election, causing these validators to fork from the main chain.

The VRF evaluation is periodically seeded with the output of a randomness beacon to make it less predictable for the validators themselves to see which slots are they going to lead. This property prevents an attacker who silently compromises the validator from learning the slot when the validator would become a leader and launching an attack when the validator is about to announce a block. This approach also helps prevent bribery attacks, where a validator proves to external parties that it will be a leader in a particular slot and harvests bribes in exchange for completing some task as leader (e.g., blocking a transaction).

Such approaches, where the number of leaders elected is a random variable, are called Probabilistic Leader Election (PLE). PLE can result in no leaders being elected for a given slot. This is equivalent to electing a leader who is malicious or offline in that the slot will ultimately end up being skipped, reducing efficiency of the consensus protocol.

But the largest caveat with PLE is that multiple leaders might be elected, necessitating some sort of tie-breaking procedure. Ties pose a risk to consensus, since a validator with a winning input may report it to only half of the network, potentially causing disagreement in the chosen leader. Furthermore, processes for resolving ties can take extra time and communication, hurting efficiency. Dfinity, discussed in more detail in the first post of this series, uses a VRF-based randomness beacon to elect a single leader; however, it sacrifices unpredictability to do so. Ideally, any process for picking a leader should avoid ties entirely and still be unpredictable, which leads us to the holy grail of this research area – Single Secret Leader Election.

 

The goal of Single Secret Leader Election (SSLE) is to select a unique leader from a set of validators while maintaining fairness and unpredictability. Protocol Labs presented the notion as a research problem, and Dan Boneh, the Stanford computer scientist and a16z crypto research advisor, with Saba Eskandarian, Lucjan Hanzlik, and Nicola Greco, later offered a formal definition of SSLE. This uniqueness property avoids the consensus risks and efficiency costs arising from tie-breaking procedures. Concretely, Sarah Azouvi, of Protocol Labs, and Danielle Cappelletti, of Politecnico di Torino, show that when SSLE is used compared to PLE in a longest chain protocol, blocks can be finalized significantly faster (25 percent faster with an adversary controlling a third of the stake). Thus, developing a practical SSLE protocol is an important problem.

In the most common approach, which we’ll call shuffle-based (used in both the original SSLE paper and an Ethereum SSLE Proposal), each validator registers a nonce that looks random, yet that they can prove belongs to them. The nonces are then compiled into a list. The list is shuffled such that the nonces become unlinked from the validators who submitted them; that is, given the shuffled list, no adversary can tell which validator submitted which nonce. A list index is then chosen according to a public randomness beacon, and the leader reveals itself by proving that the nonce at that index of the shuffled list belongs to them.

Since only one index is chosen, the shuffle-based protocol always outputs a unique leader. Because the random beacon is built to output uniformly random values, the protocol is also fair: each validator has an equal chance of being elected. Furthermore, if the shuffling is done properly (i.e., uniformly at random) and the nonces become unlinkable to the validators’ identities, this protocol also achieves unpredictability.

Shuffling is necessary because while simply choosing an index from the unshuffled list based on a random beacon would already give uniqueness and fairness, unpredictability is harder to achieve: If an adversary knows which validator submitted which nonce, it knows who submitted the nonce at the chosen index and can identify the leader.

These following two approaches shuffle the list in different ways. The simpler is the Ethereum SSLE Proposal, in which n validators submit their nonces via Tor to unlink the validators’ identities from their nonces. Once all validators have registered, the list is shuffled using a public randomness beacon, and the validators become leaders in the order of the shuffled list. While this scheme is practical – the election must be run only once per n slots – this reliance on Tor may be undesirable (as is the case with relying on the security of any outside protocol). Furthermore, it is not perfectly unpredictable: after the first n-1 leaders reveal themselves, the final nth leader is known.

Instead of using Tor, the original SSLE paper has every validator register for election in sequence by appending its nonce to the list, shuffling the list, and re-randomizing the nonces. This re-randomization means that each nonce is mapped to a new, unlinkable string such that the validator who it belongs to can still prove ownership of the re-randomized nonce. Re-randomization makes it so that an adversary can’t tell which position any particular nonce ended up in after the shuffle, assuming at least one shuffler is honest.

While this sequential shuffling approach from the original SSLE paper avoids reliance on Tor and achieves the formal properties of SSLE, it is expensive: whenever a new validator registers, they must post the entire shuffled list to the blockchain, re-randomize all nonces, and provide a proof that they did so honestly, which results in linear amount of communication per validator. With an unchanging set of validators, this must be done (amortized) once per election, as the leader re-registers once they have revealed the proof for the nonce. The paper gives a tunable efficiency-predictability tradeoff: we can instead shuffle only a smaller subset of the list, reducing cost, if we’re willing to allow a small amount of predictability. Achieving a good balance between efficiency and security is challenging, and as a result, SSLE protocols are yet to be used widely in practice.

Conveniently, this sequential shuffling approach also can be used to solve the committee election problem, by using the random beacon to choose k distinct indices from the list as committee members. This is a nice achievement, as the problem is not trivially solved by VRF-based approaches, since running a probabilistic VRF-based protocol k times may elect a varying committee size depending on the randomness. 

Other approaches to SSLE

Another shuffle-based approach is Adaptively Secure SSLE from DDH. This construction is slightly more complicated but achieves a stronger notion of security, protecting against an adaptive adversary in Algorand’s erasures model. This adversary is adaptive in that it can choose which validators to corrupt during the protocol, as opposed to before the protocol starts.

A further challenge in SSLE is electing each validator with probability proportional to their stake, rather than uniformly at random. Shuffling-based protocols can naively achieve this by allowing each validator to register multiple nonces: one nonce for each unit of stake they hold. However, the cost of shuffling increases linearly with the number of units of stake S, becoming very expensive even for realistic stake distributions. An elegant MPC-based SSLE approach has complexity increasing only with log S, and it also avoids the need for a trusted setup or randomness beacon. However, compared to shuffling-based approaches, it requires more rounds of communication (logarithmic in the number of participants) per elected leader

***

We’ve summed up our analysis in this handy table.

	Fairness	Unpredictability/ Secrecy*	Uniqueness
Round-robin	✓	✗	✓
Ideal randomness-beacon	✓	✗	✓
Ethereum’s leader election (current)	✗	✗	✓
VRF-based leader election (Algorand)	✓	✓	✗
SSLE	✓	✓	✓

* The round-robin beacon is fully predictable, but in the rest of the beacons ✗ means that the notion is achieved up to a certain limited degree: ideal-randomness beacon is unpredictable but the adversary learns the output at the same time with the elected leader, hence the elected leader may be attacked before it announces a block; Etherum’s beacon is unpredictable up to ~6 min and can be slightly biased to hurt fairness; Algorand elects multiple leaders with a small probability.

SSLE is a promising direction, achieving fairness, unpredictability, and uniqueness. Two prominent challenges facing its adoption are efficiency and the ability to accommodate non-uniform stake distributions. Furthermore, the shuffle-based SSLE approaches that we highlight assume the existence of an unbiased random beacon, which is not straightforward to achieve in practice. As SSLE has only recently been formally defined, we’re likely to see improved protocols addressing its challenges in the near future.

***

Miranda Christ is a PhD student in Computer Science at Columbia University, where she is a member of the Theory Group and a Presidential Fellow. She is also a research intern at a16z crypto.

Joseph Bonneau is a Research Partner at a16z crypto. His research focuses on applied cryptography and blockchain security. He has taught cryptocurrency courses at the University of Melbourne, NYU, Stanford, and Princeton, and received a PhD in computer science from the University of Cambridge and BS/MS degrees from Stanford.

Valeria Nikolaenko is a Research Partner at a16z crypto. Her research focuses on cryptography and blockchain security. She has also worked on topics such as long-range attacks in PoS consensus protocols, signature schemes, post-quantum security, and multi-party computation. She holds a PhD in Cryptography from Stanford University under advisorship of Professor Dan Boneh, and worked on the Diem blockchain as part of the core research team.

***

Editor: Tim Sullivan

***

The views expressed here are those of the individual AH Capital Management, L.L.C. (“a16z”) personnel quoted and are not the views of a16z or its affiliates. Certain information contained in here has been obtained from third-party sources, including from portfolio companies of funds managed by a16z. While taken from sources believed to be reliable, a16z has not independently verified such information and makes no representations about the current or enduring accuracy of the information or its appropriateness for a given situation. In addition, this content may include third-party advertisements; a16z has not reviewed such advertisements and does not endorse any advertising content contained therein.

This content is provided for informational purposes only, and should not be relied upon as legal, business, investment, or tax advice. You should consult your own advisers as to those matters. References to any securities or digital assets are for illustrative purposes only, and do not constitute an investment recommendation or offer to provide investment advisory services. Furthermore, this content is not directed at nor intended for use by any investors or prospective investors, and may not under any circumstances be relied upon when making a decision to invest in any fund managed by a16z. (An offering to invest in an a16z fund will be made only by the private placement memorandum, subscription agreement, and other relevant documentation of any such fund and should be read in their entirety.) Any investments or portfolio companies mentioned, referred to, or described are not representative of all investments in vehicles managed by a16z, and there can be no assurance that the investments will be profitable or that other investments made in the future will have similar characteristics or results. A list of investments made by funds managed by Andreessen Horowitz (excluding investments for which the issuer has not provided permission for a16z to disclose publicly as well as unannounced investments in publicly traded digital assets) is available at https://a16z.com/investments/.

Charts and graphs provided within are for informational purposes solely and should not be relied upon when making any investment decision. Past performance is not indicative of future results. The content speaks only as of the date indicated. Any projections, estimates, forecasts, targets, prospects, and/or opinions expressed in these materials are subject to change without notice and may differ or be contrary to opinions expressed by others. Please see https://a16z.com/disclosures for additional important information.