ECFFT algorithms on the BN254 base field

This crate implements structs and traits for the ECFFT algorithms from the paper Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields by Eli Ben-Sasson, Dan Carmon, Swastik Kopparty and David Levit.

A concrete implementation is provided for the BN254 base field which is not FFT friendly (two-adicity of 1).

Example

fn test_evaluations() {
    type P = Bn254EcFftParameters;
    // ECFFT precomputations.
    let precomputation = P::precompute();
    // Can interpolate polynomials up to degree 2^14.
    let log_n = 14;
    let mut rng = test_rng();
    // Generate a random polynomial.
    let coeffs: Vec<F> = (0..1 << log_n).map(|_| rng.gen()).collect();
    let poly = DensePolynomial { coeffs };
    // Naive evaluations.
    let evals = P::coset()
        .iter()
        .map(|x| poly.evaluate(x))
        .collect::<Vec<_>>();
    // ECFFT evaluations.
    let ecfft_evals = precomputation.evaluate_over_domain(&poly);

    assert_eq!(evals, ecfft_evals);
}

BLS12-381

The base field of the BLS12-381 curve is also supported, for degrees up to 2^15. Credits to Saulius Grigaitis for finding a curve with 2-adicity 15.

Precomputations

The implementation uses precomputations for the coset and isogenies used in the ECFFT. These precomputations are computed in get_params.sage and are stored in the bn254_coset and bn254_isogenies files.

To implement the ECFFT for other fields, similar precomputations should be performed. For example, here is how to generate the precomputations for BLS12-381:

# sage get_params.sage p a b output_filename
sage get_params.sage 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab 0x1800fb41dab7368489a980e14a746abfe7c87588aac25c113301d524b734a5043bbc89dd7d0c5b41de5d348ac2e838c6 0x11c65a0a6e52b8b88366e0b0df28c6804f14f35cb833cb0d918c9e758f044d95777beb965a967af4ef518ad0618a809a bls12-381

Benchmarks

Here is a comparison of the running time for the evaluation of a polynomial of degree n-1 on a domain of n points using 3 algorithms:

• the naive evaluation in O(n^2),
• the classic FFT (on the FFT-friendly BN254 scalar field) in O(n * log n),
• the ECFFT ENTER algorithm in O(n * log^2 n).

References

• Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields by Eli Ben-Sasson, Dan Carmon, Swastik Kopparty and David Levit.
• The ECFFT algorithm.
• ECFFT on the BN254 base field in Rust.