zkEVM Bootcamp – Week 1

This is the first week of the zkEVM Bootcamp by Encode.

Scalability

Ethereum L1: Bizantine Fault Tolerance: voting approach. As we increase the number of validators, it will increase the network traffic and give scalability problems.

Solana’s approach: move away from gossip protocol: when they have tx’s they are sent to the block producer.

Parallel processing of transactions: Solana, Aptos Sui. Depends on the shared state that we have. They rely on an understanding what areas of state will be changed by a transaction.

Limitations of nodes:

computing power
bandwidth
storage

Off-chain scaling

L2 solutions:

plasma: i.e. Matic
state channels: i.e. Raiden
side chains: i.e. xDai
validium: i.e. Stark
rollups: i.e. Hermez

Rollups

The main chain holds funds and commitments to the side chains.
The side chain holds state and performs execution.

There needs to be some proof, either fraud proof (optimistic) or a validity proof (zk). Rollups require operators to stake a bond in the rollup contract. This incentivizes operators to verify and execute transactions correctly.

Zero Knowledge Proof Rollups

Validity Proofs present evidence that a state transition is correct. They reflect a more pessimistic view of the world. Blocks include values representing L2 state if, and only if, that state is correct. The zero knowledge aspect is usually ignored (the inputs and data involved is usually public).

Optimistic rollups

Fraud Proofs present evidence that a state transition was incorrect. They reflect an optimistic view of the world: the assumption is that blocks represent only correct states of L2 data, until proven otherwise. In reality, a committed block could well include an incorrect state transition.

State Channels

Allow to transact many off-chain transactions but only require 2 transactions on the L1 blockcain, one at the start and one at the end. Participants should lock a deposit on a multisig contract. I.e. Lightning network.

Plasma Chains

The Mass Exit Problem: moving assets from L2 to L1 takes a long time with Plasma and Optimistic.

Validium Chains

Validium doesn’t store data onchain while Rollup does.

3 Major Transitions

Vitalik sees 3 major transitions:

The L2 scaling transition – moving to rollups
The wallet security transition – moving to smart contract wallets
The privacy transition – make sure privacy preserving funds transfers are available

Layer 2

Bridging: Mechanism of lock and mint.

Optimistic rollup:

bundle multiple transactions on a batch.
compress data using techniques: a simple tx takes 110 bytes. An ETH tx on a rolllup takes only ~12 bytes
aggregators: there is a guarantee that the transaction will be included or else the aggregatore loses their bond.

zkEVM Introduction

zkEVM is a virtual machine, recreates all EVM opcodes, processes state transistions from execution of L2 transactions, which users transmit to the net. After this it generates validity proofs that confirm the accuracy of the off-chain state change computations.

Eventually calldata will move to blobs.

(proto) Danksharding

EIP-4844 introduces a new transaction type with an additional data field (blob), up to 125kB. These blobs are commited with KZG.

This will create a new fee market, distinct from the existing gas market. L2s will benefit as the cost of posting transactions to L1 could be reduced by 10-100 times.

These data blobs are not accessible to the EVM and deleted after 1-3 months.

Rollups post tx in data blobs along with a data commitment, created by fitting a polynomial function to the data. Provers will use the same function on the data to confirm its integrity.

The proposal-builder separator.

Cryptography Background

Hash functions: running some data on a hash function it creates a commitment on the result (digest). It also gives obfuscation, as it is very difficult to get the input from a given output. Ethereum uses Keccak which is not very zk friendly (i.e. Poseidon is)
Symmetric/Asymmetric Encryption
Fully Homomorphic Encryption: it allows arbitrary computations on encrypted data without access to the secret key. The result of the computation remains encrypted. I.e. if you want an external party to process some private data, you can give it the encrypted data they process it and you get it back and then decrypt it. this is used
- fhEVM from zama.ai
- Verifiable Random Functions: from Algorand. A cryptographic `rimitive that maps inputs to verifiable pseudorandom outputs. I.e. use a verifiable random function to give you verifiable randomness to choose a block producer.
- Verifiable Delay Functions: a way to show that some amount of time has happened o. I.e. Solana’s Proof of History
Fields
Modular Arithmetic
Group Theory: set of elements, plus a binary operation with properties of closure, associativity, identity element.

Fields

Generators: every finite field has a generator.
Group Homomorphisms: is a map between 2 algebraic structures of the same type, preserving the operations.
Equivalence classes:
- Since
  6 mod 7 = 6
  13 mod 7 = 6
  20 mod 7 = 6
  ….
  6, 13, 20… form an equivalence class.
  x mod 7 = 6
  This gives us the basis for a one way function. We cannot say which x produced that.

Fermat’s Little Theorem

A way to find multiplicative inverse: a ^-1 = a ^ (p-2) (modp)

Polynomials

If one root r of degree n is known then polynomial long division can be used to factor it into the form (x-r)(Q(x)), where Q(x) is a polynomial of degree n-1.

Schwarts-Zippel Lemma: “different polynomials are different at most points”.

If we have 2 non-equal polynomials of degree at most d, they can intersect at no more than d points.

Lagrange Interpolation

If we have a set of points we can interpolate using Lagrange and we get a polynomial that passes through all those points.

Complexity Theory

Tractable problems:

class P: problems that can be solved in polynomial time and verified as polynomial time
class NP: solutions can be verified in polynomial time, but it does not mean that we can find the solutions in polynomial time
class NP-Complete: we can transform a problem into another problem
class NP-Hard:

Interactive Proofs

There could be interaction between the prover and the verifier. And it could also be some randomness involved.

The sum check protocol.

Zero Knowledge Proof

Proving that we know something with only once piece of information shared: if the proof is valid or not.

ZKP Families: the Cambrian Explosion

Wormholes

The portal network: split up the state, as an alternative to centralization (Infufra, Alchemy)
D-LOG problem with limited classes

Matter

Arithmetic Operations with a modulo operation of a prime number. Example
A blob is been produced. Check the polynomial against the data to see it’s correct