This PR reduces 1 constraint in FpVar::{is_eq, is_neq} (and in turn, is_zero, etc.), by observing that we can remove the booleanity check while preserving soundness.
This is because:
The first constraint (self - other) * multiplier = is_not_equal guarantees is_not_equal = 0 when self - other = 0. Otherwise, we cannot find a multiplier such that (self - other) * multiplier = 0 * multiplier = is_not_equal != 0
The second constraint (self - other) * not(is_not_equal) = 0 guarantees is_not_equal = 1 when self - other != 0. Otherwise, not(is_not_equal) = 1 - is_not_equal != 0, which indicates a contradiction self - other = 0.
Before we can merge this PR, please make sure that all the following items have been
checked off. If any of the checklist items are not applicable, please leave them but
write a little note why.
[x] Targeted PR against correct branch (master)
[x] Linked to Github issue with discussion and accepted design OR have an explanation in the PR that describes this work.
[ ] Wrote unit tests (N/A)
[x] Updated relevant documentation in the code
[x] Added a relevant changelog entry to the Pending section in CHANGELOG.md
[x] Re-reviewed Files changed in the Github PR explorer
Description
Hi there, thanks for your amazing work!
This PR reduces 1 constraint in
FpVar::{is_eq, is_neq}(and in turn,is_zero, etc.), by observing that we can remove the booleanity check while preserving soundness.This is because:
(self - other) * multiplier = is_not_equalguaranteesis_not_equal = 0whenself - other = 0. Otherwise, we cannot find amultipliersuch that(self - other) * multiplier = 0 * multiplier = is_not_equal != 0(self - other) * not(is_not_equal) = 0guaranteesis_not_equal = 1whenself - other != 0. Otherwise,not(is_not_equal) = 1 - is_not_equal != 0, which indicates a contradictionself - other = 0.See also gnark's implementation: https://github.com/Consensys/gnark/blob/870ef4efa8c9fa11a8778821c8376286207ca19b/frontend/cs/r1cs/api.go#L535-L569
Please correct me if I misunderstood something :)
Before we can merge this PR, please make sure that all the following items have been checked off. If any of the checklist items are not applicable, please leave them but write a little note why.
Pendingsection inCHANGELOG.mdFiles changedin the Github PR explorer