A Summary of Fflonk

The Plonk proof system, introduced in 2019, abstracts a complete set of circuit polynomials. Later, custom gate and lookup table are added in Plonk system. These techniques are essentially abstracting more polynomials. Expression ability of these polynomials is stronger, which can abstract the relatively complex calculation process into lower polynomials, thus saving many Plonk gates. With the increasing use of custom gate technology and lookup table, more polynomials and more open points appear in the Plonk system.

For one thing, blockchain systems are very sensitive to the complexity of verification. On the other hand, different polynomial commitment systems have different verification complexity for the number of polynomials and the number of open points. Therefore, it is necessary to compare the polynomial commitment systems.

(1) the verification complexity of KZG commitment is linearly related to the number of polynomials and the number of open points. In the absence of custom gates and lookup tables, the Plonk system uses the KZG commitment to verifying a complexity of 2 bilinear maps and 18 multipoint operations.

(2) the verification complexity of Dan commitment is only related to the number of polynomials, but not the number of open points. In the absence of custom gates and lookup tables, the Plonk system uses the KZG commitment to verifying a complexity of 2 bilinear maps and 16 multipoint operations.

For KZG commitments and Dan commitments, if lookup tables and custom gate techniques are used, the multiple point calculation will be further increased.

(3) Using Fflonk to combine multiple polynomials into one polynomial, and then using Dan commitment. Plonk system requires only 2 bilinear maps and 5 multipoint operations. Besides, with lookup tables and custom gate, the complexity of verification is not increased and it is constant. Therefore, Fflonk technology combined with Dan commitment is the optimal solution in Plonk system.

How it works

Fflonk converts m polynomials f1(X),…,fm(X) opening n points a1,…,an into an equivalently of 1 polynomial F(X) opening m*n points b1,…,b_n*m.

The principle is as follow: we define operators and to group together and decompose polynomials “FFT style”:

Note that these are injective and inverse operations. That is, for any

Notation regarding roots

The following simple lemma is the basis of our scheme.

Then converts 1 polynomials F(X) opening n*m points b1,…,b_n*m. into an equivalently of 1 polynomial L(X) opening 1 points a.

The principle is as follow:

To sum up, we finally simplify to 1 polynomial L(X) opening 1 points a, which can be commit using the KZG commitment system.

For more details, please read the original paper and video, and welcome to discuss here.