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

[Richard Barnes <[e-mail]>]

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/>.  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