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, such as Mersenne prime fields. 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. Consider the Mersenne prime field Fp\mathbb{F}_p where p=231−1p = 2^{31} - 1. Our objective is to perform field multiplication a⋅ba \cdot b, where a,b∈Fpa, b \in \mathbb{F}_p. This operation involves a 31-bit integer multiplication, producing a 62-bit intermediate result, which is then reduced modulo pp. Let x=a⋅bx = a \cdot b, where a,ba, b are 31-bit values, resulting in a 62-bit product xx. 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.

Mersenne Prime Multiplication

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. However, we instantiate STARK protocols over an FFT-friendly field, meaning a field that contains a multiplicative subgroup of order that is a large power of two (commonly referred to as a smooth subgroup). ∣Fp∗∣=p−1=2k−2|\mathbb{F}_p^*| = p-1 = 2^k-2 As shown above, Mersenne prime fields lack a smooth subgroup of size that is a large power of two because there is no large power of two that divides ∣Fp∗∣|\mathbb{F}_{p}^*|. In other words, there does not exist a sufficiently large nn such that 2n ∣ p−12^n \, | \, p - 1. To make Mersenne prime fields compatible with STARKs, we use a degree-2 extension of Fp\mathbb{F}_p, defined as follows: Fp2=Fp[X]/(X2+1)\mathbb{F}_{p^2} = \mathbb{F}_p[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∈Fpa, b \in \mathbb{F}_p and ii is the root of the polynomial X2+1X^2 + 1 i.e. i2+1=0i^2 + 1 = 0. The order of the multiplicative group of this extended field is calculated as follows: ∣Fp2∗∣=p2−1=(p−1)⋅(p+1)|\mathbb{F}_{p^2}^*| = p^2 - 1 = (p-1) \cdot (p+1) For Mersenne primes of the form p=2k−1p = 2^k - 1, this becomes: ∣Fp2∗∣=(2k−2)⋅(2k)|\mathbb{F}_{p^2}^*| = (2^k-2) \cdot (2^k) As shown above, 2k ∣ ∣Fp2∗∣2^k \, | \, |\mathbb{F}_{p^2}^*| i.e. Fp2∗\mathbb{F}_{p^2}^* 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).

​
Secure Field

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 Fp\mathbb{F}_{p}, which is equivalent to degree-2 extension of Fp2\mathbb{F}_{p^2}, denoted as Fp4=Fp2[X]/(X2−2−i)\mathbb{F}_{p^4} = \mathbb{F}_{p^2}[X]/(X^2 - 2 - i) The elements of Fp4\mathbb{F}_{p^4} can be represented as (r,s)(r, s) or r+u⋅sr + u \cdot s where r,s∈Fp2r, s \in \mathbb{F}_{p^2} and uu is the root of the polynomial X2−2−iX^2 - 2 - i i.e. u2−2−i=0u^2 - 2 - i = 0. Alternatively, the elements of Fp4\mathbb{F}_{p^4} can also be represented as four elements of Fp\mathbb{F}_{p} 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∈Fpa, b, c, d \in \mathbb{F}_p. With four elements from F_p\mathbb{F}\_{p}, the challenge space consists of 124-bit values, offering a sufficiently large 21242^{124} possibilities to sample a random challenge.