Score:1

zkSnark: Converting R1CS to QAP

et flag

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?

Score:1
cn flag

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.

et flag
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?
et flag
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}$?
Ievgeni avatar
cn flag
the $j^{\text{th}}$ coordinate of the $k^{\text{th}}$ vector
et flag
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?
Ievgeni avatar
cn flag
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".
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.