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

[Théophile Wallez <[e-mail]>]

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.