Cryptography
Zero-Knowledge Proofs: Basics
Voting systems face a fundamental tension: voters must prove their vote was counted correctly without revealing how they voted. Zero-knowledge proofs solve this - a voter can prove their encrypted vote is valid (a number between 1 and n_candidates) without decrypting it. Helios, the open-source web voting system used by Princeton student elections and IACR, uses Sigma protocol ZKPs for exactly this.
- **Helios voting**: Sigma protocols for ballot validity proofs. Used by Princeton, IACR, and the association elections of thousands of academic societies.
- **Monero ring signatures**: OR proofs prove a transaction is signed by one of n possible public keys without revealing which. Default since Monero's launch.
- **FIDO2/WebAuthn**: attestation uses Schnorr-like ZKPs to prove knowledge of a private key without transmitting it. Basis of hardware security keys.
- **Signal contact discovery**: ZKPs allow checking if a contact is a Signal user without revealing the full contact list to Signal's server.
Interactive Zero-Knowledge Proofs
A Zero-Knowledge Proof (ZKP) lets a prover convince a verifier that a statement is true without revealing any information beyond the truth of the statement. Three properties: completeness (honest prover convinces verifier), soundness (dishonest prover fails), zero-knowledge (verifier learns nothing extra).
ZKPs satisfy three formal properties: completeness (honest prover always convinces), soundness (cheating prover succeeds with negligible probability), zero-knowledge (verifier learns nothing beyond the statement truth, proven via simulator argument).
What does the zero-knowledge property formally guarantee?
Schnorr Protocol: ZKP of Secret Knowledge
The Schnorr identification protocol (1989) is a ZKP that proves knowledge of a discrete logarithm x (such that X = g^x) without revealing x. It is the canonical example of a Sigma protocol and the basis for Schnorr signatures via Fiat-Shamir.
How does the Schnorr protocol achieve zero-knowledge?
Fiat-Shamir Transform: Non-Interactive ZKPs
The Fiat-Shamir transform converts an interactive Sigma protocol into a non-interactive proof by replacing the verifier random challenge with a hash of the transcript so far. This enables offline proof generation and is the basis for Schnorr signatures and most practical NIZK constructions.
Fiat-Shamir is used in Schnorr signatures (Bitcoin Taproot, Ed25519), Bulletproofs (Monero range proofs), Plonk (zkRollups), and STARK proofs. The security proof requires the random oracle model assumption.
What does the Fiat-Shamir transform change about a Sigma protocol?
Sigma Protocols: A Class of ZKPs
Sigma protocols are three-message interactive proofs: commitment (R), challenge (c), response (s). The Schnorr protocol is the canonical Sigma protocol. Sigma protocols compose: AND proofs prove knowledge of both secrets; OR proofs prove knowledge of at least one secret without revealing which.
OR proofs enable ring signatures (prove membership in a group without revealing which member signed). Monero uses ring signatures for transaction anonymity. CoinJoin and Confidential Transactions use Sigma protocol compositions for private Bitcoin transactions.
What does an OR proof enable that individual proofs cannot?
Key Ideas
- **ZKP properties**: completeness (honest prover convinces), soundness (dishonest prover fails), zero-knowledge (verifier learns nothing beyond truth).
- **Schnorr protocol**: 3-message Sigma protocol for discrete log knowledge. Basis for Schnorr signatures and composable ZK constructions.
- **Fiat-Shamir**: replaces interactive challenge with H(transcript). Converts interactive proof to non-interactive signature. Used in all practical NIZKs.
- **Sigma protocol composition**: AND proofs (shared challenge), OR proofs (simulation technique). Enables ring signatures and private membership proofs.
Related Topics
ZKP basics lead directly to practical privacy-preserving protocols:
- ZK-SNARKs — Groth16 and PLONK extend Sigma protocols to arbitrary NP statements with succinct proofs.
- Schnorr Signatures — Schnorr signatures are exactly the Fiat-Shamir transform applied to the Schnorr identification protocol.
- Blockchain Cryptography — Ring signatures (Monero), Pedersen commitments, and range proofs use Sigma protocol compositions.
Вопросы для размышления
- The Schnorr ZKP simulator picks s and c randomly then computes R = g^s * X^c. Why does this not break soundness?
- An OR proof proves knowledge of x1 OR x2 without revealing which. How would an auditor verify the proof is valid without learning the answer?
- Fiat-Shamir security relies on the random oracle model. What does this mean in practice, and what real attack does it open up in some implementations?