Subject: [MLS] solution to getting in a Commit fairly in a busy group

From: Rohan Mahy <[email-masked]>
Date: Mon, 4 Oct 2021 05:28:02 -0700

Hello,

The protocol document describes a situation in large groups with frequent
adds and joins where a client (especially over a high latency connection)
may be trying to issue a Commit, but other clients keep getting their
Commits in first. I think this could potentially yield unpredictable
behavior.

If clients can request a commit sequence number from the Delivery Service,
all other clients with a higher commit sequence number could wait for the
commits with a lower number to complete before sending their commit. The
commit sequence number could be supplemented with a lifetime (ex: 30
seconds) after which a client loses its place in line.

This seems like an ideal extension to MLS, but unless there is a way to
make extensions mandatory within a group, I don't see how we could add this
functionality later.

Many thanks,
-rohan

*Rohan Mahy  *l  Vice President Engineering, Architecture

Chat: @rohan_wire on Wire

Wire <https://wire.com/en/download/> - Secure team messaging.

*Zeta Project Germany GmbH  *l  Rosenthaler Straße 40,
<https://maps.google.com/?q=Rosenthaler+Stra%C3%9Fe+40,%C2%A0+10178+Berlin,%C2%A0+Germany&entry=gmail&source=g>10178
Berlin,
<https://maps.google.com/?q=Rosenthaler+Stra%C3%9Fe+40,%C2%A0+10178+Berlin,%C2%A0+Germany&entry=gmail&source=g>
Germany
<https://maps.google.com/?q=Rosenthaler+Stra%C3%9Fe+40,%C2%A0+10178+Berlin,%C2%A0+Germany&entry=gmail&source=g>

Geschäftsführer/Managing Director: Morten J. Broegger

HRB 149847 beim Handelsregister Charlottenburg, Berlin

VAT-ID DE288748675

---

From: Dave Cridland <[email-masked]>
Date: Mon, 4 Oct 2021 14:21:20 +0100

> Commits in first. I think this could potentially yield unpredictable

Out of curiosity, could a malicious (or at least annoyingly contrary)
client issue spurious commits to deliberately cause other clients' commits
to fail, forcing them to (for example) continue using existing keying
material?

Dave.

---

From: Richard Barnes <[email-masked]>
Date: Mon, 4 Oct 2021 09:50:03 -0400

To Dave's question: No, that's not possible, at least not as you describe
it.  Any Commit causes the key schedule to move forward, so if a malicious
client uses their Commits to block others' commits, they would still be
ratcheting the key schedule forward.  That's not to say that they don't
have other objectives that would be accomplished that way, e.g., preventing
themselves being evicted by another participant.

On the more general question: I don't think this is really a problem for
the MLS protocol to solve, but rather a question of DS design / MLS
orchestration.  As long as you have a centralized DS, it's pretty
straightforward to have the DS enforce some notion of fairness.  For
example, in the Webex implementation, all Commits are generated by one
"leader" (with other participants generating only requests to join or
leave), which makes them non-rivalrous except for leader transitions.  You
could also have the DS implement a locking scheme of the type you describe,
but there's not really any need to tie that into the crypto protocol.

If you were going to do something integrated with MLS, ISTM you would
basically want to tunnel some Byzantine fault-tolerant consensus protocol
in Proposals (Paxos, Raft, etc.), using some Proposals designed for this
purpose.  But this would be a pretty complex extension.

--RLB

On Mon, Oct 4, 2021 at 9:21 AM Dave Cridland <[email-masked]> wrote:

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

---

From: Rohan Mahy <[email-masked]>
Date: Mon, 4 Oct 2021 08:58:34 -0700

Hi Richard,

> but there's not really any need to tie that into the crypto protocol.

The relatively light-weight solution of DS orchestration I proposed, still
required a place to put the "commit sequence number" inside MLS so all the
clients could see it. To be clear, I think this would be an MLS extension
and not part of the core protocol.

Thanks,
-rohan

VAT-ID DE288748675

On Mon, Oct 4, 2021 at 6:50 AM Richard Barnes <[email-masked]> wrote:

>>> The protocol document describes a situation in large groups with
>>> frequent adds and joins where a client (especially over a high latency
>>> connection) may be trying to issue a Commit, but other clients keep getting
>>> their Commits in first. I think this could potentially yield unpredictable
>>> behavior.
>>>
>>

---

From: Richard Barnes <[email-masked]>
Date: Mon, 4 Oct 2021 13:22:17 -0400

> and not part of the core protocol.

What I'm saying is just that you could put the sequence number in whatever
framing you're using to send around MLS messages, and not touch the MLS at
all.

Just to be clear about one aspect of this proposed solution: Consider the
case where a client receives CommitB with a higher sequence number, then
CommitA shows up.  You might think that the client could apply CommitA,
then CommitB.  That is not necessarily the case -- Commits are ordered
because they depend on the state established by the previous commit.  If
both CommitB and CommitA were generated from the same epoch, they are in
conflict; the client would have to throw away CommitB instead of applying
it.

In general, there are kind of two broad classes of solution here that
people tend to come to:
1. Locking: Designating one member is the only authorized committer for
some period of time
2. Tie-breakers: Queuing up Commits over some time period, and applying the
one that wins according to some tie-breaking function

Your proposal is in the "tie-breaker" bucket, with "lowest sequence number"
as the tie-breaker.  (You could also just do something like "leftmost in
the tree" or "smallest u64 derived from H(epoch || leaf index)")  Webex is
in the "locking" bucket, with the leader holding the lock.  The two
approaches have kind of complementary sets of trade-offs.

--RLB

---

From: Rohan Mahy <[email-masked]>
Date: Wed, 6 Oct 2021 08:19:50 -0700

> framing you're using to send around MLS messages, and not touch the MLS at
Yes, but then the sequence number is not synchronized to the state of the
MLS group, which would cause timing/ordering problems for my proposal (and
would also not be e2e authenticated).

> conflict; the client would have to throw away CommitB instead of applying
agreed

> 1. Locking: Designating one member is the only authorized committer for
Yes. While you could think of this as a "soft-lock". It is specifically a
precondition. Like HTTP Etags/If-Unmodified-Since/412 Precondition Failed
behavior. Commit B has a precondition of no outstanding reserved Commits.

Out of band you can request a commit sequence number from the delivery
service. The delivery service would reply with the requested sequence
number, its expiration time (ex: 30 seconds), and (if not yet expired) the
expiration time of the previous sequence number issued. The delivery
service would presumably have a policy to limit excessive simultaneous
commit sequence number requests (by rate and number).

Inside the group, an MLS client would have to wait for either a Commit
using the previous sequence number, or the expiration time of that previous
sequence number, whichever comes first, before issuing a Commit (which
would include the newly requested sequence number).

If we were worried about cheating, the sequence number could be a token for
the requesting client, signed by the delivery service.

> one that wins according to some tie-breaking function
Not what I was proposing.

Again, this is something we can add later as an extension, now that we have
required extensions.

Thanks,
-rohan

VAT-ID DE288748675

On Mon, Oct 4, 2021 at 10:22 AM Richard Barnes <[email-masked]> wrote:

>> The relatively light-weight solution of DS orchestration I proposed,
>> still required a place to put the "commit sequence number" inside MLS so
>> all the clients could see it. To be clear, I think this would be an MLS
>> extension and not part of the core protocol.
>>
>
> 2. Tie-breakers: Queuing up Commits over some time period, and applying
> the one that wins according to some tie-breaking function
>
> Your proposal is in the "tie-breaker" bucket, with "lowest sequence
> number" as the tie-breaker.  (You could also just do something like
> "leftmost in the tree" or "smallest u64 derived from H(epoch || leaf
> index)")  Webex is in the "locking" bucket, with the leader holding the
> lock.  The two approaches have kind of complementary sets of trade-offs.
>
> --RLB
>
>
>> Thanks,
>> -rohan
>>
>>> To Dave's question: No, that's not possible, at least not as you
>>> describe it.  Any Commit causes the key schedule to move forward, so if a
>>> malicious client uses their Commits to block others' commits, they would
>>> still be ratcheting the key schedule forward.  That's not to say that they
>>> don't have other objectives that would be accomplished that way, e.g.,
>>> preventing themselves being evicted by another participant.
>>>