2.8 KiB
Quadratic Arithmetic Programs (QAPs)
QAPs from R1CS
One way to prove that we know a satisfying assignment to some rank-1 constraint system is to actually reveal our assignment \textbf{z} to the verifier. The verifier can check that \langle \textbf{a}_i, \textbf{z} \rangle \cdot \langle \textbf{b}_i, \textbf{z} \rangle = \langle \textbf{c}_i, \textbf{z} \rangle$holds for alli$. However, this isn't zero-knowledge, nor does it lead to short proofs.
Our first goal is to compress the $idifferent inner product equations into a *single* equation. We do this through the use of [interpolation polynomials](https://en.wikipedia.org/wiki/Polynomial_interpolation). Letu_i(x)be a polynomial that interpolates over all of theith elements in \textbf{a}atkdistinct pointsr_0, r_1, ..., r_{k-1}. Do the same for v_i(x)with\textbf{b}andw_i(x)with\textbf{c}$.
We can now express our constraint system in a single equation:
\langle \textbf{u(x)}, \textbf{z} \rangle \cdot \langle \textbf{v(x)}, \textbf{z} \rangle = \langle \textbf{w(x)}, \textbf{z} \rangle
If we evaluate this equation at the point $x = r_i, the vectors of interpolation polynomials will evaluate into vectors of coefficients that correspond to the ith constraint. This means that although we have simplified the condition into a single equation, we still have to check that the equation is satisfied at k$ different points.
Let's rearrange the equation slightly by setting the right hand side to zero:
\langle \textbf{u(x)}, \textbf{z} \rangle \cdot \langle \textbf{v(x)}, \textbf{z} \rangle - \langle \textbf{w(x)}, \textbf{z} \rangle = 0
It is possible for us to check that this equation holds at each of the points $r_0, r_1, ..., r_{k-1}by constructing a **target polynomial**t(x) = \prod_{i=0}^{k-1} (x - r_i)which has roots at each point. It turns out that if\langle \textbf{u(x)}, \textbf{z} \rangle \cdot \langle \textbf{v(x)}, \textbf{z} \rangle - \langle \textbf{w(x)}, \textbf{z} \ranglereally is zero at each point, thent(x)will divide it. Let's call thek - 2degree quotient polynomialh(x)$.
The prover now gives the verifier the assignment \textbf{z} and the coefficients \textbf{h} of the $h(x)polynomial, and the verifier can [probabilistically check](https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma) that the constraint system is satisfied by choosing a randomx \in \mathbb{F}_q$ and checking that the following equation holds:
\langle \textbf{u(x)}, \textbf{z} \rangle \cdot \langle \textbf{v(x)}, \textbf{z} \rangle - \langle \textbf{w(x)}, \textbf{z} \rangle = \langle \textbf{x}^{k-1}, \textbf{h} \rangle \cdot t(x)
We call this relation a quadratic arithmetic program or QAP for short.