1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – user93353
    Oct 27, 2021 at 11:10
  • $\begingroup$ 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}$? $\endgroup$
    – user93353
    Oct 27, 2021 at 11:53
  • $\begingroup$ the $j^{\text{th}}$ coordinate of the $k^{\text{th}}$ vector $\endgroup$
    – Ievgeni
    Oct 27, 2021 at 12:44
  • $\begingroup$ 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 - x3+x−30 - so I am unable to figure why exactly we are using Lagrange's interpolation? $\endgroup$
    – user93353
    Oct 27, 2021 at 14:08
  • $\begingroup$ I'm speaking about polynomials in this sentence ""We go from four groups of three vectors of length six to six groups of three degree-3 polynomials". $\endgroup$
    – Ievgeni
    Oct 27, 2021 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.