Rank-1 Constraint System

R1CS is a notation to describe a computation’s circuit into three matrices, $A,B,$ and $C$ which follows following rule:

$$Aw.Bw=Cw$$

where $w$ is the witness vector.

$w$ represents witness vector and is usually denoted as $[1outx\dots ]$, comprising of all unique constrains after flattening the computation in R1CS form. R1CS notation can include computation of form $a\ast b+c=d$ and each matrix is of size $g\ast w$, where $g$ denotes number of gates (unique multiplications) and $w$ denotes size of witness vector.

Note: $w$ isn’t necessary for R1CS calculation.

Computation to QAP

Converting any computation to QAP follows four steps:

1. Flattening
2. R1CS
3. Witness
4. QAP

Let’s first take an example, a slightly complex than taken by Vitalik in this amazing explanation:

$$out=3x^{2}y+5xy-x-2y+3$$

Flattening the computation:

1. $v_1=3xx$
2. $v_2=v_{1}y$
3. $-v_2+x+2y-3+out=5xy$

This means, number of gates, $g=3$, and number of unique constraints, $w=5$. Witness vector will be of the form: $W=[1outxy{v}_1{v}_2]$.

R1CS matrices looks like:

$$\begin{array}{ccc}A& =& \left[\begin{array}{cccccc}1& out& x& y& v1& v2\\ 0& 0& 3& 0& 0& 0\\ 0& 0& 3& 0& 0& 1\\ 0& 0& 5& 0& 0& 0\end{array}\right]\\ B& =& \left[\begin{array}{cccccc}0& 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0& 0\end{array}\right]\\ C& =& \left[\begin{array}{cccccc}0& 0& 3& 0& 1& 0\\ 0& 0& 0& 0& 0& 1\\ -3& 1& 1& 2& 0& -1\end{array}\right]\end{array}$$

These matrices can be used to form a zero-knowledge proof themselves, by converting these into elliptic curve points, and bilinear pairings. But it’s quite unoptimised, and then comes to rescue, our god and saviour, polynomials.

R1CS vectors are converted into polynomials for each constraint. Each column vector is interpolated to form a polynomial. Thus, $w$ polynomials are formed of degree $g-1$, each for $A,B,andC$.

QAP

Polynomial under addition and multiplication form an algebraic ring. Polynomials can be proven succinctly using Schwartz-Zippel lemma.

$$\sum _{i=0}^w{a}_i{u}_i(x)\sum _{i=0}^w{a}_i{v}_i(x)=\sum _{i=0}^w{a}_i{w}_i(x)+h(x)t(x)$$

These polys, then can be evaluated at a random point $\tau$. $u_i(x)$ is a polynomial interpolated from $i^{th}$ constraint from matrix $A$.

$$\begin{array}{ccc}{\sum }_{i=0}^w{a}_i{u}_i(\tau ){\sum }_{i=0}^w{a}_i{v}_i(\tau )& =& {\sum }_{i=0}^w{a}_i{w}_i(\tau )+h(\tau )t(\tau )\\ {\sum }_{i=0}^w{a}_i[u_i(\tau ){]}_1& =& {\sum }_{i=0}^w{a}_i{\sum }_{j=0}^{g-1}{u}_{i,j}[{\tau }^{j}G{]}_1\\ {\sum }_{i=0}^w{a}_i[v_i(\tau ){]}_2& =& {\sum }_{i=0}^w{a}_i{\sum }_{j=0}^{g-1}{v}_{i,j}[{\tau }^{j}G{]}_2\\ {\sum }_{i=0}^w{a}_i[w_i(\tau ){]}_1& =& {\sum }_{i=0}^w{a}_i{\sum }_{j=0}^{g-1}{w}_{i,j}[{\tau }^{j}G{]}_1\\ h(\tau )t(\tau )& =& {\sum }_{i=0}^{deg(h)}{h}_i[{\tau }^{i}t(\tau )G{]}_1\end{array}$$

and verified by verifier using following relation:

$$\begin{array}{c}e([A{]}_1,[B{]}_2)=e([C{]}_1,[G{]}_2)\end{array}$$

Problem is, prover knows $A,B,C,w,t$ and can invent values which satisfy above relation. Groth16 designed a protocol that is more efficient for both prover and verifier that this.

Groth16

TODO

completeness, soundness, zero knowledge

TODO

Questions

• can’t understand how linear combinations are free in R1CS?

Resources

• [])
• vitalik article’s sage mode
• can there be a better way of defining polys in qap
• ZK IAP Lecture 7: Arithmetizations
• shumochu’s thread about R1CS vs plonkish arithmetization