Explore Circle STARKs

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

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

This article will explore how these technologies work, with a particular focus on Circle STARKs, a scheme 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 through the evaluation of the polynomial at random points. This significantly simplifies the proof process.

To prevent attacks, we need to choose random points after the attacker provides the polynomial. This is straightforward in a 256-bit field, but in smaller fields, the selectable random values are too few and can be easily brute-forced by attackers.

There are two solutions:

1. Conduct multiple random inspections
2. Extended Fields

Multiple random checks are simple and effective, but have relatively low efficiency. Extended fields are similar to plural, allowing for more complex calculations over finite fields.

Regular FRI

The first step of the FRI protocol is to transform the computational problem into a polynomial equation. Then, it proves that the proposed polynomial solution indeed satisfies the equation and does not exceed the required degree.

FRI verifies by reducing the problem of proving a polynomial degree of d to the problem of proving a degree of d/2. This process can be repeated multiple times, each time simplifying the problem by half.

The key to FRI is using a 2-to-1 mapping to reduce the dataset size by half. This mapping needs to be repeatable until only one value remains.

Circle FRI

The cleverness of Circle STARKs lies in the fact that for a prime p, a group of size p can be found that has a similar one-to-one correspondence. This group consists of points that satisfy specific conditions.

These points follow an additive pattern, similar to trigonometric functions or complex multiplication.

Starting from the second round, the mapping changes. Each x represents two points: (x,y) and (x,-y). (x → 2x^2 - 1) is the point doubling rule.

Circle FFTs

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

As a developer, you can almost ignore these details. Just store the polynomial as an evaluation value and use FFT when low-level scaling is needed.

Quotienting

In the STARK of the circle group, due to the absence of a single-point linear function, different techniques are required to replace traditional multiplication operations.

We demonstrate by evaluating at two points that adding a virtual point.

Vanishing polynomials

In circular STARK, 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

Reverse bit order

In STARKs, polynomial evaluations are usually arranged in reverse order. In Circle STARKs, this ordering needs to be adjusted to reflect its special folding structure.

Efficiency

Circle STARKs are very efficient. The key is to make full use of the space in computation tracing for useful work, without leaving a lot of idle space.

Compared to Binius, Circle STARKs are conceptually simpler, but slightly less efficient.

Conclusion

Circle STARKs are not more complex for developers than conventional STARKs. Understanding Circle FRI and FFTs helps in understanding other special FFTs.

Future STARK optimizations may focus on:

1. Maximize the efficiency of hash functions and other basic cryptographic primitives.
2. Recursive construction to enhance parallelization
3. Arithmetic Virtual Machine to Improve Development Experience