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

From: Richard Barnes <[email-masked]>
Date: Mon, 6 Aug 2018 09:00:57 -0400

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

---

From: Raphael Robert <[email-masked]>
Date: Mon, 6 Aug 2018 21:08:36 +0200

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 <[email-masked]> 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.)
> 
> 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
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls

---

From: Richard Barnes <[email-masked]>
Date: Tue, 7 Aug 2018 10:12:36 -0400

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 <[email-masked]> 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
>
> - 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.
>
> 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.
>
> than the logic to keep track of the tree..  But I would be interested in