Learn how to write a STARK prover from scratch in Python

Starkware is one of the projects that are always on my watch list. Today, I finally have some spare time to go over one of their stark 101 tutorials to write a stark prover from scratch.

The tutorial is a great material to understand the proving mechanism, in which the verifier is succinct logarithmically using a small amount of computation and the prover is proving in a quasi-linear to achieve efficiency on both sides. In other terms, it is scalable. As the amount of verification scales in a log-squared manner, the computation required does grow but it grows very slowly.

Starkware’s team encourage us to rewrite another set of exercises for stark verifier, or maybe rewrite it using a different recurrence rule, or try a different computational statement to see if it can optimize performance better.

If you would also want to give this tutorial a try. I would recommend first read this article where it explains the mathematical primer. It helps you to pick up the math quicker.

After that, you can now clone this GitHub repo, and start playing with the jupyter notebooks.

Videos are available here.