Consider removing ComputeMerkleRoot opcode and relying on Noir implementation.

[TomAFrench]

Problem

We currently have two implementations for merkle root computation, one as a black box function in barretenberg and another in Noir:

https://github.com/noir-lang/noir/blob/e790c9f5da784f7617a0b578623b470af7e01116/noir_stdlib/src/merkle.nr#L12-L31

The requires backends to implement not only a pedersen hash gadget but another for merkle trees, which is unnecessary.

Proposed solution

We can remove the ComputeMerkleRoot opcode and just rely on the Noir implementation of merkle tree proof verification.

This would simplify backends (no need to ensure that native and Noir implementations match) with the downside of slightly more verbose ACIR code.

Alternatives considered

No response

Additional context

We currently implement solving of ComputeMerkleRoot opcodes up in https://github.com/noir-lang/acvm-backend-barretenberg/blob/master/src/acvm_interop/pwg/merkle.rs. Ideally we should bring this solver down into ACVM and call out to the backend for the pedersen hashes only.

We could do this now but it doesn't make much sense if we're just going to remove the opcode entirely.

Submission Checklist

• Once I hit submit, I will assign this issue to the Project Board with the appropriate tags.

[TomAFrench]

@kevaundray, I'd be interested to know your opinion on this.

This would be a non-breaking change for Noir but would break any existing ACIR programs. As we're changing the serialisation logic in the next release (which would break these anyway) then now is a good time to remove this opcode.

[kevaundray]

@kevaundray, I'd be interested to know your opinion on this.

This would be a non-breaking change for Noir but would break any existing ACIR programs. As we're changing the serialisation logic in the next release (which would break these anyway) then now is a good time to remove this opcode.

I think it's fine to remove this if it's wholly redundant