Benedikt Bünz
There has been a lot of recent development in accumulation/folding schemes. One of the primary goals is to reduce the size of this recursive circuit needed to verify the accumulation. This short note gives a small improvement on Nova that yields a recursive circuit of just 1 Group scalar multiplication and a constant number of hashes and field operations.
Current state of folding schemes
There are several folding schemes. We give a brief overview of the current state of the art and their respective accumulation verifiers (which have to be implemented as part of the IVC circuit).
| Scheme | exps | and ops | Supported degree | Multi acc. |
|---|---|---|---|---|
| Nova | 2 | O(1) | 2 | No |
| Protostar | 3 | O(d) | d | No |
| Protogalaxy | 1 | O(log(l)+d) | d | Yes |
| Mova | 1 | O(log(l)) | 2 | Yes |
| Ova | 1 | O(1) | 2 | No |
The table displays several folding schemes and different components of the accumulation verifier cost: ops measures the number of group scalar multiplications (usually the most expensive part of the circuit). and ops measures the number of field ops and the number/size of the hash computations. They tend to be the same. Here is the number of verification checks done in the circuit. Supported degree states what degree is supported by the scheme. Nova, Mova and Ova all support R1CS a degree 2 scheme that can implement addition and multiplication gates. Multi-acc says whether the scheme can be used to accumulate many accumulators into one and build PCD. A variant of Protostar, Protogalaxy and Nova, all achieved accumulation schemes with only a single group operation. However, all these schemes require at least hashes, where is the number of constraints. We present an improvement that only requires a constant number of hashes or equivalently halves the number of group operations done by the Nova accumulatino verifier.
Nova recap
Nova builds an accumulation scheme for R1CS in the following way. Consider a group with hard discrete logarithm and two sets of rangdom generators and . Consider the R1CS matrices . A fresh proof consists of a commitment to a vector , such that
. andNote that technically there also needs to be a public input prepended to but for simplicity we will assume that .
An accumulator consists of and such that
. andThe accumulation scheme takes a fresh proof and an accumulator and produces a new accumulator using the following algorithm:
Define . Define Define . Note that is a degree polynomial but the highest coefficient is . Let be the degree 1 coefficient of . Compute Compute ( is modeled as a random oracle) Compute Compute Compute Compute Output
The verifier receives as input and computes
Output as the new accumulator instance
Ova
Ova is a slight modification to Nova that shaves off 1 group operation and a few hashes. The key idea is that we can commit to and in one commitment. This slightly breaks the abstraction between the IVC scheme and the accumulation scheme. We assume that the accumulation prover receives as input which proves the current step of the computation and that the previous accumulation was performed correctly. Note that can be generated without being aware of or . Alternatively the accumulation prover can receive the commitment to as input and add to it the commitment to . This yields a commitment to the concattenated vector . This works because both and are multiplied by the same challenge in Nova.
Construction
We assume that the discrete log between and is hard to compute.
Fresh proofs are as in Nova. Accumulators consists of a single commitment a vector and a scalar , such that
and
The accumulation prover operates as follows:
Receive as input Compute as in Nova Compute Compute Output
The accumulation verifier receives as input
Compute Compute Compute
The decider receives a commitment , a vector and a scalar and computes and checks that
Completeness sketch
Completeness holds as the scheme is identical to Nova but using the same commitment for and which are both multiplied by the same challenge .
Soundness sketch
We show that the underlying interactive scheme is -special-sound (using a Protostar analysis). Let . Given two transcripts and such that
for We can use these to compute openings for and , i.e.:Given a third accepting transcript we have that for , otherwise one can find a non zero vector , such that , which breaks the DLOG assumption in . Since R1CS is degree functions this shows that they hold for any , i.e. for This implies that and .
Applications
Ova yields an IVC scheme through standard compilers (e.g. BCLMS). Interestingly, it does not yield a PCD scheme. PCD is the extension of IVC from line graphs to arbitrary dags. A key limitation is that Ova takes advantage of the fact that there is exactly one proof with error term and one accumulator.
On the other hand, Ova, likely, has the smallest recursion overhead of any known scheme. An interesting application would be to Cyclefold (https://eprint.iacr.org/2023/1192) where a small R1CS circuit for computing group operations is paired with a more expressive circuit that computes the underlying predicate. Insted of using Nova to compute the group-expoentiation circuit one could use Ova. Cyclefold reports about 10k group operations for implementing the Nova verifier in an R1CS instance. This could be reduced by almost 50% using Ova.
