Explore Circle STARKs

In recent years, the design of STARKs protocols has tended to use smaller fields. The earliest STARKs implementations used 256-bit fields, which are compatible with elliptic curve-based signatures. However, this design is less efficient and wastes computing power when handling large numbers. To address this issue, STARKs began to shift towards using smaller fields: first Goldilocks, then Mersenne31 and BabyBear.

This transformation has enhanced the proof speed. For example, Starkware can prove 620,000 Poseidon2 hash values per second on an M3 laptop. As long as we trust Poseidon2 as a hash function, we can solve the challenge of developing an efficient ZK-EVM. So how do these technologies work? How are these proofs established over smaller fields? This article will explore these details, with a particular focus on the Circle STARKs solution.

Common Issues with Using Smaller Mathematical Fields

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

For example, suppose the commitment of polynomial A needs to be generated, which must satisfy A^3(x) + x - A(ωx) = x^N. The protocol may require the selection of a random coordinate r and prove that A(r) + r - A(ωr) = r^N. Then backtrack A(r) = c, proving Q = (A - c)/(X - r) is a polynomial.

To prevent attacks, it is necessary to choose r only after the attacker provides A. In elliptic curve-based protocols, a random 256-bit number can be chosen. However, in STARKs with smaller fields, there are only about 2 billion possible r values, and the attacker may be able to brute-force crack it.

There are two solutions:

1. Conduct multiple random checks
2. Extended Field

Multiple random checks are simple and effective, but there are efficiency issues. The extension field is similar to a complex number, but based on a finite field. A new value α is introduced, declaring α^2 = a certain value. This allows for more complex calculations over the finite field. The extension field is only used in scenarios such as the FRI protocol, while most mathematical operations are still performed over the base field.

Regular FRI

When constructing a SNARK or STARK, the first step is arithmetization, which converts the computational problem into polynomial equations. To prove that there is a solution, it is necessary to demonstrate that the proposed values are reasonable polynomials with a maximum degree. For this, a step-by-step application of random linear combination techniques is used:

1. Suppose there is an evaluation value of polynomial A, we need to prove the degree < 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

Essentially, B isolates even coefficients, and C isolates odd coefficients. Given B and C, A can be recovered. If the degree of A < 2^20, the degrees of B and C are A's degree and A's degree - 1, respectively. D is a random linear combination, and the degree should be A's degree.

FRI simplifies the verification process 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 halving the problem.

To achieve a gradual reduction of the domain, a two-to-one mapping is used. This mapping allows for the dataset size to be halved and is repeatable. Starting from the multiplicative subgroup, the set S undergoes a squaring operation, and the new set S^2 retains the same properties. This allows for the continuous reduction of the dataset size until only one value remains.

The BabyBear modulus allows its maximum multiplicative subgroup to include all non-zero values, with a subgroup size of 2k-1. A subgroup of size 2^k can be selected, and then the FRI method can be applied to gradually reduce the polynomial degree to 15. The Mersenne31 modulus results in a multiplicative subgroup size of 2^31-1, which can only be divided by 2 once, after which the above technique cannot be used.

The Mersenne31 field is suitable for 32-bit CPU/GPU computations. Its modulus characteristics allow many operations to be completed using efficient bit manipulation. In the Mersenne31 field, arithmetic operations are approximately 1.3 times faster than in the BabyBear field. If FRI can be implemented in the Mersenne31 field, it will significantly enhance computational efficiency.

Circle FRI

The brilliance of Circle STARKs lies in the fact that, given a prime p, a group of size p can be found that has a similar one-to-two 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)

The double form is: 2 * (x,y) = (2x^2 - 1, 2xy)

We focus on the points at odd positions on the circle. First, we converge all the 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 law.

Circle FFTs

The Circle group also supports FFT, and its construction method is similar to FRI. The objects processed by Circle FFT are 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 used for low-degree extension: given N values, generate k*N values on the same polynomial.

Business Operations

In the STARK protocol, a common operation is to perform a quotient operation on specific points. For example, proving P(x)=y:

1. Calculate the quotient 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 single-point linear function, different techniques must be employed to replace traditional multiplicative operations. It is proven by evaluating at two points that an additional virtual point, which does not need to be focused on, is added.

If the polynomial P equals y1 at x1 and y2 at x2, choose the interpolation function L that equals y1 at x1 and y2 at x2: L = ((y2 - y1)/(x2 - x1)) * (x - x1) + y1

Then prove that P - L is zero at these two points, and prove that the quotient Q is a polynomial by dividing L by L.

Vanishing Polynomial

In STARK, polynomial equations usually take the form C(P(x), P(next(x))) = Z(x) · H(x), Z(x) is zero over the entire 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

The disappearance polynomial can be derived from the folding function: conventional STARK reuses x → x^2, and circular STARK reuses x → 2x^2 - 1.

Reverse Order

In STARKs, polynomial evaluation is usually arranged in reverse bit order. For example, when n=16: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

This sorting makes the values of the early groups in the FRI evaluation process adjacent in the order, saving space.

In circle STARKs, the folding structure is slightly different. To adjust the reverse bit order to reflect this structure, each bit except the last one needs to be inverted, with the last bit determining whether to flip the other bits.

Size 16 folded reverse order: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

Efficiency

Circle STARKs are very efficient. Calculations typically involve:

1. Native Arithmetic: Used for business logic
2. Native Arithmetic: Used in Cryptography
3. Find Parameters: General Efficient Calculation Methods

The key to efficiency lies in fully utilizing the computational tracking space. The size of Circle STARKs field is 2^31, which wastes less space.

Binius is better than Circle STARKs, allowing for the mixing of different sized fields, resulting in more efficient bit packing. However, the cost is a more complex concept, while the concept of Circle STARKs is relatively simple.

Conclusion

Circle STARKs are not more complex for developers than STARKs. Understanding Circle FRI and Circle FFTs can serve as a way to understand other special FFTs.

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

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