Zero-Knowledge Properties:
1. Completeness: If statement is true, prover can convince verifier
2. Soundness: If statement is false, prover cannot convince verifier
3. Zero-Knowledge: Verifier learns nothing except truth of statement

Example: Proving you know a password without revealing it

Ali Baba's Cave:

┌─────────────────────────────────────────────────────────────────────┐
│                                                                   │
│                    ┌──────────────────────┐                      │
│                    │                      │                      │
│                    │    Magic Door        │                      │
│                    │    (Secret Password) │                      │
│                    │                      │                      │
│   Path A ──────────┤                      ├────────── Path B    │
│                    │                      │                      │
│                    └──────────────────────┘                      │
│                                                                   │
│   Process:                                                        │
│   1. Verifier stands outside                                      │
│   2. Verifier randomly calls Path A or Path B                    │
│   3. If Prover knows password: Can emerge from any path          │
│   4. Repeat 50 times → Confidence approaches 100%               │
│   5. Verifier learns nothing about the password                  │
│                                                                   │
└─────────────────────────────────────────────────────────────────────┘

ZK-SNARK Components:

1. Setup Phase (Trusted Setup):
   - Generate common reference string (CRS)
   - One-time setup
   - Security-critical
   - Requires multi-party computation (MPC)

2. Prover:
   - Input: Statement + Witness + CRS
   - Output: Proof (small ~200 bytes)

3. Verifier:
   - Input: Statement + Proof + CRS
   - Output: True/False
   - Fast verification (~milliseconds)

4. Proof System:
   - Elliptic curve pairings
   - Polynomial commitments
   - Quadratic Arithmetic Programs (QAPs)

QAP Construction:
1. Circuit → R1CS (Rank-1 Constraint System)
2. R1CS → QAP (Quadratic Arithmetic Program)
3. QAP → ZK-SNARK

R1CS:
- Each constraint: (A × B) = C
- A, B, C are vectors
- Valid if all constraints hold

QAP:
- Polynomials A(x), B(x), C(x)
- Check: A(x) × B(x) = C(x) at random points
- Efficient verification

ZK-SNARK Proof:
1. Prove A(x) × B(x) = C(x)
2. Zero-knowledge: Randomize proof
3. Succinct: Constant size

ZK-STARK Characteristics:
1. Trusted Setup: None (transparent)
2. Post-Quantum: Hash-based (quantum resistant)
3. Prover Time: O(n log n)
4. Verifier Time: O(log² n)
5. Proof Size: O(log² n)
6. No Pairings: Only hash functions

ZK-STARK Construction:
1. Arithmetic Circuit → Polynomial
2. Low Degree Extension (LDE)
3. FRI (Fast Reed-Solomon Interactive Oracle Proof)
4. Hash-based commitments
5. Interactive challenge/response

Privacy Coin Examples:

Zcash:
- Uses zk-SNARKs
- Shielded transactions
- Hides sender, receiver, amount
- Selective disclosure

Monero:
- Uses ring signatures
- Confidential transactions
- Stealth addresses
- Different approach

Aztec:
- Layer-2 ZK solution
- Private DeFi
- Encrypted balances
- Public verification

ZK-Rollup Architecture:
┌─────────────────────────────────────────────────────────────────────┐
│  Off-Chain:                                                       │
│  1. User submits transaction to sequencer                         │
│  2. Sequencer batches transactions                               │
│  3. Executes state transitions                                   │
│  4. Generates ZK proof                                           │
│  5. Submits proof to L1                                          │
│                                                                   │
│  On-Chain:                                                        │
│  1. Verifier contract checks proof                               │
│  2. Updates state root                                           │
│  3. Validates transaction                                        │
│  4. Finalizes batch                                              │
│                                                                   │
│  Benefits:                                                        │
│  • 100-1000× scalability                                         │
│  • Instant finality                                              │
│  • No challenge period                                           │
│  • Ethereum security                                             │
└─────────────────────────────────────────────────────────────────────┘

ZK-KYC Process:

1. User completes KYC with regulated provider
2. Provider issues Verifiable Credential
3. User generates ZK Proof:
   - "I am over 18"
   - "I am not on sanctions list"
   - "I have verified identity"

4. Service provider verifies proof
5. No personal data exposed
6. Compliant with regulations

Trusted Setup (ZK-SNARK):
- Requires initial multi-party computation (MPC)
- Toxic waste: Must be destroyed
- If compromised: Fake proofs possible
- Solution: MPC ceremonies (many participants)

Trusted Setup Alternatives:
- ZK-STARK: No trusted setup
- Halo: Recursive SNARKs
- PlonK: Universal setup
- Marlin: Transparent setup

Circuit: Prove you know secret s such that:
y = s³ + s² + s

Variables:
- s: Secret (witness)
- y: Public input

Constraints:
1. v₁ = s × s (s²)
2. v₂ = s × v₁ (s³)
3. y = v₂ + v₁ + s

R1CS Representation:
Constraint 1: A₁ = s, B₁ = s, C₁ = v₁
Constraint 2: A₂ = s, B₂ = v₁, C₂ = v₂
Constraint 3: A₃ = v₂+v₁+s, B₃ = 1, C₃ = y

1. User submits transaction:
   - Sender
   - Recipient
   - Amount
   - Signature

2. Sequencer:
   - Collects transactions
   - Orders them
   - Executes state transition

3. Prover:
   - Generates ZK proof
   - Proves state transition valid
   - Compresses state update

4. L1 Contract:
   - Verifies proof
   - Updates state root
   - Finalizes batch