UltraPLONK Arithmetization

The arithmetization used by Halo 2 comes from PLONK, or more precisely its extension UltraPLONK that supports custom gates and lookup arguments. We'll call it UPA (UltraPLONK arithmetization).

The term UPA and some of the other terms we use to describe it are not used in the PLONK paper.

UPA circuits are defined in terms of a rectangular matrix of values. We refer to rows, columns, and cells of this matrix with the conventional meanings.

A UPA circuit depends on a configuration:

  • A finite field , where cell values (for a given statement and witness) will be elements of .

  • The number of columns in the matrix, and a specification of each column as being fixed, advice, or instance. Fixed columns are fixed by the circuit; advice columns correspond to witness values; and instance columns are normally used for public inputs (technically, they can be used for any elements shared between the prover and verifier).

  • A subset of the columns that can participate in equality constraints.

  • A polynomial degree bound.

  • A sequence of polynomial constraints. These are multivariate polynomials over that must evaluate to zero for each row. The variables in a polynomial constraint may refer to a cell in a given column of the current row, or a given column of another row relative to this one (with wrap-around, i.e. taken modulo ). The maximum degree of each polynomial is given by the polynomial degree bound.

  • A sequence of lookup arguments defined over tuples of input expressions (which are multivariate polynomials as above) and table columns.

A UPA circuit also defines:

  • The number of rows in the matrix. must correspond to the size of a multiplicative subgroup of ; typically a power of two.

  • A sequence of equality constraints, which specify that two given cells must have equal values.

  • The values of the fixed columns at each row.

From a circuit description we can generate a proving key and a verification key, which are needed for the operations of proving and verification for that circuit.

Note that we specify the ordering of columns, polynomial constraints, lookup arguments, and equality constraints, even though these do not affect the meaning of the circuit. This makes it easier to define the generation of proving and verification keys as a deterministic process.

Typically, a configuration will define polynomial constraints that are switched off and on by selectors defined in fixed columns. For example, a constraint can be switched off for a particular row by setting . In this case we sometimes refer to a set of constraints controlled by a set of selector columns that are designed to be used together, as a gate. Typically there will be a standard gate that supports generic operations like field multiplication and division, and possibly also custom gates that support more specialized operations.