This section defines interactive proofs and arguments, proofs of knowledge, zero knowledge, Sigma-protocols, the Fiat–Shamir transform, and SNARKs. It proves that special soundness yields knowledge soundness (Theorem 9.13) and that, under a min-entropy condition, the Fiat–Shamir transform of a Sigma-protocol is a knowledge-sound, zero-knowledge non-interactive argument in the random oracle model (Theorem 9.21), and it states the recipe on which the Halo 2 proving system deployed in Orchard is built: 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 (Theorem 9.29).
Soundness requires that no cheating prover make the verifier accept a false statement. Interactive proofs and arguments provide soundness; their refinement, proofs of knowledge, entitles the verifier to conclude that the prover possesses a witness, not merely that one exists, so that a prover holding none—no spendable note, no authorisation, no satisfying assignment—cannot mint value, spend another’s coins, or certify a false computation to validators that accept the proof in place of the hidden data.
Zero knowledge requires that the verifier, whether it follows the protocol or deviates from it arbitrarily, learn nothing beyond the truth of the statement: neither the witness—the factorisation, the colouring, the discrete logarithm, the transcript of the computation—nor what it would reveal, such as the identity of the spender, the links between transactions, or the amounts a shielded protocol hides. The two requirements are in tension, soundness asking that the transcript bind the prover and zero knowledge that it reveal nothing; a single protocol achieves both.
Succinctness requires a proof much shorter than the statement it certifies and cheap to check. The SNARK, the succinct non-interactive argument of knowledge, is knowledge-sound and succinct; a zk-SNARK, a SNARK that is also zero knowledge, has all three properties, so every validator can check a private transaction and learn from it only its validity.
The section draws on 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, its running example.
Conventions are those of §1: λ is the security parameter, adversaries are PPT (non-uniform where it matters), and negl denotes a negligible function. Proof systems are indexed by an instance x rather than by 1 λ , and asymptotic statements are measured in the instance length | x | . For the instances this volume considers, | x | and λ are polynomially related, so the two scales agree up to the polynomial factors the definitions already absorb.
A statement, and the reason for its truth, are formalised as an instance and a witness of a relation over bit strings.
Fix the alphabet { 0, 1 } . A language is a set
| L R := { x : ∃ w with (x, w) ∈ R }, |
and for each instance x the (possibly empty) witness set
is
polynomially balanced: there is a polynomial p with
polynomial-time decidable: a deterministic algorithm decides, in time polynomial in | x | , whether a given pair (x, w) belongs to R .
The class NP is exactly the class of languages induced
this way: a language L lies in NP if and only if
Three relations recur through the section, in increasing order of expressive power.
Discrete logarithm. In the setting of
§8.4—a cyclic group
| R dl = { (X, x) ∈ G × F q : X = [x] G } . |
Because
Graph three-colouring. With instances encoding finite
graphs
| R 3 c o l = { (G, c) : c : V → { 1, 2, 3 } and c (u) ≠ c (v) for all { u, v } ∈ E }, |
the relation of proper three-colourings. The induced language L 3 c o l is NP -complete—every 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 NP language by reduction (§9.8).
Circuit satisfiability. With instances encoding circuits,
| R sat = { (C, w) : C a Boolean (or arithmetic) circuit and C (w) = 1 } . |
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 F , and the prover proves knowledge of a satisfying assignment (§9.8).
The discrete-logarithm example shows that “
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
| ⟨ P (w), V ⟩ (x) ∈ { 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 verifier is the party the protocol protects, so its power is fixed at PPT: a guarantee that holds only for verifiers with super-polynomial resources protects no real verifier. The power of the prover varies, and distinguishes proofs from arguments.
Let
Completeness. For every
| Pr [⟨ P (w), V ⟩ (x) = 1] ≥ 1 − c (| x |) . |
Soundness. For every
| Pr [⟨ P ∗ (z), V ⟩ (x) = 1] ≤ s (| x |) . |
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 (| x |) + s (| x |) ≤ 1 − 1 poly (| x |), |
and in the protocols of this volume both errors are negligible (often
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
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 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 NP -complete language whose communication is much smaller than the witness would let an unbounded prover compress NP certificates below what complexity theory is believed to allow, collapsing classes believed distinct, whereas succinct arguments exist under standard assumptions (§9.8). In cryptographic applications, the SNARK literature included, the prover is resource-bounded, so the argument notion is the appropriate one.
Without interaction and verifier randomness—with a deterministic
verifier and a single prover message—a proof
system proves exactly the class NP : the one message is a
certificate, the verifier’s check is the relation’s decision
procedure, and zero knowledge is impossible, since the certificate is
essentially the witness itself and the verifier can repeat the
prover’s analysis offline. Verifier randomness forces a cheating
prover to commit to its messages before knowing the challenge,
so a random spot-check detects what a predictable one does not.
Interaction lets the verifier probe adaptively, round after round.
Together they add expressive power: the equality
Let (P, V) be an interactive proof (or argument) for L with
completeness error c and soundness error s , and let
For completeness, the honest prover fails at least one of the k
runs with probability at most
For the relation R dl every instance
Let (P, V) be an interactive protocol and R an NP-relation.
The protocol is a proof of knowledge for R with
knowledge error
| ε (x) := Pr [⟨ P ∗, V ⟩ (x) = 1] |
for the probability that P ∗ convinces the honest verifier, the
following holds whenever
| q (| x |) ε (x) − κ (x) . |
If the guarantee is required only for PPT prover strategies P ∗ , the protocol is an argument of knowledge.
The extraction cost may grow without bound as ε approaches κ , so the bound is useful when the prover’s success is noticeably above the knowledge error. A prover succeeding with probability at most κ need yield nothing: the knowledge error is the “free” success rate, typically the probability of blind guessing, below which acceptance carries no evidence of knowledge. Through the expected-time clause, extractors are the reason this volume’s adversary class admits expected polynomial time (Remark 1.4).
A counterparty in a live execution cannot rewind the prover: the extractor is an analytical device, never executed during an honest run of the protocol. 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 requires no reading of its code. The simulator of §9.5 rewinds a verifier in the same way to produce transcripts without a witness.
A proof of knowledge for R with knowledge error κ is an
interactive proof for L R with soundness error
Fix
Under the simulation paradigm, the verifier learned nothing beyond the truth of the statement if it could have produced, without interacting with the prover, a transcript indistinguishable from the real one. The three grades of indistinguishability—perfect, statistical, computational—carry over 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), with ensembles indexed by instances x (and auxiliary inputs) rather than by the security parameter alone, and negligibility measured in | x | .
Let (P, V) be an interactive proof or argument for
| View V ∗ (P (w), V ∗ (z)) (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 Sim such that for every
| { Sim (x, z) } and { View V ∗ (P (w), V ∗ (z)) (x) } |
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 ∗ :
Honest-verifier zero knowledge (HVZK): the guarantee is
required only for
Malicious-verifier (auxiliary-input) zero knowledge: the guarantee holds for every PPT verifier strategy V ∗ , deviating arbitrarily, with arbitrary auxiliary input z . Here Sim may use V ∗ as a subroutine and rewind it, and is permitted expected polynomial running time (Remark 1.4).
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
The auxiliary input z models the prior knowledge a malicious verifier may bring to the interaction—the history of earlier protocol runs, partial information about the witness, or any other string. Quantifying over all z 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 becomes the z of the analysis. Practice and this volume adopt the auxiliary-input formulation.
The simulator of Definition 9.10 receives the instance x :
zero knowledge bounds what the interaction reveals beyond x
and says nothing about what x itself reveals. Let x contain a
public value
Sigma-protocols realise the preceding definitions with three moves and public coins, every property following from algebraic relations among the messages; the name refers to the capital Σ that the message flow traces.
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
Commitment. The prover sends a first message a (the commitment, or announcement), computed from (x, w) and fresh randomness.
Challenge. The verifier sends
Response. The prover sends z , computed from (x, w, a, e) and its randomness.
The verifier decides by a deterministic predicate
Completeness. An honest prover holding
Special soundness. There is a PPT algorithm that, given
x and any two accepting transcripts (a, e, z) and
(a, e ′, z ′) with the same commitment a but
distinct challenges
Special honest-verifier zero knowledge (sHVZK). There
is a PPT simulator that, on input x and any challenge
Two accepting transcripts sharing a commitment but differing in challenge are called a collision. Special soundness says that a witness is efficiently computable from a collision: it is the local, two-transcript reformulation of knowledge extraction, and the basis of the theorem that follows.
Let (P, V) be a Sigma-protocol for R with challenge space
C of size
We construct an extractor establishing the slightly weaker knowledge
error 2 / N , with expected running time
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 ρ : fixing ρ fixes the commitment a (ρ) , and then each challenge e determines the response z (ρ, e) . Form the Boolean matrix
| H [ρ, e] := { 1 if Verify (x, a (ρ), e, z (ρ, e)) = 1, 0 otherwise, |
with one row per random tape and one column per challenge; then
The extractor. Step 1. Run P ∗ with fresh
ρ and a uniform challenge e , repeatedly, until an
accepting transcript (a, e, z) appears. The number of trials is
geometric with success probability ε , so this costs
1 / ε 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 ρ stays fixed—and feed one
fresh uniform challenge
Figure 14 draws the extractor on a run that ends in a collision.
Analysis. Call a row ρ heavy if its acceptance
density
Each alternation of Step 2 contains a kind-(ii) trial, which accepts
with probability ε ; the number of alternations in a
phase is therefore dominated by a geometric variable with mean
1 / ε , and a phase costs O (1 / ε)
invocations in expectation. This interleaving is necessary, not an
optimisation: a row whose only accepting challenge is the
already-used e —any row with
Now condition on the phase’s row being heavy. A kind-(i) trial draws
e ′ uniformly from
| δ ρ N − 1 N − 1 ≥ δ ρ − 1 N ≥ ε 2 − 1 N, |
which is positive precisely when
| ε / 2 − 1 / N (ε / 2 − 1 / N) + ε = Ω (ε − 2 / N ε) . |
Un-conditioning costs the heavy-row factor 1 / 2 , so each phase
yields a collision with probability
| O (ε ε − 2 / N) ⋅ O (1 ε) = O (1 ε − 2 / N), |
of the form
Closing the factor of two. The threshold
The knowledge error 1 / N of Theorem 9.13 is not an
artefact of the analysis: an explicit attack attains it. A prover with no
witness guesses the challenge in advance: it picks
The succinct arguments of §9.8 run many challenge rounds, and their extractors need a tree of transcripts in place of a collision.
Let (P, V) be a
Extraction generalises accordingly: under the hypotheses of a
tree-extraction theorem—the Attema–Cramer–Kohl analysis cited in
the proof of Theorem 9.13 is the general
form—rewinding the prover round by round assembles the required
tree of ∏ i k i accepting transcripts: the protocol is a
proof of knowledge with knowledge error growing from 1 / | C |
to the order of
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).
The honest view is a triple (a, e, z) in which e is uniform
on C . The HVZK simulator draws
The Schnorr identification protocol of
§8.4 is a Sigma-protocol for the
discrete-logarithm relation R dl of
Example 9.2, and the properties proved there,
self-contained, are exactly the clauses of
Definition 9.12. The commitment is
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 directly apply: 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
In a public-coin protocol the verifier’s messages are coin tosses and
its decision a deterministic function of the transcript
(Definition 9.3), so each message can be replaced by
a value that anyone can compute—a hash of everything sent so
far—and the interaction reduces to a single proof string, verifiable
by recomputing the hashes. The hash must be idealised: the analysis
lives in the random oracle model, with
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 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
Verifier. Given x and
A multi-round public-coin protocol applies the rule per round: the i -th challenge is
| e i := H (x, a 1, e 1, ..., 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:
Figure 15 draws a Sigma-protocol beside its transform.
The definition’s insistence that each challenge hash all
prior messages, the instance x included, is essential, and
omitting any part of it has broken deployed systems. Hashing
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 ω (log λ)
(min-entropy H ∞ :
Definition 6.23).
In the random oracle model,
perfectly complete, inheriting the protocol’s completeness;
knowledge sound: from any PPT prover P ∗ that
makes at most Q random-oracle queries and outputs an accepting
proof for x with probability ε , an extractor
obtains a witness
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.
Completeness. The honest prover computes
Zero knowledge, by programming. The simulator, on input
x , draws
| 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 ω (log λ) , so a given prior query collides with a with probability 2 − H ∞ (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. No verifier can detect the programming, and no verifier-chosen challenge exists for a malicious verifier to bias, so its deviation has no effect and honest-verifier simulation yields full non-interactive zero knowledge.
Knowledge soundness, by forking. Let P ∗ output an
accepting proof (a, z) for x with probability
ε . With overwhelming probability a successful
P ∗ actually queried H at (x, a) : otherwise the
challenge
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.21 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.15)—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.
Applying Definition 9.19 to Schnorr’s Sigma-protocol (Example 9.17) 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.21, augmented with a signing-oracle simulation. In general, the Fiat–Shamir transform of a Sigma-protocol proof of knowledge, with the message included in the challenge hash, is a signature scheme.
The Sigma-protocol paradigm reaches all of NP : a commit–challenge–reveal proof of knowledge for the NP -complete relation R 3 c o l of Example 9.2—zero knowledge under one-way functions alone, a result of Goldreich, Micali, and Wigderson taken without proof—extends to every NP language by reduction. The generic reduction is impractical, however: its proofs are polynomially longer than the computation they certify, so practical systems abandon it and arithmetise the computation directly.
A transaction’s proof is a string stored in a block and checked, possibly years later, by every full node, none of which communicates with its author; an accepting proof authorises a transfer of value. The proof system must therefore be non-interactive, short and verifiable at a cost orders of magnitude below that of the computation it certifies, and sound against a prover with every incentive to cheat. The SNARK meets all three constraints.
A non-interactive argument for an NP-relation R is a triple of PPT algorithms:
The system is complete if honestly generated proofs always verify. A preprocessing argument lets 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.
A succinct non-interactive argument of knowledge (SNARK) for an NP-relation R is a non-interactive argument that is additionally:
Knowledge sound. For every PPT prover P ∗ there is a PPT extractor E —in the ROM, observing P ∗ ’s oracle queries and rewinding or forking it—such that, on the same setup,
| Pr [Verify (s r s, x, π) = 1 ∧ (x, E P ∗) ∉ R] ≤ negl (λ), |
the probability over the setup and both algorithms’ coins: an accepting proof implies an extractable witness, except with negligible probability.
Succinct. The proof size | π | and the
verifier’s running time are sublinear in the size of the
computation proved—typically
With zero knowledge—the non-interactive, ROM form of Definition 9.10, as delivered in the Sigma case by Theorem 9.21, clause 3—it is a zk-SNARK.
The “AR” in SNARK, argument, reflects a necessity, not a choice. A succinct proof for an NP -complete language is essentially ruled out (Remark 9.5): a transcript shorter than the witness cannot information-theoretically pin the witness down. Succinct arguments avoid this obstruction because a computationally bounded prover cannot find a convincing-but-false short proof even though one may exist. In the constructions below the computational assumption enters through the polynomial commitments, which are binding only against efficient adversaries, under cryptographic assumptions; an unbounded prover could equivocate on a commitment and defeat extraction.
The statement of a private transaction 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 (Proposition 9.9), and over a large anonymity set such witnesses abound: other people’s notes satisfy the existential quantifier. Soundness alone would therefore not prevent a prover holding no spendable note from proving the statement, should it obtain a proof by some means. Knowledge soundness guarantees that whoever produced the accepting proof holds a concrete witness—a real spendable note, a real authorisation—that the extractor could recover from that prover, so the application may act—release funds, grant access—exactly as though the witness had been presented in the clear, while it stays hidden.
The first SNARKs to reach deployment, and the ones the deployed Sapling protocol still uses, verify with a bilinear pairing.
Let
bilinear:
non-degenerate:
efficiently computable.
Bilinearity lets a verifier test one multiplication of hidden
scalars—whether
The pairing-based lineage has three generations. The BCTV14 family
(Ben-Sasson, Chiesa, Tromer, and Virza) is a preprocessing argument
in the sense of Definition 9.24: 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,
The cost of this family is its setup. The reference string is produced from secret scalars—the evaluation point τ of Construction 4.35 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 τ forges KZG openings (Remark 4.38), and no verifier can distinguish such forgeries from honest proofs, so the failure of knowledge soundness is undetectable. 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- τ string serving every circuit up to a size bound, but still trusted. 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.
A subverted setup costs soundness but need not cost zero knowledge. Bellare, Fuchsbauer, and Scafuro (2016) separate the two against a reference string chosen by the adversary: soundness against such a string cannot coexist with zero knowledge, except for languages whose membership is efficiently decidable, whereas zero knowledge against it, together with ordinary soundness, is attainable. Deployed BCTV14 attains the zero-knowledge half of that combination. The specification’s note on the BCTV14 vulnerability (CVE-2019-7167) records two facts (protocol specification § 5.4.10.1). First, soundness failed independently of the toxic waste: the published parameters contained elements from which anyone holding them could forge proofs, and with them value, until the activation of Sapling (Gabizon, 2019). Second, zero knowledge holds even under subversion of the parameter generation (Bowe, Gabizon, and Green, 2017, Theorem 4.10). A holder of the BCTV14 toxic waste could likewise forge proofs; neither such a holder nor a forger exploiting the published parameters could learn anything about the witnesses of honest proofs.
The other route rests on the discrete logarithm alone. The inner-product commitment of Construction 4.39 needs no pairing and no trusted setup—its generators are derived by hashing, with no secret behind them—at the price of logarithmic proofs and a linear-time opening check (Proposition 4.40); the Halo 2 proving system deployed in Orchard takes this route.
Table 1 lists the three proof systems Zcash has
deployed (protocol specification
§“Zero-Knowledge
Proving System”). The curve of BCTV14 is BN-254, a Barreto–Naehrig
pairing-friendly curve over a 254 -bit prime field
(§ 5.4.9.1);
Halo 2 commits with points of Vesta, the Pasta curve whose scalar field
is the base field of Pallas (Definition 2.25).
The sizes are those of the specification’s encodings. A BCTV14 proof is
seven points of 33 bytes and one of 65
(§ 5.4.10.1),
and a Groth16 proof two points of 48 bytes and one of 96
(§ 5.4.10.2).
One Halo 2 proof covers all n Actions of a transaction in
| system | curve | setup | proof size (bytes) | proves |
|---|---|---|---|---|
| BCTV14 | BN-254 | per circuit, ceremony | 296 = 7 ⋅ 33 + 65 | Sprout, before Sapling |
| Groth16 | BLS12-381 | per circuit, ceremony | 192 = 48 + 96 + 48 | Sapling; Sprout after |
| Halo 2 | Vesta | transparent | 2720 + 2272 n | Orchard |
Modern SNARKs are built in two layers, one information-theoretic and one cryptographic; the information-theoretic layer is formulated in terms of polynomials.
Fix a finite field F . A polynomial interactive oracle
proof (Poly-IOP) for a relation R over 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
The oracle is an idealisation—no real prover can supply an opaque object answering evaluation queries honestly—under which soundness of the Poly-IOP layer is unconditional; the cryptography enters when the oracles are instantiated.
Arithmetisation is how a computation becomes a Poly-IOP
statement. The claim “I know w with
| q L ⋅ a + q R ⋅ b + q M ⋅ a b + q O ⋅ 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. A further step turns the
requirement on the domain into one checkable at a single point: 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
| q L ⋅ a + q R ⋅ b + q M ⋅ a b + q O ⋅ c + q C = t ⋅ Z H |
as an identity of polynomials—one that must now hold at every point of F . Checking it at a single random point is the Poly-IOP: the verifier queries the oracles at a random ζ , checks the displayed equation there, and by Schwartz–Zippel a false statement survives with probability at most d / | F | , with d bounding the degree of either side.
The polynomial commitment scheme is the cryptographic half.
The PCS of Definition 4.33 supplies what the
idealised oracle provided: a short, binding commitment to a
polynomial, with short proofs—verifiable against the commitment
alone—that
Let PIOP be a public-coin polynomial IOP for R , complete and knowledge-sound, and let 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 Commit (p i) instead; wherever the verifier would query p i (ζ) , the prover sends the claimed value together with a 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.19 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.25 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.42)—and the corresponding simulation theorem applies, the result is zero knowledge.
Completeness transfers verbatim: honest commitments open to honest evaluations, and the honest Poly-IOP verifier accepts.
Knowledge soundness is layered: the output of one
extractor is the input of another. Given a successful prover against
the compiled argument, the SNARK extractor first invokes PC
extractability on each commitment, recovering actual
polynomials p ^ i of the right degrees consistent with every
evaluation the prover got accepted; this step is where the
cryptographic assumption enters, 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 p ^ i to the Poly-IOP’s
unconditional knowledge extractor, which is sound against
any polynomials—in particular the extracted ones—and
outputs
Succinctness is a matter of counting, and it depends entirely on 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.40), 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.25 when the PC openings verify succinctly, and otherwise yields succinct proofs with linear-time verification—the trade-off Halo 2 accepts and then offsets through batching. □
The proving system deployed in Orchard (protocol specification § 5.4.10.3) instantiates the recipe of Theorem 9.29. 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.19 enforced by construction.
The linear cost of each IPA opening check (Proposition 4.40) 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.25, and it is called a zk-SNARK under the broader convention that asks succinctness of the proof alone. The system’s characteristic technique, from which Halo takes its name, is accumulation: the one expensive step, the O (d) final check of each IPA opening, is deferred and carried forward rather than performed 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, used for batching—many proofs’ deferred final checks combined into one multiscalar multiplication (consumed for Orchard bundles as described in Remark 4.41). These claims rest on model and composition hypotheses beyond the generic recipe (Remark 9.22).