In the previous post we remarked the Starknet consensus protocol will be turn-based: time will be divided into slots and each slot will have a unique leader. This post describes a suggestion for a leader election protocol modeled on an epoch-based public lottery. The remainder of the consensus protocol is abstracted away and will be treated separately. In particular we do not treat rewards or incentives.
We begin with an overview of the protocol and a brief discussion of the
leader_election function. Next we dive into the protocol components, and end with some remarks on randomness.
- The protocol is epoch based – time is divided into epochs which are in turn subdivided into slots; there is one Starknet block per slot. A Starknet epoch will be 5-10 minutes in real-time as measured by L1 block timestamps. Thus L1 divides all of time into roughly equal 10 minute intervals. A Starknet slot will be at most 10-15 seconds. These numbers are not final and may-well end up smaller.
- To promote agreement, the leader schedule for epoch(i) is determined at the end of epoch(i-2) with epoch(i-1) acting as a synchronization period. This assumes L1 transactions are included in the ledger within 1 epoch.
leader_electionfunction receives an epoch’s randomness and stake distribution as parameters; it takes a slot to a unique slot leader based on the stake and randomness. This function is common knowledge and can be calculated off-chain without sending Ethereum transactions.
- Randomness comes from L1 and should be renewed once per epoch for unpredictability. The trigger will be part of the decentralized protocol, with a frequency of several minutes. If randomness is not renewed, old randomness will be recycled. We’ll leave this point for last.
- The leader schedule for epoch(i) only considers the stake distribution at epoch(i-3). This is to ensure that randomness for epoch(i), which is sampled at epoch(i-2), is not known to depositors.
- An L1 staking contract
bookiecontrols stake and randomness.
bookiehas deposit and withdraw functionalities. We will refer to them as actions.
- There is a withdrawal delay
lock_periodwhose length has not been decided yet. Its purpose is to avoid nothing-at-stake scenarios where stake is withdrawn before malicious activity is detected.
A state update of the L1
core contract ensures via proof that L2 block authorship follows the leader schedule.
As remarked above, the
leader_election function receives an epoch’s randomness and a stake distribution as parameters; it takes a slot to a unique slot leader based on the stake and randomness.
We went with a simple leader election function: flatten each user’s stake to an interval, concatenate the intervals, and randomly choose a point. The leader is the “owner” of this point. This description requires us to specify exactly how we order stakers. We propose the lexicographic order on addresses.
bookie is Starknet’s staking contract. Its primary goal is to facilitate staking, namely entering and leaving the participant list of Starknet’s leader election protocol. Our design aims to make the leader schedule easy to calculate and efficient to prove. The
bookie contract has four roles:
- Provide deposit/withdraw functionality for stakers.
- Store current stake distribution and pending actions for calculating current and upcoming leader elections.
- Store randomness (current and historical) for calculating/verifying current and historical leader elections.
- Store some historical data to cheapen the verification of historical leader elections. Specifically, the contract stores a list of actions for each epoch.
bookie fulfills its first two roles by storing at each time the current stake distribution, alongside some functions which facilitate deposits and withdrawals. Withdrawals involve a “lock period” to avoid nothing-at-stake scenarios.
The third role of the
bookie is fulfilled through a mapping
rand(epoch)⟶randomness which takes an L2 epoch to its associated randomness.
The final role of the
bookie is fulfilled through a mapping
actions(epoch)⟶action_list which takes an L2 epoch to the list of actions performed during it, e.g deposits and withdrawals. Actions facilitate easy computation of past stake distributions with less storage, and also without need for historical data. The verification mechanism is detailed below.
This section describes how the L1
bookie contract is used alongside proofs to verify past leader elections as part of Starknet’s L1 state update in the
Before diving in, let’s give a rough outline of current Starknet state updates. We want to verify two things:
- The submitted proof is valid, i.e the state transition in question is valid.
- The initial state that was input to the off-chain proof computation actually coincides with the state of Starknet recorded in the L1
Since proof verification is stateless, the second item is what ties the proof to the current state of Starknet. Note the proof computation is off-chain, so the initial state supplied for the proof can be arbitrary. We compare it to the actual state commitment on L1 to avoid such arbitrary state updates.
Our focus is on Starknet state updates which account for the leader schedule. This introduces an additional complication: the randomness and stake distribution are stored on L1, so this part of the Starknet state lives on L1 and changes independently of the L1 state update transactions. Proofs of leader elections must account for intermediate changes in this part of the state in the same way they account for messages from L1. In summary, the verification of leader elections in an L1 state update checks two statements:
- The proof should prove that each block author in the sequence of blocks is correct according to the
leader_electionfunction. Specifically, it should prove that each block author is the evaluation of the
leader_electionat the corresponding slot using the randomness and stake distribution described in the state (starting from the initial state, and accounting for possible changes on L1).
- The randomness and stake distribution in the proof’s initial state and intermediate states (!) are consistent with the information on L1. That is, the inputs of the
leader_electionare verified against the
Before elaborating, let us describe a trick to reduce calldata (and consequently reduce costs) for the second item above. To illustrate, imagine a proof of a single block. In the naive approach, the proof is submitted to L1 alongside the resulting state (following the block’s execution). The trick is to only submit the proof alongside state-diffs, i.e the changes in the state caused by the block’s execution. This avoids the redundancy of specifying unchanged parts of the state, but at the cost of “spreading out” the state over L1 history. In our context, the trick amounts to sending proof alongside calldata which only describes intermediate L1 staking actions.
Now we can formalize the above discussion. A proof of leader elections for epochs n+1,\dots n+k is computed with respect to inputs from different places:
- Inputs from L1:
- Initial state commitment (in L1
- For each epoch n+1\leq i\leq n+k , action list
- For each epoch n+1\leq i\leq n+k randomness
- Inputs from L2:
- The initial stake state corresponding to the state commitment in
- A sequence of Starknet blocks for the epochs in question (alongside each block’s author)
The L1 verification of the proof (which is stateless) ensures that block authors are indeed output by the
leader_election function. To ensure the correctness of the inputs (from L1) to the
leader_election function, we must compare them to information on L1. To this end, the proof is appended with calldata in the form of:
- A mapping
- A mapping
Upon state update, the calldata is compared with the information stored in the
Having verified the inputs to the proven
leader_election computations, we are now convinced of the validity of state transition with regards to the leader schedule.
In summary, we have described how a Starknet L1 state update transaction verifies leader elections using reduced calldata from the state update transaction.
As far as we’re concerned, Ethereum’s randomness is of sufficient quality for Starknet. Consequently we will not pursue enhancements such as VDF and/or VRF constructions.
bookie stores randomness in the aforementioned mapping
rand(epoch)⟶randomness. Updating the randomness requires someone to initiate a transaction. Part of the decentralized protocol will be used for such updates. This raises the question of what happens if nobody sends a randomness update transaction in a certain epoch. The simplest answer is to always use the most recent randomness. In this case, the leadership schedule can be predicted just from actions involving the stake. We may slightly refine the randomness R, so that the actual value input to the
leader_election function is a derivative of the latest randomness, e.g by saying the derivative for epoch(i) is R(i)=H(R,i). In this case, the schedule will continue to change even in case of a static stake distribution.
This post described a concrete suggestion for an epoch-based public lottery protocol for leader elections in Starknet. The leader schedule can be derived from L1 data, namely randomness and staking actions stored in the permissionless L1
We look forward to reading your feedback on any aspect of leader elections!