Merkle membership functionality

[kevaundray]

(Noting that these ideas came from a discussion with Zac Williamson, who clarified a lot of the functionality that is needed for merkle trees and also possible extensions)

Currently for merkle membership, we need to provide the index and the hash path explicitly. This is not wholly problem, however, it is clutter since they will only be used for set-inclusion proofs. Below we explain the rationale behind this and the new API.

Assumptions

• Leaves in the merkle tree are unique. This assumption is valid, since we use merkle trees for set memberships and not multi-set memberships.

Indices and Hashpaths

For a sparse merkle tree, the index is the value, hence hiding the index will not be a problem since the value is explicitly computed or present.

For a regular merkle tree, the index is the next available empty leaf slot. This is not deterministic and relies on when a particular leaf is inserted. This potentially could introduce unwanted non-deterministic code into Noir from the witness. Furthermore, at least for now, one cannot think of a situation where we would need to use the index in any logic.

New API

The new API will therefore ask the witness generator for the hashpath and the index, and we will populate ACIR from the witness generator.

We will also introduce terms to differentiate between a sparse merkle tree and a non-sparse merkle tree, where the former allows non-membership checks.

[kevaundray]

Although https://github.com/noir-lang/noir/pull/115 was merged. Leaving this open to track update functionality

[kevaundray]

closing as we now have a different API and we are thinking about memberships by encpasulating behaviour in a struct.