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

where is the witness vector.

represents witness vector and is usually denoted as , comprising of all unique constrains after flattening the computation in R1CS form. R1CS notation can include computation of form and each matrix is of size , where denotes number of gates (unique multiplications) and denotes size of witness vector.

Note: 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:

Flattening the computation:

This means, number of gates, , and number of unique constraints, . Witness vector will be of the form: .

R1CS matrices looks like:

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, polynomials are formed of degree , each for .


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

These polys, then can be evaluated at a random point . is a polynomial interpolated from constraint from matrix .

and verified by verifier using following relation:

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



completeness, soundness, zero knowledge