Update Partial MMR to add a single node to it

[Dominik1999]

<pls add description @bobbinth > and please add @hackaugusto as the assignee

[bobbinth]

We need to add a method to PartialMmr to enable adding of a single leaf - something similar to Mmr::add. I think add would be an appropriate method name here as well (and it would more consistent with naming in the Mmr) - but we already have PartialMmr:add. So, I think we can do the following:

1. Rename current PartialMmr::add into PartialMmr:track.
   a. This would also mean we should rename PartialMmr::remove into PartialMmr::untrack (or something like that).
2. Add PartialMmr::add method, which could look like so:

pub fn add(&mut self, leaf: RpoDigest, track: bool) -> Vec<(InOrderIndex, RpoDigest)>

When track parameter is set to true, the PartialMmr would start tracking authentication path for the new leaf, and would also return new nodes added to the PartialMmr as a result of this update.

The new implementation of PartialMmr::add could probably be pretty close to the current ChainMmr::add_block in `miden-base.

[hackaugusto]

When track parameter is set to true, the PartialMmr would start tracking authentication path for the new leaf, and would also return new nodes added to the PartialMmr as a result of this update.

I'm adding this in, could you add a bit of information on how it is used? It seems we started returning the tracked elements with #242, so it seems it is needed by the client?

[bobbinth]

The client stores the nodes of the partial MMR in a table. This table needs to be updated as the in-memory structure is updated. The way the client does it now is:

1. Hold the entire partial MMR in memory.
2. Run apply_delta() and get the newly-added nodes (the returned vector).
3. Insert these nodes into the table.

This does require us to load the entire partial MMR into memory - but I think this is fine for now (and in the future, we can figure out a more optimal way to do this).

[hackaugusto]

@bobbinth okay, so from what I got, this is done to save the PartialMmr state to disk, so that it can be restore on a subsequent run. Right?

What about deleting nodes that are no longer necessary? For example, if we have a forest with value 7 or 0b111, there are 3 peaks in the PartialMmr, if we add with track=false, these 3 entries will be merged, and effectively deleted form the PartialMmr, the new forest will be 8 or 0b1000 and will only have the merged peak.

[bobbinth]

this is done to save the PartialMmr state to disk, so that it can be restore on a subsequent run. Right?

Correct.

What about deleting nodes that are no longer necessary? For example, if we have a forest with value 7 or 0b111, there are 3 peaks in the PartialMmr, if we add with track=false, these 3 entries will be merged, and effectively deleted form the PartialMmr, the new forest will be 8 or 0b1000 and will only have the merged peak.

Peaks are stored separately - in the block_headers table. So, for every block header of interest, the client saves the peaks.

The chain_mmr_nodes table stores only the authentication notes (i.e. PartialMmr.nodes) and I don't believe we remove any nodes from there on apply_delta(). The only way to remove nodes is to use the current remove() function (or untrack() in the future), but this is not implemented yet.

Thinking about the future, it would be good if remove/untrack, returned a set of nodes deleted from PartialMmr.nodes so that we could use it accordingly in the future.

[hackaugusto]

Thinking about the future, it would be good if remove/untrack, returned a set of nodes deleted from PartialMmr.nodes so that we could use it accordingly in the future.

Created #262.

[hackaugusto]

done with #263