---
tags: study-club
---

# 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

{%pdf https://drive.google.com/file/d/1ElU0JssGM3sy1KhSeNRaehFJ93R_y_2k/preview %}

### 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](https://www.youtube.com/watch?v=WSuUTLqqLIU) (Prof. M in GMR85)
- Zero Knowledge Proofs: An illustrated primer by Matthew Green
- [Part 1](https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer)
- [Part 2](https://blog.cryptographyengineering.com/2017/01/21/zero-knowledge-proofs-an-illustrated-primer-part-2)
- Learning ZKP Series by sec-bit
- [Series 1](https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/1/zkp-back.md)
- [Series 2](https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/2/zkp-simu.md)
- [Series 3](https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/3/zkp-pok.md)
- [Series 4](https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/4/zkp-rom.md)
- [Series 5](https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/5/zkp-crs.md)
- Evolution
- [ZKProof Reference](https://docs.zkproof.org/pages/reference/reference.pdf)
- [The evolution of pairing-based zero-knowledge proofs](http://www0.cs.ucl.ac.uk/staff/j.groth/ZKProof2019.pdf) / [Talk](https://www.youtube.com/watch?v=X-z3JYlFdzs) by Jens Groth
- Dark Forest Game
- [Game](https://zkga.me)（管理員邀請制，可以去 [discord](https://discord.gg/sjgGGq6D) 等 invitation key，或是請雅信直接和創辦人 bgu33 Brian Gu 和 Alan Luo 要 key，看需要幾組）
- [Circuit](https://github.com/darkforest-eth/darkforest-v0.3/tree/master/circuits)（我其實不確定這是不是最新現在在用的）
- [Introduction Video by Authors Brian Gu & Alan Luo (on zkSummit6)](https://www.youtube.com/watch?v=1C0z3bR-YdE)