arkworks-rs / algebra

Libraries for finite field, elliptic curve, and polynomial arithmetic
https://arkworks.rs
Apache License 2.0
636 stars 248 forks source link

Add normalization to `FpConfig` for `PartialEq` and `Eq` #800

Open weikengchen opened 8 months ago

weikengchen commented 8 months ago

Some software optimization for special primes uses unnormalized representations. For example, when two numbers are added together, the number does not always be smaller than the modulus. The same can hold for multiplication. In such situations, 1 and p+1 may both be valid results.

FpConfig allows certain level of flexibility.

We can make sure serialization always handles the normalized representation, by implementing the into_bigint in some special way.

But the problem rests on PartialEq and Eq.

Currently, PartialEq and Eq are auto-derived in Fp, which is auto-derived in BigInt as well. It examines the u64 limbs and require each limb to be the same. If we have 1 and p+1, PartialEq and Eq will return negative for them.

To solve this problem, it is advisable to add a method in FpConfig, likely called normalize, which supposedly modify p+1 into 1. Instead of auto-deriving the PartialEq and Eq, we implement them manually with normalize.

weikengchen commented 8 months ago

Related: https://github.com/l2iterative/ark-bn254-r0/blob/main/src/fields/fr.rs

Currently, without this flexibility in FpConfig, one would likely need to implement Fp anew.

mmagician commented 8 months ago

Sounds reasonable. Plonky2/3 does this for small prime fields, and holds a potentially non-canonical representation.

Pratyush commented 4 months ago

This is reasonable