Skip to main content

STARK by Hand

When the RISC Zero zkVM executes, it generates a receipt that allows third-parties to authenticate the validity of the execution. The receipt contains a zk-STARK in the form of the seal. The zk-STARK that lives on the receipt is the crux of RISC Zero's technology.

The construction of the RISC Zero STARK is highly technical, relying on several recent advances in the world of zero-knowledge cryptography. Specifically, constructing RISC Zero's zk-STARK uses the DEEP-ALI protocol & the batched FRI protocol (after a randomized preprocessing step).

In this series of 12 brief lessons, we walk through a simplified numerical example of the construction of RISC Zero's STARK.

If you make sense of these 12 lessons, you'll have a solid handle on the mechanics of a zk-STARK (and we'd likely love to hire you).

The proof system sequence diagram describes this process in more generality; we suggest going back and forth between this document and the sequence diagram.

Lesson 1: The Execution Trace

When any code executes in the RISC Zero virtual machine, each step of that execution is recorded in an Execution Trace.

We show a simplified example, computing 4 steps of a Fibonacci sequence modulo 97, using two user-specified inputs.

Lesson 1: The Execution Trace

In this example, our trace consists of 6 columns.

  • Each of the first three columns is a record of the internal state of a register at each clock cycle from initialization until termination. We call these Data Columns.
  • The next three columns are Control Columns, which we use to mark initialization and termination points.

In the full RISC Zero protocol, the Data Columns hold the state of the RISC-V processor, including ISA registers, the program counter, and various microarchitecture details such as instruction decoding data, ALU registers, etc., while the Control Columns handle system initialization and shutdown, setting up the page table with the program memory image, and other control signals that don't depend on the programs execution.

The full implementation also has Accumulator Columns, allowing for RISC-V memory emulation. The Accumulator Columns are not necessary in this simplified example.

Lesson 2: Rule checks to validate a computation

Here, we introduce a number of rule-checking cells in order to demonstrate the validity of the execution. In this example, we show six rules specific to generating Fibonacci numbers.

Lesson 2: Rule-checks to Validate RISC-V Execution

Each rule check is written as the polynomial over the data columns, for example a+bca + b - c which only equals 00 when a+b=ca + b = c. In our example aa, bb, and cc may be terms in the data columns enforcing the Fibonacci sequence rule, that F(i)+F(i+1)=F(i+2)F(i) + F(i+1) = F(i + 2).

Each rule is combined with a selector from the control columns to decide when to apply the rules. For example, we should check that the output of one step is equal to the input to the next, except when we consider the first row where there is no prior step and instead it must be equal to the user input. This combination is via multiplication e.g. (s)(a+bc)(s)(a + b - c) ensures that either a+b=ca + b = c or s=0s = 0.

Each rule checking column can be expressed as a multi-input, single-output polynomial, where the inputs are some combination of entries in the trace; we call these rule-checking polynomials. All of these polynomials are over a finite field, in this example it is the integers modulo 97.

In the full RISC-V implementation, the rules make up what it means to execute RISC-V instructions properly (i.e. checking that the program counter increments after every instruction). We check thousands of rules in order to validate the execution trace.

Lesson 3: Padding the Trace

Before encoding each column as a polynomial, we append random padding to the end of the Execution Trace, which adds the entropy needed to hide the user's data, allowing for a zero-knowledge protocol.

This random noise is generated by the host system's cryptographically secure pseudorandom number generator. We set the Control columns to 0 for these random noise rows, in order to turn off our rule checks. Lesson 3: Padding the Trace

Lesson 4: Constructing Trace Polynomials

This lesson explains the mechanics of Reed-Solomon encoding. RS encoding is a form of error-correcting code; it allows for efficient addition of redundancy to cryptographic messages.

Let's remove the rule-checking columns for a minute and turn our attention toward encoding our Trace data in terms of polynomials. Throughout these lessons, all of the arithmetic takes place in F97\mathbb{F}_{97}.

From here on, the lessons assume some familiarity with finite fields. If finite fields are foreign to you, fear not! This finite fields primer covers just enough to make sense of RISC Zero's use of finite fields.

Every element of F97\mathbb{F}_{97} can be written as a power of 5. In other words, the elements of F97\mathbb{F}_{97} are 0,50,51,,0, 5^0, 5^1, \ldots, and 5955^{95}. We write D(512)\mathcal{D}(5^{12}) for the set of powers of 5125^{12} and D(53)\mathcal{D}(5^{3}) for the set of powers of 535^{3}. Each of these sets is "evenly spaced" throughout F97\mathbb{F}_{97}, which facilitates the use of number theoretic transforms.

Put succinctly, running an iNTT on a trace column gives the coefficients of a trace polynomial.

Lesson 4a: iNTT of Trace Columns forms Trace Polynomials

The table above shows the python code and associated input/output arrays; the input arrays correspond to the trace columns and the output arrays are the coefficients of the trace polynomials. The key features about the trace polynomials are that:

  • they are at most degree 77 (length of the column minus 11) and
  • the trace polynomial evaluations on D(512)\mathcal{D}(5^{12}) precisely match the data in the padded execution trace.

Lesson 4b: Coefficients of Trace Polynomials

Evaluating the trace polynomial on the larger set D(53)\mathcal{D}(5^{3}) gives a Reed-Solomon encoded trace block.

We say the block is a degree 4 expansion of the column, and that the Reed-Solomon encoding has rate 14\frac{1}{4}. Reed-Solomon encoding improves the soundness of the protocol by amplifying any errors in an invalid trace.

Lesson 4c: Evaluating Trace Polynomials

Lesson 5: ZK Commitments of the Trace Data

The next step is for the Prover to commit the trace polynomials into a Merkle tree. In order to make RS expansion play well with zero-knowledge, we have to avoid overlapping evaluation domains between the "trace domain" and the "commitment domain."

The Prover evaluates each trace polynomial over a shift of D(53)\mathcal{D}(5^3).

We'll choose a shift of 5 and evaluate each trace polynomial over x=5,54,57,...,594.x=5, 5^4, 5^7, ..., 5^{94}.

Lesson 5: ZK Commitments Note that because of the shift, the yellow and blue cells in Data Columns 1, 2, and 3 no longer match the Inputs and Asserted Outputs. In fact, this shift in the evaluation domain disguises all the Trace Data.

We only reveal information about the disguised trace, and the random padding we appended is sufficient to prevent an attacker from deducing any connection between the disguised trace and the actual trace.

Lesson 6: Constraint Polynomials

This lesson briefly describes how arithmetization is accomplished in RISC Zero. The constraints are an "arithmetized" version of logical checks.

Now that we've encoded our trace columns into trace polynomials, let's return to our original Reed-Solomon domain and add back in our rule-checking cells.

Lesson 6: Constraint Polynomials Of course, we shouldn't expect these rule checks to evaluate to 0 in the redundancy rows, as they're not directly associated with the data from the trace.

Conveniently, by writing these rule checks in terms of our trace polynomials, we can convert our multi-input rule checking polynomials into single-input polynomials, which we call constraint polynomials.

Note that each constraint polynomial will evaluate to 0 at the input values that are associated with actual trace data.

Lesson 7: Mixing Constraint Polynomials

We can reduce computational burden by compressing a bunch of constraints into one. To do so, we add one new column, which mixes our constraint polynomials into a single mixed constraint polynomial.

After the Prover commits a Merkle root for the control polynomials and the data polynomials (and the accumulator polynomials in the full implementation), those Merkle roots are used as entropy to randomly generate a constraint mixing parameter α1\alpha_1.

Letting cic_i denote the constraint polynomials, we write:

C(x)=α10c0(x)+α11c1(x)+...+α15c5(x)C(x) = \alpha_1^0 * c_0(x) + \alpha_1^1 c_1(x) + ... + \alpha_1^5 c_5(x)

Lesson 7: Mixing Constraint Polynomials

Note that if each cic_i evaluates to 0 at some input xx, then CC will also evaluate to 0 for that input.

In this example, the degree of the mixed constraint polynomial is equal to the degree of the trace polynomials, because the rule-checking involved is particularly simple. In more complicated examples, composing our rule checking polynomials with our trace polynomials would yield high degree constraint polynomials. In that case, we'd add an extra step at the end of Lesson 9 to split our high degree validity polynomial into a few low degree validity polynomials.

Lesson 8: The Core of the RISC Zero STARK

The Prover constructs the validity polynomial by dividing the mixed constraint polynomial from the previous lesson by the publicly known zeros polynomial.

V(x)=C(x)/Z(x)V(x) = C(x) / Z(x)

If we write the constraints in terms of the trace polynomials, the result will vanish at every root of the Zeros polynomial. In our example, the zeros polynomial is

Z(x)=(x1)(x47)(x75)(x33)(x96)(x50)(x22)(x64)Z(x) = (x-1)(x-47)(x-75)(x-33)(x-96)(x-50)(x-22)(x-64), where the 8 terms are the elements of D(512)\mathcal{D}(5^{12}).

Lesson 8: The Core of the RISC Zero STARK

Normally, when we divide two low degree polynomials, we don't expect to get another low degree polynomial. But for an honest prover, it's not hard to see that V(x) will be lower degree than C(x), since the roots of Z(x) line up perfectly with roots of C(x).

The Prover evaluates V(x) over the 5,54,,5945, 5^4, \ldots, 5^{94}, commits the values to a validity Merkle tree, and appends the root to the seal.

The construction of these polynomials is the core conceptual thrust of RISC Zero's proof of trace validity. All of the information necessary to confirm the validity of the original Execution trace can be described in the following assertions about these polynomials:

(i) V(x) = C(x) / Z(x) for all x

(ii) The degree of the validity polynomial and each trace polynomials are less than or equal to 7.

The FRI protocol is the technique we use for proving (ii). Those details are omitted from this simplified example.

In the original STARK protocol, the Verifier tests (i) at a number of test points; the soundness of the protocol depends on the number of tests. The DEEP-ALI technique allows us to achieve a high degree of soundness with a single test. The details of DEEP are described in the following lesson.

Lesson 9: The DEEP Technique

The DEEP technique is a means of improving the security level associated with a single query by sampling from a larger domain than the commitment domain.

Here, we use the trace polynomials and the validity polynomial(s) to construct the DEEP polynomials.

The DEEP polynomials allow the Verifier to test V(x)=C(x)/Z(x)V(x) = C(x) / Z(x) outside the original Merkle tree commitments, which substantially improves the robustness of the Verifier's test.

Without the DEEP technique, the Prover would assert that the trace polynomials d1,d2,d3,c1,c2,c3,d_1, d_2, d_3, c_1, c_2, c_3, and the validity polynomial VV were all low degree polynomials. With the DEEP technique, the Prover argues instead that d1,d2,d3,c1,c2,c3,d'_1, d'_2, d'_3, c'_1, c'_2, c'_3, and VV' are low degree polynomials.

With commitments of the trace polynomials and the validity polynomial in place, the Verifier uses the entropy of the seal to randomly choose a DEEP test point, zz. We use z=93z=93 in this example.

The Verifier would like to be able to compute the mixed constraint polynomial, C(93)C(93). The Prover sends V(93)V(93) and the necessary evaluations of the trace polynomials to allow the Verifier to compute C(93)C(93).

In this example, the necessary evaluations are d1(93),d2(93),d3(93),c1(93),c2(93),c3(93),d2(93512),d3(93512)d_1(93), d_2(93), d_3(93), c_1(93), c_2(93), c_3(93), d_2(93\cdot5^{-12}), d_3(93\cdot 5^{-12}), shown in salmon. Note that 5125^{-12} is a pointer backwards 1 computational step; by pointing forward and backward, the taps allow for checking the rules that span multiple clock-cycles.

Lesson 9: The DEEP Technique

These 8 points, together with the publicly known rule-checking functions, allow the Verifier to manually compute C(93)C(93) and therefore V(93)V(93).

The Prover also constructs the DEEP polynomials, interpolates each one, and sends the coefficients of each DEEP polynomial to the Verifier. The DEEP polynomials are defined as follows:

d1(x)=d1(x)d1(93)x93d'_1(x) = \frac{d_1(x) - d_1(93)}{x - 93} d2(x)=d2(x)d2(x)(x93)(x6)d'_2(x) = \frac{d_2(x) - \overline{d_2}(x)}{(x-93)(x-6)} where d2(x)\overline{d_2}(x) is constructed by interpolating (6,d2(6))(6, d_2(6)) and (93,d2(93))(93, d_2(93)).

d3(x)=d3(x)d3(x)(x93)(x6)d'_3(x) = \frac{d_3(x) - \overline{d_3}(x)}{(x-93)(x-6)} where d3(x)\overline{d_3}(x) is constructed by interpolating (6,d3(6))(6, d_3(6)) and (93,d3(93))(93, d_3(93))

c1(x)=c1(x)c1(93)x93c'_1(x) = \frac{c_1(x) - c_1(93)}{x - 93}

c2(x)=c2(x)c2(93)x93c'_2(x) = \frac{c_2(x) - c_2(93)}{x - 93}

c3(x)=c3(x)c3(93)x93c'_3(x) = \frac{c_3(x) - c_3(93)}{x - 93}

V(x)=V(x)V(93)x93V'(x) = \frac{V(x) - V(93)}{x - 93} where the Prover computes V(93) by running iNTT(ValidityColumn) and then evaluating the resulting validity polynomial at z=93z=93.

Lesson 10: Mixing for FRI

After using the DEEP polynomials to check the relation between the Trace Polynomial, the validity polynomial, and the zeros polynomial at z=93z=93, the only thing left for the Prover to do is to show that the DEEP polynomials are low-degree.

The FRI protocol provides a mechanism for the Verifier to confirm the low-degree-ness of polynomials, with very little computation required of the Verifier. In order to reduce this assertion of low-degree-ness to a single application of FRI, the Prover mixes the DEEP polynomials into a single FRI polynomial, using the DEEP Mixing parameter, α2\alpha_2.

Letting c1,c2,c3,d1,d2,d3c'_1, c'_2, c'_3, d'_1, d'_2, d'_3, and VV' denote the DEEP polynomials, we mix the DEEP polynomials to construct the FRI polynomial, f0(x)=α20c1(x)+α21c2(x)+...+α26V(x)f_0(x) = \alpha_2 ^0c'_1(x) + \alpha_2 ^1 c'_2(x) + ... + \alpha_2 ^6V'(x)

Lesson 11: Mixing for FRI

To complete the argument, the Prover constructs a FRI proof that f0(x)f_0(x) is a low degree polynomial. With this process, the Prover has constructed a zero-knowledge argument of computational integrity. We omit the details of FRI for brevity, but we can check our work by running an iNTT on the evaluations of f0f_0:

iNTT([53,69,63,30,46,13,60,50,38,3,95,23,75,39,62,19,62,58,41,67,89,41,50,24,95,90,72,20,82,33,0,16],prime=97)

returns

[19, 56, 34, 48, 43, 37, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Writing this array as the coefficients of a polynomial, we see that the values in the FRI polynomial column do, in fact, correspond to the following low-degree polynomial:

f0(x)=19+56x+34x2+48x3+43x4+37x5+10x6f_0(x)=19+56x+34x^2+48x^3+43x^4+37x^5+10x^6.

Lesson 11: FRI Protocol (Commit Phase)

Given a vector commitment, the FRI protocol proves that the commitment corresponds to evaluations of a low-degree polynomial. In this example, we use FRI to prove that the "FRI Polynomial" commitment (from the previous lesson) has degree at most 7. FRI consists of two phases; this lesson shows the "Commit Phase" and the next lesson shows the "Query Phase."

The "FRI blow-up factor" here is 4, since the commitment for the FRI polynomial has 32 entries and a degree 7 polynomial has 8 coefficients. This blow-up factor is a consequence of the choice of "rate" for the Reed-Solomon expansion used earlier. A FRI blow-up factor of 4 corresponds to an RS code of rate 1/4.

FRI consists of a commit phase and a query phase. The commit phase consists of rr rounds. In each round, the prover "folds" the previous commitment into a smaller commitment (both in terms of commitment size and polynomial degree).

Here, we show 3 rounds using a folding factor of 2: in each round, the Prover commits to a vector whose length is half that of the previous commitment.

The folding at each round is accomplished by first splitting the coefficients into an even part and an odd part and then mixing the two parts together using verifier-supplied randomness.

Round 1 of FRI Commit Phase

The Prover has just committed a Merkle tree with 32 leaves for f0(x)=19+56x+34x2+48x3+43x4+37x5+10x6+0x7.f_0(x) = 19 + 56x + 34x^2 + 48x^3 + 43x^4 + 37x^5 + 10x^6 + 0x^7.

Sorting f0f_0 into even and odd parts yields two polynomials with half the number of coefficients, where f0(x)=f0,even(x2)+xf0,odd(x2)f_0(x)=f_{0,even}(x^2) + xf_{0,odd}(x^2).

Concretely, f0,even(x)=19+34x+43x2+10x3f_{0,even}(x) = 19 + 34x + 43x^2 + 10x^3 and f0,odd(x)=56+48x+37x2+0x3f_{0,odd}(x) = 56 + 48x + 37x^2 + 0x^3.

Now, the Prover mixes these two smaller polynomials together, using verifier-provided randomness r1r_1. Specifically, the commitment for Round 1 is f1=f0,even+r1f0,oddf_1 = f_{0,even} + r_1f_{0,odd}.

Assuming r1=12r_1=12, we find:

f1(x)=f0,even(x)+r1f0,odd(x)f_1(x)=f_{0,even}(x) + r_1f_{0,odd}(x) =(19+34x+43x2+10x3)+12(56+48x+37x2+0x3)= (19 + 34x + 43x^2 + 10x^3) + 12(56 + 48x + 37x^2 + 0x^3)

Reducing modulo 97, we find: f1(x)=12+28x+2x2+10x3f_1(x) = 12 + 28x + 2x^2 + 10x^3. The Prover commits a 16 leaf Merkle Tree for f1(x)f_1(x), which completes Round 1. While the leaves for the previous commitment were indexed by powers of 2828, the leaves for this commitment are indexed by powers of 28228^2.

Round 2 of FRI Commit Phase

We proceed as before, splitting f1f_1 into an even part and an odd part, where

f1(x)=f1,even(x2)+xf1,odd(x2)f_1(x)=f_{1,even}(x^2) + xf_{1,odd}(x^2)

We find f1,even(x)=12+2xf_{1,even}(x) = 12+2x and f1,odd(x)=28+10xf_{1,odd}(x) = 28+10x.

And again, the Prover mixes these using randomness from the verifier.

Assuming r2=32r_2=32, we find:

f2(x)=f1,even(x)+r2f1,odd(x)f_2(x)=f_{1,even}(x) + r_2f_{1,odd}(x) =(12+2x)+32(28+10x)= (12+2x) + 32(28+10x)

Reducing modulo 97, we find: f2(x)=35+31xf_2(x)=35+31x.

Once again, the Prover commits a Merkle tree for f2f_2, with half the number of leaves as in the previous round. This time, the leaves are indexed by powers of 28428^4.

Round 3 of FRI Commit Phase

Again, we split f2f_2 into an even and odd part and then mix. At this point, f2,even=31f_{2,even}=31 and f2,odd=35f_{2,odd}=35. Using randomness of r3=64r_3=64, we find:

f3(x)=f2,even+r2f2,oddf_3(x)=f_{2,even}+r_2f_{2,odd} =31+6435=79= 31 + 64\cdot35=79

The Prover sends evaluations of f3f_3 on powers of 28828^8 without Merklization; the Verifier can check for themselves that the evaluations for f3f_3 correspond to a constant polynomial.

This completes the commit phase of the FRI protocol. In 3 rounds of folding, we've reduced a polynomial with 8 coefficients into a polynomial with 1 coefficient (i.e., a constant polynomial).

In the RISC Zero protocol, the final round of FRI occurs when the polynomial has been reduced to degree 255. The Prover sends a vector of 1024 evaluations, which the Verifier interpolates to confirm that the evaluations correspond to a low-degree polynomial.

Lesson 12: FRI Protocol (Query Phase)

After the commit phase is completed, the Verifier makes a number of queries. In this lesson, we show the mechanics of a single query.

The queries serve as a random challenge, testing the legitimacy of the Prover's commitments. Loosely speaking, with a blow-up factor of 44, a single query will catch a cheating Prover 34\frac{3}{4} of the time. In other words, a single query provides 22 bits of security. The RISC Zero zkVM uses 5050 queries and a blow-up factor of 4, which amounts to 100 bits of security.

Note that the paragraph above is a substantial simplification of the full security analysis; the precise security level is not exactly 100 bits. For a more thorough security analysis, see our ZKP Whitepaper and the Summary on the FRI Low-Degree Test.

The Prover has committed to f0f_0 on powers of 2828, f1f_1 on powers of 28228^2, f2f_2 on powers of 28428^4, and f3f_3 on powers of 28828^8.

The Evaluations for a Single Query

For a single query, the Prover provides 2 evaluations from each of f0,f1,f_0, f_1, and f2f_2. Specifically, if the Verifier query is gg, the Prover provides evaluations of:

  • f0(g)f_0(g) and f0(g)f_0(-g)
  • f1(g2)f_1(g^2) and f1(g2)f_1(-g^2)
  • f2(g4)f_2(g^4) and f2(g4)f_2(-g^4)

The Verifier checks the Merkle branches for each of these evaluations and also checks that the evaluations from one round to the next are consistent. This includes checking that the evaluations for f2f_2 are consistent with the evaluation of f3(g8)f_3(g^8).

Checking the Evaluations are Consistent

The Verifier can confirm the evaluations for fi1f_{i-1} and fif_{i} are consistent by checking that

fi(x2)=ri+x2xfi1(x)+rix2(x)fi1(x)f_{i}(x^2) = \frac{r_i+x}{2x}f_{i-1}(x) + \frac{r_i-x}{2(-x)}f_{i-1}(-x)

To simplify the exposition, we limit our discussion to checking consistency between the evaluations for f0f_0 and f1f_1.

The Heavy Algebra

We will show that

f1(x2)=f0,even(x2)+r1f0,odd(x2)f_1(x^2) = f_{0,even}(x^2) + r_1 \cdot f_{0,odd}(x^2)

implies that

f1(x2)=r1+x2xf0(x)+r1x2(x)f0(x).f_{1}(x^2) = \frac{r_1+x}{2x}f_{0}(x) + \frac{r_1-x}{2(-x)}f_{0}(-x).

We will use the following facts:

f0,even(x2)=f0(x)+f0(x)2f_{0,even}(x^2) = \frac{f_0(x)+f_0(-x)}{2} f0,odd(x2)=f0(x)f0(x)2xf_{0,odd}(x^2) = \frac{f_0(x)-f_0(-x)}{2x}

By construction, we have

f1(x2)=f0,even(x2)+r1f0,odd(x2)f_1(x^2) = f_{0,even}(x^2) + r_1 \cdot f_{0,odd}(x^2)

Using the expressions for f0,evenf_{0,even} and f0,oddf_{0,odd}, we can re-write f1(x2)f_1(x^2) using only f0(x)f_0(x), f0(x)f_0(-x), and r1r_1:

f1(x2)=f0(x)+f0(x)2+r1f0(x)f0(x)2x.f_1(x^2) = \frac{f_0(x)+f_0(-x)}{2} + r_1 \cdot \frac{f_0(x)-f_0(-x)}{2x}.

We can now find common denominators and re-arrange terms:

f1(x2)=xf0(x)+xf0(x)2x+r1f0(x)r1f0(x)2xf_1(x^2) = \frac{xf_0(x)+xf_0(-x)}{2x} + \frac{r_1 f_0(x) - r_1 f_0(-x)}{2x} =x+r12xf0(x)+xr12xf0(x)= \frac{x+r_1}{2x}f_0(x)+\frac{x-r_1}{2x}f_0(-x) =x+r12xf0(x)+r1x2(x)f0(x)= \frac{x+r_1}{2x}f_0(x) + \frac{r_1-x}{2(-x)}f_0(-x)

which completes the claim.

The key point here is that the FRI folding procedure can be checked locally: the Verifier can check the purported evaluation fi(x2)f_i(x^2) using just two evaluations from the previous round: fi1(x)f_{i-1}(x) and fi1(x)f_{i-1}(-x).

Thanks for Reading!

Whew! Congratulations and thank you for making it this far!

Got questions, feedback, or corrections? Find us on Twitter and Discord.