Fflonk - A New Plonk Protocol: Sin7Y Tech Review (13)

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 G1-exp, while for the original PLONK algorithm, Verifier requires 16 or 18 times of G1-exp. Thus, Fflonk significantly improves the performance of 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-1fi), 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 = {t1,t2,…tm})

F(3) => vector of vector of vector in F（TT = {T1,T2,…Tm}）

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

Improved Shplonk

If you read Sin7Y’s previous article on Shplonk, you will know that this one Requires the following:

1. 2*G1 elements, sent from Prover to Verifier
2. Up to (2n+1)*G1-scalar multiplication for prover
3. **(K+3)***G1-scalar multiplication and 2 pairings for verifier

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

1. V sends a random number γ to P

2. P sends W：= [f(X) / ZT(X)]1, where

   

3. V sends open point z to P

4. P sends W` ：= [L(X)/Z T ∖ S 1 ( z ) (X-z)]1, where

   

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

A normalized transformation is performed to reduce one G1-scalar multiplication, that is, only (K+2)* G1-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.

Notation

Let p ：= |F|. for a positive integer t|(p-1), there exists a unit root wt of order t, which is satisfied with

Similarly, there is z, x ϵ F, satisfying zt = x. Now, define a vector:

Interpreting vectors as poly: for a vector v ∈ F t and a point x ∈ F , define：

Lemma

So

There are also：

Therefore, according to the theory that there are up to t intersection points between polynomials of order t, we can conclude that the following holds

The new scheme

Choose the following constant to define a new PCS according to the steps listed below:

1. 

2. 

3. open – two scenarios:

   

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.