4
$\begingroup$

One thing I don't quite understand is how to naively handle division operation in rank-1 constraint systems (R1CS).

supposedly A.s * B.s - C.s = 0 allows you to perform any addition/subtraction/multiplication/division operations, but how do you actually perform division from multiplication gate in any of the SNARKs system? the only thing I can think of is to use multiplicative inverse of the value you want to divide as your input for B in the A*Bpart, so that A*B becomes A*B^-1 which is same as performing A/B

My question is how does the verifier know the input prover send to the division gate is the multiplicative inverse of B? it seems that the verifier would need to either trust the prover sending the correct input (there is no way to check that the prover is sending B^-1 or some other B'^-1 ), did I miss something here?

-edited My question is about how to build R1CS constraint on division. for example, how do I build a constraint matrix for (a*b)/(c*d) where a,b,c,d are inputs to an arithmetic circuit.

$\endgroup$

1 Answer 1

1
$\begingroup$

Well this question depends on what you mean by $\textit{division}$. R1CS is usually defined over a finite field $\mathbb{F}_p$, so constraints about modular inverses are quite easy to represent. On the other hand, if you're asking about integer division, which is not natively supported by finite field arithmetic, then this becomes more tricky.

Let me expand on this. I'll try to follow the notation used in Vitalik's popular post. In order to represent a modular inverse operation such as $x \cdot y^{-1} = z$, we could define two constraints in our flattened arithmetic circuit:

$\text{one = y}\cdot \text{y_inv}$

$\text{z = x}\cdot \text{y_inv}$

As you can see, we've introduced the extra variable $\text{y_inv}$ and added the constraint that $y \cdot y^{-1} = 1$ (i.e., the definition of modular inverse).

Now, you might instead be asking the question of how we perform integer division i.e., $\lfloor\frac{x}{y}\rfloor = z$, using finite field arithmetic? Recall that this is much different than taking modular inverses in $\mathbb{F}_p$.

As example, let's try $7 / 2$ in $\mathbb{F}_{11}$:

$7 / 2 = 7 \cdot 2^{-1} = 7 \cdot 6 = 42 = 9 \mod 11$, since $6$ is the modular inverse of $2$ in $\mathbb{F}_{11}$.

However, $\lfloor\frac{7}{2}\rfloor = 3$ (obviously) if we're talking about integer arithmetic. This more complex operation can be represented in $O(\log(p))$ R1CS gates using non-determinsitic advice e.g., by enforcing that $x = z \cdot y + r$ and $r < y$, where $r$ is provided by the prover.

$\endgroup$
3
  • $\begingroup$ Hi Zach, Thanks for taking your time, my question is about how to build R1CS constraint on division. you say that's easy but I just don't see how. for example, how do I build a constraint matrix for (ab)/(cd) where a,b,c,d are inputs to an arithmetic circuit. It seems to me that we are limited to use addition/subtraction and multiplication gates when constructing a arithmetic circuit (for any SNARK) $\endgroup$
    – acias
    Commented Oct 2, 2020 at 10:47
  • 1
    $\begingroup$ Using just (a,b,c,d) as inputs alone doesn't work so well. Refer to my answer above where I introduce the extra input y_inv. In your case you would want the inputs to be (a,b,c,d, c_inv, d_inv). Then you just use multiplication constraints to enforce the division operation by making sure that 1 = c * c_inv, and 1 = d * d_inv, and a * b * c_inv * d_inv = output. $\endgroup$ Commented Oct 2, 2020 at 14:56
  • $\begingroup$ that would make sense, thanks! $\endgroup$
    – acias
    Commented Oct 3, 2020 at 15:06

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.