Signed comparison broken in Brillig

[ggiraldez]

Aim

Execute this program:

unconstrained fn main() {
    assert(-1 as i32 < 0);
}

Expected Behavior

The program should execute successfully.

Bug

The assertion fails at runtime:

error: Failed to solve brillig function, reason: explicit trap hit in brillig
  ┌─ /home/ggiraldez/Scratchpad/noir/signed_comparison/src/main.nr:2:12
  │
2 │     assert(-1 as i32 < 0);
  │            -------------
  │
  = Call stack:
    1. /home/ggiraldez/Scratchpad/noir/signed_comparison/src/main.nr:2:12

Failed to solve brillig function, reason: explicit trap hit in brillig

To Reproduce

Execute the given program.

Installation Method

None

Nargo Version

No response

Additional Context

Found while testing the debugger, which uses Brillig output by default, on the signed_comparison execution sample.

From a quick inspection at the Brillig opcodes generated, it seems it doesn't support signed integers properly.

Also, this now executes successfully in ACIR, but it didn't in the previous version 0.22:

~/S/n/signed_comparison [1] nargo --version
nargo version = 0.22.0
noirc version = 0.22.0+3fae4a03fded4e3f5065e7461c563f7e39745604
(git version hash: 3fae4a03fded4e3f5065e7461c563f7e39745604, is dirty: false)
~/S/n/signed_comparison ❱ cat src/main.nr 
fn main() {
    assert(-1 as i32 < 0);
}
~/S/n/signed_comparison ❱ nargo execute
error: Failed constraint
  ┌─ /home/ggiraldez/Scratchpad/noir/signed_comparison/src/main.nr:2:12
  │
2 │     assert(-1 as i32 < 0);
  │            -------------
  │
  = Call stack:
    1. /home/ggiraldez/Scratchpad/noir/signed_comparison/src/main.nr:2:12

Cannot satisfy constraint

Would you like to submit a PR for this Issue?

No

Support Needs

No response

[paulallensuxs]

Hey,

I ran some tests on my end and indeed, when executing Brillig unconstrained, it results in:

paulallensuxs@paulallensuxs:~/projects/hello_world$ nargo debug
[hello_world] Starting debugger
At opcode 0: BRILLIG: inputs: []
outputs: []
[Const { destination: RegisterIndex(0), value: Value { inner: 0 } }, Const { destination: RegisterIndex(1), value: Value { inner: 0 } }, Call { location: 4 }, Stop, Const { destination: RegisterIndex(3), value: Value { inner: 1 } }, Mov { destination: RegisterIndex(2), source: RegisterIndex(3) }, Const { destination: RegisterIndex(5), value: Value { inner: 0 } }, BinaryIntOp { destination: RegisterIndex(4), op: Sub, bit_size: 32, lhs: RegisterIndex(5), rhs: RegisterIndex(2) }, Const { destination: RegisterIndex(7), value: Value { inner: 0 } }, BinaryIntOp { destination: RegisterIndex(6), op: Add, bit_size: 32, lhs: RegisterIndex(4), rhs: RegisterIndex(7) }, BinaryIntOp { destination: RegisterIndex(7), op: LessThan, bit_size: 32, lhs: RegisterIndex(6), rhs: RegisterIndex(5) }, Const { destination: RegisterIndex(9), value: Value { inner: 1 } }, BinaryIntOp { destination: RegisterIndex(8), op: Equals, bit_size: 1, lhs: RegisterIndex(7), rhs: RegisterIndex(9) }, JumpIf { condition: RegisterIndex(8), location: 15 }, Trap, Return]

> continue
(Continuing execution...)
ERROR: Failed to solve brillig function, reason: explicit trap hit in brillig

And upon removing unconstrained, it functions correctly only with nargo version 0.23.0.

Consulting the Brillig documentation on lib.rs, it's clear it lists support for 'Unsigned integers' but there's no mention of Signed integers so I assume that Brillig interprets -1 as the unsigned version 4294967295, which explains why the code:

unconstrained fn main() {
    assert(-1 as i32 == 4294967295);
}

executes successfully, whereas something like:

unconstrained fn main() {
    assert(-1 as i32 == 4294967294);
}

triggers an the exact you're having:

...
> continue
(Continuing execution...)
ERROR: Failed to solve brillig function, reason: explicit trap hit in brillig
At opcode 0: BRILLIG: inputs: []
outputs: []
[Const { destination: RegisterIndex(0), ... ]

and running assert(-1 as i32 > 0); instead of assert(-1 as i32 < 0); will also executes successfully, because 4294967295 > 0