Gate blowup due to optimization bug in loops

[madztheo]

Aim

Using the following function

pub fn from_byte_be_to_fields<let NBytes: u32, let N: u32>(x: [u8; NBytes]) -> [Field; N] {
    let mut result = [0 as Field; N];

    let mut limb: Field = 0;
    let mut k = 0;
    for _j in 0..(15 - (N * 15 - NBytes)) {
        limb *= 256;
        limb += x[k] as Field;
        k += 1;
    }

    result[N - 1] = limb;

    for i in 1..N {
        let mut limb: Field = 0;
        for _j in 0..15 {
            limb *= 256;
            limb += x[k] as Field;
            k += 1;
        }
        result[N - i - 1] = limb;
    }

    result
}

The byte representation of an RSA public key and its corresponding Barrett reduction parameter (as required by the BigNum library) are converted to an array of 120-bit fields. Then, it is used to instantiate the parameters for the runtime bignum used for the signature verification.

pub fn verify_signature<let SIG_BYTES: u32, let IS_PSS: u32, let DATA_TO_SIGN_LEN: u32>(
    pubkey_bytes: [u8; SIG_BYTES],
    sig_bytes: [u8; SIG_BYTES],
    redc_param_bytes: [u8; SIG_BYTES + 1],
    exponent: u32,
    data_to_sign: [u8; DATA_TO_SIGN_LEN],
    data_to_sign_len: u64,
) -> bool {
    assert(
        (SIG_BYTES == 512) | (SIG_BYTES == 384) | (SIG_BYTES == 256) | (SIG_BYTES == 128),
        "Only modulus of bit size 1024, 2048, 3072 and 4096 are supported",
    );

    let msg_hash = sha256::sha256_var(data_to_sign, data_to_sign_len);

    let pubkey = utils::from_byte_be_to_fields::<SIG_BYTES, (SIG_BYTES + 14) / 15>(pubkey_bytes);
    let redc_param = utils::from_byte_be_to_fields::<SIG_BYTES + 1, _>(redc_param_bytes);
    let params = BigNumParams::new(false, pubkey, redc_param);

    let signature = RuntimeBigNum::from_be_bytes(params, sig_bytes);

    if (IS_PSS == 1) {
        verify_sha256_pss::<_, SIG_BYTES * 8>(msg_hash, signature, SIG_BYTES * 8)
    } else {
        verify_sha256_pkcs1v15::<_, SIG_BYTES * 8>(msg_hash, signature, exponent)
    }
}

All of this can be found in ZKpassport repo here.

Expected Behavior

The conversion from bytes to fields should happen with a reasonable amount of constraints (i.e. <10k)

Bug

When compiling the sig_check_dsc_rsa_pkcs_4096 circuit, using this function twice (to convert the public key and its reduction parameter), the total number of constraints totals over 680k, largely above expectations.

To Reproduce

1. clone the ZKpassport circuits repo available here
2. cd into the local repo
3. Open /crates/lib/utils/src/lib.nr and look for from_byte_be_to_fields
4. Comment the std::as_witness calls
5. run ./scripts/info.sh sig_check_dsc_rsa_pkcs_4096, it will compile the corresponding circuit, compute the number of gates with bb and output it in a json file in the info folder
6. You should see around 680k gates for the circuit
7. Open /crates/lib/utils/src/lib.nr again and uncomment the std::as_witness calls
8. You should see around 260k gates for the circuit

Workaround

Yes

Workaround Description

The workaround is to mark the variable operated on in the loops with std::as_witness reducing the amount of constraints by over 400k

Additional Context

No response

Project Impact

Nice-to-have

Blocker Context

No response

Nargo Version

nargo version = 0.36.0 noirc version = 0.36.0+801c71880ecf8386a26737a5d8bb5b4cb164b2ab

NoirJS Version

No response

Proving Backend Tooling & Version

Barretenberg - bb cli - 0.58.0

Would you like to submit a PR for this Issue?

None

Support Needs

No response

[TomAFrench]

This is a known issue (#4629) and why we added as_witness. If you can pull out the from_byte_be_to_fields function and get it to compile on its own then that would be helpful to have as a simpler reproduction case.