Potential upgrade via plookups

[jon-chuang]

Plookups provide efficient bit decomposition. For instance, one can use lookup tables of size 2^13.

Furthermore, one can use RNS decomposition (using the modulus F and a power of 2 e.g. 2^256/2^384) to efficiently check the arithmetic as per https://hackmd.io/LoEG5nRHQe-PvstVaD51Yw?both

[burdges]

I've wondered about the RNS/CRT approach before, but never really pushed the mathematics. I'd always assumed you'd need at least four primes to do the reduction step in https://cr.yp.to/antiforgery/meecrt-20060914-ams.pdf likely meaning instantiating your SNARK separately over each prime. It's a cute idea to use a power of two there. :)

[jon-chuang]

Yes, it's a bit of a stroke of genius, fairly typical of Zac (from Aztec). (who used to do work on particle physics)

[weikengchen]

Lookup tables would be useful for bit decomposition of a few bits.

The challenge seems to be here: the current nonnative library targets at general R1CS and does not assume the upstream proving system to enable defining other constraints (here, beyond the R1CS, lookup constraints). Therefore, this technique would require the upstream proving system to be very flexible in being able to compose different languages of constraints (here, lookup arguments).

[jon-chuang]

Yes, @Pratyush and I discussed this and we think it may be possible to have gadgets target a more generalised constraint system, based on its capabilities. For instance, in this case, only the bit decomposition "gadget IR opcodes" requires being resolved. The rest of the circuit could possibly remain as R1CS. In the future, we could even make this more agnostic.

[weikengchen]

And also in this reign, it would be great if there is a more generalized constraint system + a more efficient bit testing protocol (which I don't know, but there could be), such that bit testing is done in another protocol.

Since much overhead in nonnative is bit testing, reducing the cost of bit testing is useful. And thinking about that bit testing is such a fundamental operation, and also R1CS is an overkill of it, there might be some potentials.