Introduce UIntGadget and ComparisonGadget
This PR addresses issues #149 and #150.
It defines a new trait UIntGadget which defines the functions available for small unsigned integers (up to 128 bits). In particular, the UIntGadget comprises most common gadgets (e.g, EqGadget, AllocGadget) and specific functions like bitiwise and arithmetic operations. This PR introduces also a macro, named impl_uint_gadget, which allows to define a UIntGadget for an unsigned integer given a bit_size and an underlying Rust native type. The macro contains also unit tests that verifies the correctness of the functions implemented for the UIntGadget being defined with the macro. The macro is employed to define UIntGadget for all the Rust native types for unsigned integers, starting from u8 up to u128. This macro mostly addresses issue #149.
Furthermore, this PR introduces also a ComparisonGadget trait, which defines the operations that enable the comparison between gadgets implementing this trait. Two implementations of the ComparisonGadget are provided in this PR:
- Comparison between the small unsigned integers gadgets implementing the
UIntGadgettrait. In particular, the implementation of theComparisonGadgettrait is part of theimpl_uint_gadgetmacro. This implementation addresses issue #150. - Comparison between
FpGadgetelements, integrating the comparison functions already introduced inrc/feat/comp_gadgetbranch; the implementation found in this PR is enriched with additional functions that allow to compare arbitrary field elements, as opposed to the implementation inrc/feat/comp_gadgetwhich requires the field elements to be smaller than (p-1)/2, where p is the modulus of the prime field. Remarkably, the functions added in this PR to deal with arbitrary field elements require only few constraints more than the corresponding ones requiring field elements smaller than (p-1)/2; however, the latter functions are retained in the implementation of theComparisonGadgetbecause they are still useful in case it is known that the field elements are smaller than (p-1)/2
Lastly, an optimize implementation of the EqGadget is added in this PR for vectors of Booleans. This optimization allows to implement equality/inequality constraints on vectors of Booleans with about 4*len/field_bits constraints over a field for vectors with len bits, as opposed to the existing implementation that requires approximately 2 constraints per bit.