Blind lookup polynomials

[lopeetall]

The lookup polynomials h_1, h_2, and z_2 need to be blinded.

(Apologies if this is a dupe issue. I thought this had been opened already but couldn't find it.)

[lopeetall]

Here is a proposal for blinding lookups using the lookup selector to "switch" the permutation argument between two states: checking queries against the public lookup table vs. checking queries against the query vector itself.

https://hackmd.io/_Q8YR_JLTvefW3kK92KOFg

This method comes at the cost of adding one field element to the proof. Comments desired!

EDIT: Unfortunately the above doesn't quite work because of an issue at the boundary of the padding and queries. I think it is salvageable by using a dummy value perhaps.

[lopeetall]

I've improved this argument so that it no longer has an issue at the boundaries, doesn't add to the proof size, and doesn't change the optimum evaluation choices for linearization.

The improved argument can be found here.

With this argument we no longer need to pad the query vector with an element from the table, except for the very first element. All other padding can be any field element.

If there aren't any errors in the argument and we feel satisfied with it, we will need to modify the code in the following places:

1. The first row of the table must be put as the first row of the circuit (but see the alternative layout section for other options)
2. 8 more blinding rows need to be added at the beginning of the circuit
3. We need to make sure that all lookup rows are consecutive and at the very end of the circuit (but see the alternative layout section for other options)
4. The computation of the query vector in src/proof_system/prover.rs becomes a simple compression of the rows in the circuit
5. The computation of the lookup permutation polynomial in src/proof_system/permutation.rs should be changed to the new argument
6. The quotient polynomial contribution in /src/proof_system/lookup.rs needs to change to the new argument
7. The ProverKey portion of the linearization polynomial in /src/proof_system/lookup.rs needs to change to the new argument
8. The VerifierKey portion of the linearization polynomial in /src/proof_system/lookup.rs needs to change to the new argument