BrainSTARK: STARKs for Brainfuck

This tutorial covers the design of a STARK engine for Brainfuck.

A STARK [1] allows you to prove the correct execution of a computer program. The verifier can verify the resulting proof with less resources than it takes to naïvely re-execute the program.

Brainfuck [2] is a Turing-complete programming language that corresponds to a relatively straightforward instruction set architecture.

With this tutorial you will be able to prove and verify the correct execution of arbitrary Brainfuck programs.

[1]: https://aszepieniec.github.io/stark-anatomy/ [2]: https://en.wikipedia.org/wiki/Brainfuck

Looks exciting! To all readers: There are multiple parts to this post, use the numbers at the bottom of the screen to navigate.