Re: [MLS] Message Order

Richard Barnes <rlb@ipv.sx> Mon, 16 December 2019 19:32 UTC

Return-Path: <rlb@ipv.sx>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 7C04B1208F2 for <mls@ietfa.amsl.com>; Mon, 16 Dec 2019 11:32:50 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.897
X-Spam-Level:
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: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=ipv-sx.20150623.gappssmtp.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id VGS419SbEeuv for <mls@ietfa.amsl.com>; Mon, 16 Dec 2019 11:32:48 -0800 (PST)
Received: from mail-qv1-xf2e.google.com (mail-qv1-xf2e.google.com [IPv6:2607:f8b0:4864:20::f2e]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9D0B71208EB for <mls@ietf.org>; Mon, 16 Dec 2019 11:32:48 -0800 (PST)
Received: by mail-qv1-xf2e.google.com with SMTP id dc14so1554457qvb.9 for <mls@ietf.org>; Mon, 16 Dec 2019 11:32:48 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ipv-sx.20150623.gappssmtp.com; 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; d=1e100.net; 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: <13a195e741e3478b86992d610e1d6fa1@student.ethz.ch>
In-Reply-To: <13a195e741e3478b86992d610e1d6fa1@student.ethz.ch>
From: Richard Barnes <rlb@ipv.sx>
Date: Mon, 16 Dec 2019 14:32:19 -0500
Message-ID: <CAL02cgTahqHie5CnyapuDB8b4DsJTdeXmG7qXMFnyzzxNfV+uw@mail.gmail.com>
To: Andrikopoulos Konstantinos <kandriko@student.ethz.ch>
Cc: "mls@ietf.org" <mls@ietf.org>
Content-Type: multipart/alternative; boundary="000000000000be39620599d74664"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/xFwLldnGpe-4vf6Yad3uswD0gGk>
Subject: Re: [MLS] Message Order
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <mls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/mls>, <mailto:mls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/mls/>
List-Post: <mailto:mls@ietf.org>
List-Help: <mailto:mls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/mls>, <mailto:mls-request@ietf.org?subject=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
brief:

* 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!
--Richard

[1]
https://github.com/mlswg/mls-protocol/blob/master/draft-ietf-mls-protocol.md#sequencing-of-state-changes-sequencing
[2] ... because epochs are identified with a counter, cf.
https://github.com/mlswg/mls-protocol/pull/245
[3] https://matrix.org

On Mon, Dec 16, 2019 at 1:46 PM Andrikopoulos Konstantinos <
kandriko@student.ethz.ch>; 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
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls
>