In the current PartialSmt we only allow updating leaves that are tracked. A leaf is considered tracked, when it is in the underlying Smt::leaves field. However, we could allow updates to leaves that are not in the leaves field, if a merkle path happens to be in the partial SMT for that key. See also #372 (review) for a visual example.

By changing the definition of when a leaf is considered tracked, we can make the PartialSmt more flexible.

One way to change this, is to use this definition:

fn is_leaf_tracked(&self, key: &RpoDigest) -> bool {
    let current_proof = self.0.open(&key);
    let proof_root = current_proof.compute_root();
    proof_root == self.root()
}

However, this requires computing a proof and then also hashing the entire proof for every operation we check whether a leaf is tracked (which is basically all of them, e.g. open, get_value, insert, ...).

A slightly faster way to check if a leaf is not tracked would be by starting to compute an opening. As we traverse the merkle path we check whether the hashes we compute are consistent with the InnerNodes we encounter along the way. If they aren't consistent, then the leaf is not tracked.
However, for a leaf that is tracked, we would, again, have to compute all hashes all the way to the root to make sure it is tracked, which is as bad as the above definition of is_leaf_tracked.

A hybrid approach could be do keep using the leaves field to check if a leaf is tracked, and only fall back to the above definition if the leaf is not present in leaves. Depending on the operation, we can then mark the leaf as tracked in the leaves field as a way to cache the tracking.

There may be a better way to do all of this, this is just a write-up of what I have thought about.

Finally, here is a test, that may or may not help during the implementation which asserts that a leaf which is is not tracked explicitly, but for which a merkle path actually exists, can be updated.

#[test]
fn partial_smt_update_empty_subtree() {
    let key0 = RpoDigest::from(Word::from([ZERO, ZERO, ZERO, ONE]));

    let value0 = Word::from(rand_array());

    let kv_pairs = vec![(key0, value0)];

    let mut full = Smt::with_entries(kv_pairs).unwrap();

    let proof0 = full.open(&key0);

    let mut partial = PartialSmt::from_proofs([proof0]).unwrap();

    // The key we added is in the left subtree, so we expect the right child of the root to be
    // an empty subtree. In the partial SMT then, we can update any value in the right subtree
    // since they are all empty.
    let empty_subtree_root_depth_1 = EmptySubtreeRoots::entry(SMT_DEPTH, 1);
    assert_eq!(
        *empty_subtree_root_depth_1,
        partial.0.get_inner_node(NodeIndex::root().right_child()).hash()
    );

    // Construct a key that will be in the right subtree.
    let key1 = RpoDigest::from(Word::from([
        ZERO,
        ZERO,
        ZERO,
        BaseElement::try_from(BaseElement::MODULUS - 1).unwrap(),
    ]));

    let value1 = Word::from(rand_array());

    full.insert(key1, value1);
    partial.insert(key1, value1).unwrap();

    assert_eq!(full.root(), partial.root());
}