Zero-Knowledge Proofs

Formal Definition

A zero-knowledge proof is an interactive protocol between a prover P and verifier V where:

• P convinces V that a statement x ∈ L is true (where L is some language)
• V learns nothing beyond the truth of the statement

Types of ZK Proofs

Proof of Knowledge

Demonstrates that the prover knows a witness w such that (x, w) satisfies some relation R.

Proof of Membership

Demonstrates that x belongs to a language L without revealing which witness was used.

Common Proof Systems

Σ-Protocols (Sigma Protocols)

Three-round public-coin honest-verifier zero-knowledge proofs:

1. Commitment: Prover sends a commitment
2. Challenge: Verifier sends a random challenge
3. Response: Prover responds based on the challenge

Bulletproofs

Short non-interactive zero-knowledge proofs without trusted setup. Commonly used for range proofs in cryptocurrencies.

zk-SNARKs

Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge

• Succinct: Proofs are small and fast to verify
• Non-Interactive: Single message from prover to verifier
• Arguments: Computational soundness (vs. statistical)

zk-STARKs

Zero-Knowledge Scalable Transparent Arguments of Knowledge

• Scalable: Proving time grows quasi-linearly
• Transparent: No trusted setup required
• Post-Quantum: Based on hash functions

Comparison

Next: Interactive vs Non-Interactive