Nova
Presentation: https://www.youtube.com/watch?v=dDsAroTRaFI
Problem Statement
How to prove ? The naïve approach would be unrolling this into a single circuit and proving with some SNARK. But this would require a lot of memory and the proof is not incrementally updatable. Also, the verifier's time may depend on . To tackle this problem more efficiently, a new approach called incrementally-verifiable computation was introduced in Val08, BCTV14. In IVC, an augmented circuit is introduced which ensures correct execution of as well as some verifier circuit which can now be used to inductively prove the correct execution of .
Folding R1CS
Standard R1CS
Given three matrices and public input , does there exist witness such that: where . Here, we use instead of vector for public input since in Nova, it is typically a hash value.
An attempt to fold R1CS
Suppose prover holds and and verifier holds and .
Verifier picks random and send it to the prover.
Verifier computes so the folded instance becomes .
Prover computes the folded witness .

Unfortunately there exists many such that for .
This shows 3 issues:
Need to account the cross-term:
Mismatch in coefficient of
Even since
To address first issue, we add error vector which absorbs the cross-terms. To handle the second and third issues, we introduce a scalar , which absorbs an extra factor of in and in . We refer to the R1CS with these additional terms as relaxed R1CS.
Relaxed R1CS
Definition 11 from the paper. Consider a finite field . Let the public parameters consist of size bounds where . The relaxed R1CS structure consists of sparse matrices with at most non-zero values in each matrix. A relaxed R1CS instance consists of an error vector , a scalar , and public inputs and outputs . An instance is satisfied by a witness if
where . In this setup, notice that if and then it is same as standard R1CS.
Folding relaxed R1CS
To fold relaxed R1CS, the prover and verifier additionally compute:
Now, the folded instance is .

Now, you will be able get where . But there is still a few issues remaining:
The verifier has to compute which has multiple large matrix multiplications so it is non-trivial.
Verifier cannot check if is indeed the outcome of so it cannot be zero-knowledge because verifier needs to know and to fully verify.
To circumvent these issues, we use succinct and hiding additive homomorphic commitments to and in the instance, and treat both and as the witness. We refer to this variant as committed relaxed R1CS.
Committed Relaxed R1CS
Definition 12 from the paper. Consider a finite field and a commitment scheme over . Let the public parameters consist of size bounds where , and commitment parameters and for vectors of size and respectively. The committed relaxed R1CS structure consists of sparse matrices with at most non-zero entries in each matrix. A committed relaxed R1CS instance is a tuple , where and are commitments, , and are public inputs and outputs. An instance is satisfied by a witness if :
, where .
A Folding Scheme for Committed Relaxed R1CS
Suppose prover holds and . The verifier takes two committed instances and . Let and .
Prover sends where and
Verifier sends challenge .
Prover and verifier computes folded instance where
Prover computes the folded witness where

Proof of completeness. To prove completeness, we must show that for any valid witness pairs, the folding verifier will accept the folded instance. For the folded witness to satisfy the constraint, we must have:
Distributing, we get:
Aggregating by powers of , we must have:
Since and are satisfying witnesses, we have:
which holds by construction.
Proof of soundness. To prove soundness, we must show that for any wrongly constructed folded instance will be rejected by the folding verifier. The intuition is we can extract a satisfying witness from the proof if the verification passes. TODO: elaborate how we can extract it.
Theorem 3 from the paper. The above construction is a public-coin folding scheme for committed relaxed R1CS with perfect completeness, knowledge soundness, and zero-knowledge.
From Folding to IVC
We constructed a way to fold two R1CS instances into one but now what? How do we incrementally prove and verify with this? To prove that , for some count , initial input , and output , we use an augmented constraint system which in addition to invoking , performs additional bookkeeping to fold proofs of prior invocations of itself. A simple version of this augmented constraint system would take two committed relaxed R1CS instances and as an input where represents the correct execution of previous invocations and represents correct execution of -th invocation. Mainly, it performs two tasks:
(State transition) Execute a step of the incremental computation: instance contains which the augmented constraint system uses to output .
(Folding) Fold and into a single R1CS instance .

IVC over a single curve
First, let's understand how we can construct it over a single curve. What we need to constrain within this is:
Check previous state transitions are correct
(checks if error term is 0 and scalar is 1)
Check if . It might be confusing since we don't use hash here normally. To prove we would typically have . But for IVC, we need to keep track of the accumulated claim as well so we use hash here to keep the input size constant.
Apply the state transition and accumulate instances.
Check if
Accumulate into
Generate the instance for next state transitions.
Set
Generate instance which resembles correct execution of this step. Notice that the error term should be 0 and scalar should be 1 since it is not a folded instance.

IVC Verification
Given a proof , the IVC verification will do the following:
satisfy .
Conclusion
In proof-of-concept benchmarks, Nova was shown to be 4x faster at proving 10000 recursive SHA256 hashes than Halo2 (KZG) and memory usage is constant with respect to number of iterations in Nova while in Halo2 (KZG), the memory usage increases almost linearly with respect to number of iterations. This result is taken from: https://hackmd.io/0gVClQ9IQiSXHYAK0Up9hg?view
References
Written by BATZORIG ZORIGOO from A41
Last updated