Consider storing a pointer to the value of a coefficient in the final R1CS object

[ValarDragon]

Loopring put out a blog post earlier today discussing optimizations they used (https://medium.com/loopring-protocol/zksnark-prover-optimizations-3e9a3e5578c0)

One interesting memory reduction optimization is noting that for ~all circuits of interest, there are not that many distinct values of coefficients. So instead of storing one field element for each coefficient, you can instead make a list of unique coefficients used in you're circuit, and then make the coefficients in the end R1CS constraints be an index into this list. This drops the memory to store the coefficient from 32 bytes to 8 bytes. (A 1 word index)

8 bytes is enough to store an index for 2^24 unique coefficients, if for some reason the library had to be able to support R1CS constraints with more unique coefficients, then 16 bytes would be more than enough.

This optimization could be taken when producing the final R1CS object after optimizations, that gets passed into the prover.

This should be a notable reduction in the memory size of Groth16, less so for Fractal/Marlin due to them requiring degree K polynomials. This may increase proving times though, as you have to read the value of the coefficient from the pointer, though this is hopefully in L1 cache.

Similarly, I believe that this observation also suggests a better Fractal/Marlin arithmetization for circuits of interest. (Eliminating the preprocessed val oracles in exchange for more (relatively cheap) verifier work)

[Pratyush]

This is essentially a string interning optimization, right?

[ValarDragon]

Yes! (Didnt know there was a term for this)

[Pratyush]

(I only know of this because I spend too much time on the rust-lang issue tracker 😅)