Circle STARKs: Circles

This is Part II of a four-part series on Circle STARKs; Part I covers Mersenne prime fields. It was written with Mathias Hall-Andersen. The original appeared on the ZK Security blog.

In this post we start our journey into the algebra of Circle STARKs. It’s pretty easy actually.

The Complex Numbers#

You remember the complex numbers $\mathbb{C}$ from high-school maths, right? Some high-school teachers are better at conveying this than others, but the way to “construct” the complex numbers is as a quotient of the polynomial ring $\mathbb{R}[X]$ by the ideal generated by the irreducible polynomial $X^2 + 1 \in \mathbb{R}[X]$:

In other words, polynomials plus/minus multiples of $X^2 + 1$. The more common way to think about the complex numbers is as $a + b \cdot i$ where $i$ and $-i$ are the roots of the polynomial $X^2 + 1$, i.e. $i^2 + 1 = 0$ and $(-i)^2 + 1 = 0$. These two views are isomorphic (the same) via:

For completeness, let’s briefly recall the algebra of complex numbers:

You add complex numbers “coordinate-wise”:

This is because, as we saw, they are really just (equivalence classes of) polynomials in disguise and this is how you add polynomials. Similarly, you multiply complex numbers like this:

This is equivalent to multiplication of polynomials in $\mathbb{F}[X]$, followed by reduction modulo $X^2 + 1$. Finally, as a result, if you multiply a complex number by itself you get:

Because, you know, $i^2 = -1$. We also have the “complex conjugate” of a complex number $\bar{z}$, defined by flipping the imaginary component i.e. $\overline{(x + i y)} = x - i y$. This distributes over multiplication and addition: $\overline{z_1 \cdot z_2} = \bar{z_1} \cdot \bar{z_2}$ and $\overline{z_1 + z_2} = \bar{z_1} + \bar{z_2}$. Recall that both $i$ and $-i$ are roots of the polynomial $X^2 + 1$, so one can think of conjugation as switching between the arbitrary choice of $i$ and $-i$. If you feel fancy you can call such a map a field automorphism: it maps from the field to itself and preserves the field operations.

Nothing Special About The Reals#

In the section above we constructed the complex numbers as a quotient of the polynomial ring $\mathbb{R}[X]$ by the ideal generated by the irreducible polynomial $X^2 + 1 \in \mathbb{R}[X]$. Exactly the same works for any field $\mathbb{F}$ ($\mathbb{F} = \mathbb{R}$ in the above example), in particular, for finite fields: suppose we have a finite field $\mathbb{F} = \mathbb{F}_q$, then you can consider the polynomial $X^2 + 1 \in \mathbb{F}_q[X]$ and extend the field with a root of this polynomial. i.e. form the “degree 2 extension” of $\mathbb{F}_q$ as:

Note that $X^2 + 1$ needs to be irreducible in the field $\mathbb{F}_q$ e.g. $\mathbb{F} = \mathbb{F}_2$ won’t work, since:

The Unit Circle as a Group#

Do you also remember the real unit circle from high-school maths? Sure you do, here it is:

This just means every element of “$l^2$-norm 1” in $\mathbb{R}$: every point at “distance 1” from the origin or every vector of length one if you will.

If we consider the complex numbers with norm 1, we get the unit circle in the complex plane:

By looking at the circle like this, we can see that it is a group under multiplication, if you multiply two complex numbers $z_1, z_2 \in \mathbb{C}$ of norm 1, you get a complex number $z_1 \cdot z_2$ of norm 1, as shown below:

If you were really paying attention in high-school, you might even remember Euler’s formula, which is an alternate representation of complex numbers with norm 1:

This is useful because it translates between angles $\theta$ and points on the unit circle, as shown in the animation below:

So we can also write it as:

And therefore, the unit circle has a group structure, that we can view in a couple of ways:

• As multiplication of complex numbers:

  $$(x_1 + i y_1) \cdot (x_2 + i y_2) = (x_1 x_2 - y_1 y_2) + i (x_1 y_2 + x_2 y_1)$$

• As addition of angles $\theta_1 + \theta_2$:

  $$e^{i \theta_1} \cdot e^{i \theta_2} = e^{i (\theta_1 + \theta_2)}$$

The identity element is the point at angle $\theta = 0$, which is the point $(x, y)=(1,0)$ or $1 \in \mathbb{C}$:

The inverse of $z = x + i y = e^{i \theta}$ is the point with the same angle, but opposite direction:

This point always lies exactly opposite the point $z$ on the circle, so all we have to do is flip the y-coordinate: the complex conjugate of $z$. This is illustrated below with a point and its inverse moving around the circle:

This is clear from both interpretations of the group structure:

• As multiplication of complex numbers:

  $$\begin{aligned} z \cdot J(z) &= (x + i y) \cdot (x - i y) \\ &= x^2 + y^2 = 1 \end{aligned}$$

• As addition of angles:

  $$e^{i\theta} \cdot J(e^{i\theta}) = e^{i\theta} \cdot e^{-i\theta} = e^{i \theta - i \theta} = e^{i \cdot 0} = 1$$

Since we have a group, it is natural to look at maps from the group to itself. The most central of which is going to be the humble “squaring” or “doubling” map, depending on which perspective we choose:

Which simply:

• Squares the complex number $z = x + iy$ of norm $1$: $$\begin{aligned} \pi(x + iy) &= (x + iy) \cdot (x + iy) \\ &= (x^2 - y^2) + i (2xy) \\ &= 2 x^2 - 1 + i (2xy) \end{aligned}$$
• Or, equivalently, doubles the angle of the point $z = e^{i\theta}$: $$\pi(e^{i\theta}) = e^{i\theta} \cdot e^{i\theta} = e^{i \cdot 2\theta}$$

Because we have $x^2 + y^2 = 1$, we can replace $y^2$ with $1 - x^2$ and write $\pi(x + i y) = 2 x^2 - 1 + i (2xy)$. Note that the x-coordinate (“real part”) of the doubled point, $2 x^2 - 1$, does not depend on $y$, this means that we can compute the x-coordinate (“real part”) of repeated doubling using just the x-coordinate and the formula $x_{n+1} = 2 \cdot x_n^2 - 1$, a nice optimization that will come in handy later.

How “Big” is The Circle?#

We just saw that the circle is a subgroup of the multiplicative group of the complex numbers, we also saw earlier that there is nothing “special” about a degree-2 extension of the reals as opposed to any other field: notably finite fields.

The next natural question is: How “large” is this circle group that we introduced? i.e. what is its order? i.e. how many points are there on the unit circle over an arbitrary field? In order to figure this out, we create a bijective map from the circle to the projective line with an “extra point”. To explore this consider the “stereographic projection” onto the y-axis with center $(-1, 0)$: the intersection between the line $((-1, 0), (x, y))$ and the y-axis. This is illustrated below:

So as we move the point around the circle we can “hit” every value on the y-axis AND a special value “at infinity” when $(x, y) = (-1, 0)$: it sends any point on the circle to $\mathbb{R} \cup \{ \infty \}$.

It is also easy to see that the mapping is injective, i.e. every point $\mathbb{R} \cup \{ \infty \}$ corresponds to a unique point on the circle. So there is an isomorphism between the unit circle and the projective line with a point at infinity. When $x \neq -1$, the explicit mapping and inverse is given by:

Although the illustration above is only meaningful for the real numbers, the mapping (the equations above) works for any field $\mathbb{F}$. This means that the number of points on the unit circle over a field $\mathbb{F}$ is $|\mathbb{F}| + 1$, corresponding to the projective line $\mathbb{F}$ AND a point at infinity. When $|\mathbb{F}| = 2^k - 1$ (Mersenne prime) the unit circle has $2^k$ points i.e. it is a smooth group that we can use for FFTs and FRI as discussed in part one of this series.

As a sanity check: suppose we have an arbitrary field $\mathbb{F}$ (e.g. some prime field $\mathbb{F}_p$), the total number of elements in the degree two extension $\mathbb{C} = \mathbb{F}[X] / (X^2 + 1)$ is $|\mathbb{C}| = |\mathbb{F}|^2$ and the number of elements in the multiplicative group $\mathbb{C}^{*}$ is therefore $|\mathbb{C}^*| = |\mathbb{F}|^2 - 1$, everything except $0$ has an inverse. And hence $|\mathbb{S}_1| = |\mathbb{F}| + 1$ divides $|\mathbb{C}^{*}| = |\mathbb{F}|^2 - 1$ as expected: since the circle is a subgroup of the multiplicative group $\mathbb{C}^{*}$, this is required by Lagrange’s theorem.

Now that we know that the unit circle is a cyclic group of order $2^k$, let’s look a bit more at its subgroups and cosets.

Subgroups of the Unit Circle#

In the previous section we established that the number of points on the unit circle are $|\mathbb{F}| + 1$ i.e. the unit circle is a cyclic group of order $|\mathbb{F}| + 1$. A cyclic group of order $|\mathbb{F}| + 1$ has a subgroup of order $N$ for every divisor $N$ of $|\mathbb{F}| + 1$.

In the case of complex numbers, since there are $2\pi$ radians in a circle, it follows that $\omega = e^{i \theta}$, where $\theta = \frac{2\pi}{N}$, generates a cyclic subgroup of order $N$. We will denote a cyclic subgroup of size $N = 2^n$ by $G_n$. In the STARK protocol, the computation trace is encoded as a low-degree polynomial over some domain $D$ using the FFT algorithm. For Circle STARKs, the domain $D$ is a set of points on the circle curve. We will now explore suitable domains for the circle FFT.

Consider $G_{n-1}$, the cyclic subgroup of size $2^{n-1}$ and its two cosets $Q \cdot G_{n-1}$ and $Q^{-1} \cdot G_{n-1}$. The union of the two cosets $D = Q \cdot G_{n-1} \cup Q^{-1} \cdot G_{n-1}$ such that $Q \cdot G_{n-1} \cap Q^{-1} \cdot G_{n-1} = \emptyset$ is called the twin-coset of size $N=2^n$. In case of circle group defined over Mersenne prime, the twin-coset $D$ is a coset of the subgroup $G_n$ given by

we call $D$ as the standard position coset of size $N=2^n$. This set $D$ forms the trace domain for our circle FFT. We will understand the structure of the twin-coset and the standard position coset using the following example.

The animation illustrates $G_2$, a subgroup of size 4, represented by orange points. It then shows two cosets: $Q \cdot G_2$ and $Q^{-1} \cdot G_2$.

1. Rotation by $Q$: Multiplication of $G_2$ by $Q$ corresponds to rotating $G_2$ in the counterclockwise direction by an angle $\delta$. This is visualized as the rotated orange points representing $Q \cdot G_2$.

2. Rotation by $Q^{-1}$: Similarly, multiplication of $G_2$ by $Q^{-1}$ rotates $G_2$ in the clockwise direction by $\delta$. This is shown as the rotated blue points representing $Q^{-1} \cdot G_2$.

The union of both sets, $D = Q \cdot G_2 \cup Q^{-1} \cdot G_2$, forms the twin-coset, which has size 8. The different values of $Q$ correspond to rotations by different angles $\delta$. For a specific choice of $Q$ (e.g., rotation by $\delta = \pi / 8 = 0.125 \pi$), the twin-coset $D$ becomes a coset of the subgroup $G_8$. In this case, $D$ is the standard position coset of size 8.

Note that the points of a standard position coset (rotation by $\delta = 0.125 \pi$) are symmetric about the center $(0, 0)$ as well as equally spaced around the circle. In contrast, for a twin-coset (rotation by $\delta \neq 0.125 \pi$), the points are only symmetric about $(0, 0)$.

We will now look into the polynomials which are interpolated over the standard position coset (trace domain for Circle STARKs).

Polynomials Over The Circle#

In the context of STARKs, the computation trace is interpolated as polynomials over a specified domain. For traditional STARKs, this domain is the coset of a smooth additive/multiplicative subgroup, and the resulting interpolation yields univariate polynomials. Whereas, in case of Circle STARKs, the domain is formed by points on the circle curve (specifically the standard position coset). Here, interpolation results in bivariate polynomials because the points on the circle curve are represented by two variables: x and y.

Let $\mathbb{F}[x, y]$ represent the ring of bivariate polynomials with coefficients in $\mathbb{F}$. Since interpolation occurs over points on the circle curve, the resulting polynomials belong to the quotient of the polynomial ring $\mathbb{F}[x, y]$ by the ideal $\left(X^2 + Y^2 - 1\right)$. The space of these bivariate polynomials over the circle curve of total degree $\leq N/2$ is denoted by $L_N(\mathbb{F})$.

where $\left(X^2 + Y^2 - 1\right)$ denotes the ideal generated by the polynomial $X^2 + Y^2 - 1$ i.e.

Now let us look at another representation of these polynomials. For any $p(X, Y) \in L_N(\mathbb{F})$, we can substitute all the higher degree terms of $Y$ with the equation of circle $Y^2 = 1 - X^2$ and reduce $p(X, Y)$ to the form,

Since $p(X, Y)$ is of total degree $\leq N/2$, $p_0$ has degree $\leq N/2$ and $p_1$ has degree $\leq N/2 - 1$. From the above representation we can see that the space $L_N(\mathbb{F})$ is spanned by the following monomial basis:

The dimension of $L_N(\mathbb{F})$ is the number of monomial basis elements, which is $N + 1$. Now we will understand vanishing polynomial, which belongs to the space $L_N(\mathbb{F})$.

Vanishing Polynomial#

A vanishing polynomial is a non-zero polynomial that evaluates to zero over a specific set of points. In STARKs, we define polynomial constraints over the computation trace. These constraints are satisfied when the corresponding polynomial evaluates to zero over points on the trace domain. Thus the constraint polynomial must be a multiple of a polynomial which vanishes (or evaluates to zero) over the trace domain. Therefore, we are particularly interested in vanishing polynomials over the trace domain, which is a twin-coset (or standard position coset).

Before diving into vanishing polynomial, let us first understand some properties of the squaring map, which will be used to express these vanishing polynomials.

The squaring map $\pi$ is a 2-to-1 map that reduces the twin-coset (or standard position coset) $D$ of size $N$ to a twin-coset (or standard position coset) of size $N / 2$. This property of $\pi$ is essential for halving the domain during the circle FFT. The squaring map corresponds to doubling the angle of each point on the unit circle.

The following animation shows the squaring map being applied to each point in the coset one by one, which is equivalent to doubling the angle of each point (represented by rotation). The process begins with the coset represented by blue points. By doubling the angle of each point, we obtain a coset of half the size, represented by red points. Similarly, applying the squaring map to the coset represented by orange points results in a coset of half the size, represented by purple points.

Thus applying the squaring map once to a twin-coset of size 8 (represented by blue and orange points) produces a twin-coset of size 4 (represented by red and purple points). More generally, applying the squaring map $n-1$ times to a twin coset $D$ of size $N=2^n$ gives a twin-coset of size 2, which is shown as follows:

If we project the points onto the $x$-axis, we will end up with their $x$-coordinate $X_D$.

where $\pi_x$ is the projection onto the $x$-axis. We can express the vanishing polynomial over the twin-coset $D$ as

The squaring map is itself a polynomial, given by $\pi(x + i y) = (2x^2 - 1) + i (2xy)$ Therefore, when it is iteratively composed with itself and the x-projection, the result is also a polynomial: the vanishing polynomial $v_D(X, Y)$. Note that $v_D(X, Y)$ evaluates to $0$ on all points of the twin-coset $D$.

As discussed earlier, the squaring map applied to a standard position coset gives a standard position coset of half the size. The following example illustrates the squaring map applied to a standard position coset of size $N=8$.

However, in the case of a standard position coset, after applying the squaring map $n-1$ times, the final points lie on the y-axis i.e. $X_D = 0$. Thus, the vanishing polynomial over a standard position coset $D$ of size $N=2^n$ is

Conclusion#

In this post, we explored the circle curve, the trace domain used in Circle STARKs (i.e. standard position coset or more generally the twin-coset), and the bivariate polynomials interpolated over this domain. In the next post, we will build on these concepts and delve into the circle FFT.