Explore Circle STARKs

In recent years, the design of the STARKs protocol has tended towards the use of smaller fields. The earliest STARKs implementations used 256-bit fields for modular arithmetic with large numbers, compatible with elliptic curve-based signatures. However, this design was less efficient and wasted computational power in handling large numbers. To address this issue, STARKs began using smaller fields: Goldilocks, Mersenne31, and BabyBear.

This transformation enhances proof speed. For example, Starkware can prove 620,000 Poseidon2 hash values per second on an M3 notebook. As long as Poseidon2 is trusted as a hash function, the challenge of efficient ZK-EVM development can be addressed. So how do these technologies work? How are proofs established over small fields? This article will explore these details, with a particular focus on the Circle STARKs solution.

Common Questions About Using Small Fields

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

For example, suppose we want to prove that the polynomial A satisfies A^3(x) + x - A(ωx) = x^N. The protocol may require selecting a random coordinate r and proving A(r) + r - A(ωr) = r^N. Then, we can infer A(r) = c, proving Q = (A - c)/(X - r) is a polynomial.

To prevent attacks, it is necessary to choose r after the attacker provides A. In a 256-bit field, this is straightforward: simply choose a random 256-bit number. However, in a small field, there are only about 2 billion possible r values, and although the attacker has a large workload, they may still attempt all possibilities.

There are two solutions:

1. Conduct multiple random checks
2. Extended Field

Multiple checks are simple and effective, but there are efficiency issues. The extended field is similar to a plural, but based on a finite field. A new value α is introduced to satisfy a certain relation, such as α^2 = a certain value. This creates a new mathematical structure that allows for more complex operations over a finite field. The extended field is only used when random linear combinations are needed, while most operations are still performed in the base field.

Regular FRI

The first step in constructing a SNARK or STARK is to transform the computational problem into a polynomial equation P(X,Y,Z)=0. The solution needs to prove that the proposed values are reasonable polynomials with a finite degree. This is achieved by incrementally applying random linear combinations:

1. Suppose there is an evaluation value of polynomial A, to prove that the degree is <2^20.
2. Consider B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
3. D is a random linear combination of B and C: D = B + rC

B isolates the even coefficients of A, and C isolates the odd coefficients. Given B and C, A can be recovered: A(x) = B(x^2) + xC(x^2). If the degree of A < 2^20, the degrees of B and C are the degree of A and the degree of A - 1, respectively. D, as a random combination, should have the degree of A.

FRI simplifies verification by reducing the proof of polynomial degree d to a proof of degree d/2. This process can be repeated multiple times, each time halving the problem. If the output at any stage does not meet the expected degree, that round of verification will fail.

FRI reduces the polynomial degree and the size of the point set by half at each step. The former is key to the functioning of FRI, while the latter allows the algorithm to run extremely fast: the total computational cost is O(N) instead of O(N*log(N)).

To achieve a gradual reduction of the domain, a two-to-one mapping is used. This mapping allows the dataset size to be halved and is repeatable. Starting from the multiplicative subgroup, the multiple 2x of each element x is also in the set. Squaring the set S, the new set S^2 retains the same property. This allows for the continuous reduction of the dataset size until only one value remains.

The modulus of BabyBear allows its maximum multiplicative subgroup to contain all non-zero values, with a size of 2^k-1. This is very suitable for the aforementioned technique, as it can effectively reduce the polynomial degree through repeated mappings. The multiplicative subgroup size of Mersenne31 is 2^31-1, which can only be divided by 2 once, after which this technique cannot be used.

The Mersenne31 field is very suitable for 32-bit CPU/GPU operations. Its modulus characteristic (, such as 2^31-1), allows many operations to utilize efficient bit manipulation: results exceeding the modulus can be reduced by shifting. Multiplication can be efficiently processed with specific CPU instructions. Arithmetic operations in Mersenne31 are about 1.3 times faster than BabyBear. If FRI can be implemented in Mersenne31, it would significantly improve efficiency.

Circle FRI

The cleverness of Circle STARKs lies in the fact that, given a prime number p, a group of size p can be found that has a similar two-to-one property. This group consists of points that satisfy specific conditions, such as the set of points where x^2 mod p equals a certain value.

These points follow the additive rule: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1) Double form: 2*(x,y) = (2x^2 - 1, 2xy)

We focus on the points at odd positions on the circle. First, we converge all points onto a straight line: f0(x) = (F(x,y) + F(x,-y))/2

Then perform a random linear combination to obtain the one-dimensional polynomial P(x).

From the second round, the mapping becomes: f0(2x^2-1) = (F(x) + F(-x))/2

This mapping halves the size of the set each time. Each x represents two points: (x,y) and (x,-y). (x → 2x^2 - 1) is the point doubling rule. We convert the x coordinates of two opposite points on the circle to the x coordinates of the doubled points.

Circle FFTs

The Circle group also supports FFT, with a construction method similar to FRI. The key difference is that Circle FFT processes not strict polynomials, but Riemann-Roch spaces: polynomials modulo the circle (x^2 + y^2 - 1 = 0).

The coefficients output by Circle FFT are specific bases: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}

Developers can almost ignore this point. STARKs only need to store polynomials as a set of evaluation values. FFT is only used for low-degree expansion: given N values, generate k*N values on the same polynomial.

Business Operations

Common operations in STARK involve performing arithmetic on specific points. For example, proving P(x)=y can be done through the following steps:

1. Calculation of the ratio: Q = (P - y)/(X - x)
2. Prove that Q is a polynomial and not a fraction

In the circle group STARK, due to the lack of a linear function through a single point, different techniques are required. A tangent function can be constructed, but it has a multiplicity of 2 at the point. Therefore, it must be evaluated at two points to prove.

If P equals y1 at x1 and y2 at x2, we choose the interpolation function L to be equal at these two points. Then prove that P - L is zero at these two points, and by dividing L by L, show that the quotient Q is a polynomial.

Vanishing Polynomial

The polynomial equations that STARK attempts to prove are typically of the form C(P(x), P(next(x))) = Z(x) · H(x), where Z(x) is identically zero in the original evaluation domain.

In the circular STARK, the corresponding function is: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

Reverse Order

Polynomial evaluations in STARKs are usually arranged in reverse bit order. In circle STARKs, the folding structure is slightly different:

• Step 1: Pair (x,y) with (x,-y)
• Step two: Pair x with -x
• Next steps: pair p and q, so that Q^i(p) = -Q^i(q)

To adjust the reverse order, each digit except the last one needs to be reversed, with the last digit determining whether to flip the other digits.

Efficiency

Circle STARKs are very efficient. Calculations usually involve:

1. Native Arithmetic: Used for business logic
2. Native Arithmetic: Used for cryptography ( such as Poseidon hash )
3. Find Parameters: General Efficient Computing Methods

The key to efficiency lies in fully utilizing the computational tracking space. Here, the field size is 2^31, which does not waste much space. Hashes like Poseidon make full use of every bit of each number in any field.

Binius achieves more efficient bit packing by mixing fields of different sizes, but at the cost of a more complex concept. Circle STARKs are conceptually relatively simple.

Conclusion

Circle STARKs are not more complex for developers than STARKs. The main differences in implementation compared to conventional FRI lie in the three issues mentioned above. Although the underlying mathematics is complex, this complexity is well hidden.

Understanding Circle FRI and FFTs can serve as a pathway to understand other special FFTs, such as binary field FFTs and elliptic curve FFTs.

Combining technologies such as Mersenne31, BabyBear, and Binius, we are approaching the efficiency limits of the STARKs base layer. Future optimizations may focus on:

1. Maximize the arithmetic efficiency of hash functions, signatures, etc.
2. Recursive construction to enable more parallelization
3. Arithmetic Virtual Machine to Improve Developer Experience