Why do we use FFT and IFFT in PLONK?

In the PLONK (Permutation-based zk-SNARK) protocol, Fast Fourier Transform (FFT) and Inverse Fast Fourier Transform (IFFT) are used as crucial components for efficient polynomial evaluation and interpolation.

Lagrange and Monomial Basis

The Lagrange Basis is a method of representing polynomials using a set of basis polynomials known as Lagrange polynomials. These basis polynomials are constructed such that each polynomial evaluates to 1 at one specific point and 0 at all other points. The Lagrange Basis provides a unique polynomial representation for a given set of interpolation points.

On the other hand, the Monomial Basis represents polynomials using a set of monomials, where each monomial is a power of the variable. For example, the monomial basis for a polynomial of degree 3 would include terms like x^0, x^1, x^2, and x^3. The Monomial Basis allows for a more straightforward and intuitive representation of polynomials.

The main difference between the two lies in their representation and computation properties. The Lagrange Basis is often used for polynomial interpolation, where the polynomial needs to pass through specific points. It ensures a unique representation and is useful for evaluating the polynomial at arbitrary points. However, computations in the Lagrange Basis can be computationally intensive due to the need for interpolation calculations.

Conversion

By converting polynomials to the coefficient domain using the IFFT, PLONK enables efficient polynomial manipulations and computations.

The IFFT takes the evaluated polynomial values and transforms them back into the coefficient representation. This allows for efficient operations and computations on the coefficients of the polynomials.

Moreover, the IFFT helps in achieving a key property known as the "low-degree extension." This property allows for extending a polynomial with a small degree to a polynomial with a higher degree, while preserving certain evaluation values.

By leveraging the IFFT and working in the coefficient domain, PLONK achieves efficient and secure computation of custom constraints, which are essential for building complex zk-SNARK circuits. The use of IFFT ensures that the protocol can handle large-scale computations while maintaining computational efficiency and security.