Plookup

Plookup allows us to check if witness values belong to a look up table. This is usualy useful for reducing the number of constraints needed for bit-wise operations. So in the rest of this document we’ll use the XOR table as an example.

XOR table

First, let’s define some terms:

  • lookup table: a table of values that means something, like the XOR table above
  • joint lookup table: a table where cols have been joined together in a single col (with a challenge)
  • table entry: a cell in a joint lookup table
  • single lookup value: a value we’re trying to look up in a table
  • joint lookup values: several values that have been joined together (with a challenge)

A joint lookup table looks like this, for some challenge :

joint lookup table

Constraints

Computes the aggregation polynomial for maximum lookups per row, whose -th entry is the product of terms:

for .

  • is the -th entry in the table
  • is the -th lookup in the -th row of the witness

For every instance of a value in and , there is an instance of the same value in

is sorted in the same order as , increasing along the ‘snake-shape’

Whenever the same value is in and , that term in the denominator product becomes

this will cancel with the corresponding looked-up value in the witness

Whenever the values and differ, that term in the denominator product will cancel with some matching

because the sorting is the same in and .

There will be exactly the same number of these as the number of values in if only contains values from . After multiplying all of the values, all of the terms will have cancelled if is a sorting of and , and the final term will be because of the random choice of and , there is negligible probability that the terms will cancel if is not a sorting of and

But because of the snakify:

  • we are repeating an element between cols, we need to check that it’s the same in a constraint
  • we invert the direction, but that shouldn’t matter

FAQ

  • how do we do multiple lookups per row?
  • how do we dismiss rows where there are no lookup?