Re: [MLS] Cost of the partial-tree approach

[Raphael Robert <[e-mail]>]

Having to choose between security and efficiency is always a terrible choice to make. I'd like to explore an idea where the only choice is about how the workload is distributed.

I made some simulations to see how quickly the workload converges from linear to ~log N for the partial-tree approach (see graph in [1]). The setup was as follows: the tree creator added 1k members to a tree at once. The members iteratively did updates in a random order. I measured the copath length after each update (min, max and average). The length of the copath is equivalent to the number of DH / KEM operations the sender has to do, and thus the size of the message. Note that in a punctured tree the copath is not the list of siblings of the direct path anymore, rather every node of the copath needs to be "resolved" if it is a blank node. In a tree with many blank nodes the new copath can therefore be quite long.

The graph clearly shows the efficiency is very bad for the initial set of updates, but also quickly converges after only a fraction of the updates have been done.
My conclusion from this is that a full tree is not necessary to address the efficiency issue.

Instead of pre-populating the whole tree with node secrets, it might be enough to only pre-populate a fraction of the nodes. With the blanking mechanism, nodes can be arbitrarily blanked/populated. The only rule is that leaf nodes need to know the node secrets of their (non-blanked) parent nodes.
This means that we can pre-populate whatever nodes are most suitable to improve efficiency. This happens to be the case with the top of the tree (the top being the part close to the root of the tree). The closer a node is to the root, the more likely it is to be part of an arbitrary copath. Conveniently, the same node is equally likely to be overwritten during an update, henceforth removing the double-join state for that node. Even more conveniently, the top of the tree contains far fewer nodes than the rest of the tree, making the pre-population quite cheap.

An example in numbers:
A tree is vertically divided in "levels". A tree with 1k leaves has log2(1k) ~ 10 levels. Let's say we pre-populate the upper 5 levels of the tree (the "top"). The top contains about ~3% of the total number of nodes in the tree. After only 1.5% of the members have updated (assuming an even distribution of members who update) the top of the tree does not contain double-joins anymore. The copath length for early updates is drastically reduced as can be seen in [2]. The comparison with the empty tree can be seen in [3].

However while this effectively increases efficiency, the double-join issue remains during the early epochs of a tree. Now since the number nodes that were pre-populated is relatively low, it might just be practical to use a bookkeeping mechanism to track those nodes.
If a node secret is known to a member that is not a descendent of that node, this is considered to be a double-join. For every such node, we can simply keep a list of illicit owners.
Whenever a member is evicted from the group, additional blanking has to be done: So far only the nodes in the direct path of evicted member had to be blanked, now we also blank the nodes the evicted member double-joined. It is important that all of blanking happens before new values are KEMed to the resolved copath of the evicted member. This guarantees that the evicted member doesn't have any access to any node secrets anymore.

The entries of the bookkeeping (the "book") have to be shared with newly invited members. It is important that every member has the same view of the book to guarantee that eviction can always be fully achieved. Passing the book to a new member therefore has to be tamper-proof, because especially inviting members might have an incentive to lie about the nodes they double-joined. The book could simply be added to the group state, so that its content is "pinned" when deriving epoch secrets. This would guarantee that a new member either sees the same book as the rest of the group, or they cannot derive the same epoch secrets.

The same mechanism of pre-populating nodes in the tree ("warming up" the tree) could be used more generally when adding new members to the group. Instead of just adding the UserInitKey of the new member, the inviting member could warm up the direct path of the new member (except the leaf node of the new member). This would avoid inserting new blank nodes in the tree when adding a new member.
Conversely, this could potentially also be done when evicting a member. Instead of blanking the direct path of the member, the evicting member could simply overwrite all or a part of the blanked nodes, avoiding a punctured tree at the expense of increasing the bookkeeping effort. Note that if a blank node is overwritten, the children of that node need to know its secret. The secret needs to KEMed to all children. This happens implicitly when overwriting a direct path, but needs to be done manually when overwriting arbitrary blank nodes, which could occur as a result of the bookkeeping. This could lead to a high number of KEM operations, and blanking double-joined nodes (that are outside of the direct path of the evicted member) might just be cheaper. As mentioned above, the blanking has to be done before new values are KEMed to nodes in the tree.
It remains to be seen in which situations this makes sense in terms of efficiency and what the best balance is between additional bookkeeping and puncturing the tree. Aside from some ground rules, further simulations could give an indication.

Assuming the bookkeeping mechanism works as intended and no other problems arise, the choice comes down to how much warming up is desired. Ultimately, this choice could be left to the members themselves, assuming they all have the tree efficiency as a common interest. This would allow for dynamic decision taking based on the tree structure.

Raphael

[1] https://imgur.com/a/wZtueOX
[2] https://imgur.com/a/My8anBs
[3] https://imgur.com/a/ZvmdfeH

> On 1 Oct 2018, at 18:17, Richard Barnes <[e-mail]> wrote:
> 
> Hey all,
> 
> There was some debate at the interim about the performance implications of the "partial-tree" approach to adds and removes [0] (derived from the "remove-without-double-join" approach described on the mailing list [1]).  In particular, EKR expressed concern that this approach would cause message size to degrade from log to linear.  To test this out, on the plane home I wrote a simulator that performs random group operations and compares two approaches:
> 
> 1. The "full-tree" approach, which has optimal efficiency but also has double-joins
> 2. The "partial-tree" approach, which has no double-joins but sub-optimal efficiency
> 
> I've made a little visualizer here:
> 
> https://ipv.sx/treekem/blanking/ <https://ipv.sx/treekem/blanking/>
> 
> The tl;dr is that the partial-tree approach is only very bad if you have a very sparse tree, in particular, if you follow the "Init w/o 2J" approach of [0].  In all other cases, as long as updates happen sufficiently frequently, the two approaches are within a small constant factor of one another.  The intuition here is that adds / removes degrade the tree (since they add blank nodes) while updates heal the tree (since they fill in blank nodes).  
> 
> If you have the simulator start out with a sparse tree (untick "Start full"), you'll see that initially, the "partial-tree" approach is very bad, pretty much linear, but it gets better as nodes update, and eventually merges with the "full-tree" line.  If you start with a full tree, the lines don't diverge.
> 
> Obviously, this isn't dispositive in one direction or another.  But ISTM that this experiment indicates that the cost of the "partial-tree" approach might not be too bad, given that it clears up a significant ambiguity / saves the cost of double-join bookkeeping.
> 
> --Richard
> 
> [0] https://github.com/mlswg/wg-materials/blob/master/interim-2018-09/no_more_double_joins.pdf <https://github.com/mlswg/wg-materials/blob/master/interim-2018-09/no_more_double_joins.pdf>
> [1] https://mailarchive.ietf.org/arch/msg/mls/Zzw2tqZC1FCbVZA9LKERsMIQXik <https://mailarchive.ietf.org/arch/msg/mls/Zzw2tqZC1FCbVZA9LKERsMIQXik>
> 
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls