Explore Circle STARKs

In recent years, the trend in the design of STARKs protocols has been to shift towards using smaller fields. The earliest implementations of STARKs used 256-bit fields, but this design was less efficient. To address this issue, STARKs have started to move towards using smaller fields, such as Goldilocks, Mersenne31, and BabyBear.

This transformation greatly enhances the proof speed. For example, Starkware can prove 620,000 Poseidon2 hashes per second on an M3 laptop. This means that as long as Poseidon2 is trusted as a hash function, the challenges of efficient ZK-EVM can be addressed.

This article will explore how these technologies work, with a particular focus on Circle STARKs, a solution compatible with the Mersenne31 field.

Common Issues with Using Small Fields

When creating hash-based proofs, an important technique is to indirectly verify polynomial properties by evaluating the proof polynomial at random points. This greatly simplifies the proof process.

However, conducting such random sampling on small fields poses security issues. For instance, the Mersenne31 field has only about 2 billion possible sampling points, which is feasible for a determined attacker.

There are two solutions:

1. Conduct multiple random checks
2. Extended Field

Multiple checks are simple and effective, but there are efficiency issues. Expanding fields can provide more sampling point options, thereby improving security.

Regular FRI

The first step of the FRI protocol is to transform the computational problem into a polynomial equation. Then, it is proven that the proposed polynomial solution is indeed a valid polynomial and has a certain maximum degree.

FRI achieves this by gradually simplifying the problem of proving the degree of a polynomial to d into proving the degree to d/2. This process can be repeated multiple times, each time halving the size of the problem.

Every step of FRI reduces the polynomial degree and the size of the point set by half. The former is key to the functioning of FRI, while the latter allows the algorithm to run at high speed.

Circle FRI

The cleverness of Circle STARKs lies in its discovery of a group of size p that has a similar one-to-two property. This group is composed of points that satisfy specific conditions.

Starting from the second round, the mapping changes:

f_0(2x^2-1) = (F(x) + F(-x))/2

This mapping reduces the size of the point set by half each time.

Circle FFTs

The Circle group also supports FFT, and the construction method is similar to FRI. However, the objects processed by Circle FFT are not strictly polynomials, but rather the so-called Riemann-Roch spaces.

As a developer, you can almost ignore this. STARKs only require you to store the polynomial as a set of evaluation values. The only place where FFT is needed is for low-degree extension.

Business Operation

In Circle STARKs, due to the absence of a linear function that can be applied through a single point, different techniques need to be employed to replace traditional division methods.

We have to assess at two points to prove, thereby adding a virtual point that does not need to be focused on.

Vanishing Polynomial

In Circle STARKs, the form of the vanishing polynomial is:

Z_1(x,y) = y Z_2(x,y) = x
Z_{n+1}(x,y) = (2 * Z_n(x,y)^2) - 1

Reversed Order

The inverse order in Circle STARKs needs to be adjusted to reflect its special folding structure. Specifically, each position except the last one needs to be reversed, and the last position determines whether to flip the other positions.

Efficiency

Circle STARKs are very efficient. Compared to large field SNARKs, they can make better use of space in computation traces.

Binius is better than Circle STARKs in some ways, but at the cost of being conceptually more complex. In contrast, Circle STARKs are relatively simple conceptually.

Conclusion

Circle STARKs are not more complex for developers than conventional STARKs. Although the mathematics behind it is complex, this complexity is well hidden.

Combining technologies such as Mersenne31, BabyBear, and Binius, we seem to be approaching the efficiency limits of the STARKs base layer. Future optimization directions may include:

1. Maximize the efficiency of hash functions and signatures
2. Recursive construction to improve parallelism
3. Optimize the virtual machine to improve the development experience