# What is Quadratic Arithmetic Programs

Reading https://vitalik.eth.limo/general/2016/12/10/qap.html

proof $3$ is the solution for $x^3 + x + 5 = 35$

## Constraint

$x*x = \text{sym_1}$
$\text{sym_1} * x = y$
$y+ x = \text{sym_2}$
$\text{sym_2} + 5 = \text{out}$

## R1CS

$AZ \circ BZ = CZ$
$A = \begin{bmatrix}
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{bmatrix}$
$B = \begin{bmatrix}
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{bmatrix}$
$C = \begin{bmatrix}
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{bmatrix}$
$Z = \begin{bmatrix}
1 \\
x \\
\text{out} \\
\text{sym_1} \\
y \\
\text{sym_2} \\
\end{bmatrix}$

## R1CS to QAP

Convert the matrix-vector product of R1CS into a polynomial using Lagrange interpolation

### Lagrange interpolation

A simple example to see how Lagrange interpolation works:

Given three points, $(1, 3), (2, 2), (3, 4)$, directly write the curve passing through these three points.
- First write the curve $y_1 = (x - 2)(x - 3)$ through the two points $(2, 0), (3, 0)$. When $x = 1$, $y_1 = 2$, how to change it to $3$ to satisfy $(1, 3)$. It is definitely not possible to directly add $1$ to the $y_1$ equation, so that it will not exceed $(2,0)$, $(3,0)$. Then multiply it by a number, which will not affect $(2,0)$, $(3,0)$. So the curve passing through $(1, 3), (2, 0), (3, 0)$ is $y_{1}\prime = (x - 2)(x - 3)\cdot\frac{3}{ (1-2)(1-3)}$
- Similarly, writing the curve through $(1,0), (2, 2), (3, 0)$ is $y_2 = (x-1)(x-3)\cdot\frac{2}{( 2-1)(2-3)}$
- The curve of $(1,0), (2, 0), (3, 4)$ is $y_3 = (x-1)(x-2)\cdot\frac{4}{(3-1) (3-2)}$
- $y = y_1 + y_2 + y_3$

### QAP

Select the $i$th column in $A, B, C$ respectively, and perform polynomial encoding on them.
here it is

$A[0] = \begin{bmatrix}
0 \\
0 \\
0 \\
5 \\
\end{bmatrix}$，Then we get four points $(1,0), (2,0), (3,0),(4,5)$，and they define a polynomial $\frac{5}{6} w^3 - 5 w^2 + \frac{55}{6}w - 5$，coefficients is：$\begin{bmatrix}-5 & \frac{55}{6} & -5 & \frac{5}{6} \end{bmatrix}$

sage: R.<w> = PolynomialRing(QQ)
sage: points = [(1,0), (2,0), (3,0), (4,5)]
sage: R.lagrange_polynomial(points)
5/6*w^3 - 5*w^2 + 55/6*w - 5
sage: R.lagrange_polynomial(points).coefficients()
[-5, 55/6, -5, 5/6]

Similarly, finally get:

$A_P = \begin{bmatrix}
-5 & \frac{55}{6} & -5 & \frac{5}{6} \\
8 & -\frac{34}{3} & 5 & -\frac{2}{3} \\
0 & 0 & 0 & 0 \\
-6 & \frac{19}{2} & -4 & \frac{1}{2} \\
4 & -7 & \frac{7}{2} & -\frac{1}{2} \\
-1 & \frac{11}{6} & -1 & \frac{1}{6} \\
\end{bmatrix}$

$B_P = \begin{bmatrix}
3 & -\frac{31}{6} & \frac{5}{2} & -\frac{1}{3} \\
-2 & \frac{31}{6} & -\frac{5}{2} & \frac{1}{3} \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{bmatrix}$

$C_P = \begin{bmatrix}
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
-1 & \frac{11}{6} & -1 & \frac{1}{6} \\
4 & -\frac{13}{3} & \frac{3}{2} & -\frac{1}{6} \\
-6 & \frac{19}{2} & -4 & \frac{1}{2} \\
4 & -7 & \frac{7}{2} & -\frac{1}{2} \\
\end{bmatrix}$

As you can see below, QAP can also be converted to R1CS:

$A = \begin{bmatrix}
A_{P0}(1) & A_{P1}(1) & A_{P2}(1) & A_{P3}(1) & A_{P4}(1) & A_{P5}(1) \\
A_{P0}(2) & A_{P1}(2) & A_{P2}(2) & A_{P3}(2) & A_{P4}(2) & A_{P5}(2) \\
A_{P0}(3) & A_{P1}(3) & A_{P2}(3) & A_{P3}(3) & A_{P4}(3) & A_{P5}(3) \\
A_{P0}(4) & A_{P1}(4) & A_{P2}(3) & A_{P3}(4) & A_{P4}(4) & A_{P5}(4) \\
\end{bmatrix}$

$B = \begin{bmatrix}
B_{P0}(1) & B_{P1}(1) & B_{P2}(1) & B_{P3}(1) & B_{P4}(1) & B_{P5}(1) \\
B_{P0}(2) & B_{P1}(2) & B_{P2}(2) & B_{P3}(2) & B_{P4}(2) & B_{P5}(2) \\
B_{P0}(3) & B_{P1}(3) & B_{P2}(3) & B_{P3}(3) & B_{P4}(3) & B_{P5}(3) \\
B_{P0}(4) & B_{P1}(4) & B_{P2}(3) & B_{P3}(4) & B_{P4}(4) & B_{P5}(4) \\
\end{bmatrix}$

$C = \begin{bmatrix}
C_{P0}(1) & C_{P1}(1) & C_{P2}(1) & C_{P3}(1) & C_{P4}(1) & C_{P5}(1) \\
C_{P0}(2) & C_{P1}(2) & C_{P2}(2) & C_{P3}(2) & C_{P4}(2) & C_{P5}(2) \\
C_{P0}(3) & C_{P1}(3) & C_{P2}(3) & C_{P3}(3) & C_{P4}(3) & C_{P5}(3) \\
C_{P0}(4) & C_{P1}(4) & C_{P2}(4) & C_{P3}(4) & C_{P4}(4) & C_{P5}(4) \\
\end{bmatrix}$

According to $A\cdot Z \circ B \cdot Z = C \cdot Z$
$$\begin{align*}
(A_{P0}(X) \cdot Z[0] + A_{P1}(X) \cdot Z[1] + A_{P2}(X) \cdot Z[2] + A_{P3}(X) \cdot Z[3] + A_{P4}(X) \cdot Z[4] + A_{P5}(X) \cdot Z[5]) \cdot & \\ (B_{P0}(X) \cdot Z[0] + B_{P1}(X) \cdot Z[1] + B_{P2}(X) \cdot Z[2] + B_{P3}(X) \cdot Z[3] + B_{P4}(X) \cdot Z[4] + B_{P5}(X) \cdot Z[5]) & \\ = (C_{P0}(X) \cdot Z[0] + C_{P1}(X) \cdot Z[1] + C_{P2}(X) \cdot Z[2] + C_{P3}(X) \cdot Z[3] + C_{P4}(X) \cdot Z[4] + C_{P5}(X) \cdot Z[5]) \end{align*}$$

and $Z = \begin{bmatrix} 1 \\ 3 \\ 35 \\ 9 \\ 27 \\ 30 \end{bmatrix}$

$\begin{align*} & A_{P0}(X) \cdot Z[0] + A_{P1}(X) \cdot Z[1] + A_{P2}(X) \cdot Z[2] + A_{P3}(X) \cdot Z[3] + A_{P4}(X) \cdot Z[4] + A_{P5}(X) \cdot Z[5] \\ = & \begin{bmatrix} 1 & X & X^2 & X^3 \end{bmatrix} \cdot (A_P^\top \cdot Z) \end{align*}$

Let $\begin{align*}
t(X) = & (A_{P0}(X) \cdot Z[0] + A_{P1}(X) \cdot Z[1] + A_{P2}(X) \cdot Z[2] + A_{P3}(X) \cdot Z[3] + A_{P4}(X) \cdot Z[4] + A_{P5}(X) \cdot Z[5]) \cdot \\ & (B_{P0}(X) \cdot Z[0] + B_{P1}(X) \cdot Z[1] + B_{P2}(X) \cdot Z[2] + B_{P3}(X) \cdot Z[3] + B_{P4}(X) \cdot Z[4] + B_{P5}(X) \cdot Z[5]) \\ & - (C_{P0}(X) \cdot Z[0] + C_{P1}(X) \cdot Z[1] + C_{P2}(X) \cdot Z[2] + C_{P3}(X) \cdot Z[3] + C_{P4}(X) \cdot Z[4] + C_{P5}(X) \cdot Z[5]) \\ = & ( \begin{bmatrix} 1 & X & X^2 & X^3 \end{bmatrix} \cdot (A_P^\top \cdot Z)) \cdot (\begin{bmatrix} 1 & X & X^2 & X^3 \end{bmatrix} \cdot (B_P^\top \cdot Z) ) - \begin{bmatrix} 1 & X & X^2 & X^3 \end{bmatrix} \cdot (C_P^\top \cdot Z) \end{align*}$

Use sage:

sage: x = var("x")
sage: A_P = matrix([[-5,55/6,-5,5/6],[8,-34/3,5,-2/3],[0,0,0,0],[-6,19/2,-4,1/2],[4,-7,7/2,-1/2],[-1,11/6,-1,1/6]])
sage: B_P = matrix([[3,-31/6,5/2,-1/3],[-2,31/6,-5/2,1/3],[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]])
sage: C_P = matrix([[0,0,0,0],[0,0,0,0],[-1,11/6,-1,1/6],[4,-13/3,3/2,-1/6],[-6,19/2,-4,1/2],[4,-7,7/2,-1/2]])
sage: X = vector([1, x, x^2, x^3])
sage: t=(X*(A_P.transpose()*Z))*(X*B_P.transpose()*Z) - X*(C_P.transpose()*Z)
sage: t.expand()
-31/9*x^6 + 103/2*x^5 - 2653/9*x^4 + 4835/6*x^3 - 9574/9*x^2 + 1778/3*x - 88

and it is the same with the data in vitalik's article:
> t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]

If the given $Z$ vector is correct, when the $x = 1, 2, 3, 4, \ t(X) = 0$, it has roots: $X = 1, 2, 3, 4$. So $h(X) = \frac{t(X)}{z(X)}$, which $z(X) = (X-1)(X-2)(X-3)(X-4)$, and $h(X)$ with no remainder:

sage: z = (x-1)*(x-2)*(x-3)*(x-4)
sage: h = t/z
sage: h.reduce_trig()
-31/9*x^2 + 307/18*x - 11/3

also the same with:
> h = t / Z = [-3.666, 17.055, -3.444]