Subject: [MLS] Message ordering

From: "Alexey Ermishkin" <[email-masked]>
Date: Wed, 30 May 2018 01:04:24 +0500

I'd like to discuss the practical part of the requirement that MLS puts on
all group participants.
Hope that I haven't missed such discussion already.

All messages (not only state change messages) must have a counter field
which must be unique among all the messages and server must reject messages
that have this field duplicated.
This might be ok for a group of 3. But as MLS targets groups up to 50k
users, I believe  the percent of rejected messages will dramatically
increase and affect user experience.
I know that ART or TreeKem is, in the end, supposed to be bound to double
ratchet's KDF chain which have one sequence of message numbers per "epoch"
but that clearly won't work for large groups where participants will
constantly have to work on some "consensus" during communication.
I believe there's better solution to this problem. Maybe we should consider
making a unique KDF chain (prefix?) for each group member and perform
timestamp-based ordering, I'm not sure.

Regards, 
Alex

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Tue, 29 May 2018 22:53:23 +0200

> that have this field duplicated.

Good catch. I think this may be too strong a requirement. 
With the right design adjustments, we will probably find that per-sender counters are enough.

-Karthik

> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 29 May 2018 13:56:40 -0700

The difficulty is that key management also depends on clear ordering.

-Ekr

---

From: "Alexey Ermishkin" <[email-masked]>
Date: Wed, 30 May 2018 02:16:41 +0500

Key management or, let’s call it group sate change, usually happens less frequently than the messaging itself. It can also be performed as a background task, affecting user experience much less.

There could also be some quotas on key rotation depending on the group size. 

Suppose we have a policy that that every member can rotate his key only once per 24 hours.
In case of evenly distributed group It would allow a group of ~40k people have state update about every 2 seconds which will reduce the waiting time for newcomers and reduce the possible merge conflicts 

From: MLS <[email-masked]> On Behalf Of Eric Rescorla
Sent: Wednesday, May 30, 2018 1:57 AM
To: Karthikeyan Bhargavan <[email-masked]>
Cc: Alexey Ermishkin <[email-masked]>; [email-masked]
Subject: Re: [MLS] Message ordering

-Ekr

-Karthik

> [email-masked] <mailto:[email-masked]> 

_______________________________________________
MLS mailing list
[email-masked] <mailto:[email-masked]> 
https://www.ietf.org/mailman/listinfo/mls

---

From: Martin Thomson <[email-masked]>
Date: Wed, 30 May 2018 11:14:14 +1000

If that is the path you take, it's probably better to have a global key
update rate and to derive individual update rates based on that and the
group size.
On Wed, May 30, 2018 at 7:17 AM Alexey Ermishkin
<[email-masked]>
wrote:

> Key management or, let’s call it group sate change, usually happens less
frequently than the messaging itself. It can also be performed as a
background task, affecting user experience much less.

> In case of evenly distributed group It would allow a group of ~40k people
have state update about every 2 seconds which will reduce the waiting time
for newcomers and reduce the possible merge conflicts

> On Tue, May 29, 2018 at 1:53 PM, Karthikeyan Bhargavan