6 The verifier’s decision and its implication chain

The verifier of the toy holds the fixed data of the circuit, the five selector polynomials and the permuted-label polynomials of Construction 2.10; the public input, the column $(0,0,0,-35)$ interpolated to $\mathrm{PI}(X)$ (§4.2); and the proof. The proof is a byte string (§4.3): commitments, claimed evaluations, and one opening, in the order of the phases of §4.5 (Table 10), counted by kind in Table 8. He never sees a column polynomial, a blinder or the advice; he sees curve points and field elements, and he performs the checks below in this order.

1. 1.

   The challenges. He first commits to the instance column himself, from the public input and with the fixed blinder $1$ (§4.2), so that the public input never comes from the prover. He then replays the transcript (§4.3): he absorbs the key digest, that instance commitment and each prover message in turn, and squeezes every challenge at its prescribed point. In the toy the point $z=20$ was drawn by decree; in the deployed protocol the evaluation point $x$ is a hash of everything before it.

2. 2.

   The identity at the point. From the claimed evaluations and the fixed polynomials he evaluates himself, he forms both sides of the gate identity. In the toy this is the one field equation (5): $G(20)=75$ against $t(20)Z_H(20)=67\cdot 46=75$, accepted; the $c_0=10$ cheat of Example 2.3 gives $20$ against $64$, rejected. In the deployed protocol the identity is $C(x)=h(x)Z_H(x)$, with $C$ the $y$-combination of every constraint polynomial and $h$ the chunked quotient, and it is enforced by opening the collapsed quotient commitment at $x$ to the value $C(x)/Z_H(x)$ that the verifier computes himself from the evaluations of phase 5, inside the multipoint opening (phases 6 and 7 of §4.5).

3. 3.

   The wiring. He evaluates the boundary and update identities of the permutation argument (7) at the point and, in the deployed form, the chunk-boundary identities of §2.6 and the boundary identity ${\mathrm{\ell }}_{\mathrm{last}}(Z^2-Z)$ of Remark 2.17. In the toy the ratio of the two products (6) at $\beta =\gamma =2$ is $1$ for the honest trace and $61$ for the tampered $b_1=4$ (Example 2.8).

4. 4.

   The tables. He evaluates the four lookup identities (9) and, in the deployed form, the boundary identity ${\mathrm{\ell }}_{\mathrm{last}}(Z^2-Z)$ of Remark 2.17 at the point, five for each lookup argument. The toy’s grid has none; the two-bit check of Example 2.13 showed the shape, with both products equal to $82$ and the forged $7$ stranded in every arrangement. In the deployed protocol items 3 and 4 are not separate checks: their identities are summands of $C$ and are enforced by the one check of item 2; only the toy checks them separately.

5. 5.

   The openings. Every evaluation he received for the three checks above was claimed. He now binds each claim to its commitment: the multipoint reduction of Construction 4.4 folds every claim into one statement, and the inner-product equation (29) discharges it with one multi-scalar multiplication of length $n$. In the toy, the opening of $a(X)$ at $z=20$ to the value $59$ closes at $(54,39)$ on both sides (Table 5) and the false value $60$ moves the left-hand side to $(62,15)$; the deployed opening of the same commitment closes at $(5,72)$ and rejects $60$ likewise (Table 7). Among the claims is $\pi (x)$, which the opening binds to his own instance commitment (§4.2).

If every check passes he accepts. The accepted checks imply the following chain, read backwards from the last check to the first; Figure 17 draws it.

1. 1.

   The identity check passed at his random point. Because the commitment binds, the polynomials behind the openings were fixed before the point was chosen: the Pedersen vector commitment is binding under the discrete logarithm on Vesta (the Crypto Guide, §“Pedersen vector commitments”, recalled in §2.9), and the opening argument is knowledge sound (Theorem 3.5 and Corollary 3.13), so from any prover who passes the opening an extractor recovers the committed vector and the value it opens to, or else a discrete-logarithm relation among the hashed generators; its knowledge error is $O(\log d/|𝔽|)$, and the multipoint reduction that fed it adds one Schwartz–Zippel allowance of order $n/|𝔽|$ (Lemma 4.5). With a hash in place of coins the ordering holds by construction, every commitment being an input of the hash that produced the challenge testing it (§4.3). Because the point was random and a false identity disagrees with the true one at all but $\mathrm{deg}D$ points, passing supports $G(X)=t(X)Z_H(X)$ as polynomials except with the error $\mathrm{deg}D/|𝔽|$ of Theorem 2.5 for this fixed check: $11/97$ for the toy’s degree budget, $3/97$ for the particular cheat of Example 2.6, about $2^{-240}$ at Orchard scale, one term in the sense §1.2 fixed. In the deployed form the identity is $C=h{Z}_H$, and the challenge $y$ that combined every constraint into $C$ costs one more term, $(T-1)/|𝔽|$ for $T$ constraint polynomials (Lemma 4.6).

2. 2.

   The identity holds as polynomials. Then $Z_H\mid G$, so $G$ vanishes on every row (Theorem 2.2, equivalence (3)), so every gate equation holds at every row (Theorem 2.1). Both steps are exact equivalences with no error term: in the toy, the four rows of Table 1 each satisfy (1). In the deployed form every constraint polynomial combined into $C$ vanishes on the active rows: every custom gate, and the permutation and lookup identities that the next two links consume.

3. 3.

   The permutation identities passed. Except with the error $2N/|𝔽|$ of Theorem 2.11 over $\beta ,\gamma$, with $N$ the number of participating cells, twelve in the toy, and, in the deployed form, $N/|𝔽|$ more for the challenges at which a product factor vanishes (Corollary 2.12), the copy constraints hold: the per-row gates are wired into one coherent computation, the witness $3$ of row $0$ is the witness of rows $1$ and $2$, and each row’s output is the next row’s input. The lookup identities passed likewise: except with the error $4n/|𝔽|$ of Theorem 2.15, and $n(m-1)/|𝔽|$ more for the $\theta$-compression of (10) (Proposition 2.16) when a lookup has $m>1$ columns, every looked-up value is in its table.

4. 4.

   The public input fixed the target at $35$. In the toy, $35$ enters the gate polynomial $G$ through $\mathrm{PI}(X)$, which the verifier interpolates himself (§4.2), so it enters the identity of link 1. In the deployed circuit the instance polynomial $\pi (X)$ of Definition 4.2 is the verifier’s own: he committed to it from the values he intends to verify against, and its designated cells are copy-constrained to the advice cells that carry the same values, so the permutation of link 3 forces agreement. There is no error term of its own. The relation certified is the one at the public input the verifier supplied (§4.2).

Together with the observation that closed §2.1, that filling the advice columns is knowing the witness, because those cells are the wires carrying it and its powers, the four links say: there exists an assignment of the advice columns, a value of the witness, making the entire arithmetisation of $X^3+X+5=35$ hold, at the public $35$.

The chain so far establishes that satisfying advice exists. That the prover knows it is the extraction question. The extractor of Theorem 3.5 and Corollary 3.13 recovers, from any prover who passes the opening, the committed vector and its blinder: it establishes knowledge of committed polynomial data, and nothing more. It does not by itself prove that those polynomials encode a satisfying circuit witness; that is the upper layer’s task in the layered extraction of Remark 4.11, where the commitment scheme’s extractor turns commitments into polynomials and the polynomial IOP’s extractor turns polynomials into a witness. Under the composed hypotheses named there, a round-by-round or state-restoration knowledge-soundness theorem for the IOP, extractability and evaluation binding for the commitment scheme, and a multi-round Fiat–Shamir theorem for the transcript, an extractor for the full protocol obtains such a witness; §5 weighs those hypotheses against the deployed transcript, and in particular states in which model the tight bound is proved.

For the interactive protocol and an honest verifier the transcript reveals nothing beyond the truth of the statement (Proposition 4.9, cited, and Corollary 4.10); for the non-interactive deployed proof this is stated, not proved (§4.6). Every commitment the prover sent is a uniform group element (perfect hiding, recalled in §4.6); the verifying key’s and the instance commitments carry the fixed blinding factor $1$ and commit only public data; the evaluations of each blinded column are uniform by Lemma 4.8; the final scalar of the opening, which folding alone would have leaked as a linear form of the coefficients (Remark 3.7), is masked by the random polynomial $s(X)$ vanishing at the opening point (§3.6, in the deployed form of §3.8); and the joint transcript is simulated by the witness-free simulator of Proposition 4.9, within the distance of Corollary 4.10 for the deployed challenges. The toy has no blinding rows and is not zero knowledge: its claimed value $a(20)=59$ alone singles out the witness $3$ among the three roots $3,18,76$ of $X^3+X+5=35$ in ${𝔽}_{97}$, and indeed among all $97$ candidates; the blinding rows of Lemma 4.8 are what make the deployed evaluations uniform. The deployed mask makes the opening’s own scalar a fresh uniform value: $c=20$ under one mask (Table 7) and $c^{\prime }=46$ under another (§3.8), both accepted.

The verifier has checked a small transcript, $2720+2272a$ bytes for $a$ Actions (Table 8), and a logarithmic opening of $2k+1=23$ points. Each link of the chain carries its own error term, which bounds the failure of that link alone: the identity’s $\mathrm{deg}D/|𝔽|$ (Theorem 2.5); the $y$-combination’s $(T-1)/|𝔽|$ (Lemma 4.6); the permutation’s $2N/|𝔽|$ (Theorem 2.11) and $N/|𝔽|$ for the challenges at which a product factor vanishes (Corollary 2.12); the lookup’s $4n/|𝔽|$ (Theorem 2.15) and the $\theta$-compression’s $n(m-1)/|𝔽|$ (Proposition 2.16); the multipoint reduction’s allowance of order $n/|𝔽|$ (Lemma 4.5); and the opening’s $O(\log d/|𝔽|)$ (Theorem 3.5 and Corollary 3.13). Combining them into one knowledge error for the protocol is the compilation principle of Remark 4.11, whose hypotheses §5 names and does not discharge; no sum of the terms is asserted. Beyond these terms lie the loss of replacing coins by a hash, of which the grinding route alone multiplies a term by the query budget $Q$, so that $2^{-240}$ becomes $2^{-176}$ after $2^{64}$ attempts (§4.3, Proposition 4.3), while the multi-round transform’s full loss is weighed in §5, which asserts no factor-$Q$ bound for the compiled protocol; and the assumptions beneath the chain, the discrete logarithm on Vesta that makes the commitments bind and the extractor’s alternative output infeasible (Theorem 3.5 and Corollary 3.13), the random-oracle model for the transcript hash, and the extraction model in which the non-interactive bound is proved (§5). The isolated $2^{-240}$ is not the verdict’s error: it is one Schwartz–Zippel term for one fixed lie, read as §1.2 fixed.

For the verification of an Action proof that the consensus rules require (protocol specification, § 4.6, “Action Descriptions”), the randomised polynomial-identity test of link 1 is the algebraic core: a Schwartz–Zippel argument on one identity at one hashed point. The full verifier of §4.5 evaluates that identity’s permutation and lookup summands from the claimed evaluations, binds every claimed evaluation through the multipoint reduction, recomputes every transcript challenge, and closes the single inner-product equation with its one multi-scalar multiplication of length $n$, before concluding that the circuit’s constraints hold at the public input it verified against, the anchor, the net value commitment, the nullifier, the randomised verification key, the extracted note commitment and the flags of §4.2. Under the knowledge soundness whose status §5 classifies (designed-but-unspecified for the deployed transcript), an accepted Action proof certifies, for a known witness, that the constraints of the circuit whose verifying key the consensus rules fix (protocol specification, § 4.6) hold. That these imply the conditions of the Action statement (protocol specification, § 4.18.4) is a property of that circuit, which this volume does not verify and which the specification records as having failed for the Orchard circuit deployed before NU6.2 (the same section); value balance additionally requires the binding signature (protocol specification, § 4.14, “Balance and Binding Signature (Orchard)”), and privacy rests also on components outside the proof, such as note encryption.

Each of the five reductions of §1.2, “The chain of reductions”, is owned by a formal statement. Table 12 lists, reduction by reduction, what the toy exhibited and which statement carries it; the last two rows point beyond the spine, to the extractor that turns existence into knowledge and to the recursion, which Orchard does not deploy and on which nothing above depends.