Prover Mechanism Notes

Applications will pursue decentralized proving for a few reasons:

1. Liveness: Multiple provers ensure that the protocol operates reliably and doesn’t face downtime if some provers are temporarily unavailable.
2. Censorship Resistance: Having more provers improves censorship resistance. A small prover set could refuse to prove certain types of transactions.
3. Competition: A larger prover set can strengthen market pressures for operators to create faster and cheaper proofs.

Proof Networks

• Internalizing the prover role improves native token utility by allowing a protocol to leverage its own token for staking and prover incentivization.
• It also provides applications with greater sovereignty, rather than creating an external point of failure.
• There is often only a single proof request which must be satisfied by the prover set at a time - How about multiple proof requests?
• Can users pay for fast proof generation?

Proof Markets

Proof Market like those under development by =nil;, RiscZero, and Marlin provides out-of-the-box decentralized proving. By sharing provers across applications:

• Maximize hardware utilization
• Provers can be repurposed whenever one application does not immediately need a proof to be generated.
• Proofs with long generation times will need ZKP acceleration through specialized hardware and other optimizations.
• The market also needs to service fast proof generation for applications and users willing to pay for it.
• Proof markets want to be as flexible as possible to satisfy different applications’ needs.

Designing proof markets that are performant, decentralized, and flexible enough to power an array of ZK applications is a difficult, underexplored area of research.

Prover Selection

(How to select between from multiple provers)

1. Stake-based

   • Selected at random, weighed by their value of staked tokens
   • Downside is holding of capital
   • Less importance on accelerating proof generation since provers are not selected based on their proving speeds
   • Placing less pressure on provers to compete on performance creates space for collaboration between operators. Collaboration typically includes knowledge sharing, like the dissemination of new techniques to accelerate proof generation, or guidance for new operators on how to start proving.

2. Proof mining

   • The network provides incentives to miners to accelerate ZKP generation, which ultimately benefits the network. When miners are encouraged to find more efficient ways of generating proofs, they can reduce their operational costs. This, in turn, can lead to lower transaction fees for users. Proof mining has been pioneered by Aleo.
   • It requires some capital to accumulate machines and cover energy costs to produce more proofs.

3. Proof racing

   • Vulnerable to winner-takes-all dynamics
   • Centralization can be reduced by splitting up the proof reward across the first n operators who generate a valid proof or introducing some randomness into which proof is accepted. Yet even in this case, the fastest operator can simply run multiple machines to capture the other revenue.
   • Result in redundant computation, but provide better liveness assurances since you do not need to worry about a prover missing the slot they were selected for.
   • Analogous to MEV searching, where entities are more secretive and adversarial to maintain their competitive edge.

Should we look at other consensus research?

Proving Method

• Single party proving: single party winning the right to prove at a given slot
• Distributed proving: proof generation is distributed between multiple parties who work together to generate a single output. The difference between two?
  • Federated proving network which splits a proof into many smaller statements that can be proved separately, then recursively proved up to a single statement in a tree-like structure.
  • zkBridge, which proposed a new ZKP protocol that enables proofs to be easily distributed across machines, and has already been deployed by Polyhedra. Distributed proving is inherently easier to decentralize and can significantly improve the proof generation speed. Each group of participants can form a computing cluster and join proof mining or racing. Rewards can be divided evenly according to their contribution to the cluster.
  • Provers each prove a small number of transactions and then recursively aggregate them together face network bandwidth limitations. The sequential nature of rollup transactions also makes it difficult to parallelize — proofs for previous transactions must be included before proofs for subsequent transactions. If a prover does not make its proof available, the final proof cannot be constructed.

Matchmaking

Designing the matchmaking engine — that is, defining the rules by which provers are matched with proof requests, connecting supply and demand in the market.

• Auctions involve provers bidding on proof requests to determine which prover wins the right to generate the proof. A challenge with auctions is that if the winning bid fails to return the proof, the auction must be re-run.
  • If it were known that the second highest bidder would have the opportunity to step in if the winning bidder fails to deliver the proof, this could lead to strategic bidding behavior. It's generally more straightforward to re-run the auction if the winning bidder fails to deliver the proof.
• Orderbooks for buying and selling proofs work by matching bids and asks based on price and turnaround time criteria. They are well-suited for situations where quick matching and execution of transactions are essential, such as in low-latency use-cases to match a bid with an ask in this orderbook system, two conditions must be met:
  • Bid Price > Ask Price: The price at which the application is willing to pay for the proof (bid price) must be higher than the price at which the prover is willing to sell it (ask price).
  • Bid Turnaround Time <= Ask Turnaround Time: The time within which the application wants to receive the proof (bid's requested time) must be shorter or equal to the time within which the prover can deliver it (ask's turnaround time).
• Off-chain negotiation used by Filecoin’s decentralized storage market
• Reverse auction used by Akash’s decentralized cloud computing market when workload latency isn’t as important.

Incentives and Disincentives

• Staking
• Slashing
  • False proof generation
  • When it takes too long to generate proof or failure
  • Punishment could be proportional to the proof bid — the higher the bid that gets delayed (and therefore the more economically significant), the larger the punishment
• Reputation system
  • =nil; currently uses a reputation-based system
  • Provers with a history of dishonesty or poor performance are less likely to be matched with bids by the matching engine.
• Proof request bids
  • The protocol could place restrictions on the types of bids certain provers can accept. For example, a prover with an insufficient reputation score could be barred from matching with large bids.
• Token inflation rewards

Attack Vectors

• Sybil attack
• DDOS attack
• Proof delay attacks: By delaying or failing to return a proof, provers can expose a protocol or its users to certain economic attacks. Token slashing or reputation score penalties may be insufficient to deter malicious provers if the attack profits are large. In the event of a proof delay, rotating proof generation rights to a new prover can minimize downtime.
• Prover undercutting

The requirements for operators to enter and remain active market participants. These requirements will influence operator diversity, including their size and geographical distribution. Some protocol-level considerations include:

• Will provers need to be whitelisted or will admission be permissionless?
• Will there be a cap on the number of provers who can participate?
• Will provers be required to stake tokens to enter the network?
• Will there be any hardware or performance minimums?
• Will there be limits to how much market share an operator can hold? If so, how is that limit enforced?