Try   HackMD

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