Algorithm Details

With a normal KZG commitment, if you want to prove many evaluations of the same polynomial (for example, at every point of a big domain), you must compute a separate quotient polynomial and do a big multi-scalar multiplication for each point. That’s $O(n)$ work per proof, so for $n$ points it’s $O(n^2)$ total.

If all your evaluation points are arranged in a regular pattern — such as the roots of unity (used in FFTs) or in equal-sized cosets — then the matrix that describes “how to combine the SRS powers to form each witness” is Toeplitz (its diagonals are constant).

So instead of doing one MSM per proof, you turn the whole job into a few FFTs and some pointwise group-scalar multiplies.

So the FK20 trick is that reverse the SRS, zero-pad the polynomial coefficients, use FFTs to compute a big Toeplitz convolution once, then slice and FFT again to recover all witnesses at once.

https://github.com/crate-crypto/rust-eth-kzg/tree/master/crates/cryptography/kzg_multi_open/src/fk20

Goal: Compute every KZG witness $\pi_i$ for points $x_i=\omega^i$ in $O(n\log n)$ instead of $O(n^2)$.

Many Points (Structured Domain) — FK20

Idea:

You want a separate proof for many evaluation points arranged in a nice pattern (roots of unity or cosets). FK20 uses FFTs to generate all those proofs at once.

Steps + short explanation:

  1. Reverse and pad SRS: Aligns SRS powers so witness coefficients become a Toeplitz convolution.
  2. Zero-pad polynomial coefficients: Ensures the convolution lands in the upper half after the IFFT.
  3. FFT both vectors (size 2n): Move to frequency domain to make convolution cheap.
  4. Pointwise multiply: Combine SRS and coefficients to get the witness structure.
  5. Inverse FFT (size 2n): Back to time domain with the convolved result.
  6. Take the last n entries: This slice is the valid linear convolution for all witnesses.
  7. Final FFT (size n): Places each witness into the order of the evaluation points.