The ZK Chronicles: STARKs

Last time, we ended things with a cliffhanger question. After spending the bulk of the previous two articles explaining a couple pivotal proving systems, we noted that both require a trusted setup. So we asked ourselves: could we go fully transparent?

You know, avoid those pesky toxic waste values altogether!

On that account, there's one particular system that rises to the occasion: STARKs.

STARKs replace the entire cryptographic machinery of traditional SNARKs with something that feels almost mundane in comparison: hash functions. But don't let that fool you - that seemingly modest swap turns out to have some pretty amazing consequences.

This article is gonna be quite action-packed, since we're gonna need to introduce a new arithmetization layer, and from there, we'll see what the execution trace looks like, how the interactive proof is laid out, and then we'll even throw a new technique into the mix to tie it all together.

With that, the context is set. Vamos!

The Acronym

Let's begin by focusing on the name for a moment, so as to know what to expect for today.

STARK is once again an acronym, which stands for Scalable, Transparent, Arguments of Knowledge. And you see, it's quite the deliberate choice of naming, since being scalable and transparent are two areas where the SNARKs we've talked about struggle!

It was the way the authors chose to say "hey, check this out! We can do something differently and better than before!".

But what do those concepts mean? Well, transparent is probably the most obvious one, since it's what got us here in the first place: it means we won't ever require any trusted setup. The entire commitment infrastructure we'll be working with is built from hash functions and Merkle trees, so nothing is generated and discarded, nor kept and abused. The verifier can reproduce every public parameter from scratch, independently, with total confidence.

Scalable is perhaps the less evident claim here. I mean, weren't SNARKs already succinct?

Well, yes... but that's only in reference to their proof size and verification time. Scalable takes on a different meaning here, specifically referring to how verification time scales with the length of a computation.

For SNARKs built on arithmetic circuits, the verifier typically needs to read the entire circuit structure, so large circuits mean slow verification. And I guess there isn't much we can do anyway, right? I mean, since the circuit was such an integral element in our analysis so far...

Well, surprise surprise, STARKs sidestep this by using an entirely different computation model!

It's not like we're ditching the circuit model altogether though - this is more about recognizing that a single circuit to represent an entire computation is not always the best choice. This is a trend that we'll be touching upon in articles to come, so definitely keep this in mind!

Alright! So those are the two things STARKs set out to accomplish: being scalable and transparent.

And as a nice addition, the exclusive use of hashing functions gives STARKs a level of robustness that makes them resist quantum computer attacks. Hash functions are themselves expected to withstand quantum attacks in a way that pairing-based schemes are not. So by swapping KZG for Merkle trees, STARKs inherit this property essentially for free!

Not a simple couple of things to ask for, of course, but STARKs manage to check both boxes.

So let's see how they do it, starting with this new mysterious computation model!

A Different Kind of Computation

There's good reason as to why the proof systems we've built so far represent computations as arithmetic circuits.

For starters, circuits are a universal way to represent NP relations. They are also simple and flexibile, and importantly, they can be arithmetized, which allows us to craft nice polynomial identities that are ideal for building proving systems around them.

Nevertheless, and despite all these wonderful characteristics, there's an implicit assumption baked into the circuit model that can become a limitation: circuits are fixed, and must be fully described upfront.

In other words, every single gate needs to be specified, wired, and committed to before we do anything else. Not that this is bad per se, but just imagine that a hash function was applied ten thousand times in a row. We'd get a circuit with ten thousand copies of the same sub-circuit, chained time and time again, and the verifier would still need to read the entirety of that enormous circuit.

Why you'd want hash ten thousand times is a different question!

Though clearly intentionally manufactured, this particular example is a clear hint at an alternative approach: what if there was a way to describe a single step (like the single hash application), and then present evidence that it was correctly applied ten thousand consecutive times? That would be far more compact, and the verifier would only need to read that one-step description!

Squirtles looking down a trap hole — Nice, nice, nice, nice, nice

Indeed, this is an alternative way to think about computations. It's all good and dandy with circuits (and to be fair, they work perfectly fine in the right situations), but this is not the only way we can prescribe a computation, let alone always the most convenient.

In this case, for example, it's much more helpful to define a current state, and prescribe the way we advance that state through a single function executed multiple times:

S_{t+1} = f(S_t)

Here, $S_t$ is the state at step $t$ , and it's just a vector of $w$ field elements ( $w$ is usually called the width of the state). And $f: {\mathbb{F}_p}^w \to {\mathbb{F}_p}^w$ is the transition rule or state transition function, and is where computation is described.

Therefore, the full computation starts from an initial state $S_0$ , and consists of applying $f$ over and over a total of $T$ times, eventually reaching the final state $S_T$ . The prover's job then will be to demonstrate that their sequence of states is valid, meaning each consecutive pair $(S_t, S_{t+1})$ satisfies the transition function.

It's very important to clarify that not every computation fits neatly into this mold. Our new model requires a high degree of uniformity throughout execution.

In other words, computations that vary step-by-step will not fare too well with this model, while things like a hash chain or the execution of a virtual machine are natural fits!

Crucially, this way of framing the process means that a verifier does not need to inspect a large circuit (of size $T \cdot |f|$ ) in order to know what to check to determine that a computation is valid. They only need to know $f$ , and perform a few random checks. And that's where the scalability comes from!

Okay, that sounds promising! How about we see it in action with an example?

The Fibonacci State Transition

The simplest toy example I've come across is the Fibonacci sequence, where each number is the sum of the two that come before it. Starting from the seed values $(1, 1)$ , you'd get the sequence $2$ , $3$ , $5$ , $8$ , $13$ , $21$ , and so on.

It's very easy to model this process with a simple state vector of width $w = 2$ , and the following transition:

f(a, b) = (b, \; a + b)

There's an even more compact way to write this, to calculate the next two numbers on each step! Can you see what it is?

So, starting from $(a_0, b_0) = (1, 1)$ , successive applications of the state transition function look like this:

Step	$a$	$b$
$t=0$	1	1
$t=1$	1	2
$t=2$	2	3
$t=3$	3	5
$t=4$	5	8
...	...	...

With a total of $T$ rows and $w$ columns, that table right there is none other than the execution trace for the computation: the full record of every state obtained as $f$ was applied. And it's of course the prover's witness, which simply means it's the private evidence for the correct execution of the computation.

This table format feels familiar, right?

After all, we've had to deal with something similar in our passage through PLONK.

And I'm sure you know exactly how to do that: polynomials!

Crafting the Polynomials

Exactly! We can use the exact same technique we used before: all we do is encode each column of the trace via interpolation, and use the resulting polynomials to build some nice identities that can be checked!

If it ain't broken, don't fix it!

Thus, we'll need to define a polynomial $T_i(X)$ for each of the columns in the trace, so that it encodes all the values in each column. Of course, we'll be using the $T$ -th roots of unity $H = \{1, \omega, \omega^2, \ldots, \omega^{T-1}\}$ as our evaluation domain:

T_i(\omega^t) = S_i^{(t)}

In our Fibonacci example, $T_0(\omega^t) = a_t$ and $T_1(\omega^t) = b_t$ for each row $t$ .

We call these the trace polynomials (yeah, surprise!). Their sole purpose is to encode the data in the execution trace, which means that in a similar spirit to one of the limitations we discussed when analyzing PLONK, these polynomials don't really tell us much about the rules of the state transition.

So they alone will not be enough.

By the way, there's something we can already say about these polynomials: they have degree at most $T {-} 1$ . I know this might not sound important right now, but it will become so very soon. Keep this information in mind!

On top of the trace polynomials, we need a way to capture the state transition as another type of constraint. Again, we can try to take some inspiration from our toy Fibonacci example to imagine how this would look like. In this case, we'd have two constraints:

$a_{t+1} = b_t$ (the first register advances to the value of the second)
$b_{t+1} = a_t + b_t$ (the second register becomes the sum of the two previous values)

But remember, those values are already encoded in our trace polynomials! Can you see where this is going?

All we need to do is use the trace polynomials to build a couple simple expressions that represent the state transitions! In this case, we'd have something like this:

C_0(X) = T_0(\omega X) {-} T_1(X)

C_1(X) = T_1(\omega X) {-} T_0(X) {-} T_1(X)

That $\omega X$ right there is a neat little trick. For any value $X = \omega^k$ in the evaluation domain, $\omega X$ = $\omega^{k+1}$ . So what that expression is saying is just "evaluate the polynomial on the next row"!

These new expressions are also polynomials, and they receive the (rather obvious) name of constraint polynomials. Since this is not our first rodeo, I'll get straight to the point: if these relations hold on every row, then both constraint polynomials will have their roots in the evaluation domain (the $T$ -th roots of unity). So you can probably imagine how we can treat this, because it's the same thing we've been doing for a couple articles now!

Yeah, don't be shy, you probably guessed it: the constraint polynomials should be perfectly divisible by some vanishing polynomial, and we can build a QAP-style polynomial identity!

C_i(X) = Q_i(X) \cdot V(X)

Where:

V(X) = \prod_{t=0}^{T-1}(X {-} \omega^t) = X^T {-} 1

And of course, if the trace is not valid, the vanishing polynomial will not divide the constraint polynomials, which we should be able to catch easily by requesting evaluations, much like we did in PLONK, and aided by the power of the Schwartz-Zippel lemma.

Nothing too crazy so far! Or at least, nothing too different from what we're accustomed to.

But if we take a closer look, we'll notice something is still missing.

Anchoring the Endpoints

Okay, so we've got most of the execution trace covered by now. However, the constraint polynomials only describe what to expect from the transitions between consecutive states. But where do those transitions start, and where do they end?

You see, any sequence of valid steps will satisfy the transition constraints, even one that starts from an invalid or wrong initial state. Our constraint polynomials fail to capture this, and obviously, if we're trying to prove that some computation is valid, we need to account for these boundaries of our computation as well.

So what do we do about this? We just throw a couple more constraints at it!

Yup! We'll have to define a new, separate set of constraints to pin down the boundaries of the computation. And of course, we'll call these the boundary constraints.

I must say, the STARK guys were not the most creative in the naming department. But maybe that's a good thing!

All we do is fix the value of column $i$ at step $s$ to some constant value $v$ , like so:

B(X) = T_i(X) {-} v

This polynomial should vanish (or have a root at) $X = \omega^s$ (where $s$ is the target step), so it should be divisible by $(X {-} \omega^s)$ :

B(X) = Q_B(X)(X {-} \omega^s)

Note that at least in theory, this framing allows us to establish boundary conditions right in the middle of the table, sort of like a "checkpoint"!

Once again, the existence of a valid quotient polynomial (with no remainder) certifies the boundary condition, and we can of course check this by requesting evaluations. You know, the usual story!

Boundary constraints are the key ingredient that allows STARKs to make specific claims like "this hash function, applied to input $x$ , produces output $y$ ". The input $x$ and output $y$ are the boundary conditions, and the state transition function is the hash computation unrolled into individual steps.

And with that, we've effectively arithmetized the execution trace!

This arithmetization technique is called Arithmetic Intermediate Representation (or AIR for short). It should have a familiar feel, given our previous experience, but at the same time it probably feels fresh, given that it's based on an entirely different computation model, and given that it adds some new elements in the form of boundary conditions.

Polynomial encoding, check. What now?

Building the Proof

Good! So we've reduced the original problem into a check of a bunch of QAP-style polynomial identities, in a more scalable way than the full circuit description. Once more, this resembles the situation we had in PLONK, where we ended up using an IOP to check those identities.

Because of these similarities, STARKs can simply plug into the same IOP framework we saw back then: the prover commits to the polynomials, the verifier issues random challenges, and the prover responds with openings (evaluations at specific points) together with proofs that those evaluations are consistent with the commitments. And the verifier can then use the openings to check the polynomial identities.

But remember, we set out to build a proving system that was scalable and transparent. Scalability was already covered by the arithmetization, but transparency is something we're yet to address. And in this department, we need to be careful not to use the same commitment scheme, because KZG is not transparent!

I mean, we could use KZG, but then we'd not have a STARK. We'd get what, a scalable, universally trusted argument of knowledge? A SUTARK? Anyway!

So yeah, in fact, STARKs deviate quite significantly when it comes to their PCS of choice. Where PLONK used KZG, STARKs rely on an old, trusty friend: Merkle trees!

As we saw during our pass through polynomial commitment schemes, the idea behind Merkle trees as commitment schemes is to bundle all possible polynomial evaluations over some domain $D$ , to then simply prove that a requested evaluation belongs to the bundled set.

That is, for a polynomial $P(X)$ , we calculate:

P(D) = \{P(d_0), P(d_1), P(d_2), \ldots\}

And place all these values as leaves on the tree. This set of evaluations is usually referred to as a Reed-Solomon codeword, and the Merkle root over those values is the commitment.

Note that during this interaction, no secret parameters are used! Just plain ol' hash functions!

Great! Sounds pretty convincing so far...

The Consistency Check

With commitments in hand, the verifier's main job is to check this polynomial identity at a random point $r$ :

Q_j(r) \cdot Z(r) = C_j(r)

Something cool about this identity is that the constraint polynomials $C_j(X)$ need not be committed to directly. Instead, the prover can commit to the trace polynomials, and calculate the value of an evaluation $C_j(r)$ from the trace polynomial evaluations at $r$ and $\omega r$ .

They can do this because they know the state transition function, so they can handle that computation locally!

So the general flow goes as follows:

The prover commits to (and opens) the trace polynomials, the transition quotient polynomials $Q_j(r)$ , and the boundary quotient polynomials $Q_B(r)$ .
The verifier then requests the openings, does the local reconstruction, and verifies the identities.

And thanks to Schwartz-Zippel, if the relations hold at some random point $r$ , then they hold everywhere with high probability!

That's a valid proof system then! Or... is it?

The Blowup Factor

There's actually a very subtle problem here - one we may easily miss if we're not paying attention: what happens if $r$ happens to land on a $T$ -th root of unity?

Carly from iCarly looking at her PC with the quote 'interesting' — An amusing thought, indeed

If that's the case, then two things happen simultaneously:

$Z(r) = 0$ at every such point.
$C_j(r) = 0$ as well, because that's exactly how we engineered that polynomial!

Because of this, the check becomes $Q_j(r) \cdot 0 = 0$ . That's trivially true for any $Q_j(X)$ , meaning we're essentially not checking anything at all!

The only possible solution to this conundrum is to evaluate and commit to the polynomials over a domain larger than that of the roots of unity, a set $D' \supset H$ . At any point that belongs to $D'$ but not to $H$ (such a set is denoted as $D' \setminus H$ ), both the vanishing polynomial and the constraint polynomials evaluate to non-zero values, making the consistency check actually meaningful.

And so, we're forced to work over a larger domain. But not just any set: we also need $D$ to be a set of roots of unity as well, for reasons that will become clearer later.

Plus, it must contain $H$ ! So it must be a larger multiplicative subgroup.

The ratio between the sizes of said domains is called the blowup factor, and it's an integer value that typically sits between $2$ and $8$ in practice.

When the prover computes their Merkle tree, they do so over this expanded domain, and when a verifier chooses $r$ , they need to make sure it's not a root of unity, so that the check becomes real.

Alright! That's not so bad, is it? Everything seems pretty reasonable, and we haven't had to go through any weird shenanigans.

Well... that, my friends, is about to change.

The Catch

Deep breath, relax... ok, we ready?

As it is, everything we've presented so far is fundamentally flawed, and there's a significant gap that can lead to all kinds of exploits.

I want to convince you about this, so I propose the following: let's try cheating ourselves!

Suppose we have a slightly wrong trace, where only one of the transition steps is off. When we try to compute the constraint polynomial for that step, it won't vanish at the corresponding root of unity. That means $C_j(X)$ isn't divisible by $Z(X)$ , and I can't produce a legitimate quotient polynomial that will satisfy a QAP relation.

But that doesn't mean I'm out of options! I could fabricate a polynomial ${Q_j}^*(r)$ that just happens to satisfy the identity check at whatever random point $r$ the verifier picks, even though it has no relation to a valid trace:

{Q_j}^*(r) \cdot Z(r) = C_j(r)

How? Well, if the degree of ${Q_j}^*(X)$ is unconstrained, we can simply calculate:

{Q_j}^*(r) = C_j(r) \cdot Z(r)^{-1}

at every single point in the domain, and commit those values in a Merkle tree.

Think about it: for any query $r$ the verifier picks, the consistency check passes by construction. The committed values will satisfy the check everywhere, even when ${Q_j}^*(X)$ has nothing to do with the execution trace!

Quite the pickle, huh? This is a dire situation indeed. We're gonna need a way to tell a real quotient apart from a fabricated one, or else our whole commitment scheme falls apart.

Luckily though, there's but one key difference between these polynomials, and it's all we need to distinguish reals from fakes: their degrees!

You see, when we fabricated our false quotient polynomial, we had to work backwards and calculate each functional value. This will result in a set of evaluations $(r, {Q_j}^*(X))$ that, when interpolated, will very likely yield a high-degree polynomial.

In contrast, a "real" $Q_j(X)$ will be constructed from polynomials whose degrees we know in advance (the trace polynomials), put together by virtue of the state transition function. Therefore, we can easily put an upper bound on the expected degree, and this upper bound is very likely to be much lower than the degree of a fabricated quotient!

We had mentioned this before very briefly, but after this little exercise, the problem should be much clearer. Essentially, it can be boiled down to this simple idea right here:

Without a way to check the degree of polynomials, the verifier has no way to tell the difference between forged data and actual trace data.

Interestingly, KZG prevents this by design: the SRS limits the prover to polynomials of degree at most the SRS length. There's just no way to produce anything of higher degree. With Merkle trees, there's no such restriction, and the prover is free to commit to evaluations of any function over the domain.

So how do we fix this problem? By finding a way to sort of certify the degree of the quotient polynomials! And if a prover submits quotient polynomials of unexpectedly high degree, they're most likely cheating.

Cool! All we need now is a way to detect this.

STARKs make use of a technique called Fast Reed-Solomon Interactive Oracle Proof of Proximity (or just FRI for the friends). It's a protocol for proving that a committed polynomial has bounded degree, using nothing but hash functions and field arithmetic.

And this will be the final piece of the puzzle! Just a little more to go.

Folding

If you've been following the series so far, the word "folding" should ring a bell. Back when we covered Bulletproofs, we folded vectors. As a refresher, the process involved four steps that were executed recursively:

Splitting the vector in half
Computing some cross-terms, and sending them to the verifier
Receiving a random challenge from the verifier in response
And collapsing the two halves into a single vector of half the size

The process could be repeated until a single element remained, and that scenario was simple enough that it could be "checked directly", which cascaded all the way through to an affirmation about the original vector.

Remember? Well, I have some good news for you then: FRI uses this same pattern! Only that instead of vectors, it's applied to polynomials over a certain domain.

Let's see it in action then. First, recall that any polynomial $P(X)$ can be split into its even and odd parts:

P(X) = P_\text{E}(X^2) + X \cdot P_\text{O}(X^2)

Where, explicitly:

P_\text{E}(X^2) = \frac{P(X) + P({-}X)}{2}, \quad P_\text{O}(X^2) = \frac{P(X) {-} P({-}X)}{2X}

Here, $P_\text{E}(X)$ collects the even-indexed coefficients and $P_\text{O}(X)$ the odd-indexed ones. We saw this in action back when we worked our way through FFT, so again, this should not be all that new to us.

If the original polynomial $P(X)$ has degree at most $d$ , then we know both these new polynomials will have degree at most $d/2$ . So just by performing this split, we've already halved the degree!

For example, take $P(X) = 3 + 5X + 2X^2 + 7X^3$ .

The split results in $P_\text{E}(X) = 3 + 2X$ and $P_\text{O}(X) = 5 + 7X$ . Each part has degree at most $1$ , down from the original $3$ !

At this point, the verifier sends a random challenge $\beta$ , and the prover folds by calculating:

P'(X) = P_\text{E}(X) + \beta \cdot P_\text{O}(X)

As we saw in our little example, this new polynomial has degree at most $d/2$ . The prover commits to it with a fresh Merkle tree, and suddenly, we're back to the beginning!

Thus, we can apply this over and over, and after $\log_2 d$ rounds, the polynomial will have been folded all the way down to a constant. And since a constant can no longer be folded (it's a degree zero polynomial, after all), the process stops.

Along with the polynomials, the evaluation domain naturally halves at each step too. This has to do with the symmetry properties we analyzed in our pass through FFT. The key insight is that the elements of $D$ , being a set of roots of unity, come in symmetric pairs $\{x, -x\}$ .

And this is the reason we needed $D$ to also be a set of roots of unity!

When we substitute $X^2$ in the split polynomials, both $x$ and $-x$ map to the value $x^2$ . And so, each pair collapses to a single value, and since the domain for the next round is the set of all those squared values, the domain shrinks in half.

What do we end up with then? A tower of Merkle commitments! One per round, each over a domain half the size of the previous, until we get a constant.

But this phase, known as the FRI commit phase, is just half the story. So let's see how the rest unfolds (pun intended).

Checking the Fold

Of course, any prover could just claim to have folded everything correctly at every step. The verifier can never trust the prover, so they're gonna need to perform some checks of their own.

That's where the query phase comes in, where the verifier picks a random point $x'_0$ from the folded domain $D'$ .

Why? Well, as we've already mentioned, the domain $D$ is built from roots of unity, so its elements come in pairs ${x_0, -x_0}$ . When we folded, both these elements collapsed into the single point $x'_0 = {x_0}^2 \in D'$ , right? However, the original Merkle tree was committed over $D$ , so both $x_0$ and $-x_0$ are leaves in that first tree. The prover must therefore be able to open both $P(x_0)$ and $P({-}x_0)$ .

Those two values alone are enough for the verifier to reconstruct the value of $P'({x_0}^2)$ , which should be:

P'({x_0}^2) = \frac{P(x_0) + P({-}x_0)}{2} + \beta \cdot \frac{P(x_0) {-} P({-}x_0)}{2x_0}

Which follows directly from the definitions of $P_\text{E}$ and $P_\text{O}$ . Feel free to check for yourself!

And this value should be part of the second Merkle tree! So they can query $P'({x_0}^2)$ , and check that the value matches the commitment. We can repeat the same check for the next layer, using a new value from the third folded domain to verify the fold into the third layer, and so on.

A handful of such query paths is enough to make cheating overwhelmingly unlikely. The intuition is that a genuinely high-degree polynomial is "far" from any low-degree one, meaning it disagrees with the expected values at a large fraction of possible query points. So a few random queries will almost certainly land on an inconsistency!

And just like in Bulletproofs, the prover must commit to all layers before the verifier sends any queries. There's no going back once the tower is built.

With FRI in as the final piece snapping into place, the last gap is closed!

When the prover commits to their quotient polynomials $Q_j(X)$ , they also run FRI on each of those to prove the degree falls within the expected bound. The verifier checks this proof before accepting anything else. And if you try to sneak in a high-degree fake $Q_j$ , the FRI proof fails because some query will catch a fold inconsistency, and the whole cheating effort is stopped in its tracks!

Summary

And that's the core of what STARKs are!

We covered a lot of ground today, all stemming from a single strategic decision: we swapped KZG for Merkle trees, and suddenly we were free from trusted setups and pairing-friendly curves.

But that swap doesn't come for free. It forced us to rethink the computation model, come up with a new arithmetization technique (AIR), and add a dedicated low-degree test (FRI) to fill a gap that KZG was silently handling for us all along. Each of those pieces felt necessary once we understood why it was needed, and that's what I find most satisfying about STARKs: the construction is almost inevitable once you commit to the initial premise.

Plus, as a nice side effect, we ended up with a protocol that happens to be quantum robust, because the entire construction is hash-based!

I think this is more than enough for today, but as always, there's much more to explore. The original STARK paper is dense but rewarding. Then you have Alan Szepieniec's STARK anatomy series, which goes much deeper into both AIR and FRI, and I highly recommend it if you want to see the full construction in all its glory.

STARKs represent our first significant departure from the circuit model in a while.

This is interesting, but we should know to expect this kind of thing. After all, we're proving stuff about NP relations, not necessarily about circuits. And there might be many ways to go about this endeavor.

Before we focus on that though, I want us to take somewhat of a little detour. We've been paying a lot of attention to the mechanisms themselves, assuming that the foundations upon which they are built are always solid and ever present. And by this, I mean that we haven't really stopped to think about the finite fields we're using so much!

Turning our attention to them will bring forth some interesting questions, coupled with some interesting ways to go about proving things.

And for that, I'll see you on the next one!