This is part of an article series on accumulation, ZK folding, and NOVA:
📓 Part I: Recursive SNARKs and Incrementally Verifiable Computation (IVC)
📓 Part II: Halo and Accumulation
📓 Part III: Nova and Folding (1/2)
📓 Part IV: Nova and Folding (2/2)
In the previous article we saw how folding allows us to fold two instances of a given R1CS structure to a new one in such a way that a prover could convince the verifier that it knows witnesses for the two initial ones if it is able to do so for the folded one.
The principle behind this is to take random linear combinations. There is, however, a certain amount of magic involved: as R1CS are not very complacent to linear combinations, some skilful wizardry is needed to shapeshift them to relaxed R1CS, which are more amenable to linear combinations. In this article we will try to show using the theory of quadratic forms, that this process is in fact very natural: the scalar u comes naturally when homogenizing the quadratic equation, the error term (slack term) corresponds to the value of the resulting quadratic form and the cross term has a natural interpretation in terms of the associated bilinear form. That is a lot of complex terminology, so let’s go through it one step at a time…
A short recap
Let’s start again with a short recap. We encourage you to check out the previous article from the series before you proceed for better context.
Last time we saw that computation can be translated into arithmetic satisfiability problems and introduced one particular intermediate representation, namely Rank 1 Constraint Systems (R1CS). These are systems of quadratic equations of a particular form. More precisely, we have an input vector X and output vector Y (together we call them an instance I), and a witness vector W. Using 1, I and W, we form the vector Z and consider quadratic equations of the form
A(Z) ○ B(Z) = C(Z)
where A(•), B(•) and C(•) correspond to taking fixed linear combinations (called the structure).
In general we have several of these equations (or think of A, B and C as matrices), though we will usually just write down one of them for ease of notation. An instance I is said to be satisfied by a witness W, if all quadratic equations are satisfied by Z = (1, I, W).
The aim in folding is as follows: fix a system of equations (A, B and C, this we called the structure) and suppose you have two instances I₁ and I₂. The prover wants to convince the verifier that it knows witnesses W₁ and W₂ for the two W instances. For this, the prover wants to come up with a new instance (for the same R1CS structure, i.e., for the same set of equations), such that if it can convince the verifier that it knows a witness W for the instance I, then the verifier will be convinced that the prover knows witnesses W₁ and W₂ for the instances I₁ and I₂.
So in some sense the prover comes up with imaginary input and output to the same computation (instance I) such that if it can convince the verifier that it has some witness and correctly performed the computation step in a way to connect the artificial input to the output, the verifier will be convinced that the same holds for the two initial real input-output pairs.
This was elegantly realized in the folding scheme introduced by Kothapalli, Setty and Tzialla.
The power of random linear combinations
The soundness of this scheme is based on the following cool principle of random linear combinations used quite frequently:
If a prover can do something (solve a problem) for arbitrary linear combinations (linear combinations determined by challenges of the verifier, or a version rendered non-interactive using Fiat-Shamir and in practice a random oracle instantiation by a hash function) of two objects, then they can do it for the objects themselves.
That this is sound is usually argued as follows: given the answer to a problem for many random linear combinations of the objects, there is a way to extract an answer for the objects themselves. A prover that can answer one random challenge, can answer many of these, and hence extract a solution to the initial problems (hence it is sound to assume that the prover knows these already).
Now R1CS are quadratic equations and don’t do well with linear combinations unlike homogeneous linear equations. Taking linear combinations of solutions does not yield another solution.The value of a quadratic expression at a linear combination of two points cannot be related easily to its values at these points (or to the corresponding linear combination of these values). Basic results about quadratic forms can provide some remedy.
Making things “linear-like”
Let us start by rewriting our equations as
P(Z) = A(Z) ○ B(Z) — C(Z) = 0
Recall that Z = (1, I, W). Here P(Z) is a multivariate polynomial and satisfying the R1CS corresponds to the polynomial to evaluate to zero. Clearly a linear combination of two zeros of the polynomial P(Z) will in general not be a zero, i.e. it is not true that P(Z₁) = 0 and P(Z₂) = 0 imply that P(r₁• Z₁+ r₂ • Z₂) = 0.
This would be the case if P(Z) would be linear:
P(r₁• Z₁+ r₂ • Z₂) = r₁ • P(Z₁) + r₂ • P(Z₂) = r₁ • 0 + r₂ • 0 = 0
So there will be a certain error. Rather than working with zeros of P(Z), we concentrate on the value of P(Z) at various points. Again, as P(Z) is not linear, its value at Z₁ and at Z₂ cannot easily be related to its value at say r₁• Z₁+ r₂ • Z₂.
A first step is to homogenize the polynomial. The polynomial has degree 2 terms (coming from A(Z) ○ B(Z)) and linear terms (coming not only from C(Z) but also from A(Z) ○ B(Z) as the first entry of Z is z1 = 1), and constant terms.
It would be easier to deal only with quadratic terms (more homogeneous). A way to achieve this is to introduce a new variable u and to multiply each term of P(Z) by an appropriate power of u to make all terms have degree 2.
So we will need one factor of u for terms coming from C(Z), and one or two factor of u for terms coming from A(Z) ○ B(Z) containing one or two instances of z1 = 1 respectively. Hence this process amounts to replacing z1 = 1 by u and multiplying all of C(Z) by u. The result is
Q(Z) = A(Z) ○ B(Z) — u • C(Z) = 0
where now Z = (u, I, W)!
Q(Z) is a degree 2 homogeneous polynomial in the variables of u, I and W.
As all terms have degree 2, we see that
Q(r • Z) = r² • Q(Z)
for any constant r, so it behaves nice (regular) under scalar multiplication. It does however not respect addition. We do not have that
Q(Z₁ + Z₂) = Q(Z₁) + Q(Z₂)
and it is difficult to relate
Q(Z₁ + Z₂), Q(Z₁), Q(Z₂)
for general Z₁ and Z₂.
A short tangent on Quadratic and Bilinear Forms
After homogenization Q(Z) is a polynomial all of whose terms have degree 2. We call this a quadratic form. It is not linear, but we can associate to it a new function, which is “bilinear”. More precisely, define
B ( • , • ) takes two vectors X and Y and it can be shown that it is linear in each of them separately, hence called a bilinear form. So we have
and
Knowing B(X, Y), we can predict how our quadratic form Q(X) will behave under linear combinations. So we can infer Q(r₁X + r₂Y) from Q(X) and Q(Y), almost as if it were linear. From the defining equation for B(X, Y) we have
In particular, we have
Note that Q(r₁X + r₂Y) can be expressed as a linear combination of B(X, Y), Q(X) and Q(Y). This will become important in a bit.
Long story short…
For folding we would like Q(Z) to be linear, which it is not. However if we know B(X, Y) for a particular X and Y, then at least for those X and Y we can pretend it kind of is, i.e. we can write Q(r₁X + r₂Y) as a linear combination of B(X, Y), Q(X) and Q(Y). Knowing B(X, Y), both parties can compute Q(r₁X + r₂Y) from Q(X) and Q(Y). Translating back, they can compute the slack vector corresponding to the random linear combination from the slack vector Eₓ and Eᵧ of the R1CS instances to be folded. Randomness guarantees soundness, as in the linear case: the prover that knows the folded instance in fact knows both instances that are folded at least with very high probability.
The solution is simple…
For the folding of X and Y the prover and verifier use B(X, Y), and the rest is almost as in the linear case. There is, however, one problem: to compute B(X, Y) the verifier would need X and Y themselves, which contain the relevant witnesses. So this would neither be succinct, nor would it have the desired zero-knowledge property. It would in fact just be like sending over whole witnesses, and doing some additional work on top of it.
Commitments save the day
Rather than working with the slack vectors (i.e. the Q(X) and B(X, Y) (which we cannot pass on to the verifier), we work with commitments to them. Remember we mentioned above that the slack vector of the random linear combination can be expressed as a linear combination of the slack vectors of the two instances and B(X, Y)? This will now be very handy. If we use an additively-homomorphic commitment, we can express a commitment to the folded slack vector in terms of the commitment of the slack vectors and commitment of B(X, Y). In other words, taking commitment in the expression above (indicated by bars) we obtain
So instead of sending slack vectors the prover sends commitment to them (along with a commitment to B(X, Y) to allow the verifier to compute commitments for the folded instance). This is called Committed Relaxed R1CS.
Thank you for reading! This marks the end of our initial exploration into Nova and ZK folding schemes. We will continue to write about these topic and plan to continue with an exciting journey through IVC, Sangria, Hypernova, Supernova and many others in the near future.
Read the other articles in this series:
📓 Part I: Recursive SNARKs and Incrementally Verifiable Computation (IVC)
📓 Part II: Halo and Accumulation
📓 Part III: Nova and Folding (1/2)
📓 Part IV: Nova and Folding (2/2)
Connect with us:
Twitter | Lens Protocol | LinkedIn | Github | Request Audit
