[Proposal] Sequencer Selection: B52 — PBS with a federated prover network

[jaosef]

Sequencer Selection Proposal: PBS with a federated prover network

Summary

This proposal for sequencer selection uses concepts from MEV Auctions and Sequencer Auctions and PBS to remove the need for a cryptographic sequencer selection process for zkrollup L2s.

Instead, the proposal describes an economic algorithm, administered by an Ethereum smart contract on L1. Communication is facilitated by the gossip network of the L2.

Goals:

1. Separate block building from proving.
2. Ensure that no single actor controls the network.
3. Reduce infrastructure centralisation by incentivising many provers.
4. Facilitate MEV auctions.
5. Ensure that provers know which block to build proofs for, ahead of time.
6. Simple to build and audit.

Details

This proposal assumes the following:

1. Users pay transaction fees on L2 and there is extractable MEV on the public part of their transaction on the L2. The winning block proposer receives the fees and can extract MEV from ordering.
2. A successful proposer pays for the right to extract MEV by burning native tokens.
3. For each block, there is a valid zero-knowledge proof validating all state transitions and transactions. This proof is verified on L1.
4. Provers stake native tokens for the right to prove.
5. There is a block reward paid in native tokens to the winning block and to N uncle blocks.
6. For each proposed block, the proposer decides a percentage of the block reward that will be paid to provers, pro-rata to their contributions in the block.
7. The winning block is determined by ranking proposal on a smart contract with two factors:
   • the amount the proposer is willing to burn.
   • the number of provers who contributed to a block.

Lifecycle of a block

Block Proposal Window

Block proposing, block voting and block commitments occur during the BLOCK_PROPOSAL_WINDOW. This window lasts M seconds after the last rollup block was confirmed on L1.

Phase 1: Block proposal

A proposer orders pending transactions from the mempool into a block. A proposal consists of:

1. A commitment to the order of transactions in the block (a random secret is used as this will be revealed later).
2. The % of the block reward that the proposer will give to the provers (ratable to their contributions in the block)
3. The amount of native token that the proposer is willing to burn for the block.

A proposal is sent to the L2 gossip network.

Phase 2: Block Voting

Provers (who have previously staked) vote for the blocks that they will construct proofs for.

Economic incentives suggest that they will likely pick based on the most profitable proposals, based on the % of the block reward they will receive.

A vote consists of:

A signature over
1. The block hash 
2. The index of the binary proof tree they will make e.g `Depth 10:Index 4` 

Provers broadcast this intent to the L2 gossip network. They will likely broadcast multiple intents, for multiple parts of the block and different blocks.

If a prover does not submit a proof after declaring their intent to do so, they can be slashed.

Phase 3: Aggregation

The block proposer assembles block votes into a block transcript, detailing which provers will create which part of the proof tree from the available votes on the L2 gossip network.

The proposer commits the block transcript to L1 via an Ethereum transaction.

A block will become the head of the chain if BOTH the following conditions are met:

1. A valid proof is submitted to L1 within the PROOF_ACCEPTANCE_WINDOW (M seconds after the end of the BLOCK_PROPOSAL_WINDOW);

AND

2. It has the highest score for the current block height:
   • SCORE(y) = NUM_PROVERS (x)^3 * BURN_BID(z) ^ 2 – needs modelling

As the NUM_PROVERS is cubed, the proposer will try to create a block transcript with a very diverse prover set, in an effort to maximise their score and win the block reward, fees, and right to extract the MEV.

The proposer could also opt to burn more native token, but this will be less profitable.

Plot of the relationship between provers and burn.

In an effort to ensure the number of provers is greater than a TARGET_PROVERS, the surface could be updated per block, much like the gas prices / burn in EIP-1559.

Dynamically updating the slope would ensure that the cost for a small set of provers to sustain any censorship attack would increase with each block.

Block Acceptance Window

Phase 4: Proving

Once the block proposal window ends, a proposer will reveal the contents of a block to the L2 gossip network. Provers can look up high ranking blocks on L1 via the smart contract and start building any assigned parts of the proof tree.

Example Proof Tree

Note: Aztec is targeting a block size of 2^14, or 16,384 txs, so in this example, with each prover computing a 2^3 tree, there would be 2,048 provers.

Completed proofs are submitted back to the L2 gossip network, so they can be built on top of for higher levels of the proof tree. Provers are incentivised to contribute proofs back to ensure that the block is created and they get paid.

The MergeRollup circuit must aggregate provers public keys at each level of the tree by verifiying the prover transcript, and expose this as a public output.

Phase 5: Proof Submission

Proof submission must occur within the PROOF_ACCEPTANCE_WINDOW

Within the window, the proposer (or anyone else) can submit a completed block proof to the rollup contract. Submitting a proof will do the following:

1. Verify the proof
2. Rank the proposal on the rollup contract by its score
3. We will need to store a reference to the messages that need processing for any L1 > L2 messages, and process these once a block is picked.

State Advances

Once the PROOF_ACCEPTANCE_WINDOW has ended, anyone can finalise the current set of proof submissions and advance the block state to the winning block. This is achieved by calling a function on the L1 contract.

Fees are dispersed as follows:

1. The highest scoring block becomes the head of the chain
2. Fees get paid to the proposer of the winning block
3. The block reward gets paid to the proposer / provers in the agreed split.
4. Provers that contributed to any uncle blocks split an uncle block reward pro-rata.

Diagram

Staking

Provers must stake N native tokens to participate in block production. Every prover who contributes to a block gets paid a pro-rata % of the block reward.

Slashing

A prover can be slashed if they commit to producing part of a proof, but don’t.

Slashing occurs on L1, out of the prover’s stake.

The L1 smart contract knows (from the block transcript) who agreed to produce a block. This can be compared to the set of provers in the accepted proof that actually produced the block. This is the basis for a slashing algorithim.

There are two issues here:

What if the proposer tries to slash the prover by not including their proof?

Remedies:

1. Allow a prover to submit their proof directly to L1 within a time window to reverse a malicious slashing.
2. Implement slashing as a rate, so it effects the provers future ability to with-hold a proof.
3. Add a mechanism to incentivise inclusion of proofs
   • e.g if 100 provers attest but the proposer only includes proofs made by 55, the block rewards would be 55% of total rewards.

What if the prover tries to DDOS the proposer by not creating a proof?

1. The prover will be slashed so this attack is costly.
2. Allow non committed proofs to be included. The reward payout will be lower in this situation, but the block will succeed.

How does a prover know which block to prove?

During the voting and proposing stage, the L2 gossip network will make available a list of the current proposals and the current votes for each by provers.

In the PROOF_ACCEPTANCE_WINDOW, the provers can read the committed blocks from the L1 Rollup contract, and only prove blocks they think will win.

Redundant prover work

This proposal incentivises redundant prover work. This is a deliberate choice to ensure that the prover network is diverse and that blocks can always be produced.

There are scenarios where it may not be profitable to submit a block for the proposer of a proved block that does not win.

However, as it is not guaranteed that other proposers will submit a proof for their block in the PROOF_ACCEPTANCE_WINDOW, it is likely a proposer may gamble and submit.

Other Questions

What stops a proof being taken and used in a different block proposal?

Proofs are signed and committed to in advance. Inside a proof, a signature verification will occur. A nullifier could also be generated here that includes secret information from the committed prover to stop a proof being re-used.

What happens if no proofs are submitted?

If no proofs are submitted in the PROOF_ACCEPTANCE_WINDOW, the network will restart the BLOCK_PROPOSAL_WINDOW from the point in time that the first proposal is submitted.

Feasibility

This proposal does not require any new cryptographic primatives and is entirely administered on L1 via a smart contract. This means it is easy to build and audit.

The hardest components to architect are:

1. How does a prover select which parts of the proof tree to vote on. (Likely they will just select all)
2. How does a proposer select provers and do they track prior performance?
3. How does L1 / L2 messaging work.
4. Small changes to the merge rollup circuits, but these are not large changes.
5. As staking occurs on L1, it will likely require a storage proof in each root rollup to prove each prover is a valid prover.
6. Simulations to establish the trade offs of different BLOCK_PROPOSAL_WINDOWS and PROOF_ACCEPTANCE_WINDOWS, as well as the number of provers vs burn.

Requirements

Decentralization:

Sequencer selection must be sufficiently sybil resistant

Sequencer selection should not prioritize the best hardware or largest actors

As this proposal has PBS, it is likely that the actor who can extract the most MEV from the current transaction pool, may be a large actor as MEV simulations are computational intensive. However for this actor to win, they must pay the proving network fairly, and could lead to a more efficient network.

Hardware requirements for sequencers must be similar to those of Ethereum validators

Liveness:

Network participants must know in advance who the sequencer is for a given time slot

A rollup should be created in every given slot to reduce network latency even in periods of low transaction activity

This proposal accepts a period of network down time during BLOCK_PROPOSAL_WINDOW to facilitate coordination and liveness. Other proposals that run SSLE protocols will not face this downtime, but come with different trade offs.

To mitigate this, the BLOCK_PROPOSAL_WINDOW can be on the order of seconds. e.g on Ethereum, MEV Boost is able to propose blocks in sub 15 seconds.

The exact values chosen will need to be simulated.

Downtime can be further mitigated by allowing the proposer to specify a block hash, from which block proposal builds from.

The BLOCK_PROPOSAL_WINDOW would then start at the same time as the start of the PROOF_ACCEPTANCE window of the last confirmed rollup block, ensuring zero downtime.

Censorship Resistance:

Ensure the sequencer selection process is censorship resistant

The economic value of winning a block increases with network activity. A dishonest actor must pay more than an honest actor in this proposal to halt the entire network, which is unfeasible to maintain.

However, the cost to censor a single transaction is significantly less.Here a dishonest actor can just forgoe the fees associated with that transaction to censor. Forgoeing these fees every block would add up over time, so this attack is costly, and more of a delay than a full censorship.

Should this be an issue, censorship resistance can be further improved by adding Include Lists on L1 to allow users to force a transaction to be included.

Ensure transaction inclusion from a particular sequencer is censorship resistant

Privacy:

Should allow sequencers the option of anonymity during selection and block submission

This proposal will need to be tweaked slightly to afford better privacy to network participants.

Currently:

1. Provers must have public identities to stake / be paid rewards / vote
   • Identities can be setup with fresh accounts
2. Proposers need public identities to commit to blocks and get paid. The proposal could be tweaked to allow others to submit completed blocks for privacy.

Other Considerations

Separating ordering and block building from execution

Using L1 versus L2 for the sequencer selection protocol

Proposer-builder separations

The good bits

1. Proposer builder separation reduces censorship risk due to global regulatory differences, and helps with MEV mitigation.
2. Sophisticated actors (e.g., proposers) extract MEV, order transactions and take native token FX risk; non-sophisticated actors just stake and prove.
3. No complicated cryptography; relies on economics and game theory.
4. Easy to implement.
5. Incentivises liveness - no missed slots.
6. No one controls the network for any period of time.

Prior Work

Some of these ideas are based on Ethereum PBS and MEV auction research by Flashbots (e.g., Suave). Thank you to all your work in this space.

SUAVE, Anoma, Shared Sequencers, & Super Builders

State of research: increasing censorship resistance of transactions under...

Spam resistant block creator selection via burn auction

DISCLAIMER
The information set out herein is only conceptual and describes Aztec’s future development goals. In particular, the network roadmap is being shared in order to outline some of the plans for Aztec and is provided solely for informational purposes only and does not constitute any binding commitment. Please do not rely on this information for any purpose - the development, release, and timing of any products, features or functionality remains subject to change.

[jaosef]

Update:

The proposer here could further be separated into two entities to fully achieve PBS. Currently the proposing actor both proposes transaction ordering for a block (for voting on by the proving network), then builds the block (proof transcript), then executes the blocks state updates and finaly assembles proofs into a rollup.

The proposer could just propose transaction ordering and there is nothing stopping another actor fulfil the role of the builder. I think the reason this is not needed compared to Ethereum PBS is that the block builder can’t lie. On Ethereum their work must be checked by other validators. On a zk rollup based L2, the work is proved, for checking by Ethereum.

[spalladino]

Thanks Joe for putting this together, it’s super clear! Two questions:

1- Could the fact that NUM_PROVERS is cubed lead to sybil attacks, where an entity controlling a large number of native tokens spawn enough provers so they control the outcome of votes?

2- Can the block commitment be not pushed to L1, and instead be broadcasted as a signed message to the L2 gossip network, in order to save one tx per block?

[jaosef]

@spalladino

2- Can the block commitment be not pushed to L1, and instead be broadcasted as a signed message to the L2 gossip network, in order to save one tx per block?

Good question, this is possible, but I am undecided on if this is an issue / inevitable even with random based SSLE models. My current thoughts in no particular order:

1. The NUMBER_OF_PROVERS component of the score is a proxy for stake.
2. Ultimately the goal of having a federated proving network is to ensure the network can recover if a large % of proving capacity is shutdown. This means that as long as its always as easy as possible for any entity to spin up a proving network, the network can recover from sybil attacks. This is achieved by ensuring the compute effort needed to construct a part of the proof tree is as small as possible.
3. The proposer who can build the best block from an MEV standpoint, can generate the best incentive for the proving nextwork, as they will be willing to pay the most.
4. If a sybil attack occurs, censorship can be prevented with include list or crLists. An include list could be generated from:
   • L1, allow users to pay and send transactions directly to the L1 contract that must be included in a block (would need failing tx contexts to work) and would be expensive, but a sufficient deterent. Sending the transaction via call data would cost ~ 100,000 gas assuming the proof is 5kb.
   • Include list via uncle blocks (allow non-winning honest proposers) to add an include list on L1 with their block, forcing the next block to include these transactions.
     (https://notes.ethereum.org/s3JToeApTx6CKLJt8AbhFQ#Hybrid-PBS-can-we-use-proposers-only-for-inclusion-of-last-resort)

Do economic incentives always lead to prover centralisation?

• If proposer A is will to pay X for a block A, that means the total value of block A is MAX_MEV = PROPOSER_A_PROFIT + X
• Proposer A’s costs are:
  • Cost of simulating block A
  • Cost of running the compute for a proving network big enough to prove block A
  • The opportunity cost associated with staking capital sufficient to sybil attack the proving votes and ensure Block A wins and proposer A receives X.
• Let’s compare this to a split proposer / prover model, putting forward block B, and assume Block A and Block B’s MAX_MEV is the same. MAX_MEV = PROPOSER_B_PROFIT + X
  • Proposer B’s costs are:
    • Cost of simulating block B

To me provers will centralise if the compute cost of running a large proving network + the opportunity cost of staking sufficient assets, is less than X.

i.e centralisation will depend on the resources required to construct a proof, and the $ value of the stake, i.e the price of the native token. Likely some equilibrium will be met, this can be controlled by the depth of the uncle block reward.

I am still thinking through this so my thoughts could change!

@spalladino

1- Could the fact that NUM_PROVERS is cubed lead to sybil attacks, where an entity controlling a large number of native tokens spawn enough provers so they control the outcome of votes?

The commitment to L1 ensures that no other proposals can be submitted past the end of the BLOCK_PROPOSAL_WINDOW. A signed message does not provide the same guarantee. The proving network may start work on a block, only to be gazumped by a non public proposal that would win. This would lead to nasty race conditions.

I discussed a similar modification with flashbots around an all pays proposer model which has some benefits, but also could reduce the number of proposers, however without the commitment to L1, there is an issue.

[valerini]

Thanks Joe, this is very clearly explained, and makes a lot of sense!
I have a few questions:
Q1: When submitting to L1 do you wait 12 min for the transaction to get finalized each time?
Q2: Do you think the proposers could start a bidding war in the L2 gossip network? E.g. when proposer #1 offers fee F1 for the provers; then proposer #2 after seeing that, offers fee F1+epsilon; then the proposer #1 seeing that re-issues its proposal by offering a higher fee: F1 + 2*epsilons, etc. (similar to priority gas auctions (PGAs) that were happening in Ethereum’s mempool). Could they then possibly spam the L2 gossip network?
Q3: And last question about preventing theft of proofs. When you say that “Proofs are signed and committed to in advance. Inside a proof, a signature verification will occur.” Could you explain this mechanism a little bit more? Could you also water-mark the proof to make it un-stealable, by baking prover’s address into the Fiat-Shamir transform when creating a proof?

[jaosef]

@valerini

Q1: When submitting to L1 do you wait 12 min for the transaction to get finalized each time?

This is a good question I assume you mean to account for block re-orgs on L1? I was assuming a transaction would be final after a few confirmations. Ultimately its the proposer or provers who would make that determination, on what the last “safe” block was to build from.

As L2 state updates must be sequential and follow the order they where sent in, one way to mitigate the effect of potential re-orgs, is to add a tip to the L1 proposer when state is advanced.

If the state advance is correct e.g going from lastBlockNumber to lastBlockNumber +1, the contract could pay a portion of the block reward to block.coinbase (the L1 validator).

This would ensure that if a re-org occurred on L1, there would be an incentive to include the transactions in the correct order.

@valerini

Q2: Do you think the proposers could start a bidding war in the L2 gossip network? E.g. when proposer #1 offers fee F1 for the provers; then proposer #2 after seeing that, offers fee F1+epsilon; then the proposer #1 seeing that re-issues its proposal by offering a higher fee: F1 + 2*epsilons, etc. (similar to priority gas auctions (PGAs) that were happening in Ethereum’s mempool). Could they then possibly spam the L2 gossip network?

I do think there would be a bidding war if the BLOCK_PROPOSAL_WINDOW was on the order of minutes. Modelling will need to be done to determine the effect of a shorter vs longer window. A short window would likely prevent a binding war, as a proposer would need to broadcast their transaction, gather votes, and submit to L1 in a short time period. If the L2 gossip network was spammed, a small selection of provers can always bypass this and submit a proposal with votes directly to L1, so liveness should not be effected.

@valerini

Q3: And last question about preventing theft of proofs. When you say that “Proofs are signed and committed to in advance. Inside a proof, a signature verification will occur.” Could you explain this mechanism a little bit more? Could you also water-mark the proof to make it un-stealable, by baking prover’s address into the Fiat-Shamir transform when creating a proof?

The idea I had here was as follows:

1. The rollup circuit would prove it is following the transcript committed to by the proposer. This transcript defines the public key of the prover who committed to produce a given proof. One of the public inputs to the circuit would be the “vote” from the prover in phase 2. From this signature you can check the following:

• The public key being aggregated into the NUM_PROVERS component of the score, is the public key who committed to producing the proof, simply by checking the public key of the prover against the signature, and re-constructing the message inside the circuit. If the signature does not match.don’t increment the NUM_PROVERS (but still allow the proof).

• Payment will only go to provers who committed to the proof and had their public key aggregated. This should mean that “stolen proofs”, whilst valid, would result in a lower score, and lower payment overal, which is not beneficial for anyone.

Your point on baking the provers address into the transform could also have the same effect, great suggestion, will get Zac’s feedback on that.

[charles-espresso]

Very interesting proposal Joe!

Agree with @spalladino’s point about Sybil attacks. Assuming that the cost to create multiple accounts each with N native tokens is negligible, there would be no reason for large provers not to do so.

@valerini’s point about the bidding war is interesting. I think this is highly dependent on the cost of proving and the value of N. These parameters will need to be well-tuned. For instance, if proving is very computationally cheap and the value of N is low, then I wouldn’t be surprised to see the most effective block builders running their own proposers and proving networks, and dominating the proving for their own blocks. I would be curious to see the result of any modeling on what will happen with different values of N, different costs of proving, etc.

Additional questions:

1. If there is a fixed total uncle block reward, isn’t there an incentive for provers to spam block proposals (up until the cost of posting a block proposal to the L1 exceeds the marginal reward)?
2. Doesn’t the existence of an uncle block reward ultimately result in a lot of wasted prover work?

Overall, I think the proposal is very promising. I agree that the primary concern is that the sequencer selection prioritizes the largest actors, and it’s likely that the entity who is most effective at extracting MEV will always end up being the proposer. This, coupled with the potential for large provers to split up stake and dominate the proving, could lead to significant centralization.

[jaosef]

Thanks for the great questions and comments @charles-espresso! We will share publicly any modelling we do on this in due course.

I have answered your questions below.

@charles-espresso

Agree with @spalladino’s point about Sybil attacks. Assuming that the cost to create multiple accounts each with N native tokens is negligible, there would be no reason for large provers not to do so.

This is also worry for me in the network bootstrapping phase. Over time, I would hope that the cost would not be negligible, especially once there is significant value transacting on the network

@charles-espresso

Additional questions:

1. If there is a fixed total uncle block reward, isn’t there an incentive for provers to spam block proposals (up until the cost of posting a block proposal to the L1 exceeds the marginal reward)?
2. Doesn’t the existence of an uncle block reward ultimately result in a lot of wasted prover work?

Question 1.

Good flag! The proposal should be updated and say “The uncle block reward is only paid to the top X blocks that have valid proofs.” Secondly, the SCORE for a block could take into account the height of the proof tree, this way a spam block would only win if it was also large (computationally intensive), and with a diverse proving set (lots of stake). Further increasing the cost.

In this case, spam blocks will incur an L1 gas cost plus the cost of proving a block with a sufficiently large score. IMO this should prevent spam and ensure a valid proposer doesn’t have to do much to win the uncle reward.

I was imagining only a 1-2 block uncle reward, just to incentivise no missed blocks. Flashbots had a good suggestion here which could mitigate spam as well. The idea was to do a “pay to play” scenario, where the proposer always pays the BURN_BID for the write to commit a block to L1, even if it does not win.

Question 2.

It does result in wasted prover work, but this is a deliberate trade-off to ensure a valid block is always received and the networks block time liveness is guaranteed. e.g BLOCK_PROPOSAL_TIME + PROOF_ACCEPTANCE_WINDOW = Block Time.

This liveness guarantee is important for L2 > L1 messaging, and just a consistent UX.

Other proposals would require a slashing mechanism on an SSLE elected leader to get the same guarantees.

[ballsyalchemist]

To the point you made about builder centralization (whoever extracting MEV). I believe this is inevitable as long as there is significant MEV opportunity. Eth builders are less centralized now than a year ago because Flashbots guys have been doing public goods. But in the future, we will expect to see more decentralized block builder to come out in the space with the launch of SUAVE etc. Imo, having somewhat centralized builder set is transitory.

[rahul-kothari]

Since we never have a single sequencer leader, how would you do force inclusion of L1 to L2 messages?

Also, I think I missed this but what is the finality time for a transaction here?

[jaosef]

@rahul-kothari

Also, I think I missed this but what is the finality time for a transaction here?

Good question for L2 finality (all proposal will technically have to wait 2 L1 slots for final finality), it would be the BLOCK_PROPOSAL_WINDOW + PROOF_ACCEPTANCE_WINDOW. These need modelling and can be tweaked, but on average I would say its slightly slower than an SSLE by the length of the BLOCK_PROPOSAL_WINDOW. I imagine this to be ~30 seconds.

@rahul-kothari

how would you do force inclusion of L1 to L2 messages?

This is an open question I chatted with @LasseAztec about. The current idea is that, each proof will prove the state transitions, and in the very last step, after the end of the PROOF_ACCEPTANCE_WINDOW, when advanceState is called on the rollup contract, the new state roots would be set, and any work done to include messages in that block.

[jaosef]

After speaking with @zac-williamson for a few hours, we have concluded that this proposal does have a flaw as mentioned by @spalladino. The proposal will need modelling to understand the likelihood of this and if tweaks to parameters can prevent this.

A 51% attack

If an entity purchase 51% of the stake, they will trend towards a 100% probability of always winning block auction. Furthermore as the incentives for the provers to compete is linked to winning blocks, the 49% of the network will only win uncle blocks and will further reduce their stake.

An example:

1. There are 100 stakers (provers) and Bob controls 51 of those.

2. Bob is a block builder and so is Sally, they both run the same building software and on average can make blocks with the same value, leading them to bid similarly for a given block. Lets assume 1 token for easy maths.

3. Bob bids 1 token and receive 51 votes (as he owns 51% of the stake). Bob’s score is:132,652 = 51^3 * 1^2

4. Sally will have to bid at least 1.062 tokens to win as the maximum amount of votes she can receive is 49 votes in this scenario. (~133,000 = 49^3*1.062^2).

Over time, this creates a centralising force towards Bob, likely causing Bob to end up with 100% of the staking network, as the provers getting paid on uncle blocks will diminish over time as it is less profitable.

Further modelling is needed to tweak the formula for SCORE, or the proposal will need modification to always pay all provers, regardless of the score of their block, or to bake a VRF into the provers votes to be secure.

Fair pay prover model

Instead of splitting the block reward in the agreed split with the provers who contributed to a specific block, split the block reward amongst all the provers who contributed to any block.

This will have the effect of incentivising provers to work on any block, and to work with smaller proposers to get that block on chain, in order to prevent 51% stake attacks.

Modification with a VRF

Further protection against 51% attacks can come from modifying this proposal with a VRF as used in Irish Coffee or Cookie jar.

Instead of the sequencer using a VRF, each staker in the proving network would use a VRF attached to their vote.

A signature over
1. The block hash 
2. The index of the binary proof tree they will make e.g `Depth 10:Index 4`
3. VRF output for current block hash, which weights their vote

This has some nice properties:

1. The VRF logic can be consumed within the rollup circuit. This means each block comes with its own proof of the VRF output, for no additional cost as its baked into a proof.
2. It gives an easy way for the block builder to assemble provers into a block transcript, based on the weight of their VRF in any given block. i.e they will pick votes with high weight.
3. It ensures the maximum amount of MEV is always burnt per block, unlike other models.
4. It incentivises coordination.A builder needs to pay provers with a high VRF output fairly for a given block, not attempt to gain stake to win a block.

[spalladino]

Could a malicious sequencer grief provers by not revealing the contents of the block they have voted on, colluding with a private prover pool to build and submit proofs separately, and then slashing the honest provers?

Could this be mitigated by making the ordering of the txs in a block proposal public during the block proposal window? This would also offer a soft finality to clients, who wouldn’t need to wait until the end of the proof generation to know that their tx will be included (if everything goes well). What’s the drawback of making this info public, besides the increased size of the block proposal (since it now needs to include a bunch of tx hashes, rather than a single commitment)?

[jaosef]

@spalladino

Could a malicious sequencer grief provers by not revealing the contents of the block they have voted on, colluding with a private prover pool to build and submit proofs separately, and then slashing the honest provers?

A malicious sequencer could grieve, but it is very unlikely that their block would win in that case. for the following reasons:

1. The block commitment contains a transcript of the rollup proof effectively assigning, one prover to a given part of the tree. The proposers score is dependant on that prover constructing that proof. If they do not (as the block was not revealed) the score will be lower as a result.
2. There is a higher cost to this attack as it would require submitting 2 transactions on chain (1 for the block commitment, and one for the proof). The cost to reverse incorrect slashing for an honest prover is only 1 transaction, so the attack is unlikely to prevail.

@spalladino

hat’s the drawback of making this info public, besides the increased size of the block proposal (since it now needs to include a bunch of tx hashes, rather than a single commitment)?

The main drawback is proposers will have ordered transactions in order to extract MEV, if the transactions are public, then anyone can simply take the block, and submit it with a slightly higher score. I think the ordering must remain private until it has been committed to on L1, in order to attract MEV searchers.

[Mike]

Edit: I should have read the whole thing first, as some of these questions are addressed further down your proposal.

@jaosef

A vote consists of:

A signature over
1. The block hash 
2. The index of the binary proof tree they will make e.g `Depth 10:Index 4` 

Provers broadcast this intent to the L2 gossip network. They will likely broadcast multiple intents, for multiple parts of the block and different blocks.

If a prover does not submit a proof after declaring their intent to do so, they can be slashed.

1. To reduce communication, could we encode all intended proof tree indices (for a particular block proposal) into a single vote?
2. I guess a prover wouldn’t be able to confidently commit to an intention to produce a merge rollup proof high up the tree (at least, not immediately), because they have no guarantee that they will see the child proofs which they would need to feed into their intended proof. Perhaps this means provers would only be able to vote (with confidence) for higher up tree indices once they can see the children actually exist in the proof pool?
3. Broadcasting the intents to the gossip network doesn’t ‘register’ their intent anywhere tangible. I.e. the protocol cannot ‘see’ the gossip network and therefore cannot point to any evidence in order to slash users. Would their intents actually need to be persisted in some L1 or L2 state, to enable slashing to be provably justified? edit: Intents are encoded in a ‘transcript’ on L1
4. If a prover submits intent for a block which doesn’t ‘win’, and they didn’t produce a proof for that block, do they get slashed? What if it’s an uncle block?
5. If a block doesn’t win as a result of prover(s) not producing a block, how would the lazy prover(s) be slashed, given the lack of existence of a completed block?
6. What if nobody votes for a particular index of the tree? Do provers have the opportunity to realise this, and submit a vote to ‘unblock’ the block-production process?

Some more Q’s (which I’ll collect as I read)

@jaosef

The block proposer assembles block votes into a block transcript, detailing which provers will create which part of the proof tree from the available votes on the L2 gossip network.

The proposer commits the block transcript to L1 via an Ethereum transaction.

A block will become the head of the chain if BOTH the following conditions are met:

1. A valid proof is submitted to L1 within the PROOF_ACCEPTANCE_WINDOW (M seconds after the end of the BLOCK_PROPOSAL_WINDOW);

AND

2. It has the highest score for the current block height:

• SCORE(y) = NUM_PROVERS (x)^3 * BURN_BID(z) ^ 2 – needs modelling

7. Submitting a valid proof (of an entire block) will be costly (hundreds of thousands / millions of gas of calldata, blob data, message storing, and computation). What’s the incentive to submit, if there’s a risk that submitters might get gazumped by a later submission with a higher score? Is it just “take a gamble”?
8. It seems that we’d always need to wait until the end of the proof acceptance window (to give opportunity to all submitters, to ensure the highest score is selected). Does this cause unnecessary network delays (in the sense that a valid, perfectly nice block proof might already have been submitted to L1 earlier in the window)?
9. How are sybil attacks (from provers) prevented? I.e. how do we stop a prover spinning up multiple prover instances, thereby inflating the NUM_PROVERS component of a score? Perhaps the SCORE calculation needs to include a reference to the prover stake. E.g. the total amount being staked by all contributing provers could be incorporated, or a weighted average ‘stake per prover’.
   • Edit: looks like this might have been discussed in the comments above.

@jaosef

Provers that contributed to any uncle blocks split an uncle block reward pro-rata.

10. What’s to stop someone proposing, proving (by themselves) and submitting a block containing 1 tx, just to reap an uncle block reward? Perhaps such a reward would need to be proportionate to the number of txs in the uncle block, or perhaps some other metric for the ‘size’ of the uncle block. Further, how many submissions would be eligible for uncle rewards?

[zac-williamson]

Could the bidding process benefit from randomness via a PRF?

Without it you end up in a situation where a pool with 51% of the stake produces 100% of the blocks.

I suspect this will happen due to the large economic incentive to pool sequencer stake into pools to capture all block production. This makes the network vulnerable to censorship.

Randomly-weighting the bids removes this problem. If you have x% of the stake you make x% of blocks
(the above is assuming everybody votes against the block that produces the most value, which I think we can assume will happen from game theory)

[zac-williamson]

Is coordinating votes on L1 not very costly? For example, if you have 100 entities voting per block that’s 100 L1 transactions whose cost will have to be borne by L2 tx fees.

Even a basic voting protocol will likely change 2 state variables (~50k gas per tx), so we could be looking at 5 million gas per block just for coordinating votes for 100 participants.

One random thought is: what happens if we change B52 from voting per-block to being more of a prediction market?

Provers vote against how much they fee revenue they think they will get for a given set of blocks.
The winning Provers win the rights to submit a fixed number of blocks before the voting process is run again.

If the winning Provers do not submit blocks, then the runners up get to submit (repeat until you find somebody who makes a block)

[jaosef]

Thanks Mike! Tough questions, let me try dive in.

@Mike

• To reduce communication, could we encode all intended proof tree indices (for a particular block proposal) into a single vote?

Potentially, although the idea is that the rollup circuit is fed in the transcript that the propers committed to on L1. The prover, would feed in their vote to a given proof and the circuit would check the index matched the vote. We would need a clever way to mimic that, to ensure the score is accurate.

@Mike

• I guess a prover wouldn’t be able to confidently commit to an intention to produce a merge rollup proof high up the tree (at least, not immediately), because they have no guarantee that they will see the child proofs which they would need to feed into their intended proof. Perhaps this means provers would only be able to vote (with confidence) for higher up tree indices once they can see the children actually exist in the proof pool?

I was imagining provers would vote on complete sub-trees initially yes. There would need to be some further coordination mechanism to vote on higher up levels of the tree, or there is a grieving attack here I think.

@Mike

• If a prover submits intent for a block which doesn’t ‘win’, and they didn’t produce a proof for that block, do they get slashed? What if it’s an uncle block?

I was thinking this would occur for any valid block submitted in the proof acceptance window, but this would need to be modelled. It should follow the payment methodology for provers. i.e if provers always get paid for a valid block, (regardless of if it is becomes, the head of the chain, an uncle or a low scoring block) then they would always be eligible for slashing on any valid block. If provers don’t always get paid, then they would not get slashed. Again modelling needed here.

@Mike

• If a block doesn’t win as a result of prover(s) not producing a block, how would the lazy prover(s) be slashed, given the lack of existence of a completed block?

• What if nobody votes for a particular index of the tree? Do provers have the opportunity to realise this, and submit a vote to ‘unblock’ the block-production process?

The idea is that anyone can fill in any part of the tree that is missing to complete the block. The commitment on L1 to the proof transcript, defines the maximum SCORE a block can receive. The SCORE will not be incremented in a given proof if it is made by a prover not on the transcript (the signature / private key will not match the vote).

TLDR, a block can always be produced, it may just have a lower score than the proposer intended if different provers, do the work.

The proposer can force slashing by submitting that block to L1 (even if it may not win).

@Mike

Submitting a valid proof (of an entire block) will be costly (hundreds of thousands / millions of gas of calldata, blob data, message storing, and computation). What’s the incentive to submit, if there’s a risk that submitters might get gazumped by a later submission with a higher score? Is it just “take a gamble”?

The idea here is that a proposer knows at the end of the BLOCK_PROPOSAL_WINDOW which block should win if a proof is made. They chose to reveal the block at this point, and would only submit it if they stand a chance of winning the block or an uncle reward. They may gamble if the highest scoring block fails to reach L1 in time as well. TLDR, the proposer has a lot of information to make that gamble as the set of potential blocks and their max score is fixed at this point.

@Mike

It seems that we’d always need to wait until the end of the proof acceptance window (to give opportunity to all submitters, to ensure the highest score is selected). Does this cause unnecessary network delays (in the sense that a valid, perfectly nice block proof might already have been submitted to L1 earlier in the window)?

This is an intentional trade-off for liveness. You can shorten the delay by allowing the next BLOCK_PROPOSAL_WINDOW to start at the start of the PROOF_ACCEPTANCE_WINDOW and each proposal to reference a prior block as described above.

@jaosef

Downtime can be further mitigated by allowing the proposer to specify a block hash, from which block proposal builds from.

The BLOCK_PROPOSAL_WINDOW would then start at the same time as the start of the PROOF_ACCEPTANCE window of the last confirmed rollup block, ensuring zero downtime.

@Mike

What’s to stop someone proposing, proving (by themselves) and submitting a block containing 1 tx, just to reap an uncle block reward? Perhaps such a reward would need to be proportionate to the number of txs in the uncle block, or perhaps some other metric for the ‘size’ of the uncle block. Further, how many submissions would be eligible for uncle rewards?

This will need to be modelled, my current thinking is there is no need to to stop this. There is a cost on L1 for a proposer to submit that block, and if it is a valid uncle e.g the second highest scoring block it would get paid.

For provers, I agree it would be split pro-rata, e.g if the total number of uncle proofs is 1025 (a 2^10 tree and a 1 rollup) the prover who submitted the 1 rollup would get 1/1025 of the reward. Secondly if you assume that the winning block is the most profitable block in terms of MEV extraction, the winning block should be able to pay the proving network the highest fee, so doing work on an uncle block will always be less profitable so an equilibrium should be reached.

[jaosef]

See here @zac-williamson [Proposal] Sequencer Selection: B52 — PBS with a federated prover network - #12 by jaosef

[jaosef]

@zac-williamson

Is coordinating votes on L1 not very costly? For example, if you have 100 entities voting per block that’s 100 L1 transactions whose cost will have to be borne by L2 tx fees.

The voting from provers only occurs in the L2 p2p network.

A proposer would have to commit a valid block transcript (made up of votes collected on the L2 p2p network) to L1 in the BLOCK_PROPOSAL_WINDOW but I would assume there are only 5-10 for any given block (much like the number of entities building on Ethereum).

I think you could get a block commitment down to 1 state variable (a hash of the proof tree and the full proposal). With some gas golfing you can get this down to ~26k gas per L1 commitment and maybe a hash of calldata. The first time a proposer commits to L1 will be closer to 45k as it will be setting an empty storage slot which is an additional 20k.

This is an overhead of closer to 150k per block assuming 5 submissions at 30k.

I do think this overhead needs to be modelled, but given the protocol has 100% MEV value capture, it may be acceptable. This cost also gives the user a soft confirmation. E.g if your transaction is in the top N highest scoring commitments, its likely to be final.