# Fflonk

Link to the paper: https://eprint.iacr.org/2021/1167.pdf
Link to the slides: https://hecmas.github.io/talk/fflonk-for-the-polygon-zkevm/
Link to some comments and **optimizations**: https://hackmd.io/-2oVDtk4TJGVWFAYvUoY1g?view

## Comparison to Other Protocols

| Protocol | CRS/SRS Size | Prover Comp. | Proof Length | Verifier Comp. |
|:--------:|:--------------------------------:|:----------------------------------------:|:-------------------------------:|:--------------------------------:|
| Groth16 | $3m+w~\mathbb{G}_1$ | $3m+w-\ell~\mathbb{G}_1, m~\mathbb{G}_2$ | $2~\mathbb{G}_1,1~\mathbb{G}_2$ | $\ell~\mathbb{G}_1,3~\mathbf{P}$ |
| Plonk | $3n~\mathbb{G}_1,2~\mathbb{G}_2$ | $11n~\mathbb{G}_1$ | $7~\mathbb{G}_1, 7~\mathbb{F}$ | $16~\mathbb{G}_1, 2~\mathbf{P}$ |
| Fflonk | $9n~\mathbb{G}_1,2~\mathbb{G}_2$ | $35n~\mathbb{G}_1$ | $4~\mathbb{G}_1, 15~\mathbb{F}$ | $5~\mathbb{G}_1, 2~\mathbf{P}$ |
| PolyMath | | | $3~\mathbb{G}_1,1~\mathbb{F}$ | $2~\mathbb{G}_1,1~\mathbb{G}_2,2~\mathbf{P},O(\ell\log \ell)~\mathbf{F}$ |
- $m$ denotes the number of multiplication gates.
- $w$ denotes the number of wires.
- $n$ denotes the number of gates.
- $\ell$ denotes number of public inputs.
- $\mathbb{G}_i$ denotes scalar multiplications in $\mathbb{G}_i$.
- $\mathbf{P}$ denotes pairings.

## Full Description of the Protocol

Fix positive integer $A$ dividing $p-1$ (for the case of a sufficiently smooth prime field, setting $A=24$ is enough). Let $T$ be the set of divisors of $A$, i.e., $T = \{t \in \mathbb{N} \mid 0 < t \leq A, t \mid A\}$. Let also $\boldsymbol{S}$ be the set of $A$'th powers in $\mathbb{F}$; i.e., $\boldsymbol{S} = \{x \in \mathbb{F} \mid \exists z \in \mathbb{F} ~s.t.~z^A = x\}$.

Assume that $n$ is a power of two such that $24n$ divides $p-1$, and $H \subset \mathbb{F}$ is a multiplicative subgroup of $\mathbb{F}$ of order $n$ with generator $\omega$. One can show[^first] that the previous divisibility assumption implies that $\omega$ is a $24$-th power in $\mathbb{F}$, which is necessary to ensure that $\omega$ has some particular roots.

[^first]: **Hint**: Take an element of order $24n$ and check the relationship between this element and $\omega$.

We denote by $\omega_3$ to a generator of order $3$, by $\omega_4$ to a generator of order $4$ and by $\omega_8$ to a generator of order $8$. Finally, we denote by $L_i^{(S)}$ the Lagrange polynomials for any set $S \neq H$ and by $L_i$ the Lagrange polynomials for $H$.

### Common preprocessed input:

$$
n, (x \cdot [1]_1,...,x^{9n+17} \cdot [1]_1), (q_{L_i}, q_{R_i},q_{O_i},q_{M_i},q_{C_i})_{i=1}^n, \sigma^*, \\
\begin{array}{c}
q_L(X) = {\sum}_{i=1}^{n} q_{L_i}L_i(X), \quad
q_R(X) = {\sum}_{i=1}^{n} q_{R_i}L_i(X), \quad
q_O(X) = {\sum}_{i=1}^{n} q_{O_i}L_i(X), \\
q_M(X) = {\sum}_{i=1}^{n} q_{M_i}L_i(X), \quad
q_C(X) = {\sum}_{i=1}^{n} q_{C_i}L_i(X), \\
S_{\sigma_1}(X) = {\sum}_{i=1}^{n} \sigma^*(i)L_i(X), \quad
S_{\sigma_2}(X) = {\sum}_{i=1}^{n} \sigma^*(n+i)L_i(X), \quad
S_{\sigma_3}(X) = {\sum}_{i=1}^{n} \sigma^*(2n+i)L_i(X), \\
\begin{align}
C_0(X) = ~&q_L(X^8) + X \cdot q_R(X^8) + X^2 \cdot q_O(X^8) + X^3 \cdot q_M(X^8) + X^4 \cdot q_C(X^8) \\
&+~X^5 \cdot S_{\sigma_1}(X^8) + X^6 \cdot S_{\sigma_2}(X^8) + X^7 \cdot S_{\sigma_3}(X^8).
\end{align}
\end{array}
$$

**Degrees**: $q_L,q_R,q_O,q_M,q_C,S_{\sigma_1},S_{\sigma_2},S_{\sigma_3} \in \mathbb{F}_{<n}[X]$ and $C_0 \in \mathbb{F}_{<8n}[X]$.

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

### <ins>Prover algorithm:</ins>

#### Prover input: $(w_i)_{i \in [3(n-2)]}$.
We think the circuit as having at most $n-2$ "useful" gates, since the last two will be used to introduce random values to the wiring polynomials to achieve a zero-knowledge protocol.

#### Round 1:

Generate random blinding scalars $b_1,\dots, b_9 \in \mathbb{F}$.

Compute wire polynomials $a,b,c \in \mathbb{F}_{<n}[X]$:
\begin{align}
a(X) &:= {\sum}_{i=1}^{n-2} w_iL_i(X) + b_1L_{n-1}(X) + b_2L_{n}(X), \\
b(X) &:= {\sum}_{i=1}^{n-2} w_{(n-2)+i}L_i(X) + b_3L_{n-1}(X) + b_4L_{n}(X) , \\
c(X) &:= {\sum}_{i=1}^{n-2} w_{2(n-2)+i}L_i(X) + b_5L_{n-1}(X) + b_6L_{n}(X).
\end{align}

Compute public input polynomial $PI \in \mathbb{F}_{<\ell}[X]$:
$$
\begin{align}
PI(X) := {\sum}_{i=1}^{\ell} -w_iL_i(X).
\end{align}
$$

Compute quotient polynomial $T_0 \in \mathbb{F}_{<2n-2}[X]$:
$$
\begin{align}
T_0(X) := \left(q_L(X)a(X) + q_R(X)b(X) + q_O(X)c(X) + q_M(X)a(X)b(X) + q_C(X) + PI(X)\right) \frac{1}{Z_H(X)}.
\end{align}
$$

Compute the FFT-style combination polynomial $C_1 \in \mathbb{F}_{<8n-8}[X]$:
$$
\begin{align}
C_1(X) := a(X^4) + X \cdot b(X^4) + X^2 \cdot c(X^4) + X^3 \cdot T_0(X^4).
\end{align}
$$

$P$ computes and sends $[C_1]_1 := [C_1(x)]_1$.

#### Round 2:

Compute permutation challenges $\beta, \gamma \in \mathbb{F}$ :

$$\beta = H(transcript, 0), \gamma = H(transcript, 1)$$

Compute permutation polynomial $z \in \mathbb{F}_{<n+3}[X]$ :
$$
z(X) := (b_7X^2 + b_8X + b_9)Z_H(X) \\
+L_1(X)
+{\sum}_{i=1}^{n−1} \left(L_{i+1}(X) {\prod}_{j=1}^i \frac{(w_j + \beta \omega^j + \gamma)(w_{n+j} + \beta k_1 \omega^j + \gamma)(w_{2n+j} + \beta k_2 \omega^j + \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 quotient polynomials $T_1 \in \mathbb{F}_{<n+2}[X]$ and $T_2 \in \mathbb{F}_{<3n}[X]$:
$$
\begin{align}
T_1(X) := ~&\left[L_1(X)(z(X)-1)\right] \frac{1}{Z_H(X)}, \\
T_2(X) := ~&\left[ (a(X) + \beta X + \gamma) (b(X) + \beta k_1 X + \gamma) (c(X) + \beta k_2 X + \gamma) z(X) \right. \\
&\left. -(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)\right] \frac{1}{Z_H(X)}.
\end{align}
$$

Compute the FFT-style combination polynomial $C_2 \in \mathbb{F}_{<9n}[X]$:
$$
\begin{align}
C_2(X) := z(X^3) + X \cdot T_1(X^3) + X^2 \cdot T_2(X^3).
\end{align}
$$

$P$ computes and send $[C_2]_1 := [C_2(x)]_1$.

:::success
Now, $P$ must prove to $V$ the following identities:
\begin{align}
T_0(X)Z_H(X) = &~q_L(X)a(X) + q_R(X)b(X) + q_O(X)c(X) + q_M(X)a(X)b(X) + q_C(X) + PI(X), \\
T_1(X)Z_H(X) = &~L_1(X)(z(X)-1), \\
T_2(X)Z_H(X) = &~(a(X) + \beta X + \gamma) (b(X) + \beta k_1 X + \gamma) (c(X) + \beta k_2 X + \gamma) z(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).
\end{align}
:::

#### Round 3:

Compute the random $r \in \mathbb{F}$ :
$$
r = H(transcript)
$$

Compute evaluation challenge $\mathfrak{z} = r^{24}$. **Notice** that $\mathfrak{z} \in \boldsymbol{S}$.

Compute opening evaluations:
$$
\bar{q_L} = q_L(\mathfrak{z}), \bar{q_R} = q_R(\mathfrak{z}), \bar{q_O} = q_O(\mathfrak{z}), \bar{q_M} = q_M(\mathfrak{z}), \bar{q_C} = q_C(\mathfrak{z}) \\
\bar{S}_{\sigma_1} = S_{\sigma_1}(\mathfrak{z}), \bar{S}_{\sigma_2} = S_{\sigma_2}(\mathfrak{z}), \bar{S}_{\sigma_3} = S_{\sigma_3}(\mathfrak{z}), \\
\bar{a} = a(\mathfrak{z}), \bar{b} = b(\mathfrak{z}), \bar{c} = c(\mathfrak{z}), \bar{z} = z(\mathfrak{z}), \\
\bar{z}_{\omega} = z(\mathfrak{z}\omega), \bar{T_1}_{\omega} = T_1(\mathfrak{z}\omega), \bar{T_2}_{\omega} = T_2(\mathfrak{z}\omega).
$$
Notice that these points are enough for opening $a,b,c,T_0$ at $\mathfrak{z}$ and $z,T_1,T_2$ at $\mathfrak{z}$ and $\mathfrak{z}\omega$.

$P$ sends $(\bar{q_L}, \bar{q_R}, \bar{q_O}, \bar{q_M}, \bar{q_C}, \bar{S}_{\sigma_1}, \bar{S}_{\sigma_2}, \bar{S}_{\sigma_3}, \bar{a}, \bar{b}, \bar{c}, \bar{z}, \bar{z}_{\omega}, \bar{T_1}_{\omega}, \bar{T_2}_{\omega})$ to $V$.

:::info
Due to Lemma 5.1, P will equivalently:
1. Open $C_0$ at $S_0 = roots_8(\mathfrak{z}) = \{h_0,h_0\omega_8,h_0\omega_8^2,h_0\omega_8^3,h_0\omega_8^4,h_0\omega_8^5,h_0\omega_8^6,h_0\omega_8^7\}$.
1. Open $C_1$ at $S_1 = roots_4(\mathfrak{z}) = \{h_1,h_1\omega_4,h_1\omega_4^2,h_1\omega_4^3\}$.
1. Open $C_2$ at $S_2 = roots_3(\mathfrak{z})\cup roots_3(\mathfrak{z}\omega) = \{[h_2,h_2\omega_3,h_2\omega_3^2],[h_3,h_3\omega_3,h_3\omega_3^2]\}$.

Here, $h_0^8 = \mathfrak{z}$, $h_1^4 = \mathfrak{z}$, $h_2^3 = \mathfrak{z}$ and $h_3^3 = \mathfrak{z}\omega$, which are computed from $r$ as follows:
- $h_0 = r^3$, since $h_0^8 = r^{24} = \mathfrak{z}$.
- $h_1 = r^6$, since $h_1^4 = r^{24} = \mathfrak{z}$.
- $h_2 = r^8$, since $h_2^3 = r^{24} = \mathfrak{z}$.
- $h_3 = r^8\omega^{1/3}$, since $h_3^3 = r^{24}\omega = \mathfrak{z}\omega$.

To this end, P computes the sets $S_0,S_1,S_2$. He also computes the sets $Z_0,Z_1,Z_2$ using $Z_0',Z_1',Z_2'$ defined as follows:
\begin{array}{c}
Z_0' = \{q_L(\mathfrak{z}), q_R(\mathfrak{z}), q_O(\mathfrak{z}), q_M(\mathfrak{z}),q_C(\mathfrak{z}), S_{\sigma_1}(\mathfrak{z}), S_{\sigma_2}(\mathfrak{z}), S_{\sigma_3}(\mathfrak{z})\}, \\
Z_1' = \{a(\mathfrak{z}), b(\mathfrak{z}), c(\mathfrak{z}), T_0(\mathfrak{z})\}, \\
Z_2' = \{[z(\mathfrak{z}), T_1(\mathfrak{z}), T_2(\mathfrak{z})],[z(\mathfrak{z}\omega), T_1(\mathfrak{z}\omega), T_2(\mathfrak{z}\omega)]\}, \\
Z_0 = \{C_0(h_0),C_0(h_0\omega_8),C_0(h_0\omega_8^2),C_0(h_0\omega_8^3),C_0(h_0\omega_8^4),C_0(h_0\omega_8^5),C_0(h_0\omega_8^6),C_0(h_0\omega_8^7)\}, \\
Z_1 = \{C_1(h_1),C_1(h_1\omega_4),C_1(h_1\omega_4^2),C_1(h_1\omega_4^3)\}, \\
Z_2 = \{[C_2(h_2),C_2(h_2\omega_3),C_2(h_2\omega_3^2)],[C_2(h_3),C_2(h_3\omega_3),C_2(h_3\omega_3^2)]\}.
\end{array}

**Note** that $S_i$ and $Z_i$ can be also computed by $V$, for $i \in \{0,1,2\}$.

From now on, define $T = S_0 \cup S_1 \cup S_2$. We have $|T| = 18$.
<!--
Notice that $T\backslash S_1 = S_2$ and $T \backslash S_2 = S_1$.
-->
:::

#### Round 4:

Compute a challenge $\alpha \in \mathbb{F}$ :
$$
\alpha = H(transcript)
$$

$P$ computes the polynomial $f \in \mathbb{F}_{<9n+12}[X]$:
\begin{align}
f(X) :=~&(X^4-\mathfrak{z})(X^3-\mathfrak{z})(X^3-\mathfrak{z}\omega)(C_0(X)-r_0(X))+\alpha(X^8-\mathfrak{z})(X^3-\mathfrak{z})(X^3-\mathfrak{z}\omega) (C_1(X) - r_1(X))~+ \\[0.2cm]
&+\alpha^2 (X^8-\mathfrak{z})(X^4-\mathfrak{z})(C_2(X) - r_2(X)),
\end{align}
where:
- The polynomial $r_0 \in \mathbb{F}_{<8}[X]$ is such that $r_0(h_0\omega_8^i) = C_0(h_0\omega_8^i)$, for $i \in [8]$, that is:
$$
r_0(X) = \sum_{i=1}^8 C_0(h_0\omega_8^{i-1})L_i^{(S_0)}(X).
$$
- The polynomial $r_1 \in \mathbb{F}_{<4}[X]$ is such that $r_1(h_1\omega_4^i) = C_1(h_1\omega_4^i)$, for $i \in [4]$, that is:
$$
r_1(X) = \sum_{i=1}^4 C_1(h_1\omega_4^{i-1})L_i^{(S_1)}(X).
$$
- The polynomial $r_2 \in \mathbb{F}_{<6}[X]$ is such that $r_2(h_j\omega_3^i) = C_2(h_j\omega_3^i)$ for $i \in [3]$, $j\in\{2,3\}$, that is:
$$
r_2(X) = \sum_{i=1}^3 C_2(h_2\omega_3^{i-1})L_i^{(S_2)}(X) + \sum_{i=4}^6 C_2(h_3\omega_3^{i-1})L_i^{(S_2)}(X).
$$

$P$ computes the polynomial $W(X) := f(X)/Z_T(X)\in \mathbb{F}_{<9n-6}[X]$ and sends $[W]_1 := [(f/Z_T)(x)]_1$.

#### Round 5:

Compute a random evaluation point $y \in \mathbb{F}$ :
$$
y = H(transcript)
$$

P computes the polynomial $L \in \mathbb{F}_{<9n}[X]$:
\begin{align}
L(X) :=~&(y^4-\mathfrak{z})(y^3-\mathfrak{z})(y^3-\mathfrak{z}\omega)(C_0(X) - r_0(y))+\alpha(y^8-\mathfrak{z})(y^3-\mathfrak{z})(y^3-\mathfrak{z}\omega)(C_1(X) - r_1(y))~+ \\[0.2cm]
&+\alpha^2 (y^8-\mathfrak{z})(y^4-\mathfrak{z})(C_2(X) - r_2(y))-Z_T(y)\frac{f(X)}{Z_T(X)}.
\end{align}

$P$ computes the polynomial $W'(X) := \frac{L(X)}{Z_{T\backslash S_0}(y)(X-y)} \in \mathbb{F}_{<9n-1}[X]$ and sends $[W']_1 := [W'(x)]_1$.

<!--
Add the inverse sent from P to V and the correspoding checks in the verifier description
-->

Return:
$$
\pi_{\text{SNARK}} =
\left(
\begin{split}
\begin{array}{c}
[C_1]_1,[C_2]_1,[W]_1,[W']_1, \\
\bar{q_L}, \bar{q_R}, \bar{q_O}, \bar{q_M}, \bar{q_C}, \bar{S}_{\sigma_1}, \bar{S}_{\sigma_2}, \bar{S}_{\sigma_3}, \bar{a}, \bar{b}, \bar{c}, \bar{z}, \bar{z}_{\omega}, \bar{T_1}_{\omega}, \bar{T_2}_{\omega}
\end{array}
\end{split}
\right)
$$

### <ins>Verifier algorithm:</ins>

#### Verifier preprocessed input:

<!--
$$
\begin{split}
&[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_{M}]_1 := q_M(x) \cdot [1]_1, \\
&[q_{C}]_1 := q_C(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_3}(x) \cdot [1]_1, x \cdot [1]_2
\end{split}
$$
-->

$$
[C_0]_1 := C_0(x) \cdot [1]_1, x \cdot [1]_2
$$

$V((w_i)_{i\in[\ell]}, \pi_\text{SNARK})$ :

1. Validate $[C_1]_1,[C_2]_1,[W]_1,[W']_1 \in \mathbb{G}_1$.

1. Validate $\bar{q_L}, \bar{q_R}, \bar{q_O}, \bar{q_M}, \bar{q_C}, \bar{S}_{\sigma_1}, \bar{S}_{\sigma_2}, \bar{S}_{\sigma_3}, \bar{a}, \bar{b}, \bar{c}, \bar{z}, \bar{z}_{\omega}, \bar{T_1}_{\omega}, \bar{T_2}_{\omega} \in \mathbb{F}$.

1. Validate $w_i \in \mathbb{F}$ for $i \in [\ell]$.

1. Compute challenges $\beta,\gamma,\mathfrak{z},\alpha,y \in \mathbb{F}$ as in prover description, from the common inputs, public input, and the elements of $\pi_\text{SNARK}$.

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

1. Compute Lagrange polynomial evaluation $L_1(\mathfrak{z}) = \frac{\omega(\mathfrak{z}^n−1)}{n(\mathfrak{z}−\omega)}$.

1. Compute public input polynomial evaluation $PI(\mathfrak{z}) = \sum_{i=1}^{\ell} -w_iL_i(\mathfrak{z})$.

1. Computes $r_0(y) = \sum_{i=1}^8 C_0(h_0\omega_8^{i-1})L_i^{(S_0)}(y)$. To this end, $V$ needs to compute $Z_0$, and he can do so from $\bar{q_L}, \bar{q_R}, \bar{q_O}, \bar{q_M}, \bar{q_C}, \bar{S}_{\sigma_1}, \bar{S}_{\sigma_2}, \bar{S}_{\sigma_3}$.

1. Computes $r_1(y) = \sum_{i=1}^4 C_1(h_1\omega_4^{i-1})L_i^{(S_1)}(y)$. To this end, $V$ needs to compute $Z_1$, and he can do so from $\bar{q_L}, \bar{q_R}, \bar{q_O}, \bar{q_M}, \bar{q_C}, \bar{a}, \bar{b}, \bar{c}$. In particular, to compute $T_0(\mathfrak{z})$, he proceeds as follows:
$$
T_0(\mathfrak{z}) = \left(\bar{q_L}\bar{a} + \bar{q_R}\bar{b} + \bar{q_O}\bar{c} + \bar{q_M}\bar{a}\bar{b} + \bar{q_C} + PI(\mathfrak{z})\right)\frac{1}{Z_H(\mathfrak{z})}
$$

1. Computes $r_2(X) = \sum_{i=1}^3 C_2(h_2\omega_3^{i-1})L_i^{(S_2)}(X) + \sum_{i=4}^6 C_2(h_3\omega_3^{i-1})L_i^{(S_2)}(X)$. To this end, $V$ needs to compute $Z_2$, and he can do so from $\bar{S}_{\sigma_1}, \bar{S}_{\sigma_2}, \bar{S}_{\sigma_3}, \bar{a}, \bar{b}, \bar{c}, \bar{z}, \bar{z}_{\omega}, \bar{T_1}_{\omega}, \bar{T_2}_{\omega}$. In particular, to compute $T_1(\mathfrak{z})$ and $T_2(\mathfrak{z})$, he proceeds as follows:
\begin{align}
T_1(\mathfrak{z}) = &~\left[L_1(\mathfrak{z})(\bar{z}-1)\right]\frac{1}{Z_H(\mathfrak{z})} \\
T_2(\mathfrak{z}) = &~\left[(\bar{a} + \beta \mathfrak{z} + \gamma) (\bar{b} + \beta k_1 \mathfrak{z} + \gamma) (\bar{c} + \beta k_2 \mathfrak{z} + \gamma) \bar{z} \right. \\
& \left.-(\bar{a} + \beta \bar{S}_{\sigma_1} + \gamma) (\bar{b} + \beta \bar{S}_{\sigma_2} + \gamma) (\bar{c} + \beta \bar{S}_{\sigma_3} + \gamma) \bar{z}_{\omega}\right]\frac{1}{Z_H(\mathfrak{z})}
\end{align}

:::info
Helper for the Steps 8,9,10:
\begin{align}
C_0(h_0\omega_8^{i}) = &~\bar{q_L} + (h_0\omega_8^{i}) \cdot \bar{q_R} + (h_0\omega_8^{i})^2 \cdot \bar{q_O} + (h_0\omega_8^{i})^3 \cdot \bar{q_M} + (h_0\omega_8^{i})^4 \cdot \bar{q_C} \\[0.2cm]
&~+(h_0\omega_8^{i})^5 \cdot \bar{S}_{\sigma_1} + (h_0\omega_8^{i})^6 \cdot \bar{S}_{\sigma_2} + (h_0\omega_8^{i})^7 \cdot \bar{S}_{\sigma_3} \\[0.2cm]
C_1(h_1\omega_4^i) = &~\bar{a} + (h_1\omega_4^i) \cdot \bar{b} + (h_1\omega_4^i)^2 \cdot \bar{c} + (h_1\omega_4^i)^3 \cdot T_0(\mathfrak{z}) \\[0.2cm]
C_2(h_2\omega_3^i) = &~\bar{z} + (h_2\omega_3^i) \cdot T_1(\mathfrak{z}) + (h_2\omega_3^i)^2 \cdot T_2(\mathfrak{z}) \\[0.2cm]
C_2(h_3\omega_3^i) = &~\bar{z}_\omega + (h_3\omega_3^i) \cdot \bar{T_1}_\omega + (h_3\omega_3^i)^2 \cdot \bar{T_2}_\omega
\end{align}
:::

11. Compute the polynomial commitment $[F]_1$:
\begin{align}
[F]_1 := &~[C_0]_1 + \alpha\frac{(y^8-\mathfrak{z})(y^3-\mathfrak{z})(y^3-\mathfrak{z}\omega)}{(y^4-\mathfrak{z})(y^3-\mathfrak{z})(y^3-\mathfrak{z}\omega)}[C_1]_1+\alpha^2\frac{(y^8-\mathfrak{z})(y^4-\mathfrak{z})}{(y^4-\mathfrak{z})(y^3-\mathfrak{z})(y^3-\mathfrak{z}\omega)}[C_2]_1
\end{align}

1. Compute group-encoded batch evaluation $[E]_1$:
\begin{align}
[E]_1 := &~\left(r_0(y) + \alpha\frac{(y^8-\mathfrak{z})(y^3-\mathfrak{z})(y^3-\mathfrak{z}\omega)}{(y^4-\mathfrak{z})(y^3-\mathfrak{z})(y^3-\mathfrak{z}\omega)}r_1(y)+\alpha^2\frac{(y^8-\mathfrak{z})(y^4-\mathfrak{z})}{(y^4-\mathfrak{z})(y^3-\mathfrak{z})(y^3-\mathfrak{z}\omega)}r_2(y)\right) \cdot [1]_1
\end{align}

1. Compute the full difference $[J]_1$:
$$
[J]_1 := (y^8-\mathfrak{z})[W]_1
$$

1. Validate all evaluations:

$$e([F]_1 - [E]_1 - [J]_1 + y[W']_1, [1]_2) \stackrel{?}{=} e([W']_1,[x]_2)$$

## Some Doubts and Open Questions

- [Solved] **Election of $A$**: ~~For our use case $12$ is a good candidate since it is the least common multiple of $3$ and $4$, but in the paper they claim that $24$ is necessary. Why? I think that they say that because~~ they are considering the commitment to the preprocessed polynomials (which are $8$ are therefore the $\text{lcm}(3,4,8)=24$). ~~However, we have seen the verifier do not need to use the commitments to the preprocessed polynomials, and therefore are not necessary.~~

- [Solved] **Section 7 Assumptions:** ~~At the beginning of Section 7, why do you assume that $24n$ divides $p-1$?~~ I suppose that is to guarantee the existence of the different roots that have to be computed during the protocol. YES: it is to be able to compute roots of the generator $\omega$.

- [Solved] ~~**Preprocessed Polynomials** $q_L,q_R,q_O,q_M,q_C,S_{\sigma_1},S_{\sigma_2},S_{\sigma_3}$: I do not know yet why the verifier need to use the commitments to the preprocessed polynomials, I need to figure it out (it only uses $[x]_2$ from the preprocessing). Why do they need to send to the verifier in Lemma 6.4? In case we have to, the prover computes $g:=\text{combine}_{t_0}(\overline{f_0})$ and sends the commitment to $g$ to the verifier, which I do not see how this commitment would be used by the verifier itself.~~

- [Solved] **Computation of $r_1,r_2$**: In round 4 of the proving algorithm, the prover computes the polynomials $r_1 \in \mathbb{F}_{<4}[X]$ and $r_1 \in \mathbb{F}_{<6}[X]$ by Lagrange interpolation. How does the verifier need to obtain them? He needs so to compute $r_1(y),r_2(y)$. If they are computed via Lagrange interpolation, the verifier complexity will be dominated by this computation (rather than elliptic curve operations).
- ~~We are exploring the prover sending $r_1(y)$ and $r_2(y)$ to the verifier, but we must check if this would break the soundness of the protocol. Moreover, this would increase the proof size by $2$ field elements.~~
- We are exploring a sound alternative: the prover sending to the verifier the inverse needed to compute the $10$ Lagrange polynomials needed in the definition of $r_1(y),r_2(y)$. We are using a batching protocol for computing multiple inverses, so with one is enough.

###### tags: `PlonK`