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 , the verifier computes the terminal of the Evaluation Argument over the list of all the expected lookup values with respect to challenge . 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.
Main Columns
The Lookup Table has 4 main 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. |
Auxiliary Columns
The Lookup Table has 2 auxiliary columns:
CascadeTableServerLogDerivative
, the (running sum of the) logarithmic derivative for the Lookup Argument with the Cascade Table. In every row, accumulates the summandLookupMultiplicity / Combo
whereCombo
is the verifier-weighted combination ofLookIn
andLookOut
.PublicEvaluationArgument
, the running sum for the public evaluation argument of the Lookup Table. In every row, accumulatesLookOut
.
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 .
Initial Constraints
LookIn
is 0.CascadeTableServerLogDerivative
has accumulated the first row with respect to challenges 🍒 and 🍓 and indeterminate 🧺.PublicEvaluationArgument
has accumulated the firstLookOut
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 nextLookOut
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
- 🪠