Advancing Towards ZK Fraud Proof — zkGo: Compiling L2 Geth into ZK-Compatible Wasm

Author: Qi Zhou, EthStorage

Note that this is a joint work with Hyper Oracle and Delphinus Lab

TL;DR

• ZK fraud proof is a validity proof of L2 block transition.
• ZK fraud proof enables the challenge of a malicious sequencer in a single transaction, significantly reducing gas costs and time compared to traditional fraud proofs.
• To generate a ZK fraud proof, we emulate the L2 Geth in an instruction set architecture (ISA) and prove the execution result using zkVM.
• We choose WebAssembly (Wasm) — a widely adopted open-standard ISA and prove the execution of Wasm code using zkWasm, the state-of-the-art zkVM for Wasm developed by Delphinus Lab.
• Directly compiling L2 Geth to Wasm with Go proved challenging, necessitating modifications to L2 Geth to support Wasm compilation.
• Further, we introduced zkGo — a minimum modified Go compiler to produce Wasm code compatible with ZK prover.
• As a result of these modifications, the execution of the compiled L2 Geth Wasm code can now be proven using zkWasm.

Motivation

Optimistic Rollup stands out as a widely adopted Layer 2 solution designed to scale Ethereum. This approach optimistically posts L2 transactions and their execution outcomes on the Ethereum mainnet, substantially reducing the costs associated with on-chain execution. To ensure the correctness of these execution results, Optimistic Rollup employs a mechanism that permits anyone to challenge the outcome with a fraud proof. This entails an interactive on-chain dispute game between the challenger and the sequencer. The objective is to pinpoint the specific instruction where disagreement exists between the two parties and then replay that instruction on-chain to determine the rightful winner. This approach significantly lowers the expenses of generating validity proofs for L2 transactions, as seen in other popular rollup solutions like ZK Rollup.

However, the interactive nature of on-chain dispute games often involves multiple rounds of on-chain interactions (for example, up to 32 interactions in a 4-billion-instruction game). Consequently, considering the worst cast attack scenarios, Optimistic Rollup typically requires 7-days challenge period) before finalizing an L2 transaction. Moreover, when Ethereum’s gas prices are high, the multiple interactions within the dispute game can incur substantial gas costs.

To address these challenges, a proposal known as ZK fraud proof has emerged to harness the benefits of both Optimistic Rollup and ZK Rollup. The fundamental concept behind ZK fraud proof is to replace the multi-interaction dispute game with a single ZK fraud proof. This proof validates the L2 block transition in a single transaction, resulting in significant time and gas cost savings compared to the dispute game.

However, proving an L2 block transition in ZK fraud proof is no simple task, and it is even more intricate than Type 1 zkEVM. The complexity arises from the need to emulate the L2 execution engine written in a higher-level language, such as L2 Geth in Go, within a lower-level instruction set architecture (ISA). This ISA can produce lengthy traces, sometimes comprising billions of instructions, and demand substantial memory resources (approximately 64MB or more) that may exceed the limit of the prover supported. The advantage of proving approach lies in its maximal reutilization of the battle-tested execution engine code such as Geth. Due to characteristics, this approach is sometimes referred to as Type 0 zkEVM.

In this article, we aim to provide an update on our progress in proving the Optimism fault-proof program (op-program) using WebAssembly (Wasm) as the chosen ISA and zkWasm as the ZK virtual machine (zkVM).

What is OP-Program?

Op-program serves as the default implementation of the Optimism fault-proof program, consisting of two essential components:

1. op-program-client: This component is responsible for accepting the parameters of the L2 block and then replaying the block through a minimally modified version of Geth (L2 Geth). Following execution, it determines the correctness of a claim regarding the execution result.
2. op-program-host: This component acts as a host environment for op-program-client, providing the essential data required for op-program-client to replay a block. This data encompasses block headers, block bodies, transaction receipts, and trie nodes pertaining to the state tree in both Ethereum L1 and L2.

In the context of ZK fraud proof, our objective is to emulate and prove the execution of op-program-client using an ISA and its zkVM, and utilize op-program-host to generate the necessary data, often referred to as the “witness.” This witness will then be fed as private inputs into the zkVM prover, along with the replay parameters as public inputs. The key consideration at this juncture is the selection of the appropriate ISA and zkVM to fulfill this task effectively.

What is zkWasm?

Wasm stands out as one of the most widely adopted ISAs. It is presented in an open standard binary code format, closely resembling traditional assembly language. The versatility of Wasm is evidenced by its support in a multitude of programming languages, including C, Rust, and Go. Furthermore, executing Wasm is a straightforward process, as nearly all web browsers come equipped with a Wasm interpreter. Additionally, a variety of mature Wasm interpreters and tools, such as Node.js, Wasmi, Binaryen, among others, are readily available for developers.

Within the realm of ZK Proofs, DelphinusLab’s zkWasm (https://github.com/DelphinusLab/zkWasm) emerges as the most advanced zkWasm prover and verifier. It boasts several near-production applications and has proven its capability to handle tremendous Wasm steps within practical implementations. To ensure the correctness of the compilation of all operations into circuits, zkWasm leverages a formalization tool Z3 (https://github.com/Z3Prover/z3).

Overview of Challenges and Solutions

While Go does indeed support Wasm compilation, we encountered several challenges when attempting to run op-program-client in zkWasm:

• Unable to Direct Compile of op-program-client to Wasm.
• Insufficient Memory to Run op-program-client in zkWasm: The default op-program-client from Optimism requires over 300MB of memory, surpassing the memory limit supported by zkWasm.
• Dependence on JavaScript/Browser Host Environment: the compiled Wasm code relies on a JavaScript/Browser host environment, which is impossible to emulate in zkWasm;
• Divergent I/O Models: the compiled Wasm code uses a different I/O model compared to that of zkWasm;
• Unsupported Instructions: the compiled Wasm code utilizes instructions that zkWasm does not support, including floating-point operations and bulk memory instructions;
• Unclean proc_exit: The compiled Wasm code employs an unclean proc_exit approach, while zkWasm requires a normal program exit by returning from the main function.

To overcome these challenges, we have devised the following solutions:

1. Minimum Modifications to op-program-client: We made minimal modifications to op-program-client to enable successful Go Wasm compilation and reduce the memory footprint of op-program-client to fit into zkWasm capacity.
2. zkGo with Minimum Modifications to Go v1.21.0: We introduced minimal alterations to Go v1.21.0 to facilitate the compilation of op-program-client (and, in most cases, other Go programs with minimum modifications) that can be directly supported by zkWasm.

Modifications to OP-Program-Client

Compiling OP-Program-Client in Wasm

The initial challenge we encountered was the inability to directly compile op-program using Go’s Wasm compilation. This limitation stemmed from certain libraries utilized by L2 Geth, which uses OS interfaces such as mmap/rlimit/socket that are unsupported by the Go Wasm compiler. In fact, a similar issue was identified in Arbitrum's AVM (Arbitrum Virtual Machine), a modified Wasm, which resolved these dependencies to support Wasm as a target platform. Benefitting from the groundwork laid by Arbitrum, we followed similar steps and successfully compiled op-program into Wasm.

Reduce Memory Usage of OP-Program-Client

The second challenge arose from the fact that the default op-program-client consumes more than 300MB of memory, surpassing the maximum memory capacity supported by zkWasm. To address this memory consumption issue, we conducted a comprehensive memory footprint analysis of the op-program-client. During this analysis, we identified a substantial portion of memory dedicated to caching I/O operations. By removing this cache, we successfully reduced the memory footprint from 300MB to 39MB, ensuring it falls within the maximum memory limit supported by zkWasm.

zkGo — Minimal Modifications to Go for Generating ZK-Compatible Wasm

1. Replacing the Dependency on a JavaScript Host with an OS-like Host

Unlike Wasm programs compiled in C or Rust, which can function in minimal host environments, Wasm programs compiled in Go depend on a JavaScript environment (with Go build flag GOOS=js). This introduces a multitude of imports that zkWasm cannot emulate. To address this issue, we chose to compile op-program-client using the WebAssembly System Interface (WASI) preview 1 (GOOS=wasip1) introduced in the latest Go compiler version 1.21.0 released on Aug. 8, 2023.

2. Adapting the IO Model for zkWasm Compatibility

The WASI-compiled op-program relies on standard OS-like interfaces such as read/write, whereas zkWasm operates with ZK-based IO interfaces like wasm_input(isPublic) and wasm_output for public/private inputs. To ensure seamless compatibility without altering zkWasm's codebase, we modified the Go compiler to replace OS-like interfaces **read/write** with ZK-based IO interfaces **wasm_input/wasm_output** . Additionally, since op-program does not utilize the remaining WASI interfaces such as environ_get/args_get/fd_stat, we substituted them with no-op mock implementations within the Wasm environment. This adjustment results in zkGo generating clean Wasm code with minimal external dependencies (imports), enabling the reading of both ZK private and public inputs from op-program-host.

WASI-compiled code relies on a list of OS-like interfaces (imports).

After IO Model adaption, the compiled Wasm code only relies on 3 imports.

3. Substituting Unsupported Instructions

Regarding floating-point instructions, we replaced them with softfloat instructions. In our exploration, we uncovered a hidden flag within the Go compiler to support softfloat, albeit with a minor bug related to floor/ceil instructions. We promptly reported this issue to Google and shared our solution in the following link.

All floating-point instructions are replaced with softfloat instructions.

For bulk memory instructions, we identified a Google PR introducing these instructions. By reverting this PR, we were able to eliminate the unsupported instructions in our code.

4. Replacing proc_exit with a Normal Exit

In the context of Wasm, the compiled Go program calls proc_exit regardless of whether it exits through os.Exit()/panic() or returns from the main function. However, zkWasm requires a standard exit (return from the Wasm main) to determine the termination of zkVM. To accommodate this requirement, we modified the Go compiler with assembly code, ensuring that the compiled Wasm program performs a proper return from the Wasm main function.

How to Play with zkGo?

As a result of our above work, a developer can easily create a Go program and compile it into ZK-compatible Wasm by following these steps.

• Call wasm_input()/wasm_output() to perform I/Os;
• Make sure the program exits via the main function return;
• Run GOOS=wasip1 GOARCH=wasm go build file_to_build.go using zkGo.

To interact with the compiled op-program-client in Wasm and perform a dry run using zkWasm, you can refer to the instructions provided here.

Future Directions

Parallel Proving with Proof Aggregation

Replaying a block transaction using op-program-client involves executing billions of instructions, a task that cannot be feasibly proven in a single ZK pass due to limitations in the available number of rows or the extended time required. Our immediate focus is on dividing this complex proof into smaller, manageable tasks that can be proven in parallel. By combining this approach with proof aggregation and batching technologies, we aim to produce a succinct proof capable of verifying billions of instructions in significantly less time. We are actively collaborating with Hyper Oracle and Delphinus Labs to advance research and development in this direction.

Exploring New Proving Systems

zkWasm currently utilizes halo2 as its frontend, offering the flexibility to switch to alternative proving systems in the backend. We are engaged in ongoing collaboration with Hyper Oracle and Delphinus Labs to explore more efficient proving systems. Our objective is to further reduce the time and cost associated with generating ZK fraud proofs, enhancing the overall efficiency of the process.

Acknowledge

Many thanks Frank Liu, Junfeng Chen, and Suning Yao for reviewing the article.

For more information, please join EthStorage’s community:

• Website: https://ethstorage.io/
• Twitter: https://twitter.com/EthStorage
• Discord: https://discord.com/channels/1040111910802182186/1040111911238381619
• Telegram: https://t.me/ethstorage