zkSnark: Converting R1CS to QAP

Question

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?

Answer 1

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.

These equations determines only one polynomial (I'm unsure to can do better explanations than the one in your link), but if you want to have more knowledge about this, you can read: https://en.wikipedia.org/wiki/Lagrange_polynomial

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.