# Prover and Verifier algorithms with Plookup
Plookup additions are in $\color{purple}{\text{purple}}$.

We explicitly define a multiplicative subgroup $H$ as $\{1, \omega, \omega^2, \ldots \omega^{n-1}\}$ for some $n$th root of unity $\omega$.

**Common preprocessed input:**
$n, (x\cdot[1]_1,\ldots,x^{n+2}\cdot[1]_1), (q_{Mi}, q_{Li}, q_{Ri}, q_{Oi}, q_{Ci}, \color{purple}{q_{\text{Lookup}_i}})_{i=0}^{n-1}, \sigma(X), \color{purple}{(x_i, y_i, z_i)_{i=0}^{n-1}}$

$q_M(X) = \sum_{i=0}^{n-1}q_{Mi}\textbf{L}_i(X)$,
$q_L(X) = \sum_{i=0}^{n-1}q_{Li}\textbf{L}_i(X)$,
$q_R(X) = \sum_{i=0}^{n-1}q_{Ri}\textbf{L}_i(X)$,
$q_O(X) = \sum_{i=0}^{n-1}q_{Oi}\textbf{L}_i(X)$,
$q_C(X) = \sum_{i=0}^{n-1}q_{Ci}\textbf{L}_i(X)$,
$S_{\sigma 1}(X) = \sum_{i=0}^{n-1}\sigma(i) \textbf{L}_i(X)$,
$S_{\sigma 2}(X) = \sum_{i=0}^{n-1}\sigma(n+i) \textbf{L}_i(X)$,
$S_{\sigma 3}(X) = \sum_{i=0}^{n-1}\sigma(2n+i) \textbf{L}_i(X)$,

$\textbf{L}_i$ is the Lagrange polynomial taking the value $1$ on $\mathbf{\omega}^i$ and the value $0$ on the other elements of $H$.

The added Plookup element $\color{purple}{(x_i, y_i, z_i)_{i=0}^{n-1}}$ is the lookup table: a list of triples representing a function $g$ with $g(x_i, y_i) = z_i$.

**Public input:** $l, (w_i)_{i\in [l]}$

## Prover Algorithm

**Prover input:** wire values $(w_i)_{i\in [3n]}$, lookup queries $\color{purple}{(x_i, y_i, z_i)_{i=0}^{n-2}}$.

### Round 1

Generate random blinding scalars $(b_1,\ldots,b_9)\in \mathbb{F}_p$.
Compute wire polynomials $a(X), b(X)$, and $c(X)$:

$a(X) = (b_1X+b_2)Z_H(X)+\sum_{i=0}^{n-1} w_i\textbf{L}_i(X)$

$b(X) = (b_3X+b_4)Z_H(X)+\sum_{i=0}^{n-1} w_{n+i}\textbf{L}_i(X)$

$c(X) = (b_5X+b_6)Z_H(X)+\sum_{i=0}^{n-1} w_{2n+i}\textbf{L}_i(X)$

Compute $[a]_1$, $[b]_1$, and $[c]_1$ and add to transcript.

Generate table compression factor $\color{purple}{\zeta}$ from the transcript.

Compute compressed table $\color{purple}{\left\{t_i\right\}_{i=0}^n}$ as $\color{purple}{t_i = x_{t_i}+\zeta y_{t_i}+\zeta^2z_{t_i}}$ and sort.

Compute table polynomial $\color{purple}{t(X) = \sum_{i=0}^{n-1}t_i \textbf{L}_i(X)}$.

Compute compressed queries $\color{purple}{\left\{f_i\right\}_{i=0}^n}$ as $\color{purple}{f_i = x_{f_i}+\zeta y_{f_i}+\zeta^2z_{f_i}}$.

Compute query polynomial $\color{purple}{f(X) = \sum_{i=0}^{n-1}f_i\textbf{L}_i(X)}$.

Compute $\color{purple}{[f]_1 = [f(x)]_1}$.

Output $([a]_1, [b]_1, [c]_1, \color{purple}{[f]_1})$.

### Round 2

Compute permutation challenges $(\beta, \gamma, \color{purple}\delta, \color{purple}\varepsilon )\in \mathbb{F}_p$ from the transcript.

Compute permutation polynomial $z(X)$:

$z(X) = (b_7X^2+b_8X+b_9)Z_H(X) + \textbf{L}_0(X) \\ + \sum_{i=0}^{n-2}\left(\textbf{L}_{i+1}(X)\prod_{j=1}^{i}\frac{(w_j+\beta\omega^{j-1}+\gamma)(w_{n+j}+\beta k_1\omega^{j-1}+\gamma)(w_{2n+j}+\beta k_2\omega^{j-1}+\gamma)}{(w_j+\beta\sigma(j)+\gamma)(w_{n+j}+\beta\sigma(n+j)+\gamma)(w_{2n+j}+\beta\sigma(2n+j)+\gamma)}\right)$

Compute $\color{purple}{\left\{s_i\right\}_{i=0}^{2n-1}}$, the sorted concatenation of $(f,t)$.

Compute the Plookup polynomial $\color{purple}{p(X)}$:

$\color{purple}{p(X)= \textbf{L}_0(X) + \sum_{i=1}^{n-2} \left( \textbf{L}_i(X) \prod_{j=0}^{i-1}\frac{(\varepsilon+f_j)(1+\delta)(\varepsilon(1+\delta)+t_j+\delta t_{j+1})}{(ε(1+δ)+{h_1}_j+δ{h_1}_{j+1})(ε(1+δ)+{h_2}_j+δ{h_2}_{j+1})} \right)+ \textbf{L}_{n-1}(X)}$

Compute $[z]_1 = [z(x)]_1$, $\color{purple}{[p]_1 = [p(x)]_1}$, $\color{purple}{[h_1]_1 = [h_1(x)]_1}$, $\color{purple}{[h_2]_1 = [h_2(x)]_1}$.

Output $([z]_1, \color{purple}{[p]_1}, \color{purple}{[h_1]_1}, \color{purple}{[h_2]_1})$.

### Round 3

Compute challenges $\alpha_0, \alpha_1 \in \mathbb{F}_p$ from the transcript.

Compute the quotient polynomial $Q(X)$:

$Q(X) = \\
\quad (a(X)b(X)q_M(X) + a(X)q_L(X) + b(X)q_R(X) + c(X)q_O(X) + PI(X) + q_C(X)) \frac{1}{Z_H(X)} \\
+(a(X)+\beta X+\gamma) (b(X)+\beta k_1 X+\gamma) (c(X)+\beta k_2X+\gamma) z(X) \frac{\alpha_0}{Z_H(X)} \\
-(a(X)+\beta S_{\sigma 1}(X)+\gamma) (b(X)+\beta S_{\sigma 2}(X)+\gamma) (c(X)+\beta S_{\sigma 3}(X)+\gamma) z(X\omega)\frac{\alpha_0}{Z_H(X)} \\
+(z(X)-1)\textbf{L}_0(X)\frac{\alpha_0^2}{Z_H(X)} \\
\color{purple}{+ q_{Lookup}(X)(a(X)+\zeta b(X) + \zeta^2 c(X) - f(X))\frac{\alpha_1}{Z_H(X)}} \\
\color{purple}{+(p(X)-1)\textbf{L}_0(X)\frac{\alpha_1^2}{Z_H(X)}} \\
\color{purple}{+(X-\omega^{-1})p(X)(1+\delta)(\varepsilon+f(X))(\varepsilon(1+\delta)+t(X)+\delta t(X\omega))\frac{\alpha_1^3}{Z_H(X)}} \\
\color{purple}{-(X-\omega^{-1})p(X\omega)(\varepsilon(1+\delta)+h_1(X)+\delta h_1(X\omega))(\varepsilon(1+\delta)+h_2(X)+\delta h_2(X\omega))\frac{\alpha_1^3}{Z_H(X)}} \\
\color{purple}{+\textbf{L}_{n-1}(X)(h_1(X)-h_2(X\omega))\frac{\alpha_1^4}{Z_H(X)}} \\
\color{purple}{+\textbf{L}_{n-1}(X)(p(X)-1)\frac{\alpha_1^5}{Z_H(X)}}$

Split $Q(X)$ into degree $\leq n+2$ polynomials $Q_\text{lo}(X)$, $Q_\text{mid}(X)$, $Q_\text{hi}(X)$.

Output $([Q_\text{lo}]_1, [Q_\text{mid}]_1, [Q_\text{hi}]_1)$.

---

#### Justification for Quotient Polynomial $Q$

The Round 3 polynomial $t$ batches together the range checks needed for vanilla PLONK. The further range checks for Plookup can be included in this round. To avoid confusion with the Plookup table polynomial $t$, we rename the quotient polynomial from Round 3 to $Q$.

First we have the definition of $Q(X)$ as given in the PLONK paper, but reindexing to $0\ldots n-1$ rather than $1\ldots n$ where relevant.

| PLONK | |
| --------------------- | -------- |
| | $Q(X) =$ |
| gate check | $(a(X)b(X)q_M(X)+a(X)q_L(X)+b(X)q_R(X)+c(X)q_O(X)+PI(X)+q_C(X))\frac{1}{Z_H(X)}$ |
| accumulation check | $+(a(X)+\beta X+\gamma)(b(X)+\beta k_1 X+\gamma)(c(X)+\beta k_2X+\gamma)z(X)\frac{\alpha_0}{Z_H(X)}\\-(a(X)+\beta S_{\sigma 1}(X)+\gamma)(b(X)+S_{\sigma 2}(X)+\gamma)(c(X)+\beta S_{\sigma 3}(X)+\gamma)z(X\omega)\frac{\alpha_0}{Z_H(X)}$ |
| initial element check | $+(z(X)-1)\textbf{L}_0(X)\frac{\alpha_0^2}{Z_H(X)}$ |

We can add the terms below to include the Plookup checks. The polynomial $q_{Lookup}$ is the selector polynomial for Plookup gates. (Some notational changes from the Plookup paper are needed to combine the protocols while avoiding confusion. The changes made here are: $x \to X, Z \to p$, $g \to\omega$, $\beta \to \delta$, $\gamma \to \varepsilon$.)

| Plookup | |
| --------------------- | - |
| compression check | $+q_{Lookup}(X)(a(X)+\zeta b(X) + \zeta^2 c(X) - f(X))\frac{\alpha_1}{Z_H(X)}$ |
| initial element check | $+\textbf{L}_0(X)(p(X)-1)\frac{\alpha_1^2}{Z_H(X)}$ |
| accumulation check | $+(X-\omega^{-1})p(X)(1+\delta)\varepsilon+f(X))(\varepsilon(1+\delta)+t(X)+\delta t(X\omega))\frac{\alpha_1^3}{Z_H(X)}\\-(X-\omega^{-1})p(X\omega)(\varepsilon(1+\delta)+h_1(X)+\delta h_1(X\omega))(\varepsilon(1+\delta)+h_2(X)+\delta h_2(X\omega))\frac{\alpha_1^3}{Z_H(X)}$
| overlap check | $+\textbf{L}_{n-1}(X)(h_1(X)-h_2(X\omega))\frac{\alpha_1^4}{Z_H(X)}$ |
| final element check | $+\textbf{L}_{n-1}(X)(p(X)-1)\frac{\alpha_1^5}{Z_H(X)}$ |

---

### Round 4

Compute evaluation challenge $\mathfrak{z}$ from the transcript.

Compute opening evaluations:

$\bar{a} = a(\mathfrak{z}), \bar{b} = b(\mathfrak{z}), \bar{c} = c(\mathfrak{z}), \bar{S}_{\sigma 1} = S_{\sigma 1}(\mathfrak{z}), \bar{S}_{\sigma 2} = S_{\sigma 2}(\mathfrak{z}), \\ \bar{Q} = Q(\mathfrak{z}), \bar{z}_\omega = z(\mathfrak{z}\omega), \\
\color{purple}{\bar{p}_\omega = p(\mathfrak{z}\omega),\bar{h}_1 = h_1(\mathfrak{z}), \bar{h}_{1_\omega} = {h}_1(\mathfrak{z}\omega), \bar{h}_{2_\omega} = {h}_2(\mathfrak{z}\omega), \bar{f} = f(\mathfrak{z}\omega),
\bar{f}_\omega = f(\mathfrak{z}),
\bar{t} = t(\mathfrak{z}), \bar{t}_\omega = t(\mathfrak{z}\omega)}$

Compute linearization polynomial $r(X)$:

$r(X) = \\
\quad\bar{a} \bar{b}\cdot q_M(X) + \bar{a}\cdot q_L(X) + \bar{b}\cdot q_R(X) + \bar{c}\cdot q_O(X) + q_C(X) \\
+((\bar{a} + \beta\mathfrak{z}+\gamma)(\bar{b} + \beta k_1 \mathfrak{z}+\gamma)(\bar{c} + \beta k_2\mathfrak{z}+\gamma)z(X))\alpha_0\\
-((\bar{a} + \beta\bar{s}_{\sigma 1}+\gamma)(\bar{b} + \beta\bar{s}_{\sigma 2}+\gamma)\beta\bar{z}_{\omega} \cdot S_{\sigma 3}(X)) \alpha_0 \\
+z(X)\textbf{L}_0(\mathfrak{z})\alpha_0^2 \\
%
+\color{purple}{(\textbf{L}_0(\mathfrak{z})-1)q_{Lookup}(X)\bar{f}\alpha_1} \\
+\color{purple}{p(X)\textbf{L}_0(\mathfrak{z})\alpha_1^2} \\
+\color{purple}{(\mathfrak{z}-\omega^{-1})p(X)(1+\delta)(\varepsilon+\bar{f}_\omega)(\varepsilon(1+\delta)+\bar{t}+\delta \bar{t}_\omega)\alpha_1^3}\\
-\color{purple}{(\mathfrak{z}-\omega^{-1})\bar{p}_\omega(\varepsilon(1+\delta)+\bar{h}_1+\delta \bar{h}_{1_\omega})h_2(X)\alpha_1^3}\\
+\color{purple}{\textbf{L}_{n-1}(\mathfrak{z})h_1(X)\alpha_1^4} \\
+\color{purple}{\textbf{L}_{n-1}(\mathfrak{z})p(X)\alpha_1^5}$

Compute $\bar{r} = r(\mathfrak{z})$.

Output $\bar{r}$.

---

#### Justification for the Linearization Polynomial $r$

The linearization polynomial allows us to save sending a few field elements using the optimization by Mary Maller from Section 4 of the PLONK paper.

This trick can be used if the polynomial commitment scheme is homomorphic in this sense: for polynomials $f_i$ and scalars $a_i$:

$\quad\text{com}\left(\sum_i a_if_i\right)=\sum_i\left(a_i\cdot\text{com}(f_i)\right)$.

Given a polynomial $r(X) = \sum_i a_if_i(X)$ the Verifier can compute the commitment to $r$ using the commitments to the $f_i$ already provided by the Prover earlier in the protocol. Thus the Verifer can ensure that the commitment to $r$ is correctly computed by doing that computation themselves. Later the $\bar{r}$ provided by the Prover will be tested against the Verifier's $\text{com}(r)$ during the opening proof, showing the Prover also correctly computed $\bar{r}$.

To use this trick the polynomial $r$ must be a linear combination of polynomials to which the prover has already sent commitments to, or which are known to both the Prover and Verifier. To acheive linearity, some polynomials are replaced by their evaluations at $\mathfrak{z}$. This can be done in several ways. The following polynomial uses the trick to avoid having to send $\bar{z}$, $\bar{S}_{\sigma 3}$, $\bar{p}$, and $\bar{h}_{2}$.

| PLONK | |
| --------------------- | -------- |
| | $r(X) =$ |
| gate check | $\bar{a} \bar{b}\cdot q_M(X) + \bar{a}\cdot q_L(X) + \bar{b}\cdot q_R(X) + \bar{c}\cdot q_O(X) + q_C(X)$|
| accumulation check | $+((\bar{a} + \beta\mathfrak{z}+\gamma)(\bar{b} + \beta k_1 \mathfrak{z}+\gamma)(\bar{c} + \beta k_2\mathfrak{z}+\gamma)z(X))\alpha_0 \\ -((\bar{a} + \beta\bar{s}_{\sigma 1}+\gamma)(\bar{b} + \beta\bar{s}_{\sigma 2}+\gamma)\beta\bar{z}_{\omega} \cdot S_{\sigma 3}(X)) \alpha_0$ |
| initial element check | $+z(X)\textbf{L}_0(\mathfrak{z})\alpha_0^2$|

| Plookup | |
| --------------------- | - |
| compression check | $(\mathbf{L}_0(\mathfrak{z})-1)q_{Lookup}(X)\bar{f}\alpha_1$ |
| initial element check | $+p(X)\textbf{L}_0(\mathfrak{z})\alpha_1^2$ |
| accumulation check | $+(\mathfrak{z}-\omega^{-1})p(X)(1+\delta)(\varepsilon+\bar{f}_\omega)(\varepsilon(1+\delta)+\bar{t}+\delta \bar{t}_\omega)\alpha_1^3\\-(\mathfrak{z}-\omega^{-1})\bar{p}_\omega(\varepsilon(1+\delta)+\bar{h}_1+\delta \bar{h}_{1_\omega})h_2(X)\alpha_1^3$
| overlap check | $+\textbf{L}_{n-1}(\mathfrak{z})h_1(X)\alpha_1^4$ |
| final element check | $+\textbf{L}_{n-1}(\mathfrak{z})p(X)\alpha_1^5$ |

---
### Round 5

Compute opening challenge $v\in \mathbb{F}_p$ from the transcript.

Compute opening proof polynomial $W_\mathfrak{z}(X):$

$W_\mathfrak{z}(X) = \frac{1}{X-\mathfrak{z}}\left(
\;\begin{array}{ll}(
Q_\mathrm{lo}(X) + \mathfrak{z}^{n+2} Q_\mathrm{mid}(X) + \mathfrak{z}^{2n+4}Q_\mathrm{hi}(X) - \bar{Q})\\
+ v(r(X)-\bar{r}) \\
+ v^2(a(X)-\bar{a}) \\
+ v^3(b(X)-\bar{b}) \\
+ v^4(c(X)-\bar{c}) \\
+ v^5(S_{\sigma 1}(X) - \bar{s}_{\sigma 1}) \\
+ v^6(S_{\sigma 2}(X) - \bar{s}_{\sigma 2}) \\
\color{purple}{+ v^7 (f(X) - \bar{f})} \\
\color{purple}{+v^8(h_1(X)-\bar{h}_1)} \\
\end{array}\right.$

Compute opening proof polynomial $W_{\mathfrak{z}\omega}(X)$:

$W_{\mathfrak{z}\omega}(X) =
\frac{1}{X-\mathfrak{z}\omega}\left(\;\begin{array}{ll} z(X) - \bar{z}_\omega\\
\color{purple}{+ v'(h_1(X) - \bar{h}_{1\omega})} \\
\color{purple}{+ v'^2(h_2(X)-\bar{h}_{2\omega}) }\\
\color{purple}{+ v'^3(p(X)-\bar{p}_\omega)} \\
\color{purple}{+ v'^4(f(X)-\bar{f}_\omega)}
\end{array}\right.$

Compute $[W_\mathfrak{z}]_1$ and $[W_{\mathfrak{z}\omega}]_1$.

Output $([W_\mathfrak{z}]_1$, $[W_{\mathfrak{z}\omega}]_1)$.

The full proof is:

$\pi_{\text{SNARK}} = ([a]_1, [b]_1, [c]_1, \color{purple}{[f]_1}, [z]_1, \color{purple}{[p]_1}, \color{purple}{[h_1]_1}, \color{purple}{[h_2]_1}, [Q_{\text{lo}}]_1, [Q_{\text{mid}}]_1, [Q_{\text{hi}}]_1, [W_\mathfrak{z}]_1, [W_{\mathfrak{z}\omega}]_1,\\
\quad\quad\quad\quad\quad\bar{a}, \bar{b}, \bar{c},\bar{s}_{\sigma 1}, \bar{s}_{\sigma 2},\bar{r}, \bar{z}_\omega, \color{purple}{\bar{p}_\omega, \bar{h}_1, \bar{h}_{1_\omega}, \bar{h}_{2_\omega}, \bar{f}, \bar{f}_\omega)}$

---

#### Justification for Round 5 polynomials

In Round 5, the Prover commits to two polynomials $W_\mathfrak{z}$ and $W_{\mathfrak{z}\omega}$. The first represents a check of multiple polynomials at a single evaluation point $\mathfrak{z}$. The second is a further check of the $z$ permutation polynomial at a second point $\mathfrak{z}\omega$.

In Round 4, the Prover computes $\bar{f}$ and $\bar{h}_1$ and supplies these to the Verifier, whose computations rely on these values from the Prover. Therefore these evaluations need to be checked in the first opening proof polynomial.

The polynomials evaluated at second points in Plookup are $h_1$, $h_2$, $p$, and $f$, so these will be checked in the second opening proof polynomial.

The $t$ polynomial is public and does not need checked in these opening proofs. The Verifier will simply compute values on $t$ themselves.

---

## Verifier algorithm

**Verifier preprocessed input:**
$[q_M]_1 := q_M(x)\cdot[1]_1, [q_L]_1 := q_L(x)\cdot[1]_1, [q_R]_1 := q_R(x)\cdot[1]_1, [q_O]_1 := q_O(x)\cdot[1]_1,\\
[q_\text{Lookup}]_1 := q_\text{Lookup}(x)\cdot[1]_1, [s_{\sigma 1}]_1 := s_{\sigma 1}(x)\cdot[1]_1, [s_{\sigma 2}]_1 := s_{\sigma 2}(x)\cdot[1]_1, [s_{\sigma 3}]_1 := s_{\sigma 1}(3)\cdot[1]_1, \\
\color{purple}{[t]_1 := t(x)\cdot[1]_1},
x\cdot[1]_2$

1. Validate $([a]_1, [b]_1, [c]_1, [z]_1, \color{purple}{[p]_1}, \color{purple}{[h_1]_1}, \color{purple}{[h_2]_1}, \color{purple}{[f]_1}, [Q_{\text{lo}}]_1, [Q_{\text{mid}}]_1, [Q_{\text{hi}}]_1, [W_\mathfrak{z}]_1, [W_{\mathfrak{z}\omega}]_1)\in \mathbb{G}^{12}_1$.

2. Validate $(\bar{a}, \bar{b}, \bar{c}, \bar{z}, \bar{s}_{\sigma 1}, \bar{s}_{\sigma 2}, \bar{r}, \bar{z}_\omega, \color{purple}{\bar{p}_\omega, \bar{h}_1, \bar{h}_{1_\omega}, \bar{h}_{2_\omega}, \bar{f}, \bar{f}_\omega}) \in \mathbb{F}_p^{14}$.

3. Validate $(w_i)_{i\in[l]}\in\mathbb{F}^l_p$.

4. Compute challenges $\beta, \gamma, \delta, \varepsilon, \alpha_0, \alpha_1, \mathfrak{z}, v, \color{purple}{v'}, u \in \mathbb{F}_p$.

5. Compute zero polynomial evaluation $Z_H(\mathfrak{z}) = \mathfrak{z}^n-1$.

6. Compute Lagrange polynomial evaluation $\textbf{L}_0(\mathfrak{z}) = \frac{\mathfrak{z}^n-1}{n(\mathfrak{z}-1)}$ and $\color{purple}{\textbf{L}_{n-1}(\mathfrak{z}) = \frac{\mathfrak{z}^n-1}{n(\mathfrak{z}\omega-1)}}$.

7. Compute public input polynomial evaluation $PI(\mathfrak{z})=\sum_{i\in l}w_i\textbf{L}_i(\mathfrak{z})$, public table polynomial evaluations $\color{purple}{\bar{t} = t(\mathfrak{z})}$ and $\color{purple}{\bar{t}_\omega = t(\mathfrak{z\omega})}$, and public selector polynomial evaluation $\bar{q}_\text{Lookup} = q_\text{Lookup}(\mathfrak{z})$.

8. Compute the quotient polynomial evaluation:

$\quad\quad \bar{Q} =\left(\begin{array} \bar{r} + PI(\mathfrak{z}) - ((\bar{a}+\beta\bar{s}_{\sigma 1}+\gamma)(\bar{b}+\beta\bar{s}_{\sigma 2}+\gamma)(\bar{c}+\gamma)\bar{z}_\omega)\alpha_0 \\
-\textbf{L}_0(\mathfrak{z})\alpha_0^2 \color{purple}{ + \left(1-L_0(\mathfrak{z})\right)\bar{q}_\text{Lookup}(\bar{a}+\zeta \bar{b} + \zeta^2 \bar{c})\alpha_1-\textbf{L}_0(\mathfrak{z})\alpha_1^2 \\
-(\mathfrak{z}-\omega^{-1})\bar{p}_\omega(\varepsilon(1+\delta)+\bar{h}_1+\delta \bar{h}_{1_\omega})(\varepsilon(1+\delta)+\delta \bar{h}_{2_\omega})\alpha_1^3 \\
-\textbf{L}_{n-1}(\mathfrak{z})\bar{h}_{2_\omega}\alpha_1^4-\textbf{L}_{n-1}(\mathfrak{z})\alpha_1^5 }\end{array} \right)\frac{1}{Z_H(\mathfrak{z})}$

9. Compute the first part of the batched polynomial commitment $[D]_1 := v\cdot[r]_1+u\cdot\left([z]_1 + v'[h_1]_1+v'^2[h_2]_1+v'^3[p]_1+v'^4[f]_1\right):$

$\quad\quad[D]_1 = \bar{a}\bar{b}v\cdot[q_M]_1 + \bar{a}v\cdot[q_L]_1 + \bar{b}v\cdot[q_R]_1 + \bar{c}v\cdot[q_O]_1 + v\cdot[q_C]_1 \color{purple}{+(\mathbf{L_0}(\mathfrak{z})-1)\bar{f}v\alpha_1\cdot[q_{\text{Lookup}}]_1} \\ \quad\quad\quad\quad
+\left((\bar{a}+\beta\mathfrak{z}+\gamma)(\bar{b}+\beta k_1\mathfrak{z}+\gamma)(\bar{c}+\beta k_2 \mathfrak{z}+\gamma)\alpha v + \textbf{L}_0(\mathfrak{z})\alpha^2 v + u \right)\cdot[z]_1 \\ \quad\quad\quad\quad
-(\bar{a}+\beta\bar{s}_{\sigma 1} + \gamma)(\bar{b}+\beta\bar{s}_{\sigma 2} + \gamma)\alpha v \beta \bar{z}_\omega[s_{\sigma 3}]_1 \\ \quad\quad\quad\quad
\color{purple}{+\left(\textbf{L}_{n-1}(\mathfrak{z})\alpha_1^4v+uv'\right)\cdot[h_1]_1 \\ \quad\quad\quad\quad
-\left((\mathfrak{z}-\omega^{-1})\bar{p}_\omega(\varepsilon(1+\delta)+\bar{h}_1+\delta\bar{h}_{1_\omega})\alpha_1^3v + uv'^2\right)\cdot[h_2]_1 \\\quad\quad\quad\quad
+\left((\mathfrak{z}-\omega^{-1})(1+\delta)(\varepsilon+\bar{f})(\varepsilon(1+\delta)+\bar{t}+\delta\bar{t}_\omega)\alpha_1^3v + \textbf{L}_0(\mathfrak{z})\alpha_1^2v + \textbf{L}_{n-1}(\mathfrak{z})\alpha_1^5v +uv'^3\right)\cdot[p]_1 \\ \quad\quad\quad\quad}$

10. Compute full batched polynomial commitment $[F]_1$ :

$\quad\quad [F]_1:= [Q_\text{lo}]_1+\mathfrak{z}^{n+2}\cdot[Q_\text{mid}]_1+\mathfrak{z}^{2n+4}\cdot[Q_\text{hi}]_1
\\ \quad\quad\quad\quad
+[D]_1+v^2\cdot[a]_1+v^3\cdot[b]_1+v^4\cdot[c]_1+v^5\cdot[s_{\sigma 1}]_1+v^6\cdot[s_{\sigma 2}]_1 \\ \quad\quad\quad\quad
\color{purple}{+v^7\cdot[f]_1+v^8\cdot[h_1]_1}$

11. Compute group-endcoded batch evaluation $[E]_1$ :

$\quad\quad [E]_1 := \left(\begin{array}&\bar{Q} +v\bar{r} + v^2\bar{a} + v^3\bar{b} + v^4\bar{c} +v^5\bar{s}_{\sigma 1} +v^6\bar{s}_{\sigma 2} \color{purple}{+v^7\bar{f}+v^8\bar{h}_1} \\
+u(\bar{z}_\omega\color{purple}{+v'\bar{h}_{1_\omega} + v'^2\bar{h}_{2_\omega}+v'^3\bar{p}_\omega+v'^4\bar{f}_\omega})\end{array}\right)\cdot[1]_1$

12. Batch validate all evaluations:

$e({W_\mathfrak{z}]_1}+u\cdot[W_{\mathfrak{z}\omega}]_1, [x]_2) \stackrel{?}{=} e(\mathfrak{z}\cdot [W_\mathfrak{z}]_1+u\mathfrak{z}\omega[W_{\mathfrak{z}\omega}]_1 + [F]_1 - [E]_1, [1]_2)$