Range Checks
A range-check is a common utility, asserting that a number is in some range [MIN, MAX]. It is important to keep in mind that you can make use of bit-decompositions to check for range [0, 2^n), which would be done by simply checking if a number is representable with n-bits.
Other zkDSLs often use lookup tables for range checks, which can be much cheaper than bit decompositions. Circom compiles to R1CS, which has no lookup tables, so we use bit decompositions instead.
AssertInRange
template AssertInRange(MIN, MAX) {
assert(MIN < MAX);
signal input in;
var b = nbits(MAX);
// find `in - MIN`:
// if `in > MIN` this is a b-bit value
// otherwise, it will underflow due to negation,
// and may be larger than MAX
component lowerBound = AssertBits(b);
lowerBound.in <== in - MIN; // e.g. 1 - 1 = 0 (for 0 <= in)
// find `in + 2^b - MAX - 1`
// if `in < MAX` this will result in a value less than `2^b - 1`
// ensuring that it is a b-bit value, otherwise this will be a value
// larger than b-bits
component upperBound = AssertBits(b);
upperBound.in <== in + (2 ** b) - MAX - 1; // e.g. 9 + (15 - 9) = 15 (for in <= 15)
}
Above is one way of doing a generic range check. Our approach here is to check:
in - MINis a b-bit valuein + 2^b - 1 - MAXis a b-bit value
where b is the minimum number of bits required to represent MAX. The nbits function is described within the bits section.
If in < MIN, the operation in - MIN will underflow and we will have a huge number, definitely not be b-bit representable (assuming a not-so-large MAX). As an edge case, if in == MIN we get 0, which is definitely b-bits.
If in > MAX, the operation in + 2^b - 1 - MAX becomes larger than 2^b - 1, which is not b-bit representable. As an edge case, if in == MAX we get 2^b - 1, which is the largest b-bit number.
Constraint Count
AssertInRange(MIN, MAX) decomposes two numbers into bits, where is the number of bits of MAX, so it has non-linear constraints. For example, AssertInRange(1, 9) has 8, and AssertInRange(0, 1000) has 20.