Circle Fast-Fourier Transform (CircleFFT)

This folder contains all the necessary tools to work with the circle FFT, which is a suitable way of performing an analogue of the radix-2 FFT algorithm over fields which are not smooth. We say a finite field is smooth if the size of the multiplicative group of the field is divisible by a sufficiently high power of 2. In the case of $\mathbb{Z}_p$, the previous sentence indicates that $p - 1 = 2^m c$, where $m$ is sufficiently large (for example, $2^{25}$), ensuring we can use the radix-2 Cooley-Tuckey algorithm for the FFT with vectors of size up to $2^{25}$.

This mathematical structure provides several advantages for computational operations. It leads to a variant of STARKs called Circle STARKs. For an introduction to circle STARKs, we recommend our blog or Vitalik's explanation

Implementation Content

This module includes the following components:

CirclePoint: Represents a point in the Circle group.
CFFT (Circle Fast Fourier Transform): Algorithm for evaluating and interpolating polynomials in the Circle group.
Cosets: Implementation of cosets of the Circle group.
Polynomials: Evaluation and interpolation of bivariable polynomials on the standard coset.
Twiddles: Factors used in the CFFT algorithm.

What is the Circle Group?

Given a finite field $\mathbb{F}$, the Circle Group over $\mathbb{F}$ consists of all the points $(x, y)$ such that $x, y \in \mathbb{F}$ and $x^2 + y^2 = 1$, with the following group operation:

$$(a, b) + (c, d) = (a \cdot c - b \cdot d, a \cdot d + b \cdot c)$$

Some properties that are useful to have in mind:

The neutral element is $(1, 0)$.
The inverse of $(x, y)$ is its conjugate $(x, -y)$.

Circle Group implementation

You can find our implementation of the Circle Group in point.rs.

To implement CirclePoint for a field, you have to first implement HasCircleParams for that field. For example, in point.rs you can find our implementation for Mersenne-31 Prime Field.

impl HasCircleParams<Mersenne31Field> for Mersenne31Field {
    type FE = FieldElement<Mersenne31Field>;

    const CIRCLE_GENERATOR_X: Self::FE = Self::FE::const_from_raw(2);

    const CIRCLE_GENERATOR_Y: Self::FE = Self::FE::const_from_raw(1268011823);

    /// ORDER = 2^31
    const ORDER: u128 = 2147483648;
}

What is a Coset?

Given $g_n$ a generator of a subgroup of the circle of size $n = 2^k$ for some $k \in \mathbb{N}$, and given another point of the circle $p$ (usually called shift), the Coset $p + \langle g_n \rangle$ is the set that results of taking every point in $\langle g_n \rangle$ (the subgroup generated by $g_n$) and adding $p$ to them.

For example, if $\langle g_4 \rangle = { p_1, p_2, p_3, p_4 }$, then $p + \langle g_4 \rangle = { p + p_1, p + p_2, p + p_3, p+ p_4 }$

Standard Coset

The CFFT algorithm uses what we called a Standard Coset. A Standard Coset is a Coset of the form $g_{2n} + \langle g_n \rangle$. In other worlds, it is a coset of the subgroup of size $n = 2^k$ with the shift $g_{2n}$ (the generator of the subgroup of size $2n = 2^{k+1}$).

In coset.rs you will find our implementation for the Circle Group over the Mersenne-31 Prime Field. You can use it in the following way:

use lambdaworks_math::circle::cosets::Coset;
use lambdaworks_math::circle::point::CirclePoint;
use lambdaworks_math::field::fields::mersenne31::field::Mersenne31Field;

// Create a standard coset of size 2^k
let log_2_size = 3; // k = 3, for a coset of size 8.
let coset = Coset::new_standard(log_2_size);

// Get the coset generator
let generator = coset.get_generator();

// Get all elements of the coset
let elements = coset.get_coset_points();

Implementation Details for CFFT

Overview

The Circle Fast Fourier Transform (CFFT) is used to evaluate and interpolate polynomials efficiently over points in a standard coset of the Circle group. The implementation uses an in-place FFT algorithm operating on slices whose length is a power of two.

In-Place FFT Computation

The cfft function an input of length $2^n$ and computes an algorithm of $n$ layers. In each layer $i$:

The input is divided into chunks of size $2^{i+1}$.
Butterfly operations are applied to pairs of elements within each chunk using precomputed twiddle factors.

Twiddle Factors

Purpose: Twiddle factors are needed in the butterfly operation used in the CFFT.
Computation: They are computed by the get_twiddles function that takes as input a coset of the Circle group.
Configuration: The twiddles are different depending on whether we want to use them for a CFFT (needed to evaluate a polynomial) or for a ICFFT (needed to interpolate a polynomial).

Bit-Reverse Permutation

Before applying the FFT:

The input coefficients must be reordered into bit-reversed order.
This reordering, performed by a helper function ( in_place_bit_reverse_permute), is essential for the correctness of the in-place FFT computation.

Result Ordering

After the FFT:

The computed evaluations are not in natural order.
The helper function order_cfft_result_naive rearranges these evaluations into the natural order, aligning them with the original order of the coset points.

Inverse FFT (ICFFT)

Process: The inverse FFT (icfft) mirrors the forward FFT's layered approach, but with operations that invert the transformation. It is used for polynomial interpolation, instead of evaluation.
Scaling: After processing, the result is scaled by the inverse of the input length to recover the original polynomial coefficients.

Design Considerations and Optimizations

Modularity: Separating FFT computation from data reordering enhances the maintainability and clarity of the implementation.
Optimization Potential: Although the current ordering functions use a straightforward (naive) approach, there is room for further optimization (e.g., in-place value swapping).
Balance: The design strikes a balance between code clarity and performance, making it easier to understand and improve in the future.

API Usage

Working with Circle group points

use lambdaworks_math::field::{
    element::FieldElement,
    fields::mersenne31::field::Mersenne31Field,
};
use lambdaworks_math::circle::point::CirclePoint;

// Create a valid point in the Circle group, i.e a point (x, y) 
// that satisfies x^2 + y^2 = 1
let x = FieldElement::<Mersenne31Field>::zero();
let y = FieldElement::<Mersenne31Field>::one();
let point = CirclePoint::new(x, y).unwrap();

// Get the neutral element (identity) of the group.
// That is the point (1, 0).
let zero = CirclePoint::<Mersenne31Field>::zero();

// Group operations
let point1 = CirclePoint::<Mersenne31Field>::GENERATOR;
let point2 = point1.double(); // Double a point
let point3 = point1 + point2; // Add two points
let point4 = point1 * 8; // Scalar multiplication

Polynomial evaluation and interpolation using CFFT

use lambdaworks_math::field::{
    element::FieldElement,
    fields::mersenne31::field::Mersenne31Field,
};
use lambdaworks_math::circle::polynomial::{evaluate_cfft, interpolate_cfft};

// Define polynomial coefficients
let coefficients: Vec<FieldElement<Mersenne31Field>> = (0..8)
    .map(|i| FieldElement::<Mersenne31Field>::from(i as u64))
    .collect();

// Evaluate the polynomial at Circle group points
let evaluations = evaluate_cfft(coefficients.clone());

// Interpolate to recover the coefficients
let recovered_coefficients = interpolate_cfft(evaluations);

Using CFFT directly

use lambdaworks_math::field::{
    element::FieldElement,
    fields::mersenne31::field::Mersenne31Field,
};
use lambdaworks_math::circle::{
    cfft::{cfft, icfft},
    cosets::Coset,
    twiddles::{get_twiddles, TwiddlesConfig},
};
use lambdaworks_math::fft::cpu::bit_reversing::in_place_bit_reverse_permute;

// Prepare data (must be a power of 2 in length)
let mut data: Vec<FieldElement<Mersenne31Field>> = (0..8)
    .map(|i| FieldElement::<Mersenne31Field>::from(i as u64))
    .collect();

// Prepare for CFFT
let domain_log_2_size = data.len().trailing_zeros();
let coset = Coset::new_standard(domain_log_2_size);
let config = TwiddlesConfig::Evaluation;
let twiddles = get_twiddles(coset.clone(), config);

// Bit-reverse permutation (required before CFFT)
in_place_bit_reverse_permute(&mut data);

// Perform CFFT in-place
cfft(&mut data, twiddles);

// For inverse CFFT
let inverse_config = TwiddlesConfig::Interpolation;
let inverse_twiddles = get_twiddles(coset, inverse_config);

// Perform inverse CFFT
icfft(&mut data, inverse_twiddles);

References

An Introduction to Circle STARKs - LambdaClass Blog
Vitalik's Explanation of Circle STARKs
Circle FFT Paper
Anatomy of a STARK - Detailed explanation of STARKs
STARKs, Part I: Proofs with Polynomials - Vitalik Buterin's series on STARKs

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Files

README.md

README.md

Circle Fast-Fourier Transform (CircleFFT)

Implementation Content

What is the Circle Group?

Circle Group implementation

What is a Coset?

Standard Coset

Implementation Details for CFFT

Overview

In-Place FFT Computation

Twiddle Factors

Bit-Reverse Permutation

Result Ordering

Inverse FFT (ICFFT)

Design Considerations and Optimizations

API Usage

Working with Circle group points

Polynomial evaluation and interpolation using CFFT

Using CFFT directly

References

Files

README.md

Latest commit

History

README.md

File metadata and controls

Circle Fast-Fourier Transform (CircleFFT)

Implementation Content

What is the Circle Group?

Circle Group implementation

What is a Coset?

Standard Coset

Implementation Details for CFFT

Overview

In-Place FFT Computation

Twiddle Factors

Bit-Reverse Permutation

Result Ordering

Inverse FFT (ICFFT)

Design Considerations and Optimizations

API Usage

Working with Circle group points

Polynomial evaluation and interpolation using CFFT

Using CFFT directly

References