Newer STARK-based proving systems, such as Polygon's Plonky3 and StarkWare's Stwo operate over small 32-bit prime fields for most operations (low-degree extension, polynomial commitments) and use a high-degree extension field for operations that require security (FRI folding). The particular prime that both proving systems (plan to) use is the Mersenne prime .
Why small fields?
In STARKs, we usually work on multiplicative groups over . Algorithmically, multiplication scales with the square of the number of bits. So, going from a 64-bit field in Plonky2 to a 32-bit field in Plonky3 theoretically should give a 4x speedup. However, modern ALUs have vectorized 32-bit instructions and in practice, reducing the field size can lead to even more speedups.
Mersenne prime
Mersenne primes are primes of the form
The modular reduction operation in Mersenne primes is compute-friendly:
which in pseudo-code can be written as:
(k & p) + (k>>n)
The issue with Mersenne primes
Unfortunately, Mersenne primes cannot directly be used in STARKs because the multiplicative group has an order which in the case of Mersenne primes is = . This doesn't have a large 2-adicity, i.e., the group doesn't contain a subgroup whose number of elements is a large power of 2. A large 2-adicity is important for the FFT (NTT) and FRI parts of the STARK protocol since these recursively reduce the computation by half at each step.
Other approaches
Baby-bear prime
One option is to use other FFT-friendly 32-bit primes, such as the baby-bear prime that risc0 uses which has large 2-adicity:
In such primes, modular reduction is usually done by expressing the elements in Montgomery form and then using the Montgomery reduction algorithm. This is more complex and less efficient than Mersenne reduction.
Working over Elliptic curves
A way to circumvent the large 2-adicity requirement for a prime is to instead work on elliptic curve groups over the prime field.
By Hasse's theorem, we know that the number of points on an elliptic curve over a prime field satisfies the bound . This means that for arbitrary primes that don't have large 2-adicity, we can find an elliptic curve group that has. The ECFFT paper describes how the FFT algorithm can be extended to these 2-adic groups of Elliptic curves over a prime field.
Extension fields
Another approach is to work over extension fields. Extension fields are constructed by taking the polynomial ring and quotienting it by an irreducible polynomial of degree . The resulting field has elements of the form and a total of elements ( choices for each ). We can define a multiplicative group over this field, which has an order , where we exclude the point because it doesn't have an inverse.
For a quadratic extension field , the order is . Since divides the order , we know that the quadratic extension field contains a subgroup of order . For a Mersenne prime, is a large power of 2 which makes this subgroup suitable for FFT.
Assume that is an irreducible polynomial over . We use it to construct the field extension . The elements of the extension field will be of the form where and can be thought of as a root of the irreducible polynomial. For , one of the roots is the complex number so the elements in the extension field are analogous to complex numbers.
The group operation for the multiplicative group on is defined as:
and the identity element of this group is
When is irreducible in ?
The polynomial is irreducible over if and only if does not have a solution, i.e., is not a quadratic residue modulo .
Mersenne primes are of the form and hence is irreducible over . Now, we're trying to find the subgroup of order in . By definition, every element of this subgroup satisfies:
where we have used the fact that since all other terms in the expansion are multiples of and hence, equal to (also called Freshman's dream), and from Fermat's little theorem.
Since the prime is of the form , we can write it as . Substituting, we have
because and . Substituting this value into the original equation, we have
This is the equation of a unit circle in the complex plane. Therefore, the elements with order lie on the unit circle subgroup.
As a sanity check, we can also try to find the structure of the subgroup with order . For this subgroup:
The subgroup with simply corresponds to the multiplicative group of the base field and we know that it has order .
Another proof
Start with the circle group defined over a prime field as:
where .
The points in the circle group can be parametrized with a parameter as:
except for the point which can be thought of as the limit as .
This transformation is isomorphic and the inverse can be defined as:
This parametrization is analogous to the trigonometric parametrization of a unit circle with , and .
Now, for primes where is not a quadratic residue (i.e. ), the order of the circle group is . The comes from all the points generated for all possible values of and the extra to accommodate the point .
If is a quadratic residue then the denominator is undefined so the order of the circle group is i.e. . We subtract to exclude the two roots for which .
