When opening at a single point for n polynomials, the common technique is to use a random linear combination, which requires n−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 z←F and constructs a vanishing polynomial L(X) for this point. This method allows an opening at t points to be converted into an opening at a single point. However, the verifier still needs to perform 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.
When performing Radix-2 FFT, P(X) is decomposed into even and odd parts:
P(X)=PE(X2)+X⋅PO(X2)
Now, consider a simple problem of opening at a single point x for multiple polynomials P0(X),P1(X). We define P(X) as follows:
P(X)=P0(X2)+X⋅P1(X2)
Let x=z2, and open P(X) at S={z,−z}:
P(z)=P0(x)+z⋅P1(x)P(−z)=P0(x)−z⋅P1(x)
By performing the following computations, we can retrieve P0(x) and P1(x):
P0(x)=2P(z)+P(−z)P1(x)=2zP(z)−P(−z)
Thus, the original problem is transformed into opening at multiple points S={z,−z} for a single polynomial P(X), allowing us to apply SHPlonk’s batch opening method.
To generalize this approach to n polynomials, we need a way to combine P0(X),…,Pn−1(X) into a single polynomial and derive S from x.
Polynomial Combination and Decomposition
To merge multiple polynomials into one, we define the following functions:
combinen(P):F[X]n→F[X]: This constructs P(X) from P0(X),…,Pn−1(X):
P(X):=i<n∑Xi⋅Pi(Xn)
decomposen(P):F[X]→F[X]n: This extracts P0(X),…,Pn−1(X) from P(X).
By definition, we have:
decomposen(combinen(P))=P
By the way, decomposen(P) is just introduced, but not actually used in this protocol!
Finding S from x
Next, we define a function to derive the set of opening points S from x:
rootsn(x):F→Fn: This determines the point set S:
S:=(zωi)i<n
where z∈F satisfies:
zn=x
zi=x for i<n
n must be a divisor of p−1, and ω is the n-th root of unity.
For example, if n=4, meaning P={P0(X),P1(X),P2(X),P3(X)}, and we want to open at x, we construct:
Let P={P0,P1,P2}, then we compute P(X)=combine4(P), determine S0=roots4(x0) and S1=roots4(x1), and perform a batch opening with S0∪S1.
Let's set the maximum allowable number of polynomials as A. Then, if there are n<A polynomials of degree d, and each polynomial is opened at t points, the computational costs are as follows:
The number of opening setss: 1≤s≤n
srs size: A⋅(d+1)G1,2G2
Prover work: O(d)G1,O(s⋅dlogd)F
Proof length: 2G1
Verifier work: O(1)G1,O(n)F,2P
Here, Gi represents scalar multiplication in Gi, F represents addition or multiplication in F, and 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.