Plonk From Scratch

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**. # Zero Check If you have a committed polynomial $\widetilde{f(X)}$, and send it to verifier. 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 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) $$ ## 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)$ # Vanilla Plonk no lookup, no permutation, no multiplication gate, just **addition gate**! 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! 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 red part vectors are unknown to verifier, so how to get it done? ## 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} $$ 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 red part polynomials is unknown to verifier, they cannot be sent directly. 2. The verification cost is linear with gate number, can we just do ONE check? ## Round Two Regarding to the first problem, in order to hide these polynomials, we can commit the red part polynomials $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} $$ 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} $$ 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} $$ 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 - computing the quotient polynomial $t(X)$ might not be easy, especially when the degree of left part polynomial is pretty high due to **multiplications** 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. But, how does the **PROOFS** look like, and how to verify evaluations with **PROOFS**? ## 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. 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)} $$ 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} $$ 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} $$ ## 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 - computing the quotient polynomial $t(X)$ might not be easy, especially when the degree of left part polynomial is pretty high due to **multiplications** #### 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} $$ #### 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)} $$ # Vanilla Plonk with High-degree Gate no lookup, no permutation, just addition gate and **multiplication gate**! 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. 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} $$ 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} $$ ## 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)}$ #### 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 #### 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 #### 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}$: $$ \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} $$ > 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) $$ # Turbo Plonk ## 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|5|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| We have 2 additive gate, 2 multiplication gate, and 2 wiring shares here. So the extended id matrix, $\omega = 4$: |i|id_a|id_b|id_c| |---|---|---|---| |0|$\omega^0$|$k \omega^0$|$k^2 \omega^0$| |1|$\omega^1$|$k \omega^1$|$k^2 \omega^1$| |2|$\omega^2$|$k \omega^2$|$k^2 \omega^2$| |3|$\omega^3$|$k \omega^3$|$k^2 \omega^3$| The permutated id or $\sigma$ matrix: |i|id_a|id_b|id_c| |---|---|---|---| |0|$\omega^0$|$k \omega^0$|$\omega^1$| |1|$k^2 \omega^0$|$k \omega^1$|$k^2 \omega^1$| |2|$k \omega^3$|$k \omega^2$|$k^2 \omega^2$| |3|$\omega^3$|$\omega^2$|$k^2 \omega^3$| 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} $$ 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} $$ ## 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)}$ #### 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 #### 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)$ $$ \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$ #### 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} $$ # Ultra Plonk ## Problem ## Protocol #### Polynomials and Commitments #### Opening Evaluations and Proofs #### Check # 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

Read more

[Paper Reading and Code] Binius

Code Theory

Circle Stark from A New Starker

BitVM Optimization