Noir program attempts to read uninitialised memory

[TomAFrench]

Reopening @ax0's issue #2099 based on the new error.

Aim

Generate a proof for this program.

Expected Behavior

A proof is successfully generated.

Bug

We get the following error:

$ nargo execute
The application panicked (crashed).
Message:  Should not read uninitialized memory
Location: /home/tom/.cargo/registry/src/github.com-1ecc6299db9ec823/acvm-0.21.0/src/pwg/memory_op.rs:26

This is a bug. We may have already fixed this in newer versions of Nargo so try searching for similar issues at https://github.com/noir-lang/noir/issues/.
If there isn't an open issue for this bug, consider opening one at https://github.com/noir-lang/noir/issues/new?labels=bug&template=bug_report.yml

To Reproduce

1. git clone https://github.com/aragonzkresearch/noir-trie-proofs
2. cd noir-trie-proofs/tests/depth_8_storage_proof
3. nargo execute

Installation Method

Compiled from source

Nargo Version

nargo 0.9.0 (git version hash: a07b8a4, is dirty: false)

Additional Context

Would you like to submit a PR for this Issue?

No

Support Needs

No response

[jfecher]

Ah, I hoped this would be fixed by #2106. I can confirm this is still an issue after that has been merged.

[kevaundray]

@jfecher can you check if this has been solved?

[jfecher]

@kevaundray a Nargo bug with nested crates is making it more difficult for me to test it. When trying to run the integration test, Nargo complains the parent directory is a lib instead of a bin target even though I'm trying to run the test in a subdirectory which is a bin target.

After moving the subdirectory somewhere else, the bug is still present.

[vezenovm]

When trying to run the integration test, Nargo complains the parent directory is a lib instead of a bin target even though I'm trying to run the test in a subdirectory which is a bin target.

cc'ing @phated as I am not sure if this is the desired functionality or a bug. If it is a bug we can make a separate issue. I also had to move the subdirectory outside of the main noir-trie-proofs directory to reproduce this issue.

[jfecher]

@vezenovm it looks to be a result of #2107.

Edit: Erm, nevermind. The parent project is not a workspace.

[phated]

as I am not sure if this is the desired functionality or a bug.

It's both. lol. Please open an issue so it can be prioritized.

[vezenovm]

The panic is a bug, but there may also be an error in the program linked. We are not checking for index out of bounds on dynamic arrays. I'm working on a fix.

I was able to reproduce this on our array_dynamic test by adding 20 to the dynamic index at the top of main. I am also working with a local version of ACVM that shows me the index we are trying to access in the memory block:

    let idx = (z - 5*t - 5) as Field + 20;
    //dynamic array test
    dyn_array(x, idx, idx - 3); 

This errors out with:

The application panicked (crashed).
Message:  Should not read uninitialized memory at index 24
Location: /mnt/user-data/maxim/acvm/acvm/src/pwg/memory_op.rs:30

When working with the project linked in the issue, I was get a panic with an index one greater than the specified array being accessed. Due to this I think the project linked most likely has an index out of bounds bug, just that the compiler needs to have a clear error and not a panic.

[vezenovm]

After some more investigation this looks like it may be a deeper error. I made a fix that checks for loop out of bounds and on the simple case in array_dynamic I am getting a failed constraint error instead of a panic as expect. However, I am still getting a panic in the linked project.

[vezenovm]

PR #2389 has included actual location data to ACIR memory operations. The missing location data is a bug in its own right, but has also exposed another issue with how we are handling call stacks. From the PR description:

The new location data has also exposed the actual bug that occurs in #2133. It looks like we are not handling locations correctly during flattening. A smaller reproduced snippet of the storage proof example is provided in the dynamic_array_index. If the dynamic array is accessed with an index out of bounds later after flattening, only the then case of the array merger is shown. For example

    if z == 20 {
        x[0] = x[4];
    } else {
        x[idx] = 10;
        for i in 0..5 {
            x[idx] = x[i];
        }
    }
    // TODO(#2133): This line should be where we show the error
    // but instead it will show x[0] == x[4] as the line where there is an index out of bounds
    assert(x[idx] != 0)

This bug is also seen in the storage proof example, which will return the below output when calling nargo execute:

However, based on the smaller snippet above, it looks to be using the incorrect location, as the array access being reported is within the then case of an if statement:

        if ((i + n) as u32) < (N as u32)
        {
            out[i] = input[i+n];
        }

[Savio-Sou]

#2389 was a step towards a fix, but not the full fix.

[vezenovm]

#2389 was a step towards a fix, but not the full fix.

Thanks, I had not realized this got closed by that PR.

[ax0]

I'm not sure this has been resolved. I'm still getting an index out of bounds error on commit c344d86.

[vezenovm]

Ah this should not have been closed, as the change was only incldued in ACVM. More context on the fix can be found here (#2493)

[Savio-Sou]

as the change was only incldued in ACVM

Is it just a wait for ACVM v0.24.0 that contains the fix to go into Noir?

[Savio-Sou]

Is this an open issue still?

[ax0]

Nope. I can confirm that proofs can now be generated for the linked program.

[Savio-Sou]

Closed, potentially with #2504.