[RFP Submission] OP Stack Zero Knowledge Proof

ARCHIVED & OLD Missions
1

  • S4 Intent: Technical Decentralization

  • Proposed Mission: Implement a zkVM (RISCV64 or MIPS) that adheres Cannon’s virtual machine architecture.

  • Proposal Tier: Fledgling

  • Baseline grant amount: 250k OP

  • Alliance Lead: Tsiao

  • Contract Info:

  • L2 recipient address: 0x7dc04FB18731032eD89236961B1a13E3d6102AE6

  • Please list the members of your Alliance and link to any previous work:

    • Tsiao - a developer, cryptography enthusiast. He has profound experience in zero knowledge proof (ZKP) technology. Prior to the proposal, he did the following ZKP-related activities.
      • He systematically studied ZKP at university and actively participated in zku-cohort-3 where he gained exceptional skills in writing circuits.
      • Additionally, he has participated in CTF competitions and achieved several first prizes, showcasing his expertise in computer security.
    • Wenbin - a developer with more than five years of experience blockchain technology, specializing in consensus and layer 2 solutions.
      • Proficiency in permissionless blockchain development, with a deep understanding of multi-signature algorithm, multi-party secure computing, and optimistic Layer2 solutions.
      • Before applying, he served as the one of core developer for a well-known modular Layer2 blockchain project.

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

  • We are an alliance with experience in both engineering and theory. We have a strong interest in ZKP.
  • We have well-established mechanism in place to distribute benefits among our alliance members. Each person will receive a financial reward commensurate with his workload, fostering a strong sense of unity among us.
  • What sets up apart from from freelencers is our philosophy that prioritizing product delivery. We consistently meet our planned timelines and firmly believe in the importance of timely project completion.
  • Completing the mission aligns with our goals. There is a high probability that we will continue to maintain the zkVM project even after completing this mission.

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

We have two options and eagerly anticipate further discussions with the OP team to select one of them.

  1. Implement a zkMIPS which is nearly equivalent to Cannon’s virtual machine.
  2. Implement a zkRISCV64. Considering that Wave Computing announced the cessation of MIPS ISA development in March 2021 and the decreasing number of MIPS devices, we have concerns about the availability of MIPS compilers in future versions of Go. Therefore, we propose the RISCV64 route.

zkMIPS

Our solution is implementing a zkMIPS which is nearly equivalent to Cannon’s MIPS virtual machine (VM). The term ‘nearly’ indicates that we will optimize the VM to be zkSNARKs friendly. Our solution support OP’s fault proof. In the near future, we anticipate a smooth transition from Cannon’s MIPS VM to zkMIPS VM with minimal adjustments to the existing code in Cannon’s implementation.

We conducted a thorough survey and found serveral zkVMs; however, none of them meet the requirements of OP stack.

  • risc0: a riscv32 zkVM, but the riscv32 ISA is not supported by the golang compiler. It is based on zkSTARK with FRI polynomial commitment, which means it has high verifier cost.
  • zkWASM: a wasm zkVM, supported by the golang compiler, but it lacks the key component for fault proof, such as pre-image and hint, which are descripted in OP’s spec.
  • miden-vm, ola-vm, valida-vm: They are all define their own ISA tailored to gain higher prover performance, non of these ISAs are supported by the golang compiler.
  • pse/zkevm, scroll-zkevm, polygon-zkevm: They are zkEVMs. Compare to OP, they are purely different ways to implement layer 2. That means they can not be utilized to implement zk fault proof.

Besides this, somewhat they all suffer poor proof generation time. Here we bench the zkEVM inside risc0 and pse/zkEVM on a 16 cores, 128 GB RAM machine, the results show they can not generate proof for ERC20 transfer within 1 minute.

zkVM ISA Proof System / Commit Scheme Proof Size Verifier Cost Support Golang Support Cannon Fault Proof
risc0 RISCV32 zkSTARK / FRI $O(log^2 \ n)$ $O(log^2 \ n)$ :x: :x:
miden-vm Custom zkSTARK / FRI $O(log^2 \ n)$ $O(log^2 \ n)$ :x: :x:
ola-vm Custom zkSTARK / FRI $O(log^2 \ n)$ $O(log^2 \ n)$ :x: :x:
pse/zkevm EVM halo2 / KZG $O(1)$ $O(1)$ :x: :x:
scroll/zkevm EVM halo2 / KZG $O(1)$ $O(1)$ :x: :x:
polygon/zkevm EVM zkSTARK / FRI+KZG $O(1)$ $O(1)$ :x: :x:
zkWasm WASM halo2 / IPA $O(log \ n)$ $O(log \ n)$ :white_check_mark: :x:
zkMIPS MIPS halo2 / KZG → HyperNova / Folding $O(1)$ $O(1)$ :white_check_mark: :white_check_mark:

We denote circuit size as $n$, The above table lists various zkVMs and their corresponding instruction set architecture (ISA), proof system / polynomial commitment scheme, etc.

As a latecomer, zkMIPS will be designed to avoid the disadvantages of the above zkVMs, here are our goals.

  1. zkMIPS should support mips ISA, produce assertion proof for any golang program.
  2. zkMIPS should support the pre-image and hint components in fault proof, which plays a crucial role in Cannon.
  3. zkMIPS should have a considerable prover performance. This is achived by utilzing GPU and adopting cut-edge ZKP algorithm.
  4. zkMIPS should have a cheap cost for verifying proof. It is important because the verifier is a contract on L1, the gas price is expensive.

In the short term we will utilize plonkish, custom gates, lookup tables to implement zkMIPS, and we plan to utilze GPU to accelerate the proof generation. Our long term vision is implementing a zkMIPS based on folding, which proposed in Nova, and it enables ~50x prover performance.

The zkMIPS should support the following 55 instructions:

'addi', 'addiu', 'addu', 'and', 'andi',
'b', 'beq', 'beqz', 'bgez', 'bgtz', 'blez', 'bltz', 'bne', 'bnez',
'clz', 'divu',
'j', 'jal', 'jalr', 'jr',
'lb', 'lbu', 'lui', 'lw', 'lwr',
'mfhi', 'mflo', 'move', 'movn', 'movz', 'mtlo', 'mul', 'multu',
'negu', 'nop', 'not', 'or', 'ori',
'sb', 'sll', 'sllv', 'slt', 'slti', 'sltiu', 'sltu', 'sra', 'srl', 'srlv', 'subu', 'sw', 'swr', 'sync', 'syscall',
'xor', 'xori'

It also should implement Preimage and Hint read and wirte for system call. The keccak256 in Preimage is the most heavy part for ZKP. Poseidon is an arithmetization-oriented hash function, meaning that it is ZKP friendly, so we plan to use Posidon instead of keccak256.

zkRISCV64

I won’t go too much details about zkRISCV64, because the difference between zkMIPS is trivial. It use RISCV64 ISA and also support OP’s fault proof system.

But there are some drawbacks to implement zkRISCV64, I hope discussing with OP gov and make the decision together.

  • For zkRISCV64, we need re-implement Cannon with RISCV64, this will increase the development time.
  • For zkRISCV64, there are much more instructions and registers to implement, the larger feature intructions set makes audit heavy. This will also increase the development time.

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

Here is our step-by-step plan.

  1. Write a specification for the VM, including each component’s corresponding ZKP circuit. It should be clear and easy to implement.
  2. Implement the zkVM following the specification, we plan to write ZKP circuit based on halo2 proof system with KZG commitment scheme.
  3. Unit testing for each VM instruction, then integration testing of several go language programs, just like cannon did.
  4. Enable provers to utilize GPU to accelerate generating proofs.

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

  1. We will give a clear specification for the zkVM before Aug 4th AOE.
  2. We will implemented the memory and stack proof before Aug 25th AOE.
  3. We will implemented the instructions set before Sep 15th AOE.
  4. We will done integration testing for the zkVM before Sep 29th AOE.

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

  • Ideally, we can start the building without supporting, but an well-performing server after building (i.e., at test stage) would help.

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:

  • Ideally, we can start the building without but the small financial grant would help.

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

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

Exciting to see this proposal! I believe this is an application to this Foundation Mission (RFP). You don’t need to post your application to Foundation Mission (RFPs) to the forum, you just need to reply with this information directly on the github issue (bobby has already linked this proposal there but making sure the process is clear for others reading this.)

1 Like