Skip to main content

​
Mersenne Primes

Proof systems typically rely on finite field operations, where efficient field arithmetic is crucial for optimizing proof generation. In STARK protocols, there is no direct dependency between the security level of the proof system and the field size. This allows the use of small fields with highly efficient arithmetic. S-two uses a particular family of primes called Mersenne primes. A Mersenne prime is defined as a prime number that is one less than a power of two, expressed as P=2k−1P = 2^k -1. S-two uses the Mersenne prime M31\textsf{M31} of size P=231−1P = 2^{31} - 1, which is implemented as follows: 
pub struct M31(pub u32);

​
Why M31\textsf{M31}?

The key advantage is extremely cheap modular reduction after a 31-bit multiplication. Consider computing a⋅ba \cdot b, where a,b∈M31a, b \in \textsf{M31}. This operation involves a 31-bit integer multiplication, producing a 62-bit intermediate result, which is then reduced modulo PP. Suppose x=a⋅bx = a \cdot b then we can decompose xx into two 31-bit values bb and ss, such that x=231⋅b+sx = 2^{31} \cdot b + s, as shown in the following figure.
Figure 1: Product decomposition
To perform modular reduction, we start with: x≡(231⋅b+s)mod(231−1)x \equiv (2^{31} \cdot b + s) \quad mod \quad (2^{31} - 1) Substituting 231≡1mod  (231−1)2^{31} \equiv 1 \mod (2^{31} - 1) gives: x≡(b+s)mod(231−1)x \equiv (b + s) \quad mod \quad (2^{31} - 1) Since bb and ss are both 31-bit values, they can be directly represented as field elements. Consequently, modular reduction is performed with a single field addition. This makes arithmetic over Mersenne primes exceptionally fast, making them an ideal choice for our STARK protocol. The above field multiplication is implemented as: 
    fn mul(self, rhs: Self) -> Self::Output {
        Self::reduce((self.0 as u64) * (rhs.0 as u64))
    }
where reduce is a function which performs efficient reduction of the resulting number modulo PP.

​
Why We Need Extensions ?

We cannot instantiate our STARK protocols using M31\textsf{M31} since it is not FFT-friendly field, meaning it does not contain a multiplicative subgroup of order that is a large power of two (commonly referred to as a smooth subgroup). The multiplicative group of M31\textsf{M31} has the following order: P−1=231−2P-1 = 2^{31}-2 As shown above, the multiplicative group of M31\textsf{M31} lacks a smooth subgroup of size that is a large power of two because there is no large power of two that divides P−1P-1. In other words, there does not exist a sufficiently large nn such that 2n∣P−12^n|P - 1. To make M31\textsf{M31} compatible with STARKs, we will work over extensions of it.

​
Field Operations

S-two avoids code duplication by providing two Rust macros, impl_field! and impl_extension_field!, for implementing field and extension field operations. For example, field operations for M31\textsf{M31} are implemented using the Rust macro impl_field!, which takes as argument the field M31\textsf{M31} and the size of the field P=231−1P = 2^{31} - 1, as follows: 
impl_field!(M31, P);
Since we work over extensions of M31\textsf{M31}, it has the type alias BaseField, as follows: 
{{#webinclude https://raw.githubusercontent.com/starkware-libs/stwo/0790eba46b8af5697083d84fb75bd34b08a0b31f/crates/stwo/src/core/fields/m31.rs 33}}

​
Extensions of Mersenne Prime Field

This section describes two extensions of M31\textsf{M31}: complex extension and quartic extension.

​
Complex Extension

We construct the degree-2 extension of M31\textsf{M31} denoted by CM31\textsf{CM31} using the polynomial X2+1X^2 + 1 which is irreducible over M31\textsf{M31}. CM31=M31[X]/(X2+1)\textsf{CM31} = \textsf{M31}[X] / (X^2 + 1) This extension forms a field of size P2P^2, where elements can be represented as (a,b)(a, b) or a+i⋅ba + i \cdot b where a,b∈M31a, b \in \textsf{M31} and ii is the root of the polynomial X2+1X^2 + 1 i.e. i2+1=0i^2 + 1 = 0. This is implemented as follows: 
pub struct CM31(pub M31, pub M31);
The order of the multiplicative group of CM31\textsf{CM31} is calculated as follows: P2−1=(P−1)⋅(P+1)=(231−2)⋅(231)P^2 - 1 = (P-1) \cdot (P+1) = (2^{31}-2) \cdot (2^{31}) As shown above, 231∣P2−12^{31} | P^2 - 1 i.e. the multiplicative group of CM31\textsf{CM31} contains a subgroup of size that is a large power of two. This makes it suitable for instantiating STARKs. This subgroup is what we refer to as the Circle group (explored further in the next section). Similar to M31\textsf{M31}, the operations of CM31\textsf{CM31} are defined using the macros impl_field! and impl_extension_field! (which takes as argument the field CM31\textsf{CM31} and the field to be extended i.e. M31\textsf{M31}). These are implemented as follows: 
impl_field!(CM31, P2);
impl_extension_field!(CM31, M31);
where P2 is the size of CM31\textsf{CM31} i.e. P2P^2.

​
Quartic Extension

For the soundness of the protocol, it is crucial that the verifier samples random challenges from a sufficiently large field to ensure that an adversary cannot guess or brute-force the challenges and generate a proof that passes verification without knowledge of the witness. If we use P=231−1P = 2^{31} -1, then 31-bit random challenges are not sufficient to maintain the security of the protocol. To address this, the verifier draws random challenges from a degree-4 extension of M31\textsf{M31} denoted by QM31\textsf{QM31}, which is equivalent to degree-2 extension of CM31\textsf{CM31}, denoted as QM31=CM31[X]/(X2−2−i)\textsf{QM31} = \textsf{CM31}[X]/(X^2 - 2 - i) Here the polynomial (X2−2−i)(X^2 - 2 - i) is irreducible over CM31\textsf{CM31}. The elements of QM31\textsf{QM31} can be represented as (r,s)(r, s) or r+u⋅sr + u \cdot s where r,s∈CM31r, s \in \textsf{CM31} and uu is the root of the polynomial X2−2−iX^2 - 2 - i i.e. u2−2−i=0u^2 - 2 - i = 0. This is implemented as follows: 
pub struct QM31(pub CM31, pub CM31);
pub type SecureField = QM31;
Since the verifier uses the field QM31\textsf{QM31} to sample random challenges it is given the type alias SecureField. Alternatively, the elements of QM31\textsf{QM31} can also be represented as four elements of M31\textsf{M31} i.e. ((a,b),(c,d))((a, b), (c, d)) or (a+i⋅b)+(c+i⋅d)⋅u(a + i \cdot b) + (c + i \cdot d) \cdot u where a,b,c,d∈M31a, b, c, d \in \textsf{M31}. With four elements from M31\textsf{M31}, the challenge space consists of 124-bit values, offering a sufficiently large 21242^{124} possibilities to sample a random challenge. Similar to CM31\textsf{CM31}, the operations of QM31\textsf{QM31} are defined using the macros impl_field! and impl_extension_field!, implemented as follows: 
impl_field!(QM31, P4);
impl_extension_field!(QM31, CM31);
where P4 is the size of QM31\textsf{QM31} i.e. P4P^4. In the next section, we will explore the circle group, which is used to instantiate the STARK protocol.