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 = 2^k -1$. S-two uses the Mersenne prime $\textsf{M31}$ of size $P = 2^{31} - 1$, which is implemented as follows:

pub struct M31(pub u32);

Why $\textsf{M31}$?

The key advantage is extremely cheap modular reduction after a 31-bit multiplication. Consider computing $a \cdot b$, where $a, b \in \textsf{M31}$. This operation involves a 31-bit integer multiplication, producing a 62-bit intermediate result, which is then reduced modulo $P$.

Suppose $x = a \cdot b$ then we can decompose $x$ into two 31-bit values $b$ and $s$, such that $x = 2^{31} \cdot b + s$, as shown in the following figure.

Figure 1: Product decomposition

To perform modular reduction, we start with: $x \equiv (2^{31} \cdot b + s) \quad mod \quad (2^{31} - 1)$ Substituting $2^{31} \equiv 1 \mod (2^{31} - 1)$ gives: $x \equiv (b + s) \quad mod \quad (2^{31} - 1)$

Since $b$ and $s$ 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 $P$.

Why We Need Extensions ?

We cannot instantiate our STARK protocols using $\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 $\textsf{M31}$ has the following order:

$P-1 = 2^{31}-2$

As shown above, the multiplicative group of $\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-1$. In other words, there does not exist a sufficiently large $n$ such that $2^n|P - 1$. To make $\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 $\textsf{M31}$ are implemented using the Rust macro impl_field!, which takes as argument the field $\textsf{M31}$ and the size of the field $P = 2^{31} - 1$, as follows:

impl_field!(M31, P);

Since we work over extensions of $\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 $\textsf{M31}$: complex extension and quartic extension.

Complex Extension

We construct the degree-2 extension of $\textsf{M31}$ denoted by $\textsf{CM31}$ using the polynomial $X^2 + 1$ which is irreducible over $\textsf{M31}$.

$\textsf{CM31} = \textsf{M31}[X] / (X^2 + 1)$

This extension forms a field of size $P^2$, where elements can be represented as $(a, b)$ or $a + i \cdot b$ where $a, b \in \textsf{M31}$ and $i$ is the root of the polynomial $X^2 + 1$ i.e. $i^2 + 1 = 0$. This is implemented as follows:

pub struct CM31(pub M31, pub M31);

The order of the multiplicative group of $\textsf{CM31}$ is calculated as follows:

$P^2 - 1 = (P-1) \cdot (P+1) = (2^{31}-2) \cdot (2^{31})$

As shown above, $2^{31} | P^2 - 1$ i.e. the multiplicative group of $\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 $\textsf{M31}$, the operations of $\textsf{CM31}$ are defined using the macros impl_field! and impl_extension_field! (which takes as argument the field $\textsf{CM31}$ and the field to be extended i.e. $\textsf{M31}$). These are implemented as follows:

impl_field!(CM31, P2);
impl_extension_field!(CM31, M31);

where P2 is the size of $\textsf{CM31}$ i.e. $P^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 = 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 $\textsf{M31}$ denoted by $\textsf{QM31}$, which is equivalent to degree-2 extension of $\textsf{CM31}$, denoted as $\textsf{QM31} = \textsf{CM31}[X]/(X^2 - 2 - i)$

Here the polynomial $(X^2 - 2 - i)$ is irreducible over $\textsf{CM31}$.

The elements of $\textsf{QM31}$ can be represented as $(r, s)$ or $r + u \cdot s$ where $r, s \in \textsf{CM31}$ and $u$ is the root of the polynomial $X^2 - 2 - i$ i.e. $u^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 $\textsf{QM31}$ to sample random challenges it is given the type alias SecureField.

Alternatively, the elements of $\textsf{QM31}$ can also be represented as four elements of $\textsf{M31}$ i.e. $((a, b), (c, d))$ or $(a + i \cdot b) + (c + i \cdot d) \cdot u$

where $a, b, c, d \in \textsf{M31}$. With four elements from $\textsf{M31}$, the challenge space consists of 124-bit values, offering a sufficiently large $2^{124}$ possibilities to sample a random challenge.

Similar to $\textsf{CM31}$, the operations of $\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 $\textsf{QM31}$ i.e. $P^4$.

In the next section, we will explore the circle group, which is used to instantiate the STARK protocol.