This beginner friendly article is an extended version of Vitalik’s article on Quadratic Arithmetic Programs. We will provide a deeper technical dive on how to transition from a Problem to R1CS and from R1CS to QAP.

As mentioned by Vitalik, “zk-SNARKs cannot be applied to any computational problem directly; rather, you have to convert the problem into the right “form” for the problem to operate on. The form is called a “quadratic arithmetic program” (QAP)”

Along with the process for converting the code of a function into a QAP is another process that can be run alongside so that if you have an input to the code you can create a corresponding solution (sometimes called “witness” to the QAP).

After this, there is another fairly intricate process for creating the actual “zero knowledge proof” for this witness, and a separate process for verifying a proof that someone else passes along to you, but these are details that are out of scope for this post.

Introduction

We will use the same example as Vitalik because it is simple enough that the resulting QAP will not be so large as to be intimidating, but nontrivial enough that you can see all of the machinery come into play. Our goal is to prove that we know the solution to a cubic equation :

As you can see, the solution for this is $x=3$. The Prover must thus show to Verifier that he knows the solution, without giving away the value 3.

To keep things simple, we will use a Galois Field (or finite field) of GF(641) which is a prime number.

If you’re not familiar with Modular Arithmetic, I recommend reading the Finite Fields and Modular Arithmetic for ZK Proofs chapter from Rareskills Zero Knowledge book before proceeding an further.

Problem Statement to R1CS

Definition of R1CS

Rank-1 Constraint System (R1CS) is a way to represent complex mathematical statements as a series of equations that a computer can verify efficiently. In essence, R1CS allows us to break down a problem into simple constraints that verify if a solution is valid. This let’s us easily prove to the Verifier that the Prover does really know a proper witness $w$ (solution) for a specific problem or in this case a cubic equation.

Step 1: Flattening

We have a function $x^3 + x +5 = 35$, we want to simplify it into multiple small functions called constraints which take the form of $x = y \space (op) \space z$ where $(op)$ can be any arithmetic operation $(+, -, \times, /)$.

We have 4 gates because in every line $a, b, c$ and $d$ we have one arithmetic operations. Since $a$ and $b$ both have multiplication, we’ll need two multiplication gates:Gate#1 and Gate#2. Similarly, since $c$ and $d$ both have addition, we’ll also need two addition gates: Gate#3 and Gate#4.

Step 2: Gates to R1CS

Next, we will need to convert the previous statements into the R1CS (Rank-1 Constrain System) format, and which defines three vectors: A, B and C. The solution to this is a vector $(S)$ that must satisfy the equation below.

. represents the dot product which is a mathematical operation that takes two vectors and returns a single number (a scalar) so it’s not multiplication.

The length of each vector is equal to the total number of variables in the system, including a dummy variable one at the first index representing the number 1 which allows all constraints to be written in a constant form, the input variable x, a dummy variable d representing the output, and then all of the intermediate variablesa, b and c. So we will use this layout to display the variables:

Other articles might use a different layout like the one below. They are all the same, they all serve the same purpose. You can structure your layout depending on your own needs.

In this case, the Prover proves that he knows a solution that satisfies the equation$(x^3 + x +5 = 35)$ by producing a vector S which is the witness $w$ for $x = 3$ :

For the First Constraint:

By applying $x= 3$ on our first constraint $a =x \times x$, we will get:

So for $x = 3$, $a= x \times x$ will be represented as $9 =3 \times 3$ or $3 \times 3 -9 = 0$ . The first $x$ which is 3 will be in the second index of the vector A because the second index in $S = [1,3,9,27,30,35]$ is 3. The second $x$ which is also 3 will also be in the second index of vector B. This leaves us with 9 which will be in the third index of vectorC.

So the function $(A.S) \times (B.S) - (C.S) = 0$ for $x = 3$ will look like this in vector form :

For the Second Constraint:

Similarly to the first constraint, by applying $x=3$ on our second constraint $b = a \times x$, we will get:

In simple terms, for $x =3$, the second constraint will become $27 = 9 \times 3$ or $9 \times 3 -27 = 0$. 9 is the third index in vector $A$, 3 is the second index in vector $B$ and 27 is the fourth index in vector $c$. Remember these vectors are made this way because of the structure of our layout for vector S :

So the function $(A.S) \times (B.S) - (C.S) = 0$ for $x = 3$ will look like this in vector form :

For the Third Constraint:

By applying $x = 3$ on our third constraint $c = b + x$ or $c = (b + x) \times 1$, we will get:

The third constraint will become $30 = (27 + 3) \times 1$ or $(27 + 3) \times 1 - 30 =0$.

27 is the fourth index in vector A and 3 is the second index in vector A. 1 is the first index in vector B and 30 is the fifth index in vector C.

So vector $A$ is $3 + 27$, vector $b$ is $1$ and vector $C$ is $30$. Thus, $27 +3 - 30 = 0$.

For the Fourth Constraint:

By applying $x = 3$ on our third constraint $d = c + 5$ or $d = (c+5) \times 1$, we will get:

We have 5 as the first index in vector A and $c=30$ as the fifth index in vector A. 1 is the first index in vector B and d = 35 is the last index in vector C.

After adding the vector A of all the constraints from 1 to 4 into a single vector A and doing the same thing for vector B and C, we will get the complete R1CS or final vector form of $(A.S) \times (B.S) - (C.S) = 0$ for $x =3$ :

Now let’s do the dot product of vector A,B and C with vector S but only for the first row of each vector to check if our calculations are correct.

For Vector A :

For Vector B :

For Vector C :

Final Equation :

The Prover has provided the correct first part of the proof. We can then got through the other 3 rows for each vector A, B and C to find that the results will be zero but we won’t do it because you got the point. You can try it yourself and see that for every line $A \times B - C$ will always be zero. The Prover has thus proven that he knows the solution of the cubic equation. If you’re too lazy here’s the answers :

To not create any confusion later we will refer to $(A.S) \times (B.S) - (C.S) = 0$ as

$(A’.S) \times (B’.S) - (C’.S) = 0$. A will be called A’, B’ for B and C’ for C.

R1CS to QAP

The next step is taking this R1CS and converting it into QAP form, which implements the exact same logic except using polynomials instead of dot products. We go from four groups of three vectors of length six to six groups of three degree-3 polynomials, where evaluating the polynomials at each x coordinate represents one of the constraints. That is, if we evaluate the polynomials at $x=1$, then we get our first set of vectors, if we evaluate the polynomials at $x=2$, then we get our second set of vectors, and so on.

We can make this transformation using something called a Lagrange interpolation. The problem that a Lagrange interpolation solves is this: if you have a set of points (i.e. (x, y) coordinate pairs), then doing a Lagrange interpolation on those points gives you a polynomial that passes through all of those points.

What we are going to do is take the first value out of every A’ vector, use Lagrange interpolation to make a polynomial out of that (where evaluating the polynomial at i gets you the first value of the ith A’ vector), repeat the process for the first value of every B’ and C’ vector, and then repeat that process for the second values, the third values, and so on.

Step 1

Since we have 4 constraints, we will choose values for $x$ such that $x \in [ 1,2,3,4 ]$.

We’re gonna have 6 polynomials against 6 variables and A’,B’,C’ are going to be these polynomials. Don’t worry if you didn’t understand this, we’ll explain everything.

We’re gonna evaluate each vector A,B and C for every value of $x \in [ 1,2,3,4 ]$ at every constraint.

First constraint

Remember vector A, B and C for the first constraint :

We evaluate A, B and C for $x = 1$ :

Second Constraint

We evaluate A, B and C for $x = 2$ :

Third Constraint

We evaluate A, B and C for $x = 3$ :

Fourth Constraint

We evaluate A, B and C for $x = 4$ :

Step 2

We can see $A_1(x), …, A_6(x)$, $B_1(x), …, B_6(x)$ and $C_1(x), …, C_6(x)$ at every point $x$ from 1 to 4. We will display them in the format below :

We have only a single polynomial of degree 3 that passes through $A_1(1)$ to $A_1(4)$. The polynomial will intersect the $x-axis$ at $x = 1, 2 \space \text{and} \space 3$ since the result for each one of them is 0 $(A_1(1) = 0, A_1(2) = 0, A_1(3) = 0)$ and will hit the line $y = 5$ for $x = 4$.

Or we can also take the $y-coordinates$ in the first column in $(A’.S) \times (B’.S) - (C’.S) = 0$ for $x \in [1,2,3,4]$ resulting to 4 points $(1,0), (2,0), (3,0), (4,5)$ :

This is an arbitrary interpretation which we use to convert the R1CS into the QAP form. We could have as well used $[5,7,9,11]$ instead of $[1,2,3,4]$ as long as we are consistent across all equations.

The number of polynomials & their degree would depend on the length of the solution vector & the number of gates.

The solution vector S contains 6 elements $[1, 3, 9, 27, 30, 35]$, so we can construct 6 polynomials per vector. Each gate contributes 1 point to each polynomial. We have 4 gates here meaning we get 4 points per polynomial. 4 points allows us to define a polynomial of maximum degree 3. So we can construct 6 polynomials each with a maximum degree of 3.

A visual representation of the points for each polynomial of vector A’ will look like :

So in total we have 3 vectors A’, B’ and C’ with 6 polynomials each, resulting in 18 polynomials.

We can find the polynomial passing through these 4 points using Lagrange Interpolation. We will only demonstrate for only the first polynomial and give you the result for all 18 polynomials. You can do the other ones by yourselves and compare your answers.

Lagrange Interpolation

To construct the Lagrange interpolation polynomial for the points $(1,0),(2,0),(3,0),(4,5)$ over a finite field with $GF(641)$, we’ll use the following approach.

Given points $(x_1 ​ ,y_1 ​ ),(x_2 ​ ,y_2 ​ ), …, (x_n ​ ,y_n ​)$, the Lagrange polynomial $L(x)$ is constructed as:

where each $l_i(x)$ is the Lagrange basis polynomial for point $(x_i, y_i)$, defined by:

In this case :

• The points are :

  • $( 𝑥_1 , 𝑦_1 ) = ( 1 , 0 )$

  • $( 𝑥_2 , 𝑦_2 ) = ( 2 , 0 )$

  • $( 𝑥_3 , 𝑦_3 ) = ( 3 , 0 )$

  • $( 𝑥_4 , 𝑦_4 ) = ( 4 , 5 )$

• Field $GF(641)$

Since $𝑦_1 ​ =y_2 ​ =y_3 ​ =0$, only $𝑦_4 = 5$ contributes to the polynomial, so we need only compute $l_4 ( 𝑥 )$.

Step-by-Step Calculation of $l_4 ( 𝑥 )$ :

Substitute $𝑥_1=1, 𝑥_2​ =2, 𝑥_3=3$, and $𝑥_4=4$ :

1. Calculate the denominator :

   $$(4−1)(4−2)(4−3)=3⋅2⋅1=6$$

   Inverse of $6 \space mod \space 641$ is $107$, since $6 \times 107 \equiv 1 \space (mod \space 641)$.

2. Compute $l_4 ( 𝑥 )$ :

   $$l_4(x) = 107 ⋅(x−1)(x−2)(x−3) \space (mod \space 641)$$

3. Expand $(x-1)(x-2)(x-3)$ :

   Expanding this product :

   $$(x−1)(x−2)=x^2−3x+2$$

Substitute into $l_4(x)$ :

Final Polynomial $L(x)$ :

So the polynomial corresponding to the first Column of vector A’ is :

Since we didn’t calculated $𝑦_1, y_2, y_3$, you can ask chatgpt to calculate $y_1, y_2, y_3, y_4$ and generate the final polynomial if you have more than one point with coordinates other than 0.

Below are all coefficients of all 18 polynomials that we applied a finite field 641 to :

Polynomials of vector A’ : We’ll call the new vector, vector A’’.

You can see the polynomial we got from the first column i.e. $(535x^3+ 636x^2+ 116x+ 636$) appear in first row of vector A’’. The Row is to be interpreted in reverse order - i.e. $[4, 2, 3, 7]$.

I’m going to re-explain what happened so we won’t get confused later. We applied Lagrange interpolation to the first column of vector A’ and we got the first row of vector A’’ but in reverse.

Polynomials of vector B’ : We’ll call the new vector, vector B’’.

Polynomials of vector C’ : We’ll call the new vector, vector C’’.

This finishes the transformation of the problem to the QAP Form.

What do we achieve by converting it into the QAP form? Instead of checking the constraints in the R1CS individually, we can now check all of the constraints at the same time by doing the dot product check on the polynomials.

Our solution S has 6 elements $[1, 3, 9, 27, 30, 35]$. we can do a dot product of $(S.A'')$ whose output again will be a polynomial. Likewise for the other 2 polynomial matrices.

For vector A’’ :

We know the dot product is done by multiplying all the values of each row at a time in A’’ with vector S. Like this for the first row:

This approach is not correct!! Since we have rotated A’ going to A’’, we will need to calculate the dot product vertically like this for the first column :

We do the same thing for all 4 columns while applying $GF(641)$ :

or we can rotate the vector A’’ to get 4 rows and 6 columns instead of 6 rows and 4 columns and do the dot product as we usually do it, horizontally.

For vector B’’ :

For vector C’’ :

So by taking the dot product of S with each of matrix A’’, B’’, C’’, we created 3 polynomials.

We can define a new polynomial :

In the R1S, we had checked if $(A.S)∗(B.S)-(C.S) = 0$ for each of the Gates. After conversion to QAP, we can do the same by checking the value of $T$ at $x$  at $1,2,3,4$- if all 4 are zero, then we have checked all the constraints together - thereby proving that the solution vector known to the Provers satisfies the equation.

Let take a value, for example $3$ at lets check if its $0$ for $T(3)$ :

However, the Verifier doesn’t know the polynomial $T$, nor can he compute it since he doesn’t know the solution vector S. So the Prover has to prove it to the Verifier that $T$ is zero at $x \in [1,2,3,4]$. If T is really zero at $x \in [1,2,3,4]$, then we say that these are all roots of $T$. So we create a new polynomial $Z$ known by both the Prover & the Verifier. If $T$ is perfectly divisible by $Z$, then it will leave no remainder.

Let $Z$ be :

So there must exist a Polynomial $H$ such that :

In real life $T$ won’t be equal to 0. If it was 0, the Prover can act maliciously and prove that $H(x) = 0$ for any kind of polynomial $Z(x)$. This was just an example. If you structure vector $S$ like this $[\textcolor{orange}{1},\textcolor{orange}{35},3,9,27,30]$, $T(x)$ will equal to :

Usually they put the dummy variables like 1 or the output $d = 35$ at the start or/and in the end of the vector so this structure is also true : $[\textcolor{orange}{1},\textcolor{orange}{35},3,9,27,30,\textcolor{orange}{35},\textcolor{orange}{1}]$ or $[\textcolor{orange}{1},\textcolor{orange}{35},3,9,27,30]$.

In a typical zk-SNARK, the Prover proves that $Z$ exactly divides $T$ using Polynomial Commitments & Elliptic Curve Bilinear Pairings.

This is the end of our article. Hope it wasn’t hard to understand. To make sure you fully understood, you can try different structures of vector S then check that $T(x) = 0$ for $x \in [1,2,3,4]$ and $H(x) = \frac {T(x)} {Z(x)}$ has no a remainder of 0.