Ideas on a proving network

While the B52 sequencer selection proposal includes a decentralised proving network as part of it’s design, Fernet leaves it out of scope. Our goal here is to arrive at a design for a prover network that can be used by any sequencer selection algorithm.

Why decentralise provers?

Written by @jaosef

Proving correct execution is orders of magnitude slower than simply executing a transaction. If a sequencer needs access to a very larger proving network simply to make a block, that is a very large centralising force.

Why can’t we just post proofs to a worker queue with a bounty?

  1. A sequencer who must produce a block within a certain window (as defined by the SSP) will not rely on one prover to do this, as they risk revenue. A rational sequencer will either ask many provers to compute the block, leading to redundant compute and extra costs for users, or run their own compute.
  2. A rational sequencer will only pay the fastest prover, which means the second fastest prover does not get paid. Over time this may lead to centralisation with one giant prover. This creates bribe attacks, present, unless the protocol enforces all provers get paid.

Aspects

Given the above, we can discuss different aspects of proving network, such as payments, selection, participation, etc.

How are provers selected?

Let’s assume there’s a pool of valid provers to choose from at any time, already made sybil resistant via staking or a similar mechanism. How is a prover chosen to work on a given proof?

  • The sequencer can be free to choose whatever prover(s) they want. This allows sequencers to leverage reputation or other off-protocol information to make their choice. This is similar to how UniswapX allows users to grant exclusiveness in filling an order to a particular executor (albeit for a limited amount of time), or clients pick relayers in the Gas Station Network.
  • The chosen prover(s) can be decided by the protocol itself, such as via a VRF. This requires that the pool of provers is vetted in advance to ensure all provers in it can provide a reasonable quality of service. This is similar to how Livepeer picks Transcoders.

On B52 as it is today, provers submit intents to build a proof during a voting phase, and then the sequencer chooses which prover is allocated to which job. It is unclear how provers coordinate between each other, and we could end up in a situation where every prover signals intent to build the entirety of a block, and it’s fully on the sequencer to choose how work is spread out.

How are provers paid?

Provers need to be rewarded for their work. Now, prover payments can be handled in or out of protocol.

  • Provers can be paid a fraction of the block fees depending on their contributions to their proofs tree. Given each proof can include the id of the prover that proved it, it should be easy to calculate this rate. This has the benefit that provers get paid only if they submit valid work, and verification is done as part of the protocol itself.
  • Payments can be handled out of protocol, as a transaction between sequencer and provers. Sequencers could paid provers upon receipt of a valid proof, and we could require sequencers to submit a bond that is released once the prover sends back the proof, to avoid griefing. We could implement a payment-channel-like structure to avoid gas costs in these interactions, but it requires more work to build. On the other hand, keeping payments out of the main protocol gives us more flexibility in changing it.

Embedding payments into the protocol seems to be the easiest way to go. In this approach, provers could be grieved if their submitted proof is not included in the resulting tree, but we could set up a separate path in which a prover can claim uncle rewards by submitting their proof separately if it was neglected.

How many provers are selected per unit of work?

We can choose how many provers are selected for each unit of work. Choosing a single one leads to the least wasted effort, but can affect liveness if that prover fails to deliver. Given long proving times, a missing proof delays an entire layer of the proofs tree. However, if we require multiple provers for each unit of work, all provers need to be rewarded (not necessarily equally), leading to higher fees overall.

Note that, if the sequencer is left to choose prover(s) on its own, we cannot enforce it to pick multiple provers unless we have a strong sybil resistance mechanism in place. On the other hand, if we allow the sequencer to choose a single prover each round, we could end up with a single centralised prover monopolising the network, as mentioned by Joe in the first paragraphs.

How are provers vetted?

We can enforce requirements for a prover to be eligible for participation in the protocol.

  • If sequencers are completely free to choose provers, then we could roll without any requirements. Anyone can just act as a prover by helping the sequencer assemble a proof.
  • We can require a stake in the form of a fixed amount of tokens for participating, similar to validators in Ethereum. This allows the network to slash malicious behaviour by provers, even if we have not yet identified what that would look like, assuming we have a governance mechanism that permits it. It also helps prevent spam.
  • If prover selection is mandated by the protocol and not sequencers, we need a stronger signal than just staking, since we need the network to filter out which provers are able to provide a reasonable service. Here we can require that token holders stake for specific provers, similar to transcoders in Livepeer or indexers in TheGraph. This will lead to a smaller number of provers but with a vetted quality of a service.

How many provers do we expect in the network?

We want to encourage a scenario where we don’t converge to a single prover dominating the market. This could happen if we prioritise provers exclusively based on performance and set up a winner-take-all mechanic, as described here:

Related is the problem of maintaining decentralization. One challenge with proof markets is prover undercutting. A well-funded prover could choose to operate at a loss by bidding below market rates to price other operators out of the market before growing and increasing prices. Another form of undercutting is operating an excessive number of nodes while bidding market rates, allowing random selection to match the operator with a disproportionate amount of proof requests.

This can be mitigated with uncle rewards, or enforcing a minimal proving time (as Mina does, thanks Anon for bringing it up) to level the playing field.

Related to this is hardware requirements. We expect provers not to require inaccessible machines, but we still don’t know if they will require something slightly more powerful than consumer-grade machines (eg 32 cores).

Looking into other rollups

Given we’re not the only zk rollup out there with plans for decentralisation, it’s worth looking into what others are doing.

Mina

Mina’s prover network is handled through the snarketplace, a marketplace where block producers (chosen through a VRF) purchase SNARK proofs from workers. These purchases are entirely off-protocol, and the market favours the worker that offers the lowest fees, not the fastest one.

There is no protocol involvement in pricing snarks, nor are there any protocol level rewards for snark workers to produce snarks. The incentives are purely peer-to-peer, and dynamically established in a public marketplace, aka the snarketplace.

The risk of centralisation around a single entity is mitigated by the fact that the barrier to entry is low:

Is there any concern about a single large SNARK worker dumping work in the snarketplace, and then raising prices after monopolizing the market?

[…] this strategy is effective only in markets where there are high barriers to entry. Meaning, competitors who were crowded out in the predation stage are unable to rejoin the market.

This is not the case for SNARK work because the barriers to entry are low. Anyone who has spare compute can join the snarketplace and produce as little as one SNARK work and profit on that unit of work. The only barrier to entry is the initial capital expense on hardware, but hardware requirements are low so that users with spare equipment can come online and participate. If any SNARK worker succeeds in driving out the market and increases prices, newcomers are anticipated to reappear and drive prices back down.

Taiko

Taiko seems to have a very different prover environment than Mina’s: while Mina shoots for making it easy for anyone to become a prover since proofs are small, Taiko has a high barrier to participation:

Keep in mind that running a prover on mainnet will be a very competitive space, and those who generate proofs will have very powerful machines. It’s unlikely anyone will be able to be a “casual prover”.

A previous version of Taiko favored a winner-takes-all approach to submitting proofs, but this was leading to a scenario where a single prover would prevail, affecting liveness. A testnet run seems to have confirmed this. Hence, their new approach is to keep a pool of 32 provers, ranked based on stake and fees requested, and use a VRF to choose among them. Failing to submit a proof by the chosen prover leads to slashing.

Starknet

Starknet went through a similar process as this one a few months ago, weighing tradeoffs of different approaches for decentralising proving.

How to best enjoy the benefits of competition without risking centralization?

In contrast to competition, turn-based monopolies resolve incentive problems well, but may not discover the best candidate for each job or incentivize improvement. A glaring question is: what are the turns based on? Stake-based turns allow stakers to choose provers. This does not seem problematic in principle, but the “classical” role of stake is to provide Sybil resistance only for the consensus layer. What are some other interesting ways of realizing turn-based monopolies? How to incentivize improvement in such a model?

A turn-based model can also be competitive, e.g a turn-based auction. For example, Ethereum’s designation of labor for sequencers is essentially a turn-based auction, with the winner being the first sequencer willing to sell block space to a transaction in exchange for its fee.

And more recently:

When thinking of auctions, we felt an L1 auction contract is too cumbersome and expensive, while off-chain auctions may be vulnerable to censorship. Coupling proof production to block circumvents these issues. Lastly, even if you have some proofs decoupled from block production, it seems a turn-based system based on stake is still simpler to manage than an auction.

nil

While not a zk rollup in itself, nil offers a proof market where buyers can purchase ZKPs from a set of provers. Given an order with a given maximum price and time to fulfill, the market automatically matches it with a prover given their offered price.

Here are the basic rules of order matching for a request with specified time t_r and price c_r :

  • Choose proposals with t_pt_r and c_pc_r .
  • Sort them by price and proof generation time. The user’s request defines the priority of these parameters.
  • Apply proof producer’s rating to the sorted list.
  • Choose the top proposal from the list.

Provers are required to stake to participate, and are penalised if they fail to fulfill their obligations. The market also keeps a reputation system for provers, though it’s under development. Whether this incentive structure could lead to centralisation is unclear from the docs I could find.

Scroll

Thanks to Toghrul for taking the time to share his thoughts with us. I’ll try to capture our discussion here, and hope I’m not getting anything wrong!

Scroll’s main assumption is that MEV will be the main driver of revenue of their chain, so their designs goal is that sequencers do not keep all that MEV to themselves and instead share it fairly with provers. This leads to two approaches:

  1. Multiple sequencers are elected per round, and they post bids to the proving network. The proving network chooses the best bid for them, forcing sequencers to compete amongst themselves and sharing the value captured. In this model, which prover is elected to manufacture a proof is decided via a VRF, and provers are required to stake to participate.
  2. Provers themselves are the block proposal leaders, removing the role of the sequencer as the proposer. The prover is elected by the proposer selection algorithm directly.

There’s also emphasis in having a consensus layer at L2 to grant strong ordering guarantees before committing to L1, similar to the Espresso Martini sequencer selection proposal.

Going back to Aztec

Let’s go back to what we can build for Aztec. We can start with this relates to B52 and Fernet, the current candidates for sequencer selection.

B52

B52 forces block builders to share their captured MEV with provers by putting forward bids to be voted on by provers. The winning builder then selects provers among the set of their voters, and is incentivised to maximise the number of unique provers participating in that block, while choosing provers with good reputation in order not to risk liveness (or they lose their reward). Prover selection is then left entirely to the block builder. Note that prover votes are weighted by a VRF to prevent a centralised actor from taking over the proving network by spawning as many provers as work units on each block.

This approach incentivises builders to compete for extracting the most MEV (either directly or via a mev-boost-like external PBS mechanism) while sharing it with the proving network.

Fernet

Fernet doesn’t define a proving network within its scope. B52’s approach is not directly applicable to the proposal, since the winning block proposer has exclusive rights to the block contents, as long as they can produce a proof.

A marketplace, similar to Mina’s or nil’s, would be a good fit for Fernet, since it’s orthogonal to the rest of the protocol. It would require additional work to integrate, and it’s unclear how decentralised it would get. As a live example, Mina’s Snarketplace seems to lead to a powerlaw distribution of workers.

Protocol-elected provers

In both scenarios for B52 and Fernet, it’s the winning block builder or sequencer who chooses the provers. We can instead propose a protocol that picks the prover for each work unit with a turn-based system, which could be applicable to both.

On each block, we can rely on a VRF for deciding which prover in the pool would be elected to generate each unit of work. We begin by choosing which prover works on which leaf of the tree. Then, for each pair of adjacent nodes, one of the two provers chosen for those nodes is picked to build the merge node, and so forth until the root of the tree. If a given prover fails, its sibling is incentivised to step in and produce their proofs, so their subtree is included; in this scenario, the failing prover gets no reward, and the sibling gets rewarded only for the nodes that were assigned for them.

This approach ensures a fair distribution of work across the proving network, and provers cover for each other in the face of liveness issues. We could also add some form of slashing if a prover fails to deliver, though we risk a prover griefing another by just not including their proof and causing a slash.

In B52, this approach can be used to selecting which provers amongst the voters are selected for building the block, and how the workload is distributed. Rather than having provers vote for specific nodes, provers would then vote for the proposal they like the most, the builder would consolidate all votes (regardless of participation in proof generation), and from that set pick the provers that will do the actual work through this algorithm.

In Fernet, since there are no competing block proposals in each slot, this approach is applied across the entire prover pool. A missing piece, however, is how fees are shared between sequencer and provers. We could patch the sequencer scoring function (currently only a VRF) to factor in the percentage of fees the sequencer pushes to the provers. We can expect that, as the network evolves, MEV would become more of a driving force in terms of revenue, so sequencers would eventually share 100% of fees to provers to increase their chances of getting elected and extracting MEV. This assumes that protocol fees only are enough for keeping the prover network running.


Work in progress.

20 Likes

Mina is evidence that a MIN_PROVER_TIME high enough to allow for a high-latency network (snarketplace) is sufficient for liveness, while maintaining permissionlessness.
Taiko’s new scheme (staked provers) falls back to a permissionless low-latency all-pay auction on slot-miss.

Permissionlessness is valuable in preventing prover coordination attacks.

20 Likes

Thanks for the great write up, @spalladino :confetti_ball:

Generally, I think we should worry about what proving in Fernet looks like after we have decided to use it over B52, simply to make sure we’re not wasting time. However, given Fernet is the current leading candidate for sequencer selection designs, and there is other active work ongoing such as this post, I figure it is likely worth sharing some thoughts now in advance.

In Fernet, the sequencer’s themselves should be sufficiently decentralized to the point that we are no longer necessarily worried about - censorship resistance (random election, crLists, etc.) or monopolization (permisonless, and stake-based). It does not yet address proving, and the primary goals for building a decentralized proving network is to 1) ensure liveness, and 2) facilitate an economically competitive market enabling proving to get as cheap as possible.

I currently see the design space including the following options, generally -

  1. Do nothing - let sequencers vertically integrate &/or simply figure it out
  2. Enshrine a 1st party proving marketplace
  3. Enshrine a 3rd party proving marketplace
  4. Enshrine a delegation mechanism for 3rd party proving marketplaces

Let’s look at these options in more detail.

1. Do nothing - vertically integrate

This means that your proving set is defaulted to a size of 1, or as many computers as the current sequencer needs to setup in order to get the block they proposed proven within the submission window, e.g. 10 minutes. It is likely that this would either simply not work well, and have really small blocks that an average machine could prove within that time frame. However, more logically this type of solution would result in an out-of-protocol 3rd party delegation.

2. Enshrine a 1st party proving marketplace

This is what most of us think of when considering Aztec’s “proving network” - it is simply a set of computers that are choosing to run Aztec’s proving node software, and contribute compute to the infrastructure that powers Aztec. It is 1st party because it is built “in-house” alongside the rest of the protocol, then “enshrined” as it’s coded on L1, and required to be utilized. It could look a lot like B52’s proving network - staked participants are assigned portions of the tree via a block transcript. But there are many options for how this 1st party marketplace, some outlined in this post, such as -

  1. Randomly assigning portions of the proof tree
  2. Sequencer choosing/assigning portions of the proof tree
  3. First proof first serve (FIFO)
  4. Attempting to create a marketplace for the right to work
    • e.g. provers bid on portions of the proof tree

3. Enshrine a 3rd party proving marketplace

These are purpose built solutions dedicated to this problem – effecitvely in the same way ethereum provides compute, these networks provide zk proving. Enshrining a single 3rd party marketplaces come at the cost of existential risk to the protocol by introducing a 3rd party dependency that may not be philosophically or economically Aztec Aligned:tm: in the same way shared sequencers may not be. Examples include nil as you mention above.

4. Enshrine a delegation mechanism

More choices are generally better, especially for sophisticated actors. In Fernet, the sequencer’s themselves should be sufficiently decentralized to the point that we are no longer necessarily worried about censorship resistance and monopolization – to this point, we do not necessarily need to design a fully decentralized proving network, as long as it meets the other needs of liveness and is economically competitive. While the least clear design space, I imagine this sort of like UniswapX’s RFQ process - a sequencer posts a block, gets a quote from a variety of actors/services/networks on how much it may cost to prove, and can choose the cheapest quote they feel comfortable with (1 or multiple, ensuring some liveness via redundancy). This could look something like the following -

  1. A sequencer is chosen randomly via Fernet
  2. That sequencer has to commit to a mechanism within a specific time period
  3. That mechanism could be one of the following -
    • Self proving
    • Proving via a B52 style “1st party” network
    • Proving via x, y, z well known “marketplaces”
      • (if 3rd party is truly cheaper/more efficient, they should be able to go elsewhere)

I’d like to imagine that with some commercial success there would be an out of protocol “gas station” or “proving station” giving best, realtime price estimates on the above options. :shrug: Not 100% sure but seems worth exploring perhaps!

Suggested path forward

I think that if we are to move forward with Fernet, which we should have clarity on relatively soon, then we can next identify which category we would like to pursue. Personally, I think the only realistic options are #2 (1st party marketplace), and #4 (enshrined, flexible proof delegation mechanism), but haven’t yet had much time to consider the tradeoffs. Once aligned on a category of solution, I think we should put out another public RFP asking the community to help with proving designs, based on Fernet’s implications.

19 Likes

This overview is excellent - perfectly condenses a bunch of research I’ve also personally done on the matter. We actually featured this post in our newsletter so more people would read it:
https://twitter.com/hammyx_/status/1692190342550802802

13 Likes

I think we can (PBPS) (BPA)

  1. Sequencers will select bonded provers, where the bond > stake + MEV.
  2. With a fixed MAX_PROVER_TIME, the cheapest prover is preferred. If network latency overhead is proportionally small, decentralized networks connecting the cheapest compute will dominate.
8 Likes

Decentralised networks will also be utilizing unused capacity and so may be able to have different cost structure dynamics (not only by finding cheapest hardware). This is intuitive if you assume there will be app/rollup specific prover networks, which each individually will only use a portion of the total proving capacity of the hardware.

1 Like