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
- 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)
- BFS19(Dark), BGH19(Halo), ZK-STARK
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
- Dark Forest Game