Re: [MLS] Proposal: Proposals (was: Laziness)

[Richard Barnes <[e-mail]>]

BTW, big thanks to Raphael for setting us down this path, and to Katriel
for talking this through with me earlier this week (and for coming up with
the Welcome-by-Committer part).

On Thu, Aug 22, 2019 at 6:16 PM Richard Barnes <[e-mail]> wrote:

> 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
>