4
$\begingroup$

I was attempting to figure out a way to implement the modulo operation as a set of gates in an Rank-1 Constraint System, detailed by Vitalik Buterin here

However, it occurred to me that maybe we don't actually need to break down each step of the calculation into an R1CS gate, as long we sufficiently implement gates which verify the prover performed the calculation correctly.

So instead of a complicated series of gates, the following calculations can be performed "behind the scenes" (assuming unsigned ints):

m = x % y
d = x // y

And the gates in our R1CS only need to consist of:

x = d*y + m
m < y

(I am aware that m < y is a tad complicated, but not nearly as complicated as actually performing the modulo operation itself)

Am I correct that we should only include the bare minimum constraints? Or are there some sort of security flaws when doing this and it is better to have a more complicated system of gates to validate every step of the calculation?

$\endgroup$
0
$\begingroup$

This is already explained in the linked Buterin blogpost. Essentially what you are trying to achieve here, ie. implementing a MOD "gate" in a zkSNARK is simply cannot be done efficiently. This is because that MOD is not supported in finite cyclic group arithmetic. If there is an efficient MOD gate, then by applying the Chinese Remainder Theorem, one could also break the Discrete Logarithm problem over said finite group.

More precisely, given $g^x$, if there is an efficient MOD gate, then it means that you can obtain $x \pmod{p_{0}}$ and $x \pmod{p_{1}}$ efficiently - for two arbitrarily chosen primes $p_{0},p_{1}$ - from $g^x$. Then by applying the Chinese Remainder Theorem, it is trivial to get $x$, hence Discrete Logarithm Problem could be solved efficiently.

Note: in your second approach, namely creating MOD gate with the following constraints: $$x = d*y + m \land m < y$$ would also require a single MOD, since a malicious prover could make $d*y$ overflow modulo the field modulus. This needs to be checked in the circuit, otherwise a false remainder could be proven correct.

$\endgroup$
  • $\begingroup$ Wrt. to your note: "would also require a single mod", but it's not an arbitrary modulus, it's just the field congruency; not an explicit modulus gate. Second, an honest prover would not overflow $d\cdot y$, since $d = x//y$. $\endgroup$ – Ruben De Smet Oct 12 '19 at 8:27
  • $\begingroup$ Indeed, you're right! The arithmetic circuits needs to make sure that 𝑑⋅𝑦 does not overflow modulo the field size, since a cheating prover could potentially prove false statements. $\endgroup$ – István András Seres Oct 12 '19 at 17:33
  • $\begingroup$ Is it possible to come up with two sets $(d,m)$ s.t. $d\cdot y + m=x \pmod p \wedge m<y$? Something inside tells me that should be unique, but that got me wondering. $\endgroup$ – Ruben De Smet Oct 12 '19 at 18:33
  • $\begingroup$ It is certainly possible if a malicious prover makes 𝑑⋅𝑦 overflow mod p, it would yield a different remainder m :( Therefore the circuit needs to make sure, that this never happens. $\endgroup$ – István András Seres Oct 13 '19 at 6:07
  • $\begingroup$ Updated answer reflecting this discussion in the Note part of the answer. $\endgroup$ – István András Seres Oct 13 '19 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.