ECFFT

This library enables fast polynomial arithmetic over any finite field by implementing all the algorithms outlined in Elliptic Curve Fast Fourier Transform (ECFFT) Part I:

There are also some relevant algorithms implemented from ECFFT Part II:

Build FFTrees at compile time

FFTrees are the core data structure that the ECFFT algorithms are built upon. FFTrees can be generated and serialized at compile time and then be deserialized and used at runtime. This can be preferable since generating FFTrees involves a significant amount of computation. While this approach improves runtime it will significantly blow up a binary's size. Generating a FFTree capable of evaluating/interpolating degree $n$ polynomials takes $\mathcal{O}(n\log^3{n})$ - the space complexity of this FFTree is $\mathcal{O}(n)$.

// build.rs

use ark_serialize::CanonicalSerialize;
use ecfft::{secp256k1::Fp, FftreeField};
use std::{env, fs::File, io, path::Path};

fn main() -> io::Result<()> {
    let fftree = Fp::build_fftree(1 << 16).unwrap();
    let out_dir = env::var_os("OUT_DIR").unwrap();
    let path = Path::new(&out_dir).join("fftree");
    fftree.serialize_compressed(File::create(path)?).unwrap();
    println!("cargo:rerun-if-changed=build.rs");
    Ok(())
}

// src/main.rs

use ark_ff::One;
use ark_serialize::CanonicalDeserialize;
use ecfft::{ecfft::FFTree, secp256k1::Fp};
use std::sync::OnceLock;

static FFTREE: OnceLock<FFTree<Fp>> = OnceLock::new();

fn get_fftree() -> &'static FFTree<Fp> {
    const BYTES: &[u8] = include_bytes!(concat!(env!("OUT_DIR"), "/fftree"));
    FFTREE.get_or_init(|| FFTree::deserialize_compressed(BYTES).unwrap())
}

fn main() {
    let fftree = get_fftree();
    // = x^65535 + x^65534 + ... + x + 1
    let poly = vec![Fp::one(); 1 << 16];
    let evals = fftree.enter(&poly);
    let coeffs = fftree.exit(&evals);
    assert_eq!(poly, coeffs);
}

References

• Elliptic Curve Fast Fourier Transform (ECFFT) Part I
• Elliptic Curve Fast Fourier Transform (ECFFT) Part II
• The ECFFT algorithm blogpost by wborgeaud