Slice generated from a generic array is accessed outside of its capacity

[sirasistant]

Aim

Be able to run code like this:

global ARGS_HASH_CHUNK_COUNT = 64;
global ARGS_HASH_CHUNK_LENGTH = 64;

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

pub fn hash_args(args: [Field]) -> Field {
    if args.len() == 0 {
        0
    } else {
        let mut chunks_hashes = [0; ARGS_HASH_CHUNK_COUNT];
        for i in 0..ARGS_HASH_CHUNK_COUNT {
            let mut chunk_hash = 0;
            let start_chunk_index = i * ARGS_HASH_CHUNK_LENGTH;
            if start_chunk_index < args.len() {
                let mut chunk_args = [0; ARGS_HASH_CHUNK_LENGTH];
                for j in 0..ARGS_HASH_CHUNK_LENGTH {
                    let item_index = i * ARGS_HASH_CHUNK_LENGTH + j;
                    if item_index < args.len() {
                        chunk_args[j] = args[item_index];
                    }
                }
                chunk_hash = pedersen_hash(chunk_args, 44);
            }
            chunks_hashes[i] = chunk_hash;
        }
        pedersen_hash(chunks_hashes, 44)
    }
}

// Unpacks returns values from the returns hash
unconstrained pub fn unpack_returns<N>(return_hash: Field) -> [Field; N] {
    [return_hash; N]
}

// Returns the returns hash
unconstrained pub fn call_private_function_wrapper(targetAddress: Field) -> Field {
    targetAddress + 5
}

pub fn hash_args_array<N>(args: [Field; N]) -> Field {
    hash_args(args.as_slice())
}

fn call_private_function<RET_SIZE>(targetAddress: Field) -> [Field; RET_SIZE] {
    let return_hash = call_private_function_wrapper(targetAddress);
    let unpacked = unpack_returns(return_hash);
    assert_eq(hash_args_array(unpacked), return_hash);
    unpacked
}

fn main(targetAddress: Field) {
    let foo: [Field; 1] = call_private_function(targetAddress);
}

Prover.toml

targetAddress = "27" // any value works here

Expected Behavior

Program should execute successfully, and should be simplified taking into account the array length and slice capacity (hash_args should be simplified to pedersen_hash([pedersen_hash([single_return_value, 0, 0...]), 0, 0, 0...]);

Bug

error: Failed constraint
   ┌─ /mnt/user-data/alvaro/constructor/src/main.nr:49:5
   │
49 │     assert_eq(hash_args_array(unpacked), return_hash);
   │     -------------------------------------------------
   │
   = Call stack:
     1. /mnt/user-data/alvaro/constructor/src/main.nr:54:27
     2. /mnt/user-data/alvaro/constructor/src/main.nr:49:5

It appears that the slice is accessed outside of its capacity (that should be 1)

To Reproduce

Project Impact

None

Impact Context

No response

Workaround

None

Workaround Description

No response

Additional Context

No response

Installation Method

None

Nargo Version

No response

NoirJS Version

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response

[sirasistant]

This might be related, if I change the hash_args implementation to iterate over the length of the slice:

pub fn hash_args(args: [Field]) -> Field {
    if args.len() == 0 {
        0
    } else {
        assert(args.len() < ARGS_HASH_CHUNK_COUNT * ARGS_HASH_CHUNK_LENGTH);
        let mut chunks_hashes = [0; ARGS_HASH_CHUNK_COUNT];
        let mut current_chunk = [0; ARGS_HASH_CHUNK_LENGTH];
        let mut hash_index = 0;
        let mut chunk_index = 0;
        for i in 0..args.len() {
            current_chunk[chunk_index] = args[i];
            chunk_index+=1;
            if chunk_index == ARGS_HASH_CHUNK_LENGTH {
                chunks_hashes[hash_index] = pedersen_hash(current_chunk, 44);
                current_chunk = [0; ARGS_HASH_CHUNK_LENGTH];
                hash_index+=1;
                chunk_index = 0;
            }
        }
        if chunk_index > 0 {
            chunks_hashes[hash_index] = pedersen_hash(current_chunk, 44);
        }
        pedersen_hash(chunks_hashes, 44)
    }
}

I get a could not determine loop bound at compile time error

error: Could not determine loop bound at compile-time
   ┌─ /mnt/user-data/alvaro/constructor/src/main.nr:17:21
   │
17 │         for i in 0..args.len() {
   │                     ---------- If attempting to fetch the length of a slice, try converting to an array. Slices only use dynamic lengths.
   │
   = Call stack:
     1. /mnt/user-data/alvaro/constructor/src/main.nr:56:27
     2. /mnt/user-data/alvaro/constructor/src/main.nr:51:15
     3. /mnt/user-data/alvaro/constructor/src/main.nr:45:5
     4. /mnt/user-data/alvaro/constructor/src/main.nr:17:21

However, the loop bound should be known since the slice length should be the original array length from this function:

pub fn hash_args_array<N>(args: [Field; N]) -> Field {
    hash_args(args.as_slice())
}

Seems like we are losing information at some point

[TomAFrench]

Deleted initial comment as I was just compiling rather than executing.

I'd expect that the second example would fail to compile. unpack_returns returns a [u8;N] with unknown N and this return value is only used in hash_args_array which doesn't give N a concrete value so it's not possible to determine the length of the slice based on the current information in the program.

[TomAFrench]

Ah, we do actually as unpacked is returned from the circuit function with a concrete size.

[sirasistant]

Yes, the length of the array is known at the ssa level afaict, I did put a log in capacity tracker and it seems to know the capacity of the slice being one when returning from as_slice()

[sirasistant]

I think the issue is that as_slice() returns an unknown variable length, and a slice with capacity N. Since the length is unknown, the compiler cannot figure out that this evaluates to false if item_index < args.len() so it codegens a runtime access to that item_index. Problem is, that item index is beyond the capacity of the slice

[sirasistant]

So it's kind of related with the second issue: if the length returned from the intrinsic as_slice() was known at the SSA level, then both programs would compile & execute

[TomAFrench]

Minimal reproduction:

unconstrained fn return_array(val: Field) -> [Field; 1] {
    [val; 1]
}

fn main(val: Field) {
    let array = return_array(val);
    assert_constant(array.as_slice().len());
}

[sirasistant]

I can add a pass in SSA to make it aware of slice lengths returning from as_slice. I'm testing it now and it seems to work fine. I'll make a PR to see what you guys think :D. I don't know if it can be added in SSA gen, I tried there at first but it seems like it's not easy to transform the as_slice call to return a constant and the slice, but maybe I'm missing something.

[TomAFrench]

Thanks, yeah that would be helpful.

It should be possible for us to handle this in simplify_call however, we'd need to add handling for Value::Instructions which have an array as their output type. Yeah, this is ugly.