STARK 101 is a hands-on tutorial on how to write a STARK prover in Python, from scratch.
The tutorial has four segments:
Each segment has a short 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. The PDFs and notebooks are the products of the live workshop.
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.
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).
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.