zkEVM Bootcamp

What are ZK EVMs, part 1: Overview We’re starting to look at the VM part of zkEVM blockchains. In this lesson, we’ve covered several examples of them and more general theory. A zkEVM is a virtual machine in the form of a ZK circuit designed to emulate EVM by recreating all the opcodes as well as other features of EVM blockchains such as gas costs. While full compatibility with Ethereum is what most developers desire, in reality, this comes with a huge drawback in the form of higher complexity of the circuit and fewer final benefits like the throughput and fees on L2....

What are ZK EVMs, part 2: Universal circuits/circuit compiler EVM is a stack-based virtual machine. For example, if we want to add two numbers, 3 and 9, we first need to push them onto the stack and then call ADD opcode: PUSH1 3 PUSH1 9 ADD The zkEVM Prover we want to build has to compute all these small operations (create traces), which lead to changes in the blockchain’s global state....

What are ZK EVMs, part 3: Proving systems Week 4, more than half of the bootcamp. Polynomial Commitment Schemes A simple example of a commitment scheme in Solidity is: You make a keccak hash of some secret string, e.g., “hello”. Then you save it in a smart contract storage. Anybody can see the hash and make some operations, knowing you can’t change the underlying string. After the operations have been done, you reveal the string....

Presentation by Porter Adams Today was a less formal lesson where I finally had an opportunity to flex some knowledge because I’ve spent two weeks trying to figure out how zkSync works in the recent C4 contest :D We’ve talked briefly about things that we previously learned in the other lessons but from a different perspective. More interestingly, we discussed the security aspects of zk rollups and many of the common concerns that developers in the space are trying to solve:...

Overview of Proving Systems In this lesson, we repeated some parts from the previous ones, like the history of ZKP, trusted setup, SNARK vs STARK, etc. STARK uses FRI as a commitment scheme, which stands for Fast Reed-Solomon IOP of Proximity. They have a much larger proof size (like 100 kB), which is not feasible if we talk about L1 Ethereum, but a transparent setup due to the chosen commitment scheme, plus the post-quantum security....

SNARK implementation As mentioned on Day 13, SNARKs comprise a probabilistic proof and a commitment scheme. They usually require a setup where we establish a) the program that will be proved and b) some randomness. The randomness is useful both in interactive and non-interactive proofs. We use it to keep the system sound because otherwise, the Prover can craft malicious proofs. The system won’t be sound if the values we use to create randomness are known....

STARK implementation STARKs, as was mentioned before, don’t have toxic waste. This means we can make a transparent setup quick and easy. Also, they are quantum secure, but it is more like a nice topping. The fundamental security assumption of a STARK is a collision-resistant hash function, a well-known cryptographic primitive. Cairo VM (Starknet) uses AIR (arithmetic intermediate representation) arithmetization, in opposite to the popular R1CS. Computation integrity It is one of the features of STARKs (and SNARKs)....

Plonk, part 1: Linea Two days ago, we talked about the trace tables, as you probably remember. We can express our gates or steps in the form of a table, which gives us a nice visual of the data that we use to generate proof. Today, we’ve taken an example with the Fibonacci numbers, which you can read in more detail here. Presentation by Emily and Alexandre from Linea Linea is a zk-rollup; it uses validity proofs to create batches of transactions and post them on L1....

Plonk, part 2: Boojum Customizable Constraint Systems An interesting and new concept of generalization of the usual constraint systems: Plonky2 It is a library by Polygon that allows us to create SNARKs with PLONK and FRI. We’ve taken a quick example of how to make a circuit to prove a polynomial. Check out the corresponding homework; I’ll make a Rust program with Plonky2 later. Presentation of Boojum by Oles Holembovskyy from zkSync The execution trace table has a size of ~$240$ columns with ~$2^{20}$ rows, which contain gates, lookup arguments, and copy-permutation arguments....

ZKML You all know what ChatGPT or Bard is; no news here, I guess. You’ve probably also heard about how these models are trained. During the process, the neural networks of the machines are adjusted. Each node has its weight. Each iteration can change these weights. Use cases ZKML (Zero-Knowledge Machine Learning) allows us to: Prove the match an input with an output in a succinct way. Make ML-as-a-service transparent. The providers of these services can add proofs to their API so the users can know a certain version of a model with the chosen parameters processed their input....