Foundation Mission Request – OP Stack Zero Knowledge Proof

To take on this project, submit a proposal to this thread by June 28. Read more about Missions here.

S4 Intent: Technical Decentralization
Foundation Mission (RFP): Implement a zero knowledge proof which can prove Optimism’s fault proof program through an instruction set architecture supported by the golang compiler
Proposal Tier: Fledgling
Baseline grant amount: 250k OP
Accepting one or multiple proposals: Multiple
OP Labs or Optimism Foundation Sponsor: Kelvin (@smartcontracts)
Submit by: June 28th at 19:00 GMT
Selection by: July 13th at 19:00 GMT

How will this Foundation Mission (RFP) will help accomplish the above Intent?

Implementing a zero knowledge proof (ZKP) for OP Chains is a prerequisite to enable secure and low latency cross chain communication between L2 and L1, as well as directly between OP Chains. A ZKP for a well-supported instruction set architecture (ISA) that can prove the Optimism fault proof program acts as the foundation for a system that can prove any OP Stack based blockchain.

What is required to execute this Foundation Mission (RFP)?

Completing this mission means implementing a zero knowledge proof (ZKP) system that can prove the Optimism fault proof program using an instruction set architecture (ISA) supported by the golang compiler such as MIPS, RISC-V, or WASM. This proof system must additionally be shown to work in practice by proving the state transition between two blocks for a standard configuration OP Stack chain.

Support for the fault proof program introduces additional requirements on top of proving a standard execution trace for an ISA. Specifically, the fault proof program introduces the notion of the preimage oracle which uses special system calls to load external data into the program. Every fault proof vm is responsible for implementing some mechanism by which the hash of some data is placed at a particular location in memory, a syscall is executed, and the preimage for that hash is then loaded into memory for the program to utilize. The preimage oracle is also used to bootstrap the program with initial inputs. Please refer to the preimage oracle section of the fault proof program documentation for further information.

For this Mission, the Optimism Foundation will accept up to three submissions. Multiple parallel attempts at creating an OP Stack ZKP will increase chances of success and provide some friendly competition for building the best OP Stack ZKP.

Due to the wide design space, each solution will be evaluated based upon a few Solution Criteria. Due to the scope of this project, this RFP is not expected to be completed within governance Season 4 (June through September). Specific timelines will be discussed with each team that makes a submission.

The target grant payout for each submission will be 250k OP. Teams should discuss the solution criteria below with the Foundation, and may arrive at a different mutually agreeable grant amount dependent on the scope of their work.

Solution Criteria:

Performance — What is the compute cost to generate and verify the proof?
Latency — How long does the proof take to generate?
Complexity — How many lines of code is the prover / verifier?
Robustness — How confident are we that there are no bugs?
Security — What are the assumptions the system relies on for its security guarantees? (e.g. trusted setup)
OP Stack Compatibility — Are there fundamental changes required to the OP Stack?
1. Note 1: It may be the case that small changes to the OP Stack are required to achieve an acceptable performance benchmark. One example of this includes introducing a ZKP-friendly batch submission accumulator to reduce the cost of proving transaction inclusion in the OP Chain. However, the fewer changes the better.
2. Note 2: The current OP Stack state transition function is defined in the fault proof program. Changes are evaluated with respect to this state transition function.

Proposals should include their target architecture and explicitly call out any tradeoffs their approach may have. Multiple proposals which select different tradeoffs may be accepted as each one can have their uses and bring value to the ecosystem.

How should the Foundation measure progress towards this Foundation Mission (RFP)?

Progress can be measured based upon the completion of the following milestones:

Specification: A specification for the ZKP design. Should include the criteria which the implementation will aim to satisfy.
PoC Check-in: A demo of the ZKP being used to prove the OP Stack state transition. The specifics of the PoC are left up to the builder, but the idea is show off the viability of the concept.
Executable demo proving the OP Stack state transition between two blocks: An implementation of the ZKP working end to end and integrated with a live OP Stack chain. This should include instructions which allow anyone to test the proving system themselves.

These milestones mark the completion of the proposal.

Once the proposal has been completed, a final major milestone is the adoption of the ZKP by Optimism Governance. At this point the ZKP may be voted in as a default option in the Superchain bridge, making it a core component of the OP Stack. This is outside of the scope of this proposal but is included here to illustrate the critical importance of this Mission and the massive impact these proofs may have.

How should RetroPGF badgeholders measure impact upon completion of this Foundation Mission (RFP)?

Total number of token bridges using this proof system
Open-source ZKP research shared with the broader community making it easier for future ZKP builders
Fees collected by provers for their proving services

Application instructions

To apply for this RFP, please complete the form in the expandable section below and leave your response as a comment on this issue thread below. Submissions will be open until June 28, at which time the Foundation will review all submissions and select up to three individuals/teams to complete the work defined here.

Submission form

Copy the entire application below and leave a comment on this issue with your answers completed. A representative from the Optimism Foundation may reach out using the contact info provided to request more information as necessary.

Foundation Mission (RFP) Application

Please verify that you meet the qualifications for submitting at the above Tier

Alliance Lead: Please specify the best point of contact for your team
Contact info:
L2 recipient address:
Please list the members of your Alliance and link to any previous work:

Foundation Mission (RFP) Application

Please verify that you meet the qualifications for submitting at the above Tier

Alliance Lead: Phil Kelly
Contact info: [email protected]
L2 recipient address: 0x3f190781756A87750251aDb081e3e2e55de4220d
Please list the members of your Alliance and link to any previous work:
O(1) Labs is responding to this RFP. O(1) Labs is a company that specializes in developing ZKP infrastructure and tooling for Web3. The team was formed in 2017, and comprises of 40+ cryptographers, engineers and other experts. We are globally distributed with team members in Europe, North America, South America and Asia.
[x] I understand my grant for completing this RFP will be locked for one year from the date of proposal acceptance.

Our ZKP-related work includes:

Incubating the Mina Protocol (the world's first ZKP-based, succinct, L1 blockchain)
SnarkyJS (SDK for building client-side ZKP applications)
Kimchi (plonk-based ZKP proving system that does not require trusted set up)
Pickles (halo2-style recursion library for Kimchi)

What makes your Alliance best-suited to execute this Mission?

We're one of the most experienced teams in the ZKP space, with a track record of successful delivery: O(1) Labs has been working with ZKP technology since 2017 and we have proven our ability to deliver on leading class ZKP infrastructure. We incubated the Mina Protocol, which has been running in production since early 2021. We developed and released a SDK for client side ZKPs last year. We have delivered regular updates to both sets of code.
We have a deep bench across all relevant areas of expertise: We are a ZKP-focused engineering organization, with dedicated teams and expertise (theory, design and implementation) across:
- Cryptography
- Protocol
- SDKs
- Infrastructure and automation
We prioritize OSS and build in the open.
We're stable: We are financially stable, with an experienced leadership team.
We're confident in our design: Our proposed approach combines two well-tested stacks to optimize across OP Stack performance and interaction with Ethereum: Our own PLONK-ish proving system, which has been used in production for over 2 years, and the KZG scheme that the Ethereum community recently implemented to prepare for EIP-4844. This approach both delivers a good set of technical benefits, and carries a lower delivery and operational risk than a fully-new build.
We're enthusiastic and committed to this mission: As a measure of our commitment, we have already invested resources in building working (partial-scope) POC code in response to this RFP. This gives us increased confidence in the design and the predicted performance of our proposed solution.

Please describe your proposed solution based on the above Solution Criteria

Solution Overview (definition of some key terms are set out at the end of this section)

Our proposed solution is to implement a fault-proof-program-compatible MIPS VM with efficient instruction execution embedded inside a Nova-folding-style bn128-kzg-plonkish system with deep Keccak support for efficient pre-image oracle access.

This would be used to prove arbitrary fault proof program execution traces. We believe we found a good point in the tradeoff-space that maximizes both OP stack compatibility and performance.

The proof system would be Kimchi, a Halo2-like PLONKish system currently configured with an inner-product-argument style polynomial commitment scheme. Kimchi powers the Mina Protocol. It supports verifiable computation using traditional turing-machine-based instruction sets.

Kimchi is designed to have a swappable backend and while the current implementation is defined over Pasta curves using an inner-product-argument-based polynomial commitment scheme (Pasta-IPA), the proposed implementation would swap in the KZG commitment scheme using the bn128 curves (bn128-KZG).

Solution Overview

Solution Flow

The proposer feeds the inputs to the fault proof MIPS binary which the bn128-kzg Kimchi system can interpret and ZK-prove the execution trace. Just as before, pre-image syscalls are resolved using the unmodified OP Stack pre-image oracle system. Finally, the proof gets sent to a smart contract on Ethereum L1 and then, if valid, updates state on the L1.

Components

Fault-proof-program-compatible MIPS VM
- Cannon emulates big-endian 32-bit MIPS instructions that are used by the Go compiler/runtime. The current PoC partially implements this instruction set and can be used to prove the execution of MIPS programs. Using Kimchi’s VM execution engine, we plan to deliver a to-spec implementation of this MIPS ISA.
Nova-folding-style bn128-kzg-plonkish Kimchi
- We will swap the Pasta-IPA backend for Kimchi out for a bn128-KZG one so that it will be practical to verify on the EVM without any non-standard precompiles. Switching this backend prevents typical proof-carrying-data-based recursion which is currently built via the “Pickles” layer, so instead we will implement a Nova-style folding scheme by adapting Kimchi’s existing constraint description (aka “expression”) framework, using it to bi-linearize the constraints and compute the required “error” term.
Deep Keccak support
- One component of the OP stack system is the pre-image data oracle which is responsible for getting information about the EVM into the MIPS world. The OP stack currently uses the existing ledger which is built on top of Keccak hashes as a baseline. An example workflow: start with hash of block, then get the block and lookup hash of ledger, the first layer of the ledger and request the next layer, etc. With preprocessing we can reduce the loading step to a single layer of lookup from start of ledger → account to reduce the number of hashes in Keccak land.
- By unfolding keccak hashing as a dedicated sub-proof, and using the “bit expansion” approach to calculating XORs and ANDs, as well as a generalization of it to calculate sequences of XORs/ANDs, we can efficiently process Keccak hashes inside the proof system
Efficient VM instruction selection optimization
- The current PoC naively executes every instruction at every step and masks out the parts of the computation that are unused with a one-hot vector.
- Instead, we can generate a dedicated sub-proof for each instruction kind, which only executes the operations necessary for that instruction, and only “pay-for-what-you-use”.
- We expect around a 20x speedup after this optimization given that there are 30+ MIPS instructions that we pay for every step at the moment.

Out of scope

Ethereum L1 Verifier Smart Contract
- This proposal does not cover the implementation of an actual verifier on L1, but as discussed above, the technical choices ensure this is feasible.

Definitions

Polynomial commitment scheme
- A polynomial commitment scheme describes a mechanism to commit to a polynomial. This commitment can be shared publicly, and then can be used to verify that evaluations at specific points are valid (an opening of the commitment). These are used at the hearts of most proof systems, including Kimchi.
Kimchi
- Kimchi is a Halo2-like PLONKish proving system currently configured with an inner-product-argument style polynomial commitment scheme and defined over the Pasta curves (Pasta-IPA). Kimchi supports verifiable computation using traditional turing-machine-based instruction sets. It is designed to have a swappable backend and this feature will be used by this proposed solution.
Pasta-IPA vs bn128-KZG
- The Pasta-IPA configuration enables many nice properties for the proof system (universality, efficient recursion with Pickles (the recursion layer on Mina), etc); however, it is inefficient to verify directly on the EVM without extra precompiles. Due to the existence of certain bn128 Ethereum precompiles, it is more effective to use a backend using the KZG commitment scheme over the bn128 curves.
Nova-style folding
- The Nova family of proof systems achieves recursion-like computation via incrementally-verifiable-computation-style (IVC) folding. You can create a chain of partially completed proofs that can be efficiently completed. For proving machine code execution traces in low-degree constraint scenarios like this one, folding is more efficient than recursion, but requires trusted communication between all parties involved in the protocol.

Criteria

Performance
- The following estimates are based off of the prototype after applying the expected 20x speedup of the VM proving optimization:
  - Running cannon against block 8813569 and 8813570 on Goerli using the configuration in the Cannon example, just changing the l2.head/block-number and keeping all else as equal.
    - Running against block 8813569 uses 44,540,000,000 MIPS instruction-steps
    - Running against block 8813570 uses 44,420,000,000 MIPS instruction steps
  - The difference in gas between those blocks is ~51,500 gas and the difference in MIPS instructions taken is 120M. This implies a cost of ~2300 MIPS instructions per 1 gas.
  - On a modern i9-12900K, 64GB DDR5 machine, it takes 4.75s to run a 2^16 MIPS instruction benchmark using our proof-of-concept, and this translates to 28.5 gas in 4.75 seconds or 6 gas per machine-second. Or after the speedup, 28.5 gas in 0.2375s or 120 gas per machine-second.
  - Using Hetzner machine https://www.hetzner.com/dedicated-rootserver/ex101 as a benchmark, running this machine costs around $100 per month (depending on the euro exchange rate). At 120 gas per machine-second, this is 316M gas per $100 or 3.16M gas per $1 or around $0.0065 per token transfer assuming 21,000 gas per transfer before any of the fixed-overhead costs are applied.
  - There is also a fixed overhead for a fault-proof-program execution that’s on the order of 20-50B MIPS instructions — further investigation is needed to see to what extent this impacts costs when proving many transactions at once. Even after applying a generous 20x penalty multiplier due to fixed costs we still estimate less than $0.15 per txn.
- Note that other planned performance optimizations (outlined in the ‘Future phases’ section) are out-of-scope of the initial grant, but are expected to speed the compute up by at least an order of magnitude.
Latency
- Before a number of significant optimizations, and for the purposes of the initial work within the scope of this grant only, running a single state transition of around 50B instructions serially with the planned in-scope work on a single Hetzner machine https://www.hetzner.com/dedicated-rootserver/ex101 should take about 2 days.
- Although out of scope of this grant:
  - Both proving and folding can be parallelized across machines which should give us at least an order of magnitude speed up if properly used.
  - This scales multiplicatively with the other order of magnitude of performance optimizations that can be applied later as mentioned elsewhere.
Complexity
- Kimchi is currently open-sourced https://github.com/o1-labs/proof-systems and very well-documented: https://o1-labs.github.io/proof-systems/ . Kimchi is currently roughly ~35k lines of code including doc-comments about ~2k lines of parameters and excluding tests. The proposed changes are expected to add 5-10k lines of modifications to generalize kimchi; 3-5k lines of dedicated code (including whitespace, trait boilerplate, doc-comments).
Robustness
- Kimchi is built into Mina Protocol which has been securing the mainnet chain, including a peak market cap of over $6 Billion, with no security breaches since launch in March 2021. Pasta-IPA Kimchi is a part of the Mina’s Berkeley hardfork incentivized testnet which is actively ongoing. The changes are relatively straightforward and our team has experience delivering reliable ZK proof system software.
Security
- The same assumptions as any kzg-bn128-based EVM-friendly snark system: there is a required trusted setup, but we can reuse the powers-of-tau danksharding ceremony parameters.
- There are 128 bits of security with the bn128 curves.
- We also rely on the soundness of the KZG commitment scheme and the hardness the discrete logarithm problem as with any elliptic curve based proving system.
- As with any ZK circuit-based solution, the instruction logic will need to be encoded as polynomial constraints which may require a dedicated audit.
OP Stack Compatibility
- The proposed solution was carefully designed to minimize changes to the existing OP stack system. There are no fundamental changes required beyond excising the existing Cannon system. To be explicit, no precompiles are required.

Please outline your step-by-step plan to execute this Mission, including expected deadlines to complete each piece of work:

We have grouped the major elements of work into Milestone phases, and detailed the elements of each phase in the table below, with time estimates attached.

Grant 1

Workstream	Expected length of each Phase
Phase 1 / Milestone 1 - Complete and confirm specification with OP Labs: Finalized written specification	4 weeks
Phase 2 / Milestone 2: Demo of the ZKP being used to prove the OP Stack state transition: Low-level optimized Keccak in Kimchi, prover hashing changes, Keccak sys-call interface, Folding, Kzg-bn128 abstractions, VM instruction selection, and the complete VM ISA, instrument for the state transition flow.	10 weeks
Phase 3 / Milestone 3: An implementation of the ZKP working end to end and integrated with a live OP Stack chain , CLI host / pre-image integration, Documentation	2 weeks

Future Grants / Phases

Not included in the scope of this work but listed below for context and future consideration are some additional potential phases of work to complete and optimize availability of the solution within OP Stack:

GPU optimizations
Additional CLI config / features
Ethereum Verification Smart Contract
Infrastructure for parallelization of proving
RISCV-64
Running the prover backend operationally
Interop with Mina mainnet
Ongoing support and maintenance

Please define the critical milestone(s) that should be used to determine whether you’ve executed on this proposal:

The milestones are as per the RFP outlined in the workstreams above:
- Specification sign-off
- Demo of a state change
- Demo of tool proving state change on the live chain

Please list any additional support your team would require to execute this mission (financial, technical, etc.):

Design review and sign off
Communication channel (Telegram/Slack etc.) with OP team for ad-hoc questions.
Further optimizations would require additional grants and specific targets in terms of CPU/Memory/Clock time etc.

Grants are awarded in OP, locked for one year. Please let us know if access to upfront capital is a barrier to completing your Mission and you would like to be considered for a small upfront cash grant: (Note: there is no guarantee that approved Missions will receive up-front cash grants.)

Not an issue for us.

Please check the following to make sure you understand the terms of the Optimism Foundation RFP program:

[x] I understand that I will be required to provide additional KYC information to the Optimism Foundation to receive this grant
[x] I understand my locked grant may be clawed back for failure to execute on critical milestones, as outlined in the Operating Manual
[x] I confirm that I have read and understand the grant policies
[x] I understand that I will be expected to following the public grant reporting requirements outlined here
- end of application --

Jun 28 '23 14:06 O1Partners

Foundation Mission (RFP) Application

Please verify that you meet the qualifications for submitting at the above Tier

Alliance Lead: Qi Zhou
Contact info: [email protected]
L2 recipient address: 0x83Ca8766Bac8018a5ff95A7E20F4a21370F147EC
Please list the members of your Alliance and link to any previous work:
- Qi Zhou: Dr. Qi Zhou is a prominent contributor to the Ethereum ecosystem, known for authoring and co-authoring several EIPs, including EIP-4804, EIP-4972, EIP-5018, and EIP-5027, among others. His research interests revolve around building the next generation of Web3 infrastructure, with a focus on areas such as data availability, layer 2 scaling, decentralized storage, and token economics. Dr. Zhou has been recognized for his contributions with multiple grants from the Ethereum Foundation, which have supported his research into topics such as data availability sampling and proof of L2 storage using L1 contracts (EthStorage).
- Qiang Zhu: Qiang is a core developer of EthStorage and a co-author of EIP-6821. Qiang is also a contributor of https://github.com/Inphi/blob-utils developed by Inphi at OP. Furthermore, as a fervent advocate for the Ethereum community, he is the co-founder of Web3Builder.Tech, an influential study group in the Chinese Ethereum community.
- Yanlong: Yanlong is an experienced developer in the blockchain and Ethereum ecosystem. As a core developer of EthStorage, Yanlong focuses on its Proof-of-Storage ZK-SNARK algorithm. Additionally, Yanlong is a contributor of https://github.com/0xEigenLabs/eigen-zkvm, which focuses on implementing zkVM using STARK technology.
- Po: Dr. Po is a core developer of ETHStorage. Po contributes to zk-related research to lower the cost of proof of storage, a critical component of ETHStorage. Additionally, he is an active member of Antalpha-Labs (https://github.com/Antalpha-Labs), a prominent web3 developer community. He dedicates his time to sharing knowledge and writing about zk-related topics. Furthermore, he stays updated on recent zk-related research such as Nova, HyperNova and Protostar.
- Kartin Wong: Kartin is co-founder of Hyper Oracle, a programmable zkOracle network. Previously, he co-authored several EIPs, including EIP-6150, and EIP-7007, with Norman Yu, and Suning Yao.
- Norman Yu: Norman is co-founder of Hyper Oracle. He is a PhD candidate at Imperial College London. Previously, he worked as a blockchain research lead in a cybersecurity firm.
- Suning Yao: Suning is a researcher at Hyper Oracle. He produces research on blockchain, and maintains an ecosystem newsletter on ZK and Layer2.

What makes your Alliance best-suited to execute this Mission?

Our alliance consists of experienced Web3 engineers from EthStorage project and Hyper Oracle project.
EthStorage is a layer 2 storage solution on Ethereum DA (ESP L2 grant recipient). It employs ZK-SNARK and L1 smart contracts to verify the off-chain replications of EIP-4844 BLOBs in a decentralized L2 storage network.
Hyper Oracle is a programmable zkOracle network for Ethereum, providing trust-minimized off-chain computation with zkWASM (ESP KZG grant recipient).
In addition, the alliance members receive Vitalik’s personal grant on cross-L2 bridge and data availability sampling grant from EF. The alliance members also author ERC-4804: web3:// access protocol and ERC-7007: AIGC NFTs.
Moreover, the alliance initiates web3buidler.tech - a developer community for Web3 education with thousands of developers. The group actively reviews the significant events in the Ethereum ecosystem and hosts discussions weekly. The group’s YouTube channel can be found at https://www.youtube.com/@Web-fc1es.

Please describe your proposed solution based on the above Solution Criteria (if applicable):

We are proposing a multi-step zkWASM prover/verifier to reduce the interaction cost/time of current interactive dispute games. By verifying thousands or even hundreds of thousands of WASM steps on-chain using zkWASM, we are able to reduce about 10-18 attack-defence interactions in https://github.com/ethereum-optimism/optimism/blob/develop/packages/contracts-bedrock/contracts/dispute/FaultDisputeGame.sol, thus significantly reducing the finality time of OP.
The zkWASM prover is built on top of https://github.com/DelphinusLab/zkWasm, where our alliance is actively collaborating and co-developing with Delphinus Lab. The prover has been demonstrated to prove thousands or even hundreds of thousands of WASM steps in a practical setup.
The op-program-client will be modified to support WASM target with host support for preimage oracles and hints. The zkWASM circuits will be also added to support host APIs.
A WASM emulator will be implemented to emulate the compiled op-program-client in WASM and to generate corresponding public/private inputs for the zkWASM prover.

Solution Criteria:

Performance — Current state-of-the-art zkWASM prover at https://github.com/DelphinusLab/zkWasm needs a machine with 32+C, 1+TB memory, and 2x4090 GPUs
Latency — Depending on the steps to prove, the time will range from a few minutes (~1K steps) to hours (~100K steps).
Complexity — The zkWASM prover/verifier is already open-source at https://github.com/DelphinusLab/zkWasm. It supports BN128 curve and solidity verifier. Additional host circuits need to be implemented to support preimage oracles/hints.
Robustness — DelphinusLab zkWASM is perhaps the most widely adopted zkWASM with a couple of near-production applications.
Security — https://github.com/DelphinusLab/zkWasm is based on PSE Halo2 with needs of KZG ceremony (can re-use existing ones).
OP Stack Compatibility — The op-program-client needs to be modified to support WASM target (e.g., fastcache is updated to support GOOS=js). No further modification is required in our current estimation.

Please outline your step-by-step plan to execute this Mission, including expected deadlines to complete each piece of work:

we will come up with the specification of the proposal solution in WASM ~ 2-4 weeks
we will modify op-program-client so that the code can be compiled in WASM ~ 4-6 weeks
we will build a zkWASM prover/verifier that can verified one and multiple steps on-chain ~ 8-16 weeks
we will build a WASM emulator to emulate the execution of op-program-client ~ 4-6 weeks
we will integrate all components to an executable demo ~ 2-4 weeks

Please define the critical milestone(s) that should be used to determine whether you’ve executed on this proposal:

A specification for the proposal
PoC with
- An op-program-client in WASM, runnable with op-program-server using existing WASM interpreter (with host API support for preimage oracle/hints)
- One-step zkWASM prover/verifier
Executable Demo with
- Multi-step zkWASM prover/verifier
- WASM emulator to provide public/private inputs to the prover

Please list any additional support your team would require to execute this mission (financial, technical, etc.):

Help to go-through of the plan of interactive dispute games that is under development.

Grants are awarded in OP, locked for one year. Please let us know if access to upfront capital is a barrier to completing your Mission and you would like to be considered for a small upfront cash grant: (Note: there is no guarantee that approved Missions will receive up-front cash grants.)

Not a must, but an upfront capital cover basic labor costs and devices will be helpful.

Please check the following to make sure you understand the terms of the Optimism Foundation RFP program:

[X] I understand my grant for completing this RFP will be locked for one year from the date of proposal acceptance.
[X] I understand that I will be required to provide additional KYC information to the Optimism Foundation to receive this grant
[X] I understand my locked grant may be clawed back for failure to execute on critical milestones, as outlined in the Operating Manual
[X] I confirm that I have read and understand the grant policies
[X] I understand that I will be expected to following the public grant reporting requirements outlined here

-- end of application --

Jun 28 '23 14:06 qizhou

Foundation Mission (RFP) Application

Please verify that you meet the qualifications for submitting at the above [Tier]

Alliance Lead: Steven Li
Contact info: [email protected]
L2 recipient address: 0x1eDE56C5A215F3C64c5Dcf409bFE9644098bF428
Please list the members of your Alliance and link to any previous work:
- RISC Zero - [RiscZero.com] - @RiscZero

Read more about Alliances [here]

What makes your Alliance best-suited to execute this Mission?

At RISC Zero, we are building a general purpose zk virtual machine on the RISC-V ISA. This zkVM is an industry leading system with best in class proving and recursion performance, on chain verification, and exceptional versatility. Our approach is based on the RISC-V instruction set architecture, augmented with peripheral circuits to accelerate common cryptographic tasks such as hashing and ECDSA signature verification. Our zkVM was the first to adopt a standard, general-purpose ISA, and continues to lead the category in maturity and performance, while also providing one of the strongest security guarantees in the industry.
Our team consists of world class engineers, cryptographers, hackers, and entrepreneurs with decades of experience building and leading projects in Blockchain, AI, hardware, formal methods, and computer and network security.
We have built the first and only [continuations system] which allows us to take advantage of large-scale parallelism when proving non-trivial computations.
- Continuations works by taking advantage of a high-performance, non-proving emulator whose runtime is trivial compared to the proving phase. The emulator is used to identify places where the proving steps can be split-up; these splits are then used to allow parallel proving, which can then be rolled-up in logarithmic time.
- With this approach, the effective clock-speed of the prover increases with the size of the computation; as a result, when operating in the parallel regime (such as datacenter deployments and p2p networks), large computations can be proven in logarithmic time.
We have developed the first ZK Fraud Proof System with LayerN by combining the LayerN execution layer with our zkVM. More details regarding this implementation can be found [here].
We have already completed extensive work in generating a ZK validity proof of a ETH L1 transaction and the subsequent block construction. This tooling is based heavily on Reth, which is quickly becoming the industry standard in functionality and performance.
Our zkVM achieves industry-leading performance for non-trivial computations (1B+ cycles, where each cycle is roughly 1 RISC-V instruction) such as those found in the construction of new state roots for Ethereum and Optimism. This is achieved through our use of continuations, which allows large proving tasks to be split up and proven in parallel.
- In internal tests, we have proven 4B cycles of execution at an effective speed of 1MHz on a modest cluster of GPUs (100 GPUs, each using 1 CPU core and less than 10GB RAM).
- Recent improvements will increase this to 2.5MHz. At these speeds, 4B cycles can be proven in under 30 minutes. These numbers were obtained on a cluster that was resource constrained; on a larger cluster, the proof times would have been further reduced.
- Additional recent improvements to our VM and prover are expected to increase the speed to 5MHz in the coming weeks. This would allow 4B cycles to be proven in under 15 minutes, without increasing the size of the proving cluster.
- We believe 10-20MHz will be achieved by the end of the year. This would allow 4B cycles to be proven in under 7 minutes, without increasing the size of the proving cluster.
- Our proving cluster can also easily scale to thousands of GPUs enabling exponential improvements to proof times

Please describe your proposed solution based on the above Solution Criteria (if applicable):

Our proposed solution architecture achieves the goals set forth by the RFP and also:

Minimizes technical risk by leveraging existing tools and technologies.
Maintains compatibility across the OP Stack
Allows us to iterate rapidly towards a protocol ready solution.
Enables us to deliver a performant and functional solution into developer hands in the shortest amount of time.
Takes advantage of the industry leading features of our zkVM.
Our Solution is as follows:

We propose upgrading Optimism’s fault protocol to use zero knowledge proofs instead of the current interactive fault protocol. Specifically, we will provide tooling based on our zkVM that proves correctness of Optimism state transitions to the L1, including:
1. The L1->L2 derivation logic.
2. Sequences of Optimism epochs.
This approach will dramatically reduce the time required to achieve finality. With this approach, Optimism can still publish optimistic state updates; however, instead of a multi-day dispute window, our zkVM-based approach will make it possible to definitively prove the validity of these state updates using ZK proofs.

Once a proof has been published, the state transition can safely be regarded as final. With this approach, anyone who wishes to finalize a state transition can do so by submitting a zero knowledge proof that witnesses the correctness of the state transition, and anyone who seeks to dispute an incorrect state transition can do so by simply publishing a proof of the correct new state. When such a proof is published, the result is twofold:
1. The proof is incontrovertible evidence that a fault has occurred, and can therefore be used to justify slashing the faulty state provider.
2. The proof is also incontrovertible evidence of the correct state, which means that no further debate about the correct state is required.
Our approach is based on a variety of technologies that are functioning as of today:
- Our zkVM, which provides a general-purpose computing environment based on the RISC-V instruction set architecture, augmented with accelerated co-processors for common cryptographic tasks including hashing and ECDSA signature verification.
- Our Ethereum smart contract for verifying proofs generated by our zkVM.
- Our infrastructure for low-cost, high-speed, parallel proving, which makes it possible for large proofs to be generated quickly by leveraging a distributed cluster of GPUs.
- Our Ethereum ZK client, which is based on reth, and which is designed to efficiently run within our zkVM (and which is therefore capable of proving the correctness of state updates for Ethereum-like chains, including Optimism.)
We propose:
- To modify our Ethereum ZK client to have first-class support for Optimism. This will make it possible to prove that a given Optimism block is valid, in the sense that it was obtained by starting from a given “parent” block, together with a sequence of transactions (see next bullet).
- To implement Optimism’s L1 -> L2 derivation logic within our zkVM. This will make it possible to prove that a given sequence of transactions was generated by the Optimism sequencer.
- To implement an epoch union. This will make it possible to prove that a sequence of Optimism epochs (each consisting of L2 blocks generated by our ZK client) is (1) sequentially consistent and (2) constructed using the L2 transactions obtained by the L1 -> L2 derivation logic.
- To demonstrate that the above deliverables (together with our other existing tooling) can prove correctness of Optimism state transitions on the L1.
Our ZK client

Our ZK client consists of two components: a zkVM guest program, i.e., a program that runs within our zkVM (similar in spirit to op-program), and a host library, i.e., a conventional software library that orchestrates execution of the zkVM guest program (similar in spirit to cannon).

The guest program runs within our zkVM. It is responsible for computing the state transition. At a glance, it:
- Consumes the following inputs:
  - A list of transaction requests.
  - Information from the initial (L2) block, i.e., the block that contains the initial state.
  - A partial state tree whose root hash matches the initial state root, and which contains
    - All of the account information and storage nodes that are required to execute the given transactions.
    - All of the branches needed to witness the non-existence of any accounts or storage that are created by the given transactions.
    - Hash commitments (at the greatest possible height) for all other (irrelevant) paths in the state tree.
- Performs the following computations:
  - Verifies that the initial state root matches the value given in the initial L2 block.
  - Verifies the authorizing signature for each of the transaction requests.
  - Sequentially executes the transactions.
    - Generates the transaction outputs (also known as “receipts” in the Ethereum nomenclature.)
    - Updates the partial state tree.
- Generates the following output:
  - A hash commitment to the the initial L2 block (and by extension, the initial state).
  - A hash commitment to the set of transactions.
  - A hash commitment to the set of receipts generated by the transactions.
  - A hash commitment to the new state root.
The host library is responsible for gathering the data required to compute a state transition, as well as orchestrating execution of the guest program within the zkVM. At a glance, it:
- Consumes the following inputs:
  - An L2 block hash (or L2 block number). The block’s state root will be taken as the “initial” state root.
  - A list of transaction requests.
- Performs the following actions:
  - Sequentially executes the transactions, using an L2 RPC provider to fetch the relevant account and storage information.
  - Keeps track of which accounts/storage are needed to execute the transactions.
  - Fetches inclusion/non-existence proofs for the initial state of the relevant account/storage nodes.
  - Using the data provided by the inclusion/non-existence proofs, constructs the partial state tree required by the zkVM guest.
  - Uses the zkVM to execute the guest program with the required inputs.
- Generates the following output:
  - A zero-knowledge proof, generated by our zkVM. This proof witnesses the veracity of the state transition.
Our L1->L2 derivation system

Our derivation program consists of two components: a zkVM guest that uses L1 data to generate L2 transactions, and a host library that fetches the necessary data from the L1.

The zkVM guest will implement the derivation logic described in [this specification] (and as implemented by [Magi]). Specifically, it will
- Consume the following inputs:
  - A sequence of L1 blocks (and their corresponding transactions).
- Perform the following actions:
  - Extract the calldata from the relevant transactions.
  - Read the frame data from those calldata.
  - Deserialize the L2 transactions from the appropriate channels.
- Generate the following output:
  - A hash commitment to the resulting L2 transaction sequence.
The host will facilitate the retrieval of the relevant L1 data, using the Ethereum JSON-RPC interface.

Our epoch union

The systems described above make it possible to prove that a given Optimism block was generated by applying transactions obtained from the L1->L2 derivation process.

To extend this to a complete solution, we will also provide a zkVM guest that implements an epoch union. This guest program will
- Consume the following inputs:
  - Proofs & outputs generated by our ZK client.
  - Proofs & outputs generated by our L1->L2 derivation system.
- Perform the following actions:
  - Verify the given proofs, using the zkVM’s proof-sets feature (which provides efficient “ZK recursion.”)
  - Enforce that the L2 blocks generated by the ZK client are
    - Sequentially compatible.
    - Generated using the “right” transactions.
- Produce the following output:
  - Information about the initial & final state of the Optimism chain
  - Information about the L1 blocks used in the L1->L2 derivation process.
As with the other systems, a host library will also be provided to orchestrate the execution of the zkVM guest.

Benefits of this approach

To reduce project risk, we will base the above on our existing solution for Ethereum. This approach reduces risk in several ways:
- It is already underway and likely to achieve “alpha” status sometime in 2023 Q3.
  - Adapting it to support Optimism is low risk due to Optimism’s noteworthy similarity to Ethereum.
- It is based on Reth’s core components, which allows us to benefit from reth’s industry leading performance and compatibility.
- It is heavily performance optimized for our zkVM.
  - Because it assembles the relevant data in the host program, rather than engaging in interactive host/guest IO, we are able to significantly reduce the amount of computation required by the zkVM.
  - Because it is written in Rust, it does not require expensive garbage collection operations, which again significantly reduces the amount of computation required by the zkVM.
  - It is able to take advantage of the zkVM’s native accelerators for big integer operations, which provides a dramatic speedup for elliptic curve signature verification.
OP Stack integration

The systems described above are designed to integrate into Optimism’s current L1 interface:
- L2 transactions are obtained via the L1->L2 derivation process.
- Sequences of L2 blocks are rolled-up into epochs.
- Epoch proofs can be verified on the L1, and can therefore be used to update the safety status of the L2 blocks held within.
Future Plans

The RISC Zero team is scheduled to start development of a new version of our circuit by the end of the year. This circuit’s unique architecture will allow it to efficiently execute programs compiled to either RISCV64 or MIPS32, both of which are supported by the official Go compiler. It will also will reduce proving time, increase language compatibility, and streamline program integrations. These improvements will enable two additional approaches for Optimism:
- The new circuit will have first-class support for Go, which will make it possible to replace our reth-based ZK client with a new client based on OP-geth. This will reintroduce garbage collection and other overhead into the system, but may still be desirable for teams that prefer Go over Rust.
- A direct port of the cannon fault proof system and op-program onto a RISCV64 or MIPS zkVM. Once again, this will reintroduce garbage collection and other overhead to the system; however, it will also be less disruptive than alternative approaches.
In short, the next version of our circuit will increase optionality and performance.
How does this achieve the goals set forth by the RFP?
- “Completing this mission means implementing a zero knowledge proof (ZKP) system that can prove the Optimism [fault proof program] using an instruction set architecture (ISA) supported by the golang compiler such as MIPS, RISC-V, or WASM.”
  - Our ZK system will integrate directly into the existing Optimism ecosystem, such that no major changes will be required from the OP stack it self. Its outward interface remains in Go in order to connect with the existing code, and will be a “drop in” replacement to cannon and op-program.
- “This proof system must additionally be shown to work in practice by proving the state transition between two blocks for a standard configuration OP Stack chain.”
  - By basing our ZK system on proving the components of OP-reth we will be able to generate a ZK proof for any OP opcode and subsequently any state transition. Additionally we will prove the OP-reth block construction mechanism which enables us to prove the inclusion of a state transition within the L2 block. Subsequently we can prove the state transition between two whole blocks for a standard configuration OP Stack chain.
  - By performing L1->L2 derivation in the zkVM, we can prove the provenance of the transactions used to generate new L2 blocks.
  - By performing an epoch union in the zkVM, we can submit a single proof to the L1 that witnesses the correctness of Optimism epochs.
Solution Criteria
- Performance — What is the compute cost to generate and verify the proof?
  - <2B zkVM cycles for a single Optimism block. For comparison, instrumentation indicates that the current cannon/op-program approach requires 50B+ cycles of execution. The difference can be attributed to the overhead of the Go garbage collector, together with architectural differences between op-program and our ZK client, notably around the handling of oracle data.
  - The reduction in execution cycles directly translates to a reduction in proof time and cost, which is the primary motivation behind the approach described in this proposal.
  - Our on chain verifier takes a constant 200k gas to execute, regardless of the complexity of the state transition. This verifier is based on the popular Circom framework.
    - We currently use the Groth16 backend, whose security characteristics are well known. This requires a trusted setup, which can be handled in various ways. In the future we plan to support other backends (such as Plonk or FFlonk) that remove the need for trusted setup.
- Latency — How long does the proof take to generate?
  - Our prover is able to take advantage of massive parallelism. We have demonstrated proving across a cluster of 100 GPUs, with the ability to scale to thousands.
  - Multiple Optimism blocks can be proven in parallel. The L1->L2 derivation proof can also be generated in parallel with the block proofs. These results can then be rolled-up into a single epoch proof.
  - When sufficient parallel resources are available and our industry first continuations system, we expect that an Optimism block can be proven in 10-20 minutes. The L1->L2 derivation proofs are expected to require similar (or less) time and resources. The epoch union is expected to require even fewer resources.
  - We believe proving time will be further reduced in the coming months, and greatly reduced with the introduction of the next major version of our circuit.
- Complexity — How many lines of code is the prover / verifier?
  - Our ZKP framework is roughly 10kloc of Rust, including
    - 1.6kloc for the prover
    - 1kloc for the verifier
    - Remaining code is split between standard cryptographic libraries and support for accelerated proving on various hardware targets (nVidia CUDA and Apple Metal).
  - Our zkVM is roughly 54kloc of Rust, including:
    - 36kloc of circuit constraints
      - 17kloc for recursive proof verification
      - 19kloc for the VM itself
    - 1.2kloc for finite field operations
    - Remaining code includes the standard library for VM guests, host-side logic to support continuations, high-performance serializers/deserializers for host/guest communication, and related utilities.
  - This effort will be directly supported by the zkVM maintainers.
- Robustness — How confident are we that there are no bugs?
  - We rigorously employ extensive automated testing in our CI.
  - We are in the process of conducting circuit/codebase audits with top firms and will have these audits finished by the end of the year. These audits include traditional design and code reviews, as well as the application of formal methods.
  - The ZK client is based on Reth, which is poised to become an industry standard.
- Security — What are the assumptions the system relies on for its security guarantees? (e.g. trusted setup)
  - The zkVM emits STARK-based proofs that require no trusted setup.
    - 100 bits of security
    - Security is based on widely held conjectures:
      - SHA2 and Poseidon are one-way functions
      - Reed-Solomon proximity gaps.
    - Security can be tuned to reduce or eliminate conjectures concerning Reed-Solomon proximity gaps.
  - On-chain verification is based on STARK->SNARK conversion.
    - SNARKs are verified using logic generated by Circom.
    - SNARK is currently Groth16, which requires trusted setup. Future improvements may add support for alternative SNARK frameworks that do not require trusted setup, such as Plonk or FFlonk.
- OP Stack Compatibility — Are there fundamental changes required to the OP Stack? Will our solution require large changes to the OP stack and introduce new requirements for validators?
  - The simple answer is No; robust compatibility across the entire OP stack today and in the future is a principal goal of ours.
  - With the adoption of ZK, validators can continue to use their existing logic or can instead verify ZK proofs.
Why are we not directly porting op-program on top of our existing zkVM?
- Through our tests, op-program requires more than 50B+ MIPS cycles and 300MB+ in read()/write() to run to completion. Even with purpose built MIPS zkVMs and some of the most cutting edge and performant ZK technologies, we do not believe it is possible to achieve reasonable performance and cost targets in a realistic development time frame.
- The nature of cannon-based fault proofs requires that op-program must retain vast amounts of data in memory. In that context, it is imperative that claims of faults can be proven by potentially disputing the contents of memory.
  
  This requirement is not necessary in the context of zero knowledge proofs, which (by their nature) do not require inspection of intermediate program states by third-parties. With zero knowledge proofs, the correctness of the state transition is a logical consequence of the fact that (1) the correct program (our ZK client) was executed and (2) cryptographically-enforced commitments to the program’s inputs (the initial block and list of transactions).
- While it is technically possible for zkVM guests to retain hundreds of megabytes of data in memory, doing so reduces performance while offering no security benefits.
Why are we basing our work off of OP-reth instead of OP-geth?
- We considered building our ZK state transition program around either the OP-geth or OP-reth clients, in Go and Rust respectively. We ended up making the decision to build on top of the OP-reth client due to our focus on delivering a performant and upgradable OP Stack ZK system. The primary differentiator is Go’s need for garbage collection — an operation that is prohibitively expensive for data-intensive zero knowledge programs.
- [Reth has shown itself to be substantially more performant than Geth.] By building our solution around OP-reth we are able to avoid Go’s intrinsic performance issues and offer a system that enables the “secure and low latency cross chain communication between L2 and L1, as well as directly between OP Chains” that the RFP requires.
- Our deference to performance concerns will result in a vastly superior system by reducing the time and computing resources needed to generate proofs.

Please outline your step-by-step plan to execute this Mission, including expected deadlines to complete each piece of work:

To ensure project success, we propose an execution timeline spanning 6 calendar months in two parallel swim lanes:

ZK client

Milestone 1.1
- Timeline: 4 weeks.
- Summary: Add support for Optimism RPC providers to our existing ZK client. Our ZK client already uses Ethereum’s JSON-RPC standard to fetch information about existing blocks. We will extend this to enable fetching data about Optimism blocks.
Milestone 1.2: add support for Optimism transactions and opcodes to our existing ZK client.
- Timeline: 6 weeks.
- Summary: Our ZK client uses revm to execute transactions for Ethereum. Using OP-reth as a guide, we will add first-class support for Optimism transactions and opcodes to our ZK client.
Milestone 1.3: add support for partial state tree representation to our existing ZK client.
- Timeline: 6 weeks.
- Summary: One of the most performance-critical parts of any ZK client is the efficient construction, update, and verification of modified Patricia tries. We have not yet built this component for our ZK client; we will add this component in this milestone.
Milestone 1.4: testing and validation.
- Timeline: 4 weeks.
- Summary: Testing and validation of the aforementioned components will take place concurrent with their development. Once the basic functionality described above has been implemented, we will execute rigorous end-to-end testing and validation against real-world data from Optimism testnets to ensure all of the components work together as intended.
Milestone 1.5: integration, benchmarks, and delivery
- Timeline: 4 weeks.
- Summary: To ease integration of our solution into the Optimism stack, we will provide necessary Go libraries for generating validity proofs and Solidity libraries for using our on-chain proof verifier. At this stage we will also collect rigorous benchmarking data to document proof generation times under various real-world scenarios.

L1->L2 derivation system (to be built concurrently with the ZK client)

Milestone 2.1: extract channels/frames from L1
- Timeline: 4 weeks.
- Summary: Implement zkVM host/guest logic for identifying relevant L1 transactions from a sequence of L1 blocks, and extract frame data from these L1 transactions.
Milestone 2.2: extract L2 transactions from frame data
- Timeline: 4 weeks.
- Summary: Building on the previous milestone, implement the logic to extract the L2 transactions from the frame data.

Epoch union (to be built after the L1->L2 derivation system)

Milestone 2.3: Generate correctness proofs for entire epochs.
- Timeline: 4 weeks
- Summary: Use zkVM proof-sets to recursively join a collection of L2 block proof(s), together with L1->L2 derivation proof(s), into a proof that covers 1 or more epochs.

Please define the [critical milestone(s)] that should be used to determine whether you’ve executed on this proposal:

Generate state transition proofs for multiple epochs chosen from an Optimism testnet.
- Demonstrate the ability to prove 10 distinct epochs, chosen in consultation with the Foundation to ensure acceptable test coverage.
- Demonstrate the ability to prove a sequence of epochs that spans 180 or more L2 blocks in a single proof.
Validate the aforementioned proofs on an Ethereum testnet.

Please list any additional support your team would require to execute this mission (financial, technical, etc.):

No financial support beyond the grant is required.
The committee must assist in selecting the L2 epochs to be used during final acceptance testing.
An engineer who is deeply familiar with the differences between Optimism and Ethereum must be available to answer technical questions in a timely manner.

Grants are awarded in OP, locked for one year. Please let us know if access to upfront capital is a barrier to completing your Mission and you would like to be considered for a small upfront cash grant: (Note: there is no guarantee that approved Missions will receive up-front cash grants.)

Upfront capital is not a barrier to completing our mission.

Please check the following to make sure you understand the terms of the Optimism Foundation RFP program:

[x] I understand my grant for completing this RFP will be locked for one year from the date of proposal acceptance.
[x] I understand that I will be required to provide additional KYC information to the Optimism Foundation to receive this grant
[x] I understand my locked grant may be clawed back for failure to execute on critical milestones, as outlined in the [Operating Manual]
[x] I confirm that I have read and understand the [grant policies]
[x] I understand that I will be expected to following the public grant reporting requirements outlined [here]
- end of application --

Jun 28 '23 18:06 stevenli27

Submissions for this RFP are now closed. Thanks to everyone who submitted a proposal!

Someone from the Optimism Foundation will reach out on or shortly after July 13 to communicate which proposal(s) have been accepted and schedule a kickoff.

In the meantime, feel free to tag me here or reach out directly ([email protected]) with any questions.

🚀

Jun 28 '23 19:06 bdresser

Hi all – we are extending the selection deadline to July 20 to allow time for review. The Optimism team may be in touch to discuss the proposals above. Again, feel free to reach out with questions.

Jun 30 '23 21:06 bdresser

Hi folks – thank you again for the excellent proposals here.

We're excited to share that we will be moving forward with the proposals from O(1) Labs and RISC Zero.

@stevenli27 and @O1Partners we will be in touch directly to kick off the project and discuss expectations in more detail.

For all other teams here: we'd love to help you find the right way to contribute to the Optimism Collective. See the rest of the issues in the Ecosystem Contributions repo for ideas, suggestions, and other possible projects. And stay tuned for more RFPs posted in the next few months. Thank you again for your proposals.

Jul 20 '23 21:07 bdresser

Hi OP community! Happy to share that work ⚒️ on this has kicked off at O(1) Labs, with detailed design 📋 and planning underway this week on optimized low-level keccak hashing and folding support in our Kimchi proof system. I'll share more details as we progress! 🏃‍♀️

Aug 03 '23 20:08 stevenpack

Hi again OP community! 👋 Some updates on our work to provide a zero knowledge proof of the OP fault proof program 💻 . As a reminder, the major pieces of work (which can you view in our response) are:

Optimizing Kimchi, our proof system for the Mina Protocol, for OP-specific operations like Keccak, that would otherwise be SNARK-unfriendly 😒 -> 😄
Swapping out our pasta-ipa backend with bn128-kzg and combining with folding for more efficient verification 👍
Integrating into the Canon "environment", via the keccak-syscall and a CLI host. ⌨️
Putting it all together. 🧰

You can checkout the low-level, optimized Keccak RFC here. Final comments almost resolved and implementation will kick off soon.

The folding implementation is broken up to 3 separate sub-streams.

Generalize exp framework - RFC approved. ✅ Code implemented and in review! ✔️ Kimchi quadricization - RFC approved ✅ Implementation ready to start 🚗 Folding - RFC approved ✅ Implementation depends on ☝️

Next up is the keccak-syscall integrations and CLI host integration.

Onwards! 🏃

Sep 12 '23 22:09 stevenpack

Greetings Op community! 👋

The RISC Zero team is pleased to announce that we have made significant progress on the following deliverables:

Block building
L1 -> L2 derivation (i.e., provably reading the transaction stream from the Op sequencer)

For the block builder, we have added support for Optimism blocks to Zeth! With this update, Zeth is able to provably construct blocks from Op mainnet. We have tested against a handful of real-world blocks. For example, the proof for block 107728767 takes just under 1B cycles of execution. Using the Bonsai proof cluster (with 64 GPUs) we can prove this block in roughly 23 minutes.

For L1 -> L2 derivation, we have a branch in Zeth that demonstrates the ability to provably read from the Op sequencer using data from the L1. This branch has been tested on real-world data. We are currently optimizing and scaling the implementation.

As next steps, we will continue to expand test coverage for the block builder and improve the L1 -> L2 derivation system to handle large volumes of L1 data.

We are also coordinating with the zkVM platform team, who is working to add support for recursive proof verification. As their work completes we will begin building the “epoch union” tool, which will tie together the block builder & L1 -> L2 derivation system, and also allow proving sequences of Op blocks back to the L1.

Sep 18 '23 23:09 intoverflow

Hi, OP community👋!

I'm excited to present our collaborative efforts from the EthStorage team, in conjunction with Hyper Oracle and Delphinus Lab, in our pursuit of achieving Zero-Knowledge Fraud Proof using Wasm. With minimum modifications to op-program-client and introducing zkGo - a minimum modified Go compiler to produce Wasm code compatible with ZK prover, we are able to compile op-program-client into ZK-compatible Wasm code and pass the zkWasm dry-run with the witness generated by op-program-host!

To be more specific, the following is the overview of the challenges we faced:

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:

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.
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.

Repo to Replay: https://github.com/ethstorage/optimism/tree/js-io/op-program#build-wasi-and-replay-without-op-host-program

The full details can be found at https://perfect-amphibian-929.notion.site/Advancing-Towards-ZF-Fraud-Proof-zkGo-Compiling-L2-Geth-into-ZK-Compatible-Wasm-315a878af5754c549e5003568e1ee124?pvs=4

Sep 26 '23 05:09 qizhou

Hi again OP Community! 👋

Some incremental and positive updates this week. See our proposal above to get a sense of the overall workstreams.

The work for the prover side of folding is in progress. 🚗
The design for the keccak gadget is complete ✅ and the witness generation for it has started 🚗
Expression framework generalisation and constraint bi-linearisation) are complete and in review. ✅
The instruction implementations are in-progress 🚗
Started on cannon client integration. 🚗

Now back to work 👨‍💻

Sep 27 '23 16:09 stevenpack

Hi OP folks and everyone interested in zero-knowledge proofs of OP! 👋

As always, see our proposal above to get a sense of the overall architecture and workstreams. As a reminder some of the big areas are: optimized keccak, kzg-bn128 implementation, MIPS ISA instruction processing, folding, integration with cannon and the pre-oracle hash.

Given the heavy use of keccak in EVM-based systems, its implementation in a zkVM needs to be efficient and so we've invested significantly in that area:

Recent updates:

Keccak's RFC has been updated and is available for review, the implementation is also ready for review. (I.e. initial PRs, not merged yet pending review)

Folding is still in progress and going well.

Our next intermediate goal is and end-to-end execution (with or without folding TBD), including interacting with cannon.

To that end, we've spent a lot of time getting to know cannon, the op-program, op-program-client and setting up test environments to run all these components together. Here is the RFC for this important workstream. Implementation work is about to start.


+-----------------+           +----------------+         +----------------+
|                 |           |                |         |                |
|                 |           |                |         |                |
|     Client      o<--------->o     zkVM       o<------->o      Host      |
|     (MIPS)      |           |                |         |  (op-program)  |
|                 |           |                |         |                |
+-----------------+           +----------------+         +----------------+

Seeing each workstream mature and the integration steps for an end-to-end demo kicking off is super exciting! ❗

See you in a couple of weeks!

Oct 11 '23 12:10 stevenpack

Howdy OP-nation 👋 . Some great progress over here at O(1) Labs in the last 2 weeks. 🔥

Folding landed in our Kimchi proof system -- it is being integrated into zkVM now. I love how succinct this API is.

We're loading the op-program! That means we can read and parse all the instructions exported by Cannon. We're not successfully executing it e2e yet, so there are some instructions in the ISA we're debugging, but this is a good place to be.
As part of that execution, we need to support syscalls for loading block data from the preimage. Check out the very detailed design here

Our next goals 🎯 are:

Completely execute the op-program (with mocked data)
Completely execute with real pre-image data (sourced via syscalls)
Completely execute with folded proof
Capture first performance numbers

Onwards! 🏃‍♀️ 🏃‍♂️

Oct 25 '23 21:10 stevenpack

No updates last 2 weeks due to team offsite and DevConnect. Regular programming (🤣) will resume shortly.

Nov 13 '23 17:11 stevenpack

Hi OP & friends! I'm Austin, the new PM working with the Crypto team at O(1). We've been heads down on the PoC and recently hit an exciting milestone - the zkVM is fully compatible with Cannon!

The e2e demo, performance numbers, and docs to run it yourself are coming soon. Stay tuned!

Dec 15 '23 14:12 AustinBaggio

Hi friends! Quick update from the RISC Zero team:

We've made some big improvements to op-derive (our implementation of L1 -> L2 Derivation). We've tested it on 10,000 real-world blocks from Op mainnet 🥳 The implementation will land into Zeth soon.

Our approach to derivation works like so:

You provide: an Op block to use as a safe head, and the number of Op blocks you'd like to derive.
op-derive then applies the L1 -> L2 Derivation process to derive the transaction lists for the next several blocks (however many you request).

The tool provides the following output:

The hash of the Op head
The hash of the Eth "tail" (the last Eth block that was read during the derive process)
Hashes of the derived blocks

For example, suppose we start from op block 110800000 and derive 3 blocks. The tool would output the following:

Eth tail: 18341377 0x4eb45301f17a8fcdbf65dd1122361db575792b517287121675bf856dfb8122f2
Op Head: 110800000 0x1545e3edbd5b7a5cb1ce231c9eabb6da6dd97596b8db21b81201187b5de6245e
Derived: 110800001 0x45eb3f54dfe4dfe462ebb5f13a4e48b4e3332f0ef48106f241f190dde7b68086
Derived: 110800002 0x89d059ee39f9d41560dbe7f658bb311628e04f7453b566aac5e48b9d01f5183a
Derived: 110800003 0x39c420afa9c7e36a5d2c90c1606035c5264fc3831e21b0fd9e2ae7c75d5e48fb

When we run this process in the zkVM, we obtain a ZK proof of the following:

If the Op head is in the Op history, and if the Eth tail is in the Eth history, then:

Block 110800001 (identified by the given hash) has the right block number, parent hash, and list of transactions.
If Zeth agrees that the given hash for block 110800001 is valid, then block 110800001 is also in the Op history.
If block 110800001 is in the Op history, then block 110800002 has the right block number, parent hash, and list of transactions.
And so on, inductively.

We have begun work on a final integration tool that uses recursive ZK proof verification (aka "proof composition") to put these pieces together. We hope to be testing the integration in January.

Until then, we wanted to share some updated performance data for zeth and op-derive.

For these tests, I used zeth to prove a sequence of Op mainnet blocks. (These proofs were generated using Bonsai, our proof service.)

Op block no	Segment count	Start time	Stop time	Elapsed
110800001	360	0:19:52	0:22:56	0:03:04
110800002
110800003	509	0:38:54	0:42:45	0:03:51
110800004	101	0:49:24	0:51:11	0:01:47
110800005	860	0:59:05	1:05:12	0:06:07
110800006	602	1:05:28	1:09:50	0:04:22
110800007	118	1:10:15	1:12:03	0:01:48
110800008	262	1:12:28	1:15:18	0:02:50
110800009	1142	1:15:34	1:22:58	0:07:24
110800010	664	1:26:08	1:30:44	0:04:36

In the table above, segments is a measure of proof complexity (each segment represents roughly 1M cycles of execution). Time is denoted by hh:mm:ss.

We see that a typical Op block takes 2-8 minutes to prove. The exception is block 110800002, which for some reason takes much longer than the others (roughly 10k segments).

The proof times for op-derive are similar:

Op head	Block count	Eth head	Eth tail	Eth blocks read	Segment count	Start time	Stop time	Elapsed
110800000	10	18341358	18341377	19	1268	1:31:12	1:38:51	0:07:39
110800000	100	18341358	18341391	33	2077	1:39:26	1:51:57	0:12:31
110801000	10	18341523	18341541	18	1136	1:52:39	1:59:47	0:07:08
110801000	100	18341523	18341553	30	1916	2:00:16	2:11:45	0:11:29

Here I ran 4 jobs, two of them deriving only 10 blocks, and the other two deriving 100 blocks. These took roughly 8 and 13 minutes, respectively.

It's interesting to note that it's most efficient to derive large numbers of blocks at the same time. This is due to a combination of factors. In particular, the work required to perform derivation scales with the number of L1 blocks that need to be processed, and it is common for batcher transactions to be "lumped together." This means most Eth blocks contain little information relevant to derivation, but some Eth blocks contain enough information to derive several Op blocks. Larger derive jobs are able to take advantage of this, while smaller jobs end up doing a bunch of work only to throw most of it away.

Anyway! We're pretty excited to share this progress and these initial performance figures. In our next update, expect to hear more about how we're integrating op-derive with zeth to build an end-to-end proof 😁

Dec 16 '23 03:12 intoverflow

Hey OP & friends!

Big update from us at o1 to close out 2023 - We have a working demo of the MIPS zkVM proving OP blocks! 🎉

Danny recorded a video demo, or you can run it yourself by following the commands in this readme. When you run run-code.sh, it will fetch the latest block for Cannon, run Cannon & the op-program to verify the claim is correct, run the zkVM, create a proof, and verify it.

To add a bit of context to the video (Updated): 0:00 - 1': Environment set-up. 1' to 3': Cannon runs with the op-program stopping at 100k instruction as opposed to executing the whole program to save time. There is a longer trace later in the video covering 100M instructions. 3' to 4'02: The zkVM is compiled and run on the same input as Cannon. Here we're showing that Cannon and the zkVM prove the same state transition successfully. 5:10: Shows proving 100M instructions. We log every 10M instructions and take a snapshot of the state. The zkVM log replicates the logs from Cannon. 27:15: The result of the 100M instructions.

Still to go:

Complete implementing IVC (folding)
Complete the pre-image checks integration (keccak)

The o1 team is off on holiday next week for a much-needed break. 🎄 See you all in 2024!

Dec 21 '23 21:12 AustinBaggio

Hello, OP community! 👋

Wishing you all a Happy New Year! We're excited to bring you the latest developments from our team, EthStorage, in collaboration with the hardworking teams at Hyper Oracle and Delphinus Lab.

Our journey in the realm of zk Fraud Proof since the release of the zkGo compiler in September 2023 has been marked by significant strides. Here's a breakdown of our accomplishments across three key areas:

Continuation Proving System: The derivation of a single block using the op-program client was posing a challenge due to ~50 billion Wasm instructions. To overcome this hurdle, we've introduced a groundbreaking continuation proving system. This system segments instructions, processing around 1 million per segment, allowing for parallel proof generation. In addition, the system aggregates all segment proofs in a single proof, greatly saving the verification cost. Our initial rollout, tested with 4 segments, has proven to be successful.
Keccak Host Circuit Implementation: Recognizing the substantial instruction costs associated with the Keccak256Hash function in the op-program client's proving process, we conducted profiling and implemented a Keccak host circuit in zkWasm. This optimized circuit has been successfully tested with a Rust compiled program. Upon integrating the optimized Keccak host function and replacing the original Kecak256Hash function in the op-program, we successfully reduced the number of Wasm instructions from ~50B to ~37B, achieving a remarkable 25% reduction in Wasm instructions.
Trace Generation Optimization: Employing parallelization and caching techniques, we've significantly enhanced trace generation for wasm programs in zkWasm. Witness generation has seen a remarkable 20-fold acceleration compared to our unoptimized implementation. As a result, generating a trace for the op-client smoke_test (~ 2B instructions) only takes about 12 minutes. A summary of the optimization can be found here.

In all, we're thrilled to share our recent progress. Our next milestone involves integrating zkWasm with the op-client's Go implementation compiled by our zkGo compiler for end-to-end proving capabilities. Stay tuned for our next update🚀🚀🚀!

Jan 08 '24 04:01 qizhou

Hey OP and friends, a quick update from O1:

The Keccak integration is nearly complete. The main remaining work is landing the communication channel between the MIPS and the Keccak interpreters, and incorporating the Keccak witness into the proof so that the Keccak circuit is verifiable.
IVC is also almost done. The IVC circuits have been implemented and the main remaining work is landing the IVC dependencies.

Next week we’ll be focusing on integration testing. Stay tuned 🔥

Jan 17 '24 17:01 AustinBaggio

The RISC Zero team is back with another update!

We’re thrilled to announce that we’ve completed our integration work and have generated validity proofs (and verified them onchain!) for a variety of real-world Op epochs, as well as 1 proof that rolls up a sequence of 180 Op blocks into a single proof (!)

As described in our previous update, our tooling splits up the proving process into various subtasks, such as reading transactions from the Op sequencer and executing those transactions in order to construct the corresponding blocks. In our previous updates we have given performance figures for these individual subtasks. Now that we have integrated these components, we are pleased to share the performance for the entire ensemble.

Epochs

We picked 10 random epochs and generated proofs for each. The following table measures proving performance using the Bonsai proving service:

Op head (block number)	Op blocks in epoch	Op transactions in epoch	Op gas in epoch	ZK cycles (sum over all subtasks)	ZK cycles per gas	Proving time (sum over all subtasks)	Proving time per Op transaction
113963903	6	43	31,318,286	4,973,133,256	158.79	44.43m	1.03m
114020225	6	66	17,593,272	6,125,891,706	348.19	45.96m	0.69m
114089340	11	149	67,908,211	12,264,792,370	180.60	162.66m	1.09m
114165247	6	70	76,354,707	8,138,846,749	106.59	88.86m	1.26m
114223488	6	76	32,366,635	5,420,867,580	167.48	61.34m	0.80m
114547269	6	35	34,833,946	5,195,351,593	149.14	92.15m	2.63m
114354386	6	47	32,964,680	4,931,978,261	149.61	63.39m	1.34m
114400259	24	195	159,052,117	23,721,178,029	149.14	252.61m	1.29m
114453440	6	43	42,705,954	8,269,166,215	193.63	102.87m	2.39m
114511643	6	38	26,039,828	7,518,243,384	288.72	116.21m	3.05m

Rolling up 180 blocks

To demonstrate the tooling's composability features, we have also constructed a validity proof for a sequence of 180 Op blocks:

Op head (block number)	Op blocks	Op transactions	Op gas	ZK cycles (sum over all subtasks)	ZK cycles per gas	Proving time (sum over all subtasks)	Proving time per Op transaction
114228596	180	1541	883,744,542	189,559,578,906	214.49	27.05h	1.05m

Performance observations

There is considerable variability in the number of ZK cycles required to process an Op transaction. Using the data above, the average number of ZK cycles required per gas is 196.54, though there is a fair bit of variable due to misalignment between the gas schedule and the ZK-cost of various EVM instructions.

The best indicator of overall proof cost seems to be the number of transactions. Here, we see that a typical proof requires 1.15 minutes to prove per transaction included in the proof. But again, there is a fair bit of variance due to outlier transactions.

We believe the average and variance in these statistics will be reduced through circuit and library improvements currently planned for later this year.

Onchain verification

We have verified the proofs listed above using our onchain proof verifier (on Sepolia). For example, our 180-block rollup was verified in this transaction.

These proofs cost less than 250k gas to verify. In a fully integrated solution, the Op L1 contract could use this verifier to validate proofs generated by our tooling, in either a full-validity mode, or alternatively in a ZK-fault-proof mode. In the latter, the dispute protocol could be simplified such that the accuser simply provides a proof for the block (or epoch) in question, definitively establishing its correct value.

Conclusions

These data demonstrate the end-to-end flow described in our project proposal. It has been exciting to get deep into the Op architecture, expand the capabilities of the Zeth prover, and build tooling for the L1 -> L2 derivation procedure.

It has also been exciting to see the progress made by our colleagues at O1 and the collaboration between EthStorage, Hyper Oracle, and Delphinus Lab. The future of ZK+OP is clearly bright and we look forward to the next steps for this Foundation Mission 🚀

Feb 14 '24 22:02 intoverflow

Very well done.

Mar 05 '24 06:03 modewei

ecosystem-contributions
ecosystem-contributions copied to clipboard

Foundation Mission Request: OP Stack Zero Knowledge Proof

Foundation Mission Request – OP Stack Zero Knowledge Proof

How will this Foundation Mission (RFP) will help accomplish the above Intent?

What is required to execute this Foundation Mission (RFP)?

Solution Criteria:

How should the Foundation measure progress towards this Foundation Mission (RFP)?

How should RetroPGF badgeholders measure impact upon completion of this Foundation Mission (RFP)?

Application instructions

Foundation Mission (RFP) Application

Foundation Mission (RFP) Application

Solution Overview

Solution Flow

Components

Out of scope

Definitions

Foundation Mission (RFP) Application

Foundation Mission (RFP) Application

Epochs

Rolling up 180 blocks

Performance observations

Onchain verification

Conclusions

ecosystem-contributions ecosystem-contributions copied to clipboard

Foundation Mission Request: OP Stack Zero Knowledge Proof

Foundation Mission Request – OP Stack Zero Knowledge Proof

How will this Foundation Mission (RFP) will help accomplish the above Intent?

What is required to execute this Foundation Mission (RFP)?

Solution Criteria:

How should the Foundation measure progress towards this Foundation Mission (RFP)?

How should RetroPGF badgeholders measure impact upon completion of this Foundation Mission (RFP)?

Application instructions

Foundation Mission (RFP) Application

Foundation Mission (RFP) Application

Solution Overview

Solution Flow

Components

Out of scope

Definitions

Foundation Mission (RFP) Application

Foundation Mission (RFP) Application

Epochs

Rolling up 180 blocks

Performance observations

Onchain verification

Conclusions

ecosystem-contributions
ecosystem-contributions copied to clipboard