# Fflonk ## Introduction 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 \leftarrow \mathbb{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. ## Background Please read [SHPlonk](/intro/primitives/commitment-scheme/shplonk.md) beforehand! ## Protocol Explanation When performing Radix-2 FFT, $$P(X)$$ is decomposed into even and odd parts: $$ P(X) = P\_E(X^2) + X \cdot P\_O(X^2) $$ Now, consider a simple problem of opening at a single point $$x$$ for multiple polynomials $$P\_0(X), P\_1(X)$$. We define $$P(X)$$ as follows: $$ P(X) = P\_0(X^2) + X \cdot P\_1(X^2) $$ Let $$x = z^2$$, and open $$P(X)$$ at $$\bm{S} = {z, -z}$$: $$ 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 $$P\_0(x)$$ and $$P\_1(x)$$: $$ P\_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 $$\bm{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 $$P\_0(X), \dots, P\_{n-1}(X)$$ into a single polynomial and derive $$\bm{S}$$ from $$x$$. ### Polynomial Combination and Decomposition To merge multiple polynomials into one, we define the following functions: * $$\mathsf{combine}*n(\bm{P}): \mathbb{F}\[X]^n \to \mathbb{F}\[X]$$: This constructs $$P(X)$$ from $$P\_0(X), \dots, P*{n-1}(X)$$: $$ P(X) := \sum\_{i < n} X^i \cdot P\_i(X^n) $$ * $$\mathsf{decompose}*n(P): \mathbb{F}\[X] \rightarrow \mathbb{F}\[X]^n$$: This extracts $$P\_0(X), \dots, P*{n-1}(X)$$ from $$P(X)$$. By definition, we have: $$ \mathsf{decompose}\_n(\mathsf{combine}\_n(\bm{P})) = \bm{P} $$ By the way, $$\mathsf{decompose}\_n(P)$$ is just introduced, but not actually used in this protocol! ### Finding $$\bm{S}$$ from $$x$$ Next, we define a function to derive the set of opening points $$\bm{S}$$ from $$x$$: * $$\mathsf{roots}\_n(x): \mathbb{F} \to \mathbb{F}^n$$: This determines the point set $$\bm{S}$$: $$ \bm{S} := (z\omega^i)\_{i < n} $$ where $$z \in \mathbb{F}$$ satisfies: * $$z^n = x$$ * $$z^i \neq x$$ for $$i < n$$ $$n$$ must be a divisor of $$p - 1$$, and $$\omega$$ is the $$n$$-th root of unity. For example, if $$n = 4$$, meaning $$\bm{P} = {P\_0(X), P\_1(X), P\_2(X), P\_3(X)}$$, and we want to open at $$x$$, we construct: $$ 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: $$ \bm{S} = {z, z\omega, -z, -z\omega } $$ This is because $$\omega^2 = -1$$ since $$\omega^4 = 1$$. Opening at $$\bm{S}$$ gives: $$ 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 = z^4$$ by definition! By computing: $$ P\_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 $$P\_0(x), P\_1(x), P\_2(x), P\_3(x)$$. ### Opening Multiple Polynomials at Multiple Points Consider the same example from SHPlonk: * $$P\_0(X)$$ is opened at $$x\_0$$ with value $$y\_0$$. * $$P\_1(X)$$ is opened at $$x\_0, x\_1$$ with values $$y\_1, y\_2$$. * $$P\_2(X)$$ is opened at $$x\_0, x\_1$$ with values $$y\_3, y\_4$$. Let $$\bm{P} = {P\_0, P\_1, P\_2}$$, then we compute $$P(X) = \mathsf{combine}\_4(\bm{P})$$, determine $$\bm{S}\_0 = \mathsf{roots}\_4(x\_0)$$ and $$\bm{S}\_1 = \mathsf{roots}\_4(x\_1)$$, and perform a batch opening with $$S\_0 \cup S\_1$$. 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 sets** $$s$$: $$1 \le s \le n$$ * $$\mathsf{srs}$$ **size**: $$A \cdot (d + 1) \mathbb{G}\_1, 2\mathbb{G}\_2$$ * **Prover work**: $$O(d)\mathbb{G}\_1, O(s \cdot d \log d) \mathbb{F}$$ * **Proof length**: $$2\mathbb{G}\_1$$ * **Verifier work**: $$O(1)\mathbb{G}\_1, O(n)\mathbb{F}, 2\mathsf{P}$$ Here, $$\mathbb{G}\_i$$ represents scalar multiplication in $$\mathbb{G}\_i$$​, $$\mathbb{F}$$ represents addition or multiplication in $$\mathbb{F}$$, and $$\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 , it says verifying **groth16** and **fflonk** proofs costs are almost identical. TODO([Ryan Kim](mailto:undefined) ): compare the prover performance between groth16 and fflonk. ## References * * --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://fractalyze.gitbook.io/intro/primitives/commitment-scheme/fflonk.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.