I've added notes based on the papers I've read on Merkle trees, Verkle trees, and the Mutator set. For Merkle trees, I reviewed Aztec's work on the index Merkle tree and noted the differences from the sparse Merkle tree.

Challenges with Sparse Merkle Trees

The current design of nullifier trees leverages Sparse Merkle Trees (SMTs) to facilitate membership checks. SMTs store nullifiers at leaves indexed by their value, with each path from leaf to root representing a membership proof. However, SMTs have limitations when used in cryptographic circuits:

• Tree depth and hashing costs: For an SMT designed over the bn254 curve, which supports $2^{254}$ values, the tree depth must be 254. Every membership proof requires 254×2 hashes, making nullifier insertions computationally expensive.
• Linear scaling: As nullifiers are randomly inserted, the number of constraints and hashing operations scales linearly with the number of insertions, leading to circuit bloat and slow proof generation.

Overview of the Indexed Merkle Tree

Indexed Merkle Trees (IMTs) address the inefficiencies of SMTs by modifying the structure of each node. In an IMT, each node not only stores a nullifier but also pointers to the next higher nullifier in the tree. This results in a linked list-like structure within the Merkle tree, where nodes are connected in increasing order of nullifier values. The key advantage is that we can now use a much smaller tree depth (e.g., 32 levels), significantly reducing the cost of nullifier insertions.

Non-Membership Proofs in IMTs

The IMT facilitates efficient non-membership proofs by allowing nodes to act as “low nullifiers,” representing the next lower and higher values surrounding the queried nullifier. When checking for non-membership, the system confirms that the nullifier falls between two existing values, significantly reducing the number of required hashes.

For example, to prove that a nullifier $v=20$ does not exist in the tree, the system reveals the "low nullifier" (e.g., $v=10$) and shows that its next value ($v_{\text{next}} = 30$) skips over 20. This requires a handful of hashes and range checks, instead of traversing a deep SMT.

Insertion Protocol in IMTs

Inserting a nullifier in an IMT follows a straightforward protocol:

1. Find the low nullifier $v_{\text{low}}$​ such that $v_{\text{low}} < v < v_{\text{next}}$​.
2. Perform a membership check for $v_{\text{low}}$ to confirm it exists in the tree.
3. Update the pointers of $v_{\text{low}}$ and insert the new nullifier with its pointers to $v_{\text{next}}$​.
4. Recalculate the tree root, adjusting pointers as needed.

This results in significantly fewer constraints compared to SMTs, as the tree depth is much smaller and fewer hashing operations are needed.

Pros

• Reduced Circuit Complexity: IMTs reduce the tree depth, leading to fewer hashing operations and constraints, which translates to faster proof generation.
• Efficient Non-Membership Proofs: IMTs allow for efficient non-membership checks without needing to traverse the entire tree.