Comparisons in Circom are hard.

Habitually to decide, we rely on a substraction. But the scalar field of BN254 is over 254 bits but doesn’t cover $[0;2^{254}-1]$. Moreover, we need one bit to know the result of this substraction so comparisons are naively only feasible between numbers of less than 252 bits.

The Circom library provide the 252 bits number comparator but this circuit does not enforce that numbers are indeed 252 bits or less which can cause vulnerabilities in certain cases if not enforced.

To compare our nullifiers, we will need to compare numbers of arbitrary number of bits. For that, first we can decompose the numbers in 254 bits. To ensure that a number $k$ isn’t represented by $p+k$, circom provide the aliascheck circuit that ensure that a number is indeed strictly less than p once written in bits.

So we can use the Num2Bits_strict function from the Circom library to safely transform the numbers in their 254 bits representation.

For simplicity let’s take an example where $p=17$ so it’s on 5 bits. let’s say we want to compare $5$ and $11$ so $00101$ and $01011$. We have a tool to compare numbers of 3 bits.

  1. We can start comparing every bits except the 2 less significant.
  2. a) If one is greater than the other the comparison is done b) If they are equal, we can check the two last bits enumerating every case.

Let’s say we compare $a$ and $b$ such that:

  1. $a_0$ (resp. $b_0$) represents the number such that the 252 most significant bits of $a$ form $a_0$.
  2. $a_1$ the penultimate bit of $a$.
  3. $a_2$ the last bit of $a$.
$a_0 > b_0$ $a_0 = b_0$ $a_1 = b_1$ $a_1 = 1$ $a_2 = b_2$ $a_2 = 1$ result
Yes No Any Any Any Any $a > b$
No No Any Any Any Any $b > a$
No Yes No Yes Any Any $a>b$
No Yes No No Any Any $b > a$
No Yes Yes Any No Yes $a > b$
No Yes Yes Any No No $b > a$
No Yes Yes Any Yes Any $a = b$

To recover the arithmetic expression leading to these results, here are what we want:

$a_0 > b_0$ $a_0 = b_0$ $a_1 = b_1$ $a_1 = 1$ $a_2 = b_2$ $a_2 = 1$ Is $a < b$
1 0 - - - - 0
0 0 - - - - 1
0 1 0 1 - - 0
0 1 0 0 - - 1
0 1 1 - 0 1 0
0 1 1 - 0 0 1

It’s possible from this truth table to derive a boolean expression. If we note $A,B,C,D,E$ and $F$ the evaluation of the first 6 columns, then we can compute and simplify the boolean expression to get:

$result = \neg A(\neg B + B (\neg C \neg D + C \neg E \neg F))$ which has 5 multiplications