--- title: Circle STARKs date: 2024-04-05 summary: Notes on the M31 Mersenne prime and Circle STARKs. --- Newer [STARK](https://aszepieniec.github.io/stark-anatomy/)-based proving systems, such as Polygon's [Plonky3](https://github.com/Plonky3/Plonky3) and StarkWare's [Stwo](https://github.com/starkware-libs/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 $p = 2^{31} - 1$. ## Why small fields? In STARKs, we usually work on multiplicative groups over $\mathbb F_p$. Algorithmically, multiplication scales with the square of the number of bits. So, going from a 64-bit field in [Plonky2](https://github.com/0xPolygonZero/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 $$ p = 2^n - 1 $$ The modular reduction operation in Mersenne primes is compute-friendly: $$ \begin{align*} k &\equiv (k\mod 2^n) + \left\lfloor\frac{k}{2^n}\right\rfloor \mod 2^n - 1 \end{align*} $$ which in pseudo-code can be written as: ```rust (k & p) + (k >> n) ``` #### Derivation of reduction formula Any number $k$ can be expressed as: $$ \begin{align*} k &= k \mod 2^n + \left\lfloor\frac{k}{2^n}\right\rfloor \cdot 2^n \\ \end{align*} $$ Taking modulo $p = 2^n - 1$ on both sides: $$ \begin{align*} k &\equiv k \mod 2^n + \left\lfloor\frac{k}{2^n}\right\rfloor \cdot 2^n &\mod 2^n - 1\\ k &\equiv k \mod 2^n + \left\lfloor\frac{k}{2^n}\right\rfloor \cdot (2^n \mod 2^n - 1) &\mod 2^n - 1\\ k &\equiv k \mod 2^n + \left\lfloor\frac{k}{2^n}\right\rfloor &\mod 2^n - 1\\ \end{align*} $$ where we used the fact that $2^n \equiv 1 \mod 2^n - 1$. ### The issue with Mersenne primes Unfortunately, Mersenne primes cannot directly be used in STARKs because the multiplicative group $\mathbb F_p$ has an order $p - 1$ which in the case of Mersenne primes is $2^n - 2$ = $2\cdot(2^{n-1} - 1)$. 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](https://github.com/risc0/risc0/blob/6d2faab58d27a12f8c213293376a01a0cbf2a939/risc0/core/src/field/baby_bear.rs) that risc0 uses which has large 2-adicity: $$ p = 2^{31} - 2^{27} + 1 $$ In such primes, modular reduction is usually done by expressing the elements in Montgomery form and then using the [Montgomery reduction](https://en.wikipedia.org/wiki/Montgomery_modular_multiplication#The_REDC_algorithm) 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](https://en.wikipedia.org/wiki/Hasse%27s_theorem_on_elliptic_curves), we know that the number of points $N$ on an elliptic curve over a prime field $\mathbb F_p$ satisfies the bound $|N - (p + 1)| \leq 2\sqrt{p}$. This means that for arbitrary primes that don't have large 2-adicity, we can find an elliptic curve group that has. The [ECFFT](https://eprint.iacr.org/2022/1542) 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 $\mathbb F_p[x]$ and quotienting it by an irreducible polynomial of degree $d$. The resulting field has elements of the form $(a_1, a_2\ldots a_d)$ and a total of $p^d$ elements ($p$ choices for each $a_i$). We can define a multiplicative group over this field, which has an order $p^d - 1$, where we exclude the point $(0, 0, \ldots, 0)$ because it doesn't have an inverse. For a quadratic extension field $\mathbb{F}_{p^2}$, the order is $p^2 - 1$. Since $p + 1$ divides the order $p^2 - 1 = (p+1)(p-1)$, we know that the quadratic extension field contains a subgroup of order $p + 1$. For a Mersenne prime, $p + 1 = 2^n$ is a large power of 2 which makes this subgroup suitable for FFT. Assume that $1 + x^2$ is an irreducible polynomial over $\mathbb F_p$. We use it to construct the field extension $\mathbb F_{p^2}$. The elements of the extension field will be of the form $a + xb$ where $a, b \in \mathbb F_p$ and $x$ can be thought of as a root of the irreducible polynomial. For $1 + x^2$, one of the roots is the complex number $i = \sqrt{-1}$ so the elements in the extension field are analogous to complex numbers. The group operation for the multiplicative group on $\mathbb{F}_{p^2}$ is defined as: $$ (a_1, b_1) \cdot (a_2, b_2) = (a_1a_2 - b_1b_2, a_1b_2 + a_2b_1) $$ and the identity element of this group is $(1, 0)$ #### When is $1 + x^2$ irreducible in $\mathbb F_p$? The polynomial $1 + x^2$ is irreducible over $\mathbb F_p$ if and only if $x^2 \equiv -1 \mod p$ does not have a solution, i.e., $-1$ is not a quadratic residue modulo $p$. We have $x^2 \not\equiv -1\mod p$. Raising both sides to power $\frac{p - 1}{2}$, we have: $$ \begin{align*} (-1)^{(p-1)/2} &\not\equiv (x^2)^{(p - 1)/2} &\mod p\\ (-1)^{(p-1)/2} &\not\equiv x^{p-1} &\mod p\\ (-1)^{(p-1)/2} &\not\equiv 1 &\mod p \end{align*} $$ where we have used [Fermat's little theorem](https://en.wikipedia.org/wiki/Fermat%27s_little_theorem): $a^{p - 1} = 1 \mod p$. This inequality is only valid when $\frac{p-1}{2}$ is odd i.e. $\frac{p-1}{2} = 2k + 1$ or $$ \begin{align*} p &= 4k + 3\\ p &\equiv 3 \mod 4 \end{align*} $$ Conversely, $-1$ is a quadratic residue when $p = 1\mod 4$. Mersenne primes $2^n - 1$ are of the form $4k + 3$ and hence $1 + x^2$ is irreducible over $\mathbb F_p$. Now, we're trying to find the subgroup of order $p+1$ in $\mathbb{F}_{p^2}$. By definition, every element $z = a + xb$ of this subgroup satisfies: $$ \begin{align*} z^{p + 1} &\equiv 1 &\mod p\\ z^p\cdot z &\equiv 1 &\mod p \end{align*} $$ Consider the value $z^p$ (called [Frobenius endomorphism](https://en.wikipedia.org/wiki/Frobenius_endomorphism)): $$ \begin{align*} z^p &\equiv (a + xb)^p &\mod p\\ &\equiv a^p + x^pb^p &\mod p\\ &\equiv a + x^pb &\mod p \end{align*} $$ where we have used the fact that $(a + b)^p = a^p + b^p \mod p$ since all other terms in the expansion are multiples of $p$ and hence, equal to $0\mod p$ (also called [Freshman's dream](https://en.wikipedia.org/wiki/Freshman's_dream#Prime_characteristic)), and $a^p = a \mod p$ from Fermat's little theorem. Since the prime is of the form $p = 3\mod 4$, we can write it as $p = 4k + 3$. Substituting, we have $$ \begin{align*} z^p &\equiv a + x^{4k + 3}b &\mod p\\ &\equiv a + (x^4)^kx^3b &\mod p\\ &\equiv a - xb &\mod p \end{align*} $$ because $x^4 \equiv 1 \mod p$ and $x^3 \equiv -x \mod p$. Substituting this value into the original equation, we have $$ \begin{align*} z^p\cdot z &\equiv 1 &\mod p\\ (a + xb)^p\cdot (a + xb) &\equiv 1 &\mod p\\ (a - xb)\cdot(a + xb) &\equiv 1 &\mod p\\ a^2 - x^2b^2 &\equiv 1 &\mod p\\ a^2 + b^2 &\equiv 1 &\mod p \end{align*} $$ This is the equation of a unit circle in the complex plane. Therefore, the elements $(a, b)$ with order $p + 1$ lie on the unit circle subgroup. As a sanity check, we can also try to find the structure of the subgroup with order $p - 1$. For this subgroup: $$ \begin{align*} z^{p - 1} &\equiv 1 &\mod p\\ z^p &\equiv z &\mod p\\ (a + xb)^p &\equiv a + xb &\mod p\\ a - xb &\equiv a + xb &\mod p\\ b &\equiv 0 &\mod p \end{align*} $$ The subgroup with $b = 0$ simply corresponds to the multiplicative group of the base field $\mathbb F_p$ and we know that it has order $p - 1$. #### Another proof Start with the circle group defined over a prime field $\mathbb F_p$ as: $$ a^2 + b^2 \equiv 1 \mod p $$ where $a, b \in \mathbb F_p$. The points in the circle group $(x, y)$ can be parametrized with a parameter $t$ as: $$ \begin{align} x = \frac{1 - t^2}{1 + t^2}\\ y = \frac{2t}{1 + t^2} \end{align} $$ except for the point $(-1, 0)$ which can be thought of as the limit as $t\to \infty$. This transformation is isomorphic and the inverse can be defined as: $$ t = \frac{y}{x + 1} $$ This parametrization is analogous to the trigonometric parametrization of a unit circle with $x = \cos\theta$, $y = \sin\theta$ and $t = \tan\frac{\theta}{2}$. Circle group over a prime field Now, for primes $p$ where $-1$ is not a quadratic residue (i.e. $t^2 \not\equiv -1\mod p\ \forall\ t$), the order of the circle group is $p + 1$. The $p$ comes from all the points generated for all possible values of $t \in \mathbb F_p$ and the extra $1$ to accommodate the point $(-1, 0)$. If $-1$ is a quadratic residue then the denominator $1 + t^2$ is undefined so the order of the circle group is $(p - 2) + 1$ i.e. $p - 1$. We subtract $2$ to exclude the two roots for which $t^2 = -1$. ## Circle FFT TODO