privacy-scaling-explorations / halo2curves

Other
174 stars 141 forks source link

Misuse of `is_less_than_modulus` #178

Closed davidnevadoc closed 2 weeks ago

davidnevadoc commented 1 month ago

In the deserialization of prime field elements, we sometimes check that the resulting value lies in the correct range: [0, p-1]. This check is performed by the function is_less_than_modulus: https://github.com/privacy-scaling-explorations/halo2curves/blob/8771fe5a5d54fc03e74dbc8915db5dad3ab46a83/derive/src/field/mod.rs#L359-L364

It simply subtracts the modulus as a big integer and checks for an underflow. Note that the input must be in canonical form, not in Montgomery form. The function is called correctly in some places, but incorrectly in others (mainly in SerdeObject implementation).


Here it is correctly used: https://github.com/privacy-scaling-explorations/halo2curves/blob/8771fe5a5d54fc03e74dbc8915db5dad3ab46a83/derive/src/field/mod.rs#L464-L468

(Note that it receives the canonical form, so the input is multiplied by R2, but not in the less_than_modulus call).

But here it is not: https://github.com/privacy-scaling-explorations/halo2curves/blob/8771fe5a5d54fc03e74dbc8915db5dad3ab46a83/derive/src/field/mod.rs#L497-L503

and

https://github.com/privacy-scaling-explorations/halo2curves/blob/8771fe5a5d54fc03e74dbc8915db5dad3ab46a83/derive/src/field/mod.rs#L522-L538

davidnevadoc commented 2 weeks ago

There is no bug, this function can and should be used in both Montgomery and non-Montomery form field elements.