aztec-nr - noir_aztec::protocol::merkle_tree::membership

Function check_non_membership

pub fn check_non_membership<let TREE_HEIGHT: u32, LEAF_PREIMAGE, VALUE>(
    key: Field,
    low_leaf_preimage: LEAF_PREIMAGE,
    low_leaf_membership_witness: MembershipWitness<TREE_HEIGHT>,
    tree_root: Field,
) -> (bool, bool, bool)
where
    LEAF_PREIMAGE: IndexedTreeLeafPreimage<VALUE>

Check a key's non-existence in the indexed tree with the given tree_root. low_leaf_preimage is the preimage for the low leaf of the key. The key should be larger than the low leaf's key, and smaller than the low leaf's next key. low_leaf_membership_witness is a hint to prove that the low leaf exists in the tree with the given tree_root.

Returns:

non_existence: true if the key does not exist in the tree, false otherwise.
is_valid_low_leaf: true if the key is in range of the low leaf, false otherwise.
low_leaf_exists: true if the low leaf exists in the tree, false otherwise.