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

Richard Barnes <> Thu, 22 August 2019 22:18 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 6D2EE120227 for <>; Thu, 22 Aug 2019 15:18:06 -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 rZwXdyukL_Qv for <>; Thu, 22 Aug 2019 15:18:04 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::241]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id BAB4412012C for <>; Thu, 22 Aug 2019 15:18:04 -0700 (PDT)
Received: by with SMTP id a127so5596805oii.2 for <>; Thu, 22 Aug 2019 15:18:04 -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=jyC2uG5J5EEAcyyTu3BVrmqJ/Qqkt6aj2cUppH6rKPk=; b=kPmFYcTs5HRb9uDc6KkQjulADGdnHjS7zpbtOZRFs+dQNft7iSKoKw8atIituOV2ZE FiNTqXLwVaV6cbOKNZU7R5ZOy2+K+ufNUNmIQz5/cAk5C9HjE9h5kFkfuC4ldefU1Koc R3rcRRRZhE1iLgjCbqKhzc0xXliJf0fWtwYnqvZphRUdbCDubglz4wp2I3gd0PjFTQxb fOvXTIHKsCQTw3mR42cx+QLu/K4zgg7Vn9jvSGJVNNNovYUj2RFSRWXRt3petcqXdft8 chzLRqRcrb4CwR12ff3QCKGp6OLOnT1GA+/kcAecMxpXhJW/XnWc4SJW3euEmxPOxe9N MubQ==
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=jyC2uG5J5EEAcyyTu3BVrmqJ/Qqkt6aj2cUppH6rKPk=; b=XDWMIK8fq3jCX5AM1WxWUOY0RiwCHlnrMM+mo5x7QEv176z0WwMo626mKNhlC6raAL urFGWAqknUADyVWm/flAzqJ1dERM8awyijxTWTwPvgIGoBPCMVX8IsNLJ8doa59kEmHT 1Dup3PpttWlMVvSatt6TzEADGHqFmtBsO0TykPQMtFHQe5zhJGA51mQK/HZaRnUKLQ3A uR92sDPHYfCyfp/I8xkATXXsmT2jt2veR9WFtA0ulN6BFY0wxDDBAUWHkitsxLWIhKxb UguWdfwu3ykGEfr3jbkWu1q7xZJYa/++0pT3m3AwdHA+3CBtz/wnp7biDEciuJs6r/4c O9rg==
X-Gm-Message-State: APjAAAUEpd3YAJIYThwUCDc3crq9Ll7r2gMdsb8bI3uyCGj+X/2VoG8n nfqP21Mpe1cntih7eqxPTFi7omx5PCknGZld/pFUsR5e/88=
X-Google-Smtp-Source: APXvYqx8GCDT3UT75Xpm6vyawJI379H3Rmv6ctl5Gt0ojFQ8obnj2dpEwNK0CR08EOrseANbaUVA8jLLr87IS3JExLg=
X-Received: by 2002:aca:53cf:: with SMTP id h198mr942640oib.169.1566512283793; Thu, 22 Aug 2019 15:18:03 -0700 (PDT)
MIME-Version: 1.0
References: <>
In-Reply-To: <>
From: Richard Barnes <>
Date: Thu, 22 Aug 2019 18:17:46 -0400
Message-ID: <>
To: Messaging Layer Security WG <>
Content-Type: multipart/alternative; boundary="0000000000003669120590bc10b6"
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: Thu, 22 Aug 2019 22:18:06 -0000

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