A Proof as a Table
A Halo2 circuit is best understood as a long table. Each row represents a step in the
computation — the current in-memory state and the set of active instructions. A SNARK is
an efficient probabilistic check that at every row, the enabled instructions are correctly
applied to the current variables.
Let's look at a simple example. We have 3 advice columns (the prover's variables)
and 8 fixed columns (the circuit's instructions and parameters):
| Row | Advice | Fixed | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| \(w_l\) | \(w_r\) | \(w_o\) | \(q_r\) | \(q_l\) | \(q_o\) | \(q_c\) | \(q_m\) | \(q_\text{sha2}\) | \(q_\text{lookup}\) | \(t_\text{lookup}\) | |
| (...) | |||||||||||
| \(i-1\) | \(x_1\) | \(x_2\) | \(x_3\) | \(1\) | \(1\) | \(-1\) | \(\cdot\) | \(\cdot\) | \(\cdot\) | \(\cdot\) | \(\cdot\) |
| \(i\) | \(x_3\) | \(x_4\) | \(x_5\) | \(\cdot\) | \(\cdot\) | \(2\) | \(7\) | \(5\) | \(\cdot\) | \(\cdot\) | \(\cdot\) |
| \(i+1\) | \(x_1\) | \(x_3\) | \(x_6\) | \(\cdot\) | \(\cdot\) | \(\cdot\) | \(\cdot\) | \(\cdot\) | \(1\) | \(1\) | \(\cdot\) |
| (...) | |||||||||||
The wires \(w_l\), \(w_r\), \(w_o\) are the prover's left, right and output registers at each row. The 5 selector columns \(q_l, q_r, q_o, q_c, q_m\) enable arithmetic constraints; \(q_\text{sha2}\) enables a hash constraint; \(q_\text{lookup}\) triggers a membership check against the table \(t_\text{lookup}\). The following equations must hold at every row:
- \(\displaystyle q_l \cdot w_l + q_r \cdot w_r + q_o \cdot w_o + q_m \cdot w_l \cdot w_r + q_c = 0\)
- \(\displaystyle q_\text{sha2} \cdot \bigl(\text{sha2}(w_l,\, w_r) - w_o\bigr) = 0\)
- \(\displaystyle q_\text{lookup} \cdot w_l \in t_\text{lookup}\)
A selector set to 0 disables its constraint entirely. For instance, only at row \(i+1\) are \(q_\text{sha2}\) and \(q_\text{lookup}\) active, enforcing \(\text{sha2}(x_1, x_3) = x_6\) with \(x_1\) looked up in the table.
Columns
Columns are of two kinds. Fixed columns are baked into the circuit at design time
and are identical for every proof of the same circuit — they form the verification key.
Advice columns are the prover's workspace, committed to fresh at the start
of each proof.
Fixed Columns
Fixed columns encode the program. Their values are known to the verifier and are committed
once in the verification key. There are three roles a fixed column can play:
Selectors
A selector holds 0 or 1 at each row. Setting it to 1 activates the associated gate constraint at that row; 0 disables it entirely. A circuit may have many selectors, each switching a different rule on or off per step.
Lookup Tables
A table column holds a fixed set of allowed values defined at circuit creation time. Lookup arguments check that a wire value appears somewhere in the table — a range check, a set membership test, or a function table.
Fixed Parameters
Any constant embedded in the circuit: curve coefficients, hash round constants, domain parameters. Unlike selectors, these are not binary — they hold arbitrary field elements fixed by the designer for every proof.
Advice Columns
Advice columns are the prover's workspace. Their values are unknown at circuit-design time
and change with every proof. Each advice column produces one G1 commitment in the proof.
Wires
The primary variables of the circuit: inputs, intermediate values, and outputs the prover supplies. Each cell is checked by the active gate constraints at its row and may be copy-constrained to appear consistently in other rows.
Temporary Registers
Extra advice columns used to break complex expressions into simpler constraints, e.g., storing an intermediate product before it is used in a later gate. Often unconstrained by copy — they do not participate in the permutation argument, saving VK commitments.
Column Properties
Columns carry a key property that directly affects proof size and verifier cost. Arguments introduce a second one — rotation sets — covered in the next section.
| Property | Description |
|---|---|
| copy-constrained | Copy-constraining a column means its cells may be equated with cells in other columns or rows — this is how the same variable (e.g., \(x_1\) at rows \(i-1\) and \(i+1\)) is enforced to hold the same value across the table. Each copy-constrained column participates in the permutation argument and contributes one permutation polynomial, adding one G1 commitment to the VK. Advice columns are usually copy-constrained; unconstrained ones act as temporary registers. |
Arguments
Arguments are the assertions the proof must satisfy. Each argument type targets a different
property of the circuit — polynomial constraints, copy consistency, range membership — and
may need to read cells from more than the current row. Together, they determine the number
of commitments, evaluations, and scalar operations in the proof.
Rotation Sets
When evaluating a constraint at row \(i\), an argument may also query cells at \(i-1\),
\(i+1\), or the last row. The set of relative row offsets a column is queried at is its
rotation set.
The KZG polynomial commitment scheme opens all columns simultaneously, but columns with different rotation sets require separate multi-opening proofs (each producing one additional Q commitment and one π commitment in the proof). Minimising the number of distinct rotation sets across all columns directly reduces proof size and the number of MSM calls during verification.
The KZG polynomial commitment scheme opens all columns simultaneously, but columns with different rotation sets require separate multi-opening proofs (each producing one additional Q commitment and one π commitment in the proof). Minimising the number of distinct rotation sets across all columns directly reduces proof size and the number of MSM calls during verification.
Point Sets (derived)
// Distinct rotation groups across all // column queries — one KZG multi-open // proof per group. nb_point_sets ≈ 1 // {curr} — always present + (cc > 0 || lkp > 0 ? 1 : 0) // {curr, next} + (perm_chunks > 1 ? 1 : 0) // {curr, next, last} + (lkp > 0 ? 1 : 0) // {prev, curr}
Cost Impact
Each distinct point set adds: 1 Q commitment (proof) 1 π commitment (proof) And one extra MSM group during verification — so keeping columns on the same rotation set (or a subset of another set) is the primary lever for reducing both proof size and verifier cost.
Types
Four argument types appear in a Halo2 KZG proof. Each is present when the circuit
requires it; their contributions to commitments and evaluations are additive.
Gates
Polynomial constraints over
advice and fixed columns.
Gates add no commitments or
evaluations to the proof —
their cost is scalar operations
only (field arithmetic during
argument recomputation).
Permutation
Enforces copy constraints: cells equated across rows and columns hold the same value. Adds per chunk of cc columns: ⌈cc/(deg−2)⌉ commits cc + 3×⌈cc/(deg−2)⌉ − 1 evals Requires degree ≥ 3.
Lookups
Checks that wire values appear in a fixed table. Per lookup argument: 3 commits (Z, A_perm, S_perm) 5 scalar evaluations Requires degree ≥ 5.
Trashcans
Range arguments that bound intermediate values in foreign-field arithmetic. Per trashcan: 1 commitment 1 scalar evaluation Requires degree ≥ 4. Multiple chips may share one trashcan column (deduplicated).
Aggregation
Each argument type may carry several equations, or constraints. For instance, a
gate argument covers every gate polynomial in the circuit; a lookup argument has its own
set of auxiliary constraints. Within a single argument, all its equations are first
batched into one combined check using a random challenge — so adding more constraints to
an argument increases scalar operation cost but does not add extra commitments or
evaluations.
Once each argument is internally batched, their contributions to proof size are accumulated across all argument types: gate scalar ops are summed, lookup and trashcan counts grow additively, and permutation chunks scale with the total number of copy-constrained columns. The degree of the circuit is the maximum required by any active argument type or chip gate.
Once each argument is internally batched, their contributions to proof size are accumulated across all argument types: gate scalar ops are summed, lookup and trashcan counts grow additively, and permutation chunks scale with the total number of copy-constrained columns. The degree of the circuit is the maximum required by any active argument type or chip gate.
Degree (derived)
degree = max( degree_hint, cc > 0 ? 3 : 0, // permutation nb_lookups > 0 ? 5 : 0, // PlookUp nb_trash > 0 ? 4 : 0, // trashcan max chip degree // gate polynomials )
Total Proof Commitments
nb_commitments = nb_advice // one per advice col + ⌈cc / (degree − 2)⌉ // permutation + nb_trash // trashcans + 1 + (degree − 1) // vanishing + 3 × nb_lookups // PlookUp + 2 // H2MO PCS: F and π
Chips
A chip is a low-level, reusable module that packages a set of gate, lookup, and trashcan
arguments over a fixed subset of columns. Chips are the unit of composition: a circuit is
built by combining chips, whose columns and arguments are then merged before any size
computation takes place.
Cost Insight
The two main levers for reducing proof size and verifier cost are the number of
arguments and the number of distinct rotation sets. Chips that are defined over the
same columns — or a subset of another chip's columns — and that query those columns at
the same relative rows (same or subset rotation set) are especially cheap to combine:
their arguments share the same KZG point sets, and their columns do not add new
multi-opening proofs. Chips with disjoint column footprints or new rotation sets each
force at least one extra point set in the proof.
Column Aggregation
When multiple chips are used together, their columns are merged before any size
computation. The merging rules differ between advice and fixed columns:
Advice Columns — max-count merge
Chips declare groups of advice columns. Within a group, the chip with the most columns wins; the rest are absorbed. Example: JubJub (9 cols) absorbs Arith (5 cols). Combined count stays 9, not 5 + 9 = 14. Extra advice columns (--nb-advice) are appended after the merged set.
Fixed Columns — exclusive or shared
Fixed columns are either shared or exclusive. Shared columns are deduplicated: if two chips declare the same shared column, it appears once in the circuit. Exclusive columns are always summed: each chip instance adds its own copy. Lookup table columns are handled separately — see Lookup Tables.
Lookup Tables
Lookup tables are fixed columns whose values define a set of allowed inputs. They are
referenced by lookup arguments — a chip's lookup gate asserts that one of its wires
belongs to a particular table. Unlike ordinary fixed columns, lookup table columns have
some notable properties in Halo2.
Shared Across Chips
A single table can be referenced by lookup arguments from different chips. When chips are combined, tables are unioned: if two chips declare the same table, it appears only once in the final circuit. This deduplication is independent of the advice and fixed column merging.
One Commit per Column
Unlike gate fixed columns — which could in principle share commitments — each lookup table column receives its own G1 commitment in the VK. The total lookup table footprint is: nb_table_cols = union of all table columns across active chips Each adds 48 bytes to the VK.
No Concatenation
Tables of the same width could
theoretically be concatenated into
one taller table, reducing the
column count to 1.
Halo2 does not perform this
optimisation: each table column is
committed independently, even if
two tables have identical structure.