FFT Implementations

Overview

The fft module implements Fast Fourier Transform operations for polynomial arithmetic over finite fields. These operations are fundamental to zkSNARK construction, enabling O(n log n) polynomial evaluation and interpolation.

EvaluationDomain

Overview

Represents a multiplicative subgroup of a finite field for FFT operations.

pub struct EvaluationDomain<F: FftField> {
    pub size: u64,
    pub log_size_of_group: u32,
    pub size_as_field_element: F,
    pub size_inv: F,
    pub group_gen: F,
    pub group_gen_inv: F,
    pub generator_inv: F,
}

size

u64

Size of the domain (must be a power of 2)

group_gen

Generator of the multiplicative subgroup

size_inv

Multiplicative inverse of the size

Construction

new

Creates a new evaluation domain.

pub fn new(num_coeffs: usize) -> Result<Self>

num_coeffs

usize

Number of coefficients (will be rounded up to next power of 2)

return

Result<EvaluationDomain<F>>

Evaluation domain of size that is the smallest power of 2 >= num_coeffs

Example:

use snarkvm_algorithms::fft::EvaluationDomain;
use snarkvm_curves::bls12_377::Fr;

// Creates domain of size 256 (next power of 2 after 200)
let domain = EvaluationDomain::<Fr>::new(200)?;
assert_eq!(domain.size(), 256);

FFT Operations

fft

Performs forward FFT on polynomial coefficients.

pub fn fft<T: DomainCoeff<F>>(&self, coeffs: &[T]) -> Vec<T>

coeffs

&[T]

Polynomial coefficients in monomial basis

return

Vec<T>

Evaluations over the domain

Example:

use snarkvm_algorithms::fft::DensePolynomial;

let polynomial = DensePolynomial::from_coefficients_vec(
    vec![Fr::from(1u64), Fr::from(2u64), Fr::from(3u64)]
);

let domain = EvaluationDomain::new(polynomial.coeffs.len())?;
let evaluations = domain.fft(&polynomial.coeffs);

ifft

Performs inverse FFT (interpolation).

pub fn ifft<T: DomainCoeff<F>>(&self, evals: &[T]) -> Vec<T>

evals

&[T]

Evaluations over the domain

return

Vec<T>

Polynomial coefficients in monomial basis

Example:

// Interpolate from evaluations
let coeffs = domain.ifft(&evaluations);
assert_eq!(coeffs, polynomial.coeffs);

fft_in_place

In-place FFT that modifies the input vector.

pub fn fft_in_place<T: DomainCoeff<F>>(&self, coeffs: &mut Vec<T>)

coeffs

&mut Vec<T>

Polynomial coefficients (will be replaced with evaluations)

Example:

let mut data = polynomial.coeffs.clone();
domain.fft_in_place(&mut data);
// data now contains evaluations

ifft_in_place

In-place inverse FFT.

pub fn ifft_in_place<T: DomainCoeff<F>>(&self, evals: &mut Vec<T>)

Coset Operations

coset_fft

Performs FFT over a coset of the domain.

pub fn coset_fft<T: DomainCoeff<F>>(&self, coeffs: &[T]) -> Vec<T>

coeffs

&[T]

Polynomial coefficients

return

Vec<T>

Evaluations over coset g * domain

Example:

// Evaluate over a coset (shifted domain)
let coset_evals = domain.coset_fft(&polynomial.coeffs);

coset_ifft

Interpolates from coset evaluations.

pub fn coset_ifft<T: DomainCoeff<F>>(&self, evals: &[T]) -> Vec<T>

Domain Queries

size

Returns the size of the domain.

pub fn size(&self) -> usize

return

usize

Size of the evaluation domain

elements

Returns all elements of the domain.

pub fn elements(&self) -> Vec<F>

return

Vec<F>

All elements in the domain (powers of the generator)

Example:

let domain = EvaluationDomain::<Fr>::new(8)?;
let elements = domain.elements();
assert_eq!(elements.len(), 8);
// elements = [1, ω, ω², ω³, ω⁴, ω⁵, ω⁶, ω⁷] where ω is the generator

evaluate_vanishing_polynomial

Evaluates the vanishing polynomial Z_H(x) = x^n - 1.

pub fn evaluate_vanishing_polynomial(&self, x: F) -> F

Point to evaluate at

return

Value of vanishing polynomial at x

Example:

let domain = EvaluationDomain::<Fr>::new(8)?;
let point = Fr::from(5u64);
let vanishing = domain.evaluate_vanishing_polynomial(point);
// vanishing = point^8 - 1

DensePolynomial

Overview

Polynomial stored in coefficient form.

pub struct DensePolynomial<F: Field> {
    pub coeffs: Vec<F>,
}

coeffs

Vec<F>

Coefficients in ascending degree order (coeffs[i] is coefficient of x^i)

Construction

from_coefficients_vec

Creates polynomial from coefficient vector.

pub fn from_coefficients_vec(coeffs: Vec<F>) -> Self

coeffs

Vec<F>

Polynomial coefficients

return

DensePolynomial<F>

Polynomial with given coefficients (trailing zeros removed)

Example:

use snarkvm_algorithms::fft::DensePolynomial;

// p(x) = 1 + 2x + 3x²
let poly = DensePolynomial::from_coefficients_vec(
    vec![Fr::from(1u64), Fr::from(2u64), Fr::from(3u64)]
);

zero

Creates the zero polynomial.

pub fn zero() -> Self

return

DensePolynomial<F>

The zero polynomial

rand

Generates a random polynomial.

pub fn rand<R: Rng>(degree: usize, rng: &mut R) -> Self

degree

usize

Degree of the polynomial

rng

&mut R

Random number generator

return

DensePolynomial<F>

Random polynomial of specified degree

Example:

use snarkvm_utilities::rand::TestRng;

let mut rng = TestRng::default();
let poly = DensePolynomial::rand(100, &mut rng);
assert_eq!(poly.degree(), 100);

Polynomial Operations

degree

Returns the degree of the polynomial.

pub fn degree(&self) -> usize

return

usize

Degree of the polynomial (0 for zero polynomial)

evaluate

Evaluates the polynomial at a point.

pub fn evaluate(&self, point: F) -> F

point

Point to evaluate at

return

Value of polynomial at point (using Horner’s method)

Example:

let point = Fr::from(5u64);
let value = poly.evaluate(point);
// For p(x) = 1 + 2x + 3x², p(5) = 1 + 10 + 75 = 86

divide_by_vanishing_poly

Divides by the vanishing polynomial of a domain.

pub fn divide_by_vanishing_poly(&self, domain: &EvaluationDomain<F>) -> Result<DensePolynomial<F>>

domain

&EvaluationDomain<F>

The evaluation domain

return

Result<DensePolynomial<F>>

Quotient polynomial p(x) / (x^n - 1)

Example:

let domain = EvaluationDomain::new(8)?;
let quotient = polynomial.divide_by_vanishing_poly(&domain)?;

Arithmetic Operations

DensePolynomial implements standard arithmetic:

// Addition
let sum = &poly1 + &poly2;

// Subtraction
let diff = &poly1 - &poly2;

// Multiplication
let product = &poly1 * &poly2;

// Division
let quotient = &poly1 / &poly2;

// Scalar multiplication
let scaled = &poly * scalar;

SparsePolynomial

Overview

Polynomial with few non-zero coefficients.

pub struct SparsePolynomial<F: Field> {
    coeffs: Vec<(usize, F)>,  // (degree, coefficient) pairs
}

Construction

from_coefficients_vec

Creates sparse polynomial from (degree, coefficient) pairs.

pub fn from_coefficients_vec(coeffs: Vec<(usize, F)>) -> Self

coeffs

Vec<(usize, F)>

Vector of (degree, coefficient) pairs

return

SparsePolynomial<F>

Sparse polynomial

Example:

use snarkvm_algorithms::fft::SparsePolynomial;

// p(x) = 3x^5 + 7x^100
let sparse = SparsePolynomial::from_coefficients_vec(vec![
    (5, Fr::from(3u64)),
    (100, Fr::from(7u64)),
]);

Methods

degree

Returns the degree.

pub fn degree(&self) -> usize

evaluate

Evaluates at a point.

pub fn evaluate(&self, point: F) -> F

Evaluations

Overview

Polynomial represented in evaluation form (Lagrange basis).

pub struct Evaluations<F: FftField> {
    pub evaluations: Vec<F>,
    pub domain: EvaluationDomain<F>,
}

evaluations

Vec<F>

Polynomial evaluations over the domain

domain

EvaluationDomain<F>

The evaluation domain

Construction

from_vec_and_domain

Creates Evaluations from vector and domain.

pub fn from_vec_and_domain(evaluations: Vec<F>, domain: EvaluationDomain<F>) -> Self

evaluations

Vec<F>

Evaluation values

domain

EvaluationDomain<F>

Evaluation domain

return

Evaluations<F>

Polynomial in evaluation form

Example:

use snarkvm_algorithms::fft::Evaluations;

let domain = EvaluationDomain::new(8)?;
let evals = Evaluations::from_vec_and_domain(
    vec![Fr::from(1u64); 8],
    domain,
);

Methods

interpolate

Converts to coefficient form.

pub fn interpolate(&self) -> DensePolynomial<F>

return

DensePolynomial<F>

Polynomial in coefficient form

Example:

let polynomial = evals.interpolate();

interpolate_by_ref

Interpolates without consuming.

pub fn interpolate_by_ref(&self) -> DensePolynomial<F>

DomainCoeff Trait

Defines types that can be FFT-transformed.

pub trait DomainCoeff<F: FftField>:
    Copy + Send + Sync
    + Add<Output = Self>
    + Sub<Output = Self>
    + AddAssign
    + SubAssign
    + Zero
    + MulAssign<F>
{}

Automatically implemented for field elements and extension fields.

Polynomial Trait

Common interface for polynomial types.

pub enum Polynomial<'a, F: Field> {
    Dense(&'a DensePolynomial<F>),
    Sparse(&'a SparsePolynomial<F>),
}

Complete Example

use snarkvm_algorithms::fft::{
    DensePolynomial,
    EvaluationDomain,
    Evaluations,
};
use snarkvm_curves::bls12_377::Fr;

fn main() -> Result<()> {
    // Create a polynomial p(x) = 1 + 2x + 3x²
    let poly = DensePolynomial::from_coefficients_vec(vec![
        Fr::from(1u64),
        Fr::from(2u64),
        Fr::from(3u64),
    ]);
    
    // Create evaluation domain
    let domain = EvaluationDomain::new(poly.coeffs.len())?;
    println!("Domain size: {}", domain.size());
    
    // Forward FFT: coefficients -> evaluations
    let evaluations = domain.fft(&poly.coeffs);
    println!("Evaluations: {} elements", evaluations.len());
    
    // Verify: evaluate manually at domain points
    let domain_elements = domain.elements();
    for (i, &element) in domain_elements.iter().enumerate() {
        let manual_eval = poly.evaluate(element);
        assert_eq!(evaluations[i], manual_eval);
    }
    
    // Inverse FFT: evaluations -> coefficients
    let recovered = domain.ifft(&evaluations);
    assert_eq!(recovered, poly.coeffs);
    
    // Work with Evaluations wrapper
    let evals = Evaluations::from_vec_and_domain(evaluations, domain);
    let recovered_poly = evals.interpolate();
    assert_eq!(recovered_poly, poly);
    
    // Coset FFT for non-domain points
    let coset_evals = domain.coset_fft(&poly.coeffs);
    let recovered_coset = domain.coset_ifft(&coset_evals);
    assert_eq!(recovered_coset, poly.coeffs);
    
    Ok(())
}

Performance Considerations

Parallelization

FFT operations are parallelized using Rayon:

// Automatically uses all available cores
let evaluations = domain.fft(&coeffs);

In-Place Operations

Use in-place variants to avoid allocations:

let mut data = coeffs.clone();
domain.fft_in_place(&mut data);
// data now contains evaluations, no extra allocation

Domain Size Selection

Choose domain sizes that are powers of 2:

// Good: exact power of 2
let domain = EvaluationDomain::new(256)?;

// Still good: rounds up to next power of 2 (256)
let domain = EvaluationDomain::new(200)?;

Common Patterns

Quotient Polynomial Computation

// Compute p(x) / Z_H(x) where Z_H(x) is the vanishing polynomial
let domain = EvaluationDomain::new(circuit_size)?;
let quotient = polynomial.divide_by_vanishing_poly(&domain)?;

Lagrange Interpolation

// Interpolate polynomial from evaluations at domain points
let domain = EvaluationDomain::new(evaluations.len())?;
let evals = Evaluations::from_vec_and_domain(evaluations, domain);
let polynomial = evals.interpolate();

Overview

Algorithms

Console

Circuit

Synthesizer

Ledger

Utilities

Documentation Index

​Overview

​EvaluationDomain

​Overview

​Construction

​new

​FFT Operations

​fft

​ifft

​fft_in_place

​ifft_in_place

​Coset Operations

​coset_fft

​coset_ifft

​Domain Queries

​size

​elements

​evaluate_vanishing_polynomial

​DensePolynomial

​Overview

​Construction

​from_coefficients_vec

​zero

​rand

​Polynomial Operations

​degree

​evaluate

​divide_by_vanishing_poly

​Arithmetic Operations

​SparsePolynomial

​Overview

​Construction

​from_coefficients_vec

​Methods

​degree

​evaluate

​Evaluations

​Overview

​Construction

​from_vec_and_domain

​Methods

​interpolate

​interpolate_by_ref

​DomainCoeff Trait

​Polynomial Trait

​Complete Example

​Performance Considerations

​Parallelization

​In-Place Operations

​Domain Size Selection

​Common Patterns

​Quotient Polynomial Computation

​Lagrange Interpolation

​See Also

Build docs developers (and LLMs) love

Overview

EvaluationDomain

Overview

Construction

new

FFT Operations

fft

ifft

fft_in_place

ifft_in_place

Coset Operations

coset_fft

coset_ifft

Domain Queries

size

elements

evaluate_vanishing_polynomial

DensePolynomial

Overview

Construction

from_coefficients_vec

zero

rand

Polynomial Operations

degree

evaluate

divide_by_vanishing_poly

Arithmetic Operations

SparsePolynomial

Overview

Construction

from_coefficients_vec

Methods

degree

evaluate

Evaluations

Overview

Construction

from_vec_and_domain

Methods

interpolate

interpolate_by_ref

DomainCoeff Trait

Polynomial Trait

Complete Example

Performance Considerations

Parallelization

In-Place Operations

Domain Size Selection

Common Patterns

Quotient Polynomial Computation

Lagrange Interpolation

See Also