Anatomy of a STARK

Anatomy of a STARK, Part 0: Introduction

This series of articles is a six part tutorial explaining the mechanics of the STARK proof system. It is directed towards a technically-inclined audience with knowledge of basic maths and programming.

What Are STARKs?

One of the most exciting recent advances in the field of cryptographic proof systems is the development of STARKs. It comes in the wake of a booming blockchain industry, for which proof systems in general seem tailor-made: blockchain networks typically consist of mutually distrusting parties that wish to transact, or generally update collective state according to state evolution rules, using secret information. Since the participants are mutually distrusting, they require the means to verify the validity of transactions (or state updates) proposed by their peers. Zk-SNARKs are naturally equipped to provide assurance of computational integrity in this environment, as a consequence of their features:

Vitalik Buterin likes SNARKs

Zk-SNARKs have existed for a while, but the STARK proof system is a relatively new thing. It stands out for several reasons:

Eli Ben-Sasson likes STARKs better

In this tutorial I attempt to explain how many of the pieces work together. This textual explanation is supported by a python implementation for proving and verifying a simple computation based on the Rescue-Prime hash function. After reading or studying this tutorial, you should be able to write your own zero-knowledge STARK prover and verifier for a computation of your choice.

Why?

It should be noted early on that there are a variety of sources for learning about STARKs. Here is an incomplete list.

With these sources available, why am I writing another tutorial?

The tutorials are superficial. The tutorials do a wonderful job explaining from a high level how the techniques work and conveying an intuition why it could work. However, they fall short of describing a complete system ready for deployment. For instance, none of the tutorials describe how to achieve zero-knowledge, how to batch various low degree proofs, or how to determine the resulting security level. The EthSTARK documentation does provide a complete reference to answer most of these questions, but it is tailored to one particular computation, does not cover zero-knowledge, and does not emphasize an accessible intuitive explanation.

The papers are inaccessible. Sadly, the incentives in scientific publishing are set up to make scientific papers unreadable to a layperson audience. Tutorials such as this one are needed then, to make those papers accessible to a wider audience.

Sources are out of date. Many of the techniques described in the various tutorials have since been improved upon. For instance, the EthSTARK documentation (the most recent document cited above) describes a DEEP insertion technique in order to reduce claims of correct evaluations to those of polynomials having bounded degrees. The tutorials do not mention this technique because they pre-date it.

I prefer my own style. I disagree with a lot of the symbols and names and I wish people would use the correct ones, dammit. In particular, I like to focus on polynomials as the most fundamental objects of the proof system. In contrast, all the other sources describe the mechanics of the proof system in terms of operations on Reed-Solomon codewords2 instead.

It helps me to make sense of things. Writing this tutorial helps me systematize my own knowledge and identify areas where it is shallow or wholly lacking.

Required Background Knowledge

This tutorial does re-hash the background material when it is needed. However, the reader might want to study up on the following topics because if they are unfamiliar with them, the presentation here might be too dense.

Roadmap

Acknowledgements

The author wishes to thank Bobbin Threadbare, Thorkil Værge, and Eli Ben-Sasson for useful feedback and comments, as well as Nervos Foundation for financial support. Send him an email at alan@nervos.org or follow aszepieniec on twitter or Github. Consider donating btc, ckb or eth.

0 - 1 - 2 - 3 - 4 - 5 - 6

  1. In the literature, this idealization is known as the quantum random oracle model. 

  2. A Reed-Solomon codeword is the vector of evaluations of a low degree polynomial on a given domain of points. Different codewords belong to the same code when their defining polynomials are different but the evaluation domain is the same.