Re: [MLS] Move / Add-in-place / Compounding

I think these two operations make perfect sense (had the same ones in mind). Some comments:

Regarding Move:
We should work on a recommendation of when to do a Move instead of an Update, and also of when to do a Move even if no Update was planned.
The recommendation could initially be something naive, such as: when the ratio of blank leaves / full leaves is greater than xxx, do a Move. 

Regarding Add-in-place:
I think this has the potential of becoming the default, as opposed to the current Add. Maybe both operations could be one and the same if we just add an index to the current Add. In that case the recommendation for the index would simply be the left-most empty leaf node.

If both operations are correctly applied by clients, the tree should have the optimal size.
There is however a case where trees will not shrink, but only if the following three conditions are met:

 - A large number of members left the group (large is relative to the group size)
 - A large number of the remaining members never come online again and therefore cannot move themselves (large is again relative to the remaining group size)
 - Only very few new members are added subsequently

I suspect that the above scenario is however an edge case. If it occurs “in the wild” it might eventually get solved on a social level (when unresponsive members get removed by active ones).

> On 22 Oct 2018, at 20:34, Richard Barnes <rlb@ipv.sx> wrote:
> 
> Hey MLS folks,
> 
> tl;dr: 
> - Would there be interest in a Move operation?
> - How about an operation to Add a new member in an open slot instead of the right edge?
> 
> In looking at the "partial tree" stuff (#67), it occurred to me that once you have partial trees with blank leaves, you can in principle do two new operations: An existing member can move from one leaf in the tree to another; and an existing member can add a new member at a leaf that is currently blank.  These operations would work roughly as follows:
> 
> - Move:
>     - Blank out old dirpath
>     - Move credential from old slot to new slow
>     - Send update along new dirpath
> - Add-in-place:
>     - Blank out dirpath for slot
>     - Install new member's leaf key in slot
>     - Install new member's credential in slot
> 
> For Move, you would also want to have people step down the size of the tree.  For example, if you go from having 10 leaves (X _ X X _ _ _ _ _ X) to four leaves (X X X X) as the result of a move, then the resulting tree should only have height 2, not 4 (as is required for 10 leaves).  Fortunately, this is trivial with the tree math defined in the document; you just truncate the node vector, and the calculated root gets correspondingly smaller.
> 
> I've prototyped this out in my JS stack [1][2].  Once you've built a tree, and removed a couple of members, you can click one of the "Move" buttons to move that node to the lowest open slot.  As you can see, it's not a ton of code.
> 
> In any case, this seems to me to be potentially useful, since it addresses the issue that was raised in the BoF that the size of the resources for a group increases monotically.  Move allows you to reclaim resources that are unused (assuming some orchestration outside of MLS), and Add-in-place allows us to be conservative with resources that are already allocated (cf. realloc).
> 
> If folks think these sound like useful tools, I'll write up a PR and we can discuss in BKK.
> 
> --Richard
> 
> [1] https://ipv.sx/treekem/ <https://ipv.sx/treekem/>
> [2] https://github.com/bifurcation/treekem/commit/7f470422ba61ce668c3ab1d6b2d18edd9d6e06fd <https://github.com/bifurcation/treekem/commit/7f470422ba61ce668c3ab1d6b2d18edd9d6e06fd>
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls