Re: [MLS] Proposals for handling concurrent messages

Jeff Burdges <> Tue, 26 March 2019 14:40 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 29BB51202FE for <>; Tue, 26 Mar 2019 07:40:19 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -3.535
X-Spam-Status: No, score=-3.535 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, SPF_SOFTFAIL=0.665] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id btmRQOn1kg11 for <>; Tue, 26 Mar 2019 07:40:16 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 5DAFE1202CC for <>; Tue, 26 Mar 2019 07:40:16 -0700 (PDT)
Received: from [] ( [IPv6:2001:4ca0:2001:42:225:90ff:fe6b:d60]) by (Postfix) with ESMTP id BAE501C00C5 for <>; Tue, 26 Mar 2019 15:40:07 +0100 (CET)
From: Jeff Burdges <>
Content-Type: multipart/signed; boundary="Apple-Mail=_7459BBB6-5116-4DEE-A871-C3E64BEA4A09"; protocol="application/pgp-signature"; micalg="pgp-sha512"
Mime-Version: 1.0 (Mac OS X Mail 11.5 \(3445.9.1\))
Date: Tue, 26 Mar 2019 15:40:07 +0100
References: <> <> <>
To: "" <>
In-Reply-To: <>
Message-Id: <>
X-Mailer: Apple Mail (2.3445.9.1)
Archived-At: <>
Subject: Re: [MLS] Proposals for handling concurrent messages
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: Tue, 26 Mar 2019 14:40:19 -0000


Aside form Matrix, there are several groups from the wider Ethereum 2.0 community interested in a messaging scheme that is both distributed and privacy preserving, including both at a cryptographic level and at the metadata level (mix networks).  These include Nym (Panoramix), Status IM, Validity Labs, and the Web 3 Foundation and Parity.

We’re largely out-of-the-loop on MLS but we’re exited about MLS possibly providing a cryptographic layer without too many centralising assumptions.  We’re definitely interested in the “concurrent" updates problem in particular because mix networks can incur considerable latency.

There are also a few projects like Meshenger who should consider using MLS or similar for group messaging over mesh networks.  These have a similar need for concurrent updates, albeit stemming from network topology rather than latency.

Again apologies for my being out-of-the-loop, but I’m not completely sure what concurrency means here.  There is a merge operation that requires any decrypting party processed all the merged trees, yes?  If I understand, there is a similar tree merge operation for vanilla TreeKEM that provides similar assurances to the merge operation that I assume Casual TreeKEM exists to provide:  You simply encrypt the key update messages to anyone who possesses a set of old keys.  This is not actually heavier than encrypting to parties who possess only one key, except that you must identify the set of old keys.

Ignoring the ECC issues [2], there are afaik no commonly discussed post-quantum schemes that support the key combining operation used by Casual TreeKEM, so if Casual TreeKEM is desired then you need an explicit tree merge function too?

All that said, I kinda like that Casual TreeKEM merges seem commutative, but maybe vanilla TreeKEM could support anything useful here by keeping some symmetric key material in a large abelian group?  I’m not sure if I understand the protocol well enough yet to say if that makes sense.


[1]  I spoke with Benjamin some about the header encryption in MLS, which he convinced me looks suitable for some mix network specific concerns.

[2]  There is nothing wrong with requiring Edwards curve arithmetic instead of X25519/X448 of course, but I’m unsure if many constant-time implementations exist besides the Rust curve25519-dalek crate.  I think Ed25519 libraries normally only implement variable-time multiscalar multiplication and constant-time scalar multiplication by the basepoint.  I’d naively assume Weierstrass curves should be avoided due to similar constant-time concerns, but not personally familiar with the implementations.