reducing proof size

[sourdzl]

hi! thanks for this implementation of NOVA for SHA-256. Do you have ideas for how to reduce the final compressed proof size? Is something in the hundreds of byte range possible?

or do you think this should be pushed into a second prover/verifier system?

[avras]

Disclaimer: I am not an expert on Nova. Only have a user-level understanding.

I think you will have to use a second prover/verifier system. Like https://github.com/jbaylina/nova-circom-verifier.

Reducing the number of constraints in the step circuit is not going to reduce the proof size below 9 KB. This observation is based on running the minroot example in the Nova repository.

The minroot step circuit has a fixed number of iterations. In each iteration, the step circuit is checking a formula of the form $x_{i+1}^5 = x_i + y_i$ and adds only 3 R1CS constraints. You can verify this by changing the line here first like the following

-  for num_iters_per_step in [1024, 2048, 4096, 8192, 16384, 32768, 65535] {
+ for num_iters_per_step in [1] {

and then to this

- for num_iters_per_step in [1] {
+ for num_iters_per_step in [2] {

Increasing the number of iterations per step from 1 to 2, increases the number of constraints per step in the primary circuit from 9819 to 9822. I am guessing that the remaining ~9800 constraints are used for the folding operation.

Even for such a simple step circuit, the proof size is 9507 bytes.

$ cargo run -r --example minroot
    Finished release [optimized] target(s) in 0.07s
     Running `target/release/examples/minroot`
Nova-based VDF with MinRoot delay function
=========================================================
Proving 1 iterations of MinRoot per step
Producing public parameters...
PublicParams::setup, took 3.262475495s 
Number of constraints per step (primary circuit): 9819
Number of constraints per step (secondary circuit): 10347
Number of variables per step (primary circuit): 9813
Number of variables per step (secondary circuit): 10329
Generating a RecursiveSNARK...
RecursiveSNARK::prove_step 0: true, took 83.63359ms 
RecursiveSNARK::prove_step 1: true, took 121.375667ms 
RecursiveSNARK::prove_step 2: true, took 138.228083ms 
RecursiveSNARK::prove_step 3: true, took 137.443676ms 
RecursiveSNARK::prove_step 4: true, took 134.578872ms 
RecursiveSNARK::prove_step 5: true, took 139.643275ms 
RecursiveSNARK::prove_step 6: true, took 135.353484ms 
RecursiveSNARK::prove_step 7: true, took 137.986039ms 
RecursiveSNARK::prove_step 8: true, took 144.31789ms 
RecursiveSNARK::prove_step 9: true, took 145.768437ms 
Verifying a RecursiveSNARK...
RecursiveSNARK::verify: true, took 124.476485ms
Generating a CompressedSNARK using Spartan with IPA-PC...
CompressedSNARK::prove: true, took 2.157020991s
CompressedSNARK::len 9507 bytes
Verifying a CompressedSNARK...
CompressedSNARK::verify: true, took 93.674294ms
=========================================================

Coming back to your question. Even if we reduce the number of constraints in the SHA-256 step circuit using some clever tricks (like creating a step out of the inner loop of the compression function), we cannot hope to reduce the proof below 9 KB.

I hope this helps. Thanks for your interest!

[avras]

Closing this issue. See thread by Leonardo on an effort to verify Nova proofs of Ethereum https://twitter.com/leonardoalt/status/1671962194081095689

For completeness, let me also link to the comment by Wilson Nguyen about a possible malleability attack on Nova. https://twitter.com/mercysjest/status/1671990289282789388.