Document for progress reports on Mopro (Mobile Prover). Aiming to do check-ins ~every 2-4 weeks. (There's also a grant document to cross-check with but link is private). Feb 1 - Apr 15 Done (abbreviated) Improve DevEx significantly with mopro-cli as main interfaceDemo https://www.loom.com/share/6ff382b0497c47aea9d0ef8b6e790dd8 Finish up MoPerf: https://hackmd.io/5ItB2D50QcavF18cWIrmfQ

Introduction to Folding PSE Summer Program (Sep, 2023) Introduction Folding schemes like Nova are a new powerful primitive for recursive SNARKs For big circuits, we can fold similar computation into one big thing Useful in e.g. ZK-VM (Virtual Machines) and ZK-ML (Machine learning) Usable today with tools like Circom and Nova Scotia Note:

Some questions you should be able to answer after the Introduction to Folding talk by Oskar given at PSE Summer Program 2023. Basic questions to check your understand. Questions What problem does folding solve? What is a folding scheme? Why is folding useful for ZK-VM and ZK-ML? Which part of the steps in IVC does the verifier have to look at in Nova? Why do we need relaxed R1CS? Why do we need a final SNARK at the end? What is recursion overhead and why care?

Agenda CCS Multifolding PoC E2E Integration & Upstream effort Next steps Customizable Constraint System (CCS) R1CS generalization; translate R1CS statement into CCS statement (NP-complete equivalance)only matrix-vector products and Hadamard (entry-wise) vector products Capture R1CS, Plonkish and AIR w/o overhead

Not updated to latest version yet 2023-06-19 Main text last updated 2023-06-11 NOTE: This is a draft. The text is a copy of the original text for easier feedback. /Oskar Main diff from May 27: New introduction and clarified/simplified things in main text Introduction Zero Knowledge Proofs are magic. They allow us to do things we couldn't dream of before.

++Table of contents++ About Paper: https://eprint.iacr.org/2023/573.pdf Code PoC issue: https://github.com/privacy-scaling-explorations/Nova/issues/13 Long-lived branch: https://github.com/privacy-scaling-explorations/Nova/tree/hypernova Components

Taken from https://hackmd.io/WIobK-QvS3enrzc33PD_2Q?both=, this was written by arnaucube. R1CS to CCS overview R1CS instance: $S_{R1CS} = (m, n, N, l, A, B, C)$ CCS instance: $S_{CCS} = (m, n, N, l, t, q, d, M, S, c)$ R1CS-to-CCS parameters: $n=n,~ m=m,~ N=N,~ l=l,~ t=3,~ q=2,~ d=2$ $M={A,B,C}$, $S={{0,~1},~ {2}}$, $c={1,-1}$ Then, we can see that the CCS relation:

Context: https://hackmd.io/80cPXRc0Sa2MPuYX4Wft8w Overarching question: What does ZK in 2024 look like? What can we do in a few months to (a) Qualify potential and reduce uncertainty/make progress on important aspects (b) Create positive feedback loops to get more people working on this stuff People ? Areas of interests

Things we want to improve in Nova and Nova-based ecosystem. Context: These are issues that came out of work at ZK Vietnam Residency, specifically towards a ZK VM design https://hackmd.io/0bcDwP5QQp-eiAMVEulH7Q and seeing feasibility of a different architecture vs e.g. current Halo2-based ZKEVM CE. Audience: (i) ourselves when we keep working on it (ii) upstream people to understand pain points (iii) Zuzalu hackathon in mid-April (iv) Wider community. Nova (code) Upstream repo: https://github.com/microsoft/nova PSE fork: https://github.com/privacy-scaling-explorations/nova

Context: See https://hackmd.io/0gVClQ9IQiSXHYAK0Up9hg?view= for previous Nova benchmarks, with more of a focus on recursion. Hardware: Macbook Pro M1 Max (2021), 64GB memory. Native Nova SHA256 benchmark with varying preimage. Code: https://github.com/srinathsetty/Nova/blob/main/benches/sha256.rs Size Constraints

A really quick summary of our journey <img src=https://i.imgur.com/1XYtlno.png width = 400px></img> Note: "Unlimited" parallelization (Not true, but sounds cool) No FFTs! There's already an implementation that we could bench https://github.com/microsoft/Nova

Distributed Nova Prover sketch This section sketches how a distributed Nova prover might look like and what kind of performance we can expect. The following can be simulated in a server with N threads. Alternatively, it can be done in a distributed fashion, either in a controlled data center environment, or in a permissionless environment. As we move from a single server to a data center to a permissionless network we can expect more participants/total parallelization capacity, at the cost of higher latency and complexity. High level overview We have a coordinator and N workers Coordinator is responsible for distributing workload across workers Workers are responsible for computing base and internal case Workers process the base level folds in parallel in chunks of two

NOTE: Draft of post for zkresear.ch as one of the deliverables for the residency. Want to post this on Thursday ~2m. /Oskar Prelude This work was done at ZK Spring Residency in Vietnam. It is a joint work by Carlos (PSE), Chiro (Orochi Network), Nalin (0xPARC), Oskar (independent), and Violet (Delv). Special thanks to to Nalin for shaping the design and explaining Nova to us, Srinath Setty (Microsoft) for the Nova paper/code, and 0xPARC/PSE for hosting the Spring Residency. This post introduces our ideas for a Nova-based VM, some initial benchmarks and future steps. Nova-based ZKVM spec This is the latest version as of 2023-04-06 1pm Vietnam time.

Here's a list of some of the benchmarks we've been taking to better understand how Nova performs vs other proof systems. NOTE: Disclaimer - these benchmarks are preliminary and should be taken with a grain of salt. Some shortcuts were taken as these were done and we want to check the correctness of these calculations before being 100% confident in them. Recursive hashing Recursively hashing of SHA256 $k$ times. That is, computations of the form $h(h(h(h(h(x)))))$. This also show how doing many recursives hashes in a single fold in Nova improves performance. That is, turning expression above into: $$h(h(h(x))) \text{(d times)}\rightarrow h(h(h(x))) \text{(d times)} \rightarrow \dots$$

Extracting Execution Trace from WebAssembly Runtime NOTE: From Chrio (Orochi Network), appendix to ZK VM spec. To prove arbitrary computation we need to extract the execution trace and prove that every step of the computation is correct. In our case, we want to prove the execution trace of WebAssembly run-time. We pick the wasmi - WebAssembly (Wasm) Interpreter a light weight and deterministic Wasm run-time to start with. Method We created two new structures namely, Predator, Trace. Predator will record every single Trace to a vector of Trace. Inject the Predator instance to Executor of wasmi and start extracting before the opcode is executed (wasmi have some engineering turning so we might need to transform to the necessary format of the Trace). Passing a single reference of Predator from the construction of Engine to the EngineExecutor.

Goal: Understand feasibility of a (Super)-Nova based ZK VM such as ZK-WASM or ZK-LLVM. Specifically, understanding if a significant speed up(x10-x100+) is possible vs existing ZK-EVM architecture, and if there's a competitive advantage vs e.g. FRI-based approaches. Example use cases include arbitrary computation in a browser setting and restricted memory environments, and to do so in a short time frame. Current direction We are looking for a way on which Nova and/or SuperNova schemes can allow us to have: Lower memmory (RAM) consumption for the prover (see costs of Scroll or Polygon ZKEVM prover implementations). No lookups nor any permutation argument nor anything that gets limited due to the ammount of roots of unity of the curve you're using. We want the scheme to be significantly different than the Scroll/PSE one. So instead of splitting into general and big-purpose circuits, we would like to be able to have microopcode-style approaches or similar.

Initial questions What are our common goals?Do goals diverge in some sense? What work needs to be done? How should it be divided? What are some priorities? Do we have different priorities in some sense?

Intro @oskarth / oskarth.com vac.dev - Privacy & Communication Note: 不好意思我現在不會講中文，沒有時間準備 Director of Research at Vac Vac builds public good protocols for the decentralized web, with a focus on communication and privacy