In zkSNARKS, does R1CS require every step of the calculation, or just statements which confirm the calculation was performed correctly?

Question

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?

Answer 1

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.