Lookup gates doesn't work if the lookup "input" is not a permutation of [0..N]

[bkomuves]

As I understand lookup gates are supposed to encode finite (small) input -> output mappings, the possible (input,output) pairs listed as table.

This is currently broken if input is not a permutation of the row indices.

To problem is in this line:

plonky2/plonky2/src/gates/lookup.rs

Line 200 in 356aefb

let (input, output) = self.lut[input_val.to_canonical_u64() as usize];

It seems that as an optimization, a "happy path" was included for the case i -> f(i), so that the witness generator doesn't have to traverse the whole table. However, that line looks up the LUT without checking whether the input value, now abused as an index, is in the range; therefore causing an out-of-index exception in the unhappy case.

Some further remarks:

• I couldn't make it work even after hacking around this problem, so there may be further issues (EDIT: this was user error, I thought I have to call builder.add_all_lookups() myself, but this is not the case. It resulted in some strange errors though...)
• I don't understand why lookup tables are limited to u16 -> u16. Surely there could be practical applications with larger numbers? (Here is an example: you want to rotate 32 bit words by a constant around, as in SHA256 for example. Decompose into lower and upper 16 bit words, rotate those with a lookup, then combine back)
• It would be nice to have a lookup example among the examples in the example subdirectory
• The "whitepaper" doesn't mention lookups at all (presumably because it was written before they were added); it should be updated to describe at least the core lookup protocol