Re: [MLS] Unpredictable epochs?

Richard Barnes <> Fri, 03 January 2020 16:55 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id D006D1200DE for <>; Fri, 3 Jan 2020 08:55:42 -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, RCVD_IN_DNSWL_NONE=-0.0001, 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 CS16P7quYKv1 for <>; Fri, 3 Jan 2020 08:55:39 -0800 (PST)
Received: from ( [IPv6:2607:f8b0:4864:20::831]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 6680C120091 for <>; Fri, 3 Jan 2020 08:55:39 -0800 (PST)
Received: by with SMTP id d18so34578632qtj.10 for <>; Fri, 03 Jan 2020 08:55:39 -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=c/4I4qO/Z813fL3KErDp7bYME9KlGvjDeTN43qpqLtc=; b=f4EsCMOcSDQV/I43e5NcfyfTgTz1PWCjkCOBZFihn8aKvFk5xb8aCtgeDzZ362tpam VLQFQKugD5O9JxB6n1wyqTiYfHBZx/zS/A4ShTzChnv0Wp8KIh3sHUOVXcWMd4FHRd/S MtgB98NH5jtrlS4tGecIxbxvfetqPCHol2ai3kjUhrc85hs9Bs7yquGlTF6Svmf1u8Vq R0ZlD9PvzrrTI1WbWofdsQYmYBQeJK3TBBcRBqrADhHs9L6sRkHKti1VcyrOv7LNclb1 2w1y+2L3EnJne53SpSolrAyjeES0ANzwoj+QV1f/tLw9E3cOB1fR/35W/Y0gEj0QmkJ3 i76A==
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=c/4I4qO/Z813fL3KErDp7bYME9KlGvjDeTN43qpqLtc=; b=INkFwwWTRT721PT7SFE/o3S7qupShy5K1T7h6+lkIg0vk3FpQFYQcKfmn71y3XMHr/ rdiuxmNIz9A03EkvwJafK9WnBUMcH0hKltSQtMRmE13bDisTCGkhpKCzAqR+o2KDXVH1 c1BYdm6YJmCTPqKbrazwQve799j7UdleDJdlhZwSTb75hWtRPkbgDzz5xnYEd0PKcsrM Jh3gyhnFIAnP3cY8K56asdFszOgV21kQFTk9SLdvAQ89H0S6YzXeQCyzFOiwBYhlUQ4d bF+nmQIqNqK/XFHgzPQhMtAbxZxPOcASyKav68f2+TNen/DIiPtiKhxFJs0Olc9qMRUn YJMw==
X-Gm-Message-State: APjAAAXuT4mQrcUg0hEcOfMfyy4XRxEZdoqcISFIvmqzSkoYt+IJxzTb bzbm9RoSRfd+ICMRdfERMLOsVj7uXl4brip5RVO9Fg==
X-Google-Smtp-Source: APXvYqwflmWwF7qJau2ftai+DEEOX+xfY40SjqzLRvfLOD1g5ibcsbagNl2frMqeJ0NcDp19Bxn6qw46wZiB7QPRqM8=
X-Received: by 2002:ac8:1e90:: with SMTP id c16mr64804489qtm.265.1578070538489; Fri, 03 Jan 2020 08:55:38 -0800 (PST)
MIME-Version: 1.0
References: <> <> <> <> <> <> <> <> <> <> <> <>
In-Reply-To: <>
From: Richard Barnes <>
Date: Fri, 3 Jan 2020 11:55:21 -0500
Message-ID: <>
To: Raphael Robert <>
Cc: Kelvin Ritland <>, Michael Rosenberg <>, Messaging Layer Security WG <>, Benjamin Beurdouche <>, Jon Callas <>
Content-Type: multipart/alternative; boundary="000000000000e0a98c059b3f2dce"
Archived-At: <>
Subject: Re: [MLS] Unpredictable epochs?
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: Fri, 03 Jan 2020 16:55:43 -0000

Yeah, I'm on the same page here. My objective is to remove the roadblock
without trying to solve the whole problem.  As Kelvin points out, there's a
lot of interesting thinking to be done about how to manage a DAG of state.

In chatting with Raphael just now, he proposed a nice framing -- that the
tiebreaker bits could be used for fork *detection*.   Even in the case
where the DS is trying to maintain order, there's a chance that things go
wrong.  The tiebreaker bits would ensure that people don't try to use the
wrong keys for a message in that case.

Here's a quick PR implementing the "extended epoch" proposal:

On Fri, Jan 3, 2020 at 10:32 AM Raphael Robert <> wrote:

> I agree with Kelvin’s points in general. Allowing forks might be an
> interesting goal, but it raises a wealth of new questions.
> On the other hand I think Richard’s proposal of extending the Epoch ID
> with a commit hash makes sense to detect potential forks.
> I’d like to propose that we adopt that as a first step, but only in the
> context of fork detection for now. This doesn’t preclude us from building
> on top of that in the future, but we also don’t introduce something
> dangerous right now.
> Raphael
> On 3 Jan 2020, at 00:15, Kelvin Ritland <
>> wrote:
> Not-pseudorandom implies some assumptions, e.g., that each sender would
>> only send one Commit on top of each epoch
> This isn't bad imo, it reduces complexity to some extent. I'm somewhat in
> favour of a non-pseudorandom tiebreaker if there's no other arguments
> against it.
> How many bits of sequence number?
> Have we considered using varints? Similar to the CTLS proposal -
> Other forking considerations, I think there's more involved than just
> changing the epoch identifier:
> 1. We'll need merges as well, since forks can lead to inconsistent group
> membership:
> Suppose in epoch 1 a group has A, B, and C
> A removes C in epoch 2A
> B adds D in epoch 2B
> We now have two group states 2A with AB and 2B with ABCD - and it's
> unclear which group to use to send with. We could mandate that any client
> MUST send a "merge" commit on it's view of history before sending any
> message. This commit could just be the list of epochs that are being merged
> (+a usual DirectPath update?), and processing it would mean replaying all
> proposals up to the common ancestor for those epochs on the common ancestor.
> 2. Forward secrecy issues.
> By allowing forks, devices must now keep the previous epoch around to
> derive possible future forks - but this means we'll be re-using
> init_secret_. A possible solution could be to use the nth app secret from
> the ASTree instead of init_secret_ as the start for the new epoch secret.
> This ties nicely with using a non-pseudorandom tiebreaker.
> 3. Ordering implications
> It's unclear what a sensible ordering strategy is for the DS if we allow
> forking. (simply ensuring that each commit is based on the "current" epoch
> isn't well defined since there can be multiple "current" epochs).
> By allowing forks the DS need not enforce ordering at all imo. This means
> that apps need to keep around old epochs, but this is already required per
> (2). A different question is how many we need to keep around - perhaps a
> TTL or the past N epochs after a topological sort would make sense.
> Generally I think getting rid of server ordering is good idea:
> - Helps Matrix and general federation use cases
> - A common consistent mutated state for group operations can cause server
> side DB contention in my experience
> Forks is one way to remove ordering, and if we need to support it anyways
> it's a nice benefit.
> On Thu, Jan 2, 2020 at 12:52 PM Richard Barnes <> wrote:
>> Argh, hit send too soon.  Continuing below...
>> On Thu, Jan 2, 2020 at 3:38 PM Richard Barnes <> wrote:
>>> Hey all,
>>> Resurrecting this thread, as it seems that we never came to resolution
>>> on this question.
>>> I'd like to propose we scope down and solve a narrower problem, namely
>>> the problem of enabling forks in the group's history.  So we're not going
>>> to try to provide any privacy properties, just remove the impediment to
>>> forking.  This seems like a worthwhile thing to me just because it seems
>>> silly to have forking blocked just because of syntactic constraint, in
>>> addition to it likely being necessary for some decentralized use cases
>>> (e.g., Matrix).
>>> To allow forks, we really just need some "tie breaker" bits in the epoch
>>> ID so that if a given epoch has multiple successors, they end up with
>>> different epoch IDs.  And in order to avoid synchronization, each
>>> participant needs to be able to generate those bits independently.  There
>>> are a couple of basic questions about how to construct the tie breaker:
>>> 1. Pseudorandom or not?
>>>   - Not-pseudorandom example: tiebreaker = commitSenderID
>>>   - Pseudorandom example: tiebreaker = H(MLSPlaintext(Commit))
>>>   - Not-pseudorandom implies some assumptions, e.g., that each sender
>>> would only send one Commit on top of each epoch
>>>   - Pseudorandom risks random collisions
>>>   - Possible to do both: tiebreaker = commitSenderID ||
>>> H(MLSPlaintext(Commit))
>>> 2. How many bits of tiebreaker?
>>   - Non-pseudorandom size will be dictated by what we include
>>   - Pseudorandom size will be dictated by tolerable collision probability
>>   - Probability of collision ~ (number of forks per seq no) / 2^{number
>> of bits}
>> 3. How many bits of sequence number?
>> - DS might want to see sequence to help enforce ordering
>> - Probably want this big enough to avoid wrapping.
>> (Note that this is a value that goes in every message, so there's some
>> incentive to keep things small.)
>> Personally, my proposal would be something like:
>> struct {
>>   uint64 sequence_number;
>>   uint64 commit_hash; // H(MLSPlaintext(Commit))
>> } EpochID;
>> That seems to strike a reasonable balance between low collision
>> probability (~2^-64) and a reasonably small identifier.  If 128 bits is
>> good enough for IPv6, it can be good enough for us :)
>> Does that seem workable to folks?
>> --Richard
>>> On Fri, Apr 26, 2019 at 4:18 PM Benjamin Beurdouche <
>>> <>> wrote:
>>>> > On Apr 26, 2019, at 9:26 PM, Jon Callas <> wrote:
>>>> >
>>>> >> On Apr 26, 2019, at 2:22 AM, Michael Rosenberg <>
>>>> wrote:
>>>> >>
>>>> >> So why not remove epoch entirely?
>>>> >
>>>> > An epoch lets you deal with things happening neither too often nor
>>>> not often enough. Presume there is a client that is either malicious or
>>>> just stupid. You want to keep it from forcing a rekey every 100µs. You want
>>>> to force a rekey every so often. Hence epochs. Yeah, picking the right
>>>> epoch size is an exercise left to the reader.
>>>> You can’t use the epoch number for that as it is just global counter
>>>> for group operations, we will have to keep track of the latest group
>>>> operation “timestamp” for each member within the group state to check
>>>> “update frequency” and handle some of the situations you described.
>>>> Btw in the TreeKEM formal spec I use a 64 bit unsigned integer, and I
>>>> feel like having more than 2^32 group operations over the lifetime of a
>>>> group is not unrealistic in certain extreme use cases, especially with
>>>> large groups forcing PCS for application messages by triggering an update
>>>> after each app message...
>>>> We could remove the epoch number if we really want but it is necessary
>>>> to give the Delivery Service some ordering information (unpredictable or
>>>> not is an interesting question) to handle concurrent handshake messages
>>>> which is, I believe, the main current goal of that information.
>>>> Benjamin
>>> _______________________________________________
>> MLS mailing list
> _______________________________________________
> MLS mailing list