Theorem 3.5 and Corollary 3.13 proved the inner-product opening knowledge sound for a verifier who draws his challenges: an extractor that runs the prover as a subroutine, rewinds it and feeds it fresh challenges recovers the committed vector or a nontrivial discrete-logarithm relation among the generators, which the hardness of the discrete logarithm on Vesta excludes. The deployed verifier draws nothing; every challenge is a hash of the transcript (§4.3), and Remark 4.12 named the hypotheses under which a compiled argument inherits its layers’ guarantees without fixing them. This section determines what the extractor establishes when every challenge is a hash of the transcript. It combines the rewinding-extractor framework of the Crypto Guide, the definition of knowledge soundness (§“Knowledge soundness and extractors”), the tree extraction of Sigma-protocols (§“Sigma-protocols”) and the Fiat–Shamir theorem with its stated caveats (§“The Fiat–Shamir transform: from interactive to non-interactive”), with the algebraic group model, named among the idealisations of §“The standard model and the random oracle model”. It lifts the interactive extractor to the non-interactive argument in two layers and names the loss of the naive lifting; it states the model in which the halo2 book proves its extraction theorem and classifies what that theorem does and does not establish for the deployed transcript; and it closes on the gap between concrete and asymptotic security. The running-time vocabulary, polynomial, negligible and , is the Math Guide’s (§“Polynomial, exponential, and negligible functions” and §“Algorithms, running time, and PPT”); expected polynomial time is the Crypto Guide’s (§“Adversaries and the security parameter”, the remark on expected versus strict polynomial time); tightness and loss are the Crypto Guide’s (§“Reductions”, §“Concrete security and the bit-security budget”); the assumption is its standing one (§“Standing assumptions”).
Theorem 3.5 extracts from a tree of accepting transcripts
with three children at every node and one level per round:
leaves for
The compiled argument of §4.7 was assembled in two layers, an information-theoretic polynomial IOP and a cryptographic commitment scheme, and its extractor is assembled in the same two layers, run backwards (Figure 16).
The lower layer recovers polynomials. The prover has sent
commitments and, in phases 6 and 7, one opening of the combined
The upper layer recovers the witness. With the polynomials in
hand, the prover’s claimed evaluations are the true evaluations of fixed
polynomials except with the Schwartz–Zippel allowance of
Lemma 4.5, since a claimed value that differs from
the extracted polynomial’s value survives the reduction only with that
probability; and “the true evaluations of fixed polynomials” is
precisely the hypothesis under which §2 proved its
theorems. Theorem 2.5 turns the accepted identity
What is proved and what is described. In the interactive setting
the composed extractor is a tree extractor in the sense of the
Crypto Guide with a wider tree: three children at each of the
inner-product levels, two at the level and two at the
level,
Everything above is interactive: the extractor chose the challenges it
fed the prover. In the deployed argument the challenges are hashes, and
the extractor of the Crypto Guide’s Fiat–Shamir theorem obtains
its second transcript by forking: it finds, among the prover’s
at most hash queries, the critical one whose answer became the
challenge, rewinds to it, and answers it afresh, succeeding with
probability about
With the deployed
Remark 4.12 named the two notions built to avoid this: round-by-round knowledge soundness, which labels partial transcripts as doomed and bounds the probability that one verifier challenge lifts the doom, and state-restoration soundness, which lets the prover restore an earlier verifier state and redraw its challenge, precisely the freedom a prover attacking a transcript hash has. Each exists to obtain a bound on the compiled argument that loses a factor linear in rather than ; no equivalence between them is asserted here, as none was there. Claiming a single factor for a compiled protocol nevertheless requires the precise theorem’s state-restoration, transcript, challenge and extraction hypotheses to hold of that protocol, and this volume does not assert a factor- bound for Halo 2’s compiled protocol. The next subsection names the model in which the halo2 book proves such a bound, in the state-restoration form, for its abstract interactive protocol, what that analysis assumes, and why its instantiation to the deployed transcript remains unwritten.
The nested forking of the previous subsection rewinds because the extractor has no other way to learn what is behind a group element: three accepting continuations are the price of one representation. The algebraic group model of Fuchsbauer, Kiltz and Loss (The Algebraic Group Model and its Applications) removes the need by restricting the adversary’s group operations, and it enables tighter analyses for protocols that suit it. It is not by itself a theorem eliminating every Fiat–Shamir loss; what it eliminates is the rewinding, and what remains must still be proved.
An algebraic adversary against a group is a
algorithm that, whenever it outputs a group element
where is the vector of group elements it has previously seen: the generators it was given and the elements it has received. The vector is the representation of .
The algebraic group model sits between the standard model, in which the adversary is any algorithm and every primitive is concrete code it may inspect (Crypto Guide, §“The standard model and the random oracle model”), and the generic group model, in which the adversary may perform group operations only through an oracle on opaque handles and never exploits the representation of an element (the same section, the remark on the generic and algebraic group models). An algebraic adversary is less restricted than a generic one, since it may compute on the bit representation of group elements however it likes; it must only be able to explain each element it outputs as a combination of elements it has seen. The model is an idealisation (the same remark): a proof in it says nothing about an adversary that outputs a group element it cannot explain. Figure 17 draws the three models as nested restrictions on the adversary and places this section’s analyses on them; the random oracle model, which idealises the hash rather than the group, is an independent axis, and an analysis may combine either group model with it.
In this model the prover outputs every group element with its
representation, and the extractor reads the witness off the
representations of a single accepting transcript instead of assembling
it from rewound ones; no rewinding occurs, and the price is the
assumption that the prover is algebraic. For the deployed opening,
equation (29), the halo2 book’s Protocol
Description chapter carries this out (“Witness-extended Emulation”, the
definition of the bad-challenge sets): comparing the two sides of the
accepting equation coordinate by coordinate either exhibits a
nontrivial discrete-logarithm relation among the generators or, unless
some challenge falls in a set of bad challenges fixed by the
messages before it, forces the representation of to open to the
claimed value. The analysed protocol draws every challenge from one
space of field elements, none zero or a row, and each round
challenge further so that its factor
Ghoshal and Tessaro (Tight State-Restoration Soundness in the
Algebraic Group Model) carry this analysis out for
Bulletproofs-style inner-product arguments: they prove tight
state-restoration soundness in the algebraic group model and derive
Fiat–Shamir security bounds from it under their stated hypotheses, the
transfer from the state-restoration game to the compiled argument being
their theorem. The deployed analysis follows them. The protocol
specification defines the proving system by reference to the halo2 book
(protocol specification,
§ 5.4.10.3,
“Halo 2”), and the book’s Protocol Description chapter fixes
the framework: it adopts state-restoration soundness because the
concrete protocol is realised through the Fiat–Shamir transformation
and a cheating prover can fork the transcript at will, and it invokes
Ghoshal and Tessaro’s theorem for the passage from that game to
soundness of the compiled argument. Its abstract interactive protocol is
stated for a relation of the form “a fixed multivariate constraint
polynomial in the column polynomials and the challenges vanishes on the
rows”, with the column polynomials as the witness, over public
parameters of
Let be a public-coin interactive argument for a relation
with challenges from a space . A
state-restoration prover , given the public
parameters, outputs a statement and then queries an oracle on
pairs , where is a transcript prefix the oracle has
recorded (initially only the empty one) and is a next prover
message; it may thus extend any earlier prefix. In the real game
the oracle answers a message of rounds to with a fresh uniform
where is the event that outputs in
the real game, and the event that
outputs in the ideal game and, if an accepting transcript was
recorded,
Let be the halo2 book’s abstract interactive argument for its
relation , over a group of prime order with scalar field
, for rows, a positive integer with
for every computationally unbounded distinguisher . Here
bounds the fraction of bad challenges after
every partial transcript, and
is the probability
that , given
The theorem is quoted as an interface and not proved in this volume: it
is the halo2 book’s (Protocol Description, “Witness-extended
Emulation”), proved there by instantiating Theorem 1 of Ghoshal and
Tessaro with the bad-challenge sets described above. Its
extractor works online, from the representations of a single
transcript, and never rewinds. At the deployed
Applying those bounds to the deployed Halo 2 transcript requires matching the precise folding, masking, challenge distribution and composition assumptions of the analysed protocol to the deployed one, and this volume does not prove that instantiation theorem. Four mismatches are visible from the earlier sections. The book’s abstract relation sees the permutation and lookup arguments of §2 only through the constraint polynomial and its committed columns; the Orchard circuit’s actual gates and table columns (§4.1) and its chunked running products (“The deployed chunking” in §2.6) instantiate that abstraction and must be checked against its degree hypotheses. The book’s challenges exclude zero, the rows and, for each , the value that zeroes its factor of , while the deployed transcript squeezes full field elements with no rejection (§3.8), so the deployed challenge distribution differs from the analysed one by the excluded events. The analysed folding is the deployed normalisation of Remark 3.9, and the masking is the deployed mask of §3.8, so those two match; the hash, however, is BLAKE2b (§4.3), and the transfer theorem’s random oracle must be instantiated by it. And the book’s theorem is for the interactive argument against a state-restoration prover, the compiled bound following by the transfer theorem under its hypotheses. In the classification of §1.2, the status of the transfer is designed-but-unspecified: the bounds exist for the analysed protocol and the design intends them for the deployed one, but the theorem that carries them across is not written, here or in the specification.
The Crypto Guide distinguishes a reduction’s existence from its tightness (§“Reductions”, the definition of loss and the remark on why loss matters concretely) and reads security as a budget of bits (§“Concrete security and the bit-security budget”): a scheme inherits the strength of its assumption only up to the loss of the reduction that connects them. Two tightness gaps separate the proved statements from the deployment.
The naive Fiat–Shamir knowledge-soundness analysis of the opening loses the
factor
Each analysis cited in this section that avoids the naive loss relies on an idealisation: the halo2 book’s extraction theorem (Theorem 5.3) on the algebraic group model, and its passage to the compiled argument on the random oracle model as well; the special-soundness analysis of Attema, Fehr and Klooß on the random oracle model alone. No standard-model tight bound is claimed for the deployment, by this volume or by the analyses it cites; this is a statement about the design’s analyses, not a specification claim. The specification requires knowledge soundness and statistical zero knowledge of the proving system (§ 4.1.13, “Zero-Knowledge Proving System”) but names neither a model nor a bound. Read against the bit-security budget, the consequence is concrete. The discrete-logarithm layer offers about operations of classical security (§3.5; Crypto Guide, §“Standing assumptions”); a reduction tight in lets the argument inherit that strength, less the algebraic term of Theorem 5.3, about at queries, which is not the bottleneck; a reduction losing lets it inherit nothing. For the analysed protocol the number is therefore the assumption’s, in the algebraic group and random oracle models; for the deployed argument it is so only through the instantiation that §5.2 classifies designed-but-unspecified.
Proved without idealisation of the adversary or of the transcript hash are the interactive statement, Theorem 3.5, for uniform generators (the deployed hashed generators add its hypothesis that hash-to-curve is a random oracle), and the information-theoretic layer of §2; described, with the hypotheses named, are the layered extraction that joins them and the naive lifting’s loss; cited, with its instantiation to the deployed transcript classified designed-but-unspecified, is the halo2 book’s bound in the algebraic group model.