Re: [MLS] Message Order

Richard Barnes <> Mon, 16 December 2019 19:32 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 7C04B1208F2 for <>; Mon, 16 Dec 2019 11:32:50 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.897
X-Spam-Status: No, score=-1.897 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_NONE=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 VGS419SbEeuv for <>; Mon, 16 Dec 2019 11:32:48 -0800 (PST)
Received: from ( [IPv6:2607:f8b0:4864:20::f2e]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 9D0B71208EB for <>; Mon, 16 Dec 2019 11:32:48 -0800 (PST)
Received: by with SMTP id dc14so1554457qvb.9 for <>; Mon, 16 Dec 2019 11:32:48 -0800 (PST)
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 :cc; bh=jGmFK80nlKZPNNl6/Pb4AdUtxCDIjJYDTn7bGoWbaVI=; b=PUuT224LfiTOV4A11Ro4cNm6fEd95T5++lNXwk01UXXjrknNWRX4XzkKGmggcEhTWG mHcisOOQ2GJbDBj9Lxl1eupv3lla90P4GqAmq154+PAdLX035mgv0nDrI/3CxAhpP7DK 082JgC9a8N0jErIYKJwbNU5me7TYA2nWdMUH9glI9fQxs2VGFtdX2f9qdFP3LZD5W7ay ZiZ2Xpo67DDV4rEwZRvqbP5MF6Uj7QxGTvUH4IS4Vi79mKu5w2kTLjc27CkfxrdSU+Qj tQITrfaYXMhozE/vjek6hk+1eBU69BDZHQ5mZXF51D9nPQLynO2TzMz7FS7nU5h5ZOhv 1UiQ==
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:cc; bh=jGmFK80nlKZPNNl6/Pb4AdUtxCDIjJYDTn7bGoWbaVI=; b=HfNdIt83Ox7xLb1/RiYgcIDrcI2FUmlj23Zvb/y+A39gmdxqi1PPh8ZJKr5IMPRGe4 z34PkBCd5bGjBqMc4Vz2+XvLMTnvtN7BKudO7ZiqopcEFgf9D6IMyg7V+E11H7Cdajk7 Zg3wFoXbtlBxvxsyHmuDFRS9/FnqVt8LnIph0zS6ZaciziEkw8lBjFRbu1fETUhQ2BH3 n2o7DoVbSdonWCZOG3Qa4EMsR12/iLRNhixXkhArSM7QOF4GWbke9quxSZUD8Vz08xvB rOsuKmidkRodpKowxm4RtRABJZ/gEKjYzJPQN1YcV7+jx2Rx62fLbHt+l3XebPoDXkif ItMQ==
X-Gm-Message-State: APjAAAVgzqJ8htu9wr9SCxaDVt5I8B/HZKVdkTpa9otr/pLf7HRY9DHG /tTlGO1UOPyZISBizXB4AvHrWeTsTAlyagBMks8sG7M5RSI=
X-Google-Smtp-Source: APXvYqyEdofDxs0RQf2JLMu3APzfB1oCEcRbc3uj7YiDNVyKH6aCJ5dypaEJug+XPOKru8Q0/vgn3Yyr6groNwXSHzY=
X-Received: by 2002:a0c:f2ce:: with SMTP id c14mr973153qvm.65.1576524767437; Mon, 16 Dec 2019 11:32:47 -0800 (PST)
MIME-Version: 1.0
References: <>
In-Reply-To: <>
From: Richard Barnes <>
Date: Mon, 16 Dec 2019 14:32:19 -0500
Message-ID: <>
To: Andrikopoulos Konstantinos <>
Cc: "" <>
Content-Type: multipart/alternative; boundary="000000000000be39620599d74664"
Archived-At: <>
Subject: Re: [MLS] Message Order
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: Mon, 16 Dec 2019 19:32:50 -0000

Hi Konstantinos,

Thanks for reaching out.  I think the current thinking is described in the
"Sequencing of State Changes" section of the current document [1].  (It
probably needs a rewrite, thought, to use more current terminology.)  In

* The protocol allows each state/epoch to have a single successor [2],
* So the members of the group need to agree on which Commit message causes
this epoch change.
* In some deployment cases, a straightforward way to achieve such agreement
is to ensure that all members receive Commits in the same order, so they
can just take the first one
* You could also envision applying other techniques to agree on which
Commit is applied, e.g., running a consensus protocol
* These requirements apply only to Commits; Proposals and application
messages are uncontentious, and can be arbitrarily reordered in any case

The requirement for strict ordering of states is something the group has
accepted for a while, since in the primary use case, with a centralized
Delivery Service, it seems reasonably achievable.  However, it is
problematic for more decentralized cases, Matrix [3] being the
most-discussed example.  To make those scenarios work better, you would
need (a) non-linear epoch IDs so that you could tolerate forks in the state
history, and (b) a "merge" algorithm so that you could coalesce two forks.
Both of those are areas where some additional thinking could be helpful.

Hope that helps!

[2] ... because epochs are identified with a counter, cf.

On Mon, Dec 16, 2019 at 1:46 PM Andrikopoulos Konstantinos <> wrote:

> Hello,
> I am a computer science master's student, focusing on cryptography and
> security. As a part of a small research project, supervised by Kenneth
> Paterson, I am looking into the MLS protocol. In particular, we have been
> paying attention the message reordering problems that are mentioned in the
> current draft of the protocol.
> The purpose I am writing this email is that, before we continue further
> with the project, we would like to see if you have already decided on the
> direction that you would like the solution to follow. Would you be able to
> point us to any texts that you may have compiled or past discussions on the
> subject?
> Thank you,
> Konstantinos
> _______________________________________________
> MLS mailing list