This section constructs the evaluation domains on which polynomial proof
systems of the kind underlying Halo 2 and Zcash Orchard encode computations,
and the fast Fourier transform on them. Such a proof system records an
-step computation as a table over a finite field, one column per
register and one row per step, and convinces a verifier that every row
follows from its predecessor without the verifier replaying the
computation: by Lagrange interpolation (5.30)
each column is the value table on fixed points of a polynomial of
degree less than , so conditions on the table become polynomial
identities, checkable at a single random point by the Schwartz–Zippel
lemma (5.45). The powers of a
primitive -th root of unity form a point set on which conditions on
every row, shifts to the next row and the polynomials attached to the set are
cheap to evaluate, and on which conversion between values and
coefficients, and polynomial multiplication, cost far fewer than the
field operations of the schoolbook methods. Such a root exists in
exactly when
Throughout, denotes a field. When is to be finite, the
notation denotes the field with elements (so is a
prime power, 6.10); when we intend a prime
field specifically we write . The multiplicative group of nonzero
elements is
Let be a field and
for the set of all -th roots of unity in .
Since
The set is a finite subgroup of of order at most .
The bound
An element
The order is the least positive integer with
The group-theoretic term “generator of ” and the
polynomial term “primitive
Let
If
is a cyclic group of order exactly , and these powers are pairwise distinct.
Over the complex numbers a primitive -th root of unity always
exists, namely
The multiplicative group of a finite field is cyclic of
order
Let be a finite field and
The field contains a primitive -th root of unity if
and only if
When
Let be a generator of , which is cyclic of order
() Suppose is a primitive
-th root of unity in . Then
() Suppose
using the order-of-a-power formula
(Corollary 3.23) together with
Count. In the cyclic group
(On the coprimality hypothesis. The condition
The proof shows that for a finite field the statement reduces to
has a primitive -th root of unity
Take
For the fast algorithms below, should be a power of two, or at
least smooth—a product of small primes, ideally with many
factors of two. By 9.7, a primitive
-th root of unity exists exactly when
Let be a field containing a primitive -th root of unity . The evaluation domain of order is the multiplicative subgroup
a cyclic group of order by 9.6. We
index its elements as
The vanishing polynomial (or zerofier) of is
On a generic -point set the vanishing polynomial (5.33) is a product of linear factors with no simpler form; on the group it reduces to a binomial.
With
Moreover is separable: it has distinct roots and
Every
For separability, the formal derivative is
The proof shows that
Substitute
using 9.13 for the middle equality. The
constant is
so distinct cosets give distinct constants . □
Let be a field,
Write
In the difference
Since
If
For
Call two vectors in orthogonal when their standard
inner product (8.21) vanishes. For each frequency
let
Since has exactly points, values on determine polynomials of degree less than (5.20); the basis adapted to values on is the Lagrange basis of §5.7.
The polynomials
they form a basis of , and they give the unique
interpolant: for any data
is the unique element of with
Each is well defined and of degree
The root-count step recurs and is called the root-count device:
two polynomials of degree
On a generic point set the Lagrange polynomials admit no closed form simpler than the defining product; on the group they are expressed through the vanishing polynomial.
For
In particular, dividing out one linear factor and scaling yields all
Lagrange polynomials from the single polynomial
Fix . From 9.13,
which is exactly the numerator of in
9.20. It remains to evaluate the
denominator
—the derivative at a simple root equals the product of the
differences to the other roots, the computation already made for simple
roots in the proof of 5.40. Concretely
using
as claimed. □
The closed form gives the barycentric interpolation formula on
a compact form. Writing
Evaluating at a point
The Lagrange basis polynomials for satisfy
An element of is described by its coefficients or by its values on ; passage between these two coordinate systems is a linear isomorphism, the specialisation to of the evaluation isomorphism for general nodes in 5.32.
The evaluation map on is the -linear map (8.18)
Linearity is immediate from
The evaluation map is a vector-space isomorphism. Its inverse is the interpolation map
That is,
Both maps are linear and act between spaces of the same finite
dimension , so verifying one composition would suffice (a
one-sided inverse makes injective, hence surjective by
rank–nullity, 8.19); we verify both. For
In coordinates, is given by a matrix, which identifies
evaluation on with the Fourier transform. Matrix notation is fixed
as follows: an
Let
—rows indexed by the evaluation point , columns by the
power —represents , so that
The matrix of 9.28 is invertible, with
Equivalently,
First,
By 9.16 this sum is if
The map , read as the matrix , is the discrete Fourier transform over a finite field rather than over ; since it involves no analytic structure (no complex exponentials, no convergence), it is called the number-theoretic transform.
Let be a primitive -th root of unity in . The
number-theoretic transform (NTT) sends the coefficient vector
of a polynomial to its value vector on : it is the evaluation map
written in coordinates. Explicitly, the NTT of
each entry being the value at of the polynomial with coefficients . The inverse number-theoretic transform is interpolation—the recovery of the coefficients from the values—and by 9.29 it too is a single explicit sum:
The NTT has the convolution property of the classical DFT, the basis of
fast polynomial multiplication. The coefficients of a product are a
convolution: with
For
i.e. pointwise multiplication of value vectors corresponds to
polynomial multiplication. Equivalently, writing
so the NTT turns convolution into entrywise multiplication.
The first identity is the statement that evaluation at is a ring
homomorphism
The convolution statement is proved in three steps: (i) multiplication in
Next consider the map
9.32 reduces multiplying two
degree-
In , the element
Computing
Suppose
so that
| (7) | ||||
| (8) |
Thus the length- NTT of reduces to two length- NTTs (of the even and odd coefficient subsequences, over the domain ) plus extra operations.
Equations
(7)–(8)
constitute the butterfly: from the two subtransform outputs
The recursion is exactly 9.35: a length-
transform calls two length- transforms (on the even and odd
coefficient subsequences) and combines them with butterflies of
operations each, for the overhead. Unrolling, with
Divide by and set
Fast transforms apply when is smooth and the field contains a
primitive -th root of unity, that is,
Take
and the butterflies give
(Outputs and
This subsection states how the preceding results are used in Halo 2,
the proof system of Orchard, which encodes a computation as polynomial
identities on the evaluation domain
Witnesses as evaluations on . A prover lays out the
trace of a computation as the values of one or more polynomials on
the points of . By 9.27 this is
the same data as a polynomial of degree
Constraints as divisibility by . “Constraint
polynomial holds on every row” means vanishes on all of
, which by 9.13 means exactly that
Lagrange selectors. The Lagrange polynomials of
9.20 are selectors: is
on row and elsewhere
(9.21), so boundary and instance
constraints (e.g. “the first row equals the public input”) become
Group structure for permutations and shifts. Because
is a cyclic group
(9.11), multiplication by is the
cyclic “next-row” shift
Smoothness for speed. Provers manipulate polynomials of
size (often after enlarging the domain by a small constant
factor for low-degree testing). Transforms between representations,
multiplications and coset evaluations are computed by NTTs, which by
9.37 cost instead of
(at the sizes used in practice, the difference between
feasible and infeasible computation), provided is smooth and
contains a primitive -th root of unity. By
9.7 that requires