Note - Plonk / TurboPlonk / UltraPlonk

Plonk

$$\mathcal{R}\mathsf{snark}(\lambda )=\left\{\begin{array}{l}\\ (x,w,crs)=\left(\begin{array}{c}(w_i{)}_{i\in [\ell ]},\\ (w_i{)}_{i=1,i\notin [\ell ]}^{3n},\\ (q_{M_i},q_{L_i},q_{R_i},q_{O_i},q_{C_i}{)}_{i=1}^n,n,\sigma (x)\end{array}\right)\\ \\ \begin{array}{rl}\text{For all}i\in \{1,\dots ,3n\}& :w_i\in {\mathbb{F}}_p,\text{and}\\ \text{for all}i\in \{1,\dots ,3n\}& :w_i=w_{\sigma (i)},\text{and}\\ \text{for all}i\in \{1,\dots ,n\}& :w_i{w}_{n+i}{q}_{M_i}+w_i{q}_{L_i}+w_{n+i}{q}_{R_i}+w_{2n+i}{q}_{O_i}+q_{C_i}=0\end{array}\end{array}\right\}$$

Setup

TODO

Prove

1. Compute wire polynomials

   $\mathsf{a}(X)$,
   $\mathsf{b}(X)$,
   $\mathsf{c}(X)$ with randomnesses
   $b_{1-6}$
   $$\begin{array}{rl}& \mathsf{a}(X)=(b_{1}X+b_2){\mathsf{Z}}_{\mathsf{H}}(X)+\sum _{i=1}^n{w}_i{\mathsf{L}}_{\mathsf{i}}(X)\\ & \mathsf{b}(X)=(b_{3}X+b_4){\mathsf{Z}}_{\mathsf{H}}(X)+\sum _{i=1}^n{w}_{n+i}{\mathsf{L}}_{\mathsf{i}}(X)\\ & \mathsf{c}(X)=(b_{5}X+b_6){\mathsf{Z}}_{\mathsf{H}}(X)+\sum _{i=1}^n{w}_{2n+i}{\mathsf{L}}_{\mathsf{i}}(X)\end{array}$$

   Output

   $[a{]}_1=[\mathsf{a}(x){]}_1$,
   $[b{]}_1=[\mathsf{b}(x){]}_1$,
   $[c{]}_1=[\mathsf{c}(x){]}_1$

2. Compute permutation polynomial

   $\mathsf{z}(X)$ with randomnesses
   $b_{7-9}$ and challenge
   $(\beta ,\gamma )$
   $$\begin{array}{rl}\mathsf{z}(X)& =(b_7{X}^2+b_{8}X+b9)Z_H(X)+{\mathsf{L}}_{\mathsf{1}}(X)\\ & +\sum _{i=1}^{n-1}({\mathsf{L}}_{\mathsf{i}\mathsf{+}\mathsf{1}}(X)\prod _{j=1}^i\frac{w_j+\beta {\omega }^{j-1}+\gamma }{w_j+\sigma (j)\beta +\gamma }\frac{w_{n+j}+\beta k_1{\omega }^{j-1}+\gamma }{w_{n+j}+\sigma (n+j)\beta +\gamma }\frac{w_{2n+j}+\beta k_2{\omega }^{j-1}+\gamma }{w_{2n+j}+\sigma (2n+j)\beta +\gamma })\end{array}$$

   Output

   $[z{]}_1=[\mathsf{z}(x){]}_1$

3. Compute quotient polynomial

   $\mathsf{t}(X)$ with challenge
   $\alpha$
   $$\begin{array}{rl}\mathsf{t}(X)& =(\mathsf{a}(X)\mathsf{b}(X){\mathsf{q}}_{\mathsf{M}}(X)+\mathsf{a}(X){\mathsf{q}}_{\mathsf{L}}(X)+\mathsf{b}(X){\mathsf{q}}_{\mathsf{R}}(X)+\mathsf{c}(X){\mathsf{q}}_{\mathsf{O}}(X)+\mathsf{PI}(X)+{\mathsf{q}}_{\mathsf{C}}(X))\frac{1}{{\mathsf{Z}}_{\mathsf{H}}(X)}\\ & +((\mathsf{a}(X)+\beta X+\gamma )(\mathsf{b}(X)+\beta k_{1}X+\gamma )(\mathsf{c}+\beta k_{2}X+\gamma )\mathsf{z}(X))\frac{\alpha }{{\mathsf{Z}}_{\mathsf{H}}(X)}\\ & -((\mathsf{a}(X)+\beta {\mathsf{S}}_{{\sigma }_{\mathsf{1}}}(X)+\gamma )(\mathsf{b}(X)+\beta {\mathsf{S}}_{{\sigma }_{\mathsf{2}}}(X)+\gamma )(\mathsf{c}+\beta {\mathsf{S}}_{{\sigma }_{\mathsf{3}}}(X)+\gamma )\mathsf{z}(X\omega ))\frac{\alpha }{{\mathsf{Z}}_{\mathsf{H}}(X)}\\ & +(\mathsf{z}(X)-1){\mathsf{L}}_{\mathsf{1}}(X)\frac{{\alpha }^2}{{\mathsf{Z}}_{\mathsf{H}}(X)}\end{array}$$

   Output

   $[t_{lo}{]}_1=[{\mathsf{t}}_{\mathsf{lo}}(x){]}_1$,
   $[t_{mid}{]}_1=[{\mathsf{t}}_{\mathsf{mid}}(x){]}_1$,
   $[t_{hi}{]}_1=[{\mathsf{t}}_{\mathsf{hi}}(x){]}_1$

4. Compute linearisation polynomial

   $\mathsf{r}(X)$ with challenge
   $\mathfrak{z}$
   $$\begin{array}{l}\overline{a}=\mathsf{a}(\mathfrak{z})\\ \overline{b}=\mathsf{b}(\mathfrak{z})\\ \overline{c}=\mathsf{c}(\mathfrak{z})\end{array}\begin{array}{l}{\overline{s}}_{{\sigma }_1}={\mathsf{S}}_{{\sigma }_{\mathsf{1}}}(\mathfrak{z})\\ {\overline{s}}_{{\sigma }_2}={\mathsf{S}}_{{\sigma }_{\mathsf{2}}}(\mathfrak{z})\\ \end{array}\begin{array}{l}\overline{t}=\mathsf{t}(\mathfrak{z})\\ {\overline{z}}_{\omega }=\mathsf{z}(\mathfrak{z}\omega )\\ \end{array}$$
   
   $$\begin{array}{rl}\mathsf{r}(X)& =(\overline{a}\overline{b}\cdot {\mathsf{q}}_{\mathsf{M}}(X)+\overline{a}\cdot {\mathsf{q}}_{\mathsf{L}}(X)+\overline{b}\cdot {\mathsf{q}}_{\mathsf{R}}(X)+\overline{c}\cdot {\mathsf{q}}_{\mathsf{O}}(X)+{\mathsf{q}}_{\mathsf{C}}(X))\\ & +((\overline{a}+\beta \mathfrak{z}+\gamma )(\overline{b}+\beta k_1\mathfrak{z}+\gamma )(\overline{c}+\beta k_2\mathfrak{z}+\gamma )\cdot \mathsf{z}(X))\alpha \\ & -((\overline{a}+\beta {\overline{s}}_{{\sigma }_1}+\gamma )(\overline{a}+\beta {\overline{s}}_{{\sigma }_2}+\gamma )\beta {\overline{z}}_{\omega }\cdot {\mathsf{S}}_{{\sigma }_{\mathsf{3}}}(X))\alpha \\ & +\mathsf{z}(X){\mathsf{L}}_{\mathsf{1}}(\mathfrak{z}){\alpha }^2\end{array}$$

   Output

   $\overline{a}$,
   $\overline{b}$,
   $\overline{c}$,
   ${\overline{s}}_{{\sigma }_1}$,
   ${\overline{s}}_{{\sigma }_2}$,
   $\overline{t}$,
   ${\overline{z}}_{\omega }$,
   $\overline{r}=\mathsf{r}(\mathfrak{z})$

5. Compute opening proof polynomial

   ${\mathsf{W}}_{\mathfrak{z}}(X)$ with challenge
   $v$
   $$\begin{array}{rl}& {\mathsf{W}}_{\mathfrak{z}}(X)=\frac{1}{X-\mathfrak{z}}\left(\begin{array}{c}({\mathsf{t}}_{\mathsf{lo}}(X)+{\mathfrak{z}}^n{\mathsf{t}}_{\mathsf{mid}}(X)+{\mathfrak{z}}^{2n}{\mathsf{t}}_{\mathsf{hi}}(X)-\overline{t})\\ +v(\mathsf{r}(X)-\overline{r})\\ +v^2(\mathsf{a}(X)-\overline{a})\\ +v^3(\mathsf{b}(X)-\overline{b})\\ +v^4(\mathsf{c}(X)-\overline{c})\\ +v^5({\mathsf{S}}_{{\sigma }_1}(X)-{\overline{s}}_{{\sigma }_1})\\ +v^6({\mathsf{S}}_{{\sigma }_2}(X)-{\overline{s}}_{{\sigma }_2})\end{array}\right)\\ \\ & {\mathsf{W}}_{\mathfrak{z}\omega }(X)=\frac{\mathsf{z}(X)-{\overline{z}}_{\omega }}{X-\mathfrak{z}\omega }\end{array}$$

   Output

   $[W_{\mathfrak{z}}{]}_1=[{\mathsf{W}}_{\mathfrak{z}}(x){]}_1$,
   $[W_{\mathfrak{z}\omega }{]}_1=[{\mathsf{W}}_{\mathfrak{z}\omega }(x){]}_1$

   When we want to access adjacent gate, for example

   $\mathsf{a}(X\omega )$, we only need to add extra evaluations and aggregate them in commit

   $[{\mathsf{W}}_{\mathfrak{z}\omega }{]}_1$.
   For Dusk Network's implementation as example, they access next gate's

   $w_l$,

   $w_r$,

   $w_4$, so they have to aggregate them into

   $[{\mathsf{W}}_{\mathfrak{z}\omega }{]}_1$.

6. Submit proof

   $$\begin{array}{r}{\pi }_{SNARK}=\left(\begin{array}{c}[a{]}_1,[b{]}_1,[c{]}_1,[z{]}_1,[t_{lo}{]}_1,[t_{mid}{]}_1,[t_{hi}{]}_1,[W_{\mathfrak{z}}{]}_1,[W_{\mathfrak{z}\omega }{]}_1,\\ \overline{a},\overline{b},\overline{c},{\overline{s}}_{{\sigma }_1},{\overline{s}}_{{\sigma }_2},\overline{r},{\overline{z}}_{\omega }\end{array}\right)\end{array}$$

Verify

TODO

Question

• Why is

  ${\mathsf{L}}_{\mathsf{1}}(\mathfrak{z})=\frac{{\mathfrak{z}}^n-1}{n(\mathfrak{z}-1)}$ (Why is
  ${\mathsf{L}}_{\mathsf{1}}(X)=\frac{X^n-1}{n(X-1)}$)

  liangcc
  

  $$\begin{array}{rl}& X^n-1=(X-1)(X-\omega )(X-{\omega }^2)\dots (X-{\omega }^{n-1})\\ & X^n-1=(X-1)(X^{n-1}+X^{n-2}+\cdots +1)\\ & \frac{X^n-1}{X-1}=(X^{n-1}+X^{n-2}+\cdots +1)=(X-\omega )(X-{\omega }^2)\dots (X-{\omega }^{n-1})\end{array}$$
  

  $$\begin{array}{rl}{\mathsf{L}}_{\mathsf{1}}(X)& =\frac{(X-\omega )(X-{\omega }^2)\dots (X-{\omega }^{n-1})}{(1-\omega )(1-{\omega }^2)\dots (1-{\omega }^{n-1})}\\ \\ & =\frac{\frac{X^n-1}{X-1}}{(1-\omega )(1-{\omega }^2)\dots (1-{\omega }^{n-1})}\\ \\ & =\frac{\frac{X^n-1}{X-1}}{1^{n-1}+1^{n-2}+\cdots +1}\\ \\ & =\frac{X^n-1}{n(X-1)}\end{array}$$

• Why we use

  $2$ randomnesses in
  $\mathsf{a}(X)$,
  $\mathsf{b}(X)$ and
  $\mathsf{c}(X)$ but
  $3$ in
  $\mathsf{z}(X)$?

  Cited Ariel Gabizon from <a href="https://www.plonk.cafe/t/noob-questions-plonk-paper/73">plonk.cafe #73</a> The rule is that if the poly is opened at

  $d$ points you need

  $d+1$ blinding factors; to hide both the commitment (which is an evaluation at a secret point in the exponent, but still to prove zk holds you’ll need this to be totally random, this proof that zk holds is quite similar to existing proofs - e.g. in Marlin, but is a missing hole in the paper right now) and the

  $d$ evaluation points.
  So

  $\mathsf{z}(X)$ is opened at

  $2$ points and hence needs

  $3$ blinding factors.

• Why bother including

  ${\overline{s}}_{{\sigma }_1}$ and
  ${\overline{s}}_{{\sigma }_2}$ in proof and check them in pairing if verifier can calculate himself.

  han Guessing it's the reason that verification complexity is polylogarithmic

  $\mathcal{O}((\log n{)}^k)$, because evaluation is linear time.

• Why

  $\mathsf{r}(X)$ is lack of
  $((\overline{a}+\beta {\overline{s}}_{{\sigma }_1}+\gamma )(\overline{b}+\beta {\overline{s}}_{{\sigma }_2}+\gamma )(\overline{c}+\gamma ){\overline{z}}_{\omega })\alpha$ and
  ${\mathsf{L}}_{\mathsf{1}}(\mathfrak{z}){\alpha }^2$

  han Guessing it's because we need to ensure prover is using the

  $\alpha$,

  ${\mathsf{S}}_{{\sigma }_1}(X)$ and

  ${\mathsf{S}}_{{\sigma }_2}(X)$ as we expected, so we let verifier compute these part.

• How to constraint prover to use right

  ${\mathsf{S}}_{{\sigma }_1}(X)$ and
  ${\mathsf{S}}_{{\sigma }_2}(X)$ in
  $\mathsf{t}(X)$ and
  $\mathsf{r}(X)$ as verifier expected

  han Guessing it's constrainted by the lack part of

  $\mathsf{r}(X)$. If prover uses different

  ${\mathsf{S}}_{{\sigma }_1}(X)$ and

  ${\mathsf{S}}_{{\sigma }_2}(X)$, then reconstructed

  $\overline{t}$ by verifier will not equal to prover's

  $\overline{t}$.

TurboPlonk

Take Dusk Network implementation as an example

Relation in paper's notations

$$\mathcal{R}\mathsf{snark}(\lambda )=\left\{\begin{array}{l}\\ \\ \\ \\ \\ \\ \\ \\ (x,w,crs)=\left(\begin{array}{c}(w_i{)}_{i\in [\ell ]},\\ (w_i{)}_{i=1,i\notin [\ell ]}^{4n},\\ {\left(\begin{array}{c}{q}_{M_i},q_{L_i},q_{R_i},q_{O_i},q_{C_i},q_{4_i},\\ q_{Arit{h}_i},q_{Rang{e}_i},q_{Logi{c}_i},q_{FixedGroupAd{d}_i},q_{VariableGroupAd{d}_i}\end{array}\right)}_{i=1}^n,n,\sigma (x)\end{array}\right)\\ \\ \begin{array}{rl}\text{For all}i\in \{1,\dots ,4n\}& :w_i\in {\mathbb{F}}_p,\text{and}\\ \text{for all}i\in \{1,\dots ,4n\}& :w_i=w_{\sigma (i)},\text{and}\\ \text{for all}i\in \{1,\dots ,n\}& :q_{Arit{h}_i}=0\vee (w_i{w}_{n+i}{q}_{M_i}+w_i{q}_{L_i}+w_{n+i}{q}_{R_i}+w_{2n+i}{q}_{O_i}+w_{3n+i}{q}_{4_i}+q_{C_i})=0,\text{and}\\ \\ \text{for all}i\in \{1,\dots ,n-1\}& :q_{Rang{e}_i}=0\vee \left(\begin{array}{r}(w_{2n+i}-4w_{3n+i})\in \{0,1,2,3\}\wedge \\ (w_{n+i}-4w_{2n+i})\in \{0,1,2,3\}\wedge \\ (w_i-4w_{n+i})\in \{0,1,2,3\}\wedge \\ (w_{3n+i+1}-4w_i)\in \{0,1,2,3\}\end{array}\right),\text{and}\\ \\ \text{for all}i\in \{1,\dots ,n-1\}& :q_{Logi{c}_i}=0\vee \left(\begin{array}{r}(w_{i+1}-4w_i)\in \{0,1,2,3\}\wedge \\ (w_{n+i+1}-4w_{n+i})\in \{0,1,2,3\}\wedge \\ (w_{3n+i+1}-4w_{3n+i})\in \{0,1,2,3\}\wedge \\ (w_{2n+i}-w_i{w}_{n+i})=0\wedge \\ \left(\begin{array}{c}{q}_{C_i}[9w_{3n+i}-3(w_i+w_{n+i})]+\\ 3(w_i+w_{n+i}+w_{3n+i})-\\ 2w_{2n+i}\left(\begin{array}{c}{w}_{2n+i}(4w_{2n+i}-18(w_i+w_{n+i})+81)+\\ 18(w_i^2+w_{n+i}^2)-81(w_i+w_{n+i})+83\end{array}\right)\end{array}\right)=0\end{array}\right),\text{and}\\ \\ \text{for all}i\in \{1,\dots ,n-1\}& :q_{FixedGroupAd{d}_i}=0\vee \left(\begin{array}{r}(w_{3n+i+1}-2w_{3n+i})\in \{-1,0,1\}\wedge \\ (q_{C_i}(w_{3n+i+1}-2w_{3n+i})-w_{2n+i})=0\wedge \\ \left(\begin{array}{c}{w}_{i+1}(1+\mathcal{D}{w}_i{w}_{n+i}{w}_{2n+i})-\\ w_{n+i}(w_{3n+i+1}-2w_{3n+i})q_{L_i}-\\ w_i((w_{3n+i+1}-2w_{3n+i}{)}^2(q_{R_i}-1)+1)\end{array}\right)=0\wedge \\ \left(\begin{array}{c}{w}_{n+i+1}(1-\mathcal{D}{w}_i{w}_{n+i}{w}_{2n+i})-\\ w_i(w_{3n+i+1}-2w_{3n+i})q_{L_i}-\\ w_{n+i}((w_{3n+i+1}-2w_{3n+i}{)}^2(q_{R_i}-1)+1)\end{array}\right)=0\end{array}\right),\text{and}\\ \\ \text{for all}i\in \{1,\dots ,n-1\}& :q_{VariableGroupAd{d}_i}=0\vee \left(\begin{array}{r}(w_{3n+i+1}-w_i{w}_{3n+i})=0\wedge \\ \left(\begin{array}{c}{w}_i{w}_{3n+i}+w_{n+i}{w}_{2n+i}-\\ w_{i+1}(1+\mathcal{D}{w}_i{w}_{n+i}{w}_{2n+i}{w}_{3n+i})\end{array}\right)=0\wedge \\ \left(\begin{array}{c}{w}_i{w}_{2n+i}+w_{n+i}{w}_{3n+i}-\\ w_{n+i+1}(1-\mathcal{D}{w}_i{w}_{n+i}{w}_{2n+i}{w}_{3n+i})\end{array}\right)=0\end{array}\right)\end{array}\end{array}\right\}$$

Relation in more readable notations

$$\mathcal{R}\mathsf{snark}(\lambda )=\left\{\begin{array}{l}\\ \\ \\ \\ \\ \\ \\ \\ (x,w,crs)=\left(\begin{array}{c}(w_i{)}_{i\in [\ell ]},\\ (w_i{)}_{i=1,i\notin [\ell ]}^{4n}=(a_i{)}_{i=1,i\notin [\ell ]}^n||(b_i{)}_{i=1,i\notin [\ell ]}^n||(c_i{)}_{i=1,i\notin [\ell ]}^n||(d_i{)}_{i=1,i\notin [\ell ]}^n,\\ {\left(\begin{array}{c}{q}_{M_i},q_{L_i},q_{R_i},q_{O_i},q_{C_i},q_{4_i},\\ q_{Arit{h}_i},q_{Rang{e}_i},q_{Logi{c}_i},q_{FixedGroupAd{d}_i},q_{VariableGroupAd{d}_i}\end{array}\right)}_{i=1}^n,n,\sigma (x)\end{array}\right)\\ \\ \begin{array}{rl}\text{For all}i\in \{1,\dots ,4n\}& :w_i\in {\mathbb{F}}_p,\text{and}\\ \text{for all}i\in \{1,\dots ,4n\}& :w_i=w_{\sigma (i)},\text{and}\\ \text{for all}i\in \{1,\dots ,n\}& :q_{Arit{h}_i}=0\vee (a_i{b}_i{q}_{M_i}+a_i{q}_{L_i}+b_i{q}_{R_i}+c_i{q}_{O_i}+d_i{q}_{4_i}+q_{C_i})=0,\text{and}\\ \\ \text{for all}i\in \{1,\dots ,n-1\}& :q_{Rang{e}_i}=0\vee \left(\begin{array}{r}(c_i-4d_i)\in \{0,1,2,3\}\wedge \\ (b_i-4c_i)\in \{0,1,2,3\}\wedge \\ (a_i-4b_i)\in \{0,1,2,3\}\wedge \\ (d_{i+1}-4a_i)\in \{0,1,2,3\}\end{array}\right),\text{and}\\ \\ \text{for all}i\in \{1,\dots ,n-1\}& :q_{Logi{c}_i}=0\vee \left(\begin{array}{r}(a_{i+1}-4a_i)\in \{0,1,2,3\}\wedge \\ (b_{i+1}-4b_i)\in \{0,1,2,3\}\wedge \\ (d_{i+1}-4d_i)\in \{0,1,2,3\}\wedge \\ (c_i-a_i{b}_i)=0\wedge \\ \left(\begin{array}{c}{q}_{C_i}[9d_i-3(a_i+b_i)]+\\ 3(a_i+b_i+d_i)-\\ 2c_i\left(\begin{array}{c}{c}_i(4c_i-18(a_i+b_i)+81)+\\ 18(a_i^2+b_i^2)-81(a_i+b_i)+83\end{array}\right)\end{array}\right)=0\end{array}\right),\text{and}\\ \\ \text{for all}i\in \{1,\dots ,n-1\}& :q_{FixedGroupAd{d}_i}=0\vee \left(\begin{array}{r}(d_{i+1}-2d_i)\in \{-1,0,1\}\wedge \\ (q_{C_i}(d_{i+1}-2d_i)-c_i)=0\wedge \\ \left(\begin{array}{c}{a}_{i+1}(1+\mathcal{D}{a}_i{b}_i{c}_i)-\\ b_i(d_{i+1}-2d_i)q_{L_i}-\\ a_i((d_{i+1}-2d_i{)}^2(q_{R_i}-1)+1)\end{array}\right)=0\wedge \\ \left(\begin{array}{c}{b}_{i+1}(1-\mathcal{D}{a}_i{b}_i{c}_i)-\\ a_i(d_{i+1}-2d_i)q_{L_i}-\\ b_i((d_{i+1}-2d_i{)}^2(q_{R_i}-1)+1)\end{array}\right)=0\end{array}\right),\text{and}\\ \\ \text{for all}i\in \{1,\dots ,n-1\}& :q_{VariableGroupAd{d}_i}=0\vee \left(\begin{array}{r}(d_{i+1}-a_i{d}_i)=0\wedge \\ \left(\begin{array}{c}{a}_i{d}_i+b_i{c}_i-\\ a_{i+1}(1+\mathcal{D}{a}_i{b}_i{c}_i{d}_i)\end{array}\right)=0\wedge \\ \left(\begin{array}{c}{a}_i{c}_i+b_i{d}_i-\\ b_{i+1}(1-\mathcal{D}{a}_i{b}_i{c}_i{d}_i)\end{array}\right)=0\end{array}\right)\end{array}\end{array}\right\}$$

They split wire value into base-4, which makes

$x=\sum _{i=0}^n{q}_i{4}^i$, in range widget and logic widget to reduce gate number. For the reason that using base-4 is to make use of the max available degree of the permutation grand product in

$\mathsf{t}(X)$, which

$4n$ (4 wires).

Setup

TODO

Prove

TODO

Verify

TODO

Question

• How does logic widget work? (It checks AND and XOR at the same time)
• Why adding dummy gates like this can serve as blind factor? How could it be used to prove Zero-Knowledge property of
  $\mathcal{P}\mathfrak{lon}\mathcal{K}$ ?
  Compared to barretenberg's implementation, they use randomness wire values and cut the
  ${\mathsf{Z}}_{\mathsf{H}}(X)$'s last
  $k$ roots to achieve Zero-Knowledge and not make
  ${\mathsf{Z}}_{\mathsf{H}}(X)$'s degree over
  $4n$ at the same time. See Adding zero-knowledge into PLONK by @zacwilliamson for more details.

UltraPlonk

TODO

Reference

• Plonk
  • PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge
  • Understanding PLONK by Vitalik
  • Simplified Plonk Tutorial by BarryWhiteHat
  • Plonk By Hand Series by METASTATE TEAM
    • Part1
    • Part2 - Proof
    • Part3 - Verification
  • Adding zero knowledge to Plonk-Halo by Mir Protocol
  • ZK Study Club - Plonk with Zac Williamson
• TurboPlonk
  • Proposal: The Turbo-PLONK program syntax for specifying SNARK programs
  • PLONK custom gates design considerations
  • Into the deep end: making sense of PLONK - Zac Williamson (CTO, Aztec Protocol)
  • Adding zero-knowledge into PLONK
• Plookup
  • plookup: A simplified polynomial protocol for lookup tables
  • Prover and Verifier algorithms with Plookup
  • On PLONK and plookup
  • Multiset checks in PLONK and Plookup
  • zkSummit: plookup: Speeding up the PLONK prover - Zac Williamson & Ariel Gabizon
  • Range Polynomial Protocols
• Implementation
  • github.com/AZTECProtocol/barretenberg
  • github.com/dusk-network/plonk
  • github.com/zcash/halo2