codegen and proving fails on oob mem access with 10+ depth tree for compute_merkle_root

[n4ru]

Aim

I am attempting to compute the root for a large merkle tree. Ideally, for near-arbitrary depths (2^32 or more). This needs to be done in-circuit.

Expected Behavior

A solidity verifier should be generated. The circuit should be provable with nargo, bb.js, or whatever library ends up being used in browsers.

Bug

     Error: Command failed: nargo codegen-verifier
Error: Trying to call acir_proofs_init_proving_key resulted in an error

Caused by:
   0: RuntimeError: out of bounds memory access
   0:     at <unnamed> (<module>[294]:0xae003)
   0:     at <unnamed> (<module>[1003]:0x37ce6b)
   1: heap_get_oob

When trying to generate a solidity verifier or proof using a circuit that runs compute_merkle_root and takes a hash_path for a tree that is too deep (in this case 10+ levels), it fails with the above error.

Since compute_merkle_root just does a bunch of pedersen hashes, this issue seems to occur whenever you nest a large amount of loops. The gate count in my misbehaving circuit is sub-150k, so it is not a gate issue.

I was told the issue is resolved in newer nargo builds, but not inside the wasm proving build. I explicitly need this to work inside a browser for production, which means it has to run inside the wasm build.

To Reproduce

1. Use compute_merkle_tree on a big hashpath.
2. Attempt to generate a Solidity verifier or attempt to prove the circuit.

Installation Method

None

Nargo Version

nargo 0.10.3 (git version hash: 2db759f, is dirty: false)

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response

[Savio-Sou]

Thanks for creating the issue!

I was told the issue is resolved in newer nargo builds, but not inside the wasm proving build. I explicitly need this to work inside a browser for production, which means it has to run inside the wasm build.

Just to clarify, were you generating the Solidity verifier with nargo codegen-verifier or through the noir_wasm JavaScript package?

(Or was the "wasm build" referring to the WASM-based Nargo releases?)

Would be very helpful if you could link to a code snippet for reproducing the issue too! 🙌

[n4ru]

I am using nargo codegen-verifier and nargo prove on 0.10.3.

The code is simply any circuit with a compute_merkle_root call which takes a hash_path for a deep tree. Can post a minimally reproducible circuit/prover.toml in a bit.

[Savio-Sou]

Thanks!

To confirm nargo prove was failing as well? What was the error you were prompted with?

[Savio-Sou]

With the #4960 initiative, nargo codegen-verifier and nargo prove would be deprecated. Proving backends (e.g. Barretenberg) would be providing such utilities directly.

If the Issue here exists still with latest Barretenberg versions, creating an Issue on https://github.com/AztecProtocol/barretenberg is recommended 🤝 thanks!

[n4ru]

I believe at some point a few versions ago this issue was resolved. :)