Re: [MLS] Optimizing Unmerged Leaves (or: bringing the MLS tree size back to O(n))

[Karthik Bhargavan <[e-mail]>]

Hello All,

Getting back to this suggestion from several months ago.
Recall that the issue is that the MLS tree size with explicit unmerged leaves can grow to O(N log N) and the suggestion in this thread would bring it down to O(N).

We worked the precise changes needed to the spec to achieve this and it can be done with a small change. The patch is attached.
The key observation is that unmerged leaves for each node can be recomputed if each node has an epoch timestamp.

In implementations, members may want to pre-compute and store the unmerged leaves lists just like in the current design, 
and only use this compression proposal when creating Welcome messages.
However, as discussed in this thread and elsewhere, in practice the “log N” factor does not appear to make much of an impact.

So, we are not proposing this as a PR at this time, and are attaching the patch only as reference, in case this size optimization becomes important in the future.

Best,
Karthik.


> On 21 Jun 2021, at 13:14, Théophile Wallez <[e-mail]> wrote:
> 
> Hi and sorry for the late answer,
> 
> I'll also respond inline:
> 
> On 22/05/2021 12:14, Raphael Robert wrote:
>> 
>>> On 21. May 2021, at 16:59, Karthik Bhargavan <[e-mail] <mailto:[e-mail]>> wrote:
>>> 
>>> Solution 1
>>> —————
>>> 
>>> One possibility, close to the current MLS spec would be to not store the unmerged leaf at a node if it is already stored at the parent.
>>> This way, every leaf is present at most once in some `unmerged_leaves` array.
>>> In the worst case, this uses 4*n + 4*(n/2) = 6*n bytes (4*n for the `unmerged_leaves` array size, 4*(n/2) because at most n/2 leaves are stored in the `unmerged_leaves` arrays).
>>> In the best case, this uses 4*n bytes.
>>> The tree resolution algorithm will now have to do a little more calculation to re-compute the unmerged leaves at each node.
>> 
>> 
>> This sounds rather straight forward on a logical level. It clearly reduces the stored/transmitted payload size, but it introduces a new cost: previously only O(log n) nodes needed to be modified during an Update/Remove. Now we might have to “push down” the book keeping information from parents to children, in the worst case this affects n/2 nodes, so the cost of modifying nodes goes up to O(n).
>> If we consider a very large group, there would be a measurable difference when clients load/store nodes from/to disk.
>> My current intuition is that currently I/O operations can be done in O(log n) with clever parent hash caching. The worst case here would be the following: A client is a member of a large group and has been offline for a while (which is not a far fetched scenario). The client now comes online and has to process a large number of handshake messages. For robustness, the client might be inclined to frequently persist the intermediary state. This is where the I/O cost kicks in.
> 
> Indeed, when "pushing down" the unmerged leaves, if it is pushed down to a blank node, we might have to modify more than O(log n) nodes. This could be solved by storing unmerged leaves in blank nodes, but it is starting to get quite ugly.
> 
>>> Solution 2+
>>> —————
>>> 
>>> However, if we wish to compress further, we can do so as well, using two facts:
>>> - if a node `n` has two children `l` and `r`, then n.last_update_epoch is equal to either l.last_update_epoch or r.last_update_epoch,
>>> - if `l` is unmerged for some node then l.creation_epoch = l.last_update_epoch (because in this case, the leaf never generated an UpdatePath) (the converse is not true, for example in the case when its sibling generates an UpdatePath).
>>> 
>>> So at each node, we can store the direction from which the node was last updated (for example with a boolean flag), then given any node `n` we can "follow the path" down the tree to obtain a leaf `l`, and we have n.last_update_epoch = l.last_update_epoch.
>>> Furthermore, we don't need to store the creation epoch for leaves:
>>> - if `l` is unmerged for `n`, then n.last_update_epoch < l.creation_epoch = l.last_update_epoch,
>>> - if `l` is not unmerged for `n`, then n.last_update_epoch >= l.last_update_epoch (because when `l` is updated, it updates all the nodes above it).
>>> This uses 8*n + 1*n = 9*n bytes for the whole tree.
>> 
>> I didn’t check all the ramifications here tbh. I think it is similar to solution 1 in terms of increased I/O cost.
> 
> Actually, there is no "pushing down" here, when modifying nodes on a path from leaf to the root, only those nodes are modified (we update the direction of the parent nodes in the path, and update the last update epoch of the leaf), so the I/O cost is actually O(log n).
> 
> Thank you for your comments,
> Théophile.
> 
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls