Design and Implementation of a Toy STARK-Based Zero-Knowledge Virtual Machine

Abstract

With recent advancements in zero-knowledge proofs, zero-knowledge virtual machines (zkVMs) have emerged as a practical way to verify program correctness while keeping inputs private. A zkVM allows a prover to generate a succinct proof of computational integrity. Verification of such proofs is significantly cheaper than recomputing the original program. This thesis presents the design and implementation of a toy zkVM using the Scalable Transparent ARgument of Knowledge (STARK)-style approach. The system models execution in the algebraic intermediate representation (AIR): an execution trace together with boundary and transition constraints that restrict valid computations. These AIR constraints are proven using a cryptographic backend, based on commitment schemes and low-degree testing. Implementation is demonstrated through progressively enhanced examples that prove and verify the computation. The thesis discusses key design choices, limitations, and directions for future work toward a full virtual machine with richer instruction sets and memory.