Zk fault proof for opBNB

Background - generic VM v.s. custom circuit 

In the last year, Optimism initiated a Foundation Mission Request to develop the Op Stack Zero Knowledge Proof (ZKP) for verifying the correctness of its fault proof program. Once implemented, this ZKP can reduce the challenge period for Optimism from 7 days to 12 hours and avoid complicated interactive challenge procedures.

Optimism accepted and funded three proposals from Risc Zero, O(1) Labs, and the ETH Storage team. Each team proposes a similar approach, where the fault proof program, written in Go or Rust, is compiled into a generic instruction set such as RISCV, WASM, or MIPS.

These compiled instructions are then verified for correctness using zkVMs like zkRISCV, zkWASM, or zkMIPS, which we refer to as the generic VM approach. An alternative approach involves developing a custom circuit for the fault proof program, which we believe offers better performance compared to the generalized VM method. 

Recently, Polygon Zero announced the development of a highly performant type1 zkEVM, which aligns with our expectations for creating a custom circuit for opBNB’s fault proof program. Therefore, we have decided to develop a proof of concept (PoC) based on Polygon Zero’s type1 zkEVM codebase to demonstrate the performance advantages compared to the generalized VM approach. The PoC involves the protocol specific to Optimism, and can be used to generate ZKP for Optimism blocks.

The figure below illustrates the simple workflow of the two approaches. It is worth noting that our proposal aims to improve and enhance the robustness of the Optimism multi-proofs system.

Current Fault Proof Overview

Before delving into the ZK fault proof design, Let's quickly review the current optimism fault proof design.

The offchain fault proof program consists of two parts:

• Derive the disputed block from the anchor L1 block hash;
• Execute the disputed block based on the agreed L2 state root and compare the execution result with the claimed output root

The onchain fault dispute game works as following:

• The attacker and defender take turns initiating on-chain actions based on the claims submitted on-chain by their opponents until they agree on the disputed L2 block;
• Repeat the above challenge process until they agree on the disputed instruction of the off-chain fault proof program, which uses the disputed L2 block as the input;
• Invoke the on-chain MIPS contract to execute the disputed instruction which will determine the winner

The above fault proof design has following disadvantages:

• The attacker or defender needs to send many on-chain transactions, resulting in significant gas cost;
• The attacker or defender is susceptible to censorship attacks, where transactions become harder to include in the L1 chain due to congestion created by either party. To mitigate this risk, the on-chain dispute game must allocate sufficient time for each player to act, resulting in the long challenge period

Architecture of ZK Fault Proof

The ZK solution for fault proof is designed to address the aforementioned disadvantages. The following figure illustrates the components and workflow of the ZK fault proof design:

• Optimism Block Execution Circuit: This circuit processes L2 blocks according to the Optimism state transition protocol and generates an execution proof to verify the correctness of the L2 block;
• Optimism Block Derivation Circuit: Derivation means deriving L2 blocks from L1 data. This circuit encodes the Optimism block derivation logic from an L1 block hash and produces a derivation proof to verify the correctness of the derived L2 block;
• Fault Proof Circuit: This circuit encodes the ZKP verification logic to validate both the execution proof and derivation proof, and includes the consistency check logic between the public inputs of the circuits;
• zkFaultProofVerifier Contract: This contract resides on the L1 chain and is used to verify the correctness of the ZK fault proof, determining which party wins.

The challenger monitors the L2 output root proposed on-chain by the proposer. Upon finding an invalid output root, the challenger can generate a ZK fault proof for the disputed L1 block and submit it to the zkFaultProofVerifier contract. If the verification passes, the challenger wins.

The ZK fault proof approach has the following advantages:

• Challenger only needs to submit one on-chain transaction to the L1 which greatly reduce the gas cost;
• Since the dispute result can be determined with just a single transaction, the challenger is less susceptible to censorship attacks. Therefore, the challenge period can be appropriately reduced to improve user experience.

Our work

To demonstrate the performance advantages of the custom circuit, we quickly developed a PoC based on type1 zkEVM. This PoC only includes the Optimism block execution circuit, which is the most time-consuming of all the circuits mentioned above. The adoption work we have done is as follows:

• Changed the gas fee calculation mechanism according to opBNB protocol;
  • opBNB transaction fees consist of two components: the Execution Gas Fee and the L1 Data Fee. 
  • The Execution Gas Fee covers the cost of executing transactions on L2, similar to Ethereum's gas fee. The L1 Data Fee covers the cost of publishing L2 transaction data on Ethereum. More information can be found here
• Added the handling logic for Deposited Transaction and Deposit Receipt;
  • Deposited Transactions are derived from L1, and included in a L2 block. There are two kinds of deposited transactions: L1 attributes deposited transaction (submits the L1 block's attributes to the L1 Attributes Pre-deployed Contract) and User deposited transactions (transactions derived from an L1 call to the deposit contract). More information can be found here
• Fix bugs in the MPT trace generation codes;
• Add parallelization code for transaction proof generation

Performance Testing 

We conducted a performance test for the same L2 batch using the opBNB custom circuit and Zeth developed by Risc Zero. The opBNB custom circuit is more efficient than the generic VM approach, generating 10 times fewer ZK cycles and proving 5-6 times faster than zeth. This makes the opBNB approach 5-6 times cheaper. 

The tables below show the configuration and performance data for both.

Configurations for opBNB custom circuit and Zeth:

Batch information used in opBNB custom circuit and Zeth

Zeth generic vm approach and opBNB custom circuit performance data:

Based on the performance tables above, we can draw the following conclusions:

• From the perspective of ZK cycles, the opBNB custom circuit is more efficient than the generic VM approach. For the same batch, the number of ZK cycles generated by the generic VM method is 10 times that of the type1 zkEVM;
• From the perspective of proving time, when we consider the fixed server costs for the opBNB custom circuit and zeth, the opBNB is 5-6 times faster than zeth;
• Similarly, when considering generating ZKPs within the same time window, we can conclude that the opBNB custom circuit approach is 5-6 times cheaper than zeth based on the generic VM approach.
• There are some batches(113963903, 114223488, 114511643) where the performance of the opBNB custom circuit doesn't meet expectations.

Future work

The type1 zkEVM is currently in development, with features like continuations designed to make proof generation more parallel-friendly. Additionally, efforts are underway to enhance the performance of the backend proving system. The opBNB team can contribute to these planned improvements. We believe that the performance of the opBNB custom circuit approach will significantly improve as the performance of the type 1 zkEVM continues to advance.

To achieve a complete ZK fault proof for Optimism or opBNB, we need to implement all the components such as the block derivation circuit, fault proof circuit, and the on-chain zkFaultProofVerifier contract. These will be important tasks for the next phase of our PoC.

Once the development of the opBNB custom circuit design is complete, the opBNB team will contribute this work to the Optimism ecosystem to enhance the security and performance of the multi-proof system.

1 For batch 114223488, the proving time of opBNB is only 2.5 times faster than zeth. This is due to the presence of a complex transaction in this epoch, which involves approximately 2^27 cycles. Because the type1 zkEVM lacks a continuations mechanism, the transaction proof generation process cannot be fully parallelized, resulting in a 47.6-minute proof generation time. In contrast, the total proving time for the other transactions in this epoch is only about 25 minutes; The above analysis also applies to the batch 113963903 and 114511643.