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…]$, comprising of all unique constrains after flattening the computation in R1CS form. R1CS notation can include computation of form $a∗b+c=d$ and each matrix is of size $g∗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:

- Flattening
- R1CS
- Witness
- 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:

- $v_{1}=3xx$
- $v_{2}=v_{1}y$
- $−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=[1outxyv_{1}v_{2}]$.

R1CS matrices looks like:

$ABC === 1000 out000 x335 y000 v1000 v2010 000 000 100 011 000 000 00−3 001 301 002 100 01−1 $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.

$i=0∑w a_{i}u_{i}(x)i=0∑w a_{i}v_{i}(x)=i=0∑w a_{i}w_{i}(x)+h(x)t(x)$These polys, then can be evaluated at a random point $τ$. $u_{i}(x)$ is a polynomial interpolated from $i_{th}$ constraint from matrix $A$.

$∑_{i=0}a_{i}u_{i}(τ)∑_{i=0}a_{i}v_{i}(τ)∑_{i=0}a_{i}[u_{i}(τ)]_{1}∑_{i=0}a_{i}[v_{i}(τ)]_{2}∑_{i=0}a_{i}[w_{i}(τ)]_{1}h(τ)t(τ) ===== ∑_{i=0}a_{i}w_{i}(τ)+h(τ)t(τ)∑_{i=0}a_{i}∑_{j=0}u_{i,j}[τ_{j}G]_{1}∑_{i=0}a_{i}∑_{j=0}v_{i,j}[τ_{j}G]_{2}∑_{i=0}a_{i}∑_{j=0}w_{i,j}[τ_{j}G]_{1}∑_{i=0}h_{i}[τ_{i}t(τ)G]_{1} $and verified by verifier using following relation:

$e([A]_{1},[B]_{2})=e([C]_{1},[G]_{2}) $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?