---
tags: note
---

# Note - Plonk / TurboPlonk / UltraPlonk

## Plonk

$$
\mathcal{R}\mathsf{snark}(\lambda) =
\left\{
\begin{array}{l}
\\
(x, w, crs) =
\left(
\begin{array}{l}
(w_i)_{i \in [\ell]}, \\
(w_i)_{i = 1, i \not\in [\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{align}
\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_iw_{n+i}q_{M_i} + w_iq_{L_i} + w_{n+i}q_{R_i} + w_{2n+i}q_{O_i} + q_{C_i} = 0 \\
\end{align}
\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{align}
& \mathsf{a}(X) = (b_1X + b_2)\mathsf{Z_H}(X) + \sum_{i=1}^nw_i\mathsf{L_i}(X) \\
& \mathsf{b}(X) = (b_3X + b_4)\mathsf{Z_H}(X) + \sum_{i=1}^nw_{n+i}\mathsf{L_i}(X) \\
& \mathsf{c}(X) = (b_5X + b_6)\mathsf{Z_H}(X) + \sum_{i=1}^nw_{2n+i}\mathsf{L_i}(X) \\
\end{align}
$$

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{align}
\mathsf{z}(X) & = (b_7X^2 + b_8X + b9)Z_H(X) + \mathsf{L_1}(X) \\
& \quad + \sum_{i=1}^{n-1}\big(\mathsf{L_{i+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} \big)
\end{align}
$$

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

3. Compute quotient polynomial $\mathsf{t}(X)$ with challenge $\alpha$

$$
\begin{align}
\mathsf{t}(X) & = (\mathsf{a}(X)\mathsf{b}(X)\mathsf{q_M}(X) + \mathsf{a}(X)\mathsf{q_L}(X) + \mathsf{b}(X)\mathsf{q_R}(X) + \mathsf{c}(X)\mathsf{q_O}(X) + \mathsf{PI}(X) + \mathsf{q_C}(X))\frac{1}{\mathsf{Z_H}(X)} \\
& \quad + ((\mathsf{a}(X) + \beta X + \gamma)(\mathsf{b}(X) + \beta k_1X + \gamma)(\mathsf{c} + \beta k_2X + \gamma)\mathsf{z}(X))\frac{\alpha}{\mathsf{Z_H}(X)} \\
& \quad - ((\mathsf{a}(X) + \beta \mathsf{S_{\sigma_1}}(X) + \gamma)(\mathsf{b}(X) + \beta \mathsf{S_{\sigma_2}}(X) + \gamma)(\mathsf{c} + \beta \mathsf{S_{\sigma_3}}(X) + \gamma)\mathsf{z}(X\omega))\frac{\alpha}{\mathsf{Z_H}(X)} \\
& \quad + (\mathsf{z}(X) - 1)\mathsf{L_1}(X)\frac{\alpha^2}{\mathsf{Z_H}(X)} \\
\end{align}
$$

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

4. Compute linearisation polynomial $\mathsf{r}(X)$ with challenge $\mathfrak{z}$

$$
\begin{array}{l}
\bar{a} = \mathsf{a}(\mathfrak{z}) \\
\bar{b} = \mathsf{b}(\mathfrak{z}) \\
\bar{c} = \mathsf{c}(\mathfrak{z}) \\
\end{array}
\quad
\begin{array}{l}
\bar{s}_{\sigma_1} = \mathsf{S_{\sigma_1}}(\mathfrak{z}) \\
\bar{s}_{\sigma_2} = \mathsf{S_{\sigma_2}}(\mathfrak{z}) \\\\
\end{array}
\quad
\begin{array}{l}
\bar{t} = \mathsf{t}(\mathfrak{z}) \\
\bar{z}_{\omega} = \mathsf{z}(\mathfrak{z}\omega) \\\\
\end{array}
$$
$$
\begin{align}
\mathsf{r}(X) & = (\bar{a}\bar{b}\cdot \mathsf{q_M}(X) + \bar{a}\cdot \mathsf{q_L}(X) + \bar{b}\cdot \mathsf{q_R}(X) + \bar{c} \cdot \mathsf{q_O}(X) + \mathsf{q_C}(X)) \\
& \quad + ((\bar{a} + \beta\mathfrak{z} + \gamma)(\bar{b} + \beta k_1\mathfrak{z} + \gamma)(\bar{c} + \beta k_2\mathfrak{z} + \gamma)\cdot \mathsf{z}(X))\alpha \\
& \quad - ((\bar{a} + \beta\bar{s}_{\sigma_1} + \gamma)(\bar{a} + \beta\bar{s}_{\sigma_2} + \gamma)\beta\bar{z}_\omega\cdot \mathsf{S_{\sigma_3}}(X))\alpha \\
& \quad + \mathsf{z}(X)\mathsf{L_1}(\mathfrak{z})\alpha^2 \\
\end{align}
$$

Output $\bar{a}$, $\bar{b}$, $\bar{c}$, $\bar{s}_{\sigma_1}$, $\bar{s}_{\sigma_2}$, $\bar{t}$, $\bar{z}_{\omega}$, $\bar{r} = \mathsf{r}(\mathfrak{z})$

5. Compute opening proof polynomial $\mathsf{W}_{\mathfrak{z}}(X)$ with challenge $v$

$$
\begin{align}
& \mathsf{W}_{\mathfrak{z}}(X) = \frac{1}{X-\mathfrak{z}}
\left(
\begin{array}{l}
(\mathsf{t_{lo}}(X) + \mathfrak{z}^n\mathsf{t_{mid}}(X) + \mathfrak{z}^{2n}\mathsf{t_{hi}}(X) - \bar{t}) \\
+ v(\mathsf{r}(X) - \bar{r}) \\
+ v^2(\mathsf{a}(X) - \bar{a}) \\
+ v^3(\mathsf{b}(X) - \bar{b}) \\
+ v^4(\mathsf{c}(X) - \bar{c}) \\
+ v^5(\mathsf{S}_{\sigma_1}(X) - \bar{s}_{\sigma_1}) \\
+ v^6(\mathsf{S}_{\sigma_2}(X) - \bar{s}_{\sigma_2}) \\
\end{array}
\right) \\\\
& \mathsf{W}_{\mathfrak{z}\omega}(X) = \frac{\mathsf{z}(X) - \bar{z}_\omega}{X - \mathfrak{z}\omega}
\end{align}
$$

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

:::info
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](https://github.com/dusk-network/plonk/blob/master/src/proof_system/prover.rs#L369-L373) 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{align}
\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, \\
\bar{a}, \bar{b}, \bar{c}, \bar{s}_{\sigma_1}, \bar{s}_{\sigma_2}, \bar{r}, \bar{z}_\omega
\end{array}
\right)
\end{align}
$$

### Verify

==TODO==

### Question

- [x] Why is $\mathsf{L_1}(\mathfrak{z}) = \frac{\mathfrak{z}^n-1}{n(\mathfrak{z}-1)}$ (Why is $\mathsf{L_1}(X) = \frac{X^n-1}{n(X-1)}$)

> [name=liangcc]
$$
\begin{align}
& 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} + \dots + 1) \\
& \frac{X^n - 1}{X -1} = (X^{n-1}+ X^{n-2} + \dots + 1) = (X-\omega)(X-\omega^2)\dots(X-\omega^{n-1})
\end{align}
$$
$$
\begin{align}
\mathsf{L_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} + \dots + 1} \\\\
& = \frac{X^n-1}{n(X-1)}
\end{align}
$$

- [x] Why we use $2$ randomnesses in $\mathsf{a}(X)$, $\mathsf{b}(X)$ and $\mathsf{c}(X)$ but $3$ in $\mathsf{z}(X)$?
> [name=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 $\bar{s}_{\sigma_1}$ and $\bar{s}_{\sigma_2}$ in proof and check them in pairing if verifier can calculate himself.
> [name=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 $((\bar{a}+\beta\bar{s}_{\sigma_1}+\gamma)(\bar{b}+\beta\bar{s}_{\sigma_2}+\gamma)(\bar{c}+\gamma)\bar{z}_\omega)\alpha$ and $\mathsf{L_1}(\mathfrak{z})\alpha^2$
> [name=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
> [name=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 $\bar{t}$ by verifier will not equal to prover's $\bar{t}$.

## TurboPlonk

Take [Dusk Network](https://github.com/dusk-network/plonk) implementation as an example

:::spoiler {state="open"} **Relation in paper's notations**

<div style="margin-bottom: -10em; overflow: hidden; display: inline-block;">
<div style="transform: translateY(-12em)">

$$
\mathcal{R}\mathsf{snark}(\lambda) =
\left\{
\begin{array}{l}
\\\\\\\\\\\\\\\\
(x, w, crs) =
\left(
\begin{array}{l}
(w_i)_{i \in [\ell]}, \\
(w_i)_{i = 1, i \not\in [\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_{Arith_i}, q_{Range_i}, q_{Logic_i}, q_{FixedGroupAdd_i}, q_{VariableGroupAdd_i}
\end{array}
\right)_{i=1}^{n}, n, \sigma(x)
\end{array}
\right) \\\\
\begin{align}
\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_{Arith_i} = 0 \vee (w_iw_{n+i}q_{M_i} + w_iq_{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_{Range_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_{Logic_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}{r}
q_{C_i} [9w_{3n+i} - 3(w_{i}+w_{n+i})] + \\
3(w_{i}+w_{n+i}+w_{3n+i}) - \\
2 w_{2n+i}\left(
\begin{array}{r}
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_{FixedGroupAdd_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}{r}
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}{r}
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_{VariableGroupAdd_i} = 0 \vee \left(
\begin{array}{r}
(w_{3n+i+1} - w_{i}w_{3n+i}) = 0 \ \wedge \\
\left(
\begin{array}{r}
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}{r}
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{align}
\end{array}
\right\}
$$

</div>
</div>

:::
:::spoiler {state="open"} **Relation in more readable notations**

<div style="margin-bottom: -10em; overflow: hidden; display: inline-block;">
<div style="transform: translateY(-12em)">

$$
\mathcal{R}\mathsf{snark}(\lambda) =
\left\{
\begin{array}{l}
\\\\\\\\\\\\\\\\
(x, w, crs) =
\left(
\begin{array}{l}
(w_{i})_{i \in [\ell]}, \\
(w_i)_{i = 1, i \not\in [\ell]}^{4n} = (a_i)_{i = 1, i \not\in [\ell]}^{n} || (b_i)_{i = 1, i \not\in [\ell]}^{n} || (c_i)_{i = 1, i \not\in [\ell]}^{n} || (d_i)_{i = 1, i \not\in [\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_{Arith_i}, q_{Range_i}, q_{Logic_i}, q_{FixedGroupAdd_i}, q_{VariableGroupAdd_i}
\end{array}
\right)_{i=1}^{n}, n, \sigma(x)
\end{array}
\right) \\\\
\begin{align}
\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_{Arith_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_{Range_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_{Logic_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}{r}
q_{C_i} [9d_{i} - 3(a_{i}+b_{i})] + \\
3(a_{i}+b_{i}+d_{i}) - \\
2 c_{i}\left(
\begin{array}{r}
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_{FixedGroupAdd_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}{r}
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}{r}
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_{VariableGroupAdd_i} = 0 \vee \left(
\begin{array}{r}
(d_{i+1} - a_{i}d_{i}) = 0 \ \wedge \\
\left(
\begin{array}{r}
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}{r}
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{align}
\end{array}
\right\}
$$

</div>
</div>

:::

<br>

:::info
They split wire value into base-4, which makes $x = \sum_{i=0}^nq_i4^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](https://github.com/dusk-network/plonk/blob/master/src/proof_system/widget/logic/proverkey.rs) work? (It checks `AND` and `XOR` at the same time)
- [ ] Why adding dummy gates like [this](https://github.com/dusk-network/plonk/blob/master/src/constraint_system/composer.rs#L423) 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](https://github.com/AztecProtocol/aztec-2-bug-bounty/blob/master/barretenberg/src/aztec/plonk/proof_system/prover/prover.cpp#L181-L183), they use randomness wire values and cut the $\mathsf{Z_H}(X)$'s last $k$ roots to achieve Zero-Knowledge and not make $\mathsf{Z_H}(X)$'s degree over $4n$ at the same time. See [Adding zero-knowledge into PLONK](https://hackmd.io/@zacwilliamson/r1dm8Rj7D) by [@zacwilliamson](https://hackmd.io/@zacwilliamson) for more details.

## UltraPlonk

==TODO==

## Reference

- Plonk
- [PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge](https://eprint.iacr.org/2019/953.pdf)
- [Understanding PLONK](https://vitalik.ca/general/2019/09/22/plonk.html) by Vitalik
- [Simplified Plonk Tutorial](https://github.com/barryWhiteHat/plonk_tutorial) by BarryWhiteHat
- Plonk By Hand Series by [METASTATE TEAM](https://research.metastate.dev/)
- [Part1](https://research.metastate.dev/plonk-by-hand-part-1)
- [Part2 - Proof](https://research.metastate.dev/plonk-by-hand-part-2-the-proof)
- [Part3 - Verification](https://research.metastate.dev/plonk-by-hand-part-3-verification)
- [Adding zero knowledge to Plonk-Halo](https://mirprotocol.org/blog/Adding-zero-knowledge-to-Plonk-Halo) by Mir Protocol
- [ZK Study Club - Plonk with Zac Williamson](https://www.youtube.com/watch?v=NqrVcDuQ8hM&list=PLj80z0cJm8QHm_9BdZ1BqcGbgE-BEn-3Y&index=22)
- TurboPlonk
- [Proposal: The Turbo-PLONK program syntax for specifying SNARK programs](https://docs.zkproof.org/pages/standards/accepted-workshop3/proposal-turbo_plonk.pdf)
- [PLONK custom gates design considerations](https://hackmd.io/@kobigurk/HJgsycL0H)
- [Into the deep end: making sense of PLONK - Zac Williamson (CTO, Aztec Protocol)](https://www.youtube.com/watch?v=ty-LZf0YCK0&t=1482s)
- [Adding zero-knowledge into PLONK](https://hackmd.io/@zacwilliamson/r1dm8Rj7D)
- Plookup
- [plookup: A simplified polynomial protocol for lookup tables](https://eprint.iacr.org/2020/315.pdf)
- [Prover and Verifier algorithms with Plookup](https://hackmd.io/gMXxXhCXQ8GFb1bvnFgOIA?view)
- [On PLONK and plookup](https://research.metastate.dev/on-plonk-and-plookup/)
- [Multiset checks in PLONK and Plookup](https://hackmd.io/Iuu9P7S5Sca0TCoYJ-sFdA)
- [zkSummit: plookup: Speeding up the PLONK prover - Zac Williamson & Ariel Gabizon](https://www.youtube.com/watch?v=Vdlc1CmRYRY)
- [Range Polynomial Protocols](https://www.youtube.com/watch?v=GVByGIhQq68)
- Implementation
- [github.com/AZTECProtocol/barretenberg](https://github.com/AZTECProtocol/barretenberg)
- [github.com/dusk-network/plonk](https://github.com/dusk-network/plonk)
- [github.com/zcash/halo2](https://github.com/zcash/halo2)