# Cairo VM in Halo2
## Motivation
The Cairo language is a popular programming language for building zero knowledge applications which has a long track record with production apps built on top and zk friendly design. Building the Cairo VM in halo2 would allow any previous code written in the VM to be able to generate ZK proofs that can be efficiently verified on-chain through our existing snark-verifier stack. Compared to proofs generated by STARK, proofs generated by Halo2 with KZG backend should have smaller proof size, cheaper verification cost with tradeoff on transparency and post quantum security.
**goal**: verify any Cairo program on Ethereum using Halo2 efficiently at bytecode level. We don't plan to support builtins in this project.
## Design
**Cairo frontend**: Transform Cairo program into Cairo chip input data. The vm function succeeds iff executing the Cairo program generates expected return value.
**Cairo Chip input**: data fed to the circuit simulating state transition of Cairo VM. includes:
1. immutable memory
2. value of the three registers before & after execution
3. public instance constraints to enforce Cairo program return value is expected.
4. number of cpu cycles

**Cairo Chip**: circuits built on halo2 simulating state transition function of Cairo VM.
**VM function**: given register values, number of cpu cycles and memory, return True if:
1. all public instance constraints satisfied.
2. no unidentified behavior.
3. after running state_transition function for the given cpu cycles, the register values match expected register value.

**state transition function**: given register values, return register values after one cycle. Panic if unidentified behavior encountered. Halo2 works on scalar field of the BN254 curve, so we need to apply field emulation to simulate arithemtic operations on Cairo's native fields.
**memory read function**: read the immutable memory at arbitrary index. Will start with naive O(n) solution then adopt dynamic lookup table.

## Milestones
1. implement and teststate transition function following Cairo paper.
2. implement and test VM function which works on arbitrary cpu cycles & memory size.
3. implement Cairo frontend that transforms Cairo programs to Cairo chip inputs.
4. adopt dynamic lookup table to speed up memory reading.