[Proposal] - Staking Proving Network for Fernet

Aztec
,
1

Staking Proving Network for Fernet

Overview

This document proposes a cooperative proving network, with two explicit goals:

  1. Ensuring that the role of sequencer and prover are 100% divorced to minimise the centralising forces that can arise from this.
  2. Better incentivising stakers, and ensuring sequencer machines are not idle when not proposing

The proposal achieves these goals by re-using the existing staking set proposed in Fernet, and assigning stakers proving work in a deterministic and cooperative manor.

Rational

Fernet relies on a widely decentralised staking set, each with powerful machines, (likely 16 cores ~ 16gb ram) needed to fulfill the role of a sequencer on Aztec.

The design works well very well for randomly selecting a sequencer and ensuring the chain’s censorship resistance properties.

However, sequencing is just the tip of the block production iceberg, and when designing for block production as a whole, the staking set needs to perform more functions than just sequencing.

Block Production Life cycle

ddd
ddd2760×416 99.1 KB

In order to get a block on chain, the current sequencer in Fernet is responsible for all boxes in the diagram. They will be forced to outsource the majority of the work to better suited entities as described below.

Searching & Ordering

Stakers will likely sell the right to order the transactions in a block to a better suited entity via a secondary market e.g Flashbots.

Proving

Without a prover coordination protocol, stakers will either have to control a large proving network, or outsource proving to entities with dedicated hardware, to ensure they can produce a block. This creates large centralising forces on the sequencer staking set, as the sequencer can’t fulfil their role without help, as well as weakening the censorship properties of the network.

Proving Committee

Outsourcing proving and searching leaves sequencer machines idle for certain periods. These machines still have large resource requirements, which is wasteful. (minimum 16gb ram 16 cores).

This proposal adds a key role to the staking set, a proving committee. The committee is selected using the same VRF in Fernet to pick a subset of stakers to prove the block. The committee changes each epoch.

The committee is selected from the opposite end of the VRF to sequencers, ensuring no overlap, e.g sequencers have a high VRF, provers have a low VRF.

As members of the proving committees are already sequencers they currently maintain full nodes on the L2, so have access to the full state of the L2, simplifying proving coordination as less data needs to be transferred.

Worked Example

  1. The protocol defines a staking system used for selecting sequencers and provers. Stakers register a staking public key on an L1 smart contract and are required to run the staking and proving client.

  2. For sequencing, a VRF over the current randao value is used to determine which sequencer can produce a canonical block for a given slot (as per Fernet). The highest VRF will win.

    • The VRF is over the stakers public key, ensuring other stakers can calculate the winning VRF output. This is important to prevent with-holding attacks.

  3. The block reward is split into three portions B^{Sequencer}, B^{Provers} and B^{Submitter}

  4. For proving, the same VRF is used to select a proving committee from the lowest n VRF outputs. (n is set by the sequencer dependant on desired throughput).

  5. The current sequencers block commitments, defines the set of proofs needed for the rollup block. For any given block, stakers, compare their VRF against to see if they are in the proving committee. If so, they submit proofs defined by their VRF and the block transcript using option 1 or option 2 described below.

  6. The current sequencer must broadcast all transactions to L2 to allow the proving committee to construct proofs. This is enforced in two ways:

    • The block can only be produced if a subset of eligible provers e.g N/M helps make the proof. (This gives a guarantee that at least N/M stakers have the data for txs in private meme-pool, and preventing withholding attacks unless N/M stakers are the same entity).
    • The B^{Sequencer} is increased for each distinct prover who helps contribute to a block from within the proving committee.

  7. Provers selected for the proving committee who repeatedly (e.g 3 times in a row) do not contribute to blocks can be slashed via a mechanism similar to the L1 Activity bleed on L1. This will need tuning to allow censorship by a large staker.

  8. Once the final proof is made, anybody can submit to L1 and claim the B^{Submitter} portion of the block reward. This is designed to cover costs associated with submitting e.g gas / call data.

Distributing work to provers based on a VRF

Option 1 Binary tree traversal**

Credit to Dan Lee for this idea.

If we take the proving VRF of any staker eligible, it is possible to define a path through the proof tree based on this.

An example for a rollup of 2^11

VRF = sha256(stakingPublicKey, previousCanonicalBlockHash)
VRF = 0x9d04a3ebfac363861c8d79235cb824f5984732027ab838b6d701de2d21671191

Assuming this is 32 bytes, we truncate the first 11 bits in binary and iterate through the tree to define a proving path.

Prover Transcript = 0011 0010 110

The tree traversal is enforced in the rollup circuits, constraining the user only receives a reward if they are merging proofs on their binary path. This helps ensure a large prover has to do far more work to include a subtree that is not theirs and will be incentivised to coordinate.

Example: take a path through the tree as 1111 1111 111, for each level of the tree, to get credit for the 7th level of the tree, without including other provers work, a large prover would have to compute 2^6 other proofs for which they are not paid.

Option 2: Sorted VRFs

The same VRF used for sequencer selection is used for prover selection. The highest VRF will become the sequencer and the lowest N sequencers will be eligible for proving.

When committing to a block, the sequencer defines the tree height for the block. e.g 2^n. This is used to determine the size of the proving set used for each round of proving.

Proving is split into rounds where each eligible prover computes a sub-tree of height m, lets say 2.

Twice as many provers are selected as necessary to provide redundancy.

Let k = the height of the tree still to be proved.

For tree of size 10:

Round 1: The bottom 2^{n+1}, 2^{11} provers ranked by lowest VRF output selected. Each computes a subtree of 4, inlcuding VM proofs, and base rollup proofs.

Round 2: The bottom 2^{k-m +1}, 2^9 provers ranked by lowest VRF output selected. Each computes a subtree of 4 merge proofs.

Round 3: The bottom 2^{k-m +1}, 2^7 provers ranked by lowest VRF output selected. Each computes a subtree of 4 merge proofs.

Round 4: The bottom 2^{k-m +1}, 2^5 provers ranked by lowest VRF output selected. Each computes a subtree of 4 merge proofs.

Round 5: The bottom 2^{k-m +1}, 2^3 provers ranked by lowest VRF output selected. Each computes a subtree of 4 merge proofs.

Round 6: The sequencer completes the tree.

Issues solved by this proposal

Proof stealing
A proving network design needs to address the case where Bob steals Alices proof. This is acheived via baking in a secret key into the proof that also controls stake, ensuring only Bob can be paid for this proof.

Liveness
A sequencer with commodity hardware, should be able to get a reasonable guarantee from the proving network, that their block will be produced, or they will not be able to fulfill their role as sequencer. The Aztec block lifecycle is longer than L1, and it is likely that each block, will be worth more in Rewards, Fees, and MEV as they span a longer time span.

Sequencers must be able to trust the proving coordination protocol to deliver, or they will forgo a large revenue opportunity.

This proposal adds a requirement for the entire staking set to help produce a block proof to help guarantee that a block will be proven.

Growing a large staking set

On Ethereum validators will propose a block every ~70days on average with a block time of 12s, and less as the set grows.

On Aztec if the block time is 120s, a single sequencer would only propose a block every 700 days with 500,000 stakers, and potentially every 2800 days if the block time is 10 minutes.

This document tries to add additional revenue opportunities to the staking set to mitigate against infrequent block proposing, when a sequencers VRF is not selected. This better utilises staker resources and increases staker % ROI, even with larger block times.

Ensuring data is available

This proposal presents two methods to ensure proof data is available and prevent with-holding attacks:

  1. Modifying the canonical block ranking algorithm to require a signature from M/N of the elected proving committee. This forces a sequencer to broadcast data in order for their block to become canonical.

  2. Incentivising sequencers to quickly disseminate data by increasing their reward based on the percentage of the proving committee that contributes to the block.

Why should stakers perform two roles?

Separation of concerns is usually better when it comes to complex systems. However for a system like Aztec if the role of proving is not carefully incentivised by the protocol, centralising forces will arise due to the economic incentives the protocol gives to sequencers via Fernet. (i.e the ability to sell the ordering and proving rights for a fee).

These centralising forces arise from:

  1. Proposing a block as a sequencer is a revenue opportunity. Fees + block reward + ordering preference fee.
  2. If a sequencer is unable to produce a block when their VRF output is eligible, they will have a worse ROI on their stake.
  3. As such, rational economic sequencers will employ methods to maximise ROI including:
    • Running centralised proving infrastructure to ensure they can produce a full block
    • Paying multiple provers via a proving market
    • Selling the right to produce a block to someone better suited

Learning from Ethereum

This design is very similar to how the beacon chain operates. On L1, stakers have two key roles:

  1. Proposing blocks
  2. Acting as part of a validating consensus committee

Aztec is a ZK L2, therefore a validating
does not need to exist. However computationally intensive proofs do need to be made.

If Aztec’s rollup circuits and public VM circuits are optimised, the machine requirements for a prover should be possible to run at home e.g 16 cores + 32gb of ram.

Comparisons to other proposals

Cooperative proving network for Fernet

This protocol is a cooperative proving network and very similar to Cooperative proving network for Fernet.

It’s key differences are:

  1. This proposal enforces that the staking set for sequencers and provers is the same.
  2. This proposal elects a proving committee per block based on the low output VRF’s
  3. This proposal does not reward uncle proved blocks, instead it enforces an inactivity slash for elected provers who do not participate over a longer period.
  4. This proposal does not have a burn model attatched to it (even though burn models are awesome…)
  5. This proposal attempts to solve DA issues by either enforcing that a block will not become canonical without signoff from M/N provers, or by incentivising the sequencer more for each unique prover that participates. Both should serve to incentivise the sequencer to widley distribute proof data.

The VRF selection and fee burn model in Cooperative Proving network can be best thought of as a good alternative to Option 1 and Option 2 in this proposal of how to distribute work to provers via a VRF. It is likely the best bits from both proposals should be combined.

SideCar

This proposal is at the other end of the spectrum to SideCar. It removes all responsibility for putting a block on chain from the sequencer, after they have posted a block commitment. This seperation of concerns is beneficial for two reasons:

  1. To limit with-holding attacks from the sequencer.
  2. To fight against centralising forces that arise from sequencers with large proving power, or rely on a specific proving entity. In this proposal, a small sequencer has access to the same proving power as a large sequencer, in a decnetralised fashion thanks to Fernet. This promotes liveness and censorship resistance compared to a sequencer being reliant on either:
    • a large proving network controlled by the sequencer
    • a proving market that could change / de platform Aztec
    • a small set of large proving entities like L1 builders
  3. Seeks to better incentivse stakers, who in the current Fernet design will only produce a block every 700-2800 days.

Side car does have some advantages:

  1. Sidecar may use compute more efficiently, but at the cost of liveness
  2. Sidecar is easier to build
  3. Sidecar will be better if the publicVM proof dominates and needs very large machines, i.e 128gb ram, and 64cores, however IMO this would be a failure and not promote decentralisation as Aztec proofs must run in a data centre.

Outstanding questions

Public VM benchmarks

This design, like other designs, has a big unknown on the benchmarks of the public VM. Given public VM proofs will dominate proof construction, machines will need to be sized to match this.

Assumptions

Throughput: 10 tx/s
Blocktime: 600 seconds
VM proofs per tx: 2
VM proof time: 10s
Machines required: ~400

Numbers taken from this model.

Optional Add On : BLS Validation Training Wheel

The proving committee concept can further be extended to define a BLS Validation Training Wheel. This would further re-use the same staking set, while the training wheel is active. The proving committee must also provide a signature over the blocks state transition.

73 Likes
2

you mean 16 threads or 16 actual cores? because even something like i7-12700K has just 12 cores so 16 actual cores is definetely not something that can be called a ‘‘home machine’’.

64 Likes
3

Threads should be fine, e.g i7-432 from these ETH 2 stakers → shop

26 Likes
4

Love it, in particular since it solves the proof withholding issue from Fernet. Two comments:

  • I don’t think I understood how the binary tree traversal option works. Can you elaborate on that one?
  • A sidecar could still be implemented, but as a client-addon instead of at the protocol level, as sequencers could outsource proving work to a network like gevulot or nil.
55 Likes
5

These are opposed. A more decentralized staking set is one that can run on a cell phone (which PBS achieves, and Ethereum may).

I’m concerned that the centralizing effects of such high operating costs (capital/electricity/bandwidth) are being underestimated. I do not expect stakeholders to want to run their own hardware, and to readily stake via third parties instead.

This creates a dependency on a trusted third party (relays). PBS addresses this issue.

You’re confusing proof-time with block-time. Both Fernet and PBS can produce blocks at ~L1 speeds.
This also implies that multiple concurrent committees must be electable (requiring ~10x nodes given 12s blocks and 10min proof time).

Provers may be cheaply bribed not to prove in order to reorg the chain. Because there is no data-availability guarantee, we cannot slash provers who don’t participate. This may cost less than prover-block-reward to do, and will also cause the sequencer to get slashed.

Provers may collude against sequencers, because the sequencers stake is at risk if the provers refuse to sign.

74 Likes
6

Thanks for reading @Anon. I will try to answer inline.

The machine requirements I listed are needed to support high throughput. Aztec transactions are larger than plain-text transactions, likely 32kb per transaction, if the network supports 100 TPS, sequencers, and P2P nodes must be able to:

  1. Reliably sync to the mempool which could be 30-300mb.
  2. Build and insert data and nullifier merkle trees, the merkle nullifier tree can be very large and require more compute than a traditional tree.

We are doing everything possible to reduce the size of the machines required, and as corrected by @smallsizechad, this is 16 threads not cores.

As an L2, the effects of malicious large staking entities on the network are liveness issues, not a consensus failure as per L1, so IMO its better to design a system where we combat the effects of the centralising forces that arise from stake delegation, rather than trying to ensure it runs on all machines, as that will harm throughput / UX. A good example of this is force transactions on L1.

Does this mean you are in favour of enshrining PBS into Fernet?. Fernet currently supports out of protocol PBS, and we assume modifications of the current MEVBoost will be used. We are monitoring the L1 ePBS discussions, to see if any modifications to support enshrined PBS could be made, but as of today, this still seems un-solved.

I consider block time to be the time it takes for an observer of the L1 contract to consider a block valid – so inclusive of the proving time.

As you point out, Fernet has several with-holding issues if blocks are proposed faster than they can be proved. This proposal attempts to fix those issues by:

  1. Incentivising a sequencer to reveal proof data, either via requiring M/N provers to participate in a block, or increasing their reward for each prover.
  2. Splitting the block reward into three portions and not imposing a slash on sequencers, increases the cost to bribing the proving network to not produce a block.

Because of these mitigations, I don’t agree with your last comments.

3 Likes
7

Let me give this a try (with GPT’s help on diagrams) tagging @dan-aztec as well though.

Let’s assume a 16 transaction rollup, so 4 levels of the tree.

Let’s assume a prover is in the proving committee and their VRF output in HEX is:

0x89B4C2D6E8F1234567890ABCDEF9876543210123456789ABCDEF9876543210

From this, truncate the first 4 bits, which is 8 in hex (or 1000 in binary).

So the path derived from 1000 is:

  1. 1 - Right
  2. 0 - Left
  3. 0 - Left
  4. 0 - Left

And in our Merkle tree:

  • ROOT to HASH2
  • HASH2 to HASH2A
  • HASH2A to HASH2A1
  • HASH2A1 to I
graph TD

    ROOT[ ]
    HASH1[ ]
    HASH2[ ]
    HASH1A[ ]
    HASH1B[ ]
    HASH2A[ ]
    HASH2B[ ]
    HASH1A1[ ]
    HASH1A2[ ]
    HASH1B1[ ]
    HASH1B2[ ]
    HASH2A1[ ]
    HASH2A2[ ]
    HASH2B1[ ]
    HASH2B2[ ]
    A[A]
    B[B]
    C[C]
    D[D]
    E[E]
    F[F]
    G[G]
    H[H]
    I[I]
    J[J]
    K[K]
    L[L]
    M[M]
    N[N]
    O[O]
    P[P]
    LEGEND1[Prover VRF: 0x89B4...3210 - Path: 1000]

    ROOT --> HASH1
    ROOT --> HASH2
    HASH1 --> HASH1A
    HASH1 --> HASH1B
    HASH2 --> HASH2A
    HASH2 --> HASH2B
    HASH1A --> HASH1A1
    HASH1A --> HASH1A2
    HASH1B --> HASH1B1
    HASH1B --> HASH1B2
    HASH2A --> HASH2A1
    HASH2A --> HASH2A2
    HASH2B --> HASH2B1
    HASH2B --> HASH2B2
    HASH1A1 --> A
    HASH1A1 --> B
    HASH1A2 --> C
    HASH1A2 --> D
    HASH1B1 --> E
    HASH1B1 --> F
    HASH1B2 --> G
    HASH1B2 --> H
    HASH2A1 --> I
    HASH2A1 --> J
    HASH2A2 --> K
    HASH2A2 --> L
    HASH2B1 --> M
    HASH2B1 --> N
    HASH2B2 --> O
    HASH2B2 --> P

    class ROOT,HASH2,HASH2A,HASH2A1,I red-path
    class HASH1,HASH1A,HASH1B,HASH2B,HASH1A1,HASH1A2,HASH1B1,HASH1B2,HASH2A2,HASH2B1,HASH2B2,A,B,C,D,E,F,G,H,J,K,L,M,N,O,P same-color
    class LEGEND1 legend

    classDef same-color fill:#99ccff,stroke:#000,stroke-width:2px;
    classDef red-path fill:#ff6666,stroke:#000,stroke-width:2px;
    classDef legend fill:#ffffff,stroke:#000,stroke-width:1px,font-style:italic;

For any proof, the MergeRollup circuit can check if the current proof is on a given provers VRF path, and only pay rewards if it is. This means that a large prover will have to prove a significant amount of sub-trees for free if they want to produce the full rollup, without including other provers. For the burn based model as you proposed, you could only include the score if it is on the VRF path.

7 Likes
8

Clear as day, thanks for taking the time @jaosef! The tree traversal made sense, the part I was missing was how it related to the total payout.

4 Likes
9

If bandwidth costs are material, rational operators won’t bother syncing it at all (opting instead for a centralized third party). Large transaction sizes are a strong argument for PBS, with access to many mempools being a more important specialized activity.

And censorship issues (otherwise just use L1-sequencing). Without PBS inclusion-lists, forcing trasactions is quite expensive (L1 proof gas).

Yes. That proposal uses simple leader election because Fernet is currently broken.

Let me explain the bribery attack:
A malicious party deploys BribeContract to L1. This contract reads L2, and pays out to all provers for a block whenever a proof is missed.
I claim that as long as BribeContract holds prover-block-reward, rational provers will not prove the current block.
This is because prover-block-reward (bribe) > prover-block-reward - compute costs (honest).

I see. This allows sequencers to halt the chain for proof-time (e.g. 10 min), at the cost of a single block (see bribery attack).
See bond pricing for my suggested level of economic security.

6 Likes
10

I don’t think this attack is feasible. The provers who accept the bribe will be slashed, see below.

This means the Bribe contract will need to be funded with the prover-block-reward and sufficient capital to compensate all provers who could be slashed via the in-activity slash. For a block of size 2^10 (1000 txs) that is 2048 provers. The point of a prover staking is to ensure liveness, so the BribeContract would have to overcome a significant slash.

1 Like
11

They will just do it 2 times in a row.

Moreover I claim that if you try to slash provers the first time, then suddenly the sequencer can just threaten to withhold the data (because they can’t be slashed, and provers can).

1 Like
12

I suggest slashing all sequencer+provers if a proof is missed.

This way, the cost to halt-bribe is sequencer stake, rather than sequencer-reward/prover-reward, and it improves cooperation incentives.

Remaining concerns:

  • The threat of data withholding by sequencers/provers
    • even if unfavored in equilibrium, it may cause centralization pressure to distribute the risk
  • A maximum halt-bribe of S is considerably lower than PBS (S * block-rate * miss-frecency)
  • The security is S, but the slash is S + S * N
    • This is inefficient, and gives a multiplier of N advantage to economic adversaries (burn S to cause S*N harm)
  • High operating cost centralization effects on sequencers
3 Likes
13

Some questions @jaosef .

Regarding the binary tree approach. In the example you give, are there 16 different provers, each providing a proof at every level of the tree? Each level up the tree will have twice as many duplicate proofs as the one below it. Do all of the provers get paid for every level?

Also on the binary tree approach. If we are selecting the committee based on lowest VRF, wouldn’t this trend towards the committee comprising VRFs with lower values in the top n bits creating a biased distribution across the proof tree?

Have you thought about how you would orchestrate the proving of public VM and kernel circuit proofs?

And have you thought about fee payments? There are potentially a lot of provers to compensate per block.

3 Likes
14

I think this will need some modelling, the binary tree approach, just provides a path for the proofs a given prover “can” be paid for. With the binary tree model, you can just do faster prover wins at the higher levels, but ensure that all provers can participate at lower levels. @dan-aztec may have more thoughts.

The issue you describe is not present in Option 2: Sorted VRFs, here the network intentionally picks twice as many provers, and reduces the proving committee for each level of the tree to coordinate, and reduce redundancy. In this model, I would expect all proofs to be incentivised.

This is a good point, we may want to truncate the last N bits instead.

For all models, with more than 1 prover payment, per block I would imagine that prover payments are claimed on L1 in a pull model by the prover.

Each rollup would tally the contributions of each prover, and record in the rollup state. A prover has a way to claim this on L1 with a transaction. I will do a separate write up on this, as it could benefit multiple proposals.

5 Likes
15

Would you be open to a call to discuss this further as you have thought deeply about it? You are free to keep your camera off / remain Anon.

If so please grab some time here: Calendly - Joe Andrews

4 Likes