Fflonk

Presentation: https://www.youtube.com/watch?v=E5oLEqbx6F4

Introduction

When opening at a single point for nn polynomials, the common technique is to use a random linear combination, which requires n1n - 1 scalar multiplications. Eliminating these operations could lead to more efficient verification. Meanwhile, in SHPlonk, when opening KZG in batch, the verifier randomly samples a point zFz \leftarrow \mathbb{F} and constructs a vanishing polynomial L(X)L(X) for this point. This method allows an opening at tt points to be converted into an opening at a single point. However, the verifier still needs to perform O(n)O(n) computations, and reducing this cost could improve verification efficiency.

A natural question arises: can "the problem of opening at a single point for multiple polynomials" be transformed into "the problem of opening at multiple points for a single polynomial"? If possible, then leveraging SHPlonk’s method could enable more efficient batch opening for the verifier.

Background

Please read SHPlonk beforehand!

Protocol Explanation

When performing Radix-2 FFT, P(X)P(X) is decomposed into even and odd parts:

P(X)=PE(X2)+XPO(X2)P(X) = P_E(X^2) + X \cdot P_O(X^2)

Now, consider a simple problem of opening at a single point xx for multiple polynomials P0(X),P1(X)P_0(X), P_1(X). We define P(X)P(X) as follows:

P(X)=P0(X2)+XP1(X2)P(X) = P_0(X^2) + X \cdot P_1(X^2)

Let x=z2x = z^2, and open P(X)P(X) at S={z,z}\bm{S} = \{z, -z\}:

P(z)=P0(x)+zP1(x)P(z)=P0(x)zP1(x)P(z) = P_0(x) + z \cdot P_1(x) \\ P(-z) = P_0(x) - z \cdot P_1(x)

By performing the following computations, we can retrieve P0(x)P_0(x) and P1(x)P_1(x):

P0(x)=P(z)+P(z)2P1(x)=P(z)P(z)2zP_0(x) = \frac{P(z) + P(-z)}{2} \\ P_1(x) = \frac{P(z) - P(-z)}{2z}

Thus, the original problem is transformed into opening at multiple points S={z,z}\bm{S} = \{z, -z\} for a single polynomial P(X)P(X), allowing us to apply SHPlonk’s batch opening method.

To generalize this approach to nn polynomials, we need a way to combine P0(X),,Pn1(X)P_0(X), \dots, P_{n-1}(X) into a single polynomial and derive S\bm{S} from xx.

Polynomial Combination and Decomposition

To merge multiple polynomials into one, we define the following functions:

  • combinen(P):F[X]nF[X]\mathsf{combine}_n(\bm{P}): \mathbb{F}[X]^n \to \mathbb{F}[X]: This constructs P(X)P(X) from P0(X),,Pn1(X)P_0(X), \dots, P_{n-1}(X):

P(X):=i<nXiPi(Xn)P(X) := \sum_{i < n} X^i \cdot P_i(X^n)
  • decomposen(P):F[X]F[X]n\mathsf{decompose}_n(P): \mathbb{F}[X] \rightarrow \mathbb{F}[X]^n: This extracts P0(X),,Pn1(X)P_0(X), \dots, P_{n-1}(X) from P(X)P(X).

By definition, we have:

decomposen(combinen(P))=P\mathsf{decompose}_n(\mathsf{combine}_n(\bm{P})) = \bm{P}

By the way, decomposen(P)\mathsf{decompose}_n(P) is just introduced, but not actually used in this protocol!

Finding S\bm{S} from xx

Next, we define a function to derive the set of opening points S\bm{S} from xx:

  • rootsn(x):FFn\mathsf{roots}_n(x): \mathbb{F} \to \mathbb{F}^n: This determines the point set S\bm{S}:

S:=(zωi)i<n\bm{S} := (z\omega^i)_{i < n}

where zFz \in \mathbb{F} satisfies:

  • zn=xz^n = x

  • zixz^i \neq x for i<ni < n

nn must be a divisor of p1p - 1, and ω\omega is the nn-th root of unity.

For example, if n=4n = 4, meaning P={P0(X),P1(X),P2(X),P3(X)}\bm{P} = \{P_0(X), P_1(X), P_2(X), P_3(X)\}, and we want to open at xx, we construct:

P(X)=P0(X4)+XP1(X4)+X2P2(X4)+X3P3(X4)P(X) = P_0(X^4) + X \cdot P_1(X^4) + X^2 \cdot P_2(X^4) + X^3 \cdot P_3(X^4)

The corresponding root set is:

S={z,zω,z,zω}\bm{S} = \{z, z\omega, -z, -z\omega \}

This is because ω2=1\omega^2 = -1 since ω4=1\omega^4 = 1.

Opening at S\bm{S} gives:

P(z)=P0(x)+zP1(x)+z2P2(x)+z3P3(x)P(zω)=P0(x)+zωP1(x)z2P2(x)z3ωP3(x)P(z)=P0(x)zP1(x)+z2P2(x)z3P3(x)P(zω)=P0(x)zωP1(x)z2P2(x)+z3ωP3(x)P(z) = P_0(x) + z \cdot P_1(x) + z^2 \cdot P_2(x) + z^3 \cdot P_3(x) \\P(z\omega) = P_0(x) + z\omega \cdot P_1(x) - z^2 \cdot P_2(x) - z^3\omega \cdot P_3(x) \\P(-z) = P_0(x) - z \cdot P_1(x) + z^2 \cdot P_2(x) - z^3 \cdot P_3(x) \\P(-z\omega) = P_0(x) - z\omega \cdot P_1(x) - z^2 \cdot P_2(x) + z^3\omega \cdot P_3(x) \\

Remember that x=z4x = z^4 by definition!

By computing:

P0(x)=P(z)+P(zω)+P(z)+P(zω)4P1(x)=P(z)+P(zω)P(z)P(zω)4zP2(x)=P(z)P(zω)+P(z)P(zω)4z2P3(x)=P(z)P(zω)P(z)+P(zω)4z3P_0(x) = \frac{P(z) + P(z\omega) + P(-z) + P(-z\omega)}{4} \\ P_1(x) = \frac{P(z) + P(z\omega) - P(-z) - P(-z\omega)}{4z} \\ P_2(x) = \frac{P(z) - P(z\omega) + P(-z) - P(-z\omega)}{4z^2} \\ P_3(x) = \frac{P(z) - P(z\omega) - P(-z) + P(-z\omega)}{4z^3} \\

we can recover P0(x),P1(x),P2(x),P3(x)P_0(x), P_1(x), P_2(x), P_3(x).

Opening Multiple Polynomials at Multiple Points

Consider the same example from SHPlonk:

  • P0(X)P_0(X) is opened at x0x_0 with value y0y_0.

  • P1(X)P_1(X) is opened at x0,x1x_0, x_1 with values y1,y2y_1, y_2.

  • P2(X)P_2(X) is opened at x0,x1x_0, x_1 with values y3,y4y_3, y_4.

Let P={P0,P1,P2}\bm{P} = \{P_0, P_1, P_2\}, then we compute P(X)=combine4(P)P(X) = \mathsf{combine}_4(\bm{P}), determine S0=roots4(x0)\bm{S}_0 = \mathsf{roots}_4(x_0) and S1=roots4(x1)\bm{S}_1 = \mathsf{roots}_4(x_1), and perform a batch opening with S0S1S_0 \cup S_1.

Let's set the maximum allowable number of polynomials as AA. Then, if there are n<An < A polynomials of degree dd, and each polynomial is opened at tt points, the computational costs are as follows:

  • The number of opening sets ss: 1sn1 \le s \le n

  • srs\mathsf{srs} size: A(d+1)G1,2G2A \cdot (d + 1) \mathbb{G}_1, 2\mathbb{G}_2

  • Prover work: O(d)G1,O(sdlogd)FO(d)\mathbb{G}_1, O(s \cdot d \log d) \mathbb{F}

  • Proof length: 2G12\mathbb{G}_1

  • Verifier work: O(1)G1,O(n)F,2PO(1)\mathbb{G}_1, O(n)\mathbb{F}, 2\mathsf{P}

Here, Gi\mathbb{G}_i represents scalar multiplication in Gi\mathbb{G}_i​, F\mathbb{F} represents addition or multiplication in F\mathbb{F}, and P\mathsf{P} denotes a pairing operation.

Conclusion

Fflonk further optimizes batch opening protocols using a trick inspired by FFT, (that's why the name starts with ff, which denotes "fast fourier") reducing verifier work while maintaining prover efficiency and proof size. This makes it particularly well-suited for large-scale applications where minimizing verifier overhead is critical. In https://ethresear.ch/t/on-the-gas-efficiency-of-the-whir-polynomial-commitment-scheme/21301, it says verifying groth16 and fflonk proofs costs are almost identical.

TODO(chokobole): compare the prover performance between groth16 and fflonk.

References

Last updated