Integer Division
Integer division returns the quotient of two numbers, rounded down, e.g. . This is different from the division in a prime field, where is the field element that gives 7 when multiplied by 2.
IntDiv
template IntDiv(n) {
// ensures that `quot * in[1] + rem` can not wrap around the field
assert(n <= 125);
signal input in[2];
signal output out;
// divisor must be non-zero
signal is_non_zero <== IsZero()(in[1]);
0 === is_non_zero;
// compute the quotient and remainder outside the circuit
var quot_hint = in[0] \ in[1];
var rem_hint = in[0] % in[1];
signal quot <-- quot_hint;
signal rem <-- rem_hint;
// quotient & remainder must be n-bit numbers, otherwise a dishonest prover can
// pick a "negative" remainder (a large field element) that still passes the
// `rem < in[1]` check, or a quotient that is a field division `in[0] / in[1]`
_ <== Num2Bits(n)(quot);
_ <== Num2Bits(n)(rem);
// constrain the division operation
// in[0] / in[1] is defined as the unique pair (q, r) s.t.
// in[0] = in[1] * q + r and 0 <= r < |in[1]|
in[0] === quot * in[1] + rem;
component remIsLess = LessThan(n);
remIsLess.in <== [rem, in[1]];
remIsLess.out === 1;
out <== quot;
}
Doing integer division within a circuit is more costly than what one might one expect! Consider two -bit numbers and . An integer division implies the following equation:
where is the quotient, and is the remainder such that . As an example, consider the division . We have:
giving us the quotient and remainder . Notice that if we allowed , we could have:
which would be wrong! This is why we constrain the remainder with LessThan, to ensure .
However, that check alone is not enough. Remember that we are working in a prime field, where a “negative” number such as is actually a very large number . Consider the following:
This is a quotient with a remainder , which is wrong since should give . Is ? It should not be in the field, as is a very large number there; however, LessThan(n) is only correct for -bit inputs! It computes , which is an -bit number with its ’th bit unset, so it says that . A dishonest prover could then claim that .
To prevent this, we range-check both the quotient and the remainder using Num2Bits(n):
- With , the remainder can not be “negative” anymore, and
LessThan(n)can safely check . - With , the quotient can not be a field element like , which would satisfy in the field for any .
Finally, we must make sure that can not wrap around the field, otherwise the equation would only hold “modulo ” instead of over the integers. As and are -bit numbers, and can be at most bits (otherwise LessThan fails), the result is less than . The assert(n <= 125) ensures that this is less than the prime of BN254, which is around .
With these checks, the circuit has a unique solution for given and : the quotient and remainder of the usual integer division.
Constraint Count
IntDiv(n) has non-linear constraints, e.g. 50 for 16-bit numbers. Almost all of them come from the bit decompositions: the two range checks of the quotient & the remainder, and the -bit decomposition within LessThan.