owned this note   changed 2 years ago  
Linked with GitHub

Sequencer selection: Fernet

Discussion: "[Proposal] Sequencer Selection: Fernet", Aztec Forum.

Introduction

Fair Election Randomized Natively on Ethereum Trustlessly (Fernet) is a protocol for random sequencer selection. In each iteration, it relies on a VRF to assign a random secret score to each sequencer in order to rank them; each sequencer can then decide to propose a block or not based on their expected rank. Each sequencer proposes just an ordering for transactions.

After the initial phase where sequencers can reveal their scores and block proposals, provers choose which proposal they want to construct a proof for. In the event of multiple submissions, the one from the sequencer with the highest score wins, so provers are expected to flock to the submission with the highest rank, avoiding redundant work. Block proposals provide early confirmations in the happy path, whereas finality is only achieved at the end of a proving phase.

Staking

We require staking STAKE_AMOUNT = equiv 16 ETH on L1 for participating as a sequencer (we will use the notation PARAM = suggested value for any constant in the protocol). Each sequencer registers a public key when they stake, which will be used to verify their VRF submission. After staking, a sequencer needs to wait STAKE_ACTIVATION_WAIT_PERIOD=4 L1 blocks until they can start proposing new blocks. This waiting period prevents a sequencer from trying out multiple private keys until they land a convenient one for the VRF (see Randomness below) and proposing on the same block in which they stake.

Discussion: What to stake? Which currency should we require for staking. Options seem to be ETH, restaked ETH, or a network native token. Using a native token provides some additional defense against takeovers: if an entity purchases enough native token to take over the protocol, then the token value would drop to zero as the protocol utility disappears due to the takeover, and the unstaking delay means the entity cannot dump their tokens before they become worthless.

Unstaking also requires a delay UNSTAKING_DELAY=3days, to allow for slashing of dishonest behaviour. Even though there are no mechanics defined for slashing yet, these can be added later to punish malicious sequencers, or even handled ad-hoc via protocol governance in early stages.

Randomness

We need a verifiable random function to rank each sequencer. We propose a SNARK of a hash over the sequencer private key and a public input, borrowing this proposal from the Espresso team. The public input should be the current block number and a random beacon value from randao.

Alternatively, if EIP 2537 is implemented in Ethereum, we could use a BLS signature using the sequencer's private key, similar to how the consensus layer works.

This random beacon value is needed to prevent sequencers from generating private keys tailored for winning specific blocks in the future. The randao value consumed can be from RANDAO_BLOCKS_AGO=1 L1 blocks ago (see this article for implementation notes), should we want sequencers to know those many blocks in advance their chances of proposing a block. Note that RANDAO_BLOCKS_AGO < STAKE_ACTIVATION_WAIT_PERIOD.

This approach allows each individual proposer to secretly calculate the likelihood of being elected for a given block as soon as the random beacon value is available.

Protocol phases

The protocol is largely divided in two phases: block proposal and proving. Coordination happens in an L1 rollup contract and in the L2 P2P network. We explicitly avoid any coordination on L2 to prevent a sequencer from censoring transactions that will affect an upcoming stage.

Proposal phase

The initial proposal phase lasts PROPOSAL_PHASE_L1_BLOCKS = 2 Ethereum blocks (24 seconds). During this phase, sequencers can submit proposals to L1 for transactions ordering for the next block, which get ranked based on the VRF.

Proposers selection. At the beginning of this phase, each sequencer evaluates their VRF on the next L2 block number, which yields a score known only to them. Since the number of sequencers is known, and assuming a uniform distribution of the hash output, a sequencer can know the probability of being the winner, and decide whether to submit a proposal or not.

Multi-leader election protocols typically work by electing a specific set of leaders, for instance by checking if the VRF modulo a value is zero. This requires careful modeling (and potentially tweaking via protocol upgrades) to nail how many leaders would be probabilistically chosen in each election. Here, having a ranking function for anyone who wants to participate allows for sequencers to quickly iterate different strategies without requriring protocol-level changes.

What is a proposal. A proposal consists of an ordered list of transactions and a reference to the previous L2 block in the chain. We call this an unproven block. Each sequencer who wants to propose an unproven block sends a transaction to an L1 contract including:

  • Their VRF output.
  • The commitment to (ie a hash of) the transaction ordering in the unproven block.
  • The identifier of the previous block being built upon.

Note that the cost of this L1 submission is relatively low. We expect sequencers to adjust their strategies on whether to submit a block or not over time, relying on previous data and on other submissions seen on the mempool, or even leveraging on non-reverting RPC endpoints like Flashbots protect to submit a proposal only if it is the winning one.

The L2 P2P network. Simultaneously, sequencers broadcast through the L2 P2P network the contents of the block and a proof for their VRF. Most transactions would have already been broadcasted through the P2P network, so only the actual transaction ordering and VRF proof need to be propagated. Note that misbehaving sequencers (maliciously or not) may not share the required data on the P2P network, whether it is the ordering of the transactions, their VRF proof, or even the contents of a transaction they have included in the block which is not known to the rest of the P2P network. This leads to indetermined block proposals, as defined below.

Valid and indetermined block proposals. At the end of the proposal phase, any L2 full node can review the unproven block proposals posted to L1. We say a proposal is valid if data is not malformed, the kernel proofs for each transaction are valid, the nullifiers are not repeated, etc. This requires all block data to be available via the P2P network. If this data is not available, we say the proposal is indetermined.

Achieving soft finality. The highest-ranking valid proposal is expected to be next block, so clients can execute the state transition function on it and advance the chain with a soft degree of finality. Note that, since all proposals are required to be posted on L1, clients have assurance that no new proposals will be put forward for a block once this phase ends. Note that indetermined blocks introduce an issue: if the highest-ranking proposal is indetermined, clients cannot know whether it is valid (see the issues section below).

Off-protocol proposer-builder separation. This design leads to out-of-protocol proposer-builder separation. Block proposers, selected at random and running on consumer-grade hardware, could gather blocks from specialised builders through an off-protocol marketplace.

The decision of not enshrining PBS at the protocol layer is an engineering one: ePBS is still an active are of research on Ethereum, subject to frequent changes. It seems improbable that we can push research forward fast enough to come up with a secure design, much less an implementation, within 6 months. Furthermore, having PBS as a sidecar allows us for rapid iteration, and gives the community the flexibility to outright remove it in the event of a critical bug without requiring a major fork.

Once the proposal phase for block N ends, the proving phase for it starts, and the proposal phase for block N+1 starts as well. Sequencers on the proposal phase for N+1 are encouraged to build on the highest-ranking valid block proposal from phase N.

Proving phase

The proving phase lasts PROVING_PHASE_L1_BLOCKS = 50 L1 blocks (10 minutes). This value can be adjusted based on how long we expect the prover network to produce a full proof for a block. During this phase, provers coordinate to build a proof of what they consider to be the next canonical block.

Prover coordination. Out of scope for this proposal. The main requirement is to strike a balance between maximising liveness and minimising redundant effort. Note that provers need to be stateful, since they only see the transaction ordering, meaning they need to actually execute the state transition function to produce the witnesses for the proofs they need to generate. This could be fixed by introducing another actor, a coordinator, that generates the traces and sends them to stateless provers. The sequencer itself could hold this role.

Proof submission. Once a proof for a given block is completed, it can be submitted to L1 for verification, providing a gas rebate to the submitter. The proof must be valid and must refer to a proposal submitted during the corresponding proposal phase in order to be accepted. The VRF proof from the sequencer is included as part of the block proof, possibly on the root rollup circuit, in order to reduce overall verification costs.

Block submission. After a proof has been submitted for a given block proposal, anyone can submit the block contents (without proofs) to L1, ideally as 4844 blobs, with a gas rebate. This is needed to guarantee that all L2 nodes can run the state transition function and advance the chain, otherwise a subset of the network could propose and prove a block without ever revealing it. The block is accepted only if its hash matches the public inputs of an accepted proof. Note that block submission could be batched together with proof submission, for reduced gas costs.

Once the proving phase ends, anyone can finalize the winning block to advance the chain.

Finalization

A last L1 transaction is needed to finalize the current block and pay out rewards. This can be executed by anyone and provides a gas rebate. Once this transaction is mined on L1, the corresponding L2 block is considered final. However, note that the L2 block could still be reorg'd in the event of an L1 reorg.

Canonical block selection. Only the canonical block can be finalized to advance the chain. We define the canonical block as:

  • A block that has been proven during the proving phase.
  • A block whose contents have been submitted.
  • A block whose referenced previous block is also canonical and is at height N-1.
  • The block with the highest VRF score across all that match the conditions above.

Finalizing before the end of the proving phase. As an optimization, the highest-ranking block proposal can be finalized before the end of the proving phase, as long as all conditions for being canonical are satisfied. Any other proposal needs to wait until the end of the proving phase, so the higher-ranking ones have time to submit their proofs.

Skipped blocks. If there are no canonical blocks eligible at the end of the proving phase, we consider this slot to be skipped. The following block N+1 is then expected to be built upon N-1. Note that a skipped block prevents early finalization as described above.

Rewards. Once a block is finalized, rewards are paid out to the sequencer who proposed it, as well as to the provers involved in generating the proof. Rewards should be paid out on L2 to save gas, though could also be managed on L1 directly if the implementation is simpler.

Known issues & mitigations

Indetermined block proposals

A malicious sequencer with the highest-ranking VRF could choose not to reveal the data associated with its proposal, and rely on a private proving network to create its proofs. This would lead to the network as a whole following an incorrect block, only to be reorg'd later when the proof for the indeterminate block is submitted, thus causing provers to waste efforts. The depth of a reorg triggered in this scenario is equal to 1 + PROVING_PHASE_L1_BLOCKS / PROPOSAL_PHASE_L1_BLOCKS = 1 + 50 / 2 = 26 L2 blocks.

Furthermore, seeing a high-ranking VRF may cause other sequencers to not submit their own proposals to avoid wasting gas, even though the gas cost of the proposal is low. This reduces the set of possible blocks at the end of the proposal phase, affecting liveness for that slot if the malicious sequencer never submits a proof.

These problems can be mitigated by providing an uncle block reward of UNCLE_BLOCK_REWARD_PERCENTAGE = 20% to sequencers and provers of proven blocks with a non-winning VRF. Whether this reward is subtracted from the main block or paid via inflation is to be decided. However, the impact to clients who need to account for a large reorg is still present.

Bribing the prover network

Given that sequencers and provers may be separate agents in the network, it is possible that provers choose not to prove the highest-ranking proposal if there is an incentive for them to prove a different one. A secondary market could arise where non-winning (as in VRF) sequencers include a tip to provers to pick their proposal over the winner.

This could lead to the highest-ranking proposal never being proven during the proving phase, and another block being picked as the canonical one. This requires that most provers in the network choose to follow the bribe as opposed to the VRF score, so that the highest VRF does not get enough provers to be proven by the end of the proving phase.

B52 enshrines this in the protocol by explicitly including the fee split in the block proposal, and using it as a basis for proving voting which leads to block selection.

This does not affect liveness, but it does complicate the early-finality choice for clients, who can no longer rely on the highest-ranking valid proposal being finalized as the canonical one. Nevertheless, as long as bribes are public, clients can update their early-finality choice to mimic that of provers, mitigating this issue.

It is also possible that this issue can be mitigated by the prover network itself. For instance, if only a subset of provers is "elected" to work on the highest-bribe block, then the ones left out can choose to work on the highest-VRF one and capture its rewards.

Alternative design decisions

Replace staking with balance snapshots

Instead of staking, a snapshot of balances in a previous slot can be used to rank sequencers, as explored in Schmequencer.

This approach is simpler, since it doesn't require a separate staking infrastructure, and also more capital-efficient. On the other hand, using balances may lead to unexpected delegations: if a user locks funds in a 4626-like vault, they are unwittingly delegating their sequencing power to that vault. It also depends on L2 state, whereas by relying on staking on L1, consensus logic is managed exclusively there. Also, staking allows us to implement slashing, which is not doable with balances since they can be moved around.

Introduce a DA layer

We can remove indeterminate blocks by including a data availability layer into the protocol. Along with their commitment to L1, sequencers are also required to submit a data availability proof for the contents of the block, including the individual proofs for each transaction. Thus, any L2 node is guaranteed to have access to the data needed to verify whether a block is valid or not, reducing the risk of reorgs.

However, more research is needed to determine if there is a valid DA layer that fits the requirements. We estimate that the proof size for each tx could be up to 32kb, so even 4844 blobs are impractical.

Batch multiple proposals per proof

Instead of starting a proving phase at the end of each proposal phase, we can batch PROPOSALS_PER_PROOF proposals into a single proof. This trades latency for reduced verification and prover coordination costs.

Another negative effect of increasing the time to finalization is that reorgs caused by indeterminate blocks grow larger. The reorg depth in this scenario is increased by PROPOSALS_PER_PROOF L2 blocks.

However, batching also allows us to reduce the length of the proposal phase by subdividing it. Instead of having a single proposal phase per proof that lasts PROPOSAL_PHASE_L1_BLOCKS L1 blocks, we can have two proposal phases that each last PROPOSAL_PHASE_L1_BLOCKS / 2 blocks aggregated into a single proof. This yields the same overall time to finalization and also provides earlier soft confirmations for clients, at the expense of higher proposal phase coordination costs.

Appendix

Gas costs

  • Block proposal: A block proposal to L1 requires a commitment to the transaction ordering, a reference to the previous block, and the VRF output. Storing these three values, along with the sender address, requires 4 SSTORE operations. Using rolling storage slots (so each SSTORE requires 5k gas instead of 20k), the total cost would be around 40-50k gas. We expect no more than 5 proposals per block.
  • Proof submission: Cost of submitting and validating a proof for a block. This value is to be determined, but is the same regardless of the sequencer selection algorithm. This value can be amortized by batching together multiple blocks into a single proof.
  • Block submission: Cost of submitting the block contents to 4844 blobs. Without any compression, this is roughly 700 bytes (700 blob-gas) per transaction, plus a constant cost of about 600 bytes for the header.
  • Finalization: Stores the canonical block identifier for the current height and triggers rewards payouts. Assuming payouts happen on L2, the cost should be driven by a single SSTORE and a few SLOADs, thus not exceeding 30-40k gas.

Resources

Select a repo