Switching from pedersen to poseidon causes a bytecode and witness solving blowup

[sirasistant]

Aim

Aztec is trying to switch from pedersen to poseidon to reduce the constraints used in hashing.

Expected Behavior

We expected witness solving time and bytecode size for ACIR functions (private) to be in the same ballpark. I did expect some issues in brillig (unconstrained) due to #4535 but this problem appears to happen in ACIR, not brillig.

Bug

Switching our account contracts from pedersen to poseidon makes witness solving time to go from < 400ms to 7 seconds.
Account contract entrypoints can dispatch to up to 6 functions that can be public or private. Every dispatch requires hashing a call stack item, that is roughly 250 items for private and 200 items for public (altough some of the items for public are known to be zero at compile time).

Previously, these account functions had in the ballpark of 10k opcodes, and after the switch to poseidon we are seeing 400k+ ACIR opcodes. The flamegraphs for a test run of the sandbox before and after the switch to pedersen can be seen here:
AztecProtocol/aztec-packages#5523 (comment)

Here is a regular noir function equivalent of an account contract entrypoint:
https://github.com/sirasistant/noir-playground/blob/main/src/main.nr#L16
The entrypoint in the repo has been simplified to only dispatch to up to 2 functions instead of 6.

To Reproduce

1. Clone the repository
2. Use nargo 0.26.0+a6016b46abf6da6de4566cf6d35a675d805dd9b5
3. Play with the Hash trait implementation, switching to/from poseidon and pedersen in PrivateCallStackItem, PublicCallStackItem and PrivateCircuitPublicInputs
4. See the resulting ACIR go from to 1.5k witnesses to 70k

Project Impact

Blocker

Impact Context

This blocks the switch to Poseidon, since the witness solving blowup makes the sandbox unusable.

Workaround

None

Workaround Description

No response

Additional Context

No response

Installation Method

None

Nargo Version

0.26.0+a6016b46abf6da6de4566cf6d35a675d805dd9b5

NoirJS Version

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response

[sirasistant]

I think this is the same issue:

use dep::std::hash::{pedersen_hash_with_separator, poseidon2::Poseidon2};

global NUM_HASHES = 4;
global HASH_LENGTH = 20;

pub fn pedersen_hash<N>(inputs: [Field; N], hash_index: u32) -> Field {
    dep::std::hash::pedersen_hash_with_separator(inputs, hash_index)
}

pub fn poseidon_hash<N>(inputs: [Field; N]) -> Field {
    Poseidon2::hash(inputs, inputs.len())
}

fn main(
    to_hash: [[Field; HASH_LENGTH]; NUM_HASHES],
    enable: [bool; NUM_HASHES]
) -> pub [Field; NUM_HASHES] {
    let mut result = [0; NUM_HASHES];
    for i in 0..NUM_HASHES {
        let enable = enable[i];
        let to_hash = to_hash[i];
        if enable {
            // result[i] = pedersen_hash(to_hash, 0);
            result[i] = poseidon_hash(to_hash);
        }
    }
    result
}

(run nargo info and play with poseidon/pedersen and removing the if branch)
Conditionals wrapping poseidon hashes make it less efficient that conditionally wrapped pedersens. @TomAFrench pointed out that it's due to how predicates are being applied to the inactive branch

[jfecher]

Looks like #4716 only reduces this from a circuit of size 74602 to 70650 (-4k)

[n4ru]

Even without if statements, I'm still getting a 4x constraint blowup vs pedersen.

[TomAFrench]

@guipublic could you take a look at this? We added the #[no_predicates] attribute in order to address this but Alvaro has reported that it's still an issue to have conditional poseidon calls. We should do some testing to nail down how the performance of this changes based on how it's called.

[guipublic]

I can confirm that 'no_predicates' solves the issue highlighted in the last snippet from the comments.