# Lookup Table

The Lookup Table helps arithmetizing the lookups necessary for the split-and-lookup S-box used in the Tip5 permutation. It works in tandem with the Cascade Table. In the language of the Tip5 paper, it is a “narrow lookup table.” This means it is always fully populated, independent of the actual number of lookups.

Correct creation of the Lookup Table is guaranteed through a public-facing Evaluation Argument: after sampling some challenge $X$, the verifier computes the terminal of the Evaluation Argument over the list of all the expected lookup values with respect to challenge $X$. The equality of this verifier-supplied terminal against the similarly computed, in-table part of the Evaluation Argument is checked by the Lookup Table's terminal constraint.

## Base Columns

The Lookup Table has 4 base columns:

name | description |
---|---|

`IsPadding` | Indicator for padding rows. |

`LookIn` | The lookup input. |

`LookOut` | The lookup output. |

`LookupMultiplicity` | The number of times the value is looked up. |

## Extension Columns

The Lookup Table has 2 extension columns:

`CascadeTableServerLogDerivative`

, the (running sum of the) logarithmic derivative for the Lookup Argument with the Cascade Table. In every row, accumulates the summand`LookupMultiplicity / Combo`

where`Combo`

is the verifier-weighted combination of`LookIn`

and`LookOut`

.`PublicEvaluationArgument`

, the running sum for the public evaluation argument of the Lookup Table. In every row, accumulates`LookOut`

.

## Padding

Each padding row is the all-zero row with the exception of `IsPadding`

, which is 1.

# Arithmetic Intermediate Representation

Let all household items (🪥, 🛁, etc.) be challenges, concretely evaluation points, supplied by the verifier.
Let all fruit & vegetables (🥝, 🥥, etc.) be challenges, concretely weights to compress rows, supplied by the verifier.
Both types of challenges are X-field elements, *i.e.*, elements of $F_{p_{3}}$.

## Initial Constraints

`LookIn`

is 0.`CascadeTableServerLogDerivative`

has accumulated the first row with respect to challenges 🍒 and 🍓 and indeterminate 🧺.`PublicEvaluationArgument`

has accumulated the first`LookOut`

with respect to indeterminate 🧹.

### Initial Constraints as Polynomials

`LookIn`

`CascadeTableServerLogDerivative·(🧺 - 🍒·LookIn - 🍓·LookOut) - LookupMultiplicity`

`PublicEvaluationArgument - 🧹 - LookOut`

## Consistency Constraints

`IsPadding`

is 0 or 1.

### Consistency Constraints as Polynomials

`IsPadding·(1 - IsPadding)`

## Transition Constraints

- If the current row is a padding row, then the next row is a padding row.
- If the next row is not a padding row,
`LookIn`

increments by 1. Else,`LookIn`

is 0. - If the next row is not a padding row,
`CascadeTableServerLogDerivative`

accumulates the next row with respect to challenges 🍒 and 🍓 and indeterminate 🧺. Else,`CascadeTableServerLogDerivative`

remains unchanged. - If the next row is not a padding row,
`PublicEvaluationArgument`

accumulates the next`LookOut`

with respect to indeterminate 🧹. Else,`PublicEvaluationArgument`

remains unchanged.

### Transition Constraints as Polynomials

`IsPadding·(1 - IsPadding')`

`((1 - IsPadding')·(LookIn' - LookIn - 1))`

`+ IsPadding'·LookIn'`

`(1 - IsPadding')·((CascadeTableServerLogDerivative' - CascadeTableServerLogDerivative)·(🧺 - 🍒·LookIn' - 🍓·LookOut') - LookupMultiplicity')`

`+ IsPadding'·(CascadeTableServerLogDerivative' - CascadeTableServerLogDerivative)`

`(1 - IsPadding')·((PublicEvaluationArgument' - PublicEvaluationArgument)·(🧹 - lookup_output'))`

`+ IsPadding'·(PublicEvaluationArgument' - PublicEvaluationArgument)`

## Terminal Constraints

`PublicEvaluationArgument`

matches verifier-supplied challenge 🪠.

### Terminal Constraints as Polynomials

`PublicEvaluationArgument`

- 🪠