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

Function conditionally_check_membership

pub fn conditionally_check_membership<let TREE_HEIGHT: u32, LEAF_PREIMAGE, VALUE>(
    key: Field,
    exists: bool,
    leaf_preimage: LEAF_PREIMAGE,
    membership_witness: MembershipWitness<TREE_HEIGHT>,
    tree_root: Field,
) -> (bool, bool, bool)
where
    LEAF_PREIMAGE: IndexedTreeLeafPreimage<VALUE>

Check either membership or non-membership depending on the value of exists:

If exists == true, key is in the tree. leaf_preimage is for the key itself.
If exists == false, key is not in the tree. leaf_preimage is for the low leaf of the key. membership_witness is the hint to prove that the leaf_preimage exists in the tree with the given tree_root.

Returns:

is_valid: true if the membership (exists == true) or non-membership (exists == false) check succeeds, false otherwise.
is_expected_leaf: true if the leaf preimage is the expected matching leaf (exists == true) or low leaf (exists == false) for the key, false otherwise.
is_leaf_in_tree: true if the leaf preimage exists in the tree, false otherwise.