std::verify_proof has gates overhead due to slices

[sirasistant]

Aim

Verify proofs in circuits with large amounts of public inputs:

fn main(
    verification_key: [Field; 114],
    proof: [Field; 93],
    public_inputs: pub [Field; 3000],
    key_hash: Field
) {
    std::verify_proof(
        verification_key.as_slice(),
        proof.as_slice(),
        public_inputs.as_slice(),
        key_hash
    );
}

Expected Behavior

Verify proof should not have overhead due to slices, especially in trivial cases where we just convert arrays to slices without touching them

Bug

Noir generates two ROM arrays for each of these conversions to slice, and then reads from the array. In an example with 3k public inputs, we have a slice overhead of 13k gates due to the ROM ops with 6k rom reads.
See this simplified example:

fn main(
    verification_key: [Field; 1],
    proof: [Field; 1],
    public_inputs: pub [Field; 1],
    key_hash: Field
) {
    std::verify_proof(
        verification_key.as_slice(),
        proof.as_slice(),
        public_inputs.as_slice(),
        key_hash
    );
}

After Array Set Optimizations:
acir(inline) fn main f0 {
  b0(v0: [Field; 1], v1: [Field; 1], v2: [Field; 1], v3: Field):
    v20, v21 = call as_slice(v0)
    v22, v23 = call as_slice(v1)
    v24, v25 = call as_slice(v2)
    call recursive_aggregation(u32 1, v21, u32 1, v23, u32 1, v25, v3)
    return 
}

Compiled ACIR for main (unoptimized):
func 0
current witness index : 10
private parameters indices : [0, 1, 3]
public parameters indices : [2]
return value indices : []
INIT (id: 0, len: 1) 
INIT (id: 1, len: 1) 
INIT (id: 2, len: 1) 
EXPR [ (-1, _4) 0 ]
MEM (id: 0, read at: x4, value: x5) 
INIT (id: 3, len: 1) 
MEM (id: 1, read at: x4, value: x6) 
INIT (id: 4, len: 1) 
MEM (id: 2, read at: x4, value: x7) 
INIT (id: 5, len: 1) 
MEM (id: 3, read at: x4, value: x8) 
MEM (id: 4, read at: x4, value: x9) 
MEM (id: 5, read at: x4, value: x10) 
BLACKBOX::RECURSIVE_AGGREGATION [(8), (9), (10), (3)] [ ]

To Reproduce

Workaround

None

Workaround Description

No response

Additional Context

No response

Project Impact

Nice-to-have

Blocker Context

The cost of recursive aggregation with ultraplonk is much higher, but in ClientIVC for aztec the slice conversion can become a relevant cost

Nargo Version

No response

NoirJS Version

No response

Proving Backend Tooling & Version

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response

[jfecher]

I think this is because we have to make a new array constant to copy an array into a slice.

Since both are immutable, this shouldn't be needed however. We could fix this I think if array & slice constants had the same type, and slices are just treated as structs containing an array and a length instead. That way both constants would have the same type and we could reuse the existing one.

[sirasistant]

Yep I think in this specific case we can just switch the blackbox to arrays since it's very weird that a user would be programatically manipulating the length of the verify proof inputs (since they have to be fixed lengths imposed by the proving system / circuit being verified) but this conversion is probably happening in other contexts too