ginger-lib icon indicating copy to clipboard operation
ginger-lib copied to clipboard

Fix bug in cmp with equality when operand is (p-1)/2 + add condtional_enforce_cmp

Open nicholas-mainardi opened this issue 4 years ago • 0 comments

The comparison functions for FpGadget only accepts operands in the range [0, (p-1)/2] for a prime field Fp. In case equality between the input operands x,y must be also checked in the comparison function (e.g, x <= y), the current implementation perform the comparison by comparing x and y+1 (i.e., to check if x <= y, it is checked if x < y+1). However, if y==(p-1)/2, then y+1 > (p-1)/2, which is not properly handled by the comparison function, hence triggering a constraint violation (although y=(p-1)/2 is a legitimate value according to specs of the comparison functions).

This PR fixes this bug by dealing with the equality case without performing such troublesome addition, exploiting these 2 identities:

  • x <= y iff !(x > y)
  • x >= y iff !(x < y)

In addition, unit tests are enriched to take into account such corner cases.

Furthermore, this PR adds the comparison functions conditional_enforce_cmp and conditional_enforce_cmp_unchecked, which enforce an order relationship between the operands if and only if a boolean condition is verified

nicholas-mainardi avatar Jan 13 '22 11:01 nicholas-mainardi