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

1 Answer 1

1
$\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$
5
  • $\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$ Commented Oct 12, 2019 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$ Commented Oct 12, 2019 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$ Commented Oct 12, 2019 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$ Commented Oct 13, 2019 at 6:07
  • $\begingroup$ Updated answer reflecting this discussion in the Note part of the answer. $\endgroup$ Commented Oct 13, 2019 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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