Re: [MLS] MLS in decentralised environments

"Katriel Cohn-Gordon" <> Tue, 03 April 2018 10:41 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 0064A12DA07 for <>; Tue, 3 Apr 2018 03:41:56 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.7
X-Spam-Status: No, score=-2.7 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key) header.b=WaJBRn95; dkim=pass (2048-bit key) header.b=g7ltO+r/
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id pDDEpyCXpzNc for <>; Tue, 3 Apr 2018 03:41:53 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 087E1127337 for <>; Tue, 3 Apr 2018 03:41:52 -0700 (PDT)
Received: from compute6.internal (compute6.nyi.internal []) by mailout.nyi.internal (Postfix) with ESMTP id 1A47A20AF3 for <>; Tue, 3 Apr 2018 06:41:52 -0400 (EDT)
Received: from web5 ([]) by compute6.internal (MEProxy); Tue, 03 Apr 2018 06:41:52 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; h=content-transfer-encoding:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-sender :x-me-sender:x-sasl-enc; s=mesmtp; bh=Tn/jt2X1MjVd3BSkmVktE1iYzK B4d5t9SoX6nUhf0oM=; b=WaJBRn958Xrbqm1EgNy6WC4TfwFUVoytsEuPe32yRf IOpeOgL+93OP5+EDsYN09WBlnpvH+yXMb0oZAGFRH6G2kDDKkezh8pr4611QyPkU j+VnRFy8UzqiLeK5h7g1Sl3f0Rgkiw6pWsHcyG9uJXynmX4iuCNcfQs+Molp5npc w=
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=; h=content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-sender:x-me-sender:x-sasl-enc; s=fm2; bh=Tn/jt2 X1MjVd3BSkmVktE1iYzKB4d5t9SoX6nUhf0oM=; b=g7ltO+r/uJhwu0/vj/tkTl s7nE/BdqTtmNUjZtr2WUoHdr3JTfVh4K150YBsYisEnFDckZb2r830KL+uJZrivJ f4r4Nsjd1E6l8HQCKqR39W41km2diLOSQmflsYGJDHJbnqS8F8sQ11++MF2VnuV4 T7LBIZJCoiv9t6IRQHYAZcr9xWWgL35M8E0r6d86BYwZBuDnCNLpXhQMUWky4wN2 N6Gqav0J4mX/gEoM8uUFhEkyNnJV1QfsyWaC8cQPCU90iSIpZXVZq+cZViHZF5UC MACEYUIRq0tiOIb5mhcVPB5aRFUGK9pPXgrLJGVyYuY0gHU2LONgipLHEQDj+XOA ==
X-ME-Sender: <xms:cFrDWl3KksFXVDqcsHoYUYfMmC1l5DVM4DBux9l39-kFNJFnvQgrZw>
Received: by mailuser.nyi.internal (Postfix, from userid 99) id E52159E0AF; Tue, 3 Apr 2018 06:41:51 -0400 (EDT)
Message-Id: <>
From: "Katriel Cohn-Gordon" <>
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Type: multipart/alternative; boundary="_----------=_1522752111783620"
X-Mailer: Webmail Interface - ajax-bb419338
In-Reply-To: <>
References: <>
Date: Tue, 03 Apr 2018 11:41:51 +0100
Archived-At: <>
Subject: Re: [MLS] MLS in decentralised environments
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 03 Apr 2018 10:41:56 -0000

Hi Matthew,

Thanks for thinking about this. I agree that it's a problem I think
exists even in the centralised world, since it's much nicer to build a
system that doesn't have to provide strict sequencing guarantees.
# The problem

I'll sketch out the underlying problem first, even though I think you
spotted it pretty well, just to make sure we're on the same page. The
problem is from the ratcheting tree construction: two updates which
both want to change a particular intermediate node cannot both be
applied at the same time. Let me try out some ASCII art: consider a
simple tree like
├── x
│   ├── a
│   └── b
└── y
    ├── c
    └── d

and suppose c wants to update to c', giving the following tree and
publishing g^i(y') where y'=g^c'd
├── x
│   ├── a
│   └── b
└── y'
    ├── c'
    └── d

while d also wants to update to d', giving the following tree and
publishing g^i(y'') where y''=g^cd'
├── x
│   ├── a
│   └── b
└── y''
    ├── c
    └── d'

These can't both be applied by A: A can either set their view of the
last node on their copath to be y' or y'', but not both of them.
Moreover, A has no way of "combining" the two updates.
# Not the problem

One thing I should highlight up front is that this does not necessarily
prevent decrypting messages, only applying key updates. Specifically, if
A receives either C's or D's update they can apply it and compute the
resulting root key, then decrypt the message. Of course, if the update
is one that should have bounced, then they might have to "un-apply" it.
Moreover, if A wants to send their own update, they need to pick one of
y' and y'' to base it on. This is something I don't think we've reasoned
about in detail yet.
For other reasons due to malicious group members, I think we're likely
to come up with a system where each participant has various "proposed"
updates sitting around, and then only confirms them after receiving
some other message. This sort of algorithm should also help here,
because I think it will also need the ability to unwind or not apply a
potential update.
# Things we tried that don't yet work

One thing we thought about was using some tricks with Diffie-Hellman to
allow both updates to be processed at the same time. Unfortunately we
couldn't actually come up with a system that works  (using a KDF to
turn group elements back into integers hurts here), but there might
well be one.
Another thing is the observation that in fact it is sometimes
possible to apply two updates at once: specifically, if two updates
change different copath elements with respect to a recipient, then
that recipient can apply both of them. Unfortunately this only helps
some recipients, not all of them, so it doesn't really solve the
whole problem.
Another thing is having the server do some clever re-ordering. The
challenge  is that in the end, by construction the correct value of the
intermediate node should only be computable by its children, so there's
only so much the server can do.
For the same reason, I'm not sure the server can unilaterally rebalance
the tree; I think it would need some help from one of the participants.
I'd have to think more carefully about the precise keys which it would
need to do so, though. In particular, if you are more worried about re-
ordering join events than re-ordering key updates, there might be some
specialised tricks that work.
# Question about the Matrix context

In the Matrix setup, do nodes actually know when there is consensus on a
particular set of messages? That is, is there some point at which they
can conclude "ok, I know that the following messages are actually the
right ones, and haven't been pre-empted or undone by successors"? (If so
then I think the "multiple proposed updates" ideas will help here too.)

does that make sense? :)