lookup argument

A lookup argument is a way to prove "this value appears in this table" without writing out a constraint for every possibility. Some operations are miserable to express as pure addition and multiplication gates — checking that a number fits in 8 bits, computing a bitwise XOR, or matching an EVM opcode to its behavior. Instead of arithmetizing the logic, you precompute a table of all valid rows and then merely prove that each value your circuit uses is one of those rows. For finite, enumerable relations this is dramatically cheaper than gate-by-gate constraints.

The classic construction is plookup (Gabizon and Williamson, 2020), which proves that one multiset of queried values is contained in a table by checking a randomized grand-product (permutation-style) polynomial identity — the same machinery PLONK already uses for its copy constraints. Later refinements like logUp recast containment as a sum of logarithmic-derivative fractions, and schemes such as cq make the prover's cost essentially independent of the table size, so even a giant table (every byte pair, or a full opcode set) becomes affordable. All of them reduce "is x in table T?" to a polynomial check the verifier can confirm cheaply.

Lookups are now indispensable to practical proving, especially zkEVMs. Range checks, byte decompositions, Keccak and SHA round functions, and opcode semantics are all handled by lookups rather than exploding the multiplication-gate count. This is why modern arithmetizations are described as "PLONKish with lookups" — the gate system plus lookup tables together make proving the messy, bit-twiddling parts of real machines tractable.