search

Consensys / gnark

gnark is a fast zk-SNARK library that offers a high-level API to design circuits. The library is open source and developed under the Apache 2.0 license
https://hackmd.io/@gnark
Apache License 2.0
1.43k stars 368 forks source link

Can Plonk use R1CS instead of SparseR1CS to reduce Constraint size? #997

Closed ggq89 closed 8 months ago

ggq89 commented 10 months ago

We are currently working on a ZKP project using gnark.

After we wrote the circuit, we were surprised to find the following: the size of the constraint system compiled with SparseR1CS is about 4 times that of R1CS!

Due to special reasons, we can currently only choose to use plonk as the proof system, but we found that plonk can only use SparseR1CS, so can new features be added to allow plonk to use R1CS to reduce the number of constraints?

ThomasPiellard commented 9 months ago

hi @ggq89 , currently in gnark plonk supports only sparseR1CS which corresponds to the plonk constraints described in the plonk paper. The number of constraints grows faster in sparseR1CS if you have a lot of linear combinations in your circuit (e.g. expressions of the form ∑ᵢ aᵢ Xᵢ where the aᵢ are constants and Xᵢ are wires ) because in a R1CS the size of a linear combination in not bounded, whereas it is in a sparse R1CS, so the linear expression needs to be split in a lot of sub constraints. To lower the number of constraints in a sparseR1CS in your case, using custom gates is probably the way to go, where you could use larger (but still bounded) linear expressions. But it comes with the cost of making the permutation argument more complex (you'll need a bigger fft domain compared to the size of the circuit).