ECFFT algorithms on various prime-order fields and groups

IMPORTANT DISCLAIMER: This code is provided as is, without warranty of any kind, express or implied. It has not been audited nor fully tested. Use at your own risk.

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.

It is based on the ecfft-bn254 crate from @wborgeaud and extends it in the following ways:

• Support of polynomial with coefficients in a group of prime order r, where the evaluation point are in the prime field of order r:
  • While not explicit in the original paper, it is possible to implement all algorithms in that settings, as the algorithms are linear in the coefficients.
• Concrete implementation for the scalar field of ED25519 and the associated sub-groups of the ED25519 elliptic curve, in addition to the original BN254 and BLS12-381 base fields.
  • None of these fields are FFT-friendly.
  • Use of ECFFT over polynomial with polynomial coefficients being ED25519 points yield even better improvements over the naive implementation because
• Small refactorization to make it easier to add new concrete instantiations using macros

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);
}

Implementations

Each 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 for BN254 base field.

To implement the ECFFT for other fields, similar precomputations should be performed.

Base field of BN254 src/bn254.rs

The base field of the BN254 is supported for degrees up to 2^14.

Base field of BLS12-381 src/bls12_381.ts

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 are generated by:

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

Scalar field of ED25519 src/ed25519sc.rs

The scalar field of ED25519 is supported for degrees up to 2^15.

The curve needed for ECFFT (that has no relation to ED25519) was found by brute-force using find_ec.ipynb.

Then, precomputations are generated by:

# sage get_params.sage p a b output_filename
sage get_params.sage 7237005577332262213973186563042994240857116359379907606001950938285454250989 4392976802491101277119858233748628886670447097743165573553979461609125550624 2641390116504058046593982364855935054624196913202961355189967522292222358134 ed25519sc

This can be used for fast evaluation of polynomials of coefficients in the scalar field (we denote this by ed25519sc) and also in the group of the elliptic curve (we denote this by ed25519pt).

Benchmarks

For the base field of BN254 benches/bn254.rs

See the original ecfft-bn254 crate

For elliptic curve points of ED25519 benches/ec25519sc.rs

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

• Naive: the naive evaluation in O(n^2) over the ECFFT "basic set" with n evaluation points using the Horner algorithm.
• ECFFT: the ECFFT ENTER algorithm in O(n * log^2 n) over the ECFFT "basic set" with n evaluation points.
• Small: the naive evaluation over the n small evaluation points [-n/2,...,n/2] using the Hornet algorithm This is about 256/log n faster than over the ECFFT n evaluation points, because the scalar multiplication of an elliptic curve point with a small scalar evaluation point of log n bits is about 256 / log n faster than when the scalar evaluation point is 256-bit long (assuming a double-and-add scalar multiplication)

There is also a benchmark for the ECFFT EXTEND algorithm alone, which is in O(n * log n). The input of the EXTEND algorithm is n evaluations of a polynomial over the ECFFT "basic set" of n evaluation points and extend it to the ECFFT "basic set" of 2n evaluation points (which include those n initial evaluation points). By definition, this algorithm works only for n up to half of the supported maximum degree.

log n	Naive	ECFFT	Small	Extend
1	315 us	322 us	1.70 us	978 us
2	1.97 ms	3.33 ms	15.8 us	4.66 ms
3	9.14 ms	16.9 ms	104 us	14.0 ms
4	39.2 ms	66.1 ms	584 us	39.0 ms
5	159 ms	211 ms	2.97 ms	98.9 ms
6	653 ms	638 ms	14.5 ms	238 ms
7	2.65 s	1.79 s	69.4 ms	563 ms
8	10.4 s	4.62 s	315 ms	1.27 s
9	42.3 s	11.9 s	1.45 s	2.85 s
10	170 s	29.9 s	6.43 s	6.37 s
11	682 s	72.5 s	28.4 s	14.0 s
12		175 s	123 s	30.7 s
13				68.3 s
14				146 s

There are also benchmarks for polynomials with scalar coefficients. But those are not included above.

Table generated using:

export CRITERION_DIR="target/criterion"
mkdir -p "$CRITERION_DIR/ed25519-poly"
cp -Rp $CRITERION_DIR/ed25519-poly*/* "$CRITERION_DIR/ed25519-poly"
python3 benches_table.py --criterion-target-folder "$CRITERION_DIR/ed25519-poly" --bench-names "pt-ecfftDm-naive,pt-ecfftDm-ecfft,pt-smallDm-hornerSmall,pt-ecfftDm-extend" --short-bench-names "Naive,ECFFT,Small,Extend"

when running the benchmark in a 2-vCPU VM (AMD EPYC 7601, 2.2 GHz, 4GB RAM):

Ubuntu 20.04.3 LTS 
rustc 1.69.0 (84c898d65 2023-04-16)

The code is single-threaded and only uses one core.

Note that the code is not fully optimized. In particular:

• The code does not use optimized algorithms for double-scalar-multiplications (x A + y B), which can significantly increase ECFFT operations (but not Small Horner). Multi-scalar-multiplication from ark-ec uses the Pippenger algorithm which appears slower than using single scalar-multiplication in dimension 2.
• Using https://github.com/dalek-cryptography/ed25519-dalek could lead to performance improvements, especially with simd backend.

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.