# QAP Step-by-Step
## Metadata
**Status**:: #x
**Zettel**:: #zettel/fleeting
**Created**:: [[2024-03-20]]
**Topic**:: [[♯ Zero-Knowledge Proof]]
**GitHub**:: [circom-circuits/example-qap](https://github.com/doitian/circom-circuits/tree/main/example-qap)
## Function
$
out = x_1^2 + 4x_2^2x_1 - 2
$
## Circuit
```circom
pragma circom 2.0.0;
template QAP() {
signal input x1;
signal input x2;
signal output out;
signal x3;
signal x4;
x3 <== x1 * x1;
x4 <== x1 * x2;
out <== x3 + 4 * x2 * x4 - 2;
}
component main = QAP();
```
Compile
```shell
circom example-qap.circom --r1cs --wasm --sym --c
```
Check symbols
```shell
cat example-qap.sym
```
So witness vector is `[1, out, x1, x2, x3, x4]`
## R1CS
Print r1cs
```shellsession
$ snarkjs r1cs print example-qap.r1cs
[INFO] snarkJS: [ 21888242871839275222246405745257275088548364400416034343698204186575808495616main.x1 ] * [ main.x1 ] - [ 21888242871839275222246405745257275088548364400416034343698204186575808495616main.x3 ] = 0
[INFO] snarkJS: [ 21888242871839275222246405745257275088548364400416034343698204186575808495616main.x1 ] * [ main.x2 ] - [ 21888242871839275222246405745257275088548364400416034343698204186575808495616main.x4 ] = 0
[INFO] snarkJS: [ 21888242871839275222246405745257275088548364400416034343698204186575808495613main.x2 ] * [ main.x4 ] - [ 218882428718392752222464057452572750885483644004160343436982041865758084956151 +21888242871839275222246405745257275088548364400416034343698204186575808495616main.out +main.x3 ] = 0
```
Parse constraints as `Aw x Bw - Cw = 0`
A
```
[ 1, out, x1, x2, x3, x4]
[ 0, 0, -1, 0, 0, 0]
[ 0, 0, -1, 0, 0, 0]
[ 0, 0, 0, -4, 0, 0]
```
B
```
[ 1, out, x1, x2, x3, x4]
[ 0, 0, 1, 0, 0, 0]
[ 0, 0, 0, 1, 0, 0]
[ 0, 0, 0, 0, 0, 1]
```
C
```
[ 1, out, x1, x2, x3, x4]
[ 0, 0, 0, 0, -1, 0]
[ 0, 0, 0, 0, 0, -1]
[-2, -1, 0, 0, 1, 0]
```
Verify
```python
from sympy import symbols, Matrix, hadamard_product
one, out, x1, x2, x3, x4 = symbols("one out x1 x2 x3 x4")
w = Matrix([one, out, x1, x2, x3, x4])
A = Matrix([[0, 0, -1, 0, 0, 0], [0, 0, -1, 0, 0, 0], [0, 0, 0, -4, 0, 0]])
B = Matrix([[0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 1]])
C = Matrix([[0, 0, 0, 0, -1, 0], [0, 0, 0, 0, 0, -1], [-2, -1, 0, 0, 1, 0]])
print(hadamard_product(A * w, B * w) - C * w)
# => Matrix([[-x1**2 + x3], [-x1*x2 + x4], [2*one + out - 4*x2*x4 - x3]])
```
## Lagrange
```python
def lagrange(m):
result = Matrix()
rows = m.shape[0]
xs = list(range(1, rows + 1))
zeros = [0] * rows
for i in range(m.shape[1]):
p = interpolating_poly(rows, x, X=xs, Y=list(m.col(i)))
coeffs = p.as_poly().all_coeffs() if not p.is_zero else zeros
while len(coeffs) < rows:
coeffs.insert(0, 0)
result = result.col_insert(i + 1, Matrix(coeffs))
return result
U = lagrange(A)
V = lagrange(B)
W = lagrange(C)
print(U)
# => Matrix([[0, 0, 1/2, -2, 0, 0], [0, 0, -3/2, 6, 0, 0], [0, 0, 0, -4, 0, 0]])
print(V)
# => Matrix([[0, 0, 1/2, -1, 0, 1/2], [0, 0, -5/2, 4, 0, -3/2], [0, 0, 3, -3, 0, 1]])
print(W)
# => Matrix([[-1, -1/2, 0, 0, 0, 1], [3, 3/2, 0, 0, 1, -4], [-2, -1, 0, 0, -2, 3]])
```
## h(x)
```python
witness = Matrix([1, 74, 2, 3, 4, 6])
Ua = Poly.from_list(list(U * witness), gens=x)
Va = Poly.from_list(list(V * witness), gens=x)
Wa = Poly.from_list(list(W * witness), gens=x)
t = Poly(1, x)
for i in range(U.shape[0]):
t *= Poly(x - i - 1)
h = div(Ua * Va - Wa, t)[0]
print(Ua * Va - Wa - h * t)
# => Poly(0, x, domain='ZZ')
```
> [!important]
> U is a list of 6 polynomials. `U * witness` multiply polynomials with numbers element-wisely and add them together to create a new polynomial.
>
> The value of x does not matter. We need to approve that `Ua * Va` and `Wa + h * t` are two identical polynomials using Schwartz-Zippel Lemma by evaluate them at a random x.
>
> The proof also requires algorithm like Groth16 to prevent forged elliptic curve points.
## References
- [Quadratic Arithmetic Programs for Zero Knowledge Proofs (rareskills.io)](https://www.rareskills.io/post/quadratic-arithmetic-program)
- [R1CS to Quadratic Arithmetic Program over a Finite Field in Python (rareskills.io)](https://www.rareskills.io/post/r1cs-to-qap)