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

[Richard Barnes <[e-mail]>]

I agree there are synchronization problems, but I don't think they're
appreciably worse than before.

Right now, when you have an Update or Add conflict now, the retry logic is
"do it again"; for Remove, it's either "do it again" or "never mind",
depending on whether the thing you conflicted with was a Remove for the
same slot.

When you have a conflict with Move / Add-in-place, the retry logic is "do
it again with a different slot" or "never mind", where the latter hits if
you were going to move to a lower slot to compact the tree, but all the
lower slots are now filled.  So the only major difference relative to the
above is that you need to pick a new target.  That seems as straightforward
as a lowest_available_slot() method, which returns the next leaf if the
tree is full.

In any case, once we settle down on the set of operations, we should take
another stab at describing retry considerations.  I filed an issue [1].

--Richard

[1] https://github.com/mlswg/mls-protocol/issues/76

On Tue, Oct 23, 2018 at 5:15 AM Russ Housley <[e-mail]> wrote:

> Don't add and move make synchronization concerns worse?  Can two clients
> ask for the same empty-when-they-looked node?
>
> Russ
>
>
> On Oct 22, 2018, at 2:59 PM, Raphael Robert <[e-mail]> wrote:
>
> 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 <[e-mail]> 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/
> [2]
> https://github.com/bifurcation/treekem/commit/7f470422ba61ce668c3ab1d6b2d18edd9d6e06fd
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>
>
>