0

I'm trying to understand this article by Vitalik Butarin on conversion to QAPs as a pre-requisite to understanding zk-SNARKS.

However, I seem to have hit a dead-end when he says to convert a vector into its corresponding polynomial. I am able to follow the example he gives before that, but I haven't been able to apply that to this problem.

To quote:

Now, let’s use Lagrange interpolation to transform our R1CS. 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.

If I am following this correctly, he is trying to convert the vector $\begin{bmatrix} 0 & 0 & 0 & 5\end{bmatrix}$ to a polynomial $0.833 x^3 - 5x^2 + 9.166x - 5$ as he says later).

How did he reach this polynomial? The example only talks about $2$-D vectors. How can that be applied to a $1$-D vector? I tried by assuming the first vector as $x$ a corresponding $0$-vector $y$ ($\begin{bmatrix} 0 & 0 & 0 & 0\end{bmatrix}$), but that doesn't seem to work either.

I will appreciate any input you have.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
goelakash
  • 158

1 Answers1

0

It interpolates the following points: $(1,0), (2,0), (3,0), (4,5)$ and the interpolation polynomial is

$$\frac{5}{6}x^3-5x^2+\frac{55}{6}x-5.$$

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • Thanks, I arrived at the same conclusion some time after myself. – goelakash Dec 19 '17 at 21:26
  • Can you elaborate? I am also stuck here. Four groups of vector $(a, b, c)$ are a = [0, 1, 0, 0, 0, 0] b = [0, 1, 0, 0, 0, 0] c = [0, 0, 0, 1, 0, 0]

    a = [0, 0, 0, 1, 0, 0] b = [0, 1, 0, 0, 0, 0] c = [0, 0, 0, 0, 1, 0]

    a = [0, 1, 0, 0, 1, 0] b = [1, 0, 0, 0, 0, 0] c = [0, 0, 0, 0, 0, 1]

    a = [5, 0, 0, 0, 0, 1] b = [1, 0, 0, 0, 0, 0] c = [0, 0, 1, 0, 0, 0]

     – lkahtz Apr 26 '19 at 06:12