# Fflonk - A New Plonk Protocol
## Preface

Before getting into details of Fflonk, here is a brief summary of what it can achieve compared with PLONK.

Fflonk is a variant of PLONK and improves the performance of Verify, but at the same time increases the consumption of Prover. To be specific, the verification of the PLONK protocol, i.e., Fflonk, using the new commitment scheme only requires 5 times of G~1~-exp, while for the original PLONK algorithm, Verifier requires 16 or 18 times of G~1~-exp. Thus, Fflonk significantly improves the performance of Verify.


Figure 1 PLONK-Verify

Note: The blue and black marks in the above figure can be combined (18-\>16).

## Overview

In the original KZG10 scheme, the open of the polynomial f at the point x requires pairing for 2 times. If there are multiple polynomials (ie t polynomials) open at x, then 2t times of pairing is required; in order to improve the verification performance, the method of Batch opening in KZG10 is applied, that is, through a random number γ, multiple polynomials are linearly combined, (f(x) = ∑γ^i-1^f~i~), and then open at point x, only 2 pairings are required, but depends on the parameter t, an additional t-1 multi-exp is added. The question is how to make the complexity of Verify have no bearing on t.

There is a new commitment method in Shplonk. Under the premise of multi-poly and multi-openings, the complexity of Verify is only related to the number of polynomials, and has nothing to do with the number of openings. **If we can transform the "opening problem of t polynomials at point x" into "the opening problem of a polynomial at multiple points" and then use the commitment method in Shplonk, we will get a constant level of complexity PCS.**

## Some Definitions

In order to better understand the algorithm, let's take a look at the mathematical meaning of relevant notations.

### Notation

\[\<t\] =\> {0,1,...,t-1}

F =\>domain

F^(1)^ =\> vector in F (t ={1,2,...m})

F^(2)^ =\> vector of vector in F (T = {t~1~,t~2~,...t~m~})

F^(3)^ =\> vector of vector of vector in F（TT = {T~1~,T~2~,...T~m~}）

D^(1)^ D^(2)^ D^(3)^ =\>resembles the meaning of F^(\*)^

The element ${\overline{f}}_{i}$ in $\overline{\overline{f}}\ \in D^{2}$ =\>$\overline{\overline{f}}$is a vector in D(0<i\< \|$\overline{\overline{f}}$\|), and the element f~i,j~ in ${\overline{f}}_{i}$ is an element in the domain D (i\< \|$\overline{\overline{f}}$\|, j \< \|${\overline{f}}_{i}$\|)

F~\<d~\[X\] =\>a polynomial whose elements are in the domain F and whose degree is less than d

$\overline{f}\ \in \ {F\lbrack X\rbrack}^{t}$=\>for one point x ϵ F，$\overline{f}(x)\ : = \ (f_{0}(x),...,f_{t - 1}(x))$

- For Multi points $\overline{Z}\ \in \ F^{l}$, $\overline{f}\left( \overline{Z} \right) \in F^{(2)}$，where $\overline{f}\left( \overline{Z} \right)\ ≔ \ \left( \overline{f}\left( Z_{j} \right) \right)_{j < l}$

$\overline{\overline{f}}\ \in \ {F\lbrack X\rbrack}^{(2)}$ =\>for $\overline{\overline{Z}}\ \in \ F^{(2)}$, and \|$\overline{\overline{f}}$\|=\|$\overline{\overline{Z}}$\|，$\ \overline{\overline{f}}\left( \overline{\overline{Z}} \right) \in F^{(3)}$，where $\overline{\overline{f}}\left( \overline{\overline{Z}} \right)\ ≔ \ \left( \overline{f_{i}}\left( {\overline{Z}}_{i} \right) \right)_{i < |\overline{\overline{f}}|}$

## Improved Shplonk

If you read Sin7Y's previous article on Shplonk, you will know that one $\text{open}_{\text{shplonk}}(1^{k},\overline{\text{cm}},\overline{\overline{Z}},\overline{\overline{S}};\overline{f})$ requires:

1. **2**\*G~1~ elements, sent from Prover to Verifier

2. Up to **(2n+1)**\*G~1~-scalar multiplication for prover

3. **(K+3)\***G~1~-scalar multiplication and 2 pairings for verifier

Through careful research, we found that a simple transformation can reduce one G~1~-scalar multiplication operation in Verify. The new Shplonk commitment protocol is as follows:

$open({\{\text{cm}_{i}\}}_{i \in \lbrack k\rbrack},{\{ S_{i}\}}_{i \in \lbrack k\rbrack},{\{ r_{i}\}}_{i \in \lbrack k\rbrack};{\{ f_{i}\}}_{i \in k})$:

1. V sends a random number γ to P

2. P sends W：= \[f(X) / Z~T~(X)\]~1,~ where

$$f(X)\ : = \ \sum_{\text{i\ ϵ\ k}}^{}{\text{γ\ }^{i - 1} \bullet {(f}_{i}(X)\ - \ r_{i}(X))}{\bullet Z}_{T\backslash Si}(X)$$

3. *V sends open point z to P*

4. *P sends* W\` ：= \[L(X)/$\mathbf{Z}_{\mathbf{T\backslash S}\mathbf{1}}\mathbf{(z)}$(X-z)\]~1~, where

$$L(X)\ : = \ \sum_{\text{i\ ϵ\ k}}^{}{\text{γ\ }^{i - 1} \bullet {(f}_{i}(X)\ - \ r_{i}(z))}{\bullet Z}_{T\backslash Si}(X)\ - \ Z_{T}(z)\ \bullet (f/Z_{T})$$

5. *V verifies whether the equation* e (F+ zW\`, \[1\]~2~) = e(W\`, \[x\]~2~) holds, where

$$F\ : = \ \sum_{\text{i\ ϵ\ k}}^{}{\text{γ\ }^{i - 1} \bullet}\text{cm}_{i} \bullet \ \frac{Z_{T\backslash S_{i}}}{\text{\ Z}_{T\backslash S_{1}}}(z)\ - \ \left\lbrack \sum_{\text{i\ ϵ\ k}}^{}{\text{γ\ }^{i - 1} \bullet r_{i}(z)}\ \bullet \ \frac{\text{\ Z}_{T\backslash S_{i}}}{\text{\ Z}_{T\backslash S_{1}}}(z) \right\rbrack_{1} - \frac{\text{\ Z}_{T}}{\text{\ Z}_{T\backslash S_{1}}}(z) \bullet W$$

A normalized transformation is performed to reduce one G~1~-scalar multiplication, that is, only (**K+2)**\* G~1~-scalar multiplication and 2 pairings for verifier are needed.

## A New PCS

### FFT-like operations on vectors and polynomials

Define two FFT-like operations to combine and analyze polynomials.

1. $\text{combine}_{t}(\overline{f}):\ {F\lbrack X\rbrack}^{t}\ - > \ F\lbrack X\rbrack$ : given $\overline{f}\ \in \ {F\lbrack X\rbrack}^{t}$, calculate

$$g(x)\ : = \ \sum_{i < t}^{}{f_{i}(X^{t}) \bullet \ X^{i}}$$

If $\overline{f}\ \in \ {F_{< d}\lbrack X\rbrack}^{t}$, then$\ g\ \in \ F_{< d \bullet t}\lbrack X\rbrack$

2. $\text{decombine}_{t}(g):\ F\lbrack X\rbrack\ - > {F\lbrack X\rbrack}^{t}$ : given $g\ \in \ F\lbrack X\rbrack$，a unique $\overline{f}\ \in \ {F\lbrack X\rbrack}^{t}$ will be calculated, satisfying:

$$g(x)\ : = \ \sum_{i < t}^{}{f_{i}(X^{t}) \bullet \ X^{i}}$$

### Notation

Let p ：= \|F\|. for a positive integer t\|(p-1), there exists a unit root w~t~ of order t, which is satisfied with$\ w_{t}^{t}\ = \ 1$, $w_{t}^{i} \neq \ 1$; similarly, there is z, x ϵ F, satisfying z^t^ = x. Now, define a vector:

$\text{root}_{t}(x)\ : = \ {(zw_{t}^{i})}_{i < t}$

Interpreting vectors as poly: for a vector $v\ \in \ F^{t}$ and a poin $x\ \in \ F$, define：

$v(x)\ : = \ \sum_{i < t}^{}{v_{i}x^{i}}$

For the vector $v\ \in \ F^{t},\ S\ \in \ F^{1}$, define:

$v(S)\ : = {(v(x))}_{x \in S}$

### Lemma

For any $x\ \in \ F,\ \ \overline{S}\ \in \ F^{t},\ \overline{\text{\ f\ }} \in \ {F\lbrack X\rbrack}^{t}$, define $\overline{Z}\ : = \ \text{root}_{t}(x),\ \ g\ : = \ \text{combine}_{t}(\overline{f}),\ {\overline{S}}^{'}\ : = \ \overline{S}(\overline{Z})$

Then$\overline{\text{\ f\ }}(x) = \ \overline{S}$ if and only if $g(\overline{Z})\ = \ {\overline{S}}^{'}$ holds

Proof: for $z\ \in \ \overline{Z}$, there is

$g(z)\ : = \ \sum_{i < t}^{}{f_{i}(z^{t}) \bullet \ z^{i}}\ : = \ \sum_{i < t}^{}{f_{i}(x) \bullet \ z^{i}}\ : = \ \overline{f}(x)(z)$

so

$g\left( \overline{Z} \right)\ : = \ \overline{f}(x)(\overline{Z})$

There are also：

${\overline{S}}^{'}\ : = \ \overline{S}(\overline{Z})$

Therefore, according to the theory that there are up to t intersection points between polynomials of order t, we can conclude that $\overline{\text{\ f\ }}(x)\ = \ \overline{S}$ if and only if$\ g(\overline{Z})\ = \ {\overline{S}}^{'}$ holds.

### The new scheme

Choose a constant A\|p-1, let T:={0 \< t =\< A \| t\|A}, S := {x ϵ F \| exits z ϵ F, s.t z^t^ = x}, define a new PCS:

1. gen(d) -- generates SRS：= {\[1\]~1~, ..., \[x^A(d-1)^\]~1~, \[1\]~2~, \[x\]~2~}

2. com (t, $\overline{f}$, srs) -- for $t\ \in \ T,\ \overline{f}\ \in \ {(F_{< d}\lbrack X\rbrack)}^{t}$, let ${g\ : = \ combine}_{t}(\overline{f})$,and then com (t, $\overline{f}$, srs): = \[g(x)\]~1~

3. open -- two scenarios：

a. open(t,cm,x,$\overline{S}$,$\overline{f}$)

​ i. P calculate g
​ ii. P and V calculate ${\overline{Z}}^{'}\ : = \ \text{root}_{t}(x),\ {\overline{S}}^{'}\ : = \ \overline{S}({\overline{Z}}^{i})$

b. The open~shplonk~ (1, cm,${\overline{Z}}^{'},\ {\overline{S}}^{'},\ g$) protocol is implemented between P and V

c. $open(\overline{t},\overline{\text{cm}},\overline{\overline{Z}},\overline{\overline{\overline{S}}};\overline{f})$

​ i. for i < r, P calculates ${g_{i}\ : = \ combine}_{t_{i}}({\overline{f}}_{i}),\ \ Let\ \overline{g}\ : = \ {(g_{i})}_{i < r}$

​ ii. P and V calculate ${\overline{\overline{Z}}}^{'}$(where ${\overline{Z_{i}}}^{'}\ : = \ \bigcup_{x \in {\overline{Z}}_{i}}^{}{\text{root}_{t}(x)}$) and$\ {\overline{\overline{S}}}^{'}$(where $\ {{\overline{S}}}^{'}$ : = ${\ \bigcup_{j \in|\overline{\overline{S_{i}}}|}^{}}$${\overline{S}_{i,j}}$(${root_{t,i}}$(${Z_{i,j}}$)))

​ iii. The $\text{open}\left( 1^{r},\overline{\text{cm}},{\overline{\overline{Z}}}^{'},{\overline{\overline{S}}}^{'};\overline{g} \right)$ protocol is implemented between P and V

## Applied in Fflonk

The table below shows the theoretical complexity comparison between the original PLONK protocol, GWC19, and Fflonk, which applies the above-mentioned new PCS.

| | SRS Size | Prover group operations | Proof length | Verifier group operation |
| ----------------------------------------------- | ------------- | ----------------------- | ------------ | ------------------------ |
| [GWC19](https://eprint.iacr.org/2019/953.pdf) | 3nG~1~, 2G~2~ | 11nG~1~ | 7G~1~, 7F | 16G~1~, 2P |
| [Fflonk](https://eprint.iacr.org/2021/1167.pdf) | 9nG~1~, 2G~2~ | 35nG~1~ | 4G~1~, 15F | 5G~1~, 2P |

*Table* *1 comparison of plonk efficiency for two circuits with n gates*