This guide uses visual diagrams and analogies to help beginners understand how the ZKP authentication system works.
- The Big Picture
- Traditional vs Zero-Knowledge Authentication
- The Cave Analogy (Visual)
- Registration Flow (Visual)
- Authentication Flow (Visual)
- Mathematical Concepts (Simplified)
- System Architecture
- Security Guarantees
┌─────────────────────────────────────────────────────────────────┐
│ What This Project Does │
├─────────────────────────────────────────────────────────────────┤
│ │
│ You prove you know your password WITHOUT revealing it │
│ │
│ ┌──────────┐ ┌──────────┐ │
│ │ │ "I know the password!" │ │ │
│ │ Client │ ──────────────────────────> │ Server │ │
│ │ 👤 │ │ 🖥️ │ │
│ │ │ "Proof accepted ✓" │ │ │
│ │ │ <────────────────────────── │ │ │
│ └──────────┘ └──────────┘ │
│ ↓ ↓ │
│ Knows password Never sees password! │
│ │
└─────────────────────────────────────────────────────────────────┘
Key Insight: The server can verify you know the password without ever learning what the password is!
┌──────────────────────────────────────────────────────────────────────┐
│ TRADITIONAL METHOD (Unsafe!) │
└──────────────────────────────────────────────────────────────────────┘
Step 1: Registration
┌─────────┐ ┌─────────┐
│ Alice │ "My password is: 'secret123'" │ Server │
│ 👤 │ ────────────────────────────────────────>│ 🖥️ │
└─────────┘ └─────────┘
│
↓
┌──────────┐
│ Database │
│ ──────── │
│ alice: │
│ hash( │
│ secret123│
│ ) │
└──────────┘
Step 2: Login
┌─────────┐ ┌─────────┐
│ Alice │ "My password is: 'secret123'" │ Server │
│ 👤 │ ────────────────────────────────────────>│ 🖥️ │
└─────────┘ └─────────┘
│
↓
Checks if hash
matches stored
hash
❌ PROBLEMS:
- Password sent over network (can be intercepted)
- Server sees your password (even if hashed later)
- If database is stolen, passwords can be cracked
- Man-in-the-middle attacks possible
┌──────────────────────────────────────────────────────────────────────┐
│ ZERO-KNOWLEDGE METHOD (Secure!) │
└──────────────────────────────────────────────────────────────────────┘
Step 1: Registration
┌─────────┐ ┌─────────┐
│ Alice │ Secret → Public Keys │ Server │
│ 👤 │ │ 🖥️ │
│ │ password ──┐ │ │
│ │ ↓ │ │
│ │ Math Magic 🎩 │ │
│ │ ↓ │ │
│ │ y1 = g^x mod p │ │
│ │ y2 = h^x mod p │ │
│ │ │ │ │
│ │ "Here are my public keys (y1, y2)" │ │
│ │ ────────────────────────────────────────>│ │
└─────────┘ └─────────┘
│
↓
┌──────────┐
│ Database │
│ ──────── │
│ alice: │
│ y1 │
│ y2 │
│ salt │
└──────────┘
(NO PASSWORD STORED!)
Step 2: Authentication
┌─────────┐ ┌─────────┐
│ Alice │ "I know x such that y1=g^x and y2=h^x" │ Server │
│ 👤 │ │ 🖥️ │
│ │ Generates proof using password │ │
│ │ (proof = commitments + response) │ │
│ │ │ │
│ │ "Here's my proof: (a1, a2, s)" │ │
│ │ ────────────────────────────────────────>│ │
│ │ │ │
│ │ │ Checks: │
│ │ │ g^s·y1^c│
│ │ │ = a1? │
│ │ │ h^s·y2^c│
│ │ │ = a2? │
│ │ │ │
│ │ "✓ Proof valid!" │ │
│ │ <────────────────────────────────────────│ │
└─────────┘ └─────────┘
✅ ADVANTAGES:
- Password NEVER leaves client
- Server NEVER sees password
- Database contains only public keys (useless if stolen)
- Replay attacks prevented (one-time server nonce)
- Each proof is unique and non-reusable
This famous analogy explains zero-knowledge proofs in an intuitive way.
┌─────────────────────────────────────────────────────────────────┐
│ Ali Baba's Cave │
│ │
│ Entrance │
│ │ │
│ ↓ │
│ ┌───────┐ │
│ ┌────┤ Cave ├────┐ │
│ │ └───────┘ │ │
│ │ │ │
│ (A) (B) ← Two paths │
│ │ │ │
│ │ │ │
│ │ ┌─────┐ │ │
│ └─────┤ 🚪 ├─────┘ ← Magic door in the middle │
│ │ 🔐 │ (requires password to open) │
│ └─────┘ │
│ │
└─────────────────────────────────────────────────────────────────┘
How it works:
Round 1:
────────
1. Alice enters cave, chooses path A or B randomly
Entrance Entrance
│ │
↓ ↓
┌─────┐ ┌─────┐
│ 👤 │ │ │
(A) (B) (A) (B)
│ │ │ │
└──🚪──┘ └──🚪──┘
Alice picked A (Bob can't see)
2. Bob enters (after Alice is inside) and shouts:
"Come out from path B!"
3. If Alice knows the password:
- She can open the magic door
- Walk through to path B
- Come out successfully! ✓
4. If Alice doesn't know the password:
- She's stuck on path A
- She has 50% chance to guess right
- If Bob had said "A", she'd be lucky
- If Bob said "B", she's caught! ✗
After 20 rounds:
────────────────
- If Alice knows password: Succeeds every time (100%)
- If Alice doesn't know: Probability of success = 0.5^20 ≈ 0.0001%
Bob becomes convinced Alice knows the password!
BUT Bob learns NOTHING about what the password actually is!
This is Zero-Knowledge! 🎉
┌────────────────────────────────────────────────────────────────────────┐
│ REGISTRATION PROCESS │
└────────────────────────────────────────────────────────────────────────┘
┌──────────────┐ ┌─────────────────┐
│ CLIENT │ │ SERVER │
│ (Alice) │ │ │
└──────────────┘ └─────────────────┘
│ │
│ 1. User enters username & password │
│ username = "alice" │
│ password = "secret123" │
│ │
↓ │
┌────────┐ │
│Generate│ │
│ Salt │ ← Random 256-bit value │
└────────┘ │
│ │
│ salt = "A7F9...B2C4" │
│ │
↓ │
┌─────────────────────┐ │
│ Derive Secret (x) │ │
│ │ │
│ x = SHA256(username │ │
│ + password │ │
│ + salt) mod q │ │
└─────────────────────┘ │
│ │
│ x = 1234567890... (KEPT SECRET!) │
│ │
↓ │
┌─────────────────────┐ │
│ Compute Public Keys │ │
│ │ │
│ y1 = g^x mod p │ │
│ y2 = h^x mod p │ │
└─────────────────────┘ │
│ │
│ y1 = 89ABC...DEF │
│ y2 = 12345...678 │
│ │
│ ═══════════════════════════════════════════════════> │
│ Send: (username, y1, y2, salt) │
│ │
│ ↓
│ ┌─────────┐
│ │ Store │
│ │ in │
│ │Database │
│ └─────────┘
│ │
│ alice: {
│ y1: ...
│ y2: ...
│ salt: ...
│ }
│ │
│ <════════════════════════════════════════════════════│
│ "Registration successful!" │
│ │
KEY POINTS:
━━━━━━━━━━
• Password (secret123) NEVER sent to server ✓
• Secret x NEVER sent to server ✓
• Only public keys y1, y2 are sent ✓
• Even if someone steals y1, y2, they can't find x (hard math problem!)
• Salt makes rainbow table attacks impossible
┌────────────────────────────────────────────────────────────────────────┐
│ AUTHENTICATION PROCESS │
└────────────────────────────────────────────────────────────────────────┘
┌──────────────┐ ┌─────────────────┐
│ CLIENT │ │ SERVER │
│ (Alice) │ │ │
└──────────────┘ └─────────────────┘
│ │
│ 1. User enters password │
│ password = "secret123" │
│ │
│ ══════════════════════════════════════════════════> │
│ "I want to authenticate as alice" │
│ │
│ <══════════════════════════════════════════════════ │
│ "Here's your salt: A7F9...B2C4" │
│ │
↓ │
┌─────────────────────┐ │
│ Re-derive secret x │ │
│ │ │
│ x = SHA256(alice + │ │
│ secret123 + │ │
│ salt) │ │
└─────────────────────┘ │
│ │
│ x = 1234567890... (same as registration!) │
│ │
↓ │
┌─────────────────────┐ │
│ Generate random k │ │
│ k = 9876543210... │ │
└─────────────────────┘ │
│ │
↓ │
┌─────────────────────┐ │
│Compute Commitments │ │
│ │ │
│ a1 = g^k mod p │ │
│ a2 = h^k mod p │ │
└─────────────────────┘ │
│ │
↓ │
┌─────────────────────┐ │
│ Compute Challenge │ │
│ (Fiat-Shamir) │ │
│ │ │
│ c = SHA256(hex(a1) │ │
│ |hex(a2)|hex(y1) │ │
│ |hex(y2)|nonce) │ │
└─────────────────────┘ │
│ │
↓ │
┌─────────────────────┐ │
│ Compute Response │ │
│ │ │
│ s = k - c·x mod q │ │
└─────────────────────┘ │
│ │
↓ │
┌─────────────────────┐ │
│ Get Server Nonce │ │
│ via /challenge │ │
└─────────────────────┘ │
│ │
│ ══════════════════════════════════════════════════> │
│ Send Proof: (a1, a2, s, nonce) │
│ │
│ ↓
│ ┌─────────────────┐
│ │ Fetch from DB │
│ │ alice: { │
│ │ y1, y2, salt │
│ │ } │
│ └─────────────────┘
│ │
│ ↓
│ ┌─────────────────┐
│ │ Validate Nonce │
│ │ unused & fresh │
│ └─────────────────┘
│ │
│ ↓
│ ┌─────────────────┐
│ │Recompute │
│ │Challenge │
│ │c' = SHA256(...) │
│ └─────────────────┘
│ │
│ ↓
│ ┌─────────────────┐
│ │ Verify Equation │
│ │ g^s · y1^c = a1?│
│ │ h^s · y2^c = a2?│
│ └─────────────────┘
│ │
│ ↓
│ ┌─────────────────┐
│ │ Both match! ✓ │
│ │Create Session │
│ │Token │
│ └─────────────────┘
│ │
│ <══════════════════════════════════════════════════ │
│ "Success! Token: 7F3A9C..." │
│ │
WHAT JUST HAPPENED:
━━━━━━━━━━━━━━━━━━
1. Client proved they know x (the secret from password)
2. WITHOUT revealing x to the server
3. Server verified the proof mathematically
4. Server NEVER saw the password or x
5. Proof can't be reused (single-use nonce + unique random k)
This is the magic of Zero-Knowledge! ✨
┌────────────────────────────────────────────────────────────┐
│ EASY TO GO FORWARD, HARD TO REVERSE │
└────────────────────────────────────────────────────────────┘
Forward (Easy):
──────────────
Given: x = 7, g = 5, p = 23
y = g^x mod p
y = 5^7 mod 23
y = 78125 mod 23
y = 17
✓ Takes 1 second to compute
Backward (Hard):
───────────────
Given: y = 17, g = 5, p = 23
Find: x such that 5^x mod 23 = 17
You'd have to try:
5^1 mod 23 = 5 ✗
5^2 mod 23 = 2 ✗
5^3 mod 23 = 10 ✗
5^4 mod 23 = 4 ✗
5^5 mod 23 = 20 ✗
5^6 mod 23 = 8 ✗
5^7 mod 23 = 17 ✓ Found it!
With real numbers (2048 bits):
❌ Would take billions of years!
This is why your secret is safe! 🔒
┌────────────────────────────────────────────────────────────┐
│ WHY WE USE TWO GENERATORS (g and h) │
└────────────────────────────────────────────────────────────┘
One equation alone:
──────────────────
g^s · y1^c = a1
Someone could:
1. Pick random s, c
2. Compute a1 = g^s · y1^c
3. Fake a proof!
Two equations together:
──────────────────────
g^s · y1^c = a1
h^s · y2^c = a2
To fake this, they'd need to find s that satisfies BOTH:
- Works with g and y1
- Works with h and y2
- Where y1 = g^x and y2 = h^x for the SAME x
This is essentially impossible without knowing x!
It's like needing to pick a number that:
✓ Is divisible by 7 when paired with one lock
✓ AND divisible by 11 when paired with another lock
✓ AND both locks were made from the same master key
You can't fake it! 🎯
┌──────────────────────────────────────────────────────────────────────┐
│ COMPLETE SYSTEM ARCHITECTURE │
└──────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────┐
│ CLIENT SIDE │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ ┌──────────────┐ ┌──────────────┐ ┌───────────────┐ │
│ │ CLI Tool │ │ Web Browser │ │ Mobile App │ │
│ │ (Terminal) │ │ (JavaScript)│ │ (Swift/ │ │
│ │ │ │ │ │ Kotlin) │ │
│ └──────┬───────┘ └──────┬───────┘ └───────┬───────┘ │
│ │ │ │ │
│ └────────────────────────┼──────────────────────┘ │
│ │ │
│ ↓ │
│ ┌─────────────────────────┐ │
│ │ ZKP Library │ │
│ │ ───────────────────── │ │
│ │ • Generate parameters │ │
│ │ • Register user │ │
│ │ • Generate proof │ │
│ │ • Never exposes x │ │
│ └─────────────────────────┘ │
│ │ │
└──────────────────────────────────┼───────────────────────────────────┘
│
HTTP/HTTPS │
(JSON) │
↓
┌─────────────────────────────────────────────────────────────────────┐
│ NETWORK LAYER │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ POST /register POST /authenticate GET /verify │
│ ────────────── ─────────────────── ────────── │
│ { { Headers: │
│ username, username, Authorization │
│ password password } │
│ } } │
│ │
└──────────────────────────────────┬────────────────────────────────────┘
│
↓
┌─────────────────────────────────────────────────────────────────────┐
│ SERVER SIDE │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ ┌──────────────────────────────────────────────────────────────┐ │
│ │ HTTP Server (cpp-httplib/Flask/Actix) │ │
│ │ │ │
│ │ • Route requests │ │
│ │ • Handle sessions │ │
│ │ • Return JSON responses │ │
│ └────────┬────────────────────────────────────────┬─────────────┘ │
│ │ │ │
│ ↓ ↓ │
│ ┌─────────────────┐ ┌──────────────────┐ │
│ │ ZKP Verifier │ │ Session Manager │ │
│ │ ───────────── │ │ ─────────────── │ │
│ │ • Verify proof │ │ • Create tokens │ │
│ │ • Check math │ │ • Track expiry │ │
│ │ • Nonce │ │ • Clean old │ │
│ │ validation │ │ sessions │ │
│ └────────┬────────┘ └──────────────────┘ │
│ │ │
│ ↓ │
│ ┌──────────────────────────────────────────────────────────────┐ │
│ │ Database Layer │ │
│ │ │ │
│ │ ┌──────────────────────────────────────────────────────┐ │ │
│ │ │ SQLite Database │ │ │
│ │ │ ──────────────── │ │ │
│ │ │ │ │ │
│ │ │ Table: users │ │ │
│ │ │ ┌──────────┬──────────┬──────────┬──────────┐ │ │ │
│ │ │ │ username │ y1 │ y2 │ salt │ │ │ │
│ │ │ ├──────────┼──────────┼──────────┼──────────┤ │ │ │
│ │ │ │ alice │ 89ABC... │ 12345... │ A7F9... │ │ │ │
│ │ │ │ bob │ DEF01... │ 67890... │ B2C4... │ │ │ │
│ │ │ └──────────┴──────────┴──────────┴──────────┘ │ │ │
│ │ │ │ │ │
│ │ │ ⚠️ NO PASSWORDS STORED! │ │ │
│ │ └──────────────────────────────────────────────────────┘ │ │
│ └──────────────────────────────────────────────────────────────┘ │
│ │
└───────────────────────────────────────────────────────────────────────┘
DATA FLOW:
──────────
1. User enters credentials on client
2. Client derives secret and generates proof
3. Proof sent over HTTPS to server
4. Server verifies proof using stored public keys
5. Server creates session token
6. Client uses token for subsequent requests
┌─────────────────────────────────────────────────────────────────┐
│ CHOOSE YOUR LANGUAGE │
└─────────────────────────────────────────────────────────────────┘
C++ Implementation Python Implementation Rust Implementation
┌───────────────┐ ┌───────────────┐ ┌───────────────┐
│ 🚀 FAST │ │ 🐍 EASY │ │ 🦀 SAFE │
│ │ │ │ │ │
│ • Crypto++ │ │ • sympy │ │ • num-bigint │
│ • httplib │ │ • Flask │ │ • actix-web │
│ • SQLite3 │ │ • requests │ │ • rusqlite │
│ │ │ │ │ │
│ ~500 req/s │ │ ~200 req/s │ │ ~1000 req/s │
│ 20 MB RAM │ │ 50 MB RAM │ │ 15 MB RAM │
│ <1s startup │ │ 30-60s start │ │ 2-5s startup │
└───────────────┘ └───────────────┘ └───────────────┘
│ │ │
└────────────────┬───────────────┴──────────────────────────┘
│
↓
┌──────────────────────┐
│ Same REST API │
│ Same Database │
│ Same Security │
└──────────────────────┘
┌─────────────────────────────────────────────────────────────────────┐
│ WHAT'S PROTECTED? │
└─────────────────────────────────────────────────────────────────────┘
❌ Attack 1: Steal the password during transmission
───────────────────────────────────────────────
Attacker Wire Server
👤 ─────┐ │ 🖥️
│ eavesdrop │
└──────────────┼────────────────────────>
│ (a1, a2, s, t)
What attacker sees: a1, a2, s, t (public proof components)
What attacker DOESN'T see: x (secret) or password
✅ PROTECTED: Password never transmitted!
❌ Attack 2: Steal the database
─────────────────────────
Hacker breaks into server:
💻 ───> 🖥️ ───> 💾
What hacker gets:
┌──────────────────────────┐
│ alice: y1, y2, salt │
│ bob: y1, y2, salt │
└──────────────────────────┘
To get password from y1:
- Must solve discrete logarithm
- With 2048-bit numbers: ~10^34 years
✅ PROTECTED: Public keys are useless without solving impossible math!
❌ Attack 3: Replay old proof
────────────────────────
Attacker records:
Proof from Monday: (a1, a2, s, nonce=ABC...)
Tuesday, attacker sends same proof:
(a1, a2, s, nonce=ABC...)
Server checks nonce store: used or expired?
YES! Reject! ✅
✅ PROTECTED: One-time, short-lived nonce
❌ Attack 4: Brute force the password
──────────────────────────────────
Attacker tries to guess:
x = SHA256("alice" + "password1" + salt)
y1' = g^x mod p
Does y1' == y1? ✗
x = SHA256("alice" + "password2" + salt)
y1' = g^x mod p
Does y1' == y1? ✗
... (repeat 10^20 times)
Problem: Salt is 256 bits (2^256 possibilities)
Time needed: Longer than age of universe
✅ PROTECTED: Salt makes brute force impossible!
❌ Attack 5: Man-in-the-middle
─────────────────────────
Client ──────> Attacker ──────> Server
👤 👹 🖥️
Attacker intercepts and tries to modify proof:
- Changes a1 → a1'
Server verification:
g^s · y1^c = a1'? ✗ (Fails!)
Why? Challenge c is bound to original a1:
c = Hash(a1, a2, y1, y2)
Changing a1 invalidates the proof!
✅ PROTECTED: Cryptographic binding prevents tampering!
┌─────────────────────────────────────────────────────────────┐
│ SECURITY LAYERS │
├─────────────────────────────────────────────────────────────┤
│ │
│ Layer 1: No Password Transmission │
│ ═══════════════════════════════ │
│ Password never leaves client device │
│ │
│ Layer 2: Zero-Knowledge Property │
│ ═════════════════════════════ │
│ Server verifies without learning secret │
│ │
│ Layer 3: Discrete Log Problem │
│ ══════════════════════════ │
│ Can't reverse y = g^x mod p │
│ │
│ Layer 4: Cryptographic Binding │
│ ═══════════════════════════ │
│ Challenge ties proof to commitments │
│ │
│ Layer 5: Nonce Validation │
│ ══════════════════════════ │
│ One-time, short-lived server nonce │
│ │
│ Layer 6: Session Management │
│ ════════════════════════ │
│ Tokens expire after 1 hour │
│ │
│ Layer 7: Salt Randomization │
│ ═══════════════════════ │
│ Each user has unique 256-bit salt │
│ │
│ Combined Security: ~112-bit security level │
│ (Equivalent to AES-112) │
│ │
└─────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────┐
│ HANDS-ON DEMO │
└─────────────────────────────────────────────────────────────────┘
Step 1: Start Server
────────────────────
$ cd python/server
$ python main.py
Output:
┌──────────────────────────────────────┐
│ Initializing ZKP system... │
│ Generating 2048-bit safe primes... │
│ (this may take 30-60 seconds) │
│ Server starting on port 8080... │
│ * Running on http://0.0.0.0:8080/ │
└──────────────────────────────────────┘
Step 2: Register a User
───────────────────────
$ cd python/client
$ python cli_client.py register alice wonderland
Output:
┌──────────────────────────────────────┐
│ Success: User registered successfully│
│ Username: alice │
└──────────────────────────────────────┘
Behind the scenes:
• alice's password "wonderland" → never sent to server ✓
• Secret x computed from password
• Public keys y1, y2 sent to server
• Server stores y1, y2, salt (NO PASSWORD!)
Step 3: Login
─────────────
$ python cli_client.py login alice wonderland
Output:
┌──────────────────────────────────────────────────────┐
│ Success: Authentication successful │
│ Token: 7f3a9c5e8b1d2f4a6c9e0b3d5f8a1c4e6b8d0f2a4c... │
└──────────────────────────────────────────────────────┘
Behind the scenes:
• Password used to generate proof
• Proof sent to server (NOT password!)
• Server verified proof mathematically
• Session token created
Step 4: Verify Token
────────────────────
$ python cli_client.py verify 7f3a9c5e8b1d2f4a6c9e0b3d5f8a1c4e...
Output:
┌──────────────────────────────────────┐
│ Success: Session is valid │
│ Valid: True │
└──────────────────────────────────────┘
Step 5: Try Wrong Password
──────────────────────────
$ python cli_client.py login alice WRONG_PASSWORD
Output:
┌──────────────────────────────────────┐
│ Error: Authentication failed │
└──────────────────────────────────────┘
Why it failed:
• Wrong password → different secret x
• Different x → proof doesn't verify
• Server rejects without knowing actual password!
┌─────────────────────────────────────────────────────────────────┐
│ REMEMBER THESE POINTS │
└─────────────────────────────────────────────────────────────────┘
1. 🔐 PASSWORD NEVER LEAVES YOUR DEVICE
────────────────────────────────────
Your password is used only on your computer to generate a proof.
The proof is what gets sent to the server.
2. 🎩 MATHEMATICAL MAGIC
────────────────────
The server can verify you know the password by checking
equations, without ever seeing the password itself.
3. 🛡️ SAFE EVEN IF DATABASE IS STOLEN
──────────────────────────────────
Database contains only public keys (y1, y2).
These are useless without solving impossible math problems.
4. ⏰ REPLAY ATTACKS PREVENTED
─────────────────────────
Each authentication request uses a one-time, short-lived server nonce.
Proofs are bound to the nonce and cannot be replayed.
5. 🔬 BASED ON HARD MATH
────────────────────
Security relies on the discrete logarithm problem,
which has withstood decades of cryptanalysis.
6. 🌐 THREE IMPLEMENTATIONS
──────────────────────
Choose C++ (fast), Python (easy), or Rust (safe)
All are compatible and share the same database!
7. 📖 OPEN SOURCE & EDUCATIONAL
────────────────────────────
Complete source code, documentation, and theory available.
Perfect for learning cryptography concepts.
- ZKP_THEORY.md - Deep dive into Zero-Knowledge Proofs
- CHAUM_PEDERSEN.md - Mathematical protocol details
- IMPLEMENTATION.md - Code walkthrough with examples
- QUICKSTART.md - Get hands-on in 5 minutes
Questions? Start with the QUICKSTART.md to try it yourself!
Want to understand the math? Read ZKP_THEORY.md
Ready to build? Check implementation guides in cpp/, python/, or rust/