OpenVM STARK Specification

This document specifies the STARK proving system used by OpenVM, derived from the Python executable specification.

The Python code is the normative source of truth. This markdown specification is a narrative overlay: every formula and algorithm step links to its implementing Python function via {src} references.

Structure

The specification is organized in two parts:

Part I: STARK Protocol — the generic FRI-STARK proving system over the BabyBear field (\(p = 2^{31} - 2^{27} + 1\)) with quartic extension \(\mathbb{F}_{p^4}\). This part is independent of any specific program or AIR definition.

Part II: Programs — concrete instantiations demonstrating the protocol: a single-AIR Fibonacci example and a multi-AIR RV32IM example with LogUp bus interactions.

Reading Guide

• Start with Primitives for the mathematical vocabulary.

• Read Building Blocks for the cryptographic primitives.

• Follow Commitment Phase and Verification Phase for the protocol narrative.

• Use The Full Protocol, Rolled Out as a self-contained reference (the most important page).

• Consult Glossary of Notation to map math symbols to Python names.