A public coin, zero-knowledge Folding Scheme for Committed Relaxed R1CS

The canonical Nova paper introduced a few things:

An "augmented" R1CS structure, called Committed Relaxed R1CS
A "folding scheme" for Committed Relaxed R1CS
A way to turn the folding scheme for Committed Relaxed R1CS into an IVC
A nova-specific zkSNARK, built on top of Spartan to compress and have zero-knowledge IVC proofs; i.e. prove that you know a valid IVC proof without divulging it.

The zero-knowledge Folding Scheme for Committed Relaxed R1CS is the main cryptographic engine that makes the Nova IVC possible and corresponds to points 1 and 2. It is laid out within the paper's section 4, of which this post is a condensed summary.

Motivation

The motivation for folding stems from a prover $\mathcal{P}$ willing to convince a verifier $\mathcal{V}$ that he knows two instance-witness tuples which satisfy a particular R1CS structure. This should be done without $\mathcal{P}$ divulging those witnesses. We will review what this means below.

A trivial way for $\mathcal{V}$ to check whether the two purpoted witnesses of $\mathcal{P}$ are satisfying would be to check each of them. But this isn't satisfying, both from a computation and communication standpoint. Firstly, $\mathcal{P}$ would need to send 2 witnesses and $\mathcal{V}$ would have to check that the R1CS structure holds for both. Secondly, $\mathcal{P}$ would send $\mathcal{V}$ each of those witnesses, making this trivial solution non zero-knowledge.

A folding scheme for committed relaxed R1CS aims to patch this:

It will turn the cost of the trivial solution consisting of checking each of those two witnesses into the cost of checking a single one, computed as a linear combination of the two.
It will be zero-knowledge, keeping $\mathcal{V}$ from knowing what are the two folded witnesses.

Naive R1CS folding

Combining instance-witness pairs linearly

In R1CS, we say that $Z = (W, x, 1)$ is a satisfying instance-witness pair when:

\begin{equation} A \cdot Z \odot B \cdot Z = C \cdot Z \end{equation}

where $A, B, C$ compose the R1CS structure, $W$ is the witness and $x$ a vector of public inputs/outputs. The satisfying tuple $Z$ has $1$ as its last element, a "dummy" variable representing constants. This writeup from Vitalik is a nice introduction to what R1CS is.

In the context of folding, $\mathcal{P}$ will be in possession of two satisfying instance-witness pairs $Z_1 = (W_1, x_1, 1), Z_2 = (W_2, x_2, 1)$ .

A simple cryptographic technique available to $V$ to avoid $P$ from cheating is to send him randomness. This will be of help for folding two R1CS instances. Indeed, $V$ will require from $P$ to perform a random linear combination of the two instance-witness pairs. It will look like this:

\begin{equation} \begin{aligned} x \leftarrow x_1 + r \cdot x_2 \\ W \leftarrow W_1 + r \cdot W_2 \end{aligned} \end{equation}

where $r$ is some random scalar parameter sent by $\mathcal{V}$ . Now, $\mathcal{P}$ ends up with a new, single instance-witness pair $Z = Z_1 + r \cdot Z_2$ .

However, the newly folded $Z$ does not satisfy the canonical R1CS equation of $(1)$ anymore! Indeed, naively plugging it into the R1CS equation yields:

\begin{aligned} A \cdot Z \odot B \cdot Z = A \cdot (Z_1 + r \cdot Z_2 ) \odot B \cdot (Z_1 + r \cdot Z_2 ) \\ = AZ_1 \odot BZ_1 + r \cdot (AZ_1 \odot BZ_2 + AZ_2 + BZ_1) + r^{2} \cdot (AZ_2 \odot BZ_2) \end{aligned}

Now, we end up with a cross-term and a quadratic term. This is not equal to the expected $CZ = CZ_1 + rCZ_2 = AZ_1 \odot BZ_1 + r ( AZ_2 \odot BZ_2)$ .

Also, note that when we take a random linear combination of our two instance-witness tuples we end up with:

\begin{equation} \begin{aligned} Z &= Z_1 + r \cdot Z_2 \\ &= (W_1, x_1, 1) + r \cdot (W_2, x_2, 1) \\ &= (W_1 + r \cdot W_2, x_1 + r \cdot x_2, 1 + r) \\ \end{aligned} \end{equation}

An extra $r$ sneaked in our satisfying instance-witness tuple; the last element is not $1$ anymore!

Absorbing the cross-term and $r$

First, let's introduce an error vector $E = r \cdot (AZ_1 \odot BZ_2 + AZ_2 + BZ_1)$ to account for the corresponding cross-term. Our new R1CS equation is:

A \cdot Z \odot B \cdot Z = C \cdot Z + E

You can see how $E$ will "absorb" the cross-term by plugging it in the above derivation for $A \cdot Z \odot B \cdot Z$ .

Now, let's re-write what we have so far without this cross-term to see what remains to be dealt with:

\begin{aligned} A \cdot Z \odot B \cdot Z &= AZ_1 \odot BZ_1 + r^{2} \cdot (AZ_2 \odot BZ_2) \\ &= CZ_1 + r^{2} \cdot CZ_2 \neq CZ_1 + r CZ_2 \end{aligned}

What's left is to absorb the remaining $r^{2}, r$ terms of $(6)$ and the extra $1+r$ element. To this end, let's introduce a new term, $u$ :

\begin{equation} \begin{aligned} u &\leftarrow u_1 + r \cdot u_2 \end{aligned} \end{equation}

where $u_i \in \mathbb{F}$ .

Let's now see how $E$ and $u$ help us with folding.

Relaxed R1CS

A relaxed R1CS system will be basically R1CS, but equipped with the ability to take linear combinations of satisfying instance-witness pairs.

The relaxed R1CS equation is very similar to canonical R1CS. It says that given an error vector $E$ , an instance-witness tuple $Z = (W, x, u)$ satisfies a relaxed R1CS equation when the following holds:

\begin{aligned} A \cdot Z \odot B \cdot Z = u \cdot (C \cdot Z) + E \end{aligned}

In this context, on top of folding two satisfying $Z_1$ , $Z_2$ , we will also need to combine two error vectors $E_1$ , $E_2$ together to compute a new folded vector $E$ :

\begin{aligned} E &\leftarrow E_1 + r \cdot (AZ_1 \odot BZ_2 + AZ_2 \odot BZ_1 - u_1CZ_2 + u_2CZ_1) + r^{2} \cdot E_2 \end{aligned}

As explained above, this folded $E$ will absorb the cross-term that pops up when naively plugging in a linear combination of the two instance-witness pairs $Z_1, Z_2$ in the original R1CS equation.

Let's try again taking a random linear combination of two satisfying relaxed R1CS witness-instance pairs. Let's define $Z_1 = (W_1, x_1, u_1), Z_2 = (W_2, x_2, u_2)$ to be two satisfying instance-witness pairs and set $Z = Z_1 + r \cdot Z_2$ . We get:

\begin{aligned} A \cdot Z \odot B \cdot Z &= AZ_1 \odot BZ_1 + r \cdot (AZ_1 \odot BZ_2 + AZ_2 + BZ_1) + r^{2} \cdot (AZ_2 \odot BZ_2) \\ &= (u_1CZ_1 + E_1) + r \cdot (AZ_1 \odot BZ_2 + AZ_2 + BZ_1) + r^{2} \cdot (u_2CZ_2 + E_2) \\ &= (u_1 + r \cdot u_2) \cdot C(Z_1 + rZ_2) + E \\ &= uCZ + E \end{aligned}

The pen-ultimate equality holds since $E$ has a term $r \cdot ([\dots] - ru_1CZ_2 + ru_2CZ_1)$ . This makes it possible to write the factorization $(u_1 + r \cdot u_2) \cdot C(Z_1 + rZ_2)$ .

You can now observe how the relaxed R1CS equation works, inserting $E$ and $u$ in $(1)$ and thus absorbing the cross and quadratic terms that pop up when taking random linear combinations of two satisfying instance-witness pairs.

Committed Relaxed R1CS

Assume $\mathcal{P}$ knows two satisfying instance-witness pairs $Z_1, Z_2$ to a common particular relaxed R1CS structure. In the current state of things, checking that a relaxed R1CS holds requires to compute the $E$ term, which depends on $Z_1 = (W_1, x_1, u_1)$ and $Z_2 = (W_1, x_1, u_1)$ .

This means that $\mathcal{V}$ will need both $Z_1$ and $Z_2$ to check that the folded instance-witness pair satisfies the equation $A \cdot Z \odot B \cdot Z = uCZ + E$ . Thus, to make this scheme zero-knowledge, we will need to hide $W_1$ and $W_2$ .

We do this using a commitment scheme. On top of hiding, we will also need our commitment scheme to be additively homomorphic. Briefly, the property that an additively homomorphic commitment scheme verifies is if $\tau(W_1), \tau(W_2)$ are commmitments to witnesses $W_1, W_2$ , then the equality $\tau(W_1) + r\cdot \tau(W_2) = \tau(W_1 + r\cdot W_2)$ holds. This will make $\mathcal{V}$ able to check that the linear combination of $Z_1, Z_2$ has been performed correctly, but using committed witnesses.

Thus, a committed relaxed R1CS is a relaxed R1CS to which $\mathcal{P}$ commits to using an additively homomorphic commitment scheme. A committed relaxed R1CS instance $(\bar{E}, u, \bar{W}, x)$ is satisfied if there exists a relaxed R1CS witness $(E, W)$ such that $A \cdot Z \odot B \cdot Z = uCZ + E$ holds, where $Z=(W, x, u)$ and $\bar{E} = \tau(E), \bar{W} = \tau(W)$ - i.e. $E$ and $W$ have been correctly committed to.

A public-coin, zero-knowledge Folding Scheme for Committed Relaxed R1CS

We can now build a zero-knowledge protocol for folding committed relaxed R1CS witnesses. We describe it using the interactive version but we can make this non interactive using the fiat-shamir trick.

A prover $\mathcal{P}$ wants to convince a verifier $\mathcal{V}$ that he knows two relaxed R1CS witnesses $(E_1, W_1)$ and $(E_2, W_2)$ satisfying two committed relaxed R1CS instances $(\bar{E}_1, u_1, \bar{W}_1, x_1)$ and $(\bar{E}_2, u_2, \bar{W}_2, x_2)$ .

We want to do this in zero-knowledge. So, while both $\mathcal{P}$ and $\mathcal{V}$ know instances $(\bar{E}_1, u_1, \bar{W}_1, x_1), (\bar{E}_2, u_2, \bar{W}_2, x_2)$ , only $\mathcal{P}$ knows the two satisfying witnesses $(E_1, W_1), (E_2, W_2)$ .

The protocol is the following:

$\mathcal{P}$ computes $T=AZ_1 \odot BZ_2 + AZ_2 \odot BZ_1 - u_1CZ_2 + u_2CZ_1$ and sends $\bar{T} \leftarrow \tau(T)$ to $\mathcal{V}$ .
The verifier $\mathcal{V}$ samples a challenge $r$ and sends it to $\mathcal{P}$
Both $\mathcal{P}$ and $\mathcal{V}$ compute the folded committed relaxed R1CS instance $(\bar{E}, u, \bar{W}, x)$ , with:

\begin{aligned} \bar{E} \leftarrow \bar{E}_1 + r \cdot \bar{E}_2 \\ u \leftarrow u_1 + r \cdot u_2 \\ \bar{W} \leftarrow \bar{W_1} + r \cdot \bar{W_2} \\ x \leftarrow x_1 + r \cdot x_2 \end{aligned}

$\mathcal{P}$ sends the folded witness to $\mathcal{V}$ :

\begin{aligned} E \leftarrow E_1 + r \cdot T + r^2 \cdot E_2 \\ W \leftarrow W_1 + r \cdot W_2 \\ \end{aligned}

$\mathcal{V}$ can now do the following checks:

$\tau(E) \stackrel{?}{=} \bar{E}$
$\tau(W) \stackrel{?}{=} \bar{W}$
$A \cdot Z \odot B \cdot Z \stackrel{?}{=} uCZ + E$ , where $Z=(W, x, u)$

If all of those checks pass, $\mathcal{V}$ accepts $(E, W)$ as a satisfying folding of two satisfying witnesses of instances $(\bar{E}_1, u_1, \bar{W}_1, x_1), (\bar{E}_2, u_2, \bar{W}_2, x_2)$

We see that $\mathcal{V}$ had to check a single folded witness instead of two!

Side note: why Nova is not post-quantum

The additively homomorphic commitment scheme which Nova instantiates is pedersen commitments. But in a post-quantum context the hiding property breaks, as the hardness of the discrete logarithm fails. As of today, there is no existing quantum-resistant, additively homomorphic and succint commitment scheme. This is the sole piece missing to Nova being post-quantum ready.