# Circle Fast-Fourier Transform (CircleFFT)
This folder contains all the necessary tools to work with the [circle FFT](https://eprint.iacr.org/2024/278), which is a suitable way of performing an analogue of the [radix-2 FFT algorithm](../fft/README.md) 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](https://blog.lambdaclass.com/an-introduction-to-circle-starks/) or [Vitalik's explanation](https://vitalik.eth.limo/general/2024/07/23/circlestarks.html)
## 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.
```rust
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:
```rust
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
```rust
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
```rust
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
```rust
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](https://blog.lambdaclass.com/an-introduction-to-circle-starks/) - LambdaClass Blog
- [Vitalik's Explanation of Circle STARKs](https://vitalik.eth.limo/general/2024/07/23/circlestarks.html)
- [Circle FFT Paper](https://eprint.iacr.org/2024/278)
- [Anatomy of a STARK](https://aszepieniec.github.io/stark-anatomy/) - Detailed explanation of STARKs
- [STARKs, Part I: Proofs with Polynomials](https://vitalik.ca/general/2017/11/09/starks_part_1.html) - Vitalik Buterin's series on STARKs