High-level Overview of Nova

The Fundamentals of Nova and Incrementally Verifiable Computation

Nova is another technique for Incrementally Verifiable Computation (IVC) that uses a cryptographic primitive called a Folding scheme. In simple terms, it is a proving system that uses Folding schemes and KZG polynomial commitments to achieve IVC, which allows proving that a function 𝐹 was repeatedly applied to some initial state 𝑧, producing a sequence of states 𝑧, 𝐹(𝑧), 𝐹(𝐹(𝑧)), etc.

This section will provide a high-level description of the Nova technique and how it works.

Incrementally Verifiable Computation (IVC)

To understand Nova better, it is essential to understand IVC. IVC is a technique that allows proving that a function was repeatedly applied to some initial state, producing a sequence of states. The primary goal of IVC is to combine two cases of a given NP problem into one case.

How Nova Works

If 𝐸 is the zero vector and 𝑒 = 1, then we have 𝐴𝑧 Γ— 𝐡𝑧 = 𝐢𝑧. Namely, any R1CS can also be seen as a relaxed R1CS. Relaxed R1CS keeps the property that it is NP-complete, which means that we can change any NP problem to it. We want the folding scheme to combine two cases of R1CS with the same matrices 𝐴, 𝐡, 𝐢 into one case. Each R1CS has its own instance-witness pairs (that is, public and private data), 𝑧𝑖 = (𝑀𝑖 , π‘₯𝑖), and we want to make a new 𝑧 = (𝑀, π‘₯) that meets the R1CS system of equations with 𝐴, 𝐡, 𝐢, such that this also means that each 𝑧𝑖 = (𝑀𝑖 , π‘₯𝑖) does so. One way to do this is by having the verifier pick a random π‘Ÿ and do the following change:

This change would work for linear systems of equations, however since the R1CS is nonlinear, we cannot use this simple method. If we put this into the R1CS then we have the following:

In the relaxed R1CS, the error term 𝐸 will take all the cross-terms made by adding the linear combination, and 𝑒 will take the extra π‘Ÿ term on the right-hand side. To do this,

and both 𝑒, 𝐸 are added to the instance-witness pair.

The main problem is that the prover has to send the witnesses 𝑀1, 𝑀2 to the verifier so that he can calculate 𝐸. To do this, we see both 𝐸 and 𝑀 as witnesses and hide them using polynomial commitment schemes.

Last updated