Home/Concepts/Blockchain/Zero-Knowledge Proofs

Zero-Knowledge Proofs

Prove knowledge without revealing information interactively

⏱️ 22 min⚡ 24 interactions

What are Zero-Knowledge Proofs?

A zero-knowledge proof (ZKP) lets you prove you know something without revealing what that something is. It's like showing you can open a locked door without showing anyone the key.

💡 Three Properties of ZKPs

✓

Completeness

If true, an honest prover can convince the verifier

🔒

Soundness

A dishonest prover can't fake the proof

🕶️

Zero-Knowledge

The verifier learns nothing except that the statement is true

Interactive Proofs: Building Confidence Through Repetition

🔁 The Challenge-Response Game

In an interactive zero-knowledge proof, the prover and verifier engage in multiple rounds of challenge-response. Each successful round exponentially increases confidence. After n rounds, the probability of faking is only (1/2)ⁿ.

📊 Confidence Mathematics

Successful Rounds	Fake Probability	Confidence Level	Real-World Equivalent
10 rounds	1/1,024 (0.098%)	99.9%	Medical test accuracy
20 rounds	1/1,048,576 (~0.0001%)	99.9999%	Legal evidence standard
30 rounds	1/1,073,741,824	99.9999999%	Cryptographic certainty

✓ Interactive Advantages

•Conceptually simple: Easy to understand and implement

•Flexible: Works for many proof types without setup

•Adaptive security: Can adjust rounds based on risk

✗ Interactive Limitations

•Requires live interaction: Both parties online simultaneously

•Not blockchain-friendly: Multiple rounds = high gas costs

•Proof not transferable: Each verifier needs new session

1. Ali Baba's Cave

🏔️ Interactive: Classic ZKP Analogy

Alice knows the secret password to open a magic door in a cave. She wants to prove this to Bob without revealing the password.

1. Alice Enters (Secret Path)

2. Bob Challenges

Rounds

Success

Confidence

💡 Key Insight: After 0 successful rounds, Bob is 0% confident Alice knows the secret, but he never learned the password!

2. The Color-Blind Friend

🔴🟢 Interactive: Prove Colors Are Different

Your color-blind friend has two balls that look identical to them. You can see one is red, one is green. Prove they're different without revealing which is which.

Test Rounds

Probability of Guessing

1.0000%

3. Password Verification

🔐 Interactive: Prove You Know the Password

Stored Hash (Public)

a1b2c3d4

Commitment Schemes: The Digital Sealed Envelope

📦 Binding + Hiding = Trust Without Revelation

A commitment scheme is like sealing a number in an envelope—you can't change it (binding) and others can't see it (hiding) until you open it. This primitive is foundational to all ZKPs.

🔐 Two Essential Properties

🔒

Binding Property

Once committed, you cannot change your value. Mathematically impossible to find two different values with the same commitment.

Commit(42, salt₁) = 0xa7b3... → Can't later claim you meant 43

🕶️

Hiding Property

Commitment reveals nothing about the value. Even with infinite computing power, you can't guess the committed value.

0xa7b3... → Could be any number (42, 7, 999, etc.)

Hash-Based

Method: Hash(value || salt)

Security: SHA-256 collision resistance

Use: Bitcoin, simple protocols

✓ Fast, widely understood

Pedersen

Method: g^value · h^random

Security: Discrete log problem

Use: Zcash, Monero, advanced ZKPs

✓ Homomorphic properties

Polynomial

Method: Evaluate at secret point

Security: Polynomial hiding

Use: zk-SNARKs, KZG commitments

✓ Succinct proofs

🎯 Real Use Case: Decentralized Auctions

Problem: In traditional online auctions, late bidders can snipe by seeing current highest bid.
Solution: Each bidder commits to their bid → all reveal simultaneously → highest wins.
Result: Fair auction where no one can adjust based on others' bids. Used in ENS domain auctions!

4. Commitment Scheme

📦 Interactive: Sealed Envelope Analogy

Your Secret Number: 42

Range Proofs: Proving Bounds Without Revealing Values

📏 Privacy-Preserving Comparisons

A range proof lets you prove a value lies within a specific range without revealing the exact value. Essential for private transactions and age verification.

🎯 Why Range Proofs Matter

💰 Confidential Transactions

Problem: In Zcash/Monero, hiding transaction amounts is great for privacy, but how do we prevent negative values?
Solution: Range proof proves 0 ≤ amount ≤ 2⁶⁴ without revealing exact amount.
Impact: Prevents money printing while maintaining privacy.

🆔 Age Verification

Problem: Websites need to verify you're 18+ without storing your birthdate.
Solution: Range proof proves age ≥ 18 without revealing if you're 19, 25, or 67.
Impact: Compliance without data collection.

⚙️ Bulletproofs: Efficient Range Proofs

→

No trusted setup: Unlike zk-SNARKs, Bulletproofs don't require ceremony or parameter generation.

→

Logarithmic size: Proof for 64-bit range = only ~700 bytes (vs 32 KB for naive approach).

→

Batch verification: Verify multiple proofs together more efficiently than one-by-one.

Monero adoption: Bulletproofs reduced transaction size by ~80% (from 13 KB to ~2.5 KB) when deployed in 2018, making confidential transactions practical.

🔢 Binary Decomposition Method

To prove value ∈ [0, 2ⁿ-1]:

value = b₀·2⁰ + b₁·2¹ + ... + b₍ₙ₋₁₎·2^n-1

Prove each bit bᵢ is either 0 or 1 using commitments.

Naive size: n commitments (32n bytes for n-bit range)

Bulletproofs: O(log n) size!

📊 Performance Comparison

64-bit Naive:~2 KB

64-bit Bulletproof:~700 bytes

Aggregated (10 proofs):~1.3 KB

Efficiency: 65% smaller + aggregation = near-constant size regardless of proof count!

5. Range Proofs

📊 Interactive: Prove Age Without Revealing It

Your Age: 25

Required Minimum: 21

Non-Interactive Proofs: The Fiat-Shamir Transform

📜 Single-Message Proofs for Blockchains

Non-interactive zero-knowledge proofs (NIZKs) compress the entire challenge-response game into a single message. This makes ZKPs blockchain-ready—post once, verify forever.

🔄 Interactive → Non-Interactive Transformation

❌ Interactive Protocol (Original)

Prover:Sends commitment C

Verifier:Sends random challenge r

Prover:Sends response z

Verifier:Checks if z is valid for C and r

Problem: Requires 3 rounds, both parties online, separate proof for each verifier.

✓ Non-Interactive (Fiat-Shamir)

Prover:Generates commitment C

Prover:Computes challenge r = Hash(C || statement)

Prover:Generates response z for self-created r

Prover:Publishes single proof π = (C, z)

Solution: Single round, offline verification, anyone can verify anytime!

✓ Why This Works

Random Oracle Model: Cryptographic hash behaves like truly random function—prover can't predict Hash(C) before choosing C.

No cheating: Prover can't pick favorable challenge because hash is deterministic and unpredictable.

Public verifiability: Anyone can recompute r = Hash(C || statement) and check response z.

🔗 Blockchain Benefits

→One transaction: Post proof once, not multiple challenge-response rounds.

→Gas efficient: Single verification vs multiple interactive calls.

→Permanent record: Proof stored on-chain, verifiable forever.

→Parallel verification: Thousands of nodes verify simultaneously.

🎯 Real Example: Zcash Transaction

Interactive (impossible): Alice wants to send private tx → Would need 20+ rounds with every full node → Thousands of interactions → Network gridlock.
Non-interactive (Fiat-Shamir): Alice generates single zk-SNARK proof π locally → Posts tx + proof → All nodes verify independently in parallel → 200 bytes, ~5ms verification.
Result: Privacy at scale. This is why Zcash works!

6. ZKP Protocol Steps

🔄 Interactive: How ZKPs Work

1. Witness

Prover has secret knowledge (witness) they want to prove without revealing.

7. Traditional vs ZKP

⚖️ Interactive: Compare Methods

Data Revealed:All Sensitive Info

Trust Required:High

Privacy:Low

Risk:Data Breach Exposure

Verifiable Computation: Outsource with Trust

☁️ The Cloud Computing Revolution

Verifiable computation lets you outsource expensive calculations to untrusted servers while maintaining cryptographic proof of correctness. This is the foundation of ZK-Rollups.

🔄 The Problem: Trust vs Performance Trade-off

❌ Traditional Cloud Computing

Scenario: You have sensitive data (X, Y) and want to compute F(X, Y) = Z.
Problem: Your phone/device is too slow. Cloud server is fast but you must:

1. Send X and Y to server (privacy leak)

2. Trust server computed correctly (no verification)

3. Trust server didn't tamper with result

Risk: Malicious server can steal data, return wrong answer, or charge for work not done.

✓ ZKP Verifiable Computation

Solution: Server computes F(X, Y) and generates ZK proof π.
Benefits:

Privacy: Server never sees X or Y (encrypted inputs)

Correctness: Proof π guarantees result Z is correct

Efficiency: Verifying π is 1000x faster than recomputing F

Power: Trust math, not servers. This enables trustless cloud computing!

🎯 ZK-Rollups: Real-World Example

The scaling problem: Ethereum can process ~15 tx/s. Computing all txs on-chain = bottleneck.

ZK-Rollup solution:

1. Sequencer processes 10,000 txs off-chain (fast server)

2. Generates single ZK proof: "These 10K txs are all valid"

3. Posts proof to Ethereum (~200 bytes)

4. Ethereum verifies proof in ~5ms (not 10K txs!)

Result: 100-1000x throughput increase. Ethereum security + L1 cost ÷ 10,000.

⚡ Performance Comparison

	Compute	Verify
Direct	10 min	10 min
With ZKP	10 min	500 ms

Key insight: Proof generation is expensive (10 min), but verification is lightning fast (500 ms). Pay once, verify anywhere!

🌍 Emerging Applications Beyond Blockchain

🧬 Private ML Inference

Send encrypted medical data to AI model. Get diagnosis with proof of correct computation. Doctor never sees raw data, patient verifies AI ran correctly.

💰 Financial Audits

Prove your company is solvent (assets > liabilities) without revealing exact balances. Auditor verifies computation without seeing sensitive financial details.

🎮 Anti-Cheat Gaming

Prove your game client computed physics correctly without revealing anti-cheat algorithms. Server verifies proof, cheaters can't reverse-engineer detection.

8. Verifiable Computation

🧮 Interactive: Prove Computation Without Showing Inputs

Input A (Secret): 5

Input B (Secret): 7

Computation: A × B

9. Real-World Applications

🌍 Interactive: ZKPs in Production

💰

Zcash Private Transactions

zk-SNARKs

Send cryptocurrency without revealing sender, receiver, or amount

zk-SNARKs vs zk-STARKs: The Great Debate

⚔️ Two Philosophies of Zero-Knowledge

Both technologies prove computation without revealing inputs, but they make different trade-offs. SNARKs optimize for size and speed; STARKs optimize for transparency and post-quantum security.

🔍 The Trusted Setup Problem

⚠️ zk-SNARKs: Ceremony Required

What happens: Generate public parameters using secret randomness (toxic waste).

The risk: If anyone keeps their toxic waste, they can forge proofs and create fake money.

Zcash solution: Multi-party computation (MPC) ceremony with 200+ participants. Only need 1 honest person!

Issue: Trust assumption—must believe at least 1 participant destroyed their secret.

✓ zk-STARKs: Transparent Setup

What happens: Parameters derived from publicly verifiable randomness (e.g., digits of π).

The benefit: No secrets exist, nothing to destroy, no ceremony needed.

StarkWare approach: Anyone can verify parameter generation was done correctly—pure transparency.

Advantage: Zero trust required. Parameters are just hashes of publicly known values.

🔮 Quantum Resistance

⚛️

zk-SNARKs: Vulnerable to Quantum Computers

Why: Based on elliptic curve pairings vulnerable to Shor's algorithm.
Timeline: Practical quantum computers may exist in 10-20 years.
Impact: All existing SNARK proofs could be forged, privacy broken retroactively.

🛡️

zk-STARKs: Quantum-Resistant

Why: Based on collision-resistant hash functions, not number theory.
Security: No known quantum algorithm breaks cryptographic hashes efficiently.
Future-proof: STARKs remain secure even with quantum computers.

📏 Proof Size

SNARK:~200 bytes

STARK:~100-200 KB

Winner: SNARKs (1000x smaller)
Critical for on-chain verification costs.

⚡ Verification Time

SNARK:~5 ms

STARK:~10-100 ms

Winner: SNARKs (10-20x faster)
Important for high-throughput systems.

🔧 Prover Time

SNARK:Minutes

STARK:Seconds

Winner: STARKs (faster proving)
Better for high-frequency applications.

🎯 When to Choose Which?

Choose SNARKs if:

• Need minimal on-chain footprint (~250K gas vs 2-5M)

• Verification speed is critical (<5ms)

• Can conduct trusted ceremony (Zcash style)

• Quantum computers not immediate concern

Examples: Zcash, Tornado Cash, zkSync 1.0

Choose STARKs if:

• Need transparent setup (no trust required)

• Quantum resistance is priority

• Prover efficiency matters (fast proof generation)

• Can handle larger proofs (L2 sequencers)

Examples: StarkNet, Immutable X, Polygon Miden

10. zk-SNARKs vs zk-STARKs

⚔️ Interactive: Technology Comparison

zk-SNARK: Succinct Non-interactive ARgument of Knowledge

Proof Size:Very Small (~200 bytes)

Verification Time:Fast (milliseconds)

Setup Required:Yes (Trusted Setup)

Quantum Resistant:No

Gas Cost:Low (~250k gas)

Used by: Zcash, Tornado Cash, zkSync 1.0, Polygon Hermez

11. Sudoku Zero-Knowledge Proof

🎲 Interactive: Prove Solution Without Revealing

You've solved a Sudoku puzzle. Prove you have the correct solution without showing the numbers!

12. Private Transactions

💸 Interactive: Public vs Private Blockchain Transactions

Transaction Amount: $1,000

📊 Public Blockchain Transaction

From:0x742d...8f3a

To:0x9b1c...2e4d

Amount:$1,000

Balance After:$24,000

⚠️ Visible to everyone: Anyone can see sender, receiver, amount, and track your balance history.

🎯 Key Takeaways

🕶️

Ultimate Privacy

ZKPs enable verification without revealing sensitive data. You can prove statements are true while keeping the underlying information completely private.

🔐

Cryptographic Security

Based on hard mathematical problems. A dishonest prover has negligible chance of creating fake proofs—security backed by computation complexity.

⚡

Blockchain Scaling

ZK-Rollups use SNARKs/STARKs to prove thousands of transactions off-chain, then post a tiny proof on-chain. This enables 100x+ scaling for Ethereum.

💰

Private Transactions

Zcash pioneered private cryptocurrency using zk-SNARKs. Send funds without revealing sender, receiver, or amount—yet fully auditable for compliance.

🆔

Identity & Authentication

Prove you're over 18 without showing your birthday. Verify credentials without revealing unnecessary information. ZKPs enable selective disclosure.

🧮

Verifiable Computation

Outsource heavy computations to untrusted servers. They prove correctness using ZKPs while keeping your input data private. Trust math, not servers.

⚔️

SNARKs vs STARKs

SNARKs: tiny proofs, fast verification, need trusted setup. STARKs: larger proofs, transparent setup, quantum-resistant. Choose based on your needs.

🔮

Future of Privacy

ZKPs are foundational for Web3 privacy. From confidential DeFi to anonymous voting to private machine learning—ZKPs enable trustless verification at scale.