# 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)$?

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.)