Distributed Proof Generation Specification on top of a consensus protocol like Ethereum

Overview

This specification defines a distributed proof generation protocol integrated with Ethereum (or any consensus protocol), introducing two distinct roles:

• Validators: Existing Ethereum validators who participate in block consensus and verify submitted zk-proofs.
• Provers: A new role, separate from validators, responsible for generating zk-proofs using GPUs. Provers are required to stake separately from Ethereum validators.

The system is designed to ensure timely, redundant, and verifiable proof generation through an incentivized multi-phase protocol (T1–T5).

Variables

// Numbers needs to be adjusted, they are just some initial ideas.PROVERS_PER_PROOF = 200PROVERS_PER_AGGPROOF = 5REWARD_FULL_PROOF_PROVER_T1 = 9000 // Reward received by each selected prover in T1 if a valid FullProof is submitted.REWARD_FULL_PROOF_SENDER_T1 = 50 // Reward received by the prover who sends a valid FullProof in T1.REWARD_FULL_PROOF_VALIDATOR_T1 = 1000REWARD_T1_VALIDATOR = 3PENALTY_T1_PROVER = -1REWARD_FULL_PROOF_PROVER_T2 = 8000REWARD_FULL_PROOF_SENDER_T2 = 40REWARD_FULL_PROOF_VALIDATOR_T2 = 900REWARD_T2_VALIDATOR = 3PENALTY_T2_PROVER = -3REWARD_PROVER_REUSING_T3 = 40REWARD_PROVER_REUSED_T3 = 40REWARD_PROVER_T3 = 50REWARD_VALIDATOR_T3 = 1PENALTY_PROVER_T3 = -1PENALTY_PROVER_NOTREUSED_T3 = -1REWARD_PROVER_REUSING_T4 = 30REWARD_PROVER_REUSED_T4 = 30REWARD_PROVER_T4 = 40REWARD_VALIDATOR_T4 = 1PENALTY_PROVER_T4 = -2PENALTY_PROVER_NOTREUSED_T4 = -1REWARD_PROVER_REUSING_T5 = 20REWARD_PROVER_REUSED_T5 = 20REWARD_PROVER_T5 = 40REWARD_VALIDATOR_T5 = 1PENALTY_PROVER_T5 = -4PENALTY_PROVER_NOTREUSED_T5 = -1REWARD_AGG_PROOF_PROVER = 50REWARD_AGG_PROOF_VALIDATOR = 3

Prover Selection and Assignment

• For each new block, a deterministically random subset of provers is selected using a mechanism such as RANDAO.
• The number of selected provers depends on the block’s gas usage:

num_provers_selected = Min(PROVERS_PER_PROOF, availableProvers / 2)

• Each selected prover is randomly assigned a set of partial proofs (sub-tasks) to generate, distributed with a redundancy factor:

num_airs_assigned = (num_of_partial_proofs / num_provers_selected) * redundancy_factor

• The assigned partial_proofs of each selected prover are determined random-deterministically after the count & plan phase.
• Provers with a strong history of valid submissions may have an increased (but bounded) probability of being selected in future rounds.
• A prover may only be assigned to one proof at a time.

Multi-phase Proof Generation

T1: Challenge Commitment Phase

• All selected provers must:

  • Commit to the signed challenge (e.g., a polynomial commitment of the sub-AIRs they are responsible for constructing).
  • Optionally submit a full proof.

• Only one transaction per prover is allowed. The proof must include the prover’s public key as a public output to prevent proof stealing.

Incentives:

• If a valid full proof is submitted in T1:

  • REWARD_FULL_PROOF_PROVER_T1 for each selected prover.
  • REWARD_FULL_PROOF_VALIDATOR_T1 for the validator.
  • REWARD_FULL_PROOF_SENDER_T1 extra for the prover submitting it.

• Otherwise:

  • REWARD_T1_VALIDATOR × valid commitments for validators.
  • PENALTY_T1_PROVER for provers who fail to commit.

T2: Partial Proof Submission Phase

• All selected provers must:
  • Submit their partial proof, referencing the challenges from T1.
  • Optionally submit a full proof.

Incentives:

• If a valid full proof is submitted:

  • REWARD_FULL_PROOF_PROVER_T2 for each selected prover.
  • REWARD_FULL_PROOF_VALIDATOR_T2 for validators.
  • REWARD_FULL_PROOF_SENDER_T2 extra for the submitting prover.

• Otherwise:

  • REWARD_T2_PROVER for provers submitting valid partial proofs.
  • PENALTY_T2_PROVER for failed submissions.
  • REWARD_T2_VALIDATOR × valid partials for validators.

T3: Full Proof Aggregation Phase

• Any prover may submit a full proof, including a BloomHash summarizing reused partial proofs.

Rewards:

• REWARD_PROVER_REUSING_T3 × reused partials
• REWARD_PROVER_REUSED_T3 × times reused by others
• PENALTY_PROVER_NOTREUSED_T3 × times not reused by others
• If many valid full proofs are submitted, the above rewards are averaged among them.
• REWARD_PROVER_T3 for the submitting prover.
• REWARD_VALIDATOR_T3 × valid full proofs
• PENALTY_PROVER_T3 for non-participation.

T4 / T5: Fallback Aggregation Phases

• If T3 fails to finalize a valid proof:
  • Enter T4, then T5 if needed.
  • Retry with the same or new prover set (if T5 fails).
  • Rewards/Penalties are as in T3 but adjusted (decreased/increased) by a defined percentage.

Extension for Multiple Sub-blocks (Gigagas)

• The number of sub-blocks is limited by system caps and prover availability.
• One prover set is assigned per sub-block. The protocol above applies independently per sub-block.
• A group of PROVERS_PER_AGGPROOF provers is also selected to aggregate sub-blocks into a full block.

In T1:

• Selected provers may submit an AggProof for the block.

Incentives:

• REWARD_AGG_PROOF_PROVER per aggregator prover.
• REWARD_AGG_PROOF_VALIDATOR per validator including an AggProof.