Why I’m excited by Circle STARK and Stwo

15th Mar 2024

Research published last month represents one of the most exciting breakthroughs for scaling since the introduction of STARKs on Ethereum. The math is complex, but it uses the good old round-shaped circle (see Figure 1) to speed up STARK proving capacity by 100x and more.

The research was a collaboration between Ulrich Haböck from Polygon Labs and StarkWare’s David Levit and Shahar Papini. It will be used by many, and StarkWare is proud to be quickly putting it to practical use by building and open-sourcing the Stwo prover. In this writeup I’ll try to explain the math and its significance in the simplest way I can think of.

Figure 1

STARK Scalability and Transparency

I introduced the term STARK at the Stanford Blockchain Conference in 2017. STARK defines a set of protocols ensuring computational integrity, notably emphasizing Scalability and Transparency—the “S” and “T” in STARK, respectively. Scalability involves quick and cost-effective generation and verification of proofs of computational integrity, enabling public usage without dependence on extensive or expensive processes. This attribute is vital for applying integrity checks across different entities and has propelled StarkWare’s enhancements in blockchain computations.

Transparency within STARKs means eliminating ‘trusted setups’; all procedures are based on public randomness, reducing trust assumptions. This aspect is crucial for upholding computational integrity, particularly against influential entities that might exploit system parameters.

Together, Scalability and Transparency define the core of STARK technology, offering secure, scalable, transparent and public verification methods. Ensuring a proof system adheres to these principles is essential for maintaining effective and reliable operations. Whether you refer to your system as a STARK or call it by other names, be aware of the significant advantages that the double-pronged ‘scalability’ and ‘transparency’ offer, and do ask your local proof provider whether your proof system has both.

STARK Efficiency Means Small “Numbers”

In this section I’ll argue that computational efficiency means you’ll want to mold your proof system to best match the performance profile of modern computers. Which will lead us to crave using a specific prime number – the Mersenne prime $2^{31}-1$ .

All proof systems implemented in practice (and nearly all those discovered mathematically over the years) operate with special kinds of “numbers” that live inside the mathematical world of “finite fields”. There are many finite fields (infinitely many!) but let’s focus on the simplest members, called “prime fields”. A prime field is defined by a prime number p, like 5, and its “numbers” are $0, 1, \ldots,$ up to $p-1$ (so if $p=5$ our “numbers” are $0, 1, 2, 3,$ and $4$ ). Addition and multiplication are carried out in the finite field by first doing them the standard way, but then taking the remainder of the sum, or product, after dividing by $p$ . For example, when $p=5$ , we have $3+3=1$ (the remainder of 6 after division by 5) and $3 \times 3 =4$ (the remainder of $9$ when dividing by $5$ ). To use fewer words, we’ll write “ $3+3=1$ modulo $5$ ”, and “ $3 \times 3 = 4$ modulo $5$ ”, etc.

An important advantage of finite fields is that, well, they have finite size. This means that you’ll never need to worry about fractions, floating point operations, and arbitrarily large integers. The only “numbers” you’ll ever meet are $0, 1, \ldots,$ up to $p-1$ . So, if your prime is, say, smaller than $2^{32}$ you’ll be able to fit every “number” in a standard computer word, which saves space (computer words are 32 bits long). And when adding or multiplying, you’ll mostly be working with 32-bit words as well.

Stone, the very first STARK proof system in production, has been scaling Ethereum for the past four years, saving customers over $1B in fees. It is defined over a very large prime field, one that is of size roughly $2^{252}$ , which means storing a “number” requires eight computer words (each word is 32 bits). Adding and especially multiplying “numbers” takes quite a few computer cycles. To be precise, in Stone we clock an average of 38 cycles per multiplication. Stwo, announced last week, uses a smaller prime field, defined by the Mersenne prime $2^{31}-1$ and denoted M31. This means you can store a “number” in that field inside a single computer word and multiplication is much faster. Using vectorized operations we clock 0.3 cycles per multiplication, which is 125x faster than what we can do in Stone! (vectorized operations don’t help in the case of the Stone prime).

There are many prime numbers that fit inside a 32-bit word (the prime 5 is one of them) but there are good reasons to work with a prime that’s close to 2³². There are still quite a few other primes to select from but what makes the Mersenne prime M31= $2^{31}-1$ special is that some operations are very efficient over it because the number 2³¹ (the binary number 1,000,000,000,000,000,000,000,000,000,000, or 1 followed by 30 zeros) is equal to 1 modulo M31. Compared to another popular “small” prime number, the so-called Babybear prime (used by Risc0), which is the number $2^{31} - 2^{27}+1$ , on vectorized machines we clock M31 multiplication at ~1.3 times faster than Babybear multiplication. So, we’d really like to build our STARKs in the prime field defined by M31, but there’s a problem…

Efficiency Means Nice Multiplicative Structure

Finite fields have a lot of structure. For instance, if you consider only addition and you start adding a number (other than 0) to itself, you’ll see that you cover all numbers in the field, and then arrive back at where you started. For example, in the field defined by the prime 5, if we add 2 repeatedly we get this sequence: 2, 4, 1, 3, 0, 2, 4, 1, 3, 0,…, or the basic sequence {2,4,1,3,0} repeated infinitely many times. An interesting fact of prime fields is that no matter which non-zero number you start with, your basic recurring sequence will always be of length $p$ (try to prove this!)

Things are different when we get to multiplication. We’ll always get recurring structures but their period length depends on the number we start with. If we start with 2 (still fixing $p=5$ ) we generate the sequence 2, 4, 3, 1, 2, 4, 3, 1, … which has a period of length 4. But the number 4 generates the sequence 4,1,4,1,4,1,… which has a period of length 2, and the number 1 generates the sequence 1,1,1,1… which has a period of length 1.

For efficient STARKs, it’s crucial to choose a number $g$ within your field that, through repeated multiplication, generates a notably long basic sequence — ideally over 1,000,000. But you also need the size of this pattern to be an exact integer power of 2, like $2^{20}$ (which is greater than one million). If you’re wondering why we need this strange “power of 2” length, it’s because sequences of this structure have many similar sub-structures that hide one inside the other like some fractal pattern. What I mean is this. If $g$ generates a basic recurring pattern of length $2^{20}$ then $g^2$ generates the basic recurring sequence that is every other number in the first pattern and has size $2^{19}$ , and $(g^2)^2= g^4$ generates a recurring pattern of length $2^{18}$ (every fourth member) and so on. Notice we’ve already seen this at play: the patterns above generated by $2, 4 (=2^2)$ and $1 (=4^2)$ , working modulo the prime 5. If you’re wondering further why we need this “sub-sequence” property you’ll need to read more, in particular, about recursive algorithms and the amazing and ubiquitous Fast Fourier Transform (FFT) and its close relative the Number Theoretic Transform (NTT).

OK, so all we need is a generator $g$ inside the Mersenne field defined by $2^{31}-1$ , such that the multiplicative sequence generated by $g$ has length that is a large power of 2 (like $2^{20}$ ). Alas, no such $g$ exists! It turns out that the length of a recurring multiplicative sequence inside a field of size $p$ must divide $p-1$ with no remainder (we were lucky that both 2 and 4 divide 5-1). But for the Mersenne prime $p-1=2^{31}-2$ and this number doesn’t have a large power of 2 dividing it. In fact, the largest power of 2 that divides $2^{31}-2$ is simply 2 (can you find a recurring multiplicative sequence that has this size? Can you find more than one such pattern? If you’re curious about such questions, you’ll want to dive deeper into Finite Fields and their relatives – the Groups and Rings).

It seems we’re stuck. We need a generator $g$ inside the Mersenne field that generates a certain pattern but we also know, mathematically, that no such $g$ exists.

Think Outside the Box (or Field)

One of the beautiful aspects of mathematics is its capacity to offer generalizations that broaden our understanding and refine our solutions. So far we have concentrated on sequences resulting from the simple multiplication of a single number, g. But we can define sequences generated by pairs of numbers, and that’s exactly what we do when constructing the Circle STARK. A point $(x,y)$ lies on the circle if $x^2+y^2=1$ . We usually picture these points as lying on the good old circle, but mathematicians think differently. Notice that if we’re working in the prime field defined by 5, then $4^2+0^2=1$ , so the “point” $(4,0)$ lies on the circle. This is the point $(-1, 0)$ because 4 is the same as -1 in our field, if you add 1 to each of them, you get 0. We can identify four points on the circle : $(0,1), (-1,0), (0,-1),$ and $(0,1)$ and we can generate all of them if we start with the generator $(g_x, g_y) = (0,1)$ and apply a different law. Instead of generating from $x_{i+1}$ the element $x_i$ by setting $x_{i+1} = g\cdot x_i$ as we did in the multiplicative sequence above, we now move from a point $(x_i,y_i)$ on the circle to the point

(x_{i+1}, y_{i+1}) = (g_x * x_i - g_y * y_i, g_x *y_i + g_y *x_i) \ \ \ (*)

This way if we start with the point $(x_0,y_0) = (1,0)$ and apply the rule $(*)$ inductively with the generator $(g_x, g_y) = (0,1)$ , we get the recurring sequence $(1,0), (0,1), (-1,0), (0,-1),\ldots$

When working over the prime 5 we’ve not gained much because we already knew how to generate recurring sequences of length 4 via simple multiplication. But consider the prime 31 instead. Since 31-1=30=2*3*5, the longest sequence divisible by a power of 2 is a sequence of length 2 (can you find the sequence of length 2?). But over the circle we can find $32=2^5$ such points, generated by $(g_x,g_y) = (2,11)$ using the formula $(*)$ above (and starting with $(x_0, y_0) = (1,0)$ ).

It turns out that the number of points lying on the circle, defined over the Mersenne prime $2^{31}-1$ , is quite large. It is of size $2^{31}$ . And you can generate all $2^{31}$ numbers by starting with $(x_0,y_0) = (1,0)$ and applying the generator $(g_x,g_y)=(2,1268011823)$ using the law $(*)$ above (if you’re a developer, don’t trust my word – write it out in code; if you’re a mathematician – prove it, or read the circle STARK paper!).

So where does all of this leave us: we’re able to use the super-efficient Mersenne field for our arithmetic operations – multiplication is 125x faster than over the 252-bit Stone field and 1.3x faster than multiplication in the similar-sized Babybear field. Additionally, we have found the necessary repetitive structure (mathematically speaking, an “algebraic cyclic group”) that is large and of a size that is an exact power of 2, leading to the repetitive substructures of size ½ , ¼ etc, and the fast recursive algorithms associated with them.

From Circle STARK to Stwo?

Stwo (“STARK Two”) is the name of Starknet’s next-generation prover, set to augment, speed up, and ultimately replace the current prover – Stone (“STARK One”). Stwo’s efficiency, anticipated at 100x the speed of Stone, will use Circle STARKs over M31 (explained above) but also a lot more. Additional innovations include the “log-up” and sum-check protocols (as in this recent work by Haböck and Papini), working simultaneously with several polynomials of different degrees (“mixed degrees”) and new infrastructure for encoding circuits and virtual machines. So, while the expected improvement in STARK proving scale is roughly 100x over Stone, expect additional benefits such as more agile adoption of new compilers and virtual machines, leading to higher development velocity. Read here for more information about Stwo.

KZG Commitments and Pairing-Based SNARKs?

KZG commitments are the main competitor to the FRI protocol used by Stone, Stwo, and other STARKs and form the mathematical basis for many pairing-based SNARKs. Their main advantage is the extreme succinctness of the final proof, which famously takes around 200 Bytes (compared with dozens of KiloBytes required by FRI and current STARKs). An additional advantage they carry is a subsidy in the form of a precompile on Ethereum for a specific KZG parameter setting and integration into the core Ethereum protocol via DankSharding. These subsidies explain why many STARK systems (like those used by Polygon, RiscZero, and ZKsync) are finally wrapped inside a SNARK – to utilize the specific Ethereum pre-compile subsidy. As long as there are specific subsidies for certain proof systems expect more of the same – teams will consider wrapping their STARKs inside a SNARK. But with multiplication that is 100x faster and more on M31 compared to KZG-safe primes (current best practice calls for 380+ bits for such primes!), it is unlikely that KZG and pairing-based systems will be as efficient as Stwo in scale and throughput. While the field of elliptic curve mathematics and the scope of innovations carried out in the world of pairing-based SNARKs are breath-taking in beauty, we should remember that such SNARKs suffer not only in terms of efficiency but also require trusted setups and are prone to attacks by quantum computers. In other words, in terms of efficiency, security, and future-proofness, STARKs based on small finite fields are a better option.

Parting Thoughts

Circle STARKs mark an exciting advancement in the world of STARK technology, already transitioning from theory to practice. They stand as the latest milestone in the continually evolving legacy of STARK proofs, which are growing increasingly sophisticated. As we move forward, these proofs are set to meet new challenges and unlock applications beyond our current imagination.

It is a pleasure to see amazing and deep mathematics turn up in systems that will scale blockchains by orders of magnitude. The space referred to as “ZK” within blockchain has, more than once, taken cutting-edge “moon math” and built innovative products from it. Zcash with the first ZK-SNARK system for general circuits deployed to provide financial privacy on blockchain, STARKs as the first, most efficient, and future-proof scaling technology on Ethereum, and Cairo as the next-generation smart contract language for writing provable code, are examples. So, I’m eager to see what marvelous unforeseen applications and new math will be unleashed by Circle STARKs and Stwo.

Why I’m excited by Circle STARK and Stwo