Zero-Knowledge Proofs in Python — Core Concepts

The three required properties

A zero-knowledge proof system must satisfy three conditions:

Completeness. If the statement is true and both parties follow the protocol, the verifier will always accept the proof. An honest prover can always convince an honest verifier.

Soundness. If the statement is false, no cheating prover can convince the verifier (except with negligible probability). You can’t fake a proof for something that isn’t true.

Zero-knowledge. The verifier learns nothing beyond the fact that the statement is true. More formally: anything the verifier could compute from the proof interaction, they could have computed without the proof. The proof conveys truth without information.

Interactive vs non-interactive proofs

Interactive proofs involve a conversation between prover and verifier. The verifier sends random challenges, the prover responds, and after several rounds, the verifier is convinced. The classic example is the color-blind cave problem: a verifier sends a prover through randomly chosen entrances of a cave with a secret door, and the prover consistently emerges from the correct exit.

Non-interactive proofs require no back-and-forth. The prover generates a single proof string that anyone can verify independently. This is essential for practical applications — you can post a proof on a blockchain and thousands of nodes verify it without each one running a separate conversation.

The Fiat-Shamir heuristic converts interactive proofs into non-interactive ones by replacing the verifier’s random challenges with hash function outputs. The prover hashes their own message to generate “challenges” — since hash functions are unpredictable, this mimics a random verifier.

zk-SNARKs: succinct proofs with a trusted setup

zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge) are the most widely deployed ZKP system. Key characteristics:

• Succinct: Proofs are tiny (roughly 200 bytes) regardless of the computation size
• Non-interactive: A single proof string, no conversation needed
• Argument of Knowledge: The prover must actually “know” the secret, not just that a valid one exists

The tradeoff: SNARKs require a trusted setup ceremony. A set of public parameters is generated using secret randomness that must be destroyed afterward. If anyone retains this randomness, they can forge proofs. Systems like Zcash conduct elaborate multi-party ceremonies where even one honest participant ensures security.

Verification is extremely fast — constant time regardless of what’s being proven. This makes SNARKs ideal for blockchain applications where thousands of nodes must verify proofs cheaply.

zk-STARKs: no trusted setup, bigger proofs

zk-STARKs (Scalable Transparent Arguments of Knowledge) eliminate the trusted setup:

• Transparent: No secret parameters or setup ceremony — all randomness is public
• Scalable: Prover time scales quasi-linearly with computation size
• Post-quantum: Based on hash functions rather than elliptic curves, making them resistant to quantum computer attacks

The tradeoff: STARK proofs are larger (tens to hundreds of kilobytes versus hundreds of bytes for SNARKs). Verification is fast but not constant-time — it scales logarithmically with computation size.

StarkWare (now Starknet) uses STARKs for Ethereum layer-2 scaling, processing thousands of transactions and publishing a single proof on-chain.

What you can prove

ZKPs can prove any statement that can be expressed as a mathematical circuit or program:

• Knowledge of a preimage: “I know a value x such that hash(x) = y” — useful for password verification
• Range proofs: “My value is between 18 and 120” — age verification without revealing age
• Membership: “I belong to this group” — anonymous credentials
• Computation integrity: “I correctly executed this program on these inputs” — verifiable computation
• Set operations: “The intersection of our two sets has exactly 5 elements” — private matching

The prover encodes their statement as an arithmetic circuit — a series of addition and multiplication gates over a finite field. The ZKP system then generates a proof that the circuit produces the claimed output for some (hidden) input.

The verification asymmetry

The fundamental value proposition: proving is expensive, verification is cheap. A prover might spend minutes or hours generating a proof for a complex computation, but verification takes milliseconds. This asymmetry enables:

• Blockchain scaling: Prove 10,000 transactions are valid in one proof; every node verifies in milliseconds instead of re-executing all 10,000
• Outsourced computation: A weak device sends a computation to a powerful server and verifies the result is correct without re-running it
• Privacy-preserving compliance: Prove you meet regulatory requirements without exposing the underlying data

Common misconception

“Zero-knowledge proofs are only useful for cryptocurrency.” While blockchain is the highest-profile use case, ZKPs apply anywhere you need to prove something without revealing details — identity verification, supply chain auditing, voting systems, access control, and regulatory compliance. The technology predates Bitcoin by two decades (Goldwasser, Micali, and Rackoff published the concept in 1985).

The one thing to remember: Zero-knowledge proofs separate the truth of a statement from the information behind it, with SNARKs offering tiny proofs at the cost of a trusted setup and STARKs offering transparency at the cost of larger proofs.