First of all, we have to clear what does **Zero Check** look like. Since the bottom protocol of Plonk is **Zero Check**, while the bottom protocol of Spartan is **Sum Check**.
<br />
# Zero Check
If you have a committed polynomial $\widetilde{f(X)}$, and send it to verifier.
<br />
After then, whenever verifier wants a evaluation on a specified opening point $\zeta$:
1. verifier sends $\zeta$ to prover
2. prover compute the evaluation and sends $y$ to verifier
<br />
The problem is how to prove that the evaluation is right:
$$
y \overset{?}= f(\zeta) \\
$$
namely :
$$
f(\zeta) - y \overset{?}= 0 \\
$$
this is so-called **zero-check**! It will pass if and only if exists a *quotient polynomial* $q(X)$:
$$
f(X) - y = q(X)(X - \zeta), X \in \mathbb{F_p}
$$
and verifier will check through pairing method:
$$
e([f(X) - y + \zeta * q(X)]_g, [1]_h) \overset{?}= e([q(X)]_g,[X]_h)
$$
<br />
## Protocol
- prover sends commitment of hidden polynomial $\widetilde{f(X)}$ or $[f]_g$ to verifier at the very first moment
...
- whenever verifier wants some evaluation $f(\zeta)$
- verifier sends opening point $\zeta$ to prover
- prover sends $y$ claimed to be equal with $f(\zeta)$, and its proof $\widetilde{q(X)}$ or $[q]_g$ to verifier
- verifier check $e([f]_g - [y]_g + \zeta [q]_g, [1]_h) \overset{?}= e([q]_g,[\tau]_h)$
<br />
# Vanilla Plonk
no lookup, no permutation, no multiplication gate, just **addition gate**!
<br />
Upon this circumstance, we will use **batch opening** technic later on.
## Problem
For simplified illustration, we have the modulus:
$$
p = 17
$$
witness matrix $w$:
|i|w_a|w_b|w_c|
|---|---|---|---|
|0|1|2|3|
|1|3|4|7|
|2|5|6|11|
|3|7|8|15|
and (public) selector matrix $q$:
|i|q_L|q_R|q_O|
|---|---|---|---|
|0|1|1|1|
|1|1|1|1|
|2|1|1|1|
|3|1|1|1|
We only have 4 additive gate, and no wire sharing here!
<br />
so we have the gate check:
$$
q_L * \color{red}{w_a} + q_R * \color{red}{w_b} \overset{?}= q_O * \color{red}{w_c}
$$
on element-wise. The problem is the <span style="color:red"> red part vectors </span> are unknown to verifier, so how to get it done?
<br />
## Round One
If we a subgroup of multiplication $H$ over finite field $\mathbb{F}_{17}$, whose *order* and *generator* are both 4:
$$
H = (4^0, 4^1, 4^2, 4^3) = (1, 4, 16, 13)
$$
we can encode these vectors with *evaluation encoded* polynomials and get its coefficients through **IFFT** algorithm:
$$
\begin{aligned}
q_L &= (1, 0, 0, 0) \\
q_R &= (1, 0, 0, 0) \\
q_O &= (1, 0, 0, 0) \\
w_a &= (4, 3, 16, 12) \\
w_b &= (5, 3, 16, 12) \\
w_c &= (9, 6, 15, 7) \\
\end{aligned}
$$
<br />
Therefore we have the polynomial representated gate check equation:
$$
q_L(X) * \color{red}{w_a(X)} + q_R(X) * \color{red}{w_b(X)} \overset{?}= q_O(X) * \color{red}{w_c(X)}, X \in H
$$
The straw-man solution would be like, "prover sends all these polynomials to verifier, then verifier checks on domain $H$ one-by-one".
Two problems here:
1. The <span style="color:red">red part polynomials</span> is unknown to verifier, they cannot be sent directly.
2. The verification cost is linear with gate number, can we just do ONE check?
<br />
## Round Two
Regarding to the first problem, in order to hide these polynomials, we can commit the <span style="color:red">red part polynomials</span> $w_a(X), w_b(X), w_c(X)$, trap them into three points:
$$
\begin{aligned}
\widetilde{w_a(X)} \overset{commit} \longleftarrow w_a(X) \\
\\
\widetilde{w_b(X)} \overset{commit} \longleftarrow w_b(X) \\
\\
\widetilde{w_c(X)} \overset{commit} \longleftarrow w_c(X) \\
\end{aligned}
$$
<br />
For the second problem, introducing additional vanishing polynomial $z_H(X)$ and **quotient polynomial $t(X)$**, the check equation becomes:
$$
q_L(X) * \color{red}{w_a(X)} + q_R(X) * \color{red}{w_b(X)} - q_O(X) * \color{red}{w_c(X)} \overset{?}= \color{red}{t(X)} * z_H(X), X \in \mathbb{F}_{17}
$$
<br />
According to **Schwartz-Zippel Lemma**, the only thing we need to do is:
$$
q_L(\zeta) * \color{red}{w_a(\zeta)} + q_R(\zeta) * \color{red}{w_b(\zeta)} - q_O(\zeta) * \color{red}{w_c(\zeta)} \overset{?}= \color{red}{t(\zeta)} * z_H(\zeta), \zeta \in \mathbb{F}_{17}
$$
<br />
So we'll have a simple but good enough solution:
1. prover compute commitment for quotient polynomial $\color{red}{\widetilde{t(X)}}$, and commitments of other hided polynomials $\color{red}{\widetilde{w_a(X)}}, \color{red}{\widetilde{w_b(X)}}, \color{red}{\widetilde{w_c(X)}}$, thereafter send them to verifier
- <span style="color:blue"> computing the quotient polynomial $t(X)$ might not be easy, especially when the degree of left part polynomial is pretty high due to **multiplications**</span>
3. verifier sends a opening point $\zeta$ to prover
4. prover sends $y_{w_a},y_{w_b}, y_{w_c}$ to verifier , claiming that they are equal to the actual evaluations of the hided polynomials $w_a(\zeta),w_b(\zeta),w_c(\zeta)$, and $y_t$ equals $t(\zeta)$
5. prover also need to send **PROOFS** along with the evaluations in order to prove that they are the right ones
6. verifier check that these evaluations are right provided **PROOFS** through some computation with sub-linear time cost
7. if pass, verifier can easily check the equation above
*verifier also need to get evaluations $q_L(\zeta), q_R(\zeta), q_O(\zeta)$ through interpolating* method.
<br />
But, how does the **PROOFS** look like, and how to verify evaluations with **PROOFS**?
<br />
## Round Three
According to **zero-check**, prover need to send fours proofs $\widetilde{q_{w_a}(X)},\widetilde{q_{w_b}(X)},\widetilde{q_{w_c}(X)}, \widetilde{q_t(X)}$ to verifier, and verifier will check that one-by-one.
<br />
Alltogether we have four checks:
$$
\begin{aligned}
0 &\overset{?}= t(\zeta) - \color{red}{y_t} \\
0 &\overset{?}= w_a(\zeta) - \color{red}{y_{w_a}} \\
0 &\overset{?}= w_b(\zeta) - \color{red}{y_{w_b}} \\
0 &\overset{?}= w_c(\zeta) - \color{red}{y_{w_c}} \\
\end{aligned}
$$
and the final check :
$$
\color{red}{y_t} = (q_L(\zeta) * \color{red}{y_{w_a}} + q_R(\zeta) * \color{red}{y_{w_b}} - q_O(\zeta) * \color{red}{y_{w_c})} * \frac{1}{z_H(\zeta)}
$$
<br />
Actually we can **batch all openging checks into one** through another challenge factor $\nu$:
$$
\begin{aligned}
L(X) &= (t(X) - y_t) + \nu * (w_a(X) - y_{w_a}) + \nu^2 * (w_b(X) - y_{w_b}) + \nu^3 * (w_c(X) - y_{w_c}) \\
\\
0 &\overset{?}= L(\zeta) \\
\end{aligned}
$$
<br />
we can verify this equation through **zero-check** protocol:
$$
\begin{aligned}
&L(X) = q(X) * (X - \zeta), X \in \mathbb{F}_{17} \\
&\Downarrow \\
&L(X) + \zeta * q(X) = q(X) * X , X \in \mathbb{F}_{17} \\
&\Downarrow \\
&e([L]_g + \zeta [q]_g, [1]_h) = e([q]_g, [\tau]_h) \\
\end{aligned}
$$
<br />
## Protocol
#### Compute Polynomials and Commitments
- prover compute $\widetilde{w_a(X)}, \widetilde{w_b(X)}, \widetilde{w_c(X)}, \widetilde{t(X)}$, and send them to verifier
- <span style="color:blue"> computing the quotient polynomial $t(X)$ might not be easy, especially when the degree of left part polynomial is pretty high due to **multiplications**</span>
<br />
#### Opening Evaluations and Proofs
- verifier send opening point $\zeta$ and batch factor $\nu$ to prover
- prover compute opening evaluations $y_t, y_{w_a}, y_{w_b}, y_{w_c}$ along with their batched proof $\widetilde{q_{(X)}}$ or $\color{red}{[q]_g}$, and send them to verifier
$$
\begin{aligned}
L(X) &= (t(X) - y_t) + \nu * (w_a(X) - y_{w_a}) + \nu^2 * (w_b(X) - y_{w_b}) + \nu^3 * (w_c(X) - y_{w_c}) \\
q(X) &= L(X) * \frac{1}{X - \zeta} \\
\end{aligned}
$$
<br />
#### Check
- verifier compute commitment of batched polynomial $\widetilde{L(X)}$ or $\color{red}{[L]_g}$, having been provided $\widetilde{w_a(X)}, \widetilde{w_b(X)}, \widetilde{w_c(X)}, \widetilde{t(X)}, y_t, y_{w_a}, y_{w_b}, y_{w_c}$
$$
\begin{aligned}
E &= y_t + \alpha * y_{w_a} + \alpha^2 * y_{w_b} + \alpha^3 * y_{w_c} \\
\widetilde{L(X)} &= \boxed{\widetilde{t(X)} + \alpha * \widetilde{w_a(X)} + \alpha^2 * \widetilde{w_b(X)} + \alpha^3 * \widetilde{w_c(X)}} - \boxed{E} \\
\end{aligned}
$$
> consisting two parts: linear combination of individual polynomial commitments and evaluations
- verifier do the **paring-check**
$$
\begin{aligned}
e(\color{red}{[L]_g} + \zeta \color{red}{[q]_g}, [1]_h)
&\overset{?}= e(\color{red}{[q]_g}, [\tau]_h)
\end{aligned}
$$
- verifier do the final check
$$
\color{red}{y_t} = (q_L(\zeta) * \color{red}{y_{w_a}} + q_R(\zeta) * \color{red}{y_{w_b}} - q_O(\zeta) * \color{red}{y_{w_c})} * \frac{1}{z_H(\zeta)}
$$
<br />
# Vanilla Plonk with High-degree Gate
no lookup, no permutation, just addition gate and **multiplication gate**!
<br />
Upon this, we will use **polynomial linearization** technic later on!
## Problem
witness matrix $w$:
|i|w_a|w_b|w_c|
|---|---|---|---|
|0|1|2|3|
|1|3|4|12|
|2|5|6|13|
|3|7|8|15|
and (public) selector matrix $q$:
|i|q_L|q_R|q_M|q_O|
|---|---|---|---|---|
|0|1|1|0|1|
|1|0|0|1|1|
|2|0|0|1|1|
|3|1|1|0|1|
We have 2 additive gate, 2 multiplication gate, and no wire sharing here.
<br />
The gate check will be like:
$$
q_L * \color{red}{w_a} + q_R * \color{red}{w_b} + q_M * \color{red}{w_a} * \color{red}{w_b} \overset{?}= q_O * \color{red}{w_c}
$$
<br />
and the polynomial encoding would be like:
$$
q_L(X) * \color{red}{w_a(X)} + q_R(X) * \color{red}{w_b(X)} + q_M(X) * \color{red}{w_a(X)} * \color{red}{w_b(X)} - q_O(X) * \color{red}{w_c(X)} \overset{?}= \color{red}{t(X)} * z_H(X), X \in \mathbb{F}_{17}
$$
<br />
## Protocol
#### Preprocess
- selector vector polynomials $q_L(X), q_R(X), q_M(X), q_O(X)$
- id permutation polynomials $\sigma_a(X), \sigma_b(X), \sigma_c(X)$
- mask and commit for these public polynomials $\widetilde{q_L(X)}, \widetilde{q_R(X)}, \widetilde{q_M(X)}, \widetilde{q_O(X)}, \widetilde{\sigma_a(X)}, \widetilde{\sigma_b(X)}, \widetilde{\sigma_c(X)}$
<br />
#### Compute Polynomials and Commitments
- witness vector polynomials $\color{red}{w_a(X)}, \color{red}{w_b(X)}, \color{red}{w_c(X)}$ and public input vector polynomial $\phi(X)$
- quotient polynomials $\color{red}{t(X)}$
- degree of quotient polynomial is $2n$, namely 2 times of size of domain $H$, so we need to new domain $H'$ specially for quotient polynomial with size $3n$ (convenient for computing)
- compute evaluations of vanishing polynomial on quotient domain $H'$ through somewhat trick
- compute evaluations of polynomials $\color{red}{w_a(X)}, \color{red}{w_b(X)}, \color{red}{w_c(X)}, q_L(X), q_R(X), q_M(X), q_O(X)$ on quotient domain $H'$ through *FFT* algorithm
- compute evaluations of quotient polynomial $\color{red}{t(X)}$, and convert into coefficient encoding through *IFFT* algorithm
- split $\color{red}{t(X)}$ into two parts $\color{red}{t_1(X)} , \color{red}{t_2(X)}$, each stayed on domain $H$
$$
t(X) = \sum_{i = 0}^2 X^{i * n} * t_i(X), X \in H
$$
> the actual degree of quotient polynomial $t(X)$ is $2n$, not $3n$, so we can definitely split it into two sub-polynomials both with domain size $n$
- compute commitments for witness vector polynomials and quotient polynomials $\color{red}{\widetilde{w_a(X)}}, \color{red}{\widetilde{w_b(X)}}, \color{red}{\widetilde{w_c(X)}}, \color{red}{\widetilde{t_1(X)}}, \color{red}{\widetilde{t_2(X)}}$, and send them to verifier
<br />
#### Opening Evaluations and Proofs
- verifier send opening point $\zeta$ and linearization factor $\nu$ to prover
- prover compute opening evaluations $y_{w_a}$, claiming equals $w_a(\zeta)$
- prover compute linearized polynomial $L(X)$, and its quotient polynomial $q(X)$
$$
\begin{aligned}
L(X) &= q_L(\zeta) * \color{red}{w_a(X)} + q_R(\zeta) * \color{red}{w_b(X)} + q_M(\zeta) * y_{w_a} * \color{red}{w_b(X)} - q_O(\zeta) * \color{red}{w_c(X)} - z_H(\zeta) * (\color{red}{t_1(X)} + \zeta^n * \color{red}{t_2(X)}) + \nu * (\color{red}{w_a(X)} - y_{w_a}) \\
q(X) &= L(X) * \frac{1}{X - \zeta} \\
\end{aligned}
$$
- prover compute opening proof for linearized polynomial $\widetilde{q(X)}$ or $[q]_g$, having been provided $\color{red}{\widetilde{w_a(X)}}, \color{red}{\widetilde{w_b(X)}},\color{red}{\widetilde{w_c(X)}}, \color{red}{\widetilde{t_1(X)}}, \color{red}{\widetilde{t_2(X)}}$
- prover send $y_{w_a}, \widetilde{q(X)}$ to verifier
<br />
#### Check
- verifier compute commitment of linearized polynomial $\widetilde{L(X)}$ or $[L]_g$, having been provided individual commitments $\color{red}{\widetilde{w_a(X)}}, \color{red}{\widetilde{w_b(X)}},\color{red}{\widetilde{w_c(X)}}, \color{red}{\widetilde{t_1(X)}}, \color{red}{\widetilde{t_2(X)}}$ and open evaluations $y_{w_a}$:
<br />
$$
\begin{aligned}
\widetilde{L(X)} &= q_L(\zeta) * \color{red}{\widetilde{w_a(X)}} + q_R(\zeta) * \color{red}{\widetilde{w_b(X)}} + q_M(\zeta) * y_{w_a} * \color{red}{\widetilde{w_b(X)}} - q_O(\zeta) * \color{red}{\widetilde{w_c(X)}} - z_H(\zeta) * (\color{red}{\widetilde{t_1(X)}} + \zeta^n * \color{red}{\widetilde{t_2(X)}}) + \nu * (\color{red}{\widetilde{w_a(X)}} - y_{w_a}) \\
&= \boxed{q_L(\zeta) * \color{red}{\widetilde{w_a(X)}} + q_R(\zeta) * \color{red}{\widetilde{w_b(X)}} + q_M(\zeta) * y_{w_a} * \color{red}{\widetilde{w_b(X)}} - q_O(\zeta) * \color{red}{\widetilde{w_c(X)}} - z_H(\zeta) * (\color{red}{\widetilde{t_1(X)}} + \zeta^n * \color{red}{\widetilde{t_2(X)}}) + \nu * \color{red}{\widetilde{w_a(X)}}} - \boxed{\nu * y_{w_a}} \\
\end{aligned}
$$
<br />
> consisting two parts: linear combination of individual polynomial commitments and opening evaluations
- verifier do the **paring check**
$$
e([L]_g + \zeta [q]_g, [1]_h) \overset{?}= e([q]_g, [\tau]_h)
$$
<br />
# Turbo Plonk
## Problem
witness matrix $w$:
|i|w_a|w_b|w_c|
|---|---|---|---|
|0|1|2|<span style="color:green">3</span>|
|1|<span style="color:green">3</span>|4|12|
|2|<span style="color:blue">5</span>|6|13|
|3|7|<span style="color:blue">5</span>|12|
and (public) selector matrix $q$:
|i|q_L|q_R|q_M|q_O|
|---|---|---|---|---|
|0|1|1|0|1|
|1|0|0|1|1|
|2|0|0|1|1|
|3|1|1|0|1|
<br />
We have 2 additive gate, 2 multiplication gate, and 2 wiring shares here.
<br />
So the extended id matrix, $\omega = 4$:
|i|id_a|id_b|id_c|
|---|---|---|---|
|0|$\omega^0$|$k \omega^0$|<span style="color:green">$k^2 \omega^0$</span>|
|1|<span style="color:green">$\omega^1$</span>|$k \omega^1$|$k^2 \omega^1$|
|2|<span style="color:blue">$\omega^2$</span>|$k \omega^2$|$k^2 \omega^2$|
|3|$\omega^3$|<span style="color:blue">$k \omega^3$</span>|$k^2 \omega^3$|
The permutated id or $\sigma$ matrix:
|i|id_a|id_b|id_c|
|---|---|---|---|
|0|$\omega^0$|$k \omega^0$|<span style="color:green">$\omega^1$</span>|
|1|<span style="color:green">$k^2 \omega^0$</span>|$k \omega^1$|$k^2 \omega^1$|
|2|<span style="color:blue">$k \omega^3$</span>|$k \omega^2$|$k^2 \omega^2$|
|3|$\omega^3$|<span style="color:blue">$\omega^2$</span>|$k^2 \omega^3$|
<br />
The gate check will be like:
$$
q_L * \color{red}{w_a} + q_R * \color{red}{w_b} + q_M * \color{red}{w_a} * \color{red}{w_b} \overset{?}= q_O * \color{red}{w_c}
$$
<br />
along with wiring permutation check, the final polynomial constrain would be like:
$$
\begin{aligned}
\color{red}{t(X)} * z_H(X) &\overset{?}= q_L(X) * \color{red}{w_a(X)} + q_R(X) * \color{red}{w_b(X)} + q_M(X) * \color{red}{w_a(X)} * \color{red}{w_b(X)} - q_O(X) * \color{red}{w_c(X)} + \alpha * (z(\omega X) * g(X) - z(X) * f(X)) + \alpha^2 * L_0(X) * (z(X) - 1), X \in \mathbb{F}_{17} \\
\\
f(X) &= \prod_{i = \{a, b, c\}} (w_i(X) + \beta * k_i * X + \gamma) \\
\\
g(X) &= \prod_{i = \{a, b, c\}} (w_i(X) + \beta * \sigma_i(X) + \gamma) \\
\end{aligned}
$$
<br />
## Protocol
#### Preprocess
- selector vector polynomials $q_L(X), q_R(X), q_M(X), q_O(X)$
- id permutation polynomials $\sigma_a(X), \sigma_b(X), \sigma_c(X)$
- mask and commit for these public polynomials $\widetilde{q_L(X)}, \widetilde{q_R(X)}, \widetilde{q_M(X)}, \widetilde{q_O(X)}, \widetilde{\sigma_a(X)}, \widetilde{\sigma_b(X)}, \widetilde{\sigma_c(X)}$
<br />
#### Polynomials and Commitments
- witness vector polynomials $w_a(X), w_b(X), w_c(X)$ and public input vector polynomial $\phi(X)$
- grand-product vector polynomials $z(X)$
$$
\begin{aligned}
z(X) &= \frac{\prod_{i = \{a, b, c\}} f_i(X)}{\prod_{i = \{a, b, c\}} g_i(X)} \\
\\
f_i(X) &= w_i(X) + \beta * k_i * X + \gamma \\
g_i(X) &= w_i(X) + \beta * \sigma_i(X) + \gamma \\
\end{aligned}
$$
- quotient polynomials $t(X)$
- degree of quotient polynomial is $3n$, namely 3 times of size of domain $H$, so we need to new domain $H'$ specially for quotient polynomial with size $4n$ (convenient for computing)
- compute evaluations of vanishing polynomial on quotient domain $H'$ through somewhat trick
- compute evaluations of polynomials $w_a(X), w_b(X), w_c(X), q_L(X), q_R(X), q_M(X), q_O(X)$ on quotient domain $H'$ through *FFT* algorithm
- compute evaluations of quotient polynomial $t(X)$ on domain $H'$, and convert into coefficient encoding through *IFFT* algorithm
- split $t(X)$ into 3 parts $t_0(X), t_1(X), t_2(X)$, each stayed on domain $H$
$$
t(X) = \sum_{i = 0}^3 X^{i * n} * t_i(X), X \in H
$$
> the actual degree of quotient polynomial $t(X)$ is $3n$, not $4n$, so we can definitely split it into 3 sub-polynomials both with domain size $n$
- mask and commit for these individual polynomials $\widetilde{w_a(X)}, \widetilde{w_b(X)}, \widetilde{w_c(X)}, \widetilde{t_0(X)}, \widetilde{t_1(X)}, \widetilde{t_2(X)}, \widetilde{z(X)}$, and send them to verifier
<br />
#### Opening Evaluations and Proofs
- verifier send opening point $\zeta$ and linearization factor $\nu$ to prover
- prover compute opening evaluations $y_{w_a}, y_{w_b}, y_{w_c}, y_{\sigma_a}, y_{\sigma_b}, y_{z_\omega}$, claiming equals $w_a(\zeta), w_b(\zeta), w_c(\zeta), \sigma_a(\zeta), \sigma_b(\zeta), z(\omega \zeta)$ respectively
- prover compute linearized polynomial $L_1(X)$, and its quotient polynomial $q_1(X)$
<br />
$$
\begin{aligned}
L_1(X) &= \underbrace{\color{red}{q_L(X)} * \color{green}{y_{w_a}} + \color{red}{q_R(X)} * \color{green}{y_{w_b}} + \color{red}{q_M(X)} * \color{green}{y_{w_a}} * \color{green}{y_{w_b}} - \color{red}{q_O(X)} * \color{green}{y_{w_c}}}_{\text{gate part}} \\
\\
+& \underbrace{\alpha * [\color{red}{z(X)} * (\color{green}{y_{w_a}} + \beta * k_a * \color{green}{\zeta} + \gamma) * (\color{green}{y_{w_b}} + \beta * k_b * \color{green}{\zeta} + \gamma) * (\color{green}{y_{w_c}} + \beta * k_c * \color{green}{\zeta} + \gamma) -\color{green}{y_{z_\omega}} * (\color{green}{y_{w_a}} + \beta * \color{green}{y_{\sigma_a} + \gamma)} * (\color{green}{y_{w_b}} + \beta * \color{green}{y_{\sigma_b}} + \gamma) * (\color{green}{y_{w_c}} + \beta * \color{red}{\sigma_c(X)} + \gamma)] + \alpha^2 * \color{green}{L_0(\zeta)} * (\color{red}{z(X)} - 1))}_{\text{wiring permutation part}} \\
\\
-& \underbrace{\color{green}{z_H(\zeta)} * [\color{red}{t_0(X)} + \color{green}{\zeta^n} * \color{red}{t_1(X)} + \color{green}{\zeta^{2n}} * \color{red}{t_2(X)}]}_{\text{quotient part}} \\
\\
+& \nu * (\color{red}{w_a(X)} - \color{green}{y_{w_a}}) + \nu^2 * (\color{red}{w_b(X)} - \color{green}{y_{w_b}}) + \nu^3 * (\color{red}{w_c(X)} - \color{green}{y_{w_c}}) \\
\\
+& \nu^4 * (\color{red}{\sigma_a(X)} - \color{green}{y_{\sigma_a}}) + \nu^5 * (\color{red}{\sigma_b(X)} - \color{green}{y_{\sigma_b}}) \\
\\
q_1(X) &= L_1(X) * (X - \zeta)^{-1} \\
\end{aligned}
$$
- prover compute **shifted** linearized polynomial $L_2(X)$, and its quotient polynomial $q_2(X)$
$$
\begin{aligned}
L_2(X) &= \color{red}{z(X)} - \color{green}{y_{z_\omega}} \\
\\
q_2(X) &= L_2(X) * (X - \omega \zeta)^{-1} \\
\end{aligned}
$$
- mask and commit for quotient polynomials or opening proofs $\color{red}{\widetilde{q_1(X)}},\color{red}{\widetilde{q_2(X)}}$ or $[q_1]_g, [q_2]_g$
<br />
#### Check
- verifier compute linearized polynomial commitment $\widetilde{L_1(X)}, \widetilde{L_2(X)}$ or $[L_1]_g, [L_2]_g$, having been provided individual commitments $\widetilde{w_a(X)}, \widetilde{w_b(X)}, \widetilde{w_c(X)}, \widetilde{q_L(X)}, \widetilde{q_R(X)}, \widetilde{q_M(X)}, \widetilde{q_O(X)}, \widetilde{\sigma_a(X)}, \widetilde{\sigma_b(X)}, \widetilde{\sigma_c(X)}, \widetilde{z(X)}, \widetilde{t_1(X)}, \widetilde{t_2(X)}, \widetilde{t_3(X)}$ and opening evaluations $y_{w_a}, y_{w_b}, y_{w_c}, y_{\sigma_a}, y_{\sigma_b}, y_{z_\omega}$
- verifier do the **paring check**
$$
\begin{aligned}
e([L_1]_g + \zeta [q_1]_g, [1]_h) \overset{?}= e([q_1]_g, [\tau]_h) \\
\\
e([L_2]_g + \zeta [q_2]_g, [1]_h) \overset{?}= e([q_2]_g, [\tau]_h) \\
\end{aligned}
$$
<br />
# Ultra Plonk
## Problem
## Protocol
#### Polynomials and Commitments
#### Opening Evaluations and Proofs
#### Check
<br />
# Credits
[1] jellyfish from EspressoSystem: https://github.com/EspressoSystems/jellyfish
[2]Polynomial Commitment by Yu Guo@Secbit: https://learn.z2o-k7e.world/plonk-intro-cn/plonk-polycom.html
[3] Polynomial Encoding by Yu Guo@Secbit: https://learn.z2o-k7e.world/plonk-intro-cn/plonk-lagrange-basis.html