Lookup arguments: proving membership without scanning

Custom gates are one half of what makes PLONKish the right substrate for a verifiable database. This is the other half: lookup arguments. Where a custom gate expresses a relationship between cells, a lookup expresses a membership claim — "this value appears in that table" — and proves it in time that does not depend on how large the table is. For a database, that property is the difference between feasible and hopeless.

The problem lookups solve

Suppose a circuit needs to prove 0 ≤ amount < 2⁶⁴ — a range check, the heart of every SQL WHERE … BETWEEN. The naïve approach decomposes amount into 64 bits and adds a constraint per bit that each is 0 or 1, plus a recomposition constraint. That is dozens to hundreds of constraints for a single comparison. A query full of filters multiplies this into an unworkable circuit.

A lookup argument reframes the question. Precompute a table of all valid values (or, in practice, of all valid small "limbs" a value decomposes into). Then the circuit simply proves: the witnessed value is one of the rows of this table. No bit-by-bit decomposition, no per-bit constraints — one argument, regardless of whether the table has a thousand rows or a billion.

How it works, intuitively

The machinery (Plookup, and its successors logUp and the lookups built into Halo2) reduces "is x in table T?" to a polynomial identity over the multiset of looked-up values and the table. Informally:

• Collect every value the circuit looks up into a multiset L.
• Take the table as a multiset T.
• Prove, with a single permutation-style polynomial identity, that every element of L also appears in T — that L is a sub-multiset of T.

Because this is one identity over committed polynomials, its cost scales with the number of lookups performed, not the size of the table. A 64-bit range table can be enormous; checking a value against it is still one lookup. (In practice large tables are decomposed into smaller limb-tables to keep the committed table itself cheap — an engineering detail with real cost implications.)

 circuit witness            lookup table T (fixed, committed once)
 ──────────────            ─────────────────────────────────────
 amount = 142,837   ──┐     [ 0 .. 2^16 )   limb table
 dept_id = 7        ──┼──▶  [ valid dept ids ]
 status = 'active'  ──┘     [ allowed enums ]
      │
      ▼
 "every looked-up value ∈ T"   ← one polynomial identity

What lookups buy a verifiable database

Each maps to a relational operation that would otherwise dominate the circuit:

• WHERE x BETWEEN a AND b → a range lookup. The single most common predicate becomes the single cheapest check.
• WHERE x IN (…) → set-membership lookup against the value list.
• Enum / domain validation → lookup against the column's allowed-value table — proving data conforms to schema, in-circuit.
• JOIN key matching → tuple lookups bind matched rows across tables, complementing the permutation argument.
• Bitwise & comparison helpers → small precomputed operation tables replace expensive bit arithmetic.

This is why a modern verifiable-database circuit is, in practice, a careful interplay of custom gates (per-operator algebra) and lookups (membership and range). Neither alone is enough; together they are the PLONKish vocabulary that makes TPC-H-scale SQL provable.

The trade-offs

• Table commitment cost. The table itself must be committed. Naïvely committing a full 2⁶⁴ range is impossible; values are decomposed into limbs (e.g. four 16-bit pieces), checked against a small limb-table, and recombined. Limb size is a tuning knob — smaller tables, more lookups, vs. larger tables, fewer lookups.
• Lookup count drives proving time. As with gates, the art is minimizing how many lookups a query family needs.
• Static shape. The set of tables a circuit can reference is fixed at circuit-design time; dynamic predicates are handled by parameterising the witness, not the table.

Why it matters for the engagement

Lookups are where a lot of the fitting happens. Two institutions with the same query in the abstract — say, an AML threshold check — may have very different optimal arithmetizations depending on their data domains, value ranges, and enum sets. Choosing the right limb decomposition and table layout for that institution's data is concrete, measurable engineering work, and it is a large part of what an architecture assessment produces.

Get the lookup strategy right and a regulated query that looked computationally hopeless becomes a proof generated in seconds. Get it wrong and the same query never finishes. The difference is craft, not cryptography — which is precisely where a firm earns its keep.

What to read next

• Custom gates for SQL — the other half of PLONKish.
• Polynomial commitments — what the table and witness are committed with.
• How a verifiable query actually works — the full lifecycle.