The ZK Chronicles: Exotic Domains

Alright folks! Last time, we dedicated an entire article to building our understanding of STARKs from scratch. New computation model, new arithmetization, new commitment scheme, everything nice and shiny.

As it turns out though, there was a quiet assumption I told you guys not to worry about, but in fact, can become quite the problem: that our evaluation domain has $2^k$ elements, allowing us to fold during FRI without much of a hassle.

Or really, we need a multiplicative subgroup of size $2^k$.

Finding those is not that easy, and though we'll be more precise about that later, this should already spark some questions about what a suitable domain is.

Today, I want us to explore two such alternatives that may not seem like the usual candidates for interesting domains to work with. Even so, they have actually made some waves in the last few years for their incredible gains in efficiency, so it's definitely worth taking a look at them.

So let's see what we can do when we allow ourselves to work with some exotic domains!

Choosing the Right Field

I'm gonna kick things off with a rather strange question, but hear me out: why do proof systems have to work over large prime fields? I mean, we know we have to work with integers because of the discrete precision we know necessary for any cryptographic system, sure, and we also know that prime fields in particular have some very nice properties... but why do these fields need to be large?

The answer to this question lies in how polynomial identity testing works. When a verifier wants to check that two polynomials $f$ and $g$ are equal, they evaluate both at a random point $r$ and check $f(r) = g(r)$. By the Schwartz-Zippel lemma, if $f \neq g$ and both have degree at most $d$, then the probability of a false positive is at most $d / |\mathbb{F}|$. So for this check to be secure, you need the field to be much larger than $d$.

In practice, circuits can have millions of gates, so $d$ can easily be in the millions. If our field had only $2^{16}$ elements, a cheating prover would have a roughly 1 in 65536 chance of fooling the verifier per check. And while these may sound like fairly poor odds for the prover, it's actually quite the opposite: a cheating prover can easily skim through tens of thousands of values, and eventually forge a valid proof.

But with a 256-bit prime field though, that probability drops to near zero.

Thus, the size isn't arbitrary: it's the denominator in the soundness error. The field has to be large enough for random challenges to be truly unpredictable, and for collisions to be astronomically unlikely.

That's all great, and honestly it works wonderfully, but it comes with a hidden cost: computers do not know how to work with these large finite fields natively, because their original language is binary.

Which also happens to be a prime finite field, $\mathbb{F}_2$!

That's a problem, because we have to represent finite field elements in binary in order to perform any calculation on a CPU. And since the arithmetic is not natural, it requires careful handling. Plus, if you have to represent a tiny value as a, say, 64-bit number, you're essentially wasting a lot of space.

So, what if we tried speaking binary then? Well, binary has its own set of problems, because it's too small of a field for the Schwartz-Zippel lemma to work, given the soundness argument we discussed moments ago. So we may wonder... isn't there some sweet spot between the two options?

That's the same question Benjamin Diamond and Jim Posen from Irreducible probably asked themselves one fateful day a few years ago. Their solution to this matter is now known to the world as Binius.

Binius

That middle point we're talking about can be achieved by going back to an idea we explored during our first steps in this series.

Rather than univariate polynomials over a prime field (which has been our bread and butter for some time now), Binius uses multivariate polynomials evaluated on a boolean hypercube. And if you've been following along, this might sound familiar, because it's the same framework we explored earlier in the series in our pass through sum checks and multilinear extension, only that now it's applied natively over binary data.

But how does this actually work? Binary is still too small for the Schwartz-Zippel lemma to hold after all, so the soundness guarantees must come from a different place, right? Indeed! And that place is what we call field extensions.

I've covered this in my Elliptic Curves In-Depth series, so I recommend you go check that out for the full story!

In short, a field extension is built by adjoining to our field a new element, which is a root of an irreducible polynomial. Which sounds fancy, but is exactly how the complex numbers $\mathbb{C}$ extend the real numbers $\mathbb{R}$: by adding $i$, a root of $x^2 + 1$ (which is a polynomial that would otherwise have no solution).

Once we adjoin $i$ to our field, we can operate with it normally, meaning it can be used in additions and multiplications. Consequently, the elements of the extension are of the form $a + b \cdot i$, which is the same to say that they are pairs $(a, b)$ with $a, b$ in the base field (our original, unextended field).

We can use this idea to extend a binary field $\mathbb{F}_2$ by adjoining $\alpha$ (with the irreducible polynomial $x^2 + x + 1$, because $x^2 + 1$ is actually not irreducible in $\mathbb{F}_2$), which gives us a field with $2^2 = 4$ elements, where each element is just a pair of bits:

$$\mathbb{F}_{2^2} = \{0, 1, \alpha, \alpha + 1\}$$

Which correspond to the pairs $(0,0)$, $(1,0)$, $(0,1)$, $(1,1)$ respectively.

Okay, cool, but why stop there? What if we extend the resulting field yet again? Let's go nuts!

We can take our extension $\mathbb{F}_{2^2} = \{0, 1, \alpha, \alpha+1\}$ and adjoin yet another element $\beta$, a root of another irreducible polynomial over this field, like for example $x^2 + x + \alpha$ (you can easily check that none of the elements of $\mathbb{F}_{2^2}$ are roots of this polynomial). Which leaves us with this extended field, generated by considering all possible $a + \beta \cdot b$ combinations, with $a$ and $b$ in $\mathbb{F}_{2^2}$:

$$\mathbb{F}_{2^4} = \{0, 1, \alpha, \alpha + 1, \beta, \beta + 1, \alpha + \beta, \alpha + \beta + 1, \alpha \beta, \alpha \beta + 1, \alpha \beta + \alpha, \alpha \beta + \alpha + 1, \alpha \beta + \beta, \alpha \beta + \beta + 1, \alpha \beta + \alpha + \beta, \alpha \beta + \alpha + \beta + 1 \}$$

And would you look at that - this new field has a total of 16 elements, which is exactly the number of points in the binary hypercube $\{0,1\}^4$.

Which makes sense: each coordinate in the hypercube can be multiplied by $1$, $\alpha$, $\beta$, and $\alpha \beta$ respectively, yielding exactly $\mathbb{F}_{2^4}$. In formal terms, this means there's a bijection between $\{0,1\}^4$ and $\mathbb{F}_{2^4}$ - but no need to worry about these formalisms too much!

And again, why stop there? We can continue doing this over and over, eventually getting to fields with $2^8$ elements, or $2^{16}$, $2^{32}$, and so on, each level being a new (degree-2) extension of the previous one.

What we have just built is called a tower of binary fields. We started from a single bit, and eventually worked our way to an extended field that's large enough for Schwartz-Zippel to actually work!

By the way, fields of the form $\mathbb{F}_{2^k}$ are often called Galois fields, denoted $GF(2^k)$ - the same notation you'll find behind AES's S-box or Reed-Solomon codes. It's the exact same construction we just walked through, just under a different name.

However, since we're really dealing with binary vectors in disguise (remember, there's a 1-to-1 mapping between the field extension and a boolean hypercube), we don't really use univariate polynomials, but multivariate polynomials with several binary variables!

The field extension framework is really just the underlying machinery to understand why Schwartz-Zippel makes sense in this context!

And because every element is now a sequence of bits, operations like $\text{XOR}$, $\text{AND}$, or bit shifts become absolutely native. And practically, this means that Binius can offer substantial performance gains for workloads that heavily rely on hash functions, bitwise operations, and byte manipulations, which happen to be exactly what CPU execution traces look like!

While all this sounds nice, we've just described how Binius treats its domain of choice, but there's of course more to the full proving system. For example, it uses a multilinear commitment scheme different from KZG or FRI, and there are even some sum checks in the mix (circuits are represented in a similar fashion to GKR). The paper goes into full detail about these nuances, and it's definitely a worthwhile read.

Having said that, it should be noted that the zkVM space (a concept we'll discuss in a few articles) has taken notice of Binius, and some key players like Jolt have already borrowed concepts from Binius for their implementations.

Plus, the Irreducible team has continued iterating: Binius64 is a newer version that works natively over 64-bit words, introducing dedicated constraints for 64-bit operations. This achieves a 64-fold reduction in constraint complexity compared to bit-level approaches, while keeping all the efficiency advantages of binary field arithmetic.

All in all, it's a very interesting take on circuit handling, with very elegant mathematical machinery backing it up!

When Finite Fields Aren't Enough

If binary wasn't "exotic" enough for you... oh boy, get ready for this one!

Remember how in FRI, we repeatedly performed halving operations over the evaluation domain? For that to work, I mentioned how we need our domain to have $2^k$ elements, which means we need to find a multiplicative subgroup of said size.

Alas, that's actually easier said than done. For example, Mersenne31 is one of the most popular prime fields used for modern applications. But you know what it does not have? A large power-of-two multiplicative subgroup! Which translates directly into "yeah, you cannot run standard FRI over it".

In order to try and circumvent these problems, we need to think a little more carefully about what we actually need from the domain. Concretely, FRI requires a domain $D$ such that:

1. Every element of $D$ has a "partner": two elements that collapse to the same value under some squaring-like operation. This is the symmetric structure that enables the folding.
2. Applying that map to the whole domain produces a new domain $D'$ that is exactly half the size, and has the same structure. This is what enables recursion.
3. The process continues cleanly all the way down to a single element, so crucially, the domain size must be a power of two.

The multiplicative subgroup trick works wonderfully because squaring ($x \mapsto x^2$) is the natural "collapse" map, and pairs $\{x, -x\}$ are the natural partners we're looking for. But again, this requires a subgroup of size $2^k$ to exist in $\mathbb{F}_p$, and for Mersenne31 and many other finite fields of interest out there, that's just not the case.

So our goal now is to try and find a different group that naturally has size $2^k$. And it would be interesting to try and do so over a known field, such as Mersenne31, so that we can preserve all the efficiency it brings along.

By the way, the efficiency of Mersenne31 in particular comes from the shape of its prime modulus. Mersenne primes are of the form $2^k {-} 1$, which in binary is just $k$ ones in a row. This special structure means that reducing a value modulo $p$ can be done with a simple bit shift and addition rather than a full division, making Mersenne31 modular reductions virtually free!

It turns out such groups exist, but they come from a totally unexpected place: a circle.

Circle STARKs

Oh yeah, you heard that right! Here, consider the set of points $(x, y)$ in $\mathbb{F}_p \times \mathbb{F}_p$ that lie on the unit circle:

$$C(\mathbb{F}_p) = \{(x, y) \in \mathbb{F}_p^2 : x^2 + y^2 = 1\}$$

Would you believe me if I told you this is actually a group? Or, rather than asking you to believe me, let me show you how that would work: we can define an addition law for points on this circle like so:

$$(x_1, y_1) \cdot (x_2, y_2) = (x_1 x_2 {-} y_1 y_2, \; x_1 y_2 + x_2 y_1)$$

If you've worked with complex numbers before, you may recognize this as the multiplication rule for complex numbers of norm 1, transplanted into a finite field:

$$(\cos\alpha + i\sin\alpha)(\cos\beta + i\sin\beta) = (\cos\alpha\cos\beta {-} \sin\alpha\sin\beta) + i(\cos\alpha\sin\beta + \sin\alpha\cos\beta)$$

Or it may ring a bell from your trigonometry memories, as the identities for angle addition:

$$\begin{gathered} \cos(\alpha + \beta) = \cos\alpha\cos\beta {-} \sin\alpha\sin\beta \\ \sin(\alpha + \beta) = \cos\alpha\sin\beta + \sin\alpha\cos\beta \end{gathered}$$

Indeed, circle groups are very well studied, so this is not a wildly novel development per se. Part of what makes this so interesting for us is precisely how well-studied they are, because it allows us to make some pretty important observations. In particular, for any prime such that $p \equiv 3 \pmod{4}$, the circle group $C(\mathbb{F}_p)$ happens to have exactly $p + 1$ elements. For Mersenne31, we have $p = 2^{31} {-} 1$, so we get:

$$|C(\mathbb{F}_{2^{31}-1})| = 2^{31}$$

Which is a power of two. Just what we needed!

The theory behind these seemingly simple affirmations actually runs quite deep, touching on proofs from number theory that are probably too much of a detour for the purposes of this article.

So I'll just ask you to believe me on this one!

The squaring map follows directly from applying our multiplication map as $(x,y) \cdot (x,y)$.

$$\pi: (x, y) \mapsto (2x^2 {-} 1, \; 2xy)$$

On the real circle, doubling an angle corresponds to a couple trigonometric identities: $\cos(2\theta) = 2\cos^2\theta {-} 1$ and $\sin(2\theta) = 2\sin\theta\cos\theta$.

And there we have our two-to-one collapse! The natural "partners" on the circle are the antipodal pairs $(x, y)$ and $({-}x, -y)$, which always collapse to the same point under $\pi$:

$$\pi({-}x, -y) = (2({-}x)^2 {-} 1, \; 2({-}x)({-}y)) = (2x^2 {-} 1, \; 2xy) = \pi(x, y)$$

So in sum, this is the circle-group analogue of the $\{x, -x\}$ symmetry in standard FRI.

Applying $\pi$ to every element of a domain of size $2^k$ produces a domain of size $2^{k-1}$, and this new domain has exactly the same circle-group structure. With this, we can use recursion just like in standard FRI, until we reach a single point. The fold formula only has to be adapted from the standard one to use the antipodal pair $(x, y)$ and $({-}x, -y)$ in place of $\{x, -x\}$.

And this is, in essence, what circle STARKs do: they swap the multiplicative subgroup domain for the circle group $C(\mathbb{F}_p)$, and replace the squaring map with the doubling map $\pi$. Everything else (the split-and-fold structure, the Merkle commitments, the query phase) is essentially unchanged.

Polynomial Evaluation

Although, it's not that everything is exactly the same, as working with the circle group does require some adjustments to the polynomial theory.

You see, on a multiplicative subgroup, polynomials are just ordinary univariate polynomials over $\mathbb{F}_p$: all we do is evaluate $f(x)$ at a field element, and we're done. But what do we do on the circle? The domain is now comprised of pairs $(x, y)$ satisfying $x^2 + y^2 = 1$. So you'd imagine polynomials should be bivariate ($f(x,y)$), right?

Well, yes and no. It's true that they should be, but there's also the relation $x^2 + y^2 = 1$ that must hold for all points in the domain! That means that $y$ is never a "free" variable, and it's actually locked into the value $y^2 = 1 {-} x^2$. And that means we can do some interesting manipulations.

Imagine we start with the full bivariate polynomial $f(x,y)$. Any monomial on $f$ will look like $x^a y^b$, right? So what we can do is peel off the $y^2$ term, like this:

$$x^a y^b = x^a \cdot y^{b-2} \cdot y^2 = x^a \cdot y^{b-2} \cdot (1 {-} x^2) = x^a y^{b-2} {-} x^{a+2} y^{b-2}$$

You see what happened there? We've traded powers of $y$ for powers of $x$!

And we can keep doing this until we're left with terms containing either $y^0$ (which is just a term without $y$), or $y$. Therefore, the entire polynomial reduces to this form:

$$f(x,y) = f_0(x) + y \cdot f_1(x)$$

Which is essentially a pair of univariate polynomials, one for the "even" part and one for the "odd" part of the original bivariate polynomial.

This is usually just stated as working over the polynomial ring $\mathbb{F}_p[X, Y] / (X^2 + Y^2 {-} 1)$, sometimes called a "Riemann-Roch space". But I think that's fairly opaque, and taking the time to look at what this materializes to does pay off!

This form also turns out to be exactly right for FRI. Folding works by splitting $f$ into even and odd parts using the domain's natural symmetry, which in standard FRI, was just $x \leftrightarrow -x$. But here, the analogous symmetry is the antipodal pair $(x,y) \leftrightarrow (x,-y)$, and since $f = f_0(x) + y \cdot f_1(x)$, flipping $y$ cleanly separates the two parts, leaving $f_0$ and $f_1$ as the natural even and odd halves to fold.

And that's all we need!

I guess you might be wondering whether this whole situation is even worth it, and let me tell you: it is.

As I mentioned earlier, Mersenne31's arithmetic is incredibly fast on modern hardware. Circle STARKs unlock that speed without sacrificing the power-of-two domain structure that FRI requires, so it's the best of both worlds!

To give you some rough numbers, StarkWare's Stwo prover (which implements Circle STARKs) reports roughly a 100× speedup over their previous prover, and has already reached production on Starknet. Ever since, proving systems like Plonky3 have also adopted the approach, so the benefits of this approach are really catching fire across the ecosystem.

Summary

This was a bit of a different one, wasn't it?

But I think the message is pretty clear: improving the proof systems themselves is great, but there may be a lot to gain from challenging the very foundations they sit on top of!

And this is especially true in the field of post-quantum cryptography (and ZK), where some of the primitives we've been using so lightheartedly become obsolete!

We'll have to wait and see where this goes as time goes by, but in the meantime, it's good to keep an open mindset.

But now, it's time to get back on track with more proving mechanisms.

So far in the series, we've been heavily relying on the circuit model, with STARKs (and circle STARKs) representing our first significant departure from this model in a while.

I guess it might be odd for me to ask this now after insisting so much with this model, but it's a valid question nonetheless: do we always need to think in terms of circuits? After all, we're really proving stuff about NP relations, of which circuit evaluations are just an example. So there might be other ways to go about this endeavor.

In particular, there's yet another case I'd like to cover, in which neither circuits nor the state transition functions we saw today might be the most suitable model.

This is the case of lookup arguments, which will be the topic for our next encounter.

Until then!