No need for range check

[enricobottazzi]

The range check performed here on sourceValue and claimedValue is not necessary in my opinion.

This range check would only fail if:

• 2 ** 252 <= sourceValue < p
• 2 ** 252 <= claimedValue < p

And these are not actually cases of overflow.

I performed the test included in the library after having removed these 4 lines and they all pass successfully.

You can check these 2 gists here (circuit and test) to test out my hypotheses.

It would be interesting to understand if the LessOrEqual operation is sufficient to prevent any overflow

[leosayous21]

Hey @enricobottazzi Thanks for this!
Did you check the discussion on this PR #1 when we added it?
@BlakeMScurr did you have some update on the iden3 issue you created on this subject?

[leosayous21]

@enricobottazzi, @BlakeMScurr created a repo to test this case normally, you can find it here https://github.com/BlakeMScurr/comparator-overflow

[enricobottazzi]

Thanks for the material provided. The context is clearer now, and the implementation you applied seems correct. Wondering if you and @BlakeMScurr have any suggestions on how to fix this at the circomlib level

[BlakeMScurr]

@enricobottazzi well the algorithm is still sound for numbers in the right range, and it's probably pretty optimal, so I wouldn't change it. Maybe I'd just rename it to LessThanUnsafe, and a new LessThan that does a range check on the inputs.

That way:

• users will choose the safe way by default
• we might catch some bugs when users pull the new version
• it's still easy to use the old optimised version

What do you think?

[BlakeMScurr]

@enricobottazzi by the way, while we're discussing LessThan, I just realised you might be able to remove a constraint by doing

n2b.in <== in[1]+ (1<<n) - in[0];
out <== n2b.out[n];

instead of

n2b.in <== in[0]+ (1<<n) - in[1];
out <== 1-n2b.out[n];

I think that's right. Might try a PR some time. Although, the constraint count might end up being the same due to compile time optimisations.