Expanded and Paraphrased Explanation: PLONKish Arithmetization

The arithmetization approach used in Halo 2 is derived from the PLONK protocol, specifically from its advanced version, UltraPLONK, which includes support for custom gates and lookup arguments. For simplicity, we refer to this approach as "PLONKish."

Defining PLONKish Circuits

PLONKish circuits are represented by a rectangular matrix of values, where the conventional definitions of rows, columns, and cells apply. Here's how these circuits are configured and utilized:
Configuration Elements:

• Finite Field (F): All cell values within the matrix (pertaining to a specific statement and witness) are elements of this finite field F.
• Matrix Columns: The number of columns in the matrix is specified, with each column categorized as one of the following:
  • Fixed Columns: Values are predetermined by the circuit.
  • Advice Columns: These correspond to witness values.
  • Instance Columns: Typically used for public inputs, though they can also hold any shared elements between the prover and verifier.
  • Equality Constraints: A subset of columns is designated for equality constraints.
  • Maximum Constraint Degree: Defines the highest degree for constraints.
  • Polynomial Constraints: These are multivariate polynomials over F that must equal zero for each row. Variables in these constraints can refer to cells in the current row or cells in other rows (considering wrap-around, i.e., modulo n). The degree of each polynomial is limited by the maximum constraint degree.
  • Lookup Arguments: These are defined over tuples of input expressions (also multivariate polynomials) and table columns.

Additional Circuit Definitions:

• Number of Rows (n): The matrix has n rows, where n must be the size of a multiplicative subgroup of F×, typically a power of two.
• Equality Constraints: Specifies that certain cells must have equal values.
• Fixed Column Values: The values for fixed columns at each row.

Generating Keys

From a circuit description, two types of keys are generated:

• Proving Key: Used in the proving process.
• Verification Key: Used in the verification process.

These keys are crucial for the operations involved in proving and verifying computations within the circuit.

Configuring Constraints

In PLONKish circuits, the configuration often includes polynomial constraints controlled by selectors in fixed columns. For example, a constraint qi⋅p(...)=0q_i \cdot p(...) = 0qi​⋅p(...)=0 can be deactivated for a specific row i by setting qi=0q_i = 0qi​=0. This mechanism allows for a flexible and efficient constraint management system.

• Selectors and Gates: Constraints can be grouped and controlled by selectors, forming gates. These gates may include:
  • Standard Gates: Support basic operations like field multiplication and division.
  • Custom Gates: Support specialized operations tailored to specific needs.

Deterministic Process

Despite the ordering of columns, polynomial constraints, lookup arguments, and equality constraints not affecting the circuit's functionality, specifying this order is essential. It ensures that the generation of proving and verification keys is a deterministic process, leading to consistent and repeatable results.

In summary, PLONKish arithmetization provides a robust framework for constructing and managing circuits with complex constraints and operations, enhancing the flexibility and efficiency of cryptographic protocols like Halo 2.