zkMIPS is a novel zkVM tailored for the MIPS instruction set, leveraging its stability and extensive use in IoT and legacy applications. zkMIPS opens up numerous practical applications for ZKPs by providing efficient and secure proof generation within a zkVM framework, and enabling verifiable computation for MIPS-based programs. This thread outlines the proving process for MIPS program execution within zkMIPS.
The first step To prove the correct execution of a MIPS program in zkMIPSis to log each internal CPU state during execution. To do so, the program is run On the Prover side and the value of each CPU variable is recorded after every instruction. These values allow for the direct verification of all state transitions of the MIPS program by matching each pair of subsequent states against the MIPS CPU state transition function.
To simplify zkMIPS's proving procedure and enhance efficiency, the process of ensuring the correctness of state transition functions is divided into three layers: Continuation proving, Segment proving, and Module proving. Each layer builds on the previous one to create a comprehensive proving architecture.
In the Continuation layer, the program execution is divided into segments by logging the first and last CPU states of each segment (these states and their program counters are enough to delimit the part of the program running on that segment). Once all segment proofs have been produced in the second layer, proofs showing that subsequent segments continue each other (the second starts from where the first finishes) are recursively produced in a second round of the continuation layer. Eventually, these so-called continuation proofs combine all segment proofs into a single proof for the entire program trace, ensuring that the entire execution took place correctly.
In the Segment layer, segments are further divided into modules, each corresponding to an independent subset of MIPS instructions. At this stage, segment traces are in fact logged and broken into smaller non-sequential module traces, which are given to the modules to prove. The module proofs produced in the third layer are combined into a segment proof at a second round of the segment proving, validating that the segment trace accurately reflects the module traces.
The Module layer involves proving each module independently using specialized STARK proofs. The module traces derived from segment traces are used to produce module proofs by proving the transition functions for each instruction of that segment separately. This layer is where MIPS instructions are indeed proved by robust, independent proofs that are fed with states from the trace and polynomial attesting their underlying instructions logic.
Segment provers can run in parallel, comprising a network of provers to prove the entire program faster. Similarly, continuation provers can also run in parallel because they are executed recursively, reducing the continuation layer's time to one logarithmic relative to the number of segments. This setup enables distributed proving and increases scalability and efficiency in the proving process.
