question about "we can only remove pairs of leaves when both are pruned"

[garyyu]

Recap the short conversation in Gitter:

Gary Yu @garyyu Sep 12 21:15 https://github.com/mimblewimble/grin/blob/master/store/src/pmmr.rs#L442-L444

                if sibling_pruned || expanded.contains(sibling as u32) {
                    expanded.add(parent as u32);
                    current = parent;
                }

One question here, in current version, we remove data & hash ONLY if the sibling also pruned, then the pruned leaf with sibling not pruned can’t get data & hash removed. What’s the reason to keep this pruned leaf?

Antioch Peverell @antiochp Sep 12 23:10 @garyyu to be able to generate a Merkle proof for any given leaf we need all siblings in the path up the tree to the root. So we can only remove pairs of leaves when both are pruned.

[garyyu]

@antiochp thanks for answer. but in PMMR, we already have the hash for the parent of this given pruned leaf and its not pruned sibling, why we can't remove the data & hash of this given pruned leaf?

[antiochp]

We already have the hash of the parent yes, but we need to be able to provide a hash of the sibling in the proof to prove a node is indeed a child of the parent (of both children).

Say we have a simple MMR like this -

 A
 /\
B  C

To prove B is a child of A we need the hash of its sibling C. Then we can take that the provided hash and hash it together with the one from B to generate a hash for C and verify it against the actual hash for C.

i.e. to prove B is a child of A we need the hash of C.

we cannot do this for B is the hash and data for C have been removed. I think technically we could remove the data for C but we need to the hash itself. And we do not currently track pruned-ness of data and hash separately.

I'm sure I'm not explaining this particularly well - does it make sense?

[garyyu]

Gary Yu @garyyu Sep 13 22:26

@antiochp thanks for your good explanation. and in which situation we need prove a node is indeed a child of the parent?

Antioch Peverell @antiochp Sep 13 22:57

we do not actually use Merkle proofs anywhere today - we were considering using them for proving coinbase maturity (and we needed to know which block a coinbase output originated from, which we could do by proving where it was in the MMR)

but we wanted to be sure they worked in principle

(we care less about it being the child of a particular parent, more that it is a descendent of the overall root, which we commit to in each block header)

[antiochp]

Yeah - so this is mainly to have an MMR in a state that supports arbitrary Merkle proofs, even though we're not actively using them today.

[ignopeverell]

And Merkle proofs are part of many higher-level protocols, so it's really good to be able to support them so well.

[garyyu]

Closed, since it's indeed the design behavior.