Constant Comparisons
Circomlib comes with a more efficient method when we are comparing one signal with another constant. In this section, we will explain the constant-comparison method along with several of its usages.
These methods depend on the prime field used within the circuit, and therefore re-using these same circuits may cause bugs due to hard-coded values in other prime fields!
Note that these circuits take the bits of a number as input, but do not constrain them to be bits; the caller must ensure that, e.g. by obtaining them from Num2Bits.
CompConstant
template CompConstant(constant) {
signal input in[254];
signal output out;
// The input is compared with the constant pair-by-pair, i.e. as 127 base-4 digits.
// At pair i, we add:
// a_i = 2^i if the signal pair is LESS than the constant pair
// b_i = 2^128 - 2^i if the signal pair is GREATER than the constant pair
//
// Note that b_i is -2^i in 128-bit two's complement, so modulo 2^128 the sum is:
// (sum of 2^i over "less" pairs) - (sum of 2^i over "greater" pairs)
// The most-significant differing pair outweighs all lower ones combined
// (2^i > 2^(i-1) + ... + 1), so its sign is the sign of the sum, just like
// ordinary magnitude comparison.
var a = 1;
var b = (1 << (128)) - 1;
var sum = 0;
var bit_value = 1;
signal parts[127];
signal out_bits;
for (var i = 0; i < 127; i++) {
// Extract the i-th 2-bit digit of the constant (bit positions i*2 and i*2+1)
var constant_lsb = (constant >> (i*2)) & 1;
var constant_msb = (constant >> (i*2 + 1)) & 1;
// Extract the i-th 2-bit digit of the input signal
var in_lsb = in[i*2];
var in_msb = in[i*2 + 1];
// part_bit_a: 1 iff the signal's 2-bit digit >= the constant's 2-bit digit
// part_bit_b: 1 iff the signal's 2-bit digit > the constant's 2-bit digit
//
// These are computed using boolean arithmetic on the input bits.
// Note: x + y - x*y = OR(x, y), and x*y = AND(x, y).
var part_bit_a;
var part_bit_b;
/**/ if ((constant_msb == 0) && (constant_lsb == 0)) {
// constant pair = 0: signal >= 0 is always true; signal > 0 iff any bit set
part_bit_a = 1;
part_bit_b = in_msb + in_lsb - in_msb*in_lsb; // OR(msb, lsb)
}
else if ((constant_msb == 0) && (constant_lsb == 1)) {
// constant pair = 1: signal >= 1 iff any bit set; signal > 1 iff msb set
part_bit_a = in_msb + in_lsb - in_msb*in_lsb; // OR(msb, lsb)
part_bit_b = in_msb;
}
else if ((constant_msb == 1) && (constant_lsb == 0)) {
// constant pair = 2: signal >= 2 iff msb set; signal > 2 iff both bits set
part_bit_a = in_msb;
part_bit_b = in_msb*in_lsb; // AND(msb, lsb)
}
else if ((constant_msb == 1) && (constant_lsb == 1)) {
// constant pair = 3: signal >= 3 iff both set; signal > 3 is impossible
part_bit_a = in_msb*in_lsb; // AND(msb, lsb)
part_bit_b = 0;
}
else assert(0 != 0); // impossible case
// Combine into the weighted contribution for this pair:
// signal pair < constant pair → part_bit_a=0, part_bit_b=0 → +a (penalty)
// signal pair = constant pair → part_bit_a=1, part_bit_b=0 → 0 (neutral)
// signal pair > constant pair → part_bit_a=1, part_bit_b=1 → +b (reward)
parts[i] <== (a * (1 - part_bit_a)) + (b * part_bit_b);
// accumulate parts
sum += parts[i];
// Advance weights: a doubles, b shrinks by the same amount, preserving
// the invariant that higher pairs dominate all lower ones.
b -= bit_value;
a += bit_value;
bit_value <<= 1;
}
// Bit 127 is the sign bit of the sum in 128-bit two's complement:
// - If in > constant, the sum is "negative" modulo 2^128, so bit 127 is set.
// - If in <= constant, the sum is "non-negative" modulo 2^128, so bit 127 is clear.
// Bits above 127 are just the overflow of the 2^128 terms, and are ignored.
//
// 135 bits are needed because the maximum possible sum is:
// sum_max = Σ(i=0..126) b_i = Σ(i=0..126) (2^128 - 2^i)
// = 127·2^128 - (2^127 - 1)
// = 2^135 - 2^128 - 2^127 + 1
// which fits in 135 bits but not 134.
out_bits <== sum;
component num2bits = Num2Bits(135);
num2bits.in <== out_bits;
out <== num2bits.out[127];
// only bit 127 is needed, suppress "unused" warning with `_ <==`
_ <== num2bits.out;
}
CompConstant returns 1 if in > constant, where in is given as 254 bits and constant is known at compile time. This circuit comes from Circomlib, and it looks rather mysterious at first. Let us take it apart piece by piece.
Comparing Digit by Digit
Think of how you compare two numbers by hand: you look at their digits from the most significant one, and the first digit where they differ decides the result. For example, because of the second digit, no matter what the remaining digits are.
CompConstant does the same, but instead of decimal digits it uses pairs of bits, i.e. base-4 digits. The 254 bits of in make up 127 pairs, in[2i] being the least-significant bit (in_lsb) and in[2i+1] the most-significant bit (in_msb) of the ’th pair. The same is done for the constant, which is known at compile time, so its pairs are just numbers.
For each pair , we compare the digit of in (call it ) with the digit of the constant (call it ) using two bits:
part_bit_ais 1 ifpart_bit_bis 1 if
Since is a constant, we can write these with a simple expression for each of its four possible values, where :
| 0 | always | either bit is set, OR(in_msb, in_lsb) |
| 1 | either bit is set, OR(in_msb, in_lsb) | , in_msb |
| 2 | , in_msb | , AND(in_msb, in_lsb) |
| 3 | , AND(in_msb, in_lsb) | never |
These are exactly the four branches in the loop, using the logic gates OR(x, y) = x + y - xy and AND(x, y) = xy.
Weighting the Digits
Next, each pair contributes a part to a sum:
parts[i] <== (a * (1 - part_bit_a)) + (b * part_bit_b);
There are three cases here:
- : both bits are 0, so we add
a. - : only
part_bit_ais 1, so we add 0. - : both bits are 1, so we add
b.
What are a and b? They start at and , and at the end of each iteration a grows by bit_value and b shrinks by bit_value, which doubles every time. Following the loop, at pair we have:
Here is the idea behind these values. Suppose we could add for a pair where in is smaller, and for a pair where in is larger. The most significant differing pair, say at position , contributes , and all the pairs below it can contribute at most
So, just like comparing by hand, the most significant differing pair decides the sign of the sum: it is negative if and only if in > constant.
The problem is that there are no negative numbers in our circuits, only field elements. So instead of , CompConstant uses , which is how is represented in 128-bit two’s complement. That is , while is the positive term.
Reading the Sign
In 128-bit two’s complement, the sign is the bit 127: a number is negative if and only if its bit 127 is set. So at the end, we decompose the sum into bits with Num2Bits and return its bit 127.
The sum itself is not a 128-bit number though, since every “greater” pair adds a on top. If there are such pairs, the sum is:
The part only affects the bits from 128 and above, so the bits 0 to 127 are exactly the two’s complement form of the bracketed difference. In other words, we only read bit 127 and ignore the rest.
As an example, let the constant be , which is in base-4. Here is what happens for a few inputs:
in | base-4 | pair 1 | pair 0 | sum | bit 127 | out |
|---|---|---|---|---|---|---|
| 3 | less, | greater, | 0 | 0 | ||
| 5 | equal, | less, | 0 | 0 | ||
| 6 | equal, | equal, | 0 | 0 | ||
| 7 | equal, | greater, | 1 | 1 | ||
| 8 | greater, | less, | 1 | 1 |
Notice the first row: the lower pair is “greater”, so the sum goes beyond , but it is the higher pair that decides, and bit 127 correctly stays 0.
Why 135 Bits?
The largest possible sum is when all 127 pairs are “greater”:
So 135 bits are enough to decompose the sum, and we need all of them even though only bit 127 is used: with fewer bits, Num2Bits would fail for large sums. The _ <== num2bits.out line tells the compiler that the other bits are unused on purpose.
Why Pairs of Bits?
It may seem simpler to compare bit by bit, but then we would have 254 digits with weights up to , and we would need 254-bit two’s complement. The sum would be around , way larger than the order of the field (), so it would wrap around and the trick would break.
With pairs, there are only 127 digits, the sum stays below , and it never wraps around. Comparing a pair with a constant digit still takes a single multiplication (in_msb * in_lsb), so each part is one constraint. In total, CompConstant has 262 non-linear constraints: 127 for the parts, and 135 for the decomposition. Compare that with a LessThan(254), which is not even possible since LessThan requires n <= 252!
AliasCheck
template AliasCheck() {
signal input in[254];
component comparator = CompConstant(-1);
for (var i = 0; i < 254; i++) {
comparator.in[i] <== in[i];
}
comparator.out === 0;
}
Alias check simply asserts that a given 254-bit number is within the prime field of BN254. The role of -1 there is just a short-cut to obtain the largest number within the field, .
Why would we need this? 254 bits can represent numbers up to , which is larger than . So a field element may have two different 254-bit representations, and , which are called aliases. If a circuit uses Num2Bits(254) without an alias check, a dishonest prover can pick the bits of instead of . AliasCheck asserts that the bits represent a number , which rules out the alias.
Sign
template Sign() {
signal input in[254];
signal output out;
var half = 1 / 2;
component comparator = CompConstant(half - 1);
for (var i = 0; i < 254; i++) {
comparator.in[i] <== in[i];
}
out <== comparator.out;
}
In a prime field, a field element is defined to be positive if it is closer to 0 than it is to the order of the field. Sign checks for that property and returns 0 if the number is positive, otherwise 1 if the number is negative. Specifically, for order and a number the sign of is:
- positive when
- negative when
Here, 1 / 2 is a field division, i.e. the inverse of 2, which is . So half - 1 is , and CompConstant returns 1 exactly when the number is negative.
Constraint Count
| Circuit | Constraints |
|---|---|
CompConstant | 262 |
AliasCheck | 261 |
Sign | 262 |
Note that these take the bits of a number as input, so if you also need to decompose a number into bits with Num2Bits(254), that is another 254 constraints.