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\le A,t\mid A\}$. Let also

$\mathit{S}$ be the set of

$A$'th powers in

$\mathbb{F}$; i.e.,

$\mathit{S}=\{x\in \mathbb{F}\mid \mathrm{\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^[1] 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.

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\ne H$ and by

$L_i$ the Lagrange polynomials for

$H$.

Common preprocessed input:

$$\begin{gathered} 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 }^{\ast }, \\ \begin{array}{c}{q}_L(X)={\sum }_{i=1}^n{q}_{L_i}{L}_i(X),q_R(X)={\sum }_{i=1}^n{q}_{R_i}{L}_i(X),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),q_C(X)={\sum }_{i=1}^n{q}_{C_i}{L}_i(X),\\ S_{{\sigma }_1}(X)={\sum }_{i=1}^n{\sigma }^{\ast }(i)L_i(X),S_{{\sigma }_2}(X)={\sum }_{i=1}^n{\sigma }^{\ast }(n+i)L_i(X),S_{{\sigma }_3}(X)={\sum }_{i=1}^n{\sigma }^{\ast }(2n+i)L_i(X),\\ \begin{array}{rl}{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{array}\end{array} \end{gathered}$$

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 ]}$

Prover algorithm:

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{array}{rl}a(X)& :={\sum }_{i=1}^{n-2}{w}_i{L}_i(X)+b_1{L}_{n-1}(X)+b_2{L}_n(X),\\ b(X)& :={\sum }_{i=1}^{n-2}{w}_{(n-2)+i}{L}_i(X)+b_3{L}_{n-1}(X)+b_4{L}_n(X),\\ c(X)& :={\sum }_{i=1}^{n-2}{w}_{2(n-2)+i}{L}_i(X)+b_5{L}_{n-1}(X)+b_6{L}_n(X).\end{array}$$

Compute public input polynomial

$PI\in {\mathbb{F}}_{<\ell }[X]$:

$$\begin{array}{r}PI(X):={\sum }_{i=1}^{\ell }-w_i{L}_i(X).\end{array}$$

Compute quotient polynomial

$T_0\in {\mathbb{F}}_{<2n-2}[X]$:

$$\begin{array}{r}{T}_0(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))\frac{1}{Z_H(X)}.\end{array}$$

Compute the FFT-style combination polynomial

$C_1\in {\mathbb{F}}_{<8n-8}[X]$:

$$\begin{array}{r}{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{array}$$

$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]$ :

$$\begin{gathered} z(X):=(b_7{X}^2+b_{8}X+b_9)Z_H(X) \\ +L_1(X)+{\sum }_{i=1}^{n-1}(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 }^{\ast }(j)+\gamma )(w_{n+j}+\beta {\sigma }^{\ast }(n+j)+\gamma )(w_{2n+j}+\beta {\sigma }^{\ast }(2n+j)+\gamma )}) \end{gathered}$$

Compute quotient polynomials

$T_1\in {\mathbb{F}}_{<n+2}[X]$ and

$T_2\in {\mathbb{F}}_{<3n}[X]$:

$$\begin{array}{rl}{T}_1(X):=& [L_1(X)(z(X)-1)]\frac{1}{Z_H(X)},\\ T_2(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 )]\frac{1}{Z_H(X)}.\end{array}$$

Compute the FFT-style combination polynomial

$C_2\in {\mathbb{F}}_{<9n}[X]$:

$$\begin{array}{r}{C}_2(X):=z(X^3)+X\cdot T_1(X^3)+X^2\cdot T_2(X^3).\end{array}$$

$P$ computes and send

$[C_2{]}_1:=[C_2(x){]}_1$.

Now,

$P$ must prove to

$V$ the following identities:

$$\begin{array}{rl}{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{array}$$

Round 3:

Compute the random

$r\in \mathbb{F}$ :

$$r=H(transcript)$$

Compute evaluation challenge

$\mathfrak{z}=r^{24}$. Notice that

$\mathfrak{z}\in \mathit{S}$.

Compute opening evaluations:

$$\begin{gathered} \overline{q_L}=q_L(\mathfrak{z}),\overline{q_R}=q_R(\mathfrak{z}),\overline{q_O}=q_O(\mathfrak{z}),\overline{q_M}=q_M(\mathfrak{z}),\overline{q_C}=q_C(\mathfrak{z}) \\ {\overline{S}}_{{\sigma }_1}=S_{{\sigma }_1}(\mathfrak{z}),{\overline{S}}_{{\sigma }_2}=S_{{\sigma }_2}(\mathfrak{z}),{\overline{S}}_{{\sigma }_3}=S_{{\sigma }_3}(\mathfrak{z}), \\ \overline{a}=a(\mathfrak{z}),\overline{b}=b(\mathfrak{z}),\overline{c}=c(\mathfrak{z}),\overline{z}=z(\mathfrak{z}), \\ {\overline{z}}_{\omega }=z(\mathfrak{z}\omega ),{\overline{T_1}}_{\omega }=T_1(\mathfrak{z}\omega ),{\overline{T_2}}_{\omega }=T_2(\mathfrak{z}\omega ). \end{gathered}$$
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

$(\overline{q_L},\overline{q_R},\overline{q_O},\overline{q_M},\overline{q_C},{\overline{S}}_{{\sigma }_1},{\overline{S}}_{{\sigma }_2},{\overline{S}}_{{\sigma }_3},\overline{a},\overline{b},\overline{c},\overline{z},{\overline{z}}_{\omega },{\overline{T_1}}_{\omega },{\overline{T_2}}_{\omega })$ to

$V$.

Due to Lemma 5.1, P will equivalently:

1. Open
   $C_0$ at
   $S_0=root{s}_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\}$.
2. Open
   $C_1$ at
   $S_1=root{s}_4(\mathfrak{z})=\{h_1,h_1{\omega }_4,h_1{\omega }_4^2,h_1{\omega }_4^3\}$.
3. Open
   $C_2$ at
   $S_2=root{s}_3(\mathfrak{z})\cup root{s}_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^{\prime },Z_1^{\prime },Z_2^{\prime }$ defined as follows:

$$\begin{array}{c}{Z}_0^{\prime }=\{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^{\prime }=\{a(\mathfrak{z}),b(\mathfrak{z}),c(\mathfrak{z}),T_0(\mathfrak{z})\},\\ Z_2^{\prime }=\{[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$.

Round 4:

Compute a challenge

$\alpha \in \mathbb{F}$ :

$$\alpha =H(transcript)$$

$P$ computes the polynomial

$f\in {\mathbb{F}}_{<9n+12}[X]$:

$$\begin{array}{rl}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))+\\ & +{\alpha }^2(X^8-\mathfrak{z})(X^4-\mathfrak{z})(C_2(X)-r_2(X)),\end{array}$$
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{array}{rl}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))+\\ & +{\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{array}$$

$P$ computes the polynomial

$W^{\prime }(X):=\frac{L(X)}{Z_{T\mathrm{\setminus }{S}_0}(y)(X-y)}\in {\mathbb{F}}_{<9n-1}[X]$ and sends

$[W^{\prime }{]}_1:=[W^{\prime }(x){]}_1$.

Return:

$${\pi }_{\text{SNARK}}=\left(\begin{array}{r}\begin{array}{c}[C_1{]}_1,[C_2{]}_1,[W{]}_1,[W^{\prime }{]}_1,\\ \overline{q_L},\overline{q_R},\overline{q_O},\overline{q_M},\overline{q_C},{\overline{S}}_{{\sigma }_1},{\overline{S}}_{{\sigma }_2},{\overline{S}}_{{\sigma }_3},\overline{a},\overline{b},\overline{c},\overline{z},{\overline{z}}_{\omega },{\overline{T_1}}_{\omega },{\overline{T_2}}_{\omega }\end{array}\end{array}\right)$$

Verifier algorithm:

Verifier preprocessed input:

$$[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^{\prime }{]}_1\in {\mathbb{G}}_1$.

2. Validate

   $\overline{q_L},\overline{q_R},\overline{q_O},\overline{q_M},\overline{q_C},{\overline{S}}_{{\sigma }_1},{\overline{S}}_{{\sigma }_2},{\overline{S}}_{{\sigma }_3},\overline{a},\overline{b},\overline{c},\overline{z},{\overline{z}}_{\omega },{\overline{T_1}}_{\omega },{\overline{T_2}}_{\omega }\in \mathbb{F}$.

3. Validate

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

4. 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}}$.

5. Compute zero polynomial evaluation

   $Z_H(\mathfrak{z})={\mathfrak{z}}^n-1$.

6. Compute Lagrange polynomial evaluation

   $L_1(\mathfrak{z})=\frac{\omega ({\mathfrak{z}}^n-1)}{n(\mathfrak{z}-\omega )}$.

7. Compute public input polynomial evaluation

   $PI(\mathfrak{z})=\sum _{i=1}^{\ell }-w_i{L}_i(\mathfrak{z})$.

8. 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
   $\overline{q_L},\overline{q_R},\overline{q_O},\overline{q_M},\overline{q_C},{\overline{S}}_{{\sigma }_1},{\overline{S}}_{{\sigma }_2},{\overline{S}}_{{\sigma }_3}$.

9. 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
   $\overline{q_L},\overline{q_R},\overline{q_O},\overline{q_M},\overline{q_C},\overline{a},\overline{b},\overline{c}$. In particular, to compute
   $T_0(\mathfrak{z})$, he proceeds as follows:
   
   $$T_0(\mathfrak{z})=(\overline{q_L}\overline{a}+\overline{q_R}\overline{b}+\overline{q_O}\overline{c}+\overline{q_M}\overline{a}\overline{b}+\overline{q_C}+PI(\mathfrak{z}))\frac{1}{Z_H(\mathfrak{z})}$$

10. 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
    ${\overline{S}}_{{\sigma }_1},{\overline{S}}_{{\sigma }_2},{\overline{S}}_{{\sigma }_3},\overline{a},\overline{b},\overline{c},\overline{z},{\overline{z}}_{\omega },{\overline{T_1}}_{\omega },{\overline{T_2}}_{\omega }$. In particular, to compute
    $T_1(\mathfrak{z})$ and
    $T_2(\mathfrak{z})$, he proceeds as follows:
    
    $$\begin{array}{rl}{T}_1(\mathfrak{z})=& [L_1(\mathfrak{z})(\overline{z}-1)]\frac{1}{Z_H(\mathfrak{z})}\\ T_2(\mathfrak{z})=& [(\overline{a}+\beta \mathfrak{z}+\gamma )(\overline{b}+\beta k_1\mathfrak{z}+\gamma )(\overline{c}+\beta k_2\mathfrak{z}+\gamma )\overline{z}\\ & -(\overline{a}+\beta {\overline{S}}_{{\sigma }_1}+\gamma )(\overline{b}+\beta {\overline{S}}_{{\sigma }_2}+\gamma )(\overline{c}+\beta {\overline{S}}_{{\sigma }_3}+\gamma ){\overline{z}}_{\omega }]\frac{1}{Z_H(\mathfrak{z})}\end{array}$$

Helper for the Steps 8,9,10:

$$\begin{array}{rl}{C}_0(h_0{\omega }_8^i)=& \overline{q_L}+(h_0{\omega }_8^i)\cdot \overline{q_R}+(h_0{\omega }_8^i{)}^2\cdot \overline{q_O}+(h_0{\omega }_8^i{)}^3\cdot \overline{q_M}+(h_0{\omega }_8^i{)}^4\cdot \overline{q_C}\\ & +(h_0{\omega }_8^i{)}^5\cdot {\overline{S}}_{{\sigma }_1}+(h_0{\omega }_8^i{)}^6\cdot {\overline{S}}_{{\sigma }_2}+(h_0{\omega }_8^i{)}^7\cdot {\overline{S}}_{{\sigma }_3}\\ C_1(h_1{\omega }_4^i)=& \overline{a}+(h_1{\omega }_4^i)\cdot \overline{b}+(h_1{\omega }_4^i{)}^2\cdot \overline{c}+(h_1{\omega }_4^i{)}^3\cdot T_0(\mathfrak{z})\\ C_2(h_2{\omega }_3^i)=& \overline{z}+(h_2{\omega }_3^i)\cdot T_1(\mathfrak{z})+(h_2{\omega }_3^i{)}^2\cdot T_2(\mathfrak{z})\\ C_2(h_3{\omega }_3^i)=& {\overline{z}}_{\omega }+(h_3{\omega }_3^i)\cdot {\overline{T_1}}_{\omega }+(h_3{\omega }_3^i{)}^2\cdot {\overline{T_2}}_{\omega }\end{array}$$

11. Compute the polynomial commitment

    $[F{]}_1$:
    
    $$\begin{array}{rl}[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{array}$$

12. Compute group-encoded batch evaluation

    $[E{]}_1$:
    
    $$\begin{array}{rl}[E{]}_1:=& (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))\cdot [1{]}_1\end{array}$$

13. Compute the full difference

    $[J{]}_1$:
    
    $$[J{]}_1:=(y^8-\mathfrak{z})[W{]}_1$$

14. Validate all evaluations:

$$e([F{]}_1-[E{]}_1-[J{]}_1+y[W^{\prime }{]}_1,[1{]}_2)\stackrel{?}{=}e([W^{\prime }{]}_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

---

1. Hint: Take an element of order

   $24n$ and check the relationship between this element and
   $\omega$. ↩︎