fix: avoid overflows in integer division #2180
Merged
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
jfecher
reviewed
Aug 4, 2023
crates/noirc_evaluator/src/ssa/acir_gen/acir_ir/acir_variable.rs
Outdated
Show resolved
Hide resolved
5 tasks
kevaundray
approved these changes
Sep 11, 2023
TomAFrench
added a commit
that referenced
this pull request
Sep 11, 2023
* master: chore: Move tooling related items into their own directory (#2644) chore: add `CompilationResult` helper type (#2639) fix: initialise arrays returned by brillig (#2048) chore: clippy fix (#2631) fix(wasm): Remove stacker from dependencies (#2637) chore(ci): reenable CI for `noir_wasm` (#2636) fix: avoid overflows in integer division (#2180) chore(ci): Nightly Integration testing (#2596) feat(parser): allow multiple attributes (#2537) feat(nargo): Allow installing custom backends from the CLI (#2632) chore(ci): enforce clippy and `cargo fmt` in CI (#2628)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Description
Ensure that no overflow occurs in euclidian division.
Unfortunately the added check is not compatible with our truncation so I had to re-work it.
This could be avoided if we disallow truncation for field elements. In doing so this would:
The first point is fine IMHO, since we already forbid field comparison because it is not consistent across field elements (0<3 but 3<p for instance).
Indeed, modulo is also inconsistent across field elements (0%2=0 but p%2=1 for instance)
For the second point, we could change the semantic of casting and make
x as u32becomes simply a 32 bits range check.Problem*
Euclidian division was not checking for overflow. This is a big issue since it means noir is producing under-constrained code. For instance, the prime order of the noir native field is odd, so p=2k+1, which means that p%2=1. But we can also have p=0*2+0, which means that p%2=0. The latter does not overflow.
Related to #1604
Summary*
We add a check in euclidian division to ensure that the result 'qb+r' does not overflow.
But this also means that euclidian division cannot be performed on unbounded integers anymore, which has impact on the truncation operation.
This is resolved by reducing the input to a bit size less than the field modulus (with some margin).
As discussed in the description, this can be avoided if we change the semantic of the casting in noir.
Documentation
This PR requires documentation updates when merged.
Additional Context
PR Checklist*
cargo fmton default settings.