Proof PeaksISSUE #20 of 38

lookup arguments · plookup · logup

ZeekaVSThe Collision

Zeeka saysA lookup argument proves that every value a circuit uses appears in a precomputed table — making range checks, bit operations, and S-boxes nearly free.

Some operations are painful to express as add/multiply constraints — range checks ("this is a valid byte"), bitwise XOR, hash S-boxes. A lookup argument sidesteps that: precompute a table of all valid values and prove that each query the circuit uses is a member of that table, rather than re-deriving it with constraints.

Constructions like plookup and logUp verify membership with a single multiset check, so even a 2²⁵⁶-entry table adds little proving cost. The demo proves four byte values are in a 0…255 range table and rejects an out-of-range 300 — the same trick that makes range checks and bit-ops almost free in real circuits.

Power-ups you unlock

Prove query values are members of a fixed table
Replaces expensive in-circuit logic (range checks, XOR, etc.)
plookup and logUp are the common constructions
Verified with a multiset check, not value-by-value comparison
Tables can be huge yet add little proving cost

The Collision attacks — common mistakes

Reimplementing a range check with constraints instead of a lookup
Forgetting to constrain that queries actually use the table
Tables not committed to, so a prover can swap them
Assuming a lookup hides which entries were used (it need not)

Boss battleProve four byte values are all in a 0..255 table via membership, and show a value of 300 is rejected.

Example code

<!doctype html><html><head><meta charset="utf-8"></head>
<body style="background:#06040d;color:#e6e0ff;font-family:monospace;padding:20px"><pre id="o"></pre>
<script>
// lookup argument: prove every query is IN a table (no in-circuit recompute).
const table = Array.from({length:256}, (_,i)=>i);   // valid bytes 0..255 (range table)
const tableSet = new Set(table);
const queries = [0, 42, 200, 255];
const allIn = queries.every(q => tableSet.has(q));
document.getElementById('o').textContent = [
  'table = bytes 0..255   queries = [' + queries.join(', ') + ']',
  'all queries ∈ table? ' + allIn + '   → range-check 0..255 proven by LOOKUP',
  'sneaky query 300 ∈ table? ' + tableSet.has(300) + '   → rejected',
  'a real argument (plookup/logUp) proves this with a multiset check, not 256 compares',
  'lookups make range checks & bit-ops nearly free in the circuit'
].join('\n');
</script></body></html>

▶ Open the interactive comic issue

‹ Plonk · Universal Setup · Custom Gates Halo2 · Recursive Accumulation ›