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

Richard Barnes <> Wed, 18 September 2019 22:16 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id CE49D1200C7 for <>; Wed, 18 Sep 2019 15:16:25 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.896
X-Spam-Status: No, score=-1.896 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_NONE=0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id HeW-xMuSxjUw for <>; Wed, 18 Sep 2019 15:16:22 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::341]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id B1FF012002F for <>; Wed, 18 Sep 2019 15:16:22 -0700 (PDT)
Received: by with SMTP id 21so1270087otj.11 for <>; Wed, 18 Sep 2019 15:16:22 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=NGh4ErRkXdM85Q5080vwzWYpO5wJxiGVBrc0zP0zV98=; b=UJ6+uHWimrTgiVZFd6GF0g9wVXO0nLJMmLfjW0Eo4D8UhOYkFBzWKmvofOr0yd7MQm 0IY+0XFnE/kL5Z5dylZZoLS6fc6ADy+TQvxBemJGQz3KG6K6hF+2yyCLPkW4D8ucb6LL npsFxinQp9peDT/n9svIIetT8nruwxf0l5MaWeoMHx8fPBfFgwcjvxgYTcX6wLKNZqOG m2ebTLET5iZOd+MbQ6tbEOVcKW7YalGBGfucJ9tEzwJ5gpP1gu9bC1ufYQ4She64xPw6 FDxZ69eplitgrTi2maHZFxK4HNUbhfObU8LnZtDXZaDiBgk+waRXUz4Y+d/DhQuBPVWT ZZkw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=NGh4ErRkXdM85Q5080vwzWYpO5wJxiGVBrc0zP0zV98=; b=o0548b2JhmBVeO8A6A4jwJk7R9Y3H4fyiSv6PI1fvN1bd/xOA1ahn7+sLVJhSoWuBK tynA9AnUsvk3aBLg/tmmwTktkfHPTm/koIOtIngRqBvHnIrQicYlwE0TWn2k/LjEBPeP XqQ6fEzaAZ/6vgiHqOMLvVhYNEwHNnV4Tz04vVHN0vl9IBMgOIKyMNcnWfFAsu1TnZBi euWcBmYkgB+MiOOTTZH80J4lJrq2quOGRaZdgCU2bAr8JNOiBflbQHSOjhsgnfxKsShT SYZB2XQeNGxGPBBt8tsV4Zh5xrrwIIjhckmXATxD4nwOUfa1EjB30yaYaGfJuM+ngDvy 9vZg==
X-Gm-Message-State: APjAAAWX5FHBIVO1feiPftKjLRXcg0o2ajtv2P14iyIzIkGL9/+1YYPc fU7Tx1rtfZiozmx+nwL/8KodH0yknxEfqbHyXejaUsvzX+Fa6A==
X-Google-Smtp-Source: APXvYqwP59xJGHV+SCITxtrToiVon1TZ+UkVIES7lpUO+j+rh64UwBxOyTjXvRZ1b6Fe3c0VvJsx2CW5V2jnqTxMbyM=
X-Received: by 2002:a9d:6d82:: with SMTP id x2mr1566720otp.42.1568844981503; Wed, 18 Sep 2019 15:16:21 -0700 (PDT)
MIME-Version: 1.0
References: <>
In-Reply-To: <>
From: Richard Barnes <>
Date: Wed, 18 Sep 2019 18:16:08 -0400
Message-ID: <>
To: Messaging Layer Security WG <>
Content-Type: multipart/alternative; boundary="000000000000d4a90e0592db2f44"
Archived-At: <>
Subject: Re: [MLS] Proposal: Proposals (was: Laziness)
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 18 Sep 2019 22:16:26 -0000

I've written up a PR that implements this proposal:

Please take a look; there's plenty in there to disagree about, and several
OPEN ISSUEs.  I would like to have this landed in the next week or so, so
that we can rebase some other PRs on it (e.g., non-destructive add) and
publish a new draft for the interim.


On Thu, Aug 22, 2019 at 6:16 PM Richard Barnes <> 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