STARK 101

STARK 101

Build Your Own STARK Prover from Scratch

Build Your Own STARK Prover from Scratch

What is STARK 101

STARK 101 is a hands-on tutorial on how to write a STARK prover in Python, from scratch. The tutorial has four segments:
  1. Statement, LDE and Commitment
  2. Polynomial Constraints
  3. FRI Commitment
  4. The Proof
Each segment has a short video lecture, accompanied by an explainer in PDF format and a Jupyter notebook for self-practice. You can find everything you need in our GitHub repository We assume familiarity with Python and finite field arithmetics. STARK 101 was originally a live workshop, held in Tel Aviv in September 2019 as part of StarkWare Sessions, and again in San Francisco in February 2020, where the videos were captured. The PDFs and notebooks are the products of the live workshop.

STARK 101 Online Workshop

Before You Start

To make sure the python notebooks work properly, please click the button below to start the binder environment

We highly recommend familiarizing yourself with how Python notebooks work – we’ve created a short tutorial for you in the binder. 

 

Part I: Statement, LDE & Commitment

In the first part of STARK 101 we start by introducing the statement we will be proving throughout this workshop.

Then we take the first steps into the STARK protocol, introducing two concepts: Low Degree Extension (LDE) and commitment using Merkle tree. 

Part II: Polynomial Constraints

In part II, we create a set of polynomial constraints. We use this set in order to reduce the original statement we want to prove to a new statement, that will be the input for the next step of the protocol.

After that, we create a composition polynomial and commit on it.  

 

Part III: FRI Commitment

In part III of STARK 101 we dive into the FRI protocol. We introduce the concept of proximity between a function and a polynomial and learn how to use the FRI protocol to prove that the composition polynomial we just created in the previous part is close to a polynomial of a bounded degree.

Part IV: The Proof

In the last part of STARK 101 we tie it all together to build an end to end proof. 

We go through the commitment phase, that was gradually described in the first three parts, and describe the decommitment phase that follows. 

We explain how the prover convinces the verifier, using the proof, that the statement we set out to prove is true.  

 

STARK 101 - Finale

Congratulations! You’ve completed the STARK 101 workshop! Watch this final talk for a recap, and some ideas on what you can do next. 

6 Questions, 1 Minute, Better STARK Workshops for All

what you need to know

The Mathematical Background You'll Need - Explained

During the workshop you’ll generate a STARK proof for the 1023th element of the FibonacciSq sequence over a finite field. In this section, we explain what this last sentence means.

Finite Fields

In the workshop we will work with a finite field of prime size. This means we take a prime number p, and then work with integers in the domain {0, 1, 2, …, p – 1}. The idea is that we can treat this set of integers in the same way we treat real numbers: we can add them (but we need to take the result modulo p, so that it will fall back in the set), subtract them, multiply them and divide them. You can even define polynomials such as f(x)=a+bx2 where the coefficients a,b and the input x are all numbers in this finite set. Since the addition and multiplication are done modulo p, the output f(x) will also be in the finite set. One interesting thing to note about finite fields, which is different from real numbers, is that there is always an element, g, called the generator (in fact there is more than one), for which the sequence 1, g, g2, g3, g4, …, gp-2 (whose length is p-1) covers all the numbers in the set but 0 (modulo p, of course). Such a geometric sequence is called a cyclic group. We will supply you with python classes that implement these things so you don’t have to be familiar with how these are implemented (though the algorithm for division in a finite field is not that trivial).

FibonacciSq

For the workshop we define a sequence that resembles the well known Fibonacci sequence. In this sequence any element is the sum of squares of the two previous elements. Thus the first elements are:

1, 1, 2, 5, 29, 866, …

All the elements of the sequence will be from the finite field (which means that both squaring and addition is computed modulo p).

STARK Proof

We will create a proof for the claim “The 1023th element of the FibonacciSq sequence is …”. By “proof” we don’t mean a mathematical proof with logical deductions. Instead, we mean some data which can convince whomever reads it that the claim is correct. To make it more formal we define two entities: Prover and Verifier. The Prover generates this data (the proof). The Verifier gets this data and checks for its validity. The requirement is that if the claim is false, the Prover will not be able to generate a valid proof (even if it deviates from the protocol).
STARK is a specific protocol which describes the structure of the proof and defines what the Prover and Verifier have to do.

Some Other Things You Should Know

We recommend you take a look at our math blog posts (Arithmetization I, Arithmetization II). You don’t need to read them thoroughly, but it can give you better context on what things you can create proofs for, and what a STARK proof looks like.

Division of Polynomials

For every two polynomials f(x) and g(x), there exist two polynomials q(x) and r(x) called the quotient and remainder of the division f(x) by g(x). They satisfy f(x) = g(x) * q(x) + r(x) and the degree of r(x) is smaller than the degree of g(x). For example, if f(x)=x3+x+1 and g(x)=x2+1 then q(x)=x and r(x)=1. Indeed, x3+x+1 = (x2+1)*x + 1.

Roots of Polynomials

When a polynomial satisfies f(a) = 0 for some specific value a (we say that a is a root of f), we don’t have remainder (r(x)=0) when dividing it by (x-a) so we can write f(x) = (x-a)*q(x), and deg(q)=deg(f)-1. A similar fact is true for k roots. Namely, if aᵢ is a root of f for all i=1, 2, …, k, then there exists a polynomial q of degree deg(f)-k for which f(x) = (x-a1)(x-a2) … (x-ak)*q(x).

Want to Know More?