Estimate proving costs for Risc0 programs

[christam96]

Estimate Proving Costs for Risc0 Programs

Estimate the cost of a RISC Zero program before submitting real workloads to Bonsol,

as the cost of proof generation is proportional to the number of cycles and segments used (risc0 docs).

Motivation

We want a fair pricing mechanism for Bonsol execution requests, where buyers provide an adequate tip to provers for accepting their request and generating a proof of their program. This would involve having a ballpark figure for how to price proofs in an open market so buyers/sellers can agree on a price often and quickly.

Approach

Use executor statistics, which tell us how computationally expensive a program is. These include:

• Total Cycles
• Session Cycle
• Segments Count
• Execution time

Total Cycles and Segments Count should contribute to a model for estimating the proof cost, where cycles indicate the total number of operations to be performed and segments indicate how parallelizable the program is. The hard part is converting these statistics to a dollar amount for proof generation, since provers will have unique hardware configs.

Short Game

One approach could be to price proofs naively in order to get the market up and running. This might involve estimating a base or minimum cost for proof generation, and then adding a tip on top to incentivize provers. The tip could follow a bonding curve that diminishes over time, incentivizing provers to act quickly. For example, we could use the following equation:

$$P(t) = C_b + T_0 \cdot e^{-kt}$$

Where:

• $$P(t)$$ is the price of the proof at time $$t$$
• $$C_b$$ is the base or minimum cost for proof generation
• $$T_0$$ is the initial maximum tip amount
• $$k$$ is the decay rate constant
• $$t$$ is the time elapsed since the proof request was made

Again the tip follows a bonding curve (exponential decay) that diminishes over time.

Considerations

1. The base cost $$C_b$$ should be set to cover the minimum expenses for proof generation
2. $$T_0$$ can be adjusted to provide an attractive initial incentive for provers
3. The decay rate $$k$$ can be tuned to depending on the urgency of proof generation with a reasonable time window for provers to respond

(1) should be done by the protocol. (2) and (3) can be done by the user making the execution request.

Simulation

Next Steps (after discussion)

• Determine appropriate values for $$C_b$$ based on benchmarks
• Allow users to specify $$T_0$$ and $$k$$ when making execution requests
• Think about how to track the effectiveness of this strategy

Long Game

Since proof pricing will be a requirement in all proving marketplaces (outside Bonsol), it may be worth coming up with a systematic approach to collecting data points on proving costs. Keeping in my these costs will change over time as hardware and incentives change...

[austbot]

Thanks for the write up,, agree that we need a way to approach this.

Current State.

The basic flow of bonsol is

1. Image deployment
2. execution request
3. claim
4. prove

Currently Bonsol executes the compute and proves it in the same "unit" of code. After resolving inputs it simply tries to execute and prove as fast as possible. Note that private imputs that use the private data server method cannot be resolved until after a claim.
To estimate compute we simply look at the size of the image and then the size of the inputs, nodes have static configuration to accept or reject image deployments or execution requests based on the size of the image or inputs respectively

Prover Cost

The cost to the prover goes beyond proving time and opportunity cost. Its also solana priority fees, it may also be necessary to have the median fee for the claim and proving requests be a factor in the decision to prove something.
What makes this tricky is that we use the accounts involved in a transaction to calculate fees, so we must also include the callback program and extra accounts.

Variables needed to estimate cost

Thinking through this from a software architecture perspective we would benefit from having the following cost variables available at the time of deciding to claim or provide a price.

• Image compute estimate(segments to prove and runtime of execution)
• expiry of execution request
• tip
• size of inputs
• type of inputs
• claim dynamic fee
• execution request proof submission dynamic fee

In order to get a compute estimate we either need to have run the image before, rely on some new bonsol system where those metrics are published, or run a simulation over the image.

In the former, at an early stage of the bonsol network with low load this equates to no knowledge of the compute estimate,
in the second scenario we need some verifiability because we must assume that nodes will cheat, in the final scenario how to we get inputs that accurately represent the compute, especially in the case of the public proof input type which will require proving the dependent image which may not be available.

Given that we cannot trust the developer to tell us what the compute estimate is , and we wont have inputs to test, we must figure out a way to test the image for an initial execution cost estimate.
There are a few things we can look at without running the image, size of the elf, the pages in the MemoryImage, the PageTable info.
These may give an indication on the order of magnitude but not a perfect estimation by any means.

Solution Constraints

Since Bonsol attempts to allow provers to differentiate and be more profitable than some base segment proving reward we don't want to simply have provers connect to some machine that has already run the execution over the inputs and is sending out segments to be proven.

Similar problem space

This problem is very similar to the problem of simulation of vm executions on blockchain networks. In solana you can simulate a transaction to see what it will do, and also to see how much compute was used. Currently developers benefit from placing a marker in their instruction that says "this transaction will not use more than X compute cycles". If it does, the transaction automatically fails. This results in a loss of the signature fee, but the validator still gets a reward for packing it into a block. Because solana relies on re executing the vms and consensus, the incentive for the validator to just say that every transaction has busted the limit and therefore is a failure is handled.

Possible Solutions for the first exection

1. Expect the developer to give a compute estimate in the deployment. In this case we allow the developer to run a local simulation of their program over test inputs and commit to an upper bound on the number of segments and cycles that this Image(zkprogram) will use. This commitment will be made at deployment, and perhaps can be updated in the future.
   In this solution. In this solution we will take ideas from solution 2 to separate execution from proving. Note the developer wont be required to submit a proof that they ran the image, but they will have an incentive to put the right values or provers will never claim their execution. In this solution which goes along well with your proposed base fee instead of the node getting executor stats, it will be the developer.

2. Separate Proving into Execution and Proving in to two steps, expecting the claiming node to have decided to claim based on naive heuristics, then upon seeing the number of segments, time it took to compute and having input from fees, it can decide to revoke the claim which will cost a signature fee. Other interested claimers can then do the same. The node can have its own timeouts and limits configured that affect the initial execution stage.
   Modification: this solution may benefit from a claim order where all claimers essentially are accepted but the claim order determines who can submit the proof at the given slots.

3. There may be some areas to explore here such as a single claimer or auction winner that distributes segments to be proven and uses MPC to ensure that some guarantee the prover who proved the segment will be paid upon verification of the proof. Given that we also may ask more of the provers in due time such as , being a node in a multi party tls session proof, handing multiple zk scheme types setting up the ground work for nodes to securely communicate and multiple nodes to gain reward from a single execution request may be needed anyway.

4. Remove the notion of claiming, and instead change Bonsol to take a leader style architecture similar to solana. In this approach instead of a node claiming the compute, it is assigned to them based on some factor such as their position in the schedule, history of proving. This node has the right to prove until X slot, or it will be given to someone else. This solution simply spreads out the

Lets discuss other solutions and pros/cons of the proposed ones.

[christam96]

1. Expect the developer to give a compute estimate in the deployment.

Curious how much variable length/type inputs affect the execution stats. Is it reasonable to put the onus on developers to anticipate how the zk program will be used in the future? What if we consider committing to executor stats based on specific inputs in execution requests? This would shift the responsibility from developers to whoever is actually requesting the proof.

• Pros:
  • Removes overhead for developers to come up with an accurate test suite (time consuming and error prone)
  • Removes friction for developers to deploy zk programs on Bonsol (better UX, more programs deployed)
  • More accurate heuristics for proving costs? Since heuristics are based on specific inputs
• Cons:
  • Creating an execution request requires access to a computer/server running the zkvm (perhaps generating executor stats can be outsourced?)

[austbot]

I think inputs can affect it alot, I mean each cpu gate is a part of the r0 trace so this can directly impact proving time.
The estimate could be a rough upper bound that they could get with an estimation tool we create. But it may be onerous to have to manage this.

[christam96]

Summarizing our discussion via call, we'll focus on two things for the MVP:

1. Executor node to produce naive heuristics based on executor stats (total cycles, segments count, proof inputs)
2. Decision module for provers to make claims on execution requests

Imagining a workflow where an application (proof requestor) creates an execution request by specifying a ZK program deployed on Bonsol. An executor would download the ELF binary and generate the execution trace corresponding to that execution request, posting the result back to be stored on Bonsol (in some sort of stats registry?). A prover would then inspect the execution stats associated with a request and decide based on the tip, stats, and own business logic, decide whether to fulfill the request.