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.

# Overview

- 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.
- The
`leader_election`

function 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
`bookie`

controls stake and randomness.- The
`bookie`

has deposit and withdraw functionalities. We will refer to them as**actions**. - There is a withdrawal delay
`lock_period`

whose length has not been decided yet. Its purpose is to avoid nothing-at-stake scenarios where stake is withdrawn before malicious activity is detected.

- The

A state update of the L1 `core`

contract ensures via proof that L2 block authorship follows the leader schedule.

#
The `leader_election`

function

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`

contract

The L1 `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.

The `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.

# Verifying leader elections in an L1 state update

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 `core`

contract.

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
`core`

contract.

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_election`

function. Specifically, it should prove that each block author is the evaluation of the`leader_election`

at 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_election`

are verified against the`bookie`

contract.

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
`core`

contract) - For each epoch n+1\leq i\leq n+k , action list
`actions(i-3)`

- For each epoch n+1\leq i\leq n+k randomness
`rand(i-2)`

- Inputs from L2:

- The initial stake state corresponding to the state commitment in
`core`

- 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
`rand(epoch)âź¶randomness`

- A mapping
`actions(epoch)âź¶action_list`

Upon state update, the calldata is compared with the information stored in the `bookie`

.

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.

# Randomness

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.

The `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.

# Summary

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 `bookie`

contract.

We look forward to reading your feedback on any aspect of leader elections!