noir-lang / noir

Noir is a domain specific language for zero knowledge proofs
https://noir-lang.org
Apache License 2.0
821 stars 177 forks source link

feat!: Use BigInt instead of FieldElement in the compiler to be able to detect overflows/underflows #5338

Closed asterite closed 1 day ago

asterite commented 4 days ago

Description

Problem

Resolves #4631

Summary

Throughout the compiler, integer values are represented using FieldElement, starting at the tokenization level. If an integer value is larger than modulus, it's silently truncated (or, well, wrapped, I guess). To be able to detect that this happens we can't keep FieldElement at this level: we have to carry the unmodified integer up until we do the type range check. So, this PR changes tokens to carry a BigInt value. This BigInt is then passed to HirLiteral and even reaching the Literal enum in the monomorphization phase. Eventually, the BigInt is turned into a FieldElement right when it's needed (right after we do the type range check).

Then, this PR also enhances the type range check logic: now that we can have values that overflow the largest Field's value, we check that. But also, the previous code only checked for maximum positive values. For example, for u8 it would check that the value was less than 256. But for i8 it would check the same thing. This PR changes that check to verify it's in -128..=127 (and similarly for other integer types).

Additional Context

None.

Documentation*

Check one:

PR Checklist*

asterite commented 1 day ago

I've been thinking more about this PR and how to approach this problem.

I think that, at the lexer level, if an integer token is larger than the maximum field element, we can give a compile error. That's assuming field elements will always be bigger than the maximum value of u64. Then we can keep storing values as FieldElement. We still have to remember if the value was positive or negative, but we are already doing that.

So, I'll close the PR and later next week open another PR, but let me know otherwise!