I think this works, but it also seems like quite a heavy check.

I was thinking about an alternative approach. The main idea is that we'll only ever encounter an untracked leaf that is fine to update, if the value of the key is empty.

Also, the assumption is that the InnerNodes that are explicitly present (e.g. not retrieved through Smt::get_inner_node, since that defaults to subtree roots) in the underlying Smt::inner_nodes are all consistent with the root. This should be the case for partial SMT.

Then, if the leaf is not present, we can check if the value for the key we want to update is empty. If we can prove it is, we can update it, not otherwise. We can check whether a value is empty by comparing against the empty subtree roots until the first non-empty subtree root, which should only require computing one hash and equality comparisons otherwise.

More concretely, take the visualization from #372 (review) as an example. Conceptually, we can assume that the value for the key-to-check is empty and attempt to prove it by comparing it against the actual tree. Let's say we check for node_4:

• Compute:

  let leaf_idx = Smt::key_to_leaf_index(&key);
  let inner_node_idx = leaf_idx.index;

• Check if the parent InnerNode of node_4 (= c) in the actual tree is identical to EmptySubtreeRoots::get_inner_node(SMT_DEPTH, inner_node_idx.parent().depth()). In this example, it is, so we continue.
• Repeat to check that node c's parent is an empty subtree root. Again, it is.
• Repeat and the check fails since g is not an empty subtree root. Attempt to compute InnerNode { left: node_e, right: node_f }.hash() and check if that matches g. We can do this because node_e is present in Smt::inner_nodes. It matches, and since we're at the root - we know node_4 is an empty value that is consistent with the rest of the tree. So we consider it tracked.

I'm not fully convinced this works in all cases, but I believe the above is correct. There seem to be a few edge cases, so I'm not sure overall if it's worth it. Especially, considering that we currently don't really have a use case for updating leaves that are not explicitly tracked. But may be interesting to think about.

Thanks for the optimization suggestion!

After thinking further, it seems we can do this with zero hash computations.

Given that all explicit InnerNodes are already verified against the root, when we traverse up and hit a stored InnerNode, we just compare the empty-subtree root for that depth against the stored child hash.

Following your examples:
node_4 (tracked):
Walk up through empty nodes; at g we find a stored InnerNode with right = f_hash.
Compare empty_subtree_root == f_hash → matches (f is empty) -> tracked.
No need to compute hash(node_e, node_f).

node_2 (not tracked):
Walk up; at e we find a stored InnerNode with right = b_hash.
Compare empty_subtree_root == b_hash -> mismatch (b is non-empty because leaf 3 has data) -> not tracked.

I've implemented a test matching the visualization (local, not yet pushed): leaf 1 and leaf 3 have data, proof only for leaf 1.

Am I missing something?

I think this works, thanks for thinking about it further! You're right, we don't even need to hash anything. Very nice! Thinking about that way of checking now, it seems it would be low complexity and probably doesn't have many or any edge cases, so I think we can go ahead with that.

This affects the behavior of tracked_leaves iterator, iiuc.

I think the behavior of that iterator so far was that it returned all leaves that were explicitly added, e.g. using add_path, even after a key-value pair was set to the empty word. This is because we had special logic to reinsert the leaf, even if it's value was set to the empty word. We had that logic, so that it would still be possible to update that key's value because of our previous definition of "tracked leaf".

Iiuc, we no longer need that logic now because we consider that leaf tracked anyway, right?

The other question is, is it fine if tracked_leaves does not return leaves that were explicitly added before? This could happen if they were set to the empty word, which this logic here would remove.

I think the larger question is what the use of tracked_leaves is, now that it no longer returns the full set of leaves that can be updated. Making it return all of them would be impractical, and so I think we should remove that API. I checked in base, client and node and none of them seem to use this API, so it seems fine to remove.

With implicit tracking, we no longer need the special reinsertion logic since leaves in empty subtrees are trackable regardless. Removed tracked_leaves as suggested.

I think it would be good to keep the comment in the second bullet point, or adjust it depending on how we move forward, because how we treat empty leaves is subtle and easy to miss.

Iiuc, we still insert empty leaves into the Leaves map, but we could now optimize and skip adding those due to the new tracked logic, so:

if !leaf.is_empty() {
    self.leaves.insert(current_index.value(), leaf);
}

But, I think we generally trade memory for performance, and so it probably makes sense to still keep that "caching"? Any thoughts on this?

In any case, I think it would be good to keep/add a comment here explaining the rationale for dealing with empty leaves.

Agreed - kept the current behavior and added a comment explaining the rationale.

The original comment was outdated after decoupling, so I adjusted it to reflect that empty leaves are now implicitly trackable but we cache them to avoid the lookup cost.

I generally think we should check the inner consistency during deserialization. The code here assumes the input is trusted, since we don't check that leaves, inner nodes and root are consistent. I think this may be fine for the way we use it currently, but it would be very easy to start using in an RPC API context, where input is untrusted, without realizing that deserialization can mess up the invariants.

I think I would change this to assume untrusted input and validate the internal consistency. Maybe this could work by checking:

• that the deserialized InnerNodes are consistent with the root
• that each leaf's hash is consistent with its parent inner node's left/right child.

Maybe with the serialization refactor we could try to come up with a structure for supporting validating and non-validating deserialization, cc @bobbinth

Agreed. I think unless it creates significant complications, I would treat the inputs as untrusted (i.e., ideally, we'd validate the correctness of the deserialized data).

Added validation during deserialization - we now verify that each inner node's hash matches what its parent expects, and each leaf's hash matches its parent inner node.

Later we write // Key 0: CAN update (sibling of key 1, empty), but key0 and key1 are not actual siblings in the NodeIndex::sibling sense. So should the test setup here be such that leaf 0 and 1, 2 and 3, etc. are actual siblings, i.e. their LeafIndex::value is off by one? I think this would reflect the diagram more accurately, but then again, the diagram is inherently different from a depth 64 SMT so there's room for interpretation 😅.

I think both versions should effectively test the same thing, I just want to make sure the terminology in the comments is accurate 🙂

For key 5, 6, 7 it may be worth noting somehow that after updating key 4, the subtree is no longer empty. Just to make sure the test is not misunderstood easily.

Should we add an assert_eq!(full.root(), partial.root()); here?

Should we add a small test covering an inner node hash mismatch and a leaf hash mismatch to make sure validation is working as expected?

Done!