Lookups

Lookup instructions require their logic to have some structure to apply the prefix-suffix sumcheck, as described in Appendix A of Proving CPU Executions in Small Space. That is:

• The lookup table must have an MLE that is efficiently evaluable by the verifier. The JoltLookupTable trait encapsulates this MLE.

• The lookup index can be split into a prefix and suffix, such that MLEs can be evaluated independently on the two parts and then recombined to obtain the desired lookup entry.

• Every prefix/suffix MLE is efficiently evaluable (constant time) on Boolean inputs.

JOLT Atlas reuses some of the instruction from the original JOLT codebase and adds new ones applying the same paradigm.