Ledervalg fra Randomness Beacons og andre strategier

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, Offentlige tilfældigheds- og tilfældighedsbeaconsHvor we looked into stand-alone protocols for generating publicly verifiable and unpredictable randomness.) 

Why leader election matters

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 , 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. 

The properties of a good election protocol

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).
• uforudsigelighed: the adversary does not learn the next leader until some time T prior to the leader announcing the next block.
• Entydighed: 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 før 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, foreslog 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 runde 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 tilfældigheds fyrtårn, 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.

Nuværende 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, Er en 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 det første indlæg 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.

Enkelt hemmeligt ledervalg 

Målet Enkelt hemmeligt ledervalg (SSLE) is to select a unique leader from a set of validators while maintaining fairness and unpredictability. Protocol Labs presented the notion as a forskningsproblem, 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, Vis 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 nuntius 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 tilfældigheds fyrtårn, 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 enestående leader. Because the random beacon is built to output uniformly random values, the protocol is also retfærdig: 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 uforudsigelighed.

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, hvori 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*	Entydighed
Runde 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 er forskningspartner hos a16z crypto. Hans forskning fokuserer på anvendt kryptografi og blockchain-sikkerhed. Han har undervist i kryptovalutakurser ved University of Melbourne, NYU, Stanford og Princeton og modtog en PhD i datalogi fra University of Cambridge og BS/MS-grader fra Stanford.

Valeria Nikolaenko er forskningspartner hos a16z crypto. Hendes forskning fokuserer på kryptografi og blockchain-sikkerhed. Hun har også arbejdet med emner som langdistanceangreb i PoS-konsensusprotokoller, signaturordninger, post-kvantesikkerhed og multi-party beregning. Hun har en ph.d. i kryptografi fra Stanford University under vejledning af professor Dan Boneh og arbejdede på Diem blockchain som en del af kerneforskerteamet.

***

Redaktør: Tim Sullivan

***

De synspunkter, der er udtrykt her, er dem fra det enkelte AH Capital Management, LLC ("a16z") personale, der er citeret, og er ikke synspunkter fra a16z eller dets tilknyttede selskaber. Visse oplysninger indeholdt heri er indhentet fra tredjepartskilder, herunder fra porteføljeselskaber af fonde forvaltet af a16z. Selvom det er taget fra kilder, der menes at være pålidelige, har a16z ikke uafhængigt verificeret sådanne oplysninger og fremsætter ingen erklæringer om informationernes vedvarende nøjagtighed eller deres passende for en given situation. Derudover kan dette indhold omfatte tredjepartsreklamer; a16z har ikke gennemgået sådanne annoncer og støtter ikke noget reklameindhold indeholdt deri.

Dette indhold er kun givet til informationsformål og bør ikke påberåbes som juridisk, forretningsmæssig, investerings- eller skatterådgivning. Du bør rådføre dig med dine egne rådgivere om disse spørgsmål. Henvisninger til værdipapirer eller digitale aktiver er kun til illustrationsformål og udgør ikke en investeringsanbefaling eller tilbud om at levere investeringsrådgivningstjenester. Ydermere er dette indhold ikke rettet mod eller beregnet til brug af nogen investorer eller potentielle investorer og kan under ingen omstændigheder stoles på, når der træffes en beslutning om at investere i en fond, der administreres af a16z. (Et tilbud om at investere i en a16z-fond vil kun blive givet af private placement-memorandummet, tegningsaftalen og anden relevant dokumentation for en sådan fond og bør læses i deres helhed.) Eventuelle investeringer eller porteføljeselskaber nævnt, refereret til eller beskrevne er ikke repræsentative for alle investeringer i køretøjer, der administreres af a16z, og der kan ikke gives sikkerhed for, at investeringerne vil være rentable, eller at andre investeringer foretaget i fremtiden vil have lignende karakteristika eller resultater. En liste over investeringer foretaget af fonde forvaltet af Andreessen Horowitz (undtagen investeringer, hvortil udstederen ikke har givet tilladelse til, at a16z offentliggør såvel som uanmeldte investeringer i offentligt handlede digitale aktiver) er tilgængelig på https://a16z.com/investments /.

Diagrammer og grafer, der er angivet i, er udelukkende til informationsformål og bør ikke stoles på, når der træffes nogen investeringsbeslutning. Tidligere resultater er ikke vejledende for fremtidige resultater. Indholdet taler kun fra den angivne dato. Alle fremskrivninger, estimater, prognoser, mål, udsigter og/eller meninger udtrykt i disse materialer kan ændres uden varsel og kan afvige fra eller være i modstrid med andres meninger. Se venligst https://a16z.com/disclosures for yderligere vigtige oplysninger.