owned this note   changed a year ago  
Published Linked with GitHub

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

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
  • 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
  • DONE: Change the frequency to 1 per month for now

March 4, 2024

  • Andrei: Understand PIL2 benchmark results
    • 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?
    • 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
  • PIL2 Components
  • Next time: Andrei: Any experts in 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
      • 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
    • 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?
  • 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
  • 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
  • [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?
    • 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
    • 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?
    • 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
    • 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 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 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

December 18, 2023

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 <– Next time

    • Performance Tracking
      • 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

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

November 27, 2023

November 20, 2023

November 14, 2023

  • Progress on Stage 1 (https://github.com/near/wasmtime/milestone/1)

  • Any blockers that Andrei can help with?

    • What are the largest design questions that we need to resolve?
    • 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

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. 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
  • 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 for meeting in London
    • Anything to add?
    • Let's confirm who will lead each session

August 30, 2023

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)
      • 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

August 14, 2023

  • Bowen: logistics for the meeting in London
  • akashin: Discuss the ZK WASM roadmap
    • 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?

August 9, 2023

August 8, 2023 - ZK WASM Workshop

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)
      • "Type 2" 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 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

Select a repo