# ZK WASM Roadmap
Author: akashin
Created on: 11 August 2023
Status: WIP

---

Our long-term goal is to build an efficient ZK prover for a broad set of Web Assembly programs.

## Background

Building such prover is challenging because of the impedance mismatch between current ZK systems that can efficiently prove only some types of computations (arithmetic identities, table lookups) and Web Assembly that assumes a modern CPU architecture with support for bitwise operations, floating point numbers and random-access memory. This could lead to a long proving time, depending on how exactly WASM is mapped to [ZK Assembly](https://zkevm.polygon.technology/category/zk-assembly) and [PIL](https://zkevm.polygon.technology/PIL/introduction).
Moreover, Web Assembly instruction set is quite broad and has around [400 instructions](https://webassembly.github.io/spec/core/appendix/index-instructions.html) which increases the scope of the work.
Lastly, because we're aiming for a universal WASM prover that can take as an input a list of WASM programs (e.g. contract calls from the list of NEAR transactions), any optimizations before the execution of WASM programs (similar to optimizations during compilation from WASM to x86) will also have to be proven with ZK circuits. In other words, in practice, we will be comparing the proving time for WASM program with the time it takes to execute the compiled and optimized for x86 version of the same program on a validator machine.

## Plan of attack

For all the reasons above, it will likely take a long time (months to years) to reach the goal and it makes sense to tackle this problem incrementally by iterating these two steps:
1. Increasing the scope of supported workloads and WASM instructions
2. Improving the performance of the prover on these workloads

Within each iteration we will be:
- Extending and optimizing the implementation of WASM interpreter in ZK circuits
- Adjusting ZK circuits to support new WASM programs more efficiently

We can organize the work around milestones:

## M1: Simple program, basic i32 operations

In this milestone we will support WASM programs with a single main function that uses only i32 arithmetic and boolean operations.

Proving time for this workload should be no more than 1000x slower than the execution with the current Wasmer singlepass compiler on x86.

For this milestone, we will use the design described in https://hackmd.io/@ke2spS4iQmu1IxfGt3-qoQ/BknTXqQ3n.

Supported WASM features:
- `module`, `import`, `func`, `param`, `start`, `call`
- `i32.const`, `i32.add`, `i32.eq`

Example program:

(module
 (import "env" "assert_eq" (func $assert_eq (param i32) (param i32)))
 (func $main
	i32.const 2
	i32.const 3
	i32.add
	i32.const 5
	call $assert_eq)
 (start $main))

Note, that the call to an imported function `assert` will generate an [`ASSERT` in ZK Assembly](https://zkevm.polygon.technology/zkASM/basic-syntax#asserts).

## M2: Simple program with control flow

We extend the previous milestone with WASM instructions that allow to express control flow, e.g. conditionals and loops.

We'll support canonical arithmetic workloads like Fibonacci number calculation and simple hash functions.

Same expectations about proving time as in M1.

New supported WASM features:
* `local`, `local.get`, `local.set`
* `block`, `loop`, `br_if`, `br`

Example program:

(module
 (import "env" "assert_eq" (func $assert_eq (param i32) (param i32)))
 (func $main
	(local $counter i32)
	(local.set $counter (i32.const 0))
	(block
	 (loop
		(local.set $counter
		 (i32.add
			(local.get $counter)
			(i32.const 1)))
		(br_if 1
		 (i32.eq
			(local.get $counter)
			(i32.const 10)
		 )
		)
		(br 0)
	 )
	)
	(local.get $counter)
	(i32.const 10)
	call $assert_eq)
(start $main))

## M3: Program with function calls

We allow function calls within the program.

New supported WASM features:
* `return`