Addition to the "Arithmetic overflow" and "Incorrect Felt Comparison" note #161
Description
In arithmetic_overflow note the range of possible values in Cairo language is defined as (-P/2, P/2). That is the range if we consider felt as a signed number. We can use values greater than P/2, but then we treat felt as an unsigned number and the range is [0, P). Whether the felt is a signed or unsigned number in Cairo is a matter of interpretation, and it practically depends on which comparison/math functions we use on those felts.
An example of a different interpretation of the range of felt can be shown with comparison functions:
- is_le compares two
feltsinterpreted as signed numbers, so in range(-P/2, P/2) - is_le_felt compares two 'felts' interpreted as unsigned numbers, so in range
[0, P)
The incorrect_felt_comparison note describes the issue with comparing felts, but there is also another issue with comparing felts using listed functions. assert_le is a good choice to compare members of a Uint256 struct, because they are in range [0, 2**128), but it is insecure to compare arbitrary felts with assert_le. assert_le(a, b) practically checks if b - a < 2**128, and not if any a is lesser than b. In fact, we can have a large value as a such that a > b, but because the subtraction operation is mod P the output from b - a < 2**128 would still be true. Example below shows an example where a is a large number, but assertion function does not throw an error:
assert_le(3618502788666131213697322783095070105282824848410658236509717448704103809026, 0), where value of a is less than P but higher than 0. This issue can be mitigated with using the assert_le_felt, which interprets compared felts in range [0, P).
Please kindly consider adding this to the existing notes for Cairo devs' knowledge.