Cycle#1 - ZKP Study Club Planning / ZKP Introduction / Case Study - Dark Forest Game

ZKP Study Club Planning

Goal

• Expect we can read new ZKP related works without too much effort
• Expect we can be able to build cool projects using ZKP
• …

Rule

• Two week a cycle
• Each cycle has 1-2 host(s), and we take turn (or volunteer) to host
• Next cycle's host should assign some main resources as others' preparation to keep up for next cycle
• Everyone is nice to be prepared for next cycle
• …

ZKP Introduction

ZKP

Evolution

• GMR85/89
  • Introduce Zero-Knowledge Proof, with 3 properties:
    • Complete
      If the statement is true and both prover and verifier follow the protocol; the verifier will accept.
    • Sound
      If the statement is false, and the verifier follows the protocol; the verifier will not be convinced.
    • Zero-Knowledge
      If the statement is true and the prover follows the protocol; the verifier will not learn any confidential information from the interaction with the prover but the fact the statement is true.
  • A ZKP makes it possible to prove a statement is true while preserving confidentiality of sercret information
• GMW86/91
  • Under the assumption that encryption functions exist, all languages in NP possess ZKP. (proved by graph 3-colorability)
• BFM88
  • Introduce CRS model to achieve Non-Interactive ZKP (NIZK)
• Kil92
  • Construction of probabilistically checkable proofs which total amount of communication can be less than that needed to transmit the NP witness.
  • Succinctness is born
• FS86
  • Convertion from public-coin interactive proof of knowledge into NIZK under random oracle model
• Gro10
  • Pairing-based
  • Introduce q(k)-power knowledge of exponent assumption (q-PKE)
  • Introduce q(k)-computational power Diffie-Hellman assumption (q-CPDH)
• GW11 - SNARG
• BCCT12 - SNARK
• GGPR13
  • Introduce QSP and QAP
• PHGR13(Pinocchio), Gro16
  • Implementation of pairing-based zk-SNARK
  • Constant proof size
  • Linear prover time
  • Trusted setup per circuit
• MBKM19(Sonic), GWC19(Plonk), CHMMVW20(Marlin)
  • Universal trusted setup
• BFS19(Dark), BGH19(Halo), ZK-STARK
  • No trusted setup

Case Study - Dark Forest Game

For an easy to understand real world project using ZKP, I choose the Dark Forest Game as our first case study.

Note

• Proofs vs Arguments
  • Proofs need to be sound even against computationally unbounded provers.
  • Arguments only need to preserve soundness against computationally bounded provers.
  • Proof is used to designate both proofs and arguments for simplicity, although there are theoretical circumstances where the distinction can be relevant.

Reference

• ZKP Introduction
  • ZKP
    • Silvio Micali: Proofs, Knowledge, and Computation (Prof. M in GMR85)
    • Zero Knowledge Proofs: An illustrated primer by Matthew Green
      • Part 1
      • Part 2
    • Learning ZKP Series by sec-bit
      • Series 1
      • Series 2
      • Series 3
      • Series 4
      • Series 5
  • Evolution
    • ZKProof Reference
    • The evolution of pairing-based zero-knowledge proofs / Talk by Jens Groth
• Dark Forest Game
  • Game（管理員邀請制，可以去 discord 等 invitation key，或是請雅信直接和創辦人 bgu33 Brian Gu 和 Alan Luo 要 key，看需要幾組）
  • Circuit（我其實不確定這是不是最新現在在用的）
  • Introduction Video by Authors Brian Gu & Alan Luo (on zkSummit6)