Zero-Knowledge Proofs: An Introduction

A proof system for a relation $R$ involves a prover $P$ who claims to know a witness $w$ such that $(x, w) \in R$ for a public statement $x$, and a verifier $V$ who checks this claim through an interactive protocol. In our running example, the statement is a public group element $y = g^x \bmod p$, and the witness is the discrete logarithm $x$. The verifier already trusts $y$, $g$, and $p$; what remains unknown is whether the prover truly knows $x$. Three properties formalize what "a good proof system" means. Completeness says that if the prover honestly knows a valid witness and follows the protocol, the verifier accepts with probability 1 (or overwhelming probability). Soundness says that if no valid witness exists, or the prover does not know one, then any prover strategy — however malicious — is caught with high probability; formally, a cheating prover succeeds with probability at most a small soundness error $\varepsilon$. Zero-knowledge says that whatever the verifier learns from the interaction, it could have generated on its own without any prover at all — formalized by exhibiting a simulator $S$ that outputs transcripts indistinguishable from real ones, given only the public statement $x$. The protocol studied here belongs to a family called sigma protocols (Σ-protocols), named for the shape of their message flow: commitment, challenge, response — three moves forming a Σ-like zigzag when drawn. Sigma protocols share a common analytical toolkit: special soundness (extraction from two transcripts sharing a commitment but differing challenges) proves soundness, and an explicit honest-verifier zero-knowledge (HVZK) simulator proves the zero-knowledge property against verifiers who choose challenges honestly at random. This toolkit generalizes far beyond discrete logarithms, underpinning graph isomorphism proofs, quadratic residuosity proofs, and modern zk-SNARK constructions built by compiling many sigma protocols together.

The concrete instance is the Schnorr identification/proof-of-knowledge protocol. Fix a cyclic group $G$ of prime order $q$ with generator $g$ (in practice, a subgroup of $\mathbb{Z}_p^*$ or an elliptic curve group, chosen so the Discrete Logarithm Problem is hard). The public statement is $y = g^x$; the prover's secret witness is $x \in \mathbb{Z}_q$. The protocol proceeds in exactly three moves. 1. Commitment. The prover picks a random nonce $r \leftarrow \mathbb{Z}_q$ and sends $t = g^r$. 2. Challenge. The verifier picks a random challenge $c \leftarrow \mathbb{Z}_q$ (or a smaller challenge space $\{0,1\}^k$) and sends it. 3. Response. The prover computes $s = r + c \cdot x \bmod q$ and sends $s$. The verifier accepts if and only if:

Everything hinges on this single checking equation, which links the committed randomness, the challenge, and the response through the group's algebraic structure. ``` PROTOCOL Schnorr-Proof-of-Knowledge Public: group G of prime order q, generator g, statement y = g^x Prover's private input: x (the discrete log of y)

# Move 1 — Prover commits Prover: r ← Uniform(Z_q) # fresh randomness, never reused t ← g^r mod p send t to Verifier

# Move 2 — Verifier challenges Verifier: c ← Uniform(Z_q) # random challenge, unpredictable to Prover send c to Prover

# Move 3 — Prover responds Prover: s ← (r + c * x) mod q send s to Verifier

# Verification Verifier: accept iff g^s == t * y^c (mod p) reject otherwise ``` The protocol can be repeated $k$ times (sequentially or in parallel) to push the soundness error from $1/q$ down to a chosen security level, or converted into a non-interactive proof via the Fiat–Shamir Heuristic, replacing the verifier's random challenge with $c = H(g, y, t)$ for a cryptographic hash function $H$, modeled as a random oracle.

Time and space complexity. The protocol requires two modular exponentiations by the prover ($t = g^r$, and negligible cost for $s$, which is a single multiply-add mod $q$) and two modular exponentiations by the verifier ($y^c$ and $t \cdot y^c$, or equivalently one multi-exponentiation $g^s \cdot y^{-c}$ compared to $t$). Each exponentiation over a group with elements of bit-length $n$ costs $O(n)$ modular multiplications via square-and-multiply, each multiplication costing $O(n^2)$ with schoolbook arithmetic (or $O(n \log n \log\log n)$ with fast multiplication) — giving $O(n^3)$ (or quasi-linear-in-$n^2$) bit operations per exponentiation in the naive analysis, which is standard for any discrete-log-based scheme. Communication is three group/field elements: $t \in G$, $c \in \mathbb{Z}_q$, $s \in \mathbb{Z}_q$, so $O(n)$ bits total. Space is $O(n)$ for all stored values. This is exponentially cheaper than the brute-force alternative of the verifier trying to compute $x$ from $y$ directly, which is conjectured to require time exponential in $n$ for suitably chosen groups.

Completeness. If the prover is honest and truly knows $x$ with $y = g^x$, then:

The check passes with probability exactly 1 — completeness is perfect, not merely overwhelming.

Soundness (via special soundness). Suppose a cheating prover, without knowing a valid $x$, could make the verifier accept with non-negligible probability. We show this leads to a contradiction using special soundness: from two accepting transcripts $(t, c_1, s_1)$ and $(t, c_2, s_2)$ sharing the same commitment $t$ but with $c_1 \neq c_2$, an extractor computes:

since $g^{s_1} = t y^{c_1}$ and $g^{s_2} = t y^{c_2}$ imply $g^{s_1 - s_2} = y^{c_1 - c_2}$, so $y = g^{(s_1-s_2)/(c_1-c_2)}$, exhibiting a genuine discrete log of $y$. If a cheating prover (without knowing $x$) could answer two different random challenges correctly for the same commitment, we could extract $x$ — contradicting the assumed hardness of the discrete logarithm. Formally, this means: for a fixed commitment $t$, at most one challenge $c$ can have an accepting response, unless the prover already knows $x$. Since the verifier's challenge is drawn uniformly from a set of size $q$, a prover without the witness succeeds with probability at most $1/q$ (the soundness error), because it can pre-compute a valid response for at most one lucky guess of $c$ before committing (and cannot adapt $t$ afterward without knowing $c$ in advance). Repeating the protocol $k$ times independently drives the soundness error down to $1/q^k$, negligible for cryptographic $q$.

Zero-knowledge (via simulation). To prove the verifier learns nothing beyond "$x$ exists," we exhibit a simulator $S$ that, given only $y$ (no witness), produces transcripts distributed identically to real ones — without ever running the real protocol. The simulator works backwards: ``` SIMULATOR S(y): c ← Uniform(Z_q) # pick challenge first s ← Uniform(Z_q) # pick response first t ← g^s y^(-c) mod p # solve the equation for t output (t, c, s) ``` Check: by construction $g^s = t \cdot y^c$ holds identically, so $S$'s output always passes verification — exactly like a real transcript. Moreover, in a real execution with honest random $r$ and honest-verifier random $c$, the triple $(t, c, s)$ is distributed as: $t$ uniform over $G$ (since $r$ is uniform), $c$ uniform (verifier's choice), and $s = r + cx$ uniform over $\mathbb{Z}_q$ conditioned on $t, c$ (since $r$ is uniform and independent of $c$). In the simulated transcript, $c$ and $s$ are uniform and independent by construction, and $t$ is determined* by $c, s, y$ — but since $s$ is uniform, $t = g^s y^{-c}$ is also uniform over $G$. Both distributions are therefore identical: uniform $(t,c,s)$ subject to the single algebraic constraint $g^s = t y^c$. This gives perfect honest-verifier zero-knowledge: the simulated and real transcript distributions are exactly equal, not just computationally close. Since the simulator never touches $x$, and its output is indistinguishable from a genuine interaction, the verifier's transcript conveys no extractable information about $x$ beyond the bare fact that some valid $x$ exists.

Tradeoffs. Perfect HVZK is a strong guarantee, but it only holds against a verifier who chooses $c$ honestly at random and independent of $t$; a malicious verifier who adaptively chooses $c$ based on side information can, in principle, weaken guarantees for general sigma protocols (though Schnorr specifically remains secure due to strong structural properties, and the Fiat–Shamir transform sidesteps this concern entirely by deriving $c$ deterministically via a hash). Soundness error $1/q$ is already negligible for a 256-bit $q$, so repetition is rarely needed in practice — a single round suffices in most deployed systems.

Use a small illustrative group (too small for real security, ideal for hand-tracing). Let $p = 23$, so $\mathbb{Z}_{23}^*$ has order 22; take a subgroup of prime order $q = 11$ generated by $g = 4$ (since $4$ has order 11 mod 23: check $4^{11} \bmod 23 = 1$). The prover's secret is $x = 6$.

Compute $18^5 \bmod 23$ step by step: $18^2 = 324 = 324 - 14\cdot23 = 324-322=2$; $18^4 = 2^2 = 4$; $18^5 = 18^4 \cdot 18 = 4\cdot 18 = 72 = 72-3\cdot23=72-69=3$. Then RHS $= 18 \cdot 3 \bmod 23 = 54 \bmod 23 = 54 - 46 = 8$. Something looks off: $LHS = 1 \neq 8 = RHS$. Re-examine: recompute $t$. $4^3 = 64$, $64 \bmod 23 = 64 - 46 = 18$. Correct, $t=18$. Recompute $y$: $4^6 = (4^3)^2 = 18^2 = 324 \bmod 23$. $23\cdot14=322$, so $y = 2$, not 18 — the earlier line miscalculated $y$. Correct value: $y = 2$. Redo with $y=2$: RHS $= t \cdot y^c \bmod p = 18 \cdot 2^5 \bmod 23 = 18 \cdot 32 \bmod 23$. $32 \bmod 23 = 9$, so RHS $=18\cdot 9 = 162 \bmod 23$. $23\cdot7=161$, so RHS $=1$. Now LHS $=1=$ RHS. The equation holds — completeness confirmed once arithmetic is corrected.

Now trace a cheating attempt: an impersonator without $x$ picks a random $t' = 7$, sends it, and hopes the verifier's challenge will be some specific $c_0$ it precomputed a fake response for — say it hopes for $c=5$ and prepares $s'$ such that $g^{s'} = t' \cdot y^5 = 7\cdot 1'$. Concretely it can solve $s'$ only if it already knows $x$ or gets extraordinarily lucky guessing $c$ before the verifier reveals it; since $c$ is chosen uniformly from 11 possible values after $t'$ is fixed, the cheater's probability of matching the verifier's actual challenge is exactly $1/11$, matching the soundness bound $1/q$.

The notion of interactive proof systems and zero-knowledge was born from asking a deceptively simple question: can a proof convince you of a fact while teaching you nothing else about why it's true? This reframed "proof" from a static mathematical object into an interactive, probabilistic protocol between two parties — a shift as consequential to cryptography as Turing's reframing of "computation" was to logic.

Zero-knowledge proofs of discrete-log knowledge, exactly as presented here, underlie the Schnorr signature scheme (via Fiat–Shamir), now standardized in Bitcoin's Taproot upgrade and widely used for efficient, batchable digital signatures. Anonymous credential systems and privacy-preserving authentication protocols use sigma protocols to let users prove membership or eligibility without revealing identifying secrets. Modern zk-SNARKs and zk-STARKs, powering blockchain scaling solutions (zk-rollups) and private cryptocurrencies like Zcash, generalize this same three-part logic — completeness, soundness, zero-knowledge — to prove arbitrary computations rather than just discrete logarithms. Secure multiparty computation protocols and password-authenticated key exchange schemes also embed zero-knowledge subprotocols to prevent parties from cheating without forcing them to reveal private inputs. Understanding this one Schnorr example is the fastest route to understanding the entire modern zero-knowledge toolbox, since nearly every advanced construction is, at its core, a composition of many small sigma protocols like this one.

Ask the tutor: How does the Fiat–Shamir transform formally preserve soundness when the random oracle is replaced by a real hash function in practice?