This is the third week of the zkEVM Bootcamp by Encode.
Create a Simple Zero Knowledge Proof
Remix ZoKrates: to create zero knowledge proofs that get verified on Ethereum. Show that you know the square root of a particular number. a is a private value and b a public value. Non-interactive proof.
L3: Hyperchains
Possibilities:
- L2 for scaling, L3 for privacy
- L3 for general purpose scaling, L3 for customized scaling
- L2 for trustless scaling (rollups), L3 for weakly-trusted scaling
Privacy
From Aztec:
- privacy: all aspects of the tx remain hidden
- confidentiality: the inputs and outputs of a tx are hidden but the parties remain public
- anonymity: the inputs and outputs of a tx are public, but the tx graph is obscured, preventing identification of the parties
Commitment Schemes and Nullifiers: the commitment hides details of the asset and the owner. When the asset is transferred, the commitment is “cancelled” by the use of a nullifier and a new commitment created with the new owner. The nullifier is deterministically derived from the original asset details. Better for UTXO model, than Account based model. It’s used by zCash and Tornado Cash.
Aztec
The nullifiers are used for “deleting” data on an append only system.
With Circom you need to run a trusted setup in every circuit, but with plonk you can re-use it.
zkEVM
Typically consists of two components:
- Compiler: compiles high level languages (Rust…) into intermediate (IR) expressions for ZK system to perform
- Instruction Architecture Set Framework: executes the instructions about CPU operations and is a series of instructions used to instruct the CPU to perform operations
zkEVM Phases
Circuits:
- Circuit creation: specify the VM
- Setup: getting some public parameters (proving key and verification key)
- Proof creation
- Proof aggregation
- Proof acceptance on L1 verification
L2 aspects:
- Submit data to the DA layer
- Allow L1 and L2 messaging
- Provide an escape hatch via forced transactions
zkEVM Workflow
- Receive a tx
- Execute the relevant bytecode
- Make state changes and tx receipts
- Using zkEVM circuits with the execution trace as inmput and produce a proof of correct execution
- Aggregate proofs for a bundle of tx’s
- Submit data to L1
zkEVM Proof
The proof must encompass the following aspects related to the execution process:
- Confirm the bytecode is accurately loaded from persistent storage
- Demonstrate the opcoodes in the bytecode are executed sequentially without missing or skipping any opcode
- Verify the correct execution of each opcode, including the proper execution of the three sub-steps within each opcode (Read/Write and computation)
Interaction between parts within the EVM is complex. We can break it down into different State Machines:
- Keccak State Machine
- Storage State Machine (Poseidon)
- Poseidon State Machine
- Main State Machine
- Arithmetic State Machine
- Binary State Machine
- Memory State Machine
zkProver
We can combine different proving systems. I.e. start with a STARK (easy to create a proof) then create a SNARK proof (it’s from a smaller size)
Arithmetic Circuit Introduction
An Arithmetic Circuit is one way to represent our Domain Specific Language. They represent as a rank-1 constraint system, which can be transformed into polynomials, which is the next stage in the creation of the proof.
We can visualize our circuit as a number of addition and multiplication gates. These elements can be combined to represent any polynomial.
The circuit have constraints, which will be satisfied if the correct inputs to the gates are supplied, i.e. we get the correct witness.
When we implement a circuit we use large tables, where a gate is represented by a row in the table. When we are considering the interaction between the rows, this may be limited to nearby rows, but it varies with different arithmetisations.
What we need to prove
The core of the computations happen on the stack. The EVM wasn’t designed with zk in mind:
- EVM word size is 256 bit: finite fields are usually smaller. If we want to model variables in this sizes, we sometimes need to break it in several parts. To be sure that something is of certain size, we have an efficient range proof
- EVM has zk-unfriendly opcodes: we need a way to connect circuits
- Read and write consistency: we need efficient mapping
- EVM has a dynamic execution trace: we need efficient on/off selectors
Challenges on building a zkEVM
- Limited support for Elliptic Curves in EVM: currently EVM only supports BN256 pairing
- Mismatched Field sizes:
- Special Opcodes: like CALL and specific error types related to execution context and gas
- Stack-Based Model: zk wroks better register-based models
- Ethereum Storage Overhead: based in Merkle Patricia Trees and Keccak, both not zk friendly. Keccak has is 1000 times larger in circuit size compared to Poseidon hash
- Machine-Based proof overhead: integrating everything
- multiplication and addition gates
- custom gates: an optimization. i.e. take PLONK and optimize it
- lookup tables: many operations are not optimally represented by simple gates (i.e. bitwise operations or small range checks). In these cases we can create lookup tables and prepopulate them with values. Then we prove that the requisite value exists in the table. I.e. range check, value x is between 1 and 10. Put the values 1-10 in a lookup table and see if x is in that table. To do this, Plookup and Caulk
Wormholes
- Finite Field constant in bytecode. https://www.youtube.com/watch?v=b1jZZmfcyiY&list=PLaM7G4Llrb7x5JgkfCN9kf7IB6QtomyCu&index=21f7IB6QtomyCu&index=21