From Zero to Hero: OP Stack Fault Proof Series 2 [ENG]

Overview of Cannon’s Fault Proof System

Tokamak Network aims to deliver valuable information for current developers interested in Optimism and the evolution of the Ethereum ecosystem.

Source: Oplabs Link

This post is the second installment of the ‘The feature-complete version of OP Stack fault proofs Series,’ comprising 3 planned articles by Tokamak Network. In this article, we provides an overview of Cannon(Optimism’s FPVM), which ensures Layer 2 state transition integrity via offchain execution and onchain verification. Key components like MIPS.sol, MIPSEVM, and work together for efficient dispute resolution.

💡 Given the interconnected nature of the series, we recommend reading the articles sequentially for a cohesive understanding.

Series 1. Cannon’s Fault Proof System:
In this article, we introduce Optimism’s Fault Proof Program and explain how its Multi-Proof Architecture enhances Layer 2 security and reliability. The program integrates robust fault proof mechanisms to ensure accurate state transitions and efficient dispute resolution. [LINK]

Series 3. The Fault Dispute Game(FDG) / Bisection Game:
In this article, we explore how Optimism’s Fault Proof System resolves Layer 2 state disputes using onchain (MIPS.sol) and offchain (MIPSEVM) components. We cover the roles of proposers and challengers, the PreimageOracle’s data management, and the incentive structures ensuring integrity and security. Additionally, we explain the bisection game, which breaks down disputes into single instructions for precise verification. [LINK]

Overall Fault Proof System

Fig. Flowchart of the Overall Fault Proof System

This flow chart outlines the mechanisms and processes involved in resolving disputes over Layer 2 block state transitions within the Optimism network. The core components of this process include the interaction between Cannon and Op-challenger, the Bisection Game, onchain verification through MIPS.sol, execution trace management via Op-program, and the generation of witness proofs. Here is a detailed explanation of each step:

1. Disagreement over a Specific L2 Block State Transition: Cannon cooperates with Op-challenger to process MIPS instructions, generating state witness hashes to address disagreements on specific L2 block state transitions.

2. Bisection Game: The Op-challenger utilizes generated hashes to pinpoint a single MIPS instruction, the root of the disagreement. Cannon then produces a witness proof(offchain), which contains all the necessary data(pre-images + state information) to execute the MIPS instruction onchain.

💡 What if the offchain-generated witness proof is tampered?
▶ The onchain execution of the disputed MIPS instruction in MIPS.sol is deterministic, ensuring that the same inputs and state always produce the same output. If the offchain proof is tampered with, the onchain execution will expose the discrepancy by not matching the expected result.

3. Onchain Verification: The disputed MIPS instruction is executed onchain in MIPS.solto conclusively determine the correct post-state, thereby resolving the fault dispute. The witness proof, generated offchain by Cannon, contains all the necessary data for this onchain execution. This proof ensures the accuracy and integrity of the process during the onchain verification. If the instruction references a hashed value, Cannon retrieves the required pre-images from the PreimageOracle via Op-preimage to verify the instruction onchain.

4. Execution Trace with OP-Program: An ELF binary, compiled from Op-program, is loaded and executed within Cannon. Op-program ensures all necessary data is fetched for deriving the L2 state, guaranteeing that identical inputs lead to consistent outputs and execution traces.

5. Witness Proof Generation: Participants in the dispute game can run Op-program to generate the same witness proof for the MIPS instruction to be executed onchain. Both parties independently verify the correctness of the disputed MIPS instruction. If a pre-image is required, witness.go communicates the relevant pre-image key and offset to Op-challenger, enabling it to be posted onchain to PreimageOracle.sol.

💡 The witness proof generation process is initiated by the top-level witness.go file located in cannon/cmd, while the witness.go file in cannon/mipsevm defines the struct that contains all the necessary information for the specific MIPS instruction. If a pre-image is needed for the MIPS instruction, it is included in this process to ensure accurate and complete verification.

• witness.go communicates the relevant pre-image key and offset to Op-challenger.
• Op-challenger posts this information onchain to PreimageOracle.sol.

💡 This process generates all relevant information about the MIPS instruction to be executed onchain before the MIPSEVM execution state changes. By ensuring that all necessary information is generated and communicated before these state changes occur, the process guarantees the accuracy and integrity of the witness proof. This prevents the proof from encoding the incorrect post-state and ensures it captures the required pre-state for proper dispute resolution. If the witness proof is generated after running the instruction offchain, it will encode the post-state instead of the necessary pre-state.

Detailed Explanation of Cannon Components

Fig. Flow Diagram for Cannon Components

1. Cannon Runner

• Files: run.go, instrumented.go
• Function: Initiates and manages the execution process within Cannon. This component handles the top-level execution logic, stepping through MIPS instructions, and determining additional actions such as logging, stopping, taking snapshots, or generating witness proofs based on user configurations.
• Interaction: This interaction ensures that the Cannon Runner has the accurate state and memory details required for efficient execution management.

2. Memory and State Management

• Files: memory.go, page.go, state.go
• Function: Manages memory allocation and the state of the MIPS virtual machine. This involves storing memory nodes and pages in a way that optimizes Merkle root calculations, handling the big-endian ordering of bytes in words for MIPS instructions, and maintaining the execution state, memory Merkle roots, and optional pre-image hints.
• Interaction: This component interacts with both the Cannon Runner and MIPSEVM by providing the current state and memory details. It ensures that both the Cannon Runner and MIPSEVM have consistent and up-to-date memory and state information for their operations.

3. MIPSEVM

• File: mips.go
• Function: This component executes MIPS instructions and interacts with the PreimageOracle(Offchain) to retrieve pre-image data necessary for verifying hashed values. It ensures the offchain MIPS execution produces the same results as the onchain execution, handling memory access and state updates. Additionally, it tracks memory accesses for instructions requiring memory proofs.
• Interaction: This component interacts with Memory and State Management for current state and memory details, and with PreimageOracle (Offchain) to retrieve required pre-images.

4. Witness Proof Generation

• File: witness.go
• Function: Generates witness proofs required for dispute resolution during the fault dispute game. This process involves creating the necessary information for MIPS.sol to run the same instruction onchain and derive the post-state used to resolve the dispute. It also includes communicating relevant pre-image keys and offsets to Op-challenger for onchain posting to PreimageOracle.sol.
• Interaction: Witness Proof generation interacts with the Cannon Runner to generate witness proofs required for dispute resolution.

6. ELF Loader (Execution Trace Process)

• Files: load_elf.go, patch.go, metadata.go
• Function: Once the execution trace portion of the bisection game begins, the ELF Loader Loads and patches the ELF file containing the Op-program compiled into MIPS instructions within Cannon. To run Op-program in Cannon, a binary loader is required, composed of load_elf.go, patch.go, and metadata.go.
• load_elf.go: This file parses the top-level arguments, reads, loads, and patches the ELF binary so it can be run by Cannon.
• patch.go: This file parses the headers of the ELF file to determine what programs exist and their memory locations, instantiates the execution state for the MIPSEVM, loads each program into memory at the expected location, and sets initial values for PC, NextPC, Heap (0x20000000), Stack (0x7fffd000), and Go runtime arguments above the stack pointer.
• metadata.go: This file parses all the symbols stored in the ELF file, helping to identify which ELF symbols exist and their memory locations, which is important for functions and other functionalities.

💡 The Purpose ELF Loader is essential for preparing the MIPS program for execution by loading the ELF file, setting the initial state, patching functions, and parsing symbols. It ensures that both the challenger and verifier start from the same correct state in the bisection game, enabling precise identification and demonstration of any discrepancies in the MIPS program execution. This accurate setup is crucial for the challenger to calculate and prove the correct values when a fault is found.

5. PreimageOracle Server

Fig. Flow Diagram for PreimageOracle On/Off-chain.

Functions: The PreimageOracle Server(Offchain) supports the off-chain execution environment by providing the necessary pre-image data required for verifying hashed values during MIPS instruction execution. The server ensures that the offchain execution can produce the same results as the onchain execution by accessing the correct pre-image data.

Offchain Computation:

• The MIPSEVM executes MIPS instructions offchain, interacting with the PreimageOracle Server to retrieve necessary pre-images. This allows for fast and efficient processing.
• The PreimageOracle Server stores and manages pre-images required for verifying hashed values used during offchain execution.

Onchain Verification:

• When a state transition or execution result needs to be verified or disputed, the onchain PreimageOracle provides the pre-images to ensure that the on-chain MIPS.sol contract can accurately re-execute the instruction and verify the result.
• This ensures that the onchain state remains consistent with the offchain execution, providing a trustworthy environment for dispute resolution.

Detailed Explanation of MIPS.sol and its Role

The MIPS.sol smart contract is an on-chain virtual machine (VM) that executes the 32-bit, Big-Endian, MIPS III Instruction Set. It works alongside an off-chain counterpart, MIPSEVM (written in Go), as a vital component of the Cannon FPVM system. This system is designed to execute MIPS instructions on-chain for dispute resolution in Optimism’s Layer 2 blockchain. The stateless nature of MIPS.soland its interactions with other contracts ensure efficient and reusable dispute-resolution processes.

💡 The term “stateless” means that MIPS.sol only has one immutable state variable: the address of the PreimageOracle.sol contract. It relies on external inputs and pre-images data, ensuring each execution is independent, efficient, and easily verifiable, enhancing security and robustness by minimizing dependency on internal state. This design allows it to be reusable across multiple dispute games without redeployment.

Key Functions and Role of MIPS.sol

1. Interaction with Other Contracts:

• FaultDisputeGame.sol: MIPS.sol is primarily called by this contract, which handles active disputes.
• PreimageOracle.sol: This contract stores Pre-images, which are data snapshots used during the dispute resolution process.

2. Role in Dispute Resolution:

• MIPS.sol is used during a dispute game when it reaches a specific point in the state transition tree, called a leaf node. This point represents a single MIPS instruction that needs to be executed on-chain to resolve the contested state.
• The contract uses pre-images (previously agreed-upon L2 states) and the current instruction state to compute the true post-state. This helps resolve the dispute by comparing the computed post-state to the disputed post-state.

3. Execution of MIPS Instructions:

• Packed VM Execution State: The contract needs detailed state information (e.g., memory root, program counter, general-purpose registers) to execute a MIPS instruction.
• Memory Proofs: To verify memory reads and writes, MIPS.soluses a binary Merkle tree structure, ensuring data integrity with memory proofs.
• State Hash: After executing an instruction, the contract returns a state hash representing the new VM state, incorporating the VM’s status to signal validity.

MIPS.sol Functions:

Fig. MIPS.sol (Source: github link)

function oracle(): Retrieves the PreimageOracle address.

Fig. MIPS.sol (Source: github link)

function outputState(): This function copies the MIPS state to a free memory location, logs the state for debugging, determines the VM status based on the exit code, computes the keccak256 hash of the state, and returns the hash with the status byte set.

This function manages and records the state of the virtual machine after executing a MIPS instruction. Here’s a more detailed explanation:

1. Copying the MIPS State: The function copies the current state of the MIPS virtual machine to a free memory location. This step ensures that the state is preserved and can be referenced or used in subsequent operations.
2. Logging the State for Debugging: The state is logged, providing a way to trace the execution and identify any issues or inconsistencies. This logging is essential for debugging and verifying that the VM operates as expected.
3. Determining the VM Status: The function checks the exit code of the VM to determine its current status. The exit code indicates whether the VM has successfully executed the instruction, encountered an error, or reached a specific condition (e.g., program termination).
4. Computing the keccak256 Hash: The function computes the keccak256 hash of the VM state to ensure its integrity and uniqueness, producing a unique identifier for state verification. It can also be used to verify that the state has not been tampered with.
5. Returning the Hash with Status Byte: The function returns the hash with an appended status byte, providing a secure and concise representation of the VM’s state for further processing, verification, or storage.

Fig. MIPS.sol (Source: github link)

function handleSyscall(): This function in MIPS.sol is to manage system-level operations within the MIPS virtual machine. Here’s a detailed explanation:

• Processing System Calls: The function identifies the system call type based on the syscall number, which requests services like I/O operations, memory management, and process control.
• Updating the VM State: It performs the specified operation and updates the VM state, ensuring proper handling of system-level tasks.
• Types of System Calls Handled:
  - Memory Allocation: Allocates memory and updates memory management structures.
  - Program Termination: Terminates the program and updates the VM state.
  - Reading and Writing: Manages I/O operations, reading from inputs, and writing to outputs.
  - File Descriptor Control: Controls file descriptors for managing file operations.
• Returning the Updated State Hash: After processing the system call, it computes and returns a hash of the updated state, providing a unique identifier to ensure changes are securely recorded and verifiable.

Fig. MIPS.sol (Source: github link)

function handleBranch(): This function is essential for managing conditional execution within the MIPS VM. It updates the Program Counter based on the evaluation of branch conditions, ensuring that the program executes the correct sequence of instructions.

• Execution of Branch Instructions: The function processes branch instructions to alter the flow of execution based on specific conditions.
• Updating the Program Counter (PC): It updates the PC based on the branch condition, either jumping to the target address or moving to the next instruction.

Parameters:

• _opcode: The opcode of the branch instruction.
• _insn: The full instruction to be executed.
• _rtReg: The register index used for the branch condition.
• _rs: The value of the register to be compared.

Fig. MIPS.sol (Source: github link)

function HandleJump(): This function is essential for managing jump instructions in the MIPS virtual machine.

• Updating the Program Counter (PC): It updates the Program Counter (PC) to a new destination address specified by the _destparameter. This changes the flow of execution to a different part of the program.
• Handling Link Register (_linkReg): If a link register is specified by the _linkReg parameter, the function stores the address of the instruction following the delay slot in this register. This is typically used in jump-and-link instructions (e.g., JAL), where the return address needs to be saved for later use when the function call returns.
• Managing Jump Delay Slots: It ensures proper handling of jump delay slots, which are a feature of the MIPS architecture. A delay slot is the instruction immediately following a jump instruction, which is executed before the jump takes effect. The handleJump function ensures that this slot is correctly managed, maintaining the expected sequence of execution.
• Returning the Updated State Hash: Lastly, the function computes a hash of the updated VM state and returns it. This hash provides a unique identifier for the new state, ensuring that the jump operation’s effects are securely recorded and can be verified.

Fig. MIPS.sol (Source: github link)

function handleHiLo(): This function processes MIPS instructions involving the HI and LO registers for various operations like moving values to/from HI/LO, multiplication, and division. It updates the VM state and returns the hashed state after performing the required operation.

• Processing HI and LO Register Instructions: The HI and LO registers are special-purpose registers used in certain MIPS instructions, particularly for operations that result in values too large to fit in a single register. Common operations involving these registers include multiplication and division.
• Performing the Operation: Based on the function code, the handleHiLo function performs the necessary operation.
  For example:
  - Multiplication: The result of multiplying _rs and _rt is typically split between the HI and LO registers.
  - Division: The quotient and remainder of dividing _rs by _rt are stored in the LO and HI registers, respectively.
  - Move Operations: Values can be moved into or out of the HI and LO registers.

Parameters:

• _func: The function code of the instruction (determines the specific operation).
• _rs: The value represent the values of the source registers involved in the operation
• _rt: The value represent the values of the source registers involved in the operation
• _storeReg: The register where the result should be stored (if applicable).

Fig. MIPS.sol (Source: github link)

function step(): The purpose of the step function in MIPS.sol is to manage the execution of individual instructions within the MIPS virtual machine, ensuring that each step of the program is processed correctly. It fetches and decodes the instruction, performs the specified operation, updates the VM state accordingly, and returns a hash of the updated state to ensure the integrity and verifiability of the VM’s execution at each step.

Fetching the Instruction: The function begins by fetching the current instruction from the program memory based on the Program Counter (PC).

Decoding the Instruction: Once fetched, the function decodes the instruction to determine its type and the specific operation that needs to be performed. The instruction type could be a jump, branch, arithmetic logic unit (ALU) operation, memory access, or other types of instructions.

Performing the Operation: Based on the decoded instruction, the function performs the appropriate operation. This involves:

• Branch Instructions: Evaluating a condition and potentially altering the PC.
• Jump Instructions: Updating the PC to a new address.
• ALU Operations: Performing arithmetic or logical operations on the registers.
• Memory Access: Reading from or writing to memory locations.
• These function ensures that both conditional and unconditional operations are handled correctly.

Updating the VM State: After executing the instruction, the function updates the VM state to reflect the changes made by the instruction. This includes updating the PC, registers, memory, and any other relevant parts of the VM state.

Returning the Hashed State: Lastly, the function computes a hash of the updated VM state and returns it. This hash acts as a unique identifier for the new state, ensuring that the effects of the instruction are securely recorded and can be verified.

Conclusion

Cannon’s design ensures the accurate and efficient resolution of disputes within Optimism’s ecosystem by combining rigorous offchain processing with reliable onchain verification. This modular and scalable approach lays the foundation for future enhancements, including support for various fault proof mechanisms.

Reference

docs

• https://specs.optimism.io/fault-proof/index.html#pre-image-oracle
• https://docs.optimism.io/stack/protocol/fault-proofs/cannon
• https://docs.optimism.io/stack/protocol/fault-proofs/fp-components

Youtube

• https://www.youtube.com/watch?v=nIN5sNc6nQM

Git-hub

• https://github.com/ethereum-optimism/optimism/blob/546fb2c7a5796b7fe50b0b7edc7666d3bd281d6f/packages/contracts-bedrock/src/cannon/MIPS.sol#L622