Ethereum creator Vitalik Buterin is back again with another creation he believes will take blockchain’s security to a whole new level. He calls it Circle STARKS, and I’m here to tell you everything you need to know about it.
Small fields changed the game
Circle STARKs is all about moving away from big, inefficient numbers to smaller, more manageable fields. Originally, STARKs used large 256-bit fields, but these were slow and wasted a lot of space.
Now, with smaller fields like Goldilocks, Mersenne31, and BabyBear, everything runs faster and more efficiently. Starkware, for instance, can now handle 620,000 Poseidon2 hashes per second on an M3 laptop.
Vitalik’s Circle STARKs, implemented in Starkware’s stwo and Polygon’s plonky3, offer unique solutions using the Mersenne31 field.
Related: Vitalik Buterin thinks investors are too excessive
One of the main tricks in making hash-based proofs, or any proof, is to prove something about a polynomial by evaluating it at a random point.
For example, if a proof system needs you to commit to a polynomial P(x), you might need to show P(z) = 0 for a random point z.
This is simpler than proving things directly about P(x). If you know z in advance, you could cheat by making P(x) fit that point. To stop this, z is chosen after the polynomial is provided, often by hashing the polynomial.
Related: Vitalik Buterin thinks politicians are playing the crypto industry
It works fine with large fields, like in elliptic curve protocols, but small fields pose a problem. With small fields, an attacker could just try all possible values for z, making it much easier to cheat.
To solve this, two main methods are used: multiple random checks and extension fields. The first is simple—check the polynomial at several points instead of just one. But this can get inefficient quickly.
The second method, using extension fields, involves creating new, complex numbers that make it harder to guess z.
The magic of Circle STARKs
Circle STARKs introduce a clever twist with Circle FRI. Given a prime p, there’s a group of size p-1 with properties that fit this method perfectly. For Mersenne31, this means using a set of points in a specific arrangement.
Credits: Vitalik Buterin
The points follow a pattern similar to trigonometry or complex multiplication, making the math work out neatly. In Circle FRI, points are collapsed and combined in a way that keeps reducing their size, making the process efficient.
Vitalik says this map doubles points on a circle, taking pairs of coordinates and converting them to new points. This method works well with existing 32-bit CPU/GPU operations, making it more efficient than BabyBear.
Fast Fourier Transforms (FFTs) follow a similar path, converting evaluations of polynomials to coefficients and back.
Circle FFTs work over what mathematicians call Riemann-Roch spaces, treating multiples of a base polynomial as zero, which simplifies the math.
In STARK protocols, you often need to prove that a polynomial equals zero at certain points. Normally, you can use a simple line function to show this. In Circle STARKs, it’s a bit trickier because the equivalent line function needs to meet stricter conditions.
To handle this, Circle STARKs use interpolants—functions that equal zero at two points. By subtracting and dividing by these interpolants, you can show that the resulting quotient is a polynomial.
Vanishing polynomials, which equal zero across an evaluation domain, also play a role. In regular STARKs, this is straightforward. In Circle STARKs, it involves repeating specific functions, which makes sure the math holds up.
As Vitalik puts it, “The complexity of circle math is encapsulated, not systemic.”
