4 The Halo 2 proof system

The verifying key is a deterministic function of the commitment parameters and the circuit description: the values of the fixed columns, the gates, the lookup arguments and the permutation $\sigma$ of Definition 2.7. For the Action circuit it is a fixed consensus parameter, the key the consensus rule above identifies. The prover’s witness is the content of the advice columns. A copy constraint places two cells in one cycle of $\sigma$ (Construction 2.10), and the public inputs are bound to advice cells in this way (§4.2).

In the running example the target $35$ is public, so it is not advice but instance data: it sits in the public-input polynomial $\mathrm{PI}(X)$ of (2), which the verifier builds himself from the column $(0,0,0,-35)$; its interpolant $64+50X+33X^2+47X^3$ of §2.2 takes the value $-35=62$ on row $3$ and $0$ elsewhere. A prover who claimed that $X^3+X+5=36$ has a root would face a different $G$, one with $-36$ in place of $-35$, and her honest trace would no longer vanish on the rows: the fourth gate would read $30+5-36\ne 0$. The public input enters the polynomial $G$ whose divisibility Theorem 2.5 tests, and an accepted proof attests the statement for the verifier’s public values.

The deployed circuit binds the public values through the permutation argument of §2.6, not through a gate. The instance column is equality-enabled, so it participates in the permutation $\sigma$; it is one of the fifteen columns counted under “The deployed chunking” there, beside the ten advice and four fixed ones. Each designated instance cell is copy-constrained to an advice cell that the circuit’s constraints read (the halo2 book’s Permutation argument chapter for the mechanism), so a satisfying assignment exists only when those advice cells hold the public values the verifier supplied (Figure 10). The alternative, a dedicated gate $q(X)\left(a(X)-\pi (X)\right)\equiv 0(mod{Z}_H(X))$ with a selector $q$ active exactly on the designated rows, is not used: the copy constraint reuses the permutation argument, at no extra gate degree.

The verifier does not take $\pi (X)$ from the prover. Both parties compute the commitment to each instance polynomial from the instance values (the halo2 book’s Circuit commitments chapter), with the public blinding factor $1$ in place of a random one so that the two computations agree, and absorb it into the transcript before the first challenge is drawn, in phase 1 of §4.5; every Fiat–Shamir challenge thereby depends on the public input. The book fixes the factor $1$ for the fixed columns only; for the instance columns it is the choice of the implementation, halo2_proofs. Thereafter the instance column is treated like any other: its claimed evaluation $\pi (x)$ appears among the phase-5 evaluations, enters the permutation identities as one of the $v_i$ of Construction 2.10, and the multipoint opening of phase 6 binds it to the instance commitment. Because the verifier computed that commitment himself, from the instance values he verifies against, the prover has no freedom over $\pi$: an evaluation inconsistent with the verifier’s own values fails the opening argument, by the evaluation binding recalled in §2.9.

The Action statement’s public input is the tuple $(\mathrm{rt},{\mathrm{𝖼𝗏}}^{\mathrm{net}},\mathrm{𝗇𝖿},\mathrm{𝗋𝗄},\mathrm{𝖼𝗆𝗑},\mathrm{𝖾𝗇𝖺𝖻𝗅𝖾𝖲𝗉𝖾𝗇𝖽𝗌},\mathrm{𝖾𝗇𝖺𝖻𝗅𝖾𝖮𝗎𝗍𝗉𝗎𝗍𝗌})$ (protocol specification, § 4.18.4, “Action Statement (Orchard)”): the anchor $\mathrm{rt}$, the root of the note-commitment tree the spent note is proved against (the Crypto Guide, §“Append-only and incrementally updatable trees”); the net value commitment ${\mathrm{𝖼𝗏}}^{\mathrm{net}}$; the nullifier $\mathrm{𝗇𝖿}$; the randomised verification key $\mathrm{𝗋𝗄}$; the extracted commitment $\mathrm{𝖼𝗆𝗑}={\mathrm{𝖤𝗑𝗍𝗋𝖺𝖼𝗍}}_{\mathbb{P}}(\mathrm{𝖼𝗆})$ of the output note (the Crypto Guide, §“A shielded spend, end to end”); and the flags $\mathrm{𝖾𝗇𝖺𝖻𝗅𝖾𝖲𝗉𝖾𝗇𝖽𝗌}$ and $\mathrm{𝖾𝗇𝖺𝖻𝗅𝖾𝖮𝗎𝗍𝗉𝗎𝗍𝗌}$, which permit non-zero-valued spends and outputs. The primary-input note of the same section encodes the tuple as the sequence

each integer read as an element of $𝔽={𝔽}_{p_{\mathrm{𝖯𝖺𝗅𝗅𝖺𝗌}}}$. The Action description specifies the proof with an eighth component, $\mathrm{𝖽𝗂𝗌𝖺𝖻𝗅𝖾𝖢𝗋𝗈𝗌𝗌𝖠𝖽𝖽𝗋𝖾𝗌𝗌}:=1-\mathrm{𝖾𝗇𝖺𝖻𝗅𝖾𝖢𝗋𝗈𝗌𝗌𝖠𝖽𝖽𝗋𝖾𝗌𝗌}$, where $\mathrm{𝖾𝗇𝖺𝖻𝗅𝖾𝖢𝗋𝗈𝗌𝗌𝖠𝖽𝖽𝗋𝖾𝗌𝗌}$ permits the output note’s receiver to differ from the input note’s (protocol specification, § 4.6, “Action Descriptions”); from NU6.3 the proof of every Action of either pool is verified with this further public input, which is $1$ for every Orchard-pool Action (ZIP 258). Rows $0$ to $8$ of the instance column hold the nine values above; no normative text fixes the row of the further input, and every other row is $0$ (Figure 10). Each is copy-constrained to an advice cell the circuit’s constraints read: ${\mathrm{𝖼𝗏}}^{\mathrm{net}}$, $\mathrm{𝗇𝖿}$, $\mathrm{𝗋𝗄}$ and $\mathrm{𝖼𝗆𝗑}$ to the cells where the circuit computes them; $\mathrm{rt}$ to a cell tied to the computed Merkle root by the gate $v^{\mathrm{old}}(\mathrm{root}-\mathrm{rt})=0$, which encodes the statement’s condition that $v^{\mathrm{old}}=0$ or the Merkle path is valid; the two enable flags to cells read by the gates $v^{\mathrm{old}}(1-\mathrm{𝖾𝗇𝖺𝖻𝗅𝖾𝖲𝗉𝖾𝗇𝖽𝗌})=0$ and $v^{\mathrm{new}}(1-\mathrm{𝖾𝗇𝖺𝖻𝗅𝖾𝖮𝗎𝗍𝗉𝗎𝗍𝗌})=0$, which encode, for flags in $\{0,1\}$, the conditions $v^{\mathrm{old}}=0$ or $\mathrm{𝖾𝗇𝖺𝖻𝗅𝖾𝖲𝗉𝖾𝗇𝖽𝗌}=1$, and $v^{\mathrm{new}}=0$ or $\mathrm{𝖾𝗇𝖺𝖻𝗅𝖾𝖮𝗎𝗍𝗉𝗎𝗍𝗌}=1$; and $\mathrm{𝖽𝗂𝗌𝖺𝖻𝗅𝖾𝖢𝗋𝗈𝗌𝗌𝖠𝖽𝖽𝗋𝖾𝗌𝗌}$ to a cell read by a gate that, when it is nonzero, equates the coordinates of the receivers $({𝗀}_{𝖽},{\mathrm{𝗉𝗄}}_{𝖽})$ of the two notes. That condition is the meaning § 4.6 gives the flag; the list of conditions in § 4.18.4 does not yet include it.

The verifier computes the instance commitment from the public values $𝝅$ itself, and the copy constraints tie the designated cells to the advice cells the constraints read; so a witness extracted from an accepting proof satisfies the relation at $𝝅$, not at other public values ${𝝅}^{\prime }$ the prover may target. The probabilistic conclusion, that a prover who knows no witness for $𝝅$, whatever witnesses she holds for other instances, convinces the verifier with at most negligible probability, holds under the knowledge soundness whose status §5 classifies: designed-but-unspecified for the deployed transcript, resting on the discrete logarithm on Vesta or on the algebraic group model, with the transcript hash modelled as a random oracle. Under that hypothesis an Action proof that verifies against an anchor, a nullifier and a value commitment certifies knowledge of a witness consistent with those values.

The Fiat–Shamir transform replaces the $i$-th challenge $c_i$ by

the hash of the public statement $𝗑$ and of the transcript prefix, the prover’s messages $m_1,\mathrm{\dots },m_i$ and the earlier challenges, under a fixed hash function $H$ (the Crypto Guide, §“The Fiat–Shamir transform: from interactive to non-interactive”). The ordering of §2.9 is enforced because each commitment is an input to the hash that derives the challenge testing it. The toy of §2.4 drew $z=20$ as an interactive challenge; the deployed prover derives every challenge from a hash. The two kinds of challenge are kept apart in what follows: the interactive one is uniform by assumption, the hashed one only in the model in which the hash is a random oracle.

A prover against the compiled argument may vary the inputs of $H$ and inspect the resulting challenges. The bound on that freedom uses round-by-round soundness (Canetti, Chen, Holmgren, Lombardi, Rothblum, Rothblum and Wichs, Fiat–Shamir: From Practice to Theory), which Remark 4.11 recalls.

The proposition has the form of the halo2 book’s extraction theorem (Protocol Description chapter, “Witness-extended Emulation”, its term $qϵ$) and of the state-restoration analysis of Ghoshal and Tessaro that §5 cites, where its application to the deployed transcript is classified. For the toy’s identity check, a single challenge with error $11/97$ (§2.4), ten queries exhaust the bound. This volume establishes no round-by-round error for Halo 2, whose binding is computational. At Orchard scale the identity check’s term is about $2^{-240}$ (one Schwartz–Zippel term, in the sense §1.2 fixed), and budgets of $2^{40}$, $2^{64}$ and $2^{80}$ queries multiply that term alone to $2^{-200}$, $2^{-176}$ and $2^{-160}$; these agree with the $Q{\epsilon }_{\mathrm{bad}}$ of the halo2 book’s algebraic-group-model bound quoted in §5.2, proved for the abstract protocol, whose transfer to the deployed transcript §5 classifies. The permutation argument’s term over $(\beta ,\gamma )$, $3N/|𝔽|$ with $N=15\cdot 2042$ participating cells (Corollary 2.12), is larger, about $2^{-237.5}$.

The hash must take the whole transcript prefix as input: a statement or commitment left out can be chosen after the challenge is seen, the “weak Fiat–Shamir” failure the Crypto Guide records in §“The Fiat–Shamir transform: from interactive to non-interactive”. The bound holds with $H$ modelled as a random oracle, a heuristic. The Crypto Guide proves the one-round theorem, with its forking-lemma extractor and its programmed-oracle simulator, and states that a multi-round protocol such as this one needs a multi-round theorem whose hypotheses match the protocol at hand; §5 weighs that theorem against the deployed transcript.

The compiled argument is non-interactive: the proof is one static object, commitments, evaluations and the opening’s scalars, and verification recomputes the challenges by the same hash and runs the same checks. The protocol specification defines a Halo 2 proof as a byte sequence (protocol specification, § 5.4.10.3, “Halo 2”, and its “Encoding of Halo 2 Proofs”), so a full node verifies an Action proof from the transaction alone.

Neither the protocol specification nor the halo2 book fixes the transcript that instantiates the transform; it is that of the implementation, halo2_proofs, and is as follows. The state is a BLAKE2b-512 hash state with the sixteen-byte personalisation Halo2-Transcript (the Crypto Guide, §“Domain separation and personalisation”). Absorbing a point $P=(x,y)\ne 𝒪$ of Vesta appends the bytes $\mathrm{𝟶}𝚡\mathrm{𝟶𝟷}\Vert {\mathrm{LE}}_{256}(x)\Vert {\mathrm{LE}}_{256}(y)$; the identity is not absorbable. Absorbing a scalar $s\in 𝔽$ appends $\mathrm{𝟶}𝚡\mathrm{𝟶𝟸}\parallel {\mathrm{LE}}_{256}(s)$. Squeezing a challenge appends $\mathrm{𝟶}𝚡\mathrm{𝟶𝟶}$ to the state, which keeps it, and returns the $64$-byte digest of the state read as a little-endian integer and reduced modulo $p_{\mathrm{𝖯𝖺𝗅𝗅𝖺𝗌}}$, with no rejection of any value (§3.8). The proof carries each point as its $32$-byte compressed encoding, the $x$-coordinate with the parity of $y$ in the top bit (protocol specification, § 5.4.9.6, “Pallas and Vesta”), and each scalar as ${\mathrm{LE}}_{256}(s)$. Before any prover message both parties absorb, as a scalar, a digest of the verifying key, its BLAKE2b hash reduced into $𝔽$, and then the instance commitments of §4.2, which therefore never appear in the proof. Every prover message is then absorbed in the order the protocol fixes, and each challenge is squeezed at its prescribed point, after everything it must depend on. The proof is the sequence of the prover’s messages in the phase order of Table 10, counted by kind in Table 8; the verifier replays the absorptions and recomputes every challenge. Figure 12 in §4.5 draws the timeline.

If every claimed value is true, then $q_i-r_i$ vanishes on $T^{(i)}$ and is divisible by $Z_i$ (the Math Guide, §“Roots and the factor theorem”), each $f_i$ is a polynomial of degree , so is $f$, and $f(x_3)=v_f$ whenever no $Z_i(x_3)$ is $0$; $f^{\ast }(x_3)=v^{\ast }$ then holds, and the honest opening of §3 accepts. The verifier’s rejection when $x_3$ is one of the query points, an event of probability at most $|{\bigcup }_i{T}^{(i)}|/|𝔽|$, is the reduction’s only completeness defect.

The bound is one more Schwartz–Zippel allowance, of the order of $n/|𝔽|$. The opening’s own knowledge error, $O(\log d/|𝔽|)$ by Corollary 3.13, lies below it, and that corollary’s witness-or-relation form supplies the binding opening the lemma assumes.

In the Action circuit the point sets are five. Every fixed, instance and permuted-label polynomial, the random polynomial of phase 4 and the collapsed quotient are queried at $\{x\}$; the advice columns, five at $\{x,\omega x\}$ and five at $\{{\omega }^{-1}x,x,\omega x\}$, according to the rotations their gates read; the permuted lookup input $A^{\prime }$ at $\{x,{\omega }^{-1}x\}$ and the permuted table $S^{\prime }$ at $\{x\}$; the lookup running products and the last permutation running product at $\{x,\omega x\}$; and the first two permutation running products at $\{x,\omega x,{\omega }^{-6}x\}$, the last rotation reaching the boundary row of Remark 2.17 that chains one product into the next. The sets $\{x\}$, $\{x,\omega x\}$, $\{x,{\omega }^{-1}x\}$, $\{{\omega }^{-1}x,x,\omega x\}$ and $\{x,\omega x,{\omega }^{-6}x\}$ give the five values ${\overline{q}}_i$, the multipoint evaluations of Table 8, and the whole reduction adds one point and five scalars to the proof.

The circuit fixes the columns, gates, lookup arguments and the equality permutation $\sigma$, as §4.1 described; its selectors and lookup tables are fixed columns. Key generation interpolates every fixed column and every permuted-label polynomial $s_i(X)$ of Construction 2.10 and commits to them with the fixed blinding factor $1$ (for the fixed columns, the halo2 book’s Circuit commitments chapter); these commitments, with the circuit description, form the verifying key. The transparent parameters of the commitment scheme, the $n$ generators $𝐆$, the blinding generator $H$ and the inner-product generator $U$ hashed to the curve as §3.8 described, together with the domain data, are held separately. All of it is reproducible from public algorithms and the circuit; no secret setup trapdoor exists. Verification is a deterministic function of the parameters, the verifying key, the instance values and the proof.

Both parties first absorb the digest of the verifying key and the instance commitments of §4.2 into the transcript, so that every subsequent challenge depends on the circuit and on the public input. The prover constructs the advice columns ${𝐰}_1,\mathrm{\dots },{𝐰}_{n_a}\in {𝔽}^n$, which with the fixed and instance columns form a satisfying assignment in the sense of Definition 2.7, fills the reserved trailing rows of each with uniformly random field elements, the blinding rows of §4.6, interpolates each to $w_i(X)$ of degree , and sends $\mathrm{𝖢𝗈𝗆𝗆𝗂𝗍}(w_i;r_i)$ with fresh blinders $r_i$. The verifier absorbs the commitments.

The verifier sends $\theta$. For each lookup the prover compresses the input expressions and table columns by powers of $\theta$ as in (10), forms the permuted columns $A^{\prime }$ and $S^{\prime }$ of Construction 2.14, and sends their two commitments; the verifier absorbs them.

The verifier sends $\beta$ and $\gamma$. The prover commits to the permutation running products, one per chunk of $d_{\max }-2$ columns as “The deployed chunking” in §2.6 described, and to one lookup running product $Z_{\mathrm{lookup}}$ per lookup, and sends the commitments; the verifier absorbs them. The order is not a convenience. The permuted columns $A^{\prime }$ and $S^{\prime }$ must be fixed before the challenges that randomise the products are drawn, since Theorem 2.15 bounds the prover’s success probability only over challenges drawn after her columns; a prover who saw $\beta ,\gamma$ first could choose the permutation against them.

Before $y$ is drawn the prover commits to a uniformly random polynomial of degree , sends the commitment, and the verifier absorbs it; its role is the zero-knowledge one explained in §4.6. The verifier then sends $y$. The prover assembles the gate equation, one polynomial

the $y$-weighted combination of the $T$ constraint polynomials $g_t$ of the circuit: each constraint of each custom gate with its selector factor, the permutation identities (7) and the chunk-boundary identities, the lookup identities (9), and the boundary identities of Remark 2.17, each masked by its active-row factor where that remark requires. If every constraint holds then every $g_t$ vanishes on the rows, so $C$ does, and $Z_H\mid C$ by (3): the quotient $h(X):=C(X)/Z_H(X)=C(X)/(X^n-1)$ is a polynomial. If some constraint fails at some row, Lemma 4.6 bounds the probability that $C$ nonetheless vanishes on the rows, since $y$ is drawn after every polynomial in the $g_t$ is committed and after $\theta$, $\beta$ and $\gamma$.

For the deployed $d_{\max }=9$ and $n=2048$ the bound is $\mathrm{deg}h\le 16375$, far above the degree bound $n-1=2047$ that the commitment of Construction 3.2 supports with $d=n$ generators, so $h$ cannot be committed as one polynomial. The prover therefore uses a fixed proof shape of $d_{\max }-1$ chunks $h_0,\mathrm{\dots },h_{d_{\max }-2}$, each of degree , with

retaining leading zero chunks when the actual degree is smaller, and commits to each chunk separately with its own blinder; there are $8$ chunks for Orchard. The count is right because $h$ has at most coefficients. Once the evaluation point $x$ is drawn, the verifier recombines the chunk commitments, weighted by powers of $x^n$, into one commitment ${\sum }_i[x^{ni}]\mathrm{𝖢𝗈𝗆𝗆𝗂𝗍}(h_i)$ to the polynomial ${\sum }_i{x}^{ni}{h}_i(X)$, whose value at $x$ is $h(x)$; no chunk is ever opened on its own (the halo2 book’s Protocol Description chapter, steps 5 to 8, and note 1 of its “Zero-knowledge and Completeness”).

The verifier sends $x$. The prover evaluates every committed polynomial the verifier’s identities query, except the quotient chunks, at $x$ and at the rotated points the identities reference, $\omega x$ for the running products and for any gate reading the next row, ${\omega }^{-1}x$ for the permuted lookup input $A^{\prime }$ and for gates reading the previous row, and ${\omega }^{-6}x$, the deployed boundary row, for all but the last permutation product, and sends the claimed values as field elements. The deployed proof also carries the evaluations at $x$ of the fixed columns and of the permuted-label polynomials, which the same opening binds to the verifying key’s commitments, and of the random polynomial, bound to its phase-4 commitment. No evaluation of $h$ is sent: the verifier computes the expected quotient value $C(x)/(x^n-1)$ from the sent evaluations, evaluating ${\mathrm{\ell }}_0$, ${\mathrm{\ell }}_{\mathrm{last}}$, ${\mathrm{\ell }}_{\mathrm{blind}}$ and $Z_H$ at $x$ himself, and enforces it against the collapsed chunk commitment inside the multipoint opening of phases 6 and 7, where the claimed evaluations themselves are bound to their commitments as well. The gate equation is thus checked as the identity $C(x)=h(x)Z_H(x)$, the deployed form of (5).

The parties run Construction 4.4 on every committed polynomial with a claimed evaluation: the advice columns, the instance column, the fixed and permuted-label polynomials, the permuted lookup columns, the running products, the random polynomial, and the collapsed quotient with its expected value, the last two joining the $\{x\}$ group. The prover sends the commitment $F$ after $x_1,x_2$ and the five values ${\overline{q}}_i$ after $x_3$; after $x_4$ both parties hold the statement $(F^{\ast },x_3,v^{\ast })$.

The parties execute the deployed opening of §3.8, the masked argument in the normalisation of Remark 3.9, on $(F^{\ast },x_3,v^{\ast })$. The prover sends the mask commitment $S$; the verifier sends $\xi$ and $\zeta$; then for $k=11$ rounds the prover sends the pair $(L_j,R_j)$ and the verifier answers with $u_j$; finally the prover sends the scalars $c$ and $f$. The verifier accepts if and only if the deployed equation (29) holds with $P:=F^{\ast }$, $v:=v^{\ast }$ and $x:=x_3$, its one multi-scalar multiplication of length $n$ included. Its symmetric counterpart is the masked check (24), which differs from it by the three changes of that remark: the fold normalisation, a change of variables; the factor $\zeta$ on $U$; and the value carried as $+[v]U$ rather than $-[v]G_0$. Neither it nor (15) is the deployed equation. This is the proof’s end; Table 8 counts its bytes by kind, and nothing else is sent.

In the recursive variant of Halo 2 the verifier is itself a circuit, and that circuit defers the one expensive step of phase 7, the claim $G^{(0)}=⟨𝐬,𝐆⟩=\mathrm{𝖢𝗈𝗆𝗆𝗂𝗍}(g_{\mathrm{dep}};\mathrm{\hspace{0.17em}0})$ of (29), the deployed form (Remark 3.9) of the claim $G^{(0)}=\mathrm{𝖢𝗈𝗆𝗆𝗂𝗍}(g;\mathrm{\hspace{0.17em}0})$ of §3.4, into an accumulator folded with the accumulators of earlier proofs; a single decider at the end verifies all accumulated claims. Orchard does not do this. The protocol specification uses Halo 2 only to prove and verify Action statements and composes no proofs (protocol specification, § 4.1.13, “Zero-Knowledge Proving System”), the Orchard design proposal states that it makes no use of the recursion (ZIP 224), and the verifier pays every deferred multiplication itself; several proofs may share it by the randomised batch check of Lemma 3.14. The variant is developed as the coda of §7.

The prover computes one multi-scalar multiplication of length $n$ per commitment she sends before the opening, $22a+10$ for a bundle of $a$ Actions: per Action the ten advice columns, the six permuted lookup columns and the three permutation and three lookup products; shared, the random polynomial, the eight quotient chunks and the multipoint polynomial $f$. She also computes the $a$ instance commitments, as the verifier does (§4.2). The opening adds one of length $n$, for its mask commitment $S$, and the $2k$ cross terms of its rounds, two in each, of lengths $n/2,n/4,\mathrm{\dots },1$ in successive rounds. The verifier performs $O(a+\log n)$ field and group operations for a proof of $a$ Actions: he commits to the $a$ instance columns (at most ten nonzero values each), recomputes the challenges, evaluates each Action’s gate equation at $x$, combines the $23a+46$ commitments of phase 6, and runs the $k$ rounds of phase 7; to this he adds the single deferred multi-scalar multiplication of length $n$, which is the linear term that §3.8.1 discussed and that a batch verifier amortises across proofs with fresh random scalars; that batching is distinct from the accumulation above.

The prover of the running example sends commitments and the evaluations $a(20),b(20),c(20),t(20)$ at the random point. An evaluation is a linear equation in the secret coefficients: $a(20)=90+61\cdot 20+22\cdot {20}^2+24\cdot {20}^3=59$ is one equation in the four unknowns $(90,61,22,24)$, and evaluations at four distinct points determine the column, hence the secret witness $3$. Halo 2 therefore blinds: the witness trace reserves independent random rows, and every commitment carries an independent random blinding term. Adding random coefficients to a column polynomial would not do: a column polynomial is determined by its $n$ row values, and a random coefficient on $X^i$ changes every row, breaking the gates; a random multiple of the Lagrange polynomial ${\mathrm{\ell }}_j$ of a reserved row changes row $j$ alone, which is what a blinding row is. The random values violate no constraint: every selector is zero on the reserved rows, so the gates hold there, and the permutation and lookup identities carry the active-row factor of Remark 2.17. Each column’s openings are then uniform (Lemma 4.8); the joint statement is the proposition of “The simulator” below, whose simulator is one in the sense of the Crypto Guide (§“The simulation paradigm and zero knowledge”).

The commitment of Construction 3.2 is perfectly hiding. The prover commits a polynomial $p$ as

with $𝐩$ the coefficient vector, $𝐆$ the generator vector, and $H$ the blinding generator of §3, of no known discrete-logarithm relation to $𝐆$; the term $[r]H$ makes the commitment a uniform group element for every $p$, since $H$ generates $𝔾$, so a commitment by itself leaks nothing about what was committed. This is the perfect hiding of the Pedersen commitment, proved in the Crypto Guide (§“The Pedersen commitment” and §“Hiding and binding”) and recalled in §2.9. Every commitment the prover sends in phases 1 to 6, the advice columns, the permuted lookup columns $A^{\prime }$ and $S^{\prime }$, the permutation and lookup running products, the random polynomial, the quotient chunks and the multipoint polynomial $f$, has this form with a fresh $r$ (the halo2 book’s Protocol Description chapter, which blinds every group element of the protocol, its note 4). The verifying key’s commitments and the instance commitments carry the fixed blinding factor $1$ instead: they commit public data both parties recompute (§4.5, §4.2), so there is nothing to hide, and a random blinder would prevent the two computations from agreeing.

The prover opens commitments, and an opening reveals evaluations. To keep those evaluations from revealing the witness, the last $n_{\mathrm{blind}}$ rows of the table, the blinding rows, carry no circuit data: no gate applies there, and each advice column holds uniformly random field elements on them. By Lemma 4.8 below, a column opened at $m$ distinct points outside the rows needs $n_{\mathrm{blind}}\ge m$. The halo2 book’s Protocol Description chapter accordingly requires $n_e+1$ random evaluations of a polynomial opened at $n_e$ rotations of $x$, the extra one covering its opening at the point $x_3$ of the multipoint reduction. In the Action circuit a polynomial is opened at most four times: at three rotations of $x$, for some advice columns and the first two permutation products, and at $x_3$. The deployed circuit takes $n_{\mathrm{blind}}=5$, one more than that, a parameter fixed by the implementation, halo2_proofs; with the boundary row of Remark 2.17 its usable rows number $n-(n_{\mathrm{blind}}+1)=2042$. The permutation and lookup running products are blinded the same way, their trailing rows random, and the remark’s active-row factor exempts every one of those rows from every argument, so the random values do not violate a constraint (Figure 13; the halo2 book’s Permutation argument and Lookup argument chapters, their “Zero-knowledge adjustment” sections).