# QAP

## Introduction

Given a R1CS instance $$\bm{A},\bm{B},\bm{C}\in \mathbb{F}^{m\times n}$$, the verifier has to check if it holds:

$$
\bm{Az}\circ\bm{Bz}\stackrel{?}=\bm{Cz}
$$

which is a $$O(m)$$ complexity task so we want to somehow reduce this to $$O(1)$$.

### Preliminaries

1. [Number Theoretic Transform](https://fractalyze.gitbook.io/intro/~/revisions/0AAov1j5GF4J6Ca62R1w/primitives/number-theoretic-transform)
2. [Schwartz-Zippel Lemma](https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma)

## Protocol Explanation

Let's consider a simpler case where we want to check if $$\bm{Au}=\bm{Bv}$$. Denote $$i$$th column vectors of $$\bm{A}$$ and $$\bm{B}$$ as $$\bm{a}\_i$$ and $$\bm{b}\_i$$ respectively. Then, what we want to check becomes:

$$
\sum\_{i=1}^n\bm{a}*iu\_i\stackrel{?}=\sum*{i=1}^n\bm{b}\_iv\_i
$$

So if we consider polynomials $$f\_i=\mathsf{INTT}(\bm{a}\_i)$$ and $$g\_i=\mathsf{INTT}(\bm{b}\_i)$$ then, it is equivalent of checking if this two are same:

$$
\sum\_{i=1}^nf\_iu\_i\stackrel{?}=\sum\_{i=1}^n g\_iv\_i
$$

Since the sum itself is another polynomial, if we denote them as $$f$$ and $$g$$, we have simple equality check:

$$
f\stackrel{?}=g
$$

This check can be done using a single random challenge following the Schwartz-Zippel Lemma.

### Applying to R1CS

Similarly, let's denote the polynomial interpolation of $$i$$th column of $$\bm{A}$$, $$\bm{B}$$, $$\bm{C}$$ as $$f\_{a,i},f\_{b,i}, f\_{c,i}$$. Then, the R1CS check becomes:

$$
\sum\_{i=1}^nf\_{a,i}z\_i\sum\_{i=1}^nf\_{b,i}z\_i\stackrel{?}=\sum\_{i=1}^n f\_{c,i}z\_i
$$

Since each sum results in a single polynomial, we can simplify this equation as:

$$
f\_a\circ f\_b\stackrel{?}=f\_c
$$

### Degree imbalance

The equality above is not as simple as it looks since the $$\deg (f\_a\circ f\_b)=2m =2\deg(f\_c)$$. Because of this imbalance, our polynomials are not necessarily equal but if we think about the $$\mathsf{INTT}$$, they must be equal over the evaluation domain:

$$
\forall i =0,\dots,m-1: (f\_a\circ f\_b)(\omega^i)= f\_c(\omega^{i})
$$

which is equivalent to checking:

$$
\forall i =0,\dots,m-1: (f\_a\circ f\_b-f\_c)(\omega^i)\stackrel{?}=0
$$

In other words, $$f\_a\circ f\_b - f\_c$$ should be divisible by the degree $$m$$ **zero polynomial**:

$$
t(X)=(X-w^0)(X-\omega^1)\dots(X-w^{m-1})=X^m-1
$$

Therefore, the **quotient polynomial** must be well defined:

$$
h(X)=\frac{f\_a\circ f\_b - f\_c}{t}(X)
$$

### Final formula for QAP

Prover commits to $$f\_a,f\_b,f\_c,h$$ polynomials and verifier checks with random challenge $$\tau \in\_R \mathbb{F}$$:

$$
f\_a(\tau)\cdot f\_b(\tau)=f\_c(\tau) + h(\tau)\cdot t(\tau)
$$

## References

1. <https://rareskills.io/post/quadratic-arithmetic-program#qap-end-to-end>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://fractalyze.gitbook.io/intro/zk/arithmetization/r1cs/qap.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.