BrainSTARK, Part 0: Introduction

This tutorial teaches the reader how to design a Turing-complete zk-STARK engine, consisting of a virtual machine, prover, and verifier. Brainfuck was chosen as the target language due to its well-known and simple instruction set, but the design patterns introduced in this tutorial generalize to arbitrary instruction set architectures. The reader should be able to recompile these tools and generate a STARK Engine for a language of their choice with minimal effort.

What Are STARKs?

STARKs are one of the most exciting advances in the field of cryptography in recent years. In a nutshell, a STARK engine splits a computation into two parts, the prover and the verifier. The prover runs the original computation but additionally outputs a string of cryptographic data called the proof. The verifier reads this proof and by verifying it he can determine with cryptographic certainty whether the computational claim is correct. The amazing selling point is this: the verifier can check this proof with fewer resources than it takes to run the computation naïvely. Specifically:

The difference between a STARK and a STARK Engine is that the latter comes with a virtual machine and should be capable of proving and verifying arbitrary computations.

STARK engine diagram


This tutorial assumes some familiarity with SNARKs in general, STARKs in particular, and the mathematics involved with the latter. For a more basic introduction please see the Anatomy of a STARK tutorial, or the sources referenced in there. This tutorial builds on the Anatomy in terms of nomenclature, source code, and functionality.


Supporting Python Code

The tutorial text contains snippets of python code to illustrate key principles. To see how everything works together as a whole, checkout the repository.

The purpose of this tutorial and the supporting code is educational, and as a result questions about performance are left largely by the wayside. Indeed, for a performant STARK engine you might not want to use python, let alone support Brainfuck.


This tutorial has a companion written by Thorkil and Ferdinand. This sibling is more of a guide to the Brainfuck-STARK codebase rather than a comprehensive answer to the question, how does one produce a STARK engine? The reader might benefit from comparing both sources.


Many thanks go to Thorkil Værge for helping to debug the codebase, and to him, Ferdinand Sauer, and Bobbin Threadbare for countless useful discussions.

Next up: Part I: STARK Engine
0 - 1 - 2 - 3 - 4 - 5