zkMIPS Step-by-Step

MIPS Compiler

A program written in Go or Rust is compiled into a MIPS ELF binary file using the MIPS Compiler. The ELF file is the executable format for the MIPS instruction set.

ELF Loader

The MIPS ELF binary file is loaded into the MIPS VM using the ELF Loader.

MIPS VM

The MIPS VM runs the program and generates an execution trace for the Prover.

Any high-level language can compile down to MIPS. We get a sequence of the MIPS instructions as a result.

For example for row i, the described data operation is addition. In the instruction, the value in register 5 (13) is added to the value in register 6 (21). The result of the computation is stored in register 7 (34). For row i+1, the described data operation is addition (using an immediate operand). In the instruction, the value in register 5 (21) moves to register 6.

After each instruction is executed (left side table), we will get a value for each register. After going through all the instructions, we will get the trace table (right side table).

Prover

The Prover executes the MIPS program and uses the execution trace to generate a proof.

As part of the Prover, the following are steps in the proof generation process:

1. The program and trace are divided into segments.

After getting the trace table, the first step of continuation can be applied by splitting the table into segments. Segments are small sequential executions from the program execution.

2. The segments are divided into modules. The instructions of each segment are divided into groups of four module tables: arithmetic, logic, memory and control.

Modules are smaller non-sequential executions from the segments.

Each instruction, depending on the category it falls under, will be divided into its corresponding table. For example, instructions with the add operation (rows i - i+3) are placed in the arithmetic table.

3. STARK – The modules are proven independently and in parallel with FRI. These proofs are FRI-based modular proofs.

Each module execution that combines all segment instructions is independently proved using STARK proofs. In this layer, arithmetic, memory, logic and control proofs are generated. Traces proved in this layer are referred to as module traces.

4. LogUp (STARK) – The modular proofs from the previous step are combined into one single proof for each segment using the LogUp lookup protocol. These segment proofs are LogUp proofs written using Starky.

LogUp is the lookup scheme used by zkMIPS to prove that the program instructions were correctly verified in their own specific modules.

Traces proved in this layer are referred to as segment traces. Segment proofs can be produced before module proofs, and as a result, this layer can run in parallel with the previously described layer.^{[1] (opens in a new tab)}

5. PLONK – All segment proofs from the previous layer are recursively combined using the continuation protocol into one single continuation proof. This proves the correctness of the entire program trace. The continuation proofs are written using Plonky.

6. Groth16 – The Groth16 proving system is used to enable on-chain computation by converting the proof to an EVM-friendly format. The continuation proof is converted into an on-chain Groth16 (SNARK-based) proof.

This enables the final proof to be verified on L1. Groth16 uses bilinear functions over elliptic curves that are natively implemented in EVM which also enables zkMIPS to verify the proof faster on-chain.

The final proof is the zkMIPS proof representing the proof of the correct execution of the program.

Verifier Contract

After generating the zkMIPS proof, the verifier contract verifies the proof on-chain.

zkMIPS implements a Plonky2 verifier in Gnark for the proof verification.