Circle STARKs

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 $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 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:

(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 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 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 $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 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: $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):

\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), 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}$ .

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