# zkSnark: Converting R1CS to QAP

I am reading through Vitalin Buterin's page on R1CS & QAP - https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

I understood upto the part where he gets

$$A=\begin{pmatrix} 0&1&0&0&0&0 \\ 0&0&0&1&0&0 \\ 0&1&0&0&1&0 \\ 5&0&0&0&0&1 \\ \end{pmatrix}$$

$$B=\begin{pmatrix} 0&1&0&0&0&0 \\ 0&1&0&0&0&0 \\ 1&0&0&0&0&0 \\ 1&0&0&0&0&0 \\ \end{pmatrix}$$

$$C=\begin{pmatrix} 0&0&0&1&0&0 \\ 0&0&0&0&1&0 \\ 0&0&0&0&0&1 \\ 0&0&1&0&0&0 \\ \end{pmatrix}$$

Now, when he converts R1CS to QAP, he writes

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.

The original sets of vectors A, B & C were not at all created by any x=1, x=2 etc. They had the mapping

$$['~one', 'x', '~out', 'sym\_1', 'y', 'sym\_2'] = [ 1, 3, 35, 9, 27, 30]$$

i.e. they were calculated using $$x = 3$$ (which is the root of the polynomial $$x^3 + x + 5 = 35$$)

So I don't understand how he equates those to sampling at x=1, x=2 etc.

Can someone explain?

First, it's important to understand, how many information a polynomial of degree $$d$$ could contains. It's characterized by $$d+1$$ images (think to Lagrange polynomials to understand why).

So, we have now to focus on one specific sentence in the link you've wrote : "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.".

It implies that each group correspond to the images of the polynomials for one particular value.(Because we arbitraily decide to interpret it like this) It seems that the convention is to consider that the $$i^\text{th}$$ group gives us the images for the input $$i$$.

For example, if I would to compute the first polynomial $$P_{1,1}$$ of the first vector. I will compute $$P_{1,1}$$ of degree at most $$3$$ such that $$P_{1,1}(1)= x_1, P_{1,1}(2) = x_2, P_{1,1}(3) = x_3, P_{1,1}(4)=x_4$$, with $$x_i$$ the first coordinate of the first vector of the $$i^{\text{th}}$$ group.

More generally, we can do the same to compute the $$j^{\text{th}}$$ polynomial $$P_{j,k}$$ of the $$k^{\text{th}}$$ vector, by looking the $$k^{\text{th}}$$ coordinates of the $$j^{\text{th}}$$ vectors of the groups.
• I do know what (n+1) points define & n degree polynomial. Lagrange's interpolation is used to find a n-degree polynomial when you know n+1 points on the polynomial. However, here we already know the polynomial - $x^3 + x -30$ - so I am unable to figure why exactly we are using Lagrange's interpolation? Oct 27, 2021 at 11:10
• I know $L_i(x)= \prod_{j=0}^n \frac {x-x_j} {x_i - x_j}$ & $P_n(x) = \sum_{i=0}^n L_i(x)y_i$. However, I am unable to corelate it with the symbols you use - $P_{j,k}(1)$ & $P_{j,k}(2)$ - what is (1) & (2) here - is it P(x=1) & P(x=2) & What is $P_{j,k}$? Oct 27, 2021 at 11:53
• the $j^{\text{th}}$ coordinate of the $k^{\text{th}}$ vector Oct 27, 2021 at 12:44