[MLS] Proposal: Proposals (was: Laziness)

[Richard Barnes <[e-mail]>]

Hey all,

I’d like to pose a question to the group of whether we should do “laziness”
or not.   The complete form will be long, but the short version is: Do we
care enough about DH overhead and server-initiated operations to do a
pretty significant refactor and possibly add some complexity to the
protocol?

I would like to get a go/no-go on this idea before writing a PR, since it's
going to be a big PR.  And it would be helpful to make that decision in the
next week or two, so that we can get the edits done and a new version out a
bit in advance of the interim.  So let's get this party started!

# Objectives

The overall goal is to meet two objectives:

1. Not requiring DH operations in groups where no messaging is happening
2. Allow some flavor of server-initiated Add and Remove

The first of these objectives was raised by Raphael some time ago; see his
presentation at the January interim for more details [1].  The second has
been a long-outstanding feature request, from Facebook and Cisco, among
others.

The useful insight is that both of these require deferred operations.  In
the first case, you want to defer DH operations until someone wants to send
a message.  In the second case, you might have the server propose an
operation that it can’t do, so that the execution of the operation is
deferred until someone in the group does it.

# Proposal

The proposal here is to refactor the protocol from “immediate mode” to
“deferred mode”.  None of the underlying tree math changes, just how we
talk about it.

* Add, Remove, and Update become “Proposals” that describe an operation,
rather than carrying the information to accomplish the information
immediately
    * Add = “Please add ${ClientInitKey}”
    * Update = “Please replace the leaf at ${index} with ${key} and blank
its direct path”
    * Remove = “Please  remove the member at ${index}
* Each epoch contains a set of proposals, followed by a Commit message
    * None of the proposed changes take effect until the Commit message
    * If there are outstanding proposals, you SHOULD send a Commit before
sending a message
* A Commit message contains:
    * A description of which proposals were applied and how
    * In particular, the committer chooses the positions where new members
are added
    * A direct path that KEMs new entropy to the group (basically an update
from the Committer)
* The committer also generates Welcome messages for any new participants
    * With handshake encryption, the Welcome just needs to have the key for
the Commit
    * The Commit should commit to the state of the tree after the proposals
are executed (just like handshake messages do today)
    * ... so the new joiner doesn't need to see the proposals, just the
Commit

# Observations

* In the framework above, there's no need to synchronize proposals, just
Commits
* If the Commit includes the proposals by value or hash, then we can just
run the transcript over the Commit messages, and the proposals will be
included transitively
* Note that proposals can overwrite one another, e.g., an update and a
remove for the same slot
* If we refactor in the above form, an application could reconstruct what
we have now by always sending a (Proposal, Commit) combo
* In fact, one way to view this is as splitting off the Commit from the
current Handshake messages

# Benefits

* We get the objectives that we set out to achieve:
    * Quiescent groups can just pile up proposals, and Commit before
messaging
    * The server can synthesize Add and Remove proposals as long as clients
have a way to authenticate them (e.g., a designated sender index for the
server)
* There's a certain conceptual simplicity to only having one message that
advances the group state
* With regard to the "ghost account" concerns that DKG raised at the IETF
meeting, this ensures that the proposals to add users are part of the
transcript, thus visible to the group

# Costs

* The longer you go before a Commit, the more expensive the Commit is,
since the proposals are all destructive, in the sense that they blank out
parts of the tree
* The logic for a new joiner might get more complicated, since they're not
actually added until the Commit.  In particular, you can't send an Add
proposal and have the new member immediately able to transmit, you have to
do a Commit as well.
* At least in the form above, we lose the property that Adds are constant
time, since you would always do an asymmetric ratchet operation.  If this
were a problem, you could special-case it (if the Commit only has Adds...)
* Retry logic might get more complicated; need to wait for a Commit before
I know whether my change made it in
* The protocol gets more verbose since you need the glue to refer to the
proposals from the Commit

-----

Thanks for reading all the way to the bottom!

Personally, I'm pretty split on this.  On the one hand, I think this can be
done pretty elegantly.  On the other hand, it does feel more complex, and
I'm worried we're spending a lot of complexity budget on some fairly niche
use cases.  On the third hand, I do think we need server-initiated
Add/Remove, and all the approaches that come to mind end up looking kind of
like this

Happy to have questions / comments here, or if there’s enough interest, it
might be good to have a quick phone call.

—Richard