# Assignment: Understanding and Applying Proof Systems

ZK Core Program (Week 2) - 5/7/2025

## 1. What is a Proof System?

Answer suggestion :
> * Definition: Proof system is ...
> * Key properties: completeness, soundness, zero-knowledge (optional)
> * Common categories of Proof Systems: Interactive vs. Non-interactive, ZKP, ...
> * Examples: PLONK, Groth16, STARK,...

## 2. Choose one of the two following directions

### 2.1. (Option 1) Apply a Proof System to Solve a Real-World Problem

#### 2.1.1. Describe the Problem

* Clearly explain the context and motivation.
* Identify a specific problem where issues of privacy, integrity, or verification arise.
* Explain why a Proof System is needed or suitable in this scenario.

#### 2.1.2. Introduce the Solution with a Proof System

* Describe what the Proof System contributes to solving the problem.
* Clarify which aspect it improves (e.g., privacy, integrity, verifiability, transparency).

#### 2.1.3. Detailed Design of the Solution

**a. Problem Modeling**

* Present a simplified abstraction of the system (participants, data flow, constraints).
* You may include a diagram or structured text.

**b. Architecture of the Proposed System**

* Explain the roles of the prover, verifier, and any servers or infrastructure.
* Outline how the proof generation and verification flow will operate.

**c. Techniques and Tools to Be Used**

* Select appropriate cryptographic techniques: (zk)SNARK, (zk)STARK, Bullet Proof, etc.
* Mention libraries or frameworks: Circom, SnarkJS, Halo2, Noir, etc.

**d. Implementation Plan**

* Phase 1: Requirement analysis and design
* Phase 2: Development of the proof system components
* Phase 3: Integration and testing

**e. Task Assignment (for team-based work)**

* Assign roles such as:

* Circuit designer
* Frontend/backend developer
* Verifier and server logic implementer
* Documentation and testing lead

---
#### Example

> [!NOTE]
> zkVoting Example

**Problem:** E-voting systems often compromise voter privacy.

**Proposed solution using ZKP:**

* Voters register their public keys with the election server.
* Instead of signing the vote directly, the voter generates a zero-knowledge proof stating:
*"I know a private key corresponding to one of the registered public keys, and my vote is integrity."*

**Technical aspects:**

* Use zk-SNARK to construct the proof
* Use a Merkle Tree to commit the list of registered public keys
* Circom or Halo2 can be used to implement the circuits

**Timeline:**

* Weeks 1–2: Problem modeling and system design
* Weeks 3–4: Circuit implementation and system integration
* Week 5: Testing and documentation

**Team roles:**

* Member A: Circuit implementation
* Member B: Frontend interface
* Member C: Server logic and verification

---

### 2.2. (Option 2) Build Quality Learning Resources for a Specific Area in Proof Systems

#### 2.2.1. Select a Topic You Want to Contribute To

* Choose a specific subfield of proof systems that interests you (e.g., zk-SNARKs (Groth16, PLONK,...) , zk-STARKs, Bulletproofs, Verifiable Delay Functions, Recursive Proofs).
* Justify your choice: Is it difficult to learn? Is there a lack of quality resources in Vietnamese or English? Does it require deep foundational knowledge?

#### 2.2.2. Proposal to Develop Learning Resources

**a. Planned Structure of the Resource**

* Learning materials may include:

* Written documentation
* Conceptual explanations
* Tutorials or walkthroughs
* Exercise sets or problem sheets
* Code repositories and demos
* Curated external references

**b. Breakdown of Each Component**

* **Introduction:** Overview of the topic, its motivation, and use cases
* **Background Knowledge:** Required tools (e.g., polynomial interpolation, Merkle trees)
* **Core Concepts:** Deep dives into protocol components
* **Tutorials:** Code walkthroughs or hands-on labs
* **Practice Problems:** Design small circuits, verify toy problems
* **Reference Materials:** Recommended papers, blogs, GitHub repos, videos

**c. Implementation Plan**

* Week 1: Define structure and gather references
* Weeks 2–3: Write theory and explanation content
* Week 4: Develop examples and exercises
* Week 5: Publish the resources (e.g., GitHub, Notion, website)

**d. Task Distribution (for team work)**

* Member A: Theory writing
* Member B: Examples and coding
* Member C: Exercises, editing, and presentation

---
#### Example Proposal

> [!NOTE]
> Create qualify resource for STARK

**Topic:** STARK

**Motivation:** STARKs are transparent, post-quantum secure, and increasingly adopted. However, they are hard to learn due to heavy mathematical requirements and fragmented resources.

**Components of the Resource:**

1. **Introduction**

* What are zk-STARKs?
* Use cases and advantages (no trusted setup, scalable)

2. **Prerequisites**

* Polynomial interpolation
* Low Degree Extension (LDE)
* Merkle Trees
* FRI protocol

3. **In-depth Analysis**

* Trace generation
* Constraint systems
* Composition polynomial
* Proof generation and verification steps

4. **Examples and Exercises**

* Create a STARK that proves the correctness of Fibonacci sequence generation
* Practice on constructing FRI proofs manually

5. **Reference List**

* STARK 101 by Eli Ben-Sasson
* Tutorials from Giza or Lambdaclass
* Selected GitHub repos and research papers

**Implementation Timeline:**

* Week 1: Outline and resource collection
* Weeks 2–3: Theoretical content and diagrams
* Week 4: Exercises and toy examples
* Week 5: Final assembly and publishing

**Team Roles:**

* Member A: Write theoretical content
* Member B: Build coding examples
* Member C: Organize and publish the materials