These will be a series post about FFT and the math structure behind it. My goal are:
- Going back fundamentally to the polynomial ring and isomorphism.
- Analyse the fft implementations in Plonky3, Gnark-crypto, arkworks
However, let’s start with concrete examples to illustrate the intuition. This post will give an example of 8 points NTT (8 points FFT in finite field).
My personal comments: The first time I knew fft is from signal processing course, transforming a signal from time zone to its frequency zone. Now I see it applies into finite field and transforming polynomial from coefficients to evaluations, quite amazing. It’s not necessary to understand FFT to understand popular zero knowledge proofs, and in papers people don’t talk about FFT. Until I start doing implementations, I realize this part is not easy at all, especially when comes to optimizations. So when people with purely knowledge about zk protocols and talk to me saying, “it’s just FFT”, I feel there is big part underestimated.
Some terminologies
DFT
Discrete Fourier Transform. Transforming a polynomial from its coefficient representation to its evaluation representation at specific points. IDFT is the inverse transform, transforming a polynomial from its evaluations representation to coefficients.
FFT
Fast Fourier Transform. Efficiently computes the DFT.
Variants of FFT:
- Radix-2 FFT: Most common, efficient for sequences whose lengths are powers of 2.
- Radix-3, Radix-4, and Mixed Radix FFTs: Used for sequences of other lengths.
DIT
- DIT FFT: Decimation in Time FFT. Splits the input sequence into even and odd parts recursively and combines them to form the DFT.
- DIF FFT: Decimation in Frequency FFT. Splits the DFT computation based on output frequencies.
NTT
Number Theoretic Transform (NTT) , it is the FFT in finite field. I saw people very often mix these two concepts.
8 points NTT and butterfly, DIT
Assume we have 8th root of unity \(w\), and the multiplicative group it forms \((w^0,w^1,…,w^7)\)
The following properties apply:
\(P(x)=P_e(x^2)+xP_o(x^2)\)
\(w^i=\text{Inv}(w^{i+4})\)
We want to get the following evaluations
$$P(w^0)=P_e(w^0)+w^0P_o(w^0)$$
$$P(w^1)=P_e(w^2)+w^1P_o(w^2)$$
$$P(w^2)=P_e(w^4)+w^2P_o(w^4)$$
$$P(w^3)=P_e(w^6)+w^3P_o(w^6)$$
$$P(w^0)=P_e(w^0)-w^0P_o(w^0)$$
$$P(w^5)=P_e(w^2)-w^2P_o(w^2)$$
$$P(w^6)=P_e(w^4)-w^4P_o(w^4)$$
$$P(w^7)=P_e(w^6)-w^6P_o(w^6)$$
Observed now the 8 evaluations of \(P(x)\) are reduced to 2 polynomial of degree 4: \(P_e(x), P_o(x)\), each polynomial needs to be evaluated in 4 points, i.e., the domain reduced to its half. I write the new evaluations we need to compute in the next round to the right side and continue the reduction:
$$P(w^0)=P_e(w^0)+w^0P_o(w^0) \quad P_e(w^0)=P_{ee}(w^0) +w^0P_{eo}(w^0)$$
$$P(w^1)=P_e(w^2)+w^1P_o(w^2) \quad P_e(w^2)=P_{ee}(w^4) +w^2P_{eo}(w^4) $$
$$P(w^2)=P_e(w^4)+w^2P_o(w^4) \quad P_e(w^4)=P_{ee}(w^0) -w^0P_{eo}(w^0) $$
$$P(w^3)=P_e(w^6)+w^3P_o(w^6) \quad P_e(w^6)=P_{ee}(w^4) -w^2P_{eo}(w^4)$$
$$P(w^0)=P_e(w^0)-w^0P_o(w^0) \quad P_o(w^0)=P_{ee}(w^0) +w^0P_{eo}(w^0)$$
$$P(w^5)=P_e(w^2)-w^2P_o(w^2) \quad P_o(w^2)=P_{ee}(w^4) +w^2P_{eo}(w^4)$$
$$P(w^6)=P_e(w^4)-w^4P_o(w^4) \quad P_o(w^4)=P_{ee}(w^0) -w^0P_{eo}(w^0)$$
$$P(w^7)=P_e(w^6)-w^6P_o(w^6) \quad P_e(w^6)=P_{ee}(w^4) =w^2P_{eo}(w^4)$$
Observe now we reduced to 4 polynomials of degree 2, each of them needs to be evaluated at \(w^0,w^4\)
Continue to recursion, we will reduced to 8 polynomials of degree 1, and they are actually the coefficient of the polynomial, evaluated at \(w^0\). The reduction end, and we going back round by round to compute the evaluations at the beginning, now the butterfly structure is clear.
And the butterfly:
Observe the order of the coefficient on the left side, they are the bit-reverse of canonical order, as illustrated below
