noir
noir copied to clipboard
Published
20 hours ago •
noir-lang
noir-lang
feat: add optimization pass to remove witness equality constraints
Description
Problem*
Resolves
Summary*
This PR adds a new optimisation pass which removes constraints which just constrain one witness to be equal to another and instead replaces any references to one of those witnesses with the other.
Additional Context
Documentation*
Check one:
- [ ] No documentation needed.
- [ ] Documentation included in this PR.
- [ ] [Exceptional Case] Documentation to be submitted in a separate PR.
PR Checklist*
- [ ] I have tested the changes locally.
- [ ] I have formatted the changes with Prettier and/or
cargo fmton default settings.
Changes to circuit sizes
Generated at commit: 8b0fd1d85377f9e0b7ba66093c9037fc01ce008f, compared to commit: 5192e537708fc9ec51f53bb6a6629c9d682532d5
🧾 Summary (10% most significant diffs)
| Program | ACIR opcodes (+/-) | % | Circuit size (+/-) | % |
|---|---|---|---|---|
| brillig_hash_to_field | -1 ✅ | -50.00% | -1 ✅ | -14.29% |
| fold_basic | -1 ✅ | -33.33% | -1 ✅ | -14.29% |
| fold_basic_nested_call | -1 ✅ | -33.33% | -1 ✅ | -14.29% |
| to_be_bytes | -28 ✅ | -35.90% | -28 ✅ | -16.97% |
| brillig_blake2s | -64 ✅ | -62.75% | -72 ✅ | -42.86% |
| brillig_sha256 | -64 ✅ | -65.98% | -72 ✅ | -44.44% |
| brillig_identity_function | -6 ✅ | -66.67% | -6 ✅ | -54.55% |
Full diff report 👇
| Program | ACIR opcodes (+/-) | % | Circuit size (+/-) | % |
|---|---|---|---|---|
| 6 | 38 (-32) | -45.71% | 38,799 (0) | 0.00% |
| 7 | 38 (-32) | -45.71% | 19,350 (0) | 0.00% |
| aes128_encrypt | 95 (-48) | -33.57% | 7,881 (0) | 0.00% |
| array_dynamic_blackbox_input | 787 (-32) | -3.91% | 45,970 (0) | 0.00% |
| array_dynamic_nested_blackbox_input | 137 (-32) | -18.93% | 38,799 (0) | 0.00% |
| bench_sha256 | 3 (-32) | -91.43% | 38,799 (0) | 0.00% |
| bench_sha256_30 | 90 (-960) | -91.43% | 120,086 (0) | 0.00% |
| bit_and | 44 (-2) | -4.35% | 4,112 (0) | 0.00% |
| blake3 | 38 (-32) | -45.71% | 18,774 (0) | 0.00% |
| conditional_1 | 8,543 (-2) | -0.02% | 38,799 (0) | 0.00% |
| conditional_regression_short_circuit | 66 (-32) | -32.65% | 38,799 (0) | 0.00% |
| keccak256 | 75 (-64) | -46.04% | 55,062 (0) | 0.00% |
| merkle_insert | 1,777 (-2) | -0.11% | 29,032 (0) | 0.00% |
| pedersen_check | 37 (-1) | -2.63% | 28,858 (0) | 0.00% |
| pedersen_hash | 1 (-1) | -50.00% | 28,742 (0) | 0.00% |
| schnorr | 468 (-52) | -10.00% | 54,388 (0) | 0.00% |
| sha256 | 87 (-64) | -42.38% | 38,904 (0) | 0.00% |
| simple_bitwise | 17 (-1) | -5.56% | 8,214 (0) | 0.00% |
| simple_shield | 48 (-1) | -2.04% | 29,032 (0) | 0.00% |
| hashmap | 206,682 (-12) | -0.01% | 367,874 (-17) | -0.00% |
| no_predicates_numeric_generic_poseidon | 52 (-1) | -1.89% | 10,755 (-1) | -0.01% |
| regression_4449 | 6,034 (-64) | -1.05% | 279,787 (-72) | -0.03% |
| tuple_inputs | 42 (-1) | -2.33% | 3,628 (-1) | -0.03% |
| 5_over | 19 (-2) | -9.52% | 3,467 (-2) | -0.06% |
| 4_sub | 12 (-2) | -14.29% | 3,458 (-2) | -0.06% |
| u16_support | 261 (-2) | -0.76% | 3,055 (-2) | -0.07% |
| poseidon2 | 4 (-1) | -20.00% | 1,435 (-1) | -0.07% |
| ecdsa_secp256k1 | 201 (-32) | -13.73% | 42,901 (-32) | -0.07% |
| embedded_curve_ops | 7 (-4) | -36.36% | 4,232 (-4) | -0.09% |
| 7_function | 232 (-2) | -0.85% | 2,989 (-3) | -0.10% |
| simple_shift_left_right | 12 (-2) | -14.29% | 2,972 (-3) | -0.10% |
| 1_mul | 10 (-2) | -16.67% | 2,758 (-3) | -0.11% |
| 3_add | 10 (-2) | -16.67% | 2,756 (-3) | -0.11% |
| bench_poseidon2_hash | 3 (-1) | -25.00% | 722 (-1) | -0.14% |
| bench_poseidon2_hash_30 | 32 (-30) | -48.39% | 21,457 (-30) | -0.14% |
| bench_poseidon2_hash_100 | 102 (-100) | -49.50% | 71,507 (-100) | -0.14% |
| wrapping_operations | 30 (-4) | -11.76% | 2,924 (-5) | -0.17% |
| 2_div | 21 (-4) | -16.00% | 2,767 (-6) | -0.22% |
| sha2_byte | 15,714 (-192) | -1.21% | 82,944 (-216) | -0.26% |
| bigint | 599 (-39) | -6.11% | 7,576 (-39) | -0.51% |
| brillig_fns_as_values | 11 (-12) | -52.17% | 2,751 (-16) | -0.58% |
| bench_sha256_100 | 300 (-3,200) | -91.43% | 384,491 (-3,200) | -0.83% |
| u128 | 764 (-18) | -2.30% | 4,661 (-48) | -1.02% |
| to_le_bytes | 53 (-31) | -36.90% | 2,879 (-31) | -1.07% |
| brillig_keccak | 100 (-64) | -39.02% | 2,986 (-72) | -2.35% |
| fold_numeric_generic_poseidon | 7 (-1) | -12.50% | 12 (-1) | -7.69% |
| brillig_hash_to_field | 1 (-1) | -50.00% | 6 (-1) | -14.29% |
| fold_basic | 2 (-1) | -33.33% | 6 (-1) | -14.29% |
| fold_basic_nested_call | 2 (-1) | -33.33% | 6 (-1) | -14.29% |
| to_be_bytes | 50 (-28) | -35.90% | 137 (-28) | -16.97% |
| brillig_blake2s | 38 (-64) | -62.75% | 96 (-72) | -42.86% |
| brillig_sha256 | 33 (-64) | -65.98% | 90 (-72) | -44.44% |
| brillig_identity_function | 3 (-6) | -66.67% | 5 (-6) | -54.55% |
![github-actions[bot] avatar](https://avatars.githubusercontent.com/in/15368?v=4 "Published by a pub.dev verified publisher"){kind=small}
Changes to Brillig bytecode sizes
Generated at commit: 8b0fd1d85377f9e0b7ba66093c9037fc01ce008f, compared to commit: 5192e537708fc9ec51f53bb6a6629c9d682532d5
There are no changes in circuit sizes
This will result in changes to error messages being emitted, e.g.
#[test(should_fail_with = foo)]
fn main(x: u8) {
let y = x ^ 1;
assert_eq(x, y, "foo");
}
This will no longer fail with "foo" but a generic error message as the XOR operation will fail when trying to write an inconsistent value for y into the witness index for x.