zkwasm sync - HackMD

# ZK WASM Sync notes Index document: https://hackmd.io/IqQMg6I6Qz-AEc8MSEU4eg --- ## July 29, 2024 * News and updates * Andrei leaving NEAR in August * Will cancel the sync, Jordi to chat with Bowen * Running examples from https://github.com/0xPolygonHermez/hellozisk_rust/ * Missing the toolchain `zisk` so far * hellozisk is deprecated * Need access to another Rust repo `zisk` * Prover will also be in Rust * Currently creating state machines for ops * In the future add precompiles for hash functions, etc. * Simulator also generating a witness * Still need to decide on the chunk size for continuation * Probably start Reth, Type 1 * Likely good precompiles will be necessary * Critical to decrease a memory * Getting rid of counters * 10k SHA without precompiles, 42M steps of Zisk ## July 1, 2024 * Latest news and updates * A lot of progress on new architecture * A new processor that is more general, ZK in mind * On top of it, should be easy to implement any other VM/Intermediate code * Tried converting RiscV instructions, 1-1 mapping * Should be possible to convert WASM/Cranelift to this processor * Use memory instead of registers * Registers are expensive (take 1 or 2 polynomials) * Instead let's use memory machine * 2 main registers: PC, SP * Operation can take as an input values from memory and store them in memory * 35 polynomials for the processor * Have a simulator * Passes all RiscV spec tests * Written in JS * Documentation for the new assembly? * Still closed access * Don't have assembly yet, JS class to create the instructions * Next steps: * Andrei to take a look at repository * Outline a plan to support Cranelift/WASM ## June 17, 2024 * Skipped ## June 3, 2024 * Latest news and updates * NEAR working on the continuous benchmarks * Polygon project for writing a custom Virtual Machine * More people will work on this * Likely based on Cranelift * Backend for Cranelift - zkAsm processor * https://github.com/near/wasmtime/tree/main/docs/zkasm * Andrei: [Risc0 performance numbers](https://www.risczero.com/blog/zeth-brings-validity-proofs-to-optimisms-op-stack) * Jordi: Questions about Cranelift * https://github.com/rust-lang/rustc_codegen_cranelift is slower than rustc LLVM backend * How does this compare with ZKEVM? * How to get from Rust to zkAsm: https://github.com/near/wasmtime/pull/231 * Yes we use ISLE * Example code: https://github.com/near/wasmtime/blob/cfd17ba7d2662f48542a9da785094fd6abc25770/cranelift/codegen/src/isa/zkasm/lower.isle * Formal verification: https://www.cs.cornell.edu/~avh/veri-isle-preprint.pdf * Write a new processor designed to be compiled from Cranelift * Single line for each native instruction * Smaller PIL, 30-40 polynomials, smaller words * Use advantages of PIL2 * Translation should be simple * List of Cranelift opcodes * https://github.com/near/wasmtime/blob/cfd17ba7d2662f48542a9da785094fd6abc25770/cranelift/codegen/src/isa/zkasm/inst.isle * https://pengowray.github.io/wasm-ops/ * Gotcha: * wasm32 vs wasm64 rustc backend * wasm32 uses 32-bit pointers * Traps: * E.g. divide by zero * In WASM, user code can't observe traps * Only can be seen in runtime * Next steps: * Reproduce the environment to generate the zkasm code * Start here: https://github.com/near/wasmtime/blob/main/docs/zkasm/usage.md * Define the interface for inputs and outputs * Can use the approach from Risc0/SP1 * Example: https://succinctlabs.github.io/sp1/writing-programs/inputs-and-outputs.html ## April 15, 2024 * Latest news and updates * New ZKASM features: https://hackmd.io/AXl9fshpRFKLNb_MFxrykw?view * Questions: * What the basic machine is programmed in? * What is audited? * EIP 4844 * A new precompile * Need to post the full blob, always 130k bytes * Another layer - blob, another ROM that parses the data and makes sure it matches the posted hash ## March 18, 2024 * Bowen/Andrei: We'll have lower bandwidth for ZKWASM in the next few weeks * Need to focus on NEAR mainnet performance * Can still keep this meeting going, but will have to delay active work on our PIL2 migration * How to reach 100x improvements for Merkle proof compression * https://zkbench.dev/ as basis * Better hardware (ASICs) * Fabric - first boards by the end of the year * Better compilers * Better proving systems * Different economics * Ethereum folks are thinking to use Verkle trees for this * https://vitalik.eth.limo/general/2021/06/18/verkle.html * Smaller in size * Cheaper to generate than ZK proofs? * Bulletproof for commitment for now * Double-overhead of running WASM interpreter on ZKVM * Biggest unknown: hardware timelines and performance * When generic, might not be efficient enough without the hardware * Can we get an estimate by running through Risc0/SP1 * Discuss next steps for ZKWASM Processor * PIL2 is good for writing processors * RiscV should not be hard * Options * Reuse EVM processor * Reuse existing design like RiscV/Valida (https://delendum.xyz/writings/2023-05-10-zkvm-design.html) * Write a new processor specifically for WASM * DONE: Change the frequency to 1 per month for now ## March 4, 2024 * Andrei: Understand PIL2 [benchmark results](https://docs.google.com/spreadsheets/d/160u5pWBp7E5RdUilJ15HATk4rlDn35Mi32CCCKppnRw/edit#gid=1066493496) * What is the metric that we should be looking at? * zkGas * PIL2/Vadcop performance is tricky to estimate * Next fork in PIL2, still using Plonky2 * PIL2 questions * Is AirOut the same as PilOut? * https://github.com/0xPolygonHermez/pil2-proofman-js/ uses AirOut * Can we make Rust version available to NEAR folks? * https://github.com/0xPolygonHermez/pil2-proofman * akashin, mooori, MCJOHN974 * Do we need ETH transactions to generation PilOut? * Assuming the answer is "No". Because witness is generated by the proofman later. * Only definition of the constraints * Moving pilcom PIL2 branch into Pilcom2 repository * Change compiler to Rust * Speed up const generation * zkAsm to describe processor * Have storage and main processor ## February 26, 2024 * [10m] Polygon: Examples of ROM improvements available in PIL2 * https://hackmd.io/oA8UqucNTlGTXkYvhuVamQ?view * PIL2 Components * Can instantiate the same circuit template with different parameters * Can we build a diagram of how pieces combine together to generate the proof? * PILs * zkAsm code * Componets * Mains * https://github.com/0xPolygonHermez/pilcom/tree/feature/pil2-expression-refactoring * Next time: Andrei: Any experts in [SP1](https://blog.succinct.xyz/introducing-sp1/)? * Where is the proof efficiency compared to Risc0 coming from? * Is there anything we can learn from when building a processor for WASM? * Generating a proof locally for Rust programs looks very simple, can we have the same usability in new PIL2 prover? ## February 20, 2024 ### PIL Workshop ## February 19, 2024 * [10m] Andrei: Updates on ZKWASM progress * Have an MVP for new test infra that allows to leverage all Cranelift tests * Have an MVP for profiling tool that shows a trace of execution * Confirmed that WASMI interpreter works, fixing zkAsm for it * Started looking at compiling [NEAR Light client](https://github.com/risc0/demos/tree/main/near-zk-light-client) * Takes 40M cycles on Risc0, proving time around 15m on M1 Macbook * 1000x slowdown compared to block production * I think 8M cycles on zkAsm * [15m] Using zkAsm/PIL in Rust ecosystem * NEAR is implemented in Rust and we would like to generate proofs as a part of block production * Example that we need now: [Executing zkAsm code from Rust](https://github.com/orgs/0xPolygonHermez/discussions/66) * What should be our long-term plan? * Prover should be able to integrate with different executors * Some executors will be translated in Rust * Main is the most complex so far * Private repository at the moment - TODO: Can we make it open for us? * Production prover will be in Rust * Each specific project will pick some generic libraries with components to use * Current proverjs needs changes to use the new component * Components currently are written in JS, but in the future will be also in Rust * Internally use Node, but maybe other options might also work * TODO(akashin): Write pros/cons of using Deno * [<5m] JS CLIs * Most JS package related to zkevm and PIL seem to use `yargs` to build CLIs. Will `yargs` be used for PIL2 related packages as well or is there a switch to another library? * https://yargs.js.org/ * Workshop * Introduce PIL2 * Show how to add features to zkAsm and PIL1 and proverjs * New split into PIL2 components * Features backported from PIL2 to PIL1 * E.g. SAVE/RESTORE commands to save registers * Selectors/immediates * Binary ops on arbitrary register with immediates ## February 5, 2024 * [10m] Andrei: Updates on ZKWASM progress * Started implementing new testing infra * Started implementing new benchrmaking infra * Keccak256 passes tests (https://github.com/near/wasmtime/pull/206) * cntBinary: 5759n * cntSteps: 33994 * Only 1000 lines of WASM and 3000 lines of zkAsm * Cycle of Keccak is 134k, 44 keccaks, 134 / 44 = 3k * WASM interpreter (https://github.com/near/wasmtime/pull/202) * 443k lines of ZKASM * How should we audit it? * Needs [5 new WASM instructions](https://github.com/near/wasmtime/issues/160#issuecomment-1921029648) to run, plan to handle them this week * Possibly useful to implement instructions * https://github.com/0xPolygonHermez/zkevm-proverjs/tree/feature/save-restore * Polygon folks working on PIL2 * Change in the tooling structure to support components * ZKWASM might start leverging some of these to build new instructions * Allows to configure bitness of different operations * Inline the constants in some operations (e.g. one of the opperands = 0) * Will introduce some new instructions in zkAsm * Next step: Andrei will schedule a meeting to learn about PIL2 from Hector and Felicia * Next Monday, invite folks from Polygon ## January 29, 2024 * [5m] Andrei: Learning more about PIL and PIL2 * Can someone from Polygon organize a presentation for us? * Any materials that we can read? * Let's find some modification to processor that we want * Schedule a 2h session beginning of next week * [10m] Andrei: Passing inputs to ZK circuit * Use-case: Parameterize [benchmarks](https://github.com/near/wasmtime/tree/main/cranelift/zkasm_data/benchmarks/fibonacci) * What are out options? * Helpers - only for performance testing * `read_byte`, `write_byte` * https://github.com/0xPolygonHermez/zkevm-rom/blob/877328eff50070426f040a8843b7d6eb3140ef22/main/load-tx-rlp-utils.zkasm#L16 * SLOAD/SSTORE * Registers to put the hash of input * [15m] Andrei: Scaling program size * Use-cases: * Handling programs that take > 2^23 steps to run * Handling programs with > 1MB of input (e.g. WASM program that takes 4MB) * Anything like [Risc0 Continuations](https://www.risczero.com/news/continuations)? * In PIL2 * At the end of trace execution do a permutation check for the next state * Needs to be defined with a processor in PIL2 * Would it be possible to cache the proofs about WASM code? * Not really, because reads need to match * Would need to use the cheap hash * PIL2 - public tables can be useful ## January 22, 2024 * [Benchmarking in Stage 2](https://github.com/near/wasmtime/issues/173) * What are we trying to optimize? * Dollar per gas for proof <- main right now * Latency, generate as fast as we can * Which hardware to use? * Need to decide before measuring * GPUs are faster latency-wise but more expensive * Spot instances are a good deal * Intel CPUs right now, AVX512 enabled * Which benchmarks already exist for ZKEVM? * For specific circuit/function - look at the number of cells = rows * columns * Maximum degree of constraints matters - only if changing PIL, irrelevant for ZKASM * 400 intermediate polynomials to decrease the degree * How can we compare with other ZKVM benchmarks? * https://risc0.github.io/ghpages/dev/benchmarks/index.html * https://github.com/0xPolygonMiden/miden-vm#performance * Important to understand what exactly is measured in the proving time - is it end-to-end, does it include proof compression, what are the constant overheads? * Risc0 uses 32-bit prime * Single-core vs multi-core performance * Proving time vs execution time * Hashing and MPTs are 30% of the proof * Number of columns is defined by PIL, doesn't change with ZKASM * Can get a split of timing within the proofs * Conversion from cycles to proving time * Adjustments for 64 or 32 bit processor * There is tooling `pilPolTable` to analyze the number of columns * Useful to check when optimizing the PIL * Understanding which way of expressing computation is the best * Other things - lookups, permutations * Design: * Arithmetisation * ROM * Histogram of most used instruction ## January 15, 2024 * [ZKASM processor requirements in Stage 2](https://github.com/near/wasmtime/issues/158#issue-2035651992) * Switching to 32 bit will save cycles * arithmetic are 4 clocks * binary are 2 clocks, uses permutation check * Does it make sense to embed this into main state machine? * Probably not, state machines will be cheaper * Likely 3x speedup * Don't need arithmetic addition, only for overflows * MEMALIGN state machine for unaligned writes, byte aligned * When will we implement this? * Converting ZKEVM to PIL2, if it works likely PIL2 works * In parallel building the prover, have JS version working already. Working on Rust/C version of prover * (tentative) Targeting by the end of Q1 * Good moment to build ZKWASM processor would be after ZKEVM is converted, at least a month * For NEAR, next 6 weeks building infra * Let's try to start end of February * [SHA256](https://github.com/near/wasmtime/pull/185) works now! * The resulting ZKASM program takes 27k cycles on 32 bytes of input and 210k cycles on 448 bytes of input (there is some constant startup overhead) * 31k per 448 bytes = 32 bytes * 14; 7 * 512 bits = 448 bytes * Within 7x of state machine implementation? ## January 8, 2024 * ZKWASM Stage 1 completion * Decided to move to Stage 2 before completing [SHA256 benchmark](https://github.com/near/wasmtime/issues/143) as the work there is hard to parallelize * Currently debugging correctness, consumes around 50M rows for "Hello, world" bytestring without Cranelift optimizations * Cycles for impl with state machine - 1864 cycles for input of size 64 bytes per hash * `CONST %MAX_CNT_SHA256_F_LIMIT = ((%TOTAL_STEPS_LIMIT - 1) / 31488) * 7` * With specific state machine for SHA256 in PIL * TODO: Get a link to implementation when it is public * ZKWASM [Stage 2 planning](https://github.com/near/near-one-project-tracking/issues/6) * Top-level projects * [Benchmarking infrastructure](https://github.com/near/wasmtime/issues/173) * TODO(Moritz): Share the doc with Carlos * [Test infrastructure](https://github.com/near/wasmtime/issues/172) * [WASM Interpreter in ZKASM](https://github.com/near/wasmtime/issues/174) * Biggest size of smart contract? 24 KB on Ethereum * [Software/hardware optimizations for WASM](https://github.com/near/wasmtime/issues/175) * Collaborations: * https://github.com/near/wasmtime/issues/158 - ZKASM processor requirements to review * Try to optimize benchmarks with someone from Polygon * [Support WASM opcodes for Stage 2](https://github.com/near/wasmtime/issues/180) * `memory.fill`, `memory.grow` * Possible optimization if * Starting next week, aiming to complete by April 2024 * Q: How flexible is the Memory limit of ZKASM processor? * Possible to get more memory with changes to the processor and change the behaviour of CTX variable ## December 18, 2023 * Holiday schedule * Pagoda is OOO next week - skip the next meeting (DONE(akashin)) * Next meeting after that falls on 1st of Jan, likely not many updates :) * Let's skip and do the next one on 8th Jan * GitHub Discussions * We have [first question and answer](https://github.com/orgs/0xPolygonHermez/discussions/62) :tada: * [Documentaion](https://docs.github.com/en/discussions/managing-discussions-for-your-community/managing-discussions#about-management-of-discussions) about managing discussions * It is possible to transfer discussions between repos and organizations * Bulk-movement can be done [programmatically](https://jloh.co/posts/bulk-migrate-issues-github-cli/) * Indexed by [DuckDuckGo](https://duckduckgo.com/?t=h_&q=How+to+use+config+option+fullTracer.printOpcodes&ia=web) and [Bing](https://www.bing.com/search?form=&q=How+to+use+config+option+fullTracer.printOpcodes&form=QBLH&sp=-1&lq=0&pq=&sc=0-0&qs=n&sk=&cvid=BAA318AB349E4563AA3C396B865FCE79&ghsh=0&ghacc=0&ghpl=) * For Google indexing, might need to [add the link to discussions page to the README](https://github.com/orgs/community/discussions/3318#discussioncomment-585870) * [Stage 1 progress report](https://github.com/near/near-one-project-tracking/issues/2) * We can use arrays for global data regions https://github.com/0xPolygonHermez/zkasmcom/blob/feature/fork-etrog/test/arrays.zkasm ``` VAR GLOBAL a[300] start: 1 :MSTORE(a) 3 => E 2 :MSTORE(a + E) 7 :MSTORE(a + 4) ``` * Rebasing `feature/64bits` zkevm-proverjs on the main branch * Likely will start from scratch from PIL2 * Let's see if we run into lacking features and only rebase if needed * 32 Bit operations support timeline * Build PIL2 * Migrate ZKEVM processor to PIL2 * Stabilize PIL2 * Implement ZKWASM processor in PIL2 (ideally in a modular way) * At this point we will have 32-bit operations * We will migrate away from current feature/64bits branch * [Stage 2 planning](https://github.com/near/near-one-project-tracking/issues/6) <-- Next time * [Performance Tracking](https://github.com/near/wasmtime/issues/137) * Our current estimates are that proving on a single machine is ~50000x slower than WASM execution for Fibonacci benchmark, does this sound legit? * What do we need to focus on to speed this up? * [ZKASM processor updates](https://github.com/near/wasmtime/issues/158) ## December 11, 2023 * Team is growing, welcome Moritz! * We need a better way to ask and track technical questions * Currently using GVC + Telegram * Not inclusive, does not work for external contributors * Suboptimal search experience - same questions will get asked again and again * Not effective use of everyone's time - meeting and chat is pretty big and questions often can be answered by a single person * Threading support is not great * There are external parties interested to contribute * Currently focusing on PIL * Some interest in ZK WASM as well * Let's try something different! Options: * [GitHub discussions](https://github.com/features/discussions) * DONE(akashin): check that these are indexed * DONE(akashin): Learn how to move the issues * Let's put it under PolygonHermez for now * Zulip * Google groups * Witness generation * Shouldn't need to update the prover? * In JS, proof generation will take 1-2 hours * For PIL2 * Witness generation will go together with PIL * Single prover for everything * Targeting by Q1 * Part of tooling will be in Rust * ZK EVM port expected to take a couple of days ## December 4, 2023 * Implementing Sign extensions (https://github.com/near/wasmtime/issues/110) * E.g. for i32.sload * Swapping two variables in registers (e.g. A and B) * https://github.com/near/wasmtime/pull/135 ## November 27, 2023 * Generation of witness * How long does it take? * Is it included in 2 minutes for batch? * Currently in prod witness is also generated by C++ * But it can be generated by JS * Would be less work on C++ end * Can even do this in Rust * TODO: Check with Jordi if this is a correct path for now * TODO(akashin): Write a design doc with requirements here * From previous time * How can we avoid code duplication between processors and prover codebase in the future? * TODO: Discuss again * Stage 1 milestone finish line * Supporting two benchmarks compiled from Rust: * Fibonacci (https://github.com/near/wasmtime/issues/90#issuecomment-1824795152) * 60 WASM instructions * Simple i32/i64 arithmetics * SHA256 (https://github.com/near/wasmtime/issues/90#issuecomment-1825561270) * 3000 WASM instructions * A lot of bitwise ops * Memory loads and stores * Pass spec tests for affected i32 and i64 instructions * https://github.com/WebAssembly/spec/blob/master/test/core/i64.wast, https://github.com/WebAssembly/spec/blob/master/test/core/i32.wast * https://github.com/near/wasmtime/blob/3b4e50c3c6cce63b9cb5e08cd1d76c7a7ece29fe/docs/zkasm/test_summary.csv * Add benchmark with comparison between handwritten version * Aiming to finish by the next sync on 4th of December * Fibonacci is ready, finishing required opcodes for SHA256 * Simonas: Memory operations https://github.com/near/wasmtime/issues/110 * How hard is it to add MLOAD8? * How hard is it to add MSTORE{16/32}? * Right now: can use MEM_ALIGN_RD8/MEM_ALIGN_WR8 * Can be further optimized if use many consecutive at a time * In PIL2 possibly can specify how many bytes to read/write ## November 20, 2023 * Bowen: We want to set up progress updates * Every few weeks * Public for everyone to see * https://hackmd.io/IqQMg6I6Qz-AEc8MSEU4eg?view * Want something more high-level, for people who are not working on the project * DONE(akashin): Create a status document in wasmtime repo. Make it discoverable. Have different sections for Cranelift/ZK related pieces * How can we avoid code duplication between processors and prover codebase in the future? * Context: https://github.com/near/wasmtime/pull/89 * Components/libraries with parameterization in the future * E.g. Keccac, Main, Storage * Good opportunity to check if the new design is flexible * E.g. in PIL2 can specify in permutation checks items from different files * Challenge with 64 - all components must work in 64 (because registers are now 64) * DONE(akashin): Ask Jordi on Telegram/bump this question to next time * Working in pilcom project on PIL2 compiler, in progress now (https://github.com/0xPolygonHermez/pilcom/tree/feature/pil2) * Benchmarks https://github.com/near/wasmtime/issues/90 * Hashing * https://github.com/akashin/bench/blob/sha256/src/main.rs * https://gist.github.com/akashin/b038a9e9fcc9bb4ccf0dc5b990f5d9df * [Iterated Hashing (iter-sha2, iter-keccak)](https://github.com/risc0/risc0/blob/main/benchmarks/methods/guest/src/bin/iter_keccak.rs) * Needs SHA256 support - will it be available in PIL1 or only in PIL2? * In progress, passing ETH tests * Another zkasm instruction HASHS * Closing in around 2 weeks * Currently in internal branches * [Fibonacci](https://github.com/risc0/risc0/blob/main/benchmarks/methods/guest/src/bin/fibonacci.rs) * [Signature verification (ed25519)](https://github.com/risc0/risc0/blob/main/benchmarks/methods/guest/src/bin/ed25519_verify.rs) * Not available, let's switch to https://github.com/risc0/risc0/blob/main/benchmarks/methods/guest/src/bin/ecdsa_verify.rs * Idea: Counters * Limited HASHK number * Checking how much resources we use * Measuring end-to-end proving time * We would like to generate a few end-to-end proofs for a set of benchmarks * What are the changes in zkevm-prover (C++) for 64 bit processor? * Need to check with Jordi * Bottlenecked on devs here * Hard because there are a lot of optimizations there * First step: Change JS to generate the proof, then this change is ported to C++ * Options: * Measure the area of trace and use it as proxy for performance * Disable some state machines to get similar area in 256 bit machine * Third dimension - degree of the constraints * Support proofs in JS and port changes to C++ * DONE(Hector/Felicia): Post current times (batch proof) * https://twitter.com/eduadiez/status/1667221787178876963?s=46&t=2FzkB9sZOyy4irzxy70HVg * 10M Gas * 500 eth TXs * Need to follow up here * Behavior of JMPNZ ``` 4294967296n => A A :JMPNZ(Label) ``` * Expect it to jump, but it does not - contradicts documentation * !!! Only checks the first chunk * DONE: Make sure this is documented * Behavior of SUB https://github.com/near/wasmtime/issues/81 * How do we expect to detect sha256 algorithm as it was compiled to wasm and then emit these HASHS instructions @akashin? Unless we use an intrinsic or something like that sha256 will have to be opencoded. * We will follow the path of RiscZero - add our wrapper to SHA256 that will generate external function call ## November 14, 2023 * Progress on Stage 1 (https://github.com/near/wasmtime/milestone/1) * What's the current thinking on Spec tests / filetests? (https://github.com/near/wasmtime/issues/17) * Expect to have a runtime * DONE: Let's write down exactly what we mean here with examples * Which WASM opcodes do we already support and plan to work on next? (https://github.com/near/wasmtime/issues/22) * Is 64 bit processor working now? (https://github.com/near/wasmtime/issues/33) * We migrated, Yay! * In our hands to make changes. * We should clarify maintenance question with Polygon going forward - can we reuse processor pieces between EVM and WASM? * Benchmarks https://github.com/MCJOHN974/bench * WASM intermediate was much faster * How difficult is it to make a WASM runtime? WASM needs an external runtime * Any blockers that Andrei can help with? * What are the largest design questions that we need to resolve? * Handling integer overflows: https://github.com/near/wasmtime/issues/62 - we already have a way forward * Test infrastructure, what do we do about WASM runtime, etc. * What slows us down the most in the codebase? The most pressing tech-debt to resolve? * Making steady progress * Do we feel like we have enough understanding of ZK ASM to make progress or do we need to invest more here? * "ARITH usage and external computation" below - is this resolved? * Need to validate any external calls/free inputs * "which repo is suitable to left a tracking issue?" - is this resolved? * Using our wasmtime now * Next step: measure how many of tests from https://github.com/WebAssembly/spec/blob/master/test/core/i64.wast we pass * Find if wasmtime already has this test * We need some project management * Let's do another slot - I'll on Friday, zk wasm specific * Can use https://github.com/near/wasmtime/milestone/1 as a source of truth of what to work on next ## November 6, 2023 * Viktar: does we already have ways to run 64-bit zkasm? I found ``node test/zkasmtest.js --rows 2**18 --ns all test/zkasm/64bits.zkasm`` in ``zkevm-proverjs/feature/64bit``. In our test it fails only on ``SLT`` as not yet implemented. So, we can use it for testing operations which generate 32-bit overflow. * Is it best way to run 64-bit zkasm? * (to Pagoda team) do we want work with overflows using this 64-bit machine, or wait for more completed versions? * Viktar: when we should perform ARITH instruction? I runned code with data computed in external environment (${}, $${}), load it to registers, and everything work without ARITH. Also I have seen ARITH usage after some lines of computations. So, the question is, how far after external computation ARITH should be used? Are there any tools to check usage of ARITH? ## October 30, 2023 * Viktar: How should we do analogue of wasm ``i64.const`` in zkasm? Something like ``43093904439049308585895 => A`` don't work. * How can we load a big hard coded number in zkasm? * 999999999999999999999n => A (bigInt notation in JS) * why not do it all the time? It indicates to the compiler that it is a high value. * Viktar: Less bit operations. Does zkasm have any ways to perform smaller bit operations with proper overflow. For example, ``0xFFFF_FFFF + 1 = 0`` * `$ :ADD, JMPC(,)`. C here can be understood as carry. * an example (256 bits overflow using :ADD) --> https://github.com/0xPolygonHermez/zkevm-rom/blob/main/main/utils.zkasm#L553 * For 32bits, the overflow has to be managed by ZKwasm * is it better to use jmpc, or would masking off the result with `and` and a bitmask preferable performance wise? * jmpc is cheaper as the flag is already set. * nagisa: which repo is suitable to left a tracking issue? * ## October 09, 2023 * Felicia: Discussion about memory access. * nagisa: we haven't done a lot of experiments. Not much to cover yet. * akhi: more discussions about memory access. * Jordi: unaligned memory access can be supported but is expensive. * nagisa: the semantics of mem align instruction. * Felicia: https://github.com/0xPolygonHermez/zkasmcom/blob/feature/64bits/instructions.md * Carlos: https://wiki.polygon.technology/docs/zkevm/zkProver/mem-align-sm/ * nagisa: other questions about instructions. ARITH instruction. * Hector: ARITH: A * B + C = D * 2^256 + E * Felicia: ARITH64 bits: A * B + C = D * 2 ^ 64 + op * Carlos: https://wiki.polygon.technology/docs/zkevm/zkProver/arithmetic-sm/#field-arithmetic --> (Eqn A) ## October 02, 2023 * nagisa: Currently the documentation we're perusing is for the 256-bit word machine, but working with the assumption that words will be 64-bit soon. We know there's a [64-bit proverjs branch](https://github.com/0xPolygonHermez/zkevm-proverjs/commits/feature/64bits). Is there anything else we can look at or should keep in mind? * No documentation upgrade is planned. * Things like arithmethic should work as expected. * Bowen: How is the progress on pil2? * ETA: end of the year. Also for the VADCOPs prover. * nagisa: Had a call with wasmtime/cranelift folks, generally reception is warm, but they raise concerns with supporting certain runtime-facing functionality like `memory.grow` and such, which require an ability to modify the size of the memory available to the code being executed as the code executes. * wasm allows for unaligned access while only aligned access is allow on the machine. * Maybe the transpiler should not use unaligned access. * we are not targetting general wasm programs at this point in time. Just the wasm interpreter which we can control to not generate unaligned memory access. * nagisa: In similar vein, how hard would it be to support possibly-misaligned byte-addressed loads? Especially in the context of memory being addressed in words in zkasm machine? WASM’s addresses are byte-granular, so we’ll need to both support misaligned loads and convert address scales for every memory access… * This is answered above. We are targetting wasm in the interpreter. * Bowen: nagisa and Viktar: how are we doing on the implementation side? Can we implement the MVP op codes in the next 1-2 months * More realistic now than before. Because we are just targetting the interpreter. * Bowen: What are we doing about floating point? * We could handle it in the software. Compilers can take care of already because we care about determinism. * Bowen: working on a joint announcement of the project. ETA: 2 weeks. * Sandeep and Pagoda team wants to see: can we open up the project to contributors outside of Pagoda and Polygon? * Andrei's estimate is that we are not there yet. We need more guidelines to help with this. * On cranelift side, we have some major breaking changes. ## September 18, 2023 * akashin: Viktar and Simonas joined the project, welcome! * akashin: Discuss 6 month roadmap proposal: https://hackmd.io/wxRNuku5S8yRk8QDqA6dcA * Take a look at [C++ prover](Example of file: https://github.com/0xPolygonHermez/zkevm-prover/blob/main/src/main_sm/fork_5/main/main_executor.cpp) * Carlos: Workshop for tooling for ZK ASM * Wednesday/Thursday/Friday * DONE(akashin): Schedule time on Friday * akashin: Will be away on paternity leave in October and November * Simonas and Viktar will be points of contact for ZK WASM * zkASM memory - what is the cost of CTX tracking? * And what would it take to go to 64 MB memory? Should not be a big deal. * Need to probe memory at < 8MB increments because of range checks * Performance after switch to 64 bits * Number of steps is the same * Number of columns will be less * Two-fold gains: * Prover is faster * Number of columns is smaller * Can estimate with JS Setup without needing to build C++ prover * PIL is enough for an estimate * TODO(akashin): Take a look what is needed here * Need to adapt the state machines ## September 4, 2023 * akashin: [Concrete agenda](https://hackmd.io/zVMEcYsOQFueu9EHvoBqIg?view) for meeting in London * Anything to add? * Let's confirm who will lead each session ## August 30, 2023 * Can we reuse ETH-specific registers from ZK EVM that we don't really need? * GAS, HASHPOS, Can reuse * 1 fixed, 3 witness columns (set, get, lookups) * Usage of CALL/RETURN in ZK ASM * Plan to change these * Is this more efficient than JMP? * zkPC register semantics * PC is for EVM (can reuse it for something else) * How strict is the limitation that A and B must be registers for ops? * Might use memory in the future * Old codebase: https://github.com/akashin/zkwasm/ * WASM -> ZK ASM, not optimized at all * Examples: https://github.com/akashin/zkwasm/tree/main/data * New codebase: https://github.com/near/wasmtime/tree/zkasm-hackaton * WASM -> Cranelift IR -> ZK ASM * Examples: https://github.com/near/wasmtime/tree/zkasm-hackaton/cranelift/data * Working notes: https://hackmd.io/8faPpmGQTrmdr1mZau6XYQ?view#Example-module * Is this harder or easier to translate? ## August 29, 2023 * Agenda for the meeting in London * Timeline - 6-8 September * Goal: Knowledge sharing, supporting ZK WASM work * Activities * Presentations (30m + 30m discussion) * NEAR Contract Runtime * PIL2/Future of Proving/Plonky3? * Jordi will share some info * Anything that will change for us as users of PIL/ZK ASM? * Prove aggregation and recursion * How long does it take now? * Can we use tree structure vs linear structure? * Brainstorming (1h - 1.5h) * How we collaborate going forward * Can we make proving fast enough to be usable in NEAR? * What can we do with “Compiler JIT bombs” * How can we optimize for latency? * Will Cranelift IR be a good fit? * https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/docs/ir.md * Pair-programming (2h) * Optimizing ZK ASM * Modifying the PIL and Processor * Adding a new register * Benchmarking and profiling proofs * Run the production prover? * Linear in rows * cols (technically nlogn in some parts) * Try AWS instance (only CPU) * Ideas - https://hackmd.io/nRbL3yfuSDSEq3GKCQJE1Q#Meetup-topics * akashin: Progress on ZKASM compiler * Prototype 1: [WASM -> ZK ASM](github.com/akashin/zkwasm/) * Easier codebase to get started * WASM does not map nicely to ZK ASM * Need to implement optimizations from scratch * Prototype 2: [Cranelift IR -> ZK ASM](github.com/near/wasmtime) * Cranelift IR maps much better to ZK ASM * Gives us many optimizations like register allocation, constant folding, etc. * [Large codebase](https://github.com/near/wasmtime/tree/zkasm-hackaton/cranelift/codegen/src/isa/zkasm), harder to onboard * [Examples of compilation](https://hackmd.io/8faPpmGQTrmdr1mZau6XYQ?view#Example-module) ## August 14, 2023 * Bowen: logistics for the meeting in London * akashin: Discuss the [ZK WASM roadmap](https://hackmd.io/w4BM5m50TLONOzeNRSpeOw?view) * Does the plan make sense? * Has anyone looked into IR (e.g. LLVM, Cranelift, RiscV) -> ZK ASM compiler for EVM implementation? * Protocol written in Rust * WASM interpreter written in Rust as well * Developers program in Rust/JS an compile it to WASM and submit it to the chain * Inject gas metering in the submitted WASM code * On validators, we compile WASM to x86 and run it * For ZK: Compile Rust protocol code and WASM interpreter into ZK ASM (instead of writing it by hand) * Do we have any tools for benchmarking the resulting circuits? * you can run the following script, that runs zkasm files using the `zkproverjs`: https://github.com/0xPolygonHermez/zkevm-rom/blob/develop/tools/run-tests-zkasm.js * add `--verbose` flag to check zk-counters consumption ## August 9, 2023 * Fibonacci * Fibonacci 20 (6765) is 2.5 TGas, 3ms * Fibonacci 25 (75025) is 6.2 TGas, 5ms * Fibonacci 30 (832040) is 47 TGas, 30ms * In ZKWASM manuscript, they have 19 Fibo (~4500) computed in 800s. * SHA256 * https://github.com/Sladuca/sha256-prover-comparison * 43TGas for 1MiB of SHA256, 20ms to compute * 32768 SHA256 invocations * Plonky2 can do 2000 SHA256 invocations per second * https://github.com/near/nearcore/blob/master/runtime/near-vm/compiler-singlepass/src/codegen_x64.rs ## August 8, 2023 - ZK WASM Workshop * https://hackmd.io/LqdM1rDNR6qJpYOa21HTfg * ZK ASM language to write program * PIL to specify constraints * Executor to run the assembly * Prover * ZKevm-proverjs * PIL - main.pil * Namespace - state machine ## August 7, 2023 * What is our long-term goal? * For NEAR: Ability for large group of validators with basic hardware to verify and sign on the results of executing all transactions in the chain for improved security. * ZK-Proofs could be an ideal solution, as they can be easily validated without needing a special hardware and also could be easily distributed to many participants and committed on-chain. * Also applicable on light-clients * For ZK WASM in general: Provide open-source tool to prove the execution of Web Assembly programs * Can help to integrate across blockchains * Polygon ZK Aggregator, for all L2s and other chains * What can we set as a short-term goal? * Should be able to build prototype for WASM specifically by the end of 2024 * That includes NEAR Host Functions (see [here](https://hackmd.io/nRbL3yfuSDSEq3GKCQJE1Q?view#%E2%9D%93-How-will-WASM-foreign-host-function-calls-work)) * ["Type 2"](https://vitalik.ca/general/2022/08/04/zkevm.html) system, defined for EVM * Features that might be tricky initially * Particia Merkle Trie * Would also be good to prove state machines for other parts of transaction validation * How long would it take to implement WASM VM in ZK Assembly + PIL? * Stages * Pure WASM * Math precompiles (e.g. hashing) * Blockchain-specific parts (blockchain state?) * Transaction validation * Parts * Recursion - can reuse * ZK Assembly - try to use to write WASM ROM * See if it can express it * Some things are not efficient in processor, so need a special state machine for them * Don't know until you do it * Start with easy-to-write state machines * Important to undestand how verification works * E.g. public/private inputs * Q: Will ZK Assembly change with PIL2? * Can start with ZK Asm, no need to depend on PIL2 * In-person training session * Beginning of September * Technical questions * How big will the circuit be for: * Context: Trying to understand how computation size influences proof time and circuit size * `Fibonacci(N)`, with N in (20, 25, 30) (corresponds to values 6765, 75025, 832040) * `SUM(1..10^8)` * `SHA256(1MiB of random data)` * Let's go over [diagram](https://zkevm.polygon.technology/assets/images/fig5-main-prts-zkpr-042cd579e903d351ced9ec16a8ee7d9c.png) from https://zkevm.polygon.technology/zkProver/overview/#components-of-zkprover and discuss * Is this still an accurate representation? * What each input/output would be in case of ZK EVM * How long each step takes and how large are the outputs ## August 2, 2023 * Why use JS? * Used mainly for prototyping * In production migrated to C++ * Intros * What ZK-ROM? * ROM - Read-only-memory * Understanding how PIL stack works * Questions: https://hackmd.io/nRbL3yfuSDSEq3GKCQJE1Q?view#Questions * Proof system in use * https://eprint.iacr.org/2023/474.pdf * https://zkevm.polygon.technology/docs/zkProver/intro-stark-recursion

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.