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: 2*G1 elements, sent from Prover to Verifier Up to (2n+1)*G1-scalar multiplication for prover **(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: V sends a random number γ to P P sends W：= [f(X) / ZT(X)]1, where V sends open point z to P P sends W` ：= [L(X)/Z T ∖ S 1 ( z ) (X-z)]1, where V verifies whether the equation e (F+ zW , [x]2) holds, where , [1]2) = e(W 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: 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.

Scalar

Lookup Argument in Halo2 - Sin7Y Tech Review (14)

AppliedZKP zkEVM Circuit Code: A Guide

Nominated for 2022 - HackerNoon Contributor of the Year - Optimization

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Architecture

Nominated for 2022 - HackerNoon Contributor of the Year - Blockchain

Too Long; Didn't Read

Make resilience your competitive advantage

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

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

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

A Study on Parallel Execution: Everything You Need to Know

(1/100) Crypto Countdown: Golem

A Research Report on the Trader $JOE DeFi Platform

07/03/2018: Biggest Stories in the Cryptosphere

05/02/2018: Biggest Stories in the Cryptosphere

A Study on Parallel Execution: Everything You Need to Know

(1/100) Crypto Countdown: Golem

A Research Report on the Trader $JOE DeFi Platform

07/03/2018: Biggest Stories in the Cryptosphere

05/02/2018: Biggest Stories in the Cryptosphere

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps