This section carries the running example of §1 — the
prover knows
The verifier cannot evaluate the computation without the witness. Arithmetisation dismantles the computation into local facts, each involving only a handful of values, arranged so that “every local fact holds and the values are consistently shared” is equivalent to “the whole computation ran correctly”. The dialect of arithmetisation Halo 2 uses is called PLONKish; §2.5 defines it once the toy has shown what it generalises.
Evaluate
Four elementary operations, two multiplications and two additions, and each
becomes one row of a table. A row has three wires
| (1) |
where carries the negated public input on that row (here
, for the target ). A multiplication gate
| row | gate performed | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
The table as printed does not yet encode the computation. Nothing forces the
in row to equal the in rows and , nor the output
where denotes the cell of column in row . Figure 2 draws them as wires. They turn a list of unrelated gates into a single dataflow; enforcing them is an argument in its own right, the permutation argument of §2.6.
The claim is now equivalent to a purely combinatorial assertion:
there exist values for the advice cells
The grid has finitely many rows, and the aim is a statement about all rows at once that the verifier can check at one point. A polynomial of degree less than is determined by its values at distinct points (Math Guide, §“Lagrange interpolation”), and the rest of the section relies on this.
The table has
and row lives at the point (Figure 3).
Roots of unity are chosen
because they form a cyclic group: the row after is
Each column of the table is four numbers, one per row. Interpolate: for
the advice column there is a unique polynomial of degree
(Math Guide, §“Lagrange interpolation”), and likewise ,
, the publicly known selector polynomials
and each returns its column at the rows: takes the values
on , the values , and
the values . Interpolation is thus a
bijection between columns of four values and polynomials of degree
Assemble the left-hand side of the gate equation (1) with the polynomials in place of the per-row numbers.
Let
| (2) |
Then
The term multiplies three polynomials of degree at most , and
every other term has degree at most , so
For the honest trace,
of degree exactly , and it vanishes at all four points of by construction. “Every gate is satisfied” has become “ vanishes on ”; the copy constraints remain separate. Four separate checks are now one statement about one polynomial.
The condition “ vanishes on ” is still a statement about four points. This subsection replaces it by a polynomial identity that refers to no individual row.
The vanishing polynomial of is the monic polynomial (leading coefficient ) whose roots are exactly the points of ,
where the closed form
Every gate of the trace holds if and only if there is a polynomial
with
By Theorem 2.1, every gate holds if and only if
vanishes on . The factor theorem (Math Guide, §“Roots and
the factor theorem”) gives
| (3) |
and divisibility is the existence of the quotient . □
Satisfaction of the gate constraints is precisely the existence of ; correct wiring still requires the copy constraints. For the honest trace the division comes out even: has degree , has degree , and
is a polynomial of degree with remainder zero, as it must be.
Suppose the advice is wrong: some gate fails. Then does not vanish on
all of , so by (3) does not divide , and
no polynomial satisfies
Dividing by with remainder (Math Guide, §“Division
with remainder”) gives the quotient
| (4) |
of degree . The identity
The prover wishes to convince the verifier that
The prover commits to her polynomials
The verifier picks a point
The prover opens her commitments at : she returns the field
elements
The verifier forms from the openings and the self-evaluated
public polynomials via (2), computes
| (5) |
He accepts if and only if (5) holds.
If the prover is honest then
and the verifier accepts. He accepts every time, for every .
Soundness rests on the fact that a nonzero polynomial of low degree has few roots.
Suppose the trace is invalid, so that the prover’s gate polynomial
does not vanish on all of , and let be any polynomial she
commits to as the quotient. Set
Were the zero polynomial,
The bound is negligible when is exponential in the security parameter and is polynomial in it. The verifier does not recompute the trace; he tests one polynomial identity at one random point.
For the
At the actual draw
The fraction is large only because the field is a toy, and it concerns one particular quotient; the next paragraph bounds every cheat by . What such a term means at the deployed field size is the scale caveat of §1.2.
The argument needs small relative to , otherwise
“ roots out of ” is no constraint at all. The commitment
scheme enforces a degree bound on every committed polynomial
(Crypto Guide, §“Polynomial commitment schemes”), so the prover
cannot commit to a of unbounded degree. The bound follows the
degree the commitment admits, not the honest degree. The wires are
committed at degree below
The toy has met every ingredient concretely: an evaluation domain , a
generator , the vanishing polynomial , columns interpolated
into polynomials of degree
Fix a prime field and an integer with
a finite set of columns, each of cells, one per
row, partitioned into fixed columns (preprocessed circuit data,
known to both parties), advice columns (the prover’s witness)
and instance columns (public input); a cell is an element
of
a maximum constraint degree ;
a finite set
a finite sequence of custom gates
a set
a subset
a set of lookup arguments, each an input tuple of column expressions and a table tuple of columns.
An assignment gives every cell a value in , the fixed cells
their circuit values; write for the value of cell . It
is satisfying if every gate vanishes at every row of (in the
deployed system the selectors are zero outside ),
The letter is reserved, from §3 on, for the length of a committed vector; the constraint degree is therefore written throughout this volume.
The original PLONK system of Gabizon, Williamson and Ciobotaru uses a single fixed five-selector universal gate,
with three wire polynomials
With the Lagrange basis of , defined by
The copy constraints of §2.1 remain to be enforced.
The gate identity of §§2.2–2.4
checks each row separately; it does not assert that
Group the cells into the classes that must share a value, , , , , and let be the permutation of the twelve cells that cycles each class in the order written and fixes and :
Give every cell a distinct label: the cell in row of the -,
-, -column gets , ,
respectively, where
Write for a cell’s label and
for its value. Asserting “cells in a class are equal” is then
equivalent to asserting that the multiset (a finite collection in
which an element may occur more than once; two multisets are equal when
every element occurs equally often in both) of pairs
is unchanged when each
label is replaced by the label of the cell’s image under : a pair
moves to , and the moved pair was already
present exactly when the cell at carried the same value .
Figure 6 draws the cycles with their labels. Because
labels are distinct, comparing two multisets of pairs is a job for a
product: compress each pair to the linear form
| (6) |
If the wiring is honest the two products run over the same multiset of
factors and agree identically in
A product over all cells is not a local fact, so the prover commits to a
running product: a column with
Strip the product down to a single wired pair,
because the shared value makes the two left-hand factors a mere
reordering of the two right-hand ones: the labels may permute under
precisely because the values agree. Now let the prover cheat the
copy,
For the honest trace with
Halo 2 states the argument for any number of columns, and the statement needs one lemma on two-variable polynomials. The Schwartz–Zippel lemma of the Math Guide (§“The Schwartz–Zippel lemma”) is univariate; that section’s remark on the multivariate generalisation states the several-variable bound without proof, as a consequence of the univariate lemma applied once per variable, and Lemma 2.9 carries out that derivation for two variables.
Let
Write
Let
| (7) | ||||
which together assert
| (8) |
The verifier opens at the random point and at , and checks the boundary and the cross-multiplied update.
The first identity fixes
The assignment satisfies every equality constraint (cells related by
carry equal values) if and only if the two sides
of (8) are equal as polynomials in and
. Consequently the honest prover always satisfies
(8), and if some constraint is violated the two
sides agree at uniformly random
Index cells by , write and for value and label, and set
Each side is a product of monic linear polynomials in over the
ring , with roots
If every constraint holds then
If some constraint fails, pick with
The honest prover’s ratio is whenever the denominator is nonzero. The deployed boundary rule of Remark 2.17 admits the final value , and the error bound changes accordingly.
Let the columns be fixed before
Suppose some running products satisfy the identities and no numerator
factor
Excluding the final commitment check, the verifier’s work for the
argument is
The update identity in (7) has degree
Some constraints admit no low-degree gate on the constrained cells alone.
“This cell is a ten-bit number” or “this chunk indexes an entry of the
Sinsemilla generator table” (Sinsemilla is the hash of the Crypto
Guide, §“Sinsemilla: an algebraic hash-based commitment”) has no
low-degree formula in the cell itself: written as one polynomial gate,
“
Membership of every entry of a column in a table column is, like
a copy constraint, a statement about multisets, but it is not a
permutation: may repeat one table entry and omit others. The prover
therefore commits to , a rearrangement of in which equal values
occupy contiguous runs, and to , a rearrangement of in
which the first row of each run of holds the matching table value.
Two row-local conditions then give membership: each row of
either begins a run,
Constrain cells to two-bit values with the table
The Action circuit uses lookups of both kinds: it range-constrains each
ten-bit word of a decomposition by a lookup into the table
The objective is that every entry of the column on the active rows
appears as some entry of the column (the halo2 book’s
Lookup argument chapter). The prover supplies
polynomials and where (i) is a permutation of
with like values grouped into contiguous runs, and (ii) is a
permutation of in which the first row of each run of like values in
holds the matching value. The prover commits to and ;
after receiving challenges
| (9) | ||||
the second and fourth additionally masked by the active-row factor of Remark 2.17.
Let the active rows be
Set
So, with that probability excepted, is a rearrangement of and of
on the active rows. The third identity fixes row :
A lookup of input expressions
| (10) |
and Construction 2.14 runs on and .
Let be drawn uniformly after all input and table columns are
fixed. If the input tuple at some active row equals the table tuple at no
active row, then the compressed input at that row equals
at some active row with probability at most
For each active table row the difference of the compressed values is a
polynomial in of degree at most
Variable tables, where is itself an advice column, and range checks, where enumerates the allowed range, are special cases of the same argument.
The lookup identities, like the permutation identities of
§2.6, hold on the active rows only. The deployed
system withholds the trailing rows of every column from them: a boundary
row and, after it, blinding rows, which in every
witness column (advice, and the permuted and running-product columns of
the arguments) hold uniform random values, for the reason “Zero
knowledge: hiding the witness in Halo 2” in §4 gives;
fixed and instance columns carry no random values. Let
The random-point argument of §2.4 rests on a hypothesis:
Theorem 2.5 assumed the prover’s polynomials were fixed
before she saw . If she could choose
A commitment to a polynomial is a short string
Binding. Having published , the prover cannot later open it as two different polynomials; pins down . Committing first, then receiving , then opening, leaves her answering for the one polynomial she fixed in advance, the situation Theorem 2.5 assumed.
Hiding. The string reveals nothing about . This is what will let the proof be zero-knowledge, under “Zero knowledge: hiding the witness in Halo 2” in §4.
A polynomial commitment adds an evaluation proof: given and a
point , the prover can prove “
Encode of degree
the Pedersen vector commitment of the coefficient vector with blinder
and the inner-product argument does this in a logarithmic number of rounds, each halving the vectors, until the claim is trivial: the evaluation proof is group elements, and it needs no trusted setup, because the generators come from a public hash rather than from anyone’s secret (Crypto Guide, §“Polynomial commitment schemes”, the inner-product alternative). Halo 2 uses exactly this one polynomial commitment scheme and no other: the inner-product argument (the halo2 book, which the protocol specification names as the definition of the system, § 5.4.10.3, “Halo 2”; its Inner product argument chapter), on the Vesta curve, where the protocol specification places the Action statement’s proofs (protocol specification, § 5.4.9.6, “Pallas and Vesta”). The parameters, the generators and the deployed byte layout are given at the end of §3.
For the argument of this section the commitment must bind, so that the
prover answers for polynomials fixed before is drawn. A vector
commitment alone does not provide step 3 of the random-point check. The
only opening the Pedersen construction offers is the whole vector
together with its blinder,