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

[Richard Barnes <[e-mail]>]

So just to prove out the power of this approach, I added an "autocompact"
button to the TreeKEM JS demo:

https://ipv.sx/treekem/

If you visit that link, you can build a group by clicking UserAdd or
GroupAdd a few times, then do some Remove and Move operations.  Then click
the full moon to turn on autocompact (no good emoji for this semantic) and
do a couple more removals -- notice that the tree automatically moves
members into vacant slots, and reduces the tree to the minimum size needed.

Obviously, to do this in a distributed group would require a lot of
orchestration.  But it's nice to see that it's allowed by the crypto.

Also on that page, there's a "chaos" button that will push random buttons
until you tell it to stop, if you just need some entertainment.  Found a
couple of bugs that way!

--Richard

On Mon, Aug 6, 2018 at 3:08 PM Raphael Robert <[e-mail]> wrote:

> 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 <[e-mail]> 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/>.  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
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>