# How to calculate $v_k(s)$ in Quadratic Arithmetic Program?

In the paper Pinocchio: Nearly Practical Verifiable Computation, there are some polynomials $v_k(x)$, $w_k(x)$ and $y_k(x)$ representing the structure of there circuit. However, as in the "concrete example" in page 3, the description of $v_k(x)$ are table items like $v_1(r_5) = 0$ and $v_1(r_6) = 1$, where $r_5$ and $r_6$ are roots of the constructed target polynomial $t(n)$.

But what is the textbook form of $v_1(x)$ like $a_0 + a_1x + a_2x^2 + \dots$? How to calculate $v_1(s)$ and $g^{v_1(s)}$, if $s$ is not a root of the target polynomial $t(x)$?

## 1 Answer

The canonical algorithm to construct the QAP polynomials from an arithmetic circuit does not yield a polynomial in the standard form ($a_0 + a_1x + \dots$), but as a set of $(x,f(x))$ points. In order to compute $f(s)$ for arbitrary $s$, as required by the protocol, you have to run some interpolation algorithm to reconstruct the polynomial from all the points. (This is indeed one of the major flaws of Pinocchio, because interpolation is a very expensive operation and takes most of the execution time, even though it is not a crypto operation.)

• Can you refer me to any interpolation algorithm as an example? Thank you! – phan Nov 24 '15 at 9:20
• A classical interpolation algorithm is one attributed to Lagrange. Any computer algebra textbook (e.g., the classic book of Gerhard and von zur Gathen) should cover the topic in depth, as do many lecture notes you can find through your favourite search engine. – fkraiem Nov 24 '15 at 9:24
• By the way, the issue regarding the complexity of polynomial arithmetic is discussed in section 4.2.1 (on page 8) of the Pinocchio paper. You should read it more carefully. – fkraiem Nov 24 '15 at 9:28