Re: [MLS] Remove without double-join (in TreeKEM)

I think this is an interesting thought! In practice — when groups are somewhat dynamic — the blanks in the tree would be filled pretty quickly with new members. The only edge case I can think of right now would be when a group starts with a large amount of members, and it size decreases over time. But that scenario is generally a problematic one regarding efficiency.

Raphael

> On 6 Aug 2018, at 15:00, Richard Barnes <rlb@ipv.sx> wrote:
> 
> Hey all,
> 
> On Friday, I got to thinking about how to do the Remove operation with TreeKEM, and I think I've got a way to do it that avoids double-join problems while still being pretty elegant.
> 
> - When a member is removed from the group, remaining members update their local caches of the tree so that any nodes in the direct path of the removed leaf are set to blank
> - This means that for future group operations, some of the nodes you would encrypt to might not be blank
> - Extend the "encrypt to subgroup" function so that if the node at the head of the subgroup is blank (i.e., the subgroup is not full), then you work down the tree and encrypt to all the subtree heads.
> 
> In the short run, this fragments the tree.  In the worst case, if you delete every other member, you end up with linear updates.  This is mitigated by a few nice features, though:
> 
> 1. The tree "heals" as members update: Because an Update contains a direct path that overwrites any blanked-out nodes, from the perspective of the rest of the tree, subtrees with heads along that path are now whole from the perspective of nodes outside those subtrees.  A healed tree will still be "stringy".
> 
> 2. New members can be added into the blank leaves just by sending an Update (just like UserAdd / GroupAdd, but without growing the size of the tree).  Existing members can relocate to a blank slot in the same way.
> 
> With a bit more cleverness, it might be possible to shrink a tree back down to its minimal size after adding a bunch of members and removing them all.
> 
> I've implemented a first pass at this approach in my JS demo stack at <https://ipv.sx/treekem/ <https://ipv.sx/treekem/>>.  You can delete nodes after adding them, and updates still work.  Adds appear to be broken for the moment, but I think that's surmountable.
> 
> ---
> 
> Now, it's still possible to do Remove by the sender of the Remove doing an Update for the removed, using a leaf secret the removed node doesn't know.  That leaves the tree intact, at the cost of having the sender double-joined in the removed slot as well as his original slot.  (Effectively, it's a take-over operation.)
> 
> So we have now two choices for trade-offs around Remove:
> 
> 1. Leave some parts of the tree empty and track subtree heads; no double join
> 2. Keep the tree full and only have normal copath logic; but accept double join
> 
> Personally, I find the logic of double-join bookkeeping more intimidating than the logic to keep track of the tree..  But I would be interested in what other folks think of these trade-offs.
> 
> It might also be interesting to think of whether ART could be extended to do remove-without-double-join in something like the above way.  It wasn't immediately obvious to me, but I didn't try very hard.
> 
> --Richard
> _______________________________________________
> MLS mailing list
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls