Zero-Knowledge Proofs
Zero-knowledge proofs (ZKPs) allow one party to prove knowledge of a secret without revealing the secret itself—a powerful tool for privacy and scalability in blockchain.
What Are Zero-Knowledge Proofs?
Text
┌─────────────────────────────────────────────────────────────────┐
│ Zero-Knowledge Proof Concept │
├─────────────────────────────────────────────────────────────────┤
│ │
│ PROVER VERIFIER │
│ ┌────────┐ ┌────────┐ │
│ │ Knows │ │ Wants │ │
│ │ Secret │ ─────── Proof ────────▶ │ Proof │ │
│ │ x │ │ of x │ │
│ └────────┘ └────────┘ │
│ │
│ Properties: │
│ 1. COMPLETENESS: Valid proof always accepted │
│ 2. SOUNDNESS: Invalid proof always rejected │
│ 3. ZERO-KNOWLEDGE: Verifier learns nothing about x │
│ │
│ Example: │
│ "I know the password" without revealing the password │
│ │
└─────────────────────────────────────────────────────────────────┘
Classic Example: Ali Baba Cave
Text
┌───────────────────────────────────────────────────────────────────┐
│ Ali Baba Cave Protocol │
├───────────────────────────────────────────────────────────────────┤
│ │
│ ENTRANCE │
│ │ │
│ ┌────┴────┐ │
│ ╱ ╲ │
│ A B │
│ │ │ │
│ │ MAGIC │ │
│ │ DOOR │ │
│ │ ┃ ┃ │ │
│ │ ┃ ┃ │ │
│ └────┴──┴────┘ │
│ │
│ Protocol: │
│ 1. Prover enters cave, goes left (A) or right (B) │
│ 2. Verifier arrives, calls out "Come from A" or "Come from B" │
│ 3. Prover exits from requested side │
│ │
│ If prover knows the magic word: 100% success │
│ If prover doesn't know: 50% success per round │
│ After 20 rounds: 1/2²⁰ ≈ 0.000001% chance of cheating │
│ │
└───────────────────────────────────────────────────────────────────┘
Types of ZKPs
Text
┌───────────────────────────────────────────────────────────────────┐
│ ZKP Classification Tree │
├───────────────────────────────────────────────────────────────────┤
│ │
│ Zero-Knowledge Proofs │
│ │ │
│ ┌────────────────┼────────────────┐ │
│ │ │ │ │
│ Interactive Non-Interactive Transparent │
│ │ │ │ │
│ (Multiple (Single (No trusted │
│ rounds) message) setup) │
│ │ │ │ │
│ ┌────┴────┐ ┌─────┼─────┐ ┌────┴────┐ │
│ │ │ │ │ │ │ │ │
│ Sigma Fiat- SNARK STARK Bullet- STARKs FRI │
│ Proto Shamir │ proofs │
│ │ │ │
│ └──── zk-SNARK ┘ │
│ │ │
│ ┌──────────┼──────────┐ │
│ │ │ │ │
│ Groth16 PLONK Marlin │
│ │
└───────────────────────────────────────────────────────────────────┘
Interactive vs Non-Interactive
TypeScript
// Interactive ZKP: Multiple rounds of communication
interface InteractiveZKP {
// Round 1: Prover sends commitment
commit(): Commitment;
// Round 2: Verifier sends challenge
challenge(): Challenge;
// Round 3: Prover sends response
respond(challenge: Challenge): Response;
// Verifier checks
verify(
commitment: Commitment,
challenge: Challenge,
response: Response,
): boolean;
}
// Schnorr identification protocol example
class SchnorrProtocol {
private g: bigint; // Generator
private p: bigint; // Prime modulus
private x: bigint; // Secret (prover knows this)
public y: bigint; // Public key: y = g^x mod p
constructor(g: bigint, p: bigint, x: bigint) {
this.g = g;
this.p = p;
this.x = x;
this.y = modPow(g, x, p);
}
// Prover: Generate random r, send t = g^r mod p
commit(): { r: bigint; t: bigint } {
const r = randomBigInt(this.p - 1n);
const t = modPow(this.g, r, this.p);
return { r, t };
}
// Verifier: Send random challenge c
challenge(): bigint {
return randomBigInt(this.p - 1n);
}
// Prover: Compute s = r + c*x mod (p-1)
respond(r: bigint, c: bigint): bigint {
return (r + c * this.x) % (this.p - 1n);
}
// Verifier: Check g^s ≡ t * y^c mod p
verify(t: bigint, c: bigint, s: bigint): boolean {
const left = modPow(this.g, s, this.p);
const right = (t * modPow(this.y, c, this.p)) % this.p;
return left === right;
}
}
// Helper functions
function modPow(base: bigint, exp: bigint, mod: bigint): bigint {
let result = 1n;
base = base % mod;
while (exp > 0n) {
if (exp % 2n === 1n) {
result = (result * base) % mod;
}
exp = exp / 2n;
base = (base * base) % mod;
}
return result;
}
function randomBigInt(max: bigint): bigint {
// Simplified - use proper crypto random in production
return BigInt(Math.floor(Math.random() * Number(max)));
}
Fiat-Shamir Transform
TypeScript
// Convert interactive proof to non-interactive
// by replacing verifier's random challenge with hash
import { sha256 } from "@noble/hashes/sha256";
class NonInteractiveSchnorr {
// Fiat-Shamir: Hash the commitment to get challenge
private hashToChallenge(t: bigint, message: Uint8Array): bigint {
const input = new Uint8Array([...bigIntToBytes(t), ...message]);
const hash = sha256(input);
return bytesToBigInt(hash) % (this.p - 1n);
}
// Non-interactive proof (signature)
prove(message: Uint8Array): { t: bigint; s: bigint } {
const r = randomBigInt(this.p - 1n);
const t = modPow(this.g, r, this.p);
// Challenge is hash of commitment + message
const c = this.hashToChallenge(t, message);
const s = (r + c * this.x) % (this.p - 1n);
return { t, s };
}
// Verify non-interactive proof
verifyProof(message: Uint8Array, t: bigint, s: bigint): boolean {
const c = this.hashToChallenge(t, message);
const left = modPow(this.g, s, this.p);
const right = (t * modPow(this.y, c, this.p)) % this.p;
return left === right;
}
}
// This is essentially how Schnorr signatures work!
// Ed25519 is based on a similar scheme
zk-SNARKs
Text
┌─────────────────────────────────────────────────────────────────┐
│ zk-SNARKs │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Zero-Knowledge Succinct Non-interactive ARguments of Knowledge│
│ │
│ Properties: │
│ • SUCCINCT: Small proof size (~200 bytes) │
│ • NON-INTERACTIVE: Single message proof │
│ • ARGUMENT: Computationally sound │
│ • KNOWLEDGE: Prover must "know" the witness │
│ │
│ Process: │
│ │
│ 1. Setup (trusted) │
│ ┌────────────────┐ │
│ │ Circuit │ ──▶ Proving Key (pk) │
│ │ Definition │ ──▶ Verification Key (vk) │
│ └────────────────┘ │
│ │
│ 2. Prove │
│ ┌────────────────┐ │
│ │ Public Input │ │
│ │ Private Witness│ + pk ──▶ Proof (π) │
│ └────────────────┘ │
│ │
│ 3. Verify │
│ ┌────────────────┐ │
│ │ Public Input │ │
│ │ Proof (π) │ + vk ──▶ true/false │
│ └────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────┘
Arithmetic Circuits
TypeScript
// ZKPs typically work with arithmetic circuits over finite fields
// Example: Proving x³ + x + 5 = 35 without revealing x
/*
Circuit representation:
Input: x (private), output: 35 (public)
Constraints (R1CS format):
1. v1 = x * x (v1 = x²)
2. v2 = v1 * x (v2 = x³)
3. v3 = v2 + x + 5 (v3 = x³ + x + 5)
4. v3 == 35 (assertion)
Wire values (witness):
x = 3
v1 = 9
v2 = 27
v3 = 35 ✓
*/
interface R1CSConstraint {
// A * B = C
A: Map<string, bigint>;
B: Map<string, bigint>;
C: Map<string, bigint>;
}
class SimpleCircuit {
constraints: R1CSConstraint[] = [];
witness: Map<string, bigint> = new Map();
// Add multiplication constraint
mul(a: string, b: string, c: string): void {
this.constraints.push({
A: new Map([[a, 1n]]),
B: new Map([[b, 1n]]),
C: new Map([[c, 1n]]),
});
}
// Check if witness satisfies all constraints
verify(): boolean {
for (const constraint of this.constraints) {
let aVal = 0n,
bVal = 0n,
cVal = 0n;
for (const [wire, coeff] of constraint.A) {
aVal += coeff * (this.witness.get(wire) || 0n);
}
for (const [wire, coeff] of constraint.B) {
bVal += coeff * (this.witness.get(wire) || 0n);
}
for (const [wire, coeff] of constraint.C) {
cVal += coeff * (this.witness.get(wire) || 0n);
}
if (aVal * bVal !== cVal) return false;
}
return true;
}
}
// Example circuit for x³ + x + 5 = 35
const circuit = new SimpleCircuit();
circuit.mul("x", "x", "v1"); // x * x = v1
circuit.mul("v1", "x", "v2"); // v1 * x = v2
// Witness: x = 3
circuit.witness.set("x", 3n);
circuit.witness.set("v1", 9n); // 3²
circuit.witness.set("v2", 27n); // 3³
console.log("Valid witness:", circuit.verify()); // true
zk-STARKs
Text
┌─────────────────────────────────────────────────────────────────┐
│ zk-STARKs │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Zero-Knowledge Scalable Transparent ARguments of Knowledge │
│ │
│ Comparison with SNARKs: │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ Property │ SNARK │ STARK │ │
│ ├─────────────────┼─────────────────┼───────────────────┤ │
│ │ Trusted Setup │ Required │ Not Required ✓ │ │
│ │ Proof Size │ ~200 bytes ✓ │ ~50-200 KB │ │
│ │ Verify Time │ ~10ms ✓ │ ~100ms │ │
│ │ Quantum Safe │ No │ Yes ✓ │ │
│ │ Prover Time │ High │ Lower ✓ │ │
│ │ Transparency │ No │ Yes ✓ │ │
│ └─────────────────┴─────────────────┴───────────────────┘ │
│ │
│ Key Innovations: │
│ • Uses hash functions instead of elliptic curves │
│ • AIR (Algebraic Intermediate Representation) │
│ • FRI (Fast Reed-Solomon IOP of Proximity) │
│ │
└─────────────────────────────────────────────────────────────────┘
ZKP Applications in Blockchain
TypeScript
// 1. Private Transactions (like Zcash)
interface PrivateTransaction {
// Public
nullifiers: string[]; // Spent note identifiers
commitments: string[]; // New note commitments
proof: string; // ZK proof
// The proof attests:
// - Sender owns the input notes
// - Sum of inputs >= sum of outputs
// - No double-spending
// WITHOUT revealing amounts or addresses
}
// 2. Rollups (like zkSync, StarkNet)
interface ZKRollupBatch {
// Batch of transactions processed off-chain
previousStateRoot: string;
newStateRoot: string;
transactions: CompressedTx[];
proof: string; // ZK proof of valid state transition
}
// Verifier on L1 only checks the proof
// Much cheaper than executing all transactions
async function verifyRollupBatch(batch: ZKRollupBatch): Promise<boolean> {
// Single proof verification instead of N transaction executions
return verifyProof(
batch.proof,
[batch.previousStateRoot, batch.newStateRoot],
VERIFICATION_KEY,
);
}
// 3. Identity / KYC
interface AgeProof {
// Prove: "I am over 18" without revealing actual age or birthday
commitment: string; // Commitment to identity document
proof: string; // ZK proof that age > 18
}
// 4. Voting
interface PrivateVote {
electionId: string;
nullifier: string; // Prevents double-voting
voteCommitment: string;
proof: string; // Proves voter eligibility without revealing identity
}
ZKPs on Solana
TypeScript
// Solana has limited native ZKP support but growing ecosystem
// 1. Light Protocol - ZK Compression
// Compresses account data using ZK proofs
// 2. Elusiv - Privacy Protocol
// Private transactions using ZK proofs
// 3. Manual verification using compute units
// (Expensive, limited by compute budget)
import { PublicKey, TransactionInstruction } from "@solana/web3.js";
// Example: Groth16 verification (conceptual)
interface Groth16Proof {
a: [bigint, bigint]; // G1 point
b: [[bigint, bigint], [bigint, bigint]]; // G2 point
c: [bigint, bigint]; // G1 point
}
interface VerificationKey {
alpha: [bigint, bigint];
beta: [[bigint, bigint], [bigint, bigint]];
gamma: [[bigint, bigint], [bigint, bigint]];
delta: [[bigint, bigint], [bigint, bigint]];
ic: [bigint, bigint][];
}
// Groth16 verification equation:
// e(A, B) = e(α, β) · e(Σ vk_IC[i] * input[i], γ) · e(C, δ)
// where e is the pairing function
// This is computationally intensive on Solana
// Typically done via specialized programs or precompiles
// Light Protocol example usage
async function compressedTransfer(
connection: Connection,
payer: Keypair,
amount: number,
) {
// Light Protocol handles ZK proof generation
// and compression automatically
// const lightProvider = await LightProvider.init(connection);
// await lightProvider.compressedTransfer(recipient, amount);
}
Bulletproofs
TypeScript
// Range proofs without trusted setup
/*
Bulletproofs: Prove v ∈ [0, 2ⁿ) without revealing v
Use cases:
- Confidential transactions (prove amount is positive)
- Age verification (prove age in valid range)
- Credit score (prove score above threshold)
Properties:
- No trusted setup
- Logarithmic proof size: O(log n)
- Aggregatable: prove multiple values efficiently
*/
interface BulletproofRangeProof {
V: string; // Pedersen commitment to value
A: string; // Vector commitment
S: string; // Vector commitment
T1: string; // Polynomial commitment
T2: string; // Polynomial commitment
tau_x: bigint; // Opening
mu: bigint; // Opening
t_hat: bigint; // Evaluation
L: string[]; // Inner product proof
R: string[]; // Inner product proof
a: bigint; // Final value
b: bigint; // Final value
}
// Conceptual usage
async function provePositiveBalance(
balance: bigint,
): Promise<BulletproofRangeProof> {
// Prove: balance ∈ [0, 2⁶⁴)
// i.e., balance is a valid positive 64-bit number
// In practice, use a library like bulletproofs-js
// return bulletproofs.rangeProof(balance, 64);
throw new Error("Use bulletproofs library");
}
async function verifyPositiveBalance(
commitment: string,
proof: BulletproofRangeProof,
): Promise<boolean> {
// Verify the range proof
// return bulletproofs.verifyRangeProof(commitment, proof, 64);
throw new Error("Use bulletproofs library");
}
Building a Simple ZKP System
TypeScript
// Simplified ZKP for "I know x such that hash(x) = H"
import { sha256 } from "@noble/hashes/sha256";
interface HashPreimageProof {
commitment: Uint8Array; // Random commitment
challenge: Uint8Array; // Hash-based challenge
response: Uint8Array; // Response to challenge
}
class HashPreimageZKP {
// Prover knows preimage x such that H(x) = targetHash
static prove(
preimage: Uint8Array,
targetHash: Uint8Array,
): HashPreimageProof {
// 1. Generate random blinding factor
const r = crypto.getRandomValues(new Uint8Array(32));
// 2. Commit: C = H(H(x) || r)
const commitment = sha256(new Uint8Array([...targetHash, ...r]));
// 3. Challenge (Fiat-Shamir): c = H(C || targetHash)
const challenge = sha256(new Uint8Array([...commitment, ...targetHash]));
// 4. Response: reveal r (simplified - real ZKPs are more complex)
// In a proper system, response would be computed differently
const response = r;
return { commitment, challenge, response };
}
static verify(targetHash: Uint8Array, proof: HashPreimageProof): boolean {
// Recompute commitment
const expectedCommitment = sha256(
new Uint8Array([...targetHash, ...proof.response]),
);
// Check commitment matches
if (!this.arraysEqual(proof.commitment, expectedCommitment)) {
return false;
}
// Check challenge was computed correctly
const expectedChallenge = sha256(
new Uint8Array([...proof.commitment, ...targetHash]),
);
return this.arraysEqual(proof.challenge, expectedChallenge);
}
private static arraysEqual(a: Uint8Array, b: Uint8Array): boolean {
if (a.length !== b.length) return false;
return a.every((val, i) => val === b[i]);
}
}
// Usage
const secret = new TextEncoder().encode("my-secret-password");
const targetHash = sha256(secret);
const proof = HashPreimageZKP.prove(secret, targetHash);
const isValid = HashPreimageZKP.verify(targetHash, proof);
console.log("Proof valid:", isValid);
// Note: This is simplified - doesn't truly hide the secret
// Real ZKPs require more sophisticated mathematics
Key Takeaways
| Concept | Description |
|---|---|
| Zero-Knowledge | Prove statement without revealing the secret |
| SNARKs | Small proofs, fast verify, needs trusted setup |
| STARKs | No trusted setup, quantum-safe, larger proofs |
| Bulletproofs | Range proofs without trusted setup |
| Use Cases | Privacy, scalability (rollups), identity |
| On Solana | Light Protocol, Elusiv, limited native support |
Summary
Text
┌───────────────────────────────────────────────────────────────────┐
│ ZKP Landscape Summary │
├───────────────────────────────────────────────────────────────────┤
│ │
│ "I can prove I know something without showing you what I know" │
│ │
│ Key Trade-offs: │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ SNARK: Small + Fast verification = Trusted setup needed │ │
│ │ STARK: No trust + Quantum safe = Larger proofs │ │
│ │ Bulletproofs: No trust + Log size = Slower verification │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ │
│ Blockchain Applications: │
│ • Private transactions (hide amounts/addresses) │
│ • ZK-Rollups (scalability via proof aggregation) │
│ • Identity (prove attributes without revealing data) │
│ • Voting (private yet verifiable elections) │
│ │
│ The Future: │
│ ZKPs are becoming more efficient and accessible. │
│ Expected to be foundational for Web3 privacy & scaling. │
│ │
└───────────────────────────────────────────────────────────────────┘
Cryptography section complete! Next: Mini Projects - Apply what you've learned.