# Explaining linearisation technique in SNARKS that use KZG poly commitments

### Motivation:
In the following, we include two examples of circuits a la PLONK and details on how to linearize the resulting quotient polynomial (which we denote by $t(X)$) more efficiently such that the number of resulting field elements that are part of the proof is smaller then by naive opening.

### Notation:
Let $H = \{1, \omega, \ldots, \omega^{n-1}\}$, where $\omega$ is the $n$-th root of unity in $\mathbb{F}$.

Let the **srs** be $[1]_1, [x]_1, [x^2]_1, \ldots, [x^n]_1, [1]_{2}, [x]_{2}$, where $x \in \mathbb{F}$ is the so-called "toxic waste", $[1]_{1}$ is the generator of the source group $\mathbb{G}_1$ and $[1]_{2}$ is the generator of the source group $\mathbb{G}_{2}$.

### Example 1:
Assume that our circuit is defined only by one constraint defined in turn by the polynomial $a(X) \in \mathbb{F}[X]$ such that for all $z \in H$, $a(z) = 0$. This is equivalent to $\exists \ t(X) \in \mathbb{F}[X]$
$$t(X)(X^n-1) = a(X).$$

In this case, the prover computes the KZG polynomial commitments $[t]_{1} = t(x) \cdot [1]_{1}$ and $[a]_{1} = a(x) \cdot [1]_{1}$ and sends them to the verifier.

The verifier replies with $\zeta \xleftarrow{r} \mathbb{F}$ and the prover computes the opening evaluation $\bar{a} = a(\zeta)$ and sends $\bar{a}$ to the verifier.

In order to complete the verification, the verifier uses a standard batched version of KZG poly commitment for opening commitments $[t]_1$ and $[a]_{1}$ at $\zeta$, and, in the respective verification equation, for the evaluation of $t(\zeta)$ (which, in order to increase succinctness, he did not receive from the prover), the verifier computes and uses the value $\bar{t} = \frac{\bar{a}}{\zeta^n-1}$.

### Example 2:
Assume that our circuit is defined by three constraints defined in turn by the polynomials $a_1(X), a_2(X), b_1(X), b_2(X), b_3(X) \in \mathbb{F}[X]$ such that for all $z \in H$, $a_i(z) \cdot b_i(z) = 0, \forall i \in \{1,2\}$ and $b_3(z) \cdot (1 - b_3(z)) = 0$, for all $z \in H.$ This is equivalent to $\forall \phi \xleftarrow{r} \mathbb{F}$, $\exists \ t(X) \in \mathbb{F}[X]$
$$t(X)(X^n-1) = a_1(X) \cdot b_1(X) + \phi \cdot a_2(X) \cdot b_2(X) + \phi^2 \cdot b_3(X) \cdot ( 1-b_3(X)).$$

Assume also that the polynomials $b_1(X), b_2(X), b_3(X) \in \mathbb{F}[X]$ are known to both the prover and the verifier and, as part of the once per circuit pre-processing step, both the prover and the verifier compute the commitments $[b_1]_{1} = b_1(x) \cdot [1]_{1}, [b_2]_{1} = b_2(x) \cdot [1]_{1}, [b_3]_{1} = b_3(x) \cdot [1]_{1}.$

In this case, the prover computes commitments $[t]_{1} = t(x) \cdot [1]_{1}$, $[a_1]_{1} = a_1(x) \cdot [1]_{1}$, $[a_2]_{1} = a_2(x) \cdot [1]_{1}$ and sends them to verifier.

The verifier replies with $\zeta \xleftarrow{r} \mathbb{F}$ and the prover computes $\overline{a_1} = a_1(\zeta)$, $\overline{a_2} = a_2(\zeta)$, $\overline{b_3} = b_3(\zeta)$. The prover also computes the polynomial
$$r(X) = \overline{a_1}\cdot b_1(X) + \phi \cdot \overline{a_2} \cdot b_2(X)$$ and the evaluation $\bar{r} = r(\zeta)$. Finally, the prover sends $(\overline{a_1}, \overline{a_2}, \overline{b_3}, \bar{r})$ to the verifier.

In order to complete the verification, the verifier uses a standard batched version of KZG poly commitment for opening commitments $[t]_1$, $[a_1]_{1}$, $[a_2]_{1}$, $[r]_{1}$ and $[b_3]_{1}$ at $\zeta$, and, in the respective verification equation, for the evaluation of $t(\zeta)$ (which, in order to increase succinctness, he did not receive from the prover), the verifier computes and uses the value
$$\bar{t} = \frac{\bar{r} + \phi^2 \cdot \overline{b_3} \cdot (1 -\overline{b_3})}{\zeta^n -1}.$$

Also, the verifier does not need to be sent the commitment to $r(X)$, which is $[r]_{1} = r(x) \cdot [1]_{1}$ as the verifier can compute it himself as $[r]_{1} = \overline{a_1} \cdot [b_1]_{1} + \overline{a_2} \cdot [b_2]_{1}$.

### Efficiency summary:
In Example 1, the prover does not need to send, as part of the proof, the evaluation $\bar{t} = t(\zeta)$ to the verifier, as the verifier can compute it by himself with the proof elements he already received.

In Example 2, the prover does not need to send, as part of the proof, the evaluations $\bar{b_1} = b_1(\zeta)$ and $\bar{b_2} = b_2(\zeta)$ as both are included in the evaluation $\bar{r} = r(\zeta)$. Also, as before, the prover does not need to send the evaluation $\bar{t} = t(\zeta)$ as this can be computed by the verifier from the elements of the proof already sent to him.