ZKP学习笔记

ZK-Learning MOOC课程笔记

Lecture 12.1 zkEVM design, optimization and applications

  • Scroll
    • A scaling solution for Ethereum
    • An EVM-equivalent zk-Rollup
  • Background & motivation
    • The diagram of Layer 1 blockchain
      • Advantages: Secure, Decentralized
      • Disadvantages: Expensive, Slow
    • Zk-Rollup
      • Scroll: a native zkEVM solution
        • Advantages: Developer-friendly, Composability
        • Disadvantages: Hard to build, Large proving overhead
      • zkEVM becomes possible
        • Polynomial commitment
        • Lookup + Custom gate
        • Hardware acceleration
        • Recursive proof
      • zkEVM flavors (by Justin Drake)
        • Language level: Transpile an EVM-friendly language (Solidity or Yul) to a SNARK-friendly VM which differs from the EVM. (“Compiler” EVM to EVM-friendly language)
        • Bytecode level: Interpret EVM bytecode directly, though potentially producing different state roots than the EVM, e.g. if certain implementation-level data structures are replaced with SNARK-friendly alternatives. (Scroll)
        • Consensus level: It proves validity of L1 Ethereum state roots.
  • Build a zkEVM from scratch
    • The workflow of zero-knowledge proof
      • Program => Constraints => Proof
      • Scroll
    • Plonkish Arithmetization
      • Custom gate
      • Permutation
      • Lookup argument (range proof & xor, reduce the circuit size)
    • How should we choose “front-end”?
    • What you need to prove
      • zkEVM takes the execution traces as witness and proves it. (spec: constrains)
      • The verifier only knows the input tx / world state and the output world state.
    • EVM circuit
      • ADD
        • Step context: When sADD == 1, pc’ - pc == 1
        • Case switch: sADD is binary, sADD == 1, 1-sADD == 0; only one variable is 1.
        • Opcode specific witness: prove that a and b are consistent with that have been pushed into EVM.
          • RAM circuit (E.g., prove write after read)
      • Hash
        • Hash is complex calculation
        • Hash lookup table: preserve (input, hash) pair; use the hash circuit to prove the lookup table is correct.
      • The architecture of zkEVM circuits
    • The proof system for zkEVM:
      • Two-layer architecture: Aggregation circuit
      • The first layer
      • The second layer
        • Aggregation circuit: prove the proof is valid
      • Scroll Implementation
        • The first layer is Halo2-KZG (Poseidon hash transcript)
          • Custom gate, Lookup support
          • Good enough prover performance (GPU prover)
          • The verification circuit is “small”
          • Universal trusted setup
        • The first layer needs to be “expressive”
          • EVM circuit has 116 columns, 2496 custom gates, 50 lookups
          • Highest custom gate degree: 9
          • For 1M gas, EVM circuit needs 2^18 rows (more gas, more rows)
        • The second layer is Halo2-KZG (Keccak hash transcript)
          • Custom gate, Lookup support (express non-native efficiently)
          • Good enough prover performance (GPU prover)
          • The final verification cost can be configured to be really small
        • The second layer needs to aggregate proofs into one proof
          • Aggregation circuit has 23 columns, 1 custom gate, 7 lookups
          • Highest custom gate degree: 5
          • For aggregating EVM, RAM, Storage circuits, it needs 2^25 rows
  • Interesting problems
    • Circuit: Randomness(Random Linear Combination, RLC)
      • Using a super circuit includes all small circuits (ECDSA, Keccak, EVM…)
    • Circuit: Layout
      • Plonkish: layout permutation (in R1CS, we need to implement like if-else)
    • Circuit: Dynamic size
      • Padding for all circuits to the same rows
      • Link all circuits together
    • Prover: Hardware & Algorithm
      • Our prover
        • GPU can make MSM & NTT really fast
        • Bottleneck moves to witness generation & data copy
        • Need large CPU memory (1TB -> 300GB+)
      • Hardware friendly prover?
        • Parallelizable & Low peak memory
        • Don’t ignore the witness generation
        • Run on cheap machines, more decentralized
      • Best way to compose different proof system?
        • he first layer needs to be “expressive”
        • The second layer needs to be verifier efficient (in EVM)
        • Should we move to a smaller field?
          • (Breakdown/FRI with Goldilocks, Mersenne prime)
        • Should we stick to EC-based constructions?
          • (SuperNova, Cyclic elliptic curve with fast MSM)
      • Security: Audit & Soundness
        • The best way to audit zkEVM circuit? (In general, VM circuit based on IR)
          • Audit Manually
          • Formal verification for some opcodes
  • Other applications using zkEVM
    • zkRollup
      • Prove n Txs on layer 2 are valid
      • Verify proof in smart contract
    • Enshrine blockchain
      • Prove layer 1 block directly
      • Recursive proof
      • One proof for blockchain
    • Proof of exploit
      • Prove I know a Tx that can change the state root to state root’ (Prove I know a bug that can change your balance, etc)
      • Prove to the applications without revealing the bug (to get reward from the application).
    • Attestation (“zk oracle”)
      • Read state, compute and verify i.e. Axiom (a zk co-processor)