II Crypto Guide: Cryptographic primitives from scratch 8 Digital signatures 10 Merkle trees and commitments to sets

9 Interactive proofs, zero knowledge, and SNARKs

The adversary of this section wears two faces, one on each side of a conversation. Facing the verifier stands the cheating prover: a party with no witness—no spendable note, no authorisation, no satisfying assignment—who would nevertheless talk the verifier into accepting, and thereby mint value, spend another’s coins, or certify a false computation to a network in which every validator takes the proof’s word for the hidden data. Facing the prover stands the curious verifier: a party who follows the protocol, or deviates from it arbitrarily, in order to squeeze from the interaction more than the single bit it is owed—to distinguish which witness the prover holds, and so unmask the spender, link the transactions, or read the amounts a shielded protocol exists to hide. The two threats pull in opposite directions: defeating the first means the transcript must pin the prover down; defeating the second means the transcript must reveal nothing. That both can be defeated at once—and, more remarkably still, by a proof shorter than the statement it certifies—is the subject of this section, and the reason a private transaction can be checked by millions of verifiers who learn nothing from it but its validity.

9.1 Three questions

Three questions organise everything that follows.

Can a prover convince a sceptical verifier that a statement is true? Not by assertion—the verifier trusts nothing—but by a protocol at whose end the verifier is justified in accepting, because no cheating strategy could have survived it. The answer is the theory of interactive proofs and arguments, refined into proofs of knowledge: protocols after which the verifier is entitled to conclude not merely that a witness exists but that the prover possesses one.

Can the prover convince without revealing why the statement is true? The witness—the factorisation, the colouring, the discrete logarithm, the transcript of the computation—must stay hidden; the verifier must finish the protocol knowing the statement holds and nothing else. The answer is zero knowledge, made precise by the simulation paradigm.

Can the proof be small—dwarfed by the statement it certifies—and cheap to check? A blockchain verifier cannot afford to re-execute every computation it accepts, nor even to read a proof as long as the computation’s description. The answer is the SNARK: the succinct non-interactive argument of knowledge.

The development answers the questions in order and culminates in the architecture underlying the Halo 2 proving system deployed in Orchard: a polynomial interactive oracle proof, compiled into an argument by a polynomial commitment scheme (§4.9) and made non-interactive by the Fiat–Shamir transform. Every earlier section of this volume feeds in: the games and reductions of §1, the discrete logarithm of §2, the random oracle of §3, the commitments of §4, and the Schnorr protocol of §8.4, which will turn out to have been this section’s canonical example all along.

Conventions are those of §1 throughout: $\lambda$ is the security parameter, adversaries are PPT (non-uniform where it matters), and $\operatorname{negl}$ denotes a negligible function. Proof systems introduce one re-indexing: the objects of study are indexed by an instance $x$ rather than by $1^{\lambda}$ , and asymptotic statements are measured in the instance length $\lvert x\rvert$ —for the instances this volume cares about, $\lvert x\rvert$ and $\lambda$ are polynomially related, so the two scales agree up to the polynomial slop the definitions already absorb.

9.2 Languages, relations, and witnesses

What is a “statement”, and what does it mean to hold the “why” of one? The vocabulary is that of languages and relations over bit strings.

Definition 9.1 (Language, relation, witness).

Fix the alphabet $\{0,1\}$ . A language is a set $L\subseteq\{0,1\}^{*}$ . A binary relation is a set $R\subseteq\{0,1\}^{*}\times\{0,1\}^{*}$ of pairs $(x,w)$ , where $x$ is called the instance (or statement) and $w$ a witness for $x$ . The relation induces the language

L_{R}\;:=\;\{\,x\;:\;\exists\,w\text{ with }(x,w)\in R\,\},

and for each instance $x$ the (possibly empty) witness set is $R(x):=\{\,w:(x,w)\in R\,\}$ . The relation $R$ is an NP-relation if it is

1.

polynomially balanced: there is a polynomial $p$ with $\lvert w\rvert\leq p(\lvert x\rvert)$ for every $(x,w)\in R$ ; and
2.

polynomial-time decidable: a deterministic algorithm decides, in time polynomial in $\lvert x\rvert$ , whether a given pair $(x,w)$ belongs to $R$ .

The class $\mathsf{NP}$ is exactly the class of languages induced this way: a language $L$ lies in $\mathsf{NP}$ if and only if $L=L_{R}$ for some NP-relation $R$ . This certificate characterisation of $\mathsf{NP}$ we take from complexity theory without proof; it is the bridge over which every “statement with a short checkable reason” enters the theory. Membership in $L_{R}$ is existentially quantified—some witness exists—while holding an element of $R(x)$ is possession of the reason itself. The gap between the two quantifiers is where this section lives.

Example 9.2 (Three running relations).

Three relations recur through the section, in increasing order of expressive power.

1.

Discrete logarithm. In the setting of §8.4—a cyclic group $\mathbb{G}=\langle G\rangle$ of prime order $q$ , written additively—the relation is

$R_{\mathrm{dl}}\;=\;\bigl{\{}\,(X,x)\in\mathbb{G}\times\mathbb{F}_{q}\;:\;X=[x% ]G\,\bigr{\}}.$

Because $x\mapsto[x]G$ is a bijection $\mathbb{F}_{q}\to\mathbb{G}$ , every instance $X\in\mathbb{G}$ has exactly one witness: the induced language is trivial—all of $\mathbb{G}$ —and membership is vacuous. What is hard, under the DLP assumption of §2.1, is to produce the witness. This is the prototype of why proving membership differs from proving knowledge.
2.

Graph three-colouring. With instances encoding finite graphs $G=(V,E)$ ,

$R_{3\mathrm{col}}\;=\;\bigl{\{}\,(G,c)\;:\;c\colon V\to\{1,2,3\}\text{ and }c(% u)\neq c(v)\text{ for all }\{u,v\}\in E\,\bigr{\}},$

the relation of proper three-colourings. The induced language $L_{3\mathrm{col}}$ is $\mathsf{NP}$ -complete—every $\mathsf{NP}$ language reduces to it in polynomial time, a notion and fact we take from complexity theory without proof—so a zero-knowledge protocol for it yields one for every $\mathsf{NP}$ language by reduction (§9.8).
3.

Circuit satisfiability. With instances encoding circuits,

$R_{\mathrm{sat}}\;=\;\bigl{\{}\,(C,w)\;:\;C\text{ a Boolean (or arithmetic) circuit and }C(w)=1\,\bigr{\}}.$

This is the universal target of practical proof systems: a computation is first arithmetised into the satisfiability of an arithmetic circuit over a finite field $\mathbb{F}$ , and the prover proves knowledge of a satisfying assignment (§9.8).

The discrete-logarithm example already shows that “ $x\in L$ ” is too weak a target for cryptography: every group element is some multiple of $G$ , so a protocol establishing mere membership establishes nothing. The content of the Schnorr protocol is that the prover knows the scalar—and formalising “knows” for an algorithm, an object with no mental states, is the central conceptual move of this section (§9.4).

9.3 Interactive protocols, proofs, and arguments

Definition 9.3 (Interactive protocol).

An interactive protocol is a pair $(P,V)$ of algorithms, the prover and the verifier. Both receive a common input $x$ ; the prover additionally receives a private input $w$ (a witness, or an arbitrary auxiliary string); each party holds its own private random tape. The parties alternate sending messages $a_{1},a_{2},\dots$ over a number of rounds polynomial in $\lvert x\rvert$ ; after the last message the verifier outputs a single bit, written

\langle P(w),V\rangle(x)\;\in\;\{0,1\},

with $1$ for accept—a random variable over both parties’ coins. The transcript of an execution is the full sequence of exchanged messages (together with $x$ , and with the verifier’s coins when relevant). The protocol is public-coin if every message the verifier sends is a fresh uniformly random string that it also reveals—the verifier’s messages are its coins—and its final decision is a deterministic function of the transcript. The verifier is required to run in probabilistic polynomial time, always.

The last clause is the asymmetry on which everything turns. The verifier is the party being protected, so its power is fixed at PPT once and for all: a guarantee that only holds against verifiers with super-polynomial resources would protect nobody. The prover is the party whose power we vary, and that variation is exactly the distinction between proofs and arguments.

Definition 9.4 (Interactive proof and interactive argument).

Let $L\subseteq\{0,1\}^{*}$ be a language, and let $c,s\colon\mathbb{N}\to[0,1]$ . The protocol $(P,V)$ is an interactive proof system for $L$ with completeness error $c$ and soundness error $s$ if:

1.

Completeness. For every $x\in L$ there is a prover input $w$ with

$\Pr\bigl{[}\langle P(w),V\rangle(x)=1\bigr{]}\;\geq\;1-c(\lvert x\rvert).$
2.

Soundness. For every $x\notin L$ and every prover strategy $P^{*}$ —of unbounded computational power, with arbitrary auxiliary input $z$ —

$\Pr\bigl{[}\langle P^{*}(z),V\rangle(x)=1\bigr{]}\;\leq\;s(\lvert x\rvert).$

The soundness clause is a game in the sense of §1.4: the honest verifier is the challenger, the prover strategy is the adversary, and the win condition is an accept on a false instance. The two thresholds must be bounded apart,

c(\lvert x\rvert)+s(\lvert x\rvert)\;\leq\;1-\frac{1}{\operatorname{poly}(% \lvert x\rvert)},

and in the protocols of this volume both errors are negligible (often $c=0$ ). The class of languages admitting such proof systems— with the honest prover unbounded—is $\mathsf{IP}$ . Every protocol this volume constructs is for a language $L=L_{R}$ induced by an NP-relation $R$ , with the honest prover required to run in polynomial time given a witness $w\in R(x)$ as its private input; the unbounded honest prover matters only for the complexity-theoretic statements below.

An interactive argument system (or computationally sound proof) relaxes only the soundness quantifier: the guarantee holds against every PPT cheating prover $P^{*}$ , that is, for $x\notin L$ and PPT $P^{*}$ with arbitrary auxiliary input $z$ , $\Pr[\langle P^{*}(z),V\rangle(x)=1]\leq s(\lvert x\rvert)$ , where $s$ is required to be negligible. Soundness of an argument typically rests on a computational hardness assumption.

Remark 9.5 (Proofs versus arguments: neither dominates).

A proof resists an unbounded cheating prover: its soundness is information-theoretic and unconditional. An argument resists only efficient adversaries, and an unbounded prover can typically break one outright—by breaking the binding of a commitment the protocol relies on (Theorem 4.8 showed perfectly hiding commitments have this exposure), or simply by brute-forcing a discrete logarithm. In exchange, arguments achieve properties provably impossible for proofs, chief among them succinctness: a sound interactive proof for an $\mathsf{NP}$ -complete language whose communication is much smaller than the witness would let an unbounded prover compress $\mathsf{NP}$ certificates below what complexity theory is believed to allow, collapsing classes believed distinct, whereas succinct arguments exist under standard assumptions (§9.8). For cryptographic applications—all of the SNARK literature included—the prover is a real machine with real resource bounds, and the argument notion is exactly right: bounded-prover soundness is the price of succinctness, and its gateway.

Why interaction, and why randomness? Strip both away and see what is left. With a deterministic verifier and a single prover message, the system proves exactly the class $\mathsf{NP}$ : the one message is a certificate, the verifier’s check is the relation’s decision procedure—and there is no hope of zero knowledge, since the certificate is, in spirit, the witness itself, and the verifier could replay the prover’s analysis at leisure. Verifier randomness changes the game: a cheating prover must commit to its messages before knowing the challenge, so a random spot-check catches what a predictable one never would. Interaction lets the verifier probe adaptively, round after round. Together they buy real power: the equality $\mathsf{IP}=\mathsf{PSPACE}$ —interactive proofs capture exactly the languages decidable with polynomial memory and unrestricted running time, a class believed far larger than $\mathsf{NP}$ —is a landmark of complexity theory (Lund, Fortnow, Karloff, and Nisan; Shamir) that we cite without proof. For this section the sharper point is qualitative: interaction and randomness are what make zero knowledge and knowledge extraction possible at all. A single static certificate can be neither hidden nor rewound.

Proposition 9.6 (Soundness amplification by repetition).

Let $(P,V)$ be an interactive proof (or argument) for $L$ with completeness error $c$ and soundness error $s$ , and let $k=k(\lvert x\rvert)$ be polynomially bounded. The protocol that runs $k$ independent instances and accepts only if all $k$ accept has completeness error at most $k\cdot c$ and soundness error at most $s^{k}$ . Sequential repetition achieves this always; parallel repetition achieves it for proofs and, with care, for many arguments. In particular, if $s\leq 1-\delta$ for a noticeable function $\delta$ , then choosing $k$ with $\delta(\lvert x\rvert)\cdot k(\lvert x\rvert)=\omega(\log\lvert x\rvert)$ —always possible with $k$ polynomial—drives the soundness error below every inverse polynomial, so a base protocol needs only a noticeable soundness gap.

Proof.

For completeness, the honest prover fails at least one of the $k$ runs with probability at most $k\cdot c$ by the union bound (Math Guide, §“The union bound and a birthday calculation”). For soundness under sequential repetition, fix $x\notin L$ and any cheating strategy; conditioned on the transcripts of the first $i-1$ runs, the $i$ -th run is an execution against a fresh independently-random verifier, so it accepts with probability at most $s$ whatever state the prover carries forward; multiplying the conditional bounds gives $s^{k}$ . (For parallel repetition of proofs the same bound holds by a more careful argument, which we omit; for arguments parallel repetition can fail to amplify in general, and we use only the sequential form.) Finally $s^{k}\leq(1-\delta)^{k}\leq e^{-\delta k}$ , which is negligible once $\delta k=\omega(\log\lvert x\rvert)$ . □

9.4 Knowledge soundness and extractors

Soundness, as defined, is silent exactly where cryptography speaks. For the relation $R_{\mathrm{dl}}$ every instance $X\in\mathbb{G}$ lies in the induced language, so the soundness clause of Definition 9.4—quantified over $x\notin L$ —holds vacuously: a verifier that always accepts is “sound” for the trivial language. The assurance actually wanted is that a convincing prover possesses the discrete logarithm. But possession is not a property an algorithm wears on its sleeve; the definition reads it operationally. A prover knows a witness if an efficient procedure, granted full control over the prover—the ability to run it, feed it messages, and rewind it to an earlier state to try different continuations—can compute the witness from it. The procedure is called the extractor, and what it extracts is the meaning of “knows”.

Definition 9.7 (Knowledge soundness; proof of knowledge).

Let $(P,V)$ be an interactive protocol and $R$ an NP-relation. The protocol is a proof of knowledge for $R$ with knowledge error $\kappa\colon\mathbb{N}\to[0,1]$ if there exist a probabilistic oracle algorithm $\mathcal{E}$ (the extractor) and a polynomial $q$ such that for every prover strategy $P^{*}$ —possibly cheating, possibly computationally unbounded—and every instance $x$ , writing

\varepsilon(x)\;:=\;\Pr\bigl{[}\langle P^{*},V\rangle(x)=1\bigr{]}

for the probability that $P^{*}$ convinces the honest verifier, the following holds whenever $\varepsilon(x)>\kappa(x)$ : the extractor $\mathcal{E}$ , given $x$ and oracle access to $P^{*}$ with the ability to rewind—to run $P^{*}$ from any point with the same coins, feeding verifier messages of $\mathcal{E}$ ’s choosing—outputs a witness $w\in R(x)$ within expected running time

\frac{q(\lvert x\rvert)}{\varepsilon(x)-\kappa(x)}.

If the guarantee is required only for PPT prover strategies $P^{*}$ , the protocol is an argument of knowledge.

Three consequences can be read straight off the definition. The extraction cost may blow up as $\varepsilon$ approaches $\kappa$ : the bound $q(\lvert x\rvert)/(\varepsilon-\kappa)$ is useful precisely when the prover’s success is noticeably above the knowledge error. A prover succeeding with probability at most $\kappa$ need yield nothing at all— $\kappa$ is the “free” success rate, typically the probability of blind guessing, below which conviction carries no evidence of knowledge. And any prover noticeably above $\kappa$ surrenders the witness: whatever code and coins produce conviction can be mined, efficiently, for the very object the conviction asserts. Knowledge is thereby defined as efficient computability relative to the prover’s own code and coins—an algorithm knows what can be efficiently computed from it. Note the expected-time clause: extractors are the standing reason this volume’s adversary class admits expected polynomial time (Remark 1.4).

Remark 9.8 (The rewinding justification).

No live counterparty could rewind the prover, and none ever does: the extractor is a thought experiment, never executed during an honest run of the protocol. It exists to give the security claim its meaning—and, in security proofs, its teeth. In a reduction the extractor is the reduction: the cheating prover is a subroutine the reduction runs through its input/output interface alone (Definition 1.20), and black-box access already includes choosing the subroutine’s random tape and restarting it from the top with the same coins—so replaying it under different challenges is not science fiction but the ordinary right of a machine over its own subroutines, no reading of its code required. The same device runs in both directions across this section: the simulator of §9.5 rewinds a verifier to fake transcripts without a witness, and the extractor rewinds a prover to mine real witnesses from conviction. Rewinding is the single most important technical device in the theory.

Proposition 9.9 (Knowledge soundness implies soundness).

A proof of knowledge for $R$ with knowledge error $\kappa$ is an interactive proof for $L_{R}$ with soundness error $s(x)\leq\kappa(x)$ . The converse fails: a protocol can be sound without being a proof of knowledge.

Proof.

Fix $x\notin L_{R}$ , so that $R(x)=\emptyset$ . If some prover strategy $P^{*}$ achieved $\varepsilon(x)>\kappa(x)$ , the extractor run on $P^{*}$ would halt in finite expected time and output some $w\in R(x)$ — impossible, as the witness set is empty. Hence $\varepsilon(x)\leq\kappa(x)$ for every $P^{*}$ , which is the soundness bound. For the failure of the converse: soundness constrains only false instances, so a protocol for a trivial language—such as $R_{\mathrm{dl}}$ ’s, where no false instances exist—is automatically sound however it behaves, while nothing forces a witness to be extractable from it. One may be convinced of a true statement by a prover who does not know why it is true; knowledge soundness is strictly stronger, and it—not mere soundness—is the notion cryptographic applications actually rely on (§9.8). □

9.5 The simulation paradigm and zero knowledge

What should “the verifier learned nothing” mean? The definitional move—often called the most influential idea in modern cryptography—is the simulation paradigm: the verifier learned nothing beyond the truth of the statement if it could have produced, entirely on its own and without ever talking to the prover, a transcript indistinguishable from the real one. Whatever a party can manufacture for itself it did not learn from the conversation; if the whole conversation is reproducible without the witness, the conversation taught nothing about the witness. The three grades of indistinguishability—perfect, statistical, computational—carry over verbatim from §1.2 (Definitions 1.6 and 1.9, with the unbounded-distinguisher bound of Proposition 1.7 and the hierarchy of Proposition 1.10) under one re-indexing: ensembles are indexed by instances $x$ (and auxiliary inputs) rather than by the security parameter alone, and negligibility is measured in $\lvert x\rvert$ .

Definition 9.10 (Zero knowledge).

Let $(P,V)$ be an interactive proof or argument for $L=L_{R}$ . For a verifier strategy $V^{*}$ , an instance $x$ , a witness $w\in R(x)$ , and an auxiliary input $z$ , the view

\mathrm{View}_{V^{*}}\bigl{(}P(w),V^{*}(z)\bigr{)}(x)

is the random variable consisting of $x$ , the random tape of $V^{*}$ , and every message $V^{*}$ receives—everything the verifier sees. The protocol is zero knowledge if there exists a PPT simulator $\mathrm{Sim}$ such that for every $x\in L$ , every witness $w\in R(x)$ , and every auxiliary input $z$ , the ensembles

\bigl{\{}\mathrm{Sim}(x,z)\bigr{\}}\quad\text{and}\quad\bigl{\{}\mathrm{View}_% {V^{*}}\bigl{(}P(w),V^{*}(z)\bigr{)}(x)\bigr{\}}

are indistinguishable; the grade of indistinguishability—perfect, statistical, computational—gives perfect (PZK), statistical (SZK), or computational (CZK) zero knowledge. Two regimes for the quantifier over $V^{*}$ :

1.

Honest-verifier zero knowledge (HVZK): the guarantee is required only for $V^{*}=V$ , the verifier that follows the protocol, with $z$ empty; the simulator must reproduce the distribution of honest-execution transcripts.
2.

Malicious-verifier (auxiliary-input) zero knowledge: the guarantee holds for every PPT verifier strategy $V^{*}$ , deviating arbitrarily, with arbitrary auxiliary input $z$ . Here $\mathrm{Sim}$ may use $V^{*}$ as a subroutine and rewind it, and is permitted expected polynomial running time (Remark 1.4).

Why does the simulator’s existence suffice? The simulator receives $x$ —and $z$ —but not the witness $w$ . If its output is nevertheless indistinguishable from the real view, then the real view carries no efficiently extractable information about $w$ beyond the fact $x\in L$ : any property of $w$ an efficient verifier could compute from the interaction, it could compute equally well from the simulator’s output, which was manufactured without $w$ —otherwise the computation would itself be a distinguisher. The simulator wields a power the prover lacks: it may rewind $V^{*}$ , retrying until the verifier’s challenges happen to align with a transcript preparable without the witness. That power is legitimate for exactly the reason rewinding always is (Remark 9.8): the simulator is the analyst’s tool, holding the verifier as a subroutine, not a participant in any real execution.

The auxiliary input $z$ models the prior knowledge a malicious verifier may bring to the conversation—the history of earlier protocol runs, partial information about the witness, anything. Quantifying over all $z$ is what makes zero knowledge compose: a protocol that is zero knowledge for every auxiliary input remains zero knowledge when run as a subroutine of a larger system, whose surrounding state simply becomes the $z$ of the analysis. Practice therefore adopts the auxiliary-input formulation, and so does this volume.

9.6 Sigma-protocols

The general definitions are now in place, and one protocol shape realises them with remarkable economy: three moves, public coins, and algebra doing all the work. The shape is named for the capital $\Sigma$ its message flow traces on the page.

Definition 9.11 (Sigma-protocol).

Let $R$ be an NP-relation. A Sigma-protocol for $R$ with challenge space $C$ is a three-move public-coin protocol on common input $x$ , the prover holding $w$ with $(x,w)\in R$ :

1.

Commitment. The prover sends a first message $a$ (the commitment, or announcement), computed from $(x,w)$ and fresh randomness.
2.

Challenge. The verifier sends $e\xleftarrow{\$}C$ , uniformly random.
3.

Response. The prover sends $z$ , computed from $(x,w,a,e)$ and its randomness.

The verifier decides by a deterministic predicate $\mathrm{Verify}(x,a,e,z)\in\{0,1\}$ . Three properties are required.

•

Completeness. An honest prover holding $(x,w)\in R$ convinces the honest verifier with probability $1$ .
•

Special soundness. There is a PPT algorithm that, given $x$ and any two accepting transcripts $(a,e,z)$ and $(a,e^{\prime},z^{\prime})$ with the same commitment $a$ but distinct challenges $e\neq e^{\prime}$ , outputs a witness $w\in R(x)$ .
•

Special honest-verifier zero knowledge (sHVZK). There is a PPT simulator that, on input $x$ and any challenge $e\in C$ , outputs a pair $(a,z)$ such that $\mathrm{Verify}(x,a,e,z)=1$ and the triple $(a,e,z)$ is distributed exactly—or statistically, or computationally, close to—a real honest transcript conditioned on the challenge being $e$ . The simulator chooses $a$ after fixing $e$ ; reversing the honest order is what makes simulation possible without $w$ .

Two accepting transcripts sharing a commitment but differing in challenge are called a collision. Special soundness says a collision is a witness: it is the local, two-transcript reformulation of knowledge extraction, and the engine of the theorem that follows.

Theorem 9.12 (Special soundness yields knowledge soundness).

Let $(P,V)$ be a Sigma-protocol for $R$ with challenge space $C$ of size $N:=\lvert C\rvert$ . Then $(P,V)$ is a proof of knowledge for $R$ with knowledge error $\kappa=1/N$ .

Proof.

We construct an extractor establishing the slightly weaker knowledge error $2/N$ , with expected running time $O(1/(\varepsilon-2/N))$ prover invocations whenever the prover’s success probability satisfies $\varepsilon>2/N$ ; the closing paragraph addresses the gap to the optimal $1/N$ .

The prover as a matrix. Fix $x$ and a prover strategy $P^{*}$ ; fold any auxiliary input into its code. The behaviour of $P^{*}$ is a deterministic function of its random tape $\rho$ : fixing $\rho$ fixes the commitment $a(\rho)$ , and then each challenge $e$ determines the response $z(\rho,e)$ . Form the Boolean matrix

H[\rho,e]\;:=\;\begin{cases}1&\text{if }\mathrm{Verify}\bigl{(}x,\,a(\rho),\,e% ,\,z(\rho,e)\bigr{)}=1,\\ 0&\text{otherwise},\end{cases}

with one row per random tape and one column per challenge; then $\varepsilon=\Pr_{\rho,e}[H[\rho,e]=1]$ , and a collision is two $1$ -entries in a single row.

The extractor. Step 1. Run $P^{*}$ with fresh $\rho$ and a uniform challenge $e$ , repeatedly, until an accepting transcript $(a,e,z)$ appears. The number of trials is geometric with success probability $\varepsilon$ , so this costs $1/\varepsilon$ invocations in expectation—the geometric waiting time (Math Guide, §“Beyond finite spaces: countable additivity, limits, and densities”). Step 2. Alternate two kinds of trial: (i) rewind $P^{*}$ to the moment just after it emitted $a$ —the tape $\rho$ stays fixed—and feed one fresh uniform challenge $e^{\prime}\neq e$ ; (ii) make one entirely fresh probe, as in Step 1. If a kind-(i) trial accepts, a collision $(a,e,z),(a,e^{\prime},z^{\prime})$ is in hand: go to Step 3. If a kind-(ii) trial accepts, abandon the current row and continue Step 2 from the new accepting transcript (a fresh phase). Step 3. Apply the special-soundness algorithm of Definition 9.11 to the collision and output the witness.

Analysis. Call a row $\rho$ heavy if its acceptance density $\delta_{\rho}:=\Pr_{e}\bigl{[}H[\rho,e]=1\bigr{]}$ is at least $\varepsilon/2$ . The heavy-row lemma—a Markov-style averaging—states that an accepting entry lies in a heavy row with probability at least $1/2$ : the total accepting mass contributed by light rows is less than $\varepsilon/2$ (each light row contributes less than $\varepsilon/2$ of its own row measure), so conditioned on acceptance the light rows carry less than half the mass. Every phase opens with a fresh accepting transcript distributed exactly as Step 1’s (the opening transcript is either Step 1’s or a kind-(ii) success, both conditioned draws from the accepting entries), so the lemma applies at every phase, not only the first.

Each alternation of Step 2 contains a kind-(ii) trial, which accepts with probability $\varepsilon$ ; the number of alternations in a phase is therefore dominated by a geometric variable with mean $1/\varepsilon$ , and a phase costs $O(1/\varepsilon)$ invocations in expectation. This interleaving is not an optimisation but a necessity: a row whose only accepting challenge is the already-used $e$ —any row with $\delta_{\rho}\leq 1/N$ —contains no collision at all, and an extractor that only rewound would sit in such a row for unbounded expected time. The fresh probes cap every phase.

Now condition on the phase’s row being heavy. A kind-(i) trial draws $e^{\prime}$ uniformly from $C\setminus\{e\}$ and accepts with probability at least

\frac{\delta_{\rho}N-1}{N-1}\;\geq\;\delta_{\rho}-\frac{1}{N}\;\geq\;\frac{% \varepsilon}{2}-\frac{1}{N},

which is positive precisely when $\varepsilon>2/N$ . The phase ends at its first success of either kind, and the chance that this first success is a collision rather than a row-switch is at least

\frac{\varepsilon/2-1/N}{(\varepsilon/2-1/N)+\varepsilon}\;=\;\Omega\!\left(% \frac{\varepsilon-2/N}{\varepsilon}\right).

Un-conditioning costs the heavy-row factor $1/2$ , so each phase yields a collision with probability $\Omega\bigl{(}(\varepsilon-2/N)/\varepsilon\bigr{)}$ , and the number of phases is dominated by a geometric variable with mean $O\bigl{(}\varepsilon/(\varepsilon-2/N)\bigr{)}$ . By Wald’s identity—the expected total is the expected number of phases times the expected cost per phase (Math Guide, same section)—the extractor’s expected number of prover invocations is

O\!\left(\frac{\varepsilon}{\varepsilon-2/N}\right)\cdot O\!\left(\frac{1}{% \varepsilon}\right)\;=\;O\!\left(\frac{1}{\varepsilon-2/N}\right),

of the form $q(\lvert x\rvert)/(\varepsilon-2/N)$ demanded by Definition 9.7 with $\kappa=2/N$ .

Closing the factor of two. The threshold $\delta_{\rho}\geq\varepsilon/2$ defining heaviness is an artefact of this exposition, and it is exactly what costs the extra $1/N$ in the knowledge error. Sharper accounting removes it: Damgård’s refined heavy-row analysis in his Sigma-protocol lecture notes, and, in full generality, the $k$ -special-soundness extractor of Attema, Cramer, and Kohl, which achieves knowledge error exactly $(k-1)/N$ —here $k=2$ , giving the optimal $\kappa=1/N$ that matches the soundness error. We cite these rather than reproduce them; every use in this volume tolerates the factor of two. □

Remark 9.13 (Knowledge error equals soundness error, and how to size the challenge space).

The knowledge error $1/N$ of Theorem 9.12 is no accident of the analysis: an explicit attack meets it. A prover with no witness guesses the challenge in advance: it picks $e^{*}\in C$ , runs the sHVZK simulator on $(x,e^{*})$ to obtain an accepting pair $(a,z)$ —for a protocol such as Schnorr’s the simulator’s algebra works for every instance—and sends $a$ . If the verifier’s challenge happens to equal $e^{*}$ , which occurs with probability exactly $1/N$ , the prepared $z$ is accepted. One challenge is thus always answerable without a witness, so $1/N$ is also the protocol’s soundness error, and Theorem 9.12 says the two coincide. One caveat keeps the lower bound honest: under Definition 9.7 an extractor facing this guessing prover ( $\varepsilon=1/N$ ) is granted expected time $q(\lvert x\rvert)/(1/N-\kappa)$ , so for exponential $N$ a claimed $\kappa$ below $1/N$ is not formally refuted—the definition would hand the extractor a super-polynomial budget, enough to brute-force a witness unaided. The attack does rule out any noticeably smaller $\kappa$ once the extractor is required to run in strict polynomial time and witnesses are genuinely hard to compute: such an extractor, run on this witness-free prover, would otherwise mine a witness from nothing—for $R_{\mathrm{dl}}$ , solving the discrete-logarithm problem itself. To make the error negligible there are two routes: take $C$ exponentially large—for instance $C=\mathbb{F}_{q}$ for a $\lambda$ -bit prime $q$ , so $N=q$ —or repeat a small-challenge protocol $\omega(\log\lambda)$ times (Proposition 9.6). Large challenge spaces are why a single round of Schnorr already has negligible knowledge error, while a protocol with a polynomially small challenge space needs many repetitions.

Multi-round protocols generalise the collision to a tree. The succinct arguments of §9.8 run many challenge rounds, and their extractors need more than two transcripts.

Definition 9.14 (Tree special soundness).

Let $(P,V)$ be a $(2\mu+1)$ -move public-coin protocol for $R$ in which the prover speaks first and the verifier issues $\mu$ uniform challenges from a space $C$ , and let $k_{1},\dots,k_{\mu}$ be positive integers. A $(k_{1},\dots,k_{\mu})$ -tree of accepting transcripts for $x$ is a tree of depth $\mu$ in which every node at level $i$ has $k_{i}$ children labelled by pairwise distinct challenges for round $i$ , every root-to-leaf path carries the prover messages of one accepting transcript, and transcripts passing through a common node share their prefix up to that node. The protocol is $(k_{1},\dots,k_{\mu})$ -special-sound if a PPT algorithm computes a witness $w\in R(x)$ from any such tree. A Sigma-protocol is the case $\mu=1$ , $k_{1}=2$ .

Extraction generalises phase by phase: under the hypotheses of a tree-extraction theorem—the Attema–Cramer–Kohl analysis cited in the proof of Theorem 9.12 is the general form—rewinding the prover round by round assembles the required tree of $\prod_{i}k_{i}$ accepting transcripts: the protocol is a proof of knowledge with knowledge error growing from $1/\lvert C\rvert$ to the order of $\bigl{(}\sum_{i}(k_{i}-1)\bigr{)}/\lvert C\rvert$ , and with extraction cost polynomial provided the tree size $\prod_{i}k_{i}$ is. Both degradations are benign in the regime the compiled protocols of this section occupy: $C$ exponentially large, $\mu$ logarithmically bounded, and the $k_{i}$ constant, so the error stays negligible and $\prod_{i}k_{i}$ polynomial. This is the notion under which the inner-product argument’s extractor operates (Proposition 4.39): each of the $\log_{2}d$ folding rounds contributes one level of branching to the tree, three accepting children at every node. Each round’s accepting relation is linear in three unknown parent terms with coefficients that are powers of the challenge, so three suitably distinct challenges make that system invertible. The Halo 2 Guide carries out that extraction for the deployed protocol, whose IPA normalisation involves each round’s challenge through the coefficients $u^{-1}$ , $1$ , $u$ : the extractor accordingly needs pairwise distinct nonzero challenges at every node—a negligible-fraction exclusion absorbed into the knowledge error—and not the pairwise distinct squares ( $u\neq\pm u^{\prime}$ ) that the alternative $u^{-2},1,u^{2}$ normalisation would demand.

Proposition 9.15 (sHVZK implies HVZK).

A Sigma-protocol satisfying special honest-verifier zero knowledge is honest-verifier zero knowledge in the sense of Definition 9.10, with the same grade (perfect, statistical, or computational).

Proof.

The honest view is a triple $(a,e,z)$ in which $e$ is uniform on $C$ . The HVZK simulator draws $e\xleftarrow{\$}C$ itself, invokes the sHVZK simulator on $(x,e)$ to obtain $(a,z)$ , and outputs $(a,e,z)$ . For each fixed $e$ , the simulated pair $(a,z)$ is distributed as a real run conditioned on that challenge—exactly, or up to the stated grade of closeness—and the simulator’s $e$ has the same uniform marginal as the honest verifier’s; averaging the conditional distributions over uniform $e$ therefore reproduces the honest view, with any statistical or computational slack preserved under the averaging. □

Example 9.16 (Schnorr: the canonical Sigma-protocol).

The Schnorr identification protocol of §8.4 is a Sigma-protocol for the discrete-logarithm relation $R_{\mathrm{dl}}$ of Example 9.2, and the properties proved there, self-contained, are exactly the clauses of Definition 9.11. The commitment is $R=[r]G$ ; the challenge is a uniform $c\in\mathbb{F}_{q}$ ; the response is $s=r+cx$ ; the predicate is $[s]G=R+[c]X$ . Perfect completeness is Proposition 8.7; $2$ -special soundness is Theorem 8.8, whose collision algebra yields the witness $x=(s-s^{\prime})(c-c^{\prime})^{-1}$ ; special HVZK is Theorem 8.10, whose simulator samples $s$ and solves $R=[s]G-[c]X$ —choosing the commitment after the challenge, as the definition prescribes. The challenge space is $\mathbb{F}_{q}$ , so $N=q$ and the knowledge error $1/q$ is negligible in a single round (Remark 9.13). By Theorem 9.12 and Proposition 9.15, Schnorr’s protocol is a perfect-HVZK proof of knowledge of a discrete logarithm.

Remark 9.17 (From honest to malicious verifiers: three remedies).

Sigma-protocols are honest-verifier zero knowledge only. A malicious $V^{*}$ may choose $e$ as a function of the commitment $a$ , and the sHVZK simulator—which fixes $e$ before producing $a$ —does not obviously cope: nothing lets it predict which challenge the verifier’s function will return for a commitment it has yet to manufacture. Three standard remedies close the gap. (1) Guess and rewind, for small challenge spaces: the simulator guesses $e^{*}\xleftarrow{\$}C$ , runs the sHVZK simulator on $(x,e^{*})$ , and feeds the resulting $a$ to $V^{*}$ ; if the verifier’s challenge equals $e^{*}$ , the round is simulated, and otherwise the simulator rewinds $V^{*}$ and guesses afresh. The honest prover fixes $a$ before any challenge exists, so the simulated $a$ carries (almost) no information about the guess and each attempt succeeds with probability close to $1/N$ : for polynomially large $N$ the expected $O(N)$ attempts stay polynomial, and sequential repetition of the small-challenge protocol—simulated round by round, the auxiliary input carrying the history—is full malicious-verifier zero knowledge, at the price of many rounds. For exponentially large $N$ the guess never lands, and repetition does not generically upgrade honest-verifier to malicious-verifier zero knowledge. (2) Challenge commitment: the verifier commits to $e$ before seeing $a$ (a coin-tossing step using the commitments of §4), so $e$ cannot depend on $a$ ; under the additional conditions such a compiler imposes for simulation, the simulator rewinds past the opening. (3) The Fiat–Shamir transform: remove the verifier’s choice altogether by deriving $e$ from a hash of the transcript—under the hypotheses of Theorem 9.20, in the programmable random oracle model, the resulting non-interactive protocol is zero knowledge against all verifiers, since there is no live challenge left to skew. For the SNARK pipeline route (3) is the one that matters, and honest-verifier zero knowledge is exactly the property the transform requires. It is next.

9.7 The Fiat–Shamir transform: from interactive to non-interactive

In a public-coin protocol the verifier contributes nothing but fresh randomness: its messages are coin tosses, its decision a deterministic function of the transcript (Definition 9.3). Every such message can therefore be replaced by a value that anyone can compute—a hash of everything sent so far—and the interaction collapses into a single proof string, verifiable by recomputing the hashes. The prover no longer talks to a live, possibly malicious verifier but to a fixed public function, which is why honest-verifier zero knowledge upgrades to full non-interactive zero knowledge. The cost is that the hash must be idealised: the analysis lives in the random oracle model, with $H\colon\{0,1\}^{*}\to C$ a random oracle whose range is the challenge space (Definition 8.15), and it exploits both powers established in Proposition 3.14: observability—the reduction sees every query the adversary makes—and programmability—the reduction may fix the oracle’s output at a freshly queried point to any value, provided answers stay consistent and uniformly distributed.

Definition 9.18 (The Fiat–Shamir transform).

Let $(P,V)$ be a public-coin protocol for $R$ with challenge space $C$ , and let $H$ be a random oracle with range $C$ . The Fiat–Shamir transform $\mathrm{FS}[(P,V),H]$ is the non-interactive system defined, in the Sigma case, by:

•

Prover. Compute the commitment $a$ as in $(P,V)$ ; set $e:=H(x,a)$ ; compute the response $z$ ; output the proof $\pi:=(a,z)$ (equivalently $(a,e,z)$ ).
•

Verifier. Given $x$ and $\pi=(a,z)$ , recompute $e:=H(x,a)$ and accept iff $\mathrm{Verify}(x,a,e,z)=1$ .

A multi-round public-coin protocol applies the rule per round: the $i$ -th challenge is

e_{i}\;:=\;H(x,\,a_{1},\,e_{1},\,\dots,\,a_{i}),

each challenge hashing the entire transcript prefix. To bind a message $m$ to the proof—turning it into a signature—one includes $m$ in the hash: $e:=H(x,a,m)$ .

Remark 9.19 (The pitfall: weak Fiat–Shamir).

The definition’s insistence that each challenge hash all prior messages, the instance $x$ included, is load-bearing, and omitting any part of it has broken deployed systems. Hashing $e:=H(a)$ without $x$ —“weak Fiat–Shamir”—lets an attacker fix $(a,e,z)$ first and choose the instance afterwards, searching for an $x$ that the frozen challenge happens to validate: the interactive protocol’s soundness quantified over provers who commit before the challenge, and an unhashed $x$ re-opens exactly that order of quantifiers, yielding proofs of false statements. In multi-round protocols, hashing only the latest message rather than the running prefix breaks soundness the same way, one round at a time. The maxim: the challenge must be a hash of everything the verifier would have seen up to the moment it speaks.

Theorem 9.20 (Fiat–Shamir security in the ROM).

Let $(P,V)$ be a Sigma-protocol for $R$ with challenge space $C$ of size $N$ , special soundness, and special HVZK; assume further that, conditioned on $(x,e)$ , the first message output by the sHVZK simulator has min-entropy $\omega(\log\lambda)$ (min-entropy $H_{\infty}$ : Definition 6.23). In the random oracle model, $\Pi=\mathrm{FS}[(P,V),H]$ is a non-interactive argument for $R$ that is:

1.

perfectly complete, inheriting the protocol’s completeness;
2.

knowledge sound: from any PPT prover $P^{*}$ that makes at most $Q$ random-oracle queries and outputs an accepting proof for $x$ with probability $\varepsilon$ , an extractor obtains a witness $w\in R(x)$ with probability at least $\varepsilon\bigl{(}\varepsilon/Q-1/N\bigr{)}$ up to constant factors—non-negligible whenever $\varepsilon$ is non-negligible and $N$ is super-polynomial; and
3.

non-interactive zero knowledge: a PPT simulator that controls the random oracle produces, without the witness, proofs indistinguishable from real ones—for all verifiers, including malicious ones.

Proof.

Completeness. The honest prover computes $e=H(x,a)$ and an honest response; the verifier recomputes the very same $e$ from the same inputs and runs the same predicate, so the protocol’s probability- $1$ completeness transfers verbatim.

Zero knowledge, by programming. The simulator, on input $x$ , draws $e\xleftarrow{\$}C$ , runs the sHVZK simulator on $(x,e)$ to obtain an accepting pair $(a,z)$ , and then programs the oracle:

H(x,a)\;:=\;e.

Programming fails only if $(x,a)$ was queried before this moment; by hypothesis the simulated first message has, conditioned on $(x,e)$ , min-entropy $\omega(\log\lambda)$ , so a given prior query collides with $a$ with probability $2^{-H_{\infty}(a)}$ , and a union bound over the adversary’s prior queries makes the failure probability negligible. Conditioned on no failure, the programmed answer is a fresh uniform value—exactly what an unprogrammed oracle would have returned—so the oracle’s joint distribution is untouched, and by sHVZK the output $(a,z)$ is distributed as a real proof. The programming is invisible to every verifier, and there is no live challenge for a malicious verifier to skew: its malice is moot, and honest-verifier simulation delivers full non-interactive zero knowledge.

Knowledge soundness, by forking. Let $P^{*}$ output an accepting proof $(a,z)$ for $x$ with probability $\varepsilon$ . With overwhelming probability a successful $P^{*}$ actually queried $H$ at $(x,a)$ : otherwise the challenge $e=H(x,a)$ used by the verifier is a uniform value the prover never saw, and the proof verifies with probability at most $1/N$ . Say the critical query is the $j$ -th of the at most $Q$ queries. The extractor runs $P^{*}$ once, recording the transcript of oracle answers and the index $j$ of the critical query; it then rewinds $P^{*}$ to just before the $j$ -th query and re-runs it with the same coins, answering the first $j-1$ queries identically—so the commitment $a$ is unchanged—and the $j$ -th and subsequent queries with fresh uniform values, the $j$ -th being $e^{\prime}\xleftarrow{\$}C$ . This is precisely the experiment of the general forking lemma (Theorem 8.17, with $h=N$ ): if $P^{*}$ succeeds with probability $\varepsilon$ over $Q$ query slots, then with probability at least $\varepsilon(\varepsilon/Q-1/N)$ both runs succeed at the same index and $e\neq e^{\prime}$ . Conditioned on that event, the two runs yield accepting transcripts $(a,e,z)$ and $(a,e^{\prime},z^{\prime})$ with a common commitment and distinct challenges—a collision—and the special-soundness algorithm of Definition 9.11 outputs $w\in R(x)$ . □

Remark 9.21 (Caveats, and the refinements SNARKs need).

The random oracle is an idealisation: a real hash function is fixed, public, and not random, and there exist contrived protocols secure in the ROM yet insecure under every concrete instantiation. The transform is nonetheless trusted in practice, with the working stance of Remark 1.29, and it underlies essentially every deployed non-interactive proof and signature—Fiat–Shamir-compiled SNARKs included. Two refinements matter for the compiled arguments of §9.8. First, Theorem 9.20 covers the one-challenge Sigma case only, and does not by itself prove security for a multi-round protocol such as Halo 2’s: there the extractor must fork the transcript at each round, its success probability degrading with the round count and with the protocol’s soundness structure, and special soundness must generalise to tree special soundness (Definition 9.14)—a separate multi-round theorem, whose hypotheses must match the protocol at hand. Second, when the underlying interactive protocol is itself only computationally sound—an argument—the ROM extraction layers on top of the computational soundness reduction rather than replacing it. There is also a gap between proofs that merely observe the oracle and proofs that program it (the non-programmable ROM is strictly weaker as a proof technique); deployed systems adopt the programmable model—the zero-knowledge clause above, which programs the oracle outright, already shows why—and an analysis must state which programmable-oracle (and, where used, algebraic) model it works in.

Example 9.22 (Schnorr signatures, recovered).

Applying Definition 9.18 to Schnorr’s Sigma-protocol (Example 9.16) with a message $m$ folded into the challenge hash yields, symbol for symbol, the Schnorr signature scheme of Construction 8.12; and its EUF-CMA security in the ROM (Theorem 8.18) is established by exactly the forking argument in the proof of Theorem 9.20, augmented with a signing-oracle simulation. The signatures section proved the instance; this section supplies the general statement it instantiates. The slogan: proof of knowledge + Fiat–Shamir = signature.

9.8 SNARKs: succinct non-interactive arguments of knowledge

The Sigma-protocol paradigm reaches all of $\mathsf{NP}$ : a commit–challenge–reveal proof of knowledge for the $\mathsf{NP}$ -complete relation $R_{3\mathrm{col}}$ of Example 9.2—zero knowledge under one-way functions alone, a result of Goldreich, Micali, and Wigderson taken without proof—extends to every $\mathsf{NP}$ language by reduction. The generic reduction is hopelessly inefficient, however, its proofs polynomially longer than the computation they certify, so practical systems abandon it and arithmetise the computation directly.

A blockchain verifier operates under constraints the classical theory never contemplated. It cannot interact—a transaction is broadcast once and verified by parties who will never speak to its author, years later, from a proof string sitting in a block. It cannot afford to re-execute—every full node checks every proof, so verification must cost less than the computation being certified, by orders of magnitude. And it must resist a prover with every incentive to cheat: an accepting proof is money. The object meeting all three constraints at once is the SNARK.

Definition 9.23 (Non-interactive argument).

A non-interactive argument for an NP-relation $R$ is a triple of PPT algorithms:

•

$\mathrm{Setup}(1^{\lambda},R)\to srs$ , producing a structured reference string—the public parameters. In the random oracle model all three algorithms additionally access one globally sampled oracle; the oracle is not part of the $s r s$ —a PPT setup cannot output an infinite object—though public parameters may be derived through it. A setup holding no secret trapdoor is transparent: no secret is ever held, so none must be trusted to have been discarded (Remark 4.3).
•

$\mathrm{Prove}(srs,x,w)\to\pi$ , for $(x,w)\in R$ .
•

$\mathrm{Verify}(srs,x,\pi)\to\{0,1\}$ .

The system is complete if honestly generated proofs always verify. A preprocessing argument lets $\mathrm{Setup}$ depend on the circuit or relation and output, alongside the proving parameters, a short verification key, amortising the verifier’s per-statement work across all statements of that shape.

Definition 9.24 (SNARK).

A succinct non-interactive argument of knowledge (SNARK) for an NP-relation $R$ is a non-interactive argument that is additionally:

1.

Knowledge sound. For every PPT prover $P^{*}$ there is a PPT extractor $\mathcal{E}$ —in the ROM, observing $P^{*}$ ’s oracle queries and rewinding or forking it—such that, on the same setup,

$\Pr\bigl{[}\mathrm{Verify}(srs,x,\pi)=1\;\wedge\;(x,\mathcal{E}^{P^{*}})\notin R% \bigr{]}\;\leq\;\operatorname{negl}(\lambda),$

the probability over the setup and both algorithms’ coins: an accepting proof implies an extractable witness, except with negligible probability.
2.

Succinct. The proof size $\lvert\pi\rvert$ and the verifier’s running time are sublinear in the size of the computation proved—typically $\lvert\pi\rvert=O(\operatorname{poly}(\lambda))$ or $O(\operatorname{poly}(\lambda)\log\lvert C\rvert)$ , and verification $O(\operatorname{poly}(\lambda)\log\lvert C\rvert)$ for a circuit $C$ , independent of, or polylogarithmic in, the witness and circuit sizes. (Some of the literature reserves “succinct” for polylogarithmic proofs; the constant-size proofs of pairing-based schemes are the strongest form.)

With zero knowledge—the non-interactive, ROM form of Definition 9.10, as delivered in the Sigma case by Theorem 9.20, clause 3—it is a zk-SNARK.

Remark 9.25 (Why these systems are arguments).

The “AR” in SNARK is earned by necessity, not by preference. Remark 9.5 showed that a succinct proof for an $\mathsf{NP}$ -complete language is essentially ruled out: a transcript shorter than the witness cannot information-theoretically pin the witness down, and an unbounded prover could otherwise compress certificates below what complexity theory is believed to allow. Succinct arguments escape because a computationally bounded prover cannot find a convincing-but-false short proof even though one may exist—succinctness and computational soundness arise together, by necessity. The constructions below realise the necessity at a specific spot: their polynomial commitments are binding only against efficient adversaries, under cryptographic assumptions, and an unbounded prover could equivocate on a commitment and defeat extraction. It is at that commitment layer that the information-theoretic core turns into an argument.

What does knowledge soundness buy an application? Consider a private transaction whose statement reads: there exists a note I am authorised to spend, and input and output values balance. Plain soundness guarantees only that some satisfying witness exists—and for such existential statements about a large anonymity set, witnesses exist in abundance: other people’s notes satisfy the existential quantifier perfectly well. Soundness alone would not prevent a prover holding no spendable note from proving the existential statement, should she somehow come by a proof. Knowledge soundness closes the gap: whoever produced the accepting proof actually holds a concrete witness—a real spendable note, a real authorisation—that the extractor could recover from her. The application may then act—release funds, grant access—exactly as though the witness had been presented in the clear, while it stays hidden. Soundness protects against false statements; knowledge soundness protects against provers who do not know what they claim. Almost every cryptographic use, and certainly every monetary one, requires the latter (Proposition 9.9).

The pairing-based route

The first SNARKs to reach deployment, and the ones the deployed Sapling protocol still uses, verify with a bilinear pairing.

Definition 9.26 (Bilinear pairing).

Let $\mathbb{G}_{1},\mathbb{G}_{2},\mathbb{G}_{T}$ be cyclic groups of prime order $r$ , the first two written additively with generators $G$ and $\hat{G}$ . A bilinear pairing is a map $e\colon\mathbb{G}_{1}\times\mathbb{G}_{2}\to\mathbb{G}_{T}$ that is

1.

bilinear: $e([a]P,[b]Q)=e(P,Q)^{ab}$ for all $P\in\mathbb{G}_{1}$ , $Q\in\mathbb{G}_{2}$ , and $a,b\in\mathbb{F}_{r}$ ;
2.

non-degenerate: $e(G,\hat{G})\neq 1$ , so that $e(G,\hat{G})$ generates $\mathbb{G}_{T}$ ; and
3.

efficiently computable.

Bilinearity lets a verifier test one multiplication of hidden scalars—whether $c=ab$ , given $[a]G$ , $[b]\hat{G}$ , and $[c]G$ —without learning any of them (Example 2.9); the KZG check of Construction 4.35 is such a test. The groups come from pairing-friendly elliptic curves, chosen with a small embedding degree (the quantity of Definition 2.24, there required large) so that $\mathbb{G}_{T}$ lives in a manageable extension field; the curve of the deployed Sapling protocol is BLS12-381, a Barreto–Lynn–Scott curve of embedding degree twelve (protocol specification § 5.4.9.2). The deployed system treats the pairing as a black box, and so does this volume.

The lineage is short. The BCTV14 family (Ben-Sasson, Chiesa, Tromer, and Virza) is a preprocessing argument in the sense of Definition 9.23: the setup encodes one fixed arithmetic circuit into a structured reference string of group elements, the prover’s work is a handful of multiscalar multiplications over that string, and the proof is a constant number of group elements—eight, in the deployed encoding (protocol specification § 5.4.10.1)—checked by a constant number of pairing equations, whatever the circuit’s size. Groth’s refinement (Groth16) cuts the proof to three group elements, $\pi_{A},\pi_{C}\in\mathbb{G}_{1}$ and $\pi_{B}\in\mathbb{G}_{2}$ , and verification to a single pairing-product equation: three pairings— $\pi_{A}$ against $\pi_{B}$ , $\pi_{C}$ against a fixed verification-key element, and a public-input-weighted combination of verification-key elements against another—compared with one pairing precomputed once per circuit. Deployed Zcash uses Groth16 over BLS12-381 for every Sapling spend and output proof (protocol specification § 5.4.10.2; proofs produced and verified by the bellman crate’s groth16 module, consumed through the zcash_proofs crate). PLONK, the third generation, is the recipe of Theorem 9.28 below with the KZG scheme of Construction 4.34 as its commitment: the gate-and-permutation arithmetisation Halo 2 also uses, each polynomial opening checked by two pairings, so proof size and verification cost stay constant. Constant-size proofs and constant-time verification, independent of the circuit, are the family’s signature—the strongest form of the succinctness clause of Definition 9.24.

The price is the setup. The reference string is produced from secret scalars—the evaluation point $\tau$ of Construction 4.34 and, in Groth16, further secrets that tie the proof elements to one circuit—which must be destroyed once the parameters are published: they are the toxic waste. Whoever retains them forges accepting proofs of false statements at will, exactly as the trapdoor $\tau$ forges KZG openings (Remark 4.37), and no verifier can tell: knowledge soundness collapses silently. For Groth16 the waste is per circuit—every new statement shape needs a fresh setup—whereas PLONK’s KZG string is universal, one powers-of- $\tau$ string serving every circuit up to a size bound, but a trusted one still. The mitigation is a multiparty ceremony: participants contribute secret randomness in turn, each re-randomising the running parameters and destroying its own share, so that the waste stays unknown as long as one participant was honest. Zcash ran such ceremonies for the parameters of its earlier proof systems—the BCTV14 Sprout circuit and the Groth16 Sapling circuits (protocol specification §§ 5.7–5.8)—and each remains sound only on that one-honest-participant assumption.

The other route through the design space keeps the discrete logarithm and nothing else. The inner-product commitment of Construction 4.38 needs no pairing and no trusted setup—its generators are hashed into existence, with no secret behind them—at the price of logarithmic proofs and a linear-time opening check (Proposition 4.39); it is the road the Halo 2 Guide takes, and the one the rest of this subsection paves.

Polynomial interactive oracle proofs

Modern SNARKs are built in two layers—one information-theoretic, one cryptographic—and the information-theoretic layer speaks the language of polynomials.

Definition 9.27 (Polynomial interactive oracle proof).

Fix a finite field $\mathbb{F}$ . A polynomial interactive oracle proof (Poly-IOP) for a relation $R$ over $\mathbb{F}$ is a public-coin interactive protocol in which, in place of ordinary messages, the prover in each round sends an oracle for a polynomial $p_{i}\in\mathbb{F}[X]$ of some bounded degree; the verifier sends uniformly random field-element challenges, and may query each polynomial oracle at points of its choice, receiving the evaluation $p_{i}(\zeta)$ . After the interaction the verifier accepts or rejects as a function of its challenges and the few evaluations it queried. Completeness and (knowledge) soundness are as for interactive proofs, with the soundness analysis purely algebraic—resting, invariably, on the Schwartz–Zippel lemma: a nonzero polynomial of degree at most $d$ over $\mathbb{F}$ vanishes at a uniformly random point with probability at most $d/\lvert\mathbb{F}\rvert$ (Math Guide, §“The Schwartz–Zippel lemma”). A good Poly-IOP verifier makes only $O(1)$ or $O(\log)$ queries, each a single evaluation.

The oracle is an idealisation—no real prover can hand over an opaque box answering evaluation queries honestly—but a productive one: it isolates the algebra from the cryptography. Soundness of the Poly-IOP layer is unconditional, resting on no assumption beyond the rigidity of low-degree polynomials; the cryptography enters only when the oracles are instantiated.

Arithmetisation is how a computation becomes a Poly-IOP statement. The claim “I know $w$ with $C(w)=1$ ” (the relation $R_{\mathrm{sat}}$ of Example 9.2) is encoded as a small set of polynomial identities over $\mathbb{F}$ that hold if and only if the computation is correct. The computation is first expressed as a constraint system—the customisable PLONKish gate-and-permutation form used by Halo 2—whose satisfaction is equivalent to a handful of polynomials satisfying identities on a chosen evaluation domain, a fixed finite set of points with one point per constraint row. In the PLONKish form, polynomials encoding the wire values $a, b, c$ and fixed selector polynomials $q_{L},q_{R},q_{M},q_{O},q_{C}$ chosen at circuit-definition time must satisfy the gate identity

q_{L}\cdot a\;+\;q_{R}\cdot b\;+\;q_{M}\cdot ab\;+\;q_{O}\cdot c\;+\;q_{C}\;=\;0

at every point of the domain—selectors switching each row among addition, multiplication, and custom behaviours—while a permutation argument enforces the copy constraints wiring one gate’s output to another’s input. One more step turns the on-domain requirement into a spot-checkable one: the identity is demanded only on the domain $H$ , and a polynomial vanishes on all of $H$ exactly when it is divisible by the vanishing polynomial $Z_{H}:=\prod_{h\in H}(X-h)$ (Math Guide, §“Roots and the factor theorem”), so the prover also sends an oracle for the quotient $t$ with

q_{L}\cdot a+q_{R}\cdot b+q_{M}\cdot ab+q_{O}\cdot c+q_{C}\;=\;t\cdot Z_{H}

as an identity of polynomials—one that must now hold at every point of $\mathbb{F}$ . Checking it at a single random point is the Poly-IOP: the verifier queries the oracles at a random $\zeta$ , checks the displayed equation there, and by Schwartz–Zippel a false statement survives with probability at most $d/\lvert\mathbb{F}\rvert$ , with $d$ bounding the degree of either side.

The polynomial commitment scheme is the cryptographic half. The PCS of Definition 4.32 supplies exactly what the idealised oracle promised: a short, binding commitment to a polynomial, with short proofs—verifiable against the commitment alone—that $p(\zeta)=v$ ; evaluation binding forbids two accepted values at one point, and the extractability the definition names is what SNARK compilation consumes: a prover whose evaluation proofs verify must “know” an underlying polynomial. Three instantiations mark out the design space: KZG (Construction 4.34)—pairing-based, constant-size, trusted setup; the inner-product-argument commitment over a single elliptic curve (Construction 4.38)—transparent, no trusted setup, logarithmic-size openings, the choice made by Halo 2; and the hash-based transparent schemes, outside this volume’s deployed path and mentioned only to bound the territory.

Theorem 9.28 (The compilation recipe, informal).

Let $\mathrm{PIOP}$ be a public-coin polynomial IOP for $R$ , complete and knowledge-sound, and let $\mathrm{PC}$ be a polynomial commitment scheme that is correct, evaluation-binding, and extractable. Compile as follows: wherever the prover would send a polynomial oracle $p_{i}$ , it sends $\mathrm{Commit}(p_{i})$ instead; wherever the verifier would query $p_{i}(\zeta)$ , the prover sends the claimed value together with a $\mathrm{PC}$ evaluation proof, which the verifier checks against the commitment. Under compatible composition hypotheses the result is a public-coin interactive argument of knowledge for $R$ , and a suitable multi-round Fiat–Shamir theorem in the ROM (Definition 9.18 gives the transform: every challenge a hash of the entire transcript so far) makes it non-interactive. Its proof is succinct; under the strict Definition 9.24 it is a SNARK only if verification is also sublinear in the proved computation. If, additionally, the Poly-IOP is properly blinded—random masking terms on the prover’s polynomials, hiding commitments (Remark 4.41)—and the corresponding simulation theorem applies, the result is zero knowledge.

Proof sketch: layered extraction and the succinctness account.

Completeness transfers verbatim: honest commitments open to honest evaluations, and the honest Poly-IOP verifier accepts.

Knowledge soundness is layered, one extractor feeding another. Given a successful prover against the compiled argument, the SNARK extractor first invokes $\mathrm{PC}$ extractability on each commitment, recovering actual polynomials $\hat{p}_{i}$ of the right degrees consistent with every evaluation the prover got accepted; this step is where the cryptographic assumption lives, and why the compiled object is an argument—a prover that could equivocate on its commitments would defeat it, and only computational binding rules that out. The extractor then hands the $\hat{p}_{i}$ to the Poly-IOP’s unconditional knowledge extractor, which is sound against any polynomials—in particular the extracted ones—and outputs $w\in R(x)$ ; evaluation binding guarantees the prover could not have answered queries inconsistently with the committed $\hat{p}_{i}$ , so the algebraic soundness analysis applies to the extracted polynomials as run. Fiat–Shamir then converts the public-coin interactive argument to a non-interactive one in the ROM by the multi-round generalisation of Theorem 9.20: challenges become transcript hashes (Remark 9.19 governing what they must absorb), observability and forking supply the rewinding that the layered extractor needs—tree-style, per Definition 9.14—and the honest-verifier zero knowledge of the blinded protocol becomes full non-interactive zero knowledge by oracle programming.

Succinctness is an accounting exercise, and the account is paid entirely by $\mathrm{PC}$ . The proof consists of a constant or logarithmic number of commitments and evaluation proofs—short by construction, sublinear in the circuit, independent of the witness—so the compiled proof is succinct whenever the commitment scheme’s objects are. The verifier is sublinear only when the evaluation checks are themselves succinct, as for KZG’s two pairings; with the inner-product commitment each evaluation check costs $O(d)$ group operations (Proposition 4.39), so the compiled verifier runs in time linear in the circuit while the proof stays succinct. The compiled object therefore satisfies every clause of Definition 9.24 when the $\mathrm{PC}$ openings verify succinctly, and otherwise yields succinct proofs with linear-time verification—the trade Halo 2 accepts and then recovers through batching. □

Remark 9.29 (Halo 2 is the recipe, instantiated).

The proving system deployed in Orchard (protocol specification § 5.4.10.3) instantiates the recipe of Theorem 9.28, and each ingredient can be pointed to in the deployed source. The Poly-IOP is a PLONKish arithmetisation—custom gates declared as polynomial expressions, lookup arguments asserting that witness values lie in a declared table, and a permutation argument enforcing copy constraints. The polynomial commitment is the inner-product-argument scheme over a single elliptic curve, transparent—the generators are derived by hashing to the curve from the fixed domain string Halo2-Parameters, so the setup holds no trapdoor—with logarithmic-size openings. Fiat–Shamir over a concrete hash makes the argument non-interactive: the transcript is a running BLAKE2b state into which every prover message is absorbed, domain-separated by type, and out of which every challenge is squeezed—the entire-prefix discipline of Definition 9.18 enforced by construction.

The linear cost of each IPA opening check (Proposition 4.39) makes the deployed verifier’s work linear in the commitment dimension: Halo 2 has succinct proofs but does not meet the strict sublinear-verifier clause of Definition 9.24, and it is called a zk-SNARK under the broader convention that asks succinctness of the proof alone. The system’s signature innovation—the technique that named Halo—is accumulation: the one expensive step, the $O(d)$ final check of each IPA opening, is deferred and passed along rather than paid inside a circuit, one proof attesting to the verification of another—which is what makes recursive composition possible without a trusted setup. Deployed Zcash does not use recursion: each Orchard proof is verified directly, and what the deployed verifier takes from the Halo idea is the deferral alone, exploited for batching—many proofs’ deferred final checks collapsing into one multiscalar multiplication (consumed for Orchard bundles as described in Remark 4.40). These claims rest on model and composition hypotheses beyond the generic recipe (Remark 9.21).

Three load-bearing ideas from this section carry forward into everything the upper volumes build. Rewinding (Remark 9.8) is the universal device: the same cloning of an algorithm’s state powers the extractor that defines knowledge and the simulator that defines zero knowledge. The layered split of Theorem 9.28—an unconditionally sound information-theoretic core, wrapped in a cryptographically enforced commitment layer—is the architecture of every modern proof system, and the right frame for auditing one: algebraic bugs and cryptographic bugs live in different layers. And knowledge soundness, not mere soundness, is what an application stakes its security on: a shielded protocol does not care that a spendable note exists; it cares that the prover has one.