[MLS] Lazy handshake messages

[Raphael Robert <[e-mail]>]

Hi all,

Currently Update handshake messages are computed in an eager fashion: the
sender of a message has to do most of the work (O(log n) - O(n)) and other
group members just consume the HS message in O(1).

This leads to a bottleneck situation when a new device is added or removed
by a user (as explained at IETF 103). Depending on what multi-device mode
is being used (concealed devices under the own leaf node or 1 device per
leaf node), either and Update or an Add+Update have to be carried out in
every group. This can lead to costly operations (at least O(log n) ECIES
operations, worst case O(n) ECIES operations) in potentially hundreds of
groups.

Adding a new device or removing an old one can therefore lead to
considerable UX lag, because these operations cannot really be done in the
background and therefore constitute a large blocking atomic operation.

The following explores the idea of considerably reducing the size of the
atomic operation by asynchronously outsourcing expensive calculations to
other members of the group.

Lazy Update
-----------------

Steps:

  1. The sender creates a new leaf node (NLN), but doesn't "hash it up".
  2. The public key of the NLN is sent to the group in a new HS message
(LazyUpdate)
  3. Everyone in the group replaces the old leaf node (OLN) of the sender
with the new leaf node (NLN)
  4. Everyone blanks the sender's direct path

Aside from creating the new leaf node, no cryptographic operations have
taken place. This means FS and PCS are not guaranteed yet.
Every LazyUpdate therefore has to be followed by a regular Update, no other
regular HS message is allowed to follow a LazyUpdate (and must be rejected
by recipients). The regular Update can be issued by anyone in the group
using node resolution. That way the owner of the OLN cannot know the new
group secret (PCS) and the owner of NLN cannot know the old group secret
(FS).

The idea behind this approach is that costly operations can be spread over
time, as there is no need to issue the regular Update right away. If a
group is completely inactive, i.e. no messages are being sent, there is no
need to rotate the group secret pre-emptively, it can rather be rotated
"just in time".

The owner of the NLN only needs to know the current init secret of the
group to be able to process the regular Update that follows the LazyUpdate.
This means that several LazyUpdates can be stacked before a regular Update
is issued. Naturally every subsequent LazyUpdate will further unbalance the
tree and thus reduce efficiency. It is therefore recommended that active
members issue Updates as soon as they see fit, however each member can
apply its own strategy. For example, mobile devices might not do Updates as
frequently as PCs because of resource constraints.
Ideally, the owner of the NLN will do the regular Update themselves. In
that case the secret of the NLN probably can just be "hashed up" and KEMed
to its resolved copath. This would then be a "slow Update" stretched over 2
phases: Announcing the public key of the node leaf first (in the LazyUpdate
message), doing the KEMing later (in the Update message).

A similar concept can potentially also be applied to Remove HS messages,
where a member merely announces the removal, everyone else blanks the
direct path of the removed member, but the key rotation (by means of
issuing an Update HS) only occurs later.

Raphael