Nova

A Folding Scheme for Committed Relaxed R1CS

Relaxed R1CS

R1CS is in the format

$$(A \cdot Z) \circ (B \cdot Z)=C \cdot Z$$

In order to enable recursive, i.e., verifying two instance by one, introducing $E$ and $u$ in the equation.

$$(A \cdot Z) \circ (B \cdot Z)=u \cdot (C \cdot Z) + E$$

how to committed to an relaxed R1CS?

Committed relaxed R1CS

For sparse matrices $(A,B,C)$, a committed relaxed R1CS is a tuple $(\overline{E},u,\overline{W},x)$ where $\overline{E}=com(pp_E,E,r_e)$ and $\overline{W}=com(pp_w,W,r_w)$ such that

$$(A \cdot Z) \circ (B \cdot Z)=u \cdot (C \cdot Z) + E$$

holds where$Z=(W,x,u)$

How to fold? my understanding, how to verify one commitment in the same format that automatically verify two actually?

verifier has:

two commitments $(\overline{E}_1,u_1,\overline{W}_1,x_1)$ and $(\overline{E}_2,u_2,\overline{W}_2,x_2)$
public info $(u_1,x_1)$ and $(u_2,x_2)$ and commitments $\overline{E}_1, \overline{W}_1,\overline{E}_2,\overline{W}_2$

Folding phase

prover send $\overline{T}=com(pp_E,T,r_T)$ and

$$T=AZ_1\circ BZ_2+AZ_2 \circ BZ_1 -u_1\cdot CZ_2 – u_2\cdot CZ_1$$

to the verifier

Verifer send prover $r$
verifier and prover ouput the folded instance

$$\overline{E}\leftarrow\overline{E}_1+r\cdot \overline{T} + r^2 \overline{E}_2$$

$$u\leftarrow u_1+r\cdot u_2$$

$$\overline{W} \leftarrow \overline{W}_1 +u_2 \overline{W}_2$$

$$x\leftarrow x_1 + r\cdot x_2$$

let us verify that the folding will keep the same structure

Prover compute the new witness

$$E\leftarrow E_1+r\cdot T + r^2 \cdot E_2$$

$r_E\leftarrow r_{E_1} +r\cdot r_T + r^2\cdot r_{E_2}$ remember $T$ is also committed

$$W\leftarrow W_1 + r \cdot W_2$$

$$r_W\leftarrow r_{W_1}+ r\cdot r_{W_2}$$

Nova: An IVC Scheme with Proof Compression

folding for Plonk

https://geometry.xyz/notebook/sangria-a-folding-scheme-for-plonk

Table of Contents