ICE: ShiftLeft and ShiftRight are replaced by multiplications and divisions in optimization pass.

[resurgencelabs]

Aim

The above mentioned error comes up during nargo prove p, but not during nargo check. I am using the bitwise >> and << operators and that is when the error comes up.

Expected behavior

This should not be the case since I am implementing a working algorithm for hashing from another language, where it works.

Bug

The complete message is:

nargo prove p
The application panicked (crashed).
Message: internal error: entered unreachable code: ICE: ShiftLeft and ShiftRight are replaced by multiplications and divisions in optimization pass.
Location: crates/noirc_evaluator/src/ssa/acir_gen/operations/binary.rs:244

To reproduce

1. Include << or >> in the code.
2. nargo check //no error
3. nargo prove p //error comes up as shown above

Installation method

Binary

Nargo version

nargo 0.3.2

@noir-lang/noir_wasm version

No response

@noir-lang/barretenberg version

No response

@noir-lang/aztec_backend version

No response

Additional context

No response

Submission Checklist

• Once I hit submit, I will assign this issue to the Project Board with the appropriate tags.

[TomAFrench]

nargo 0.3.2

Hi @resurgencelabs , this version of nargo is quite old. Can you update to the latest version of nargo (preferably 0.5.0) and see if you still get this issue?

It would also be helpful to share an example program which exhibits this issue.

[resurgencelabs]

nargo 0.3.2

Hi @resurgencelabs , this version of nargo is quite old. Can you update to the latest version of nargo (preferably 0.5.0) and see if you still get this issue?

It would also be helpful to share an example program which exhibits this issue.

Thanks for the promptness, Tom. We updated to 0.5.0 but it still did not work. Here is the repository that gives this error.

If you were to fork it, and run just nargo check followed by nargo prove p, you should be able to replicate the issue.

[TomAFrench]

Hey @resurgencelabs, the issue you're running into is that bitshifts by offsets which are known only at runtime are not implemented yet.

The reason for this is that decomposing the field element into bits and applying a shift to them before reconstructing a field from these bits is rather expensive to do inside a snark. This is a bit different from traditional programming languages as processors are well optimised for bitwise operations.

You may want to consider swapping out the hash function you're implementing for a snark friendly hash function such as Pedersen (which we have in the Noir standard library). I can't give any guarantees about exactly when runtime bitshifts will be implemented unfortunately.

[resurgencelabs]

Hey @resurgencelabs, the issue you're running into is that bitshifts by offsets which are known only at runtime are not implemented yet.

The reason for this is that decomposing the field element into bits and applying a shift to them before reconstructing a field from these bits is rather expensive to do inside a snark. This is a bit different from traditional programming languages as processors are well optimised for bitwise operations.

You may want to consider swapping out the hash function you're implementing for a snark friendly hash function such as Pedersen (which we have in the Noir standard library). I can't give any guarantees about exactly when runtime bitshifts will be implemented unfortunately.

No problem. We will take a look at that as well. But whenever this is implemented, just give us a heads up as well. Thanks :)

[TomAFrench]

@resurgencelabs correction, I've been told you'll want to use the poseidon hash rather than pedersen.

[kevaundray]

This limitation is also in the new SSA. I will describe the solution which would give the best developer UX.

Shifts are converted to either multiplication by a power of two or division by a power of two. If the compiler had a method to exponentiate a constant by a runtime value, this would then be fixed.

This method would need to:

• Decompose the exponent x into bits
• Component the result by using the square-and-multiply algorithm

We would essentially want to generalize this method and copy it into the compiler:

noir/noir_stdlib/src/field.nr

Line 25 in 95b2417

fn pow_32(self, exponent: Field) -> Field {

@guipublic assigning this issue to you