Can the Delivery Service actually filter Commit messages?

[TWal]

The document says (5.2.1)

The Delivery Service can rely on the epoch and content_type fields of an MLSMessage for providing an order only to handshake messages, and possibly even filter or reject redundant Commit messages proactively to prevent them from being broadcast

I think this may be a problem if a malformed Commit for epoch n is sent by one of the group members, and this Commit is selected by the Delivery Service:

• group members will reject this Commit and stay at epoch n
• the Delivery Service will think the group has moved to epoch n+1 and reject further Commits that may be sent by other group members (that are still in epoch n)

[TWal]

(issue opened following discussions with @msprotz and @MartinSarkany)

[kkohbrok]

Yes, this is an issue that we won't be able to fix without something like a ZKP. Even with a PublicMessage, the sender of the commit could encrypt garbage to subsets of its copath instead of the correct path secrets. There's already some work on this which you can find here: https://hal.science/hal-03558760/document

If I read it correctly, it shows it's possible, even though the performance might not be what most deployments will be able to stomach.

[rohanmahy]

I think this may be a problem if a malformed Commit for epoch n is sent by one of the group members, and this Commit is selected by the Delivery Service:

* group members will reject this Commit and stay at epoch `n`

* the Delivery Service will think the group has moved to epoch `n+1` and reject further Commits that may be sent by other group members (that are still in epoch `n`)

There are three cases when this could happen:
a) the sending member has a bug that causes it to accidentally send an invalid Commit (or detached proposal)
b) a receiving member has a bug that causes it to wrongly treat as invalid a valid Commit or referenced proposal
c) the sending member maliciously sends an invalid Commit or Proposal that looks fine to the hub but invalid to the clients in order to desychronize the group from its hub

What remedies do we have?

• tell the hub that a received Commit was invalid and ask it to rollback to the previous epoch. Unfortunately without more safeguards (like more evidence or a quorum), this would allow a member who was properly removed from the group to reverse their removal.
• a member receiving an "invalid-to-it" Commit could request the GroupInfo from the hub, rejoin via External Commit, then Commit to Remove the sender of the "invalid" Commit, and restore any changes.

Note that cases a) and b) can occur even if the hub has no decision making in the group other than ordering.

[TWal]

Thanks for the clarifications, when opening this issue I was thinking of the case a). I don't think we can do much about case b), and for case c) we would need some flavor of ZKP as mentioned by Konrad.

To help with case a), I think the architecture document should not say that the DS can filter commits based on epoch numbers, the DS should only be in charge of transmitting all commits in a consistent order to group members. This doesn't change much for case b) and c), however for case a) it prevents the group to be denied of service by the DS (because every group member reject the first commit and that further commits (of the same epoch) would be filtered by the DS).

[rohanmahy]

Thanks for the clarifications, when opening this issue I was thinking of the case a). I don't think we can do much about case b), and for case c) we would need some flavor of ZKP as mentioned by Konrad.

To help with case a), I think the architecture document should not say that the DS can filter commits based on epoch numbers, the DS should only be in charge of transmitting all commits in a consistent order to group members. This doesn't change much for case b) and c), however for case a) it prevents the group to be denied of service by the DS (because every group member reject the first commit and that further commits (of the same epoch) would be filtered by the DS).

Well, we still have a problem with a) whether the DS is involved or not. Say Alice, Bob, and Cathy are in a group. Their DS just forwards Commits to the group in the order received. Alice sends a Commit that she thinks is valid. Bob receives it but thinks it is invalid. Cathy is offline.

From Bob's perspective if Alice had a bug, the best thing Bob could do would be to take some action to heal the group with Alice and any changes she tried to make in her broken Commit. If Alice was malicious the best thing Bob could do would be to remove Alice from the uncommitted version of the group. Meanwhile, if Alice had a bug, she is oblivious that Bob didn't like her Commit until she sees enough MLS messages from Bob in the "wrong" epoch(s) to realize they have diverged. If they have, Alice cannot distinguish if Bob is on the "wrong" epoch because one of them have a bug, or because Bob is malicious/compromised.

Is this better or worse than if the DS was actively involved?

• If a DS is actively involved, it can prevent two honest clients from doing many invalid things that can't easily be detected until much later.
• If a member sends a commit which causes a group to fork, there is no way to distinguish if this was a bug or a malicious client. A client could try to heal the group, but only if the GroupInfo is valid. A forked client also can't tell if an apparently invalid GroupInfo was due to malicious intent. The only other "sldegehammer") remedy would be to create a new MLS group.
• If the DS wanted to deny service, it would be far easier to drop or reorder MLS messages, which it can also do if it is merely responsible for ordering.

[TWal]

I agree that my proposed change do not solve every problem we might encounter in the case of buggy implementations, and that forks might happen "naturally" whatever the DS do.
However, I claim the following: in every situation with buggy implementations (or malicious members), using a DS-without-epoch-filtering results in a situation at least better than when using a DS-with-epoch-filtering, and in some case strictly better.
In the example you give, with DS-with-epoch-filtering, Alice lives in the group "chosen" by the DS, the other group members cannot commit and are therefore "denied of service" by the DS. They all (except Alice) have no choice but re-join the group using external commits.
However, with DS-without-epoch-filtering, every group member reject the commit of Alice, one of them (say Bob) will send another Commit for the same epoch that other group members will accept, hence only Alice lives in a fork and has to rejoin the group using external Commit.

That being said, I do not have strong opinion on this issue, although I do prefer DS-without-epoch-filtering, I might be missing things in the bigger picture (e.g. what happens in MIMI, DS-with-epoch-filtering might help the DS to know what is the current group state?). What do others think? (@bifurcation @kkohbrok @raphaelrobert)

[kkohbrok]

I agree that refraining from filtering based on epoch on the DS side solves some of the problems one might run into when using MLS. However, I do think we should include the "can filter" language. After all it only informs the reader of the possibility to filter and doesn't recommend or even require it. In some applications, where clients within a group trust one-another not to break groups, epoch-based filtering (in case of two clients committing at the same time) is the way to go and forwarding all commits might be prohibitive e.g. because bandwidth is expensive.

[bifurcation]

I agree that:

• Filtering is very natural in many DS designs, and likely to be very common
• Filtering requires clients and the DS to have the same idea of the current epoch
• Invalid commits can cause clients and the DS to have a different idea
• It is basically impossible for the DS to tell with absolute certainty when it is safe to update its state, given the diversity of failure modes
• Nonetheless, some simple things like requiring quorum acceptance can mitigate the problem

(Note that on the last point, you don't even have to rollback. You could have the DS wait until it hears from a quorum before updating its state.)

It seems like it would be appropriate to discuss the risks of filtering in this doc, in basically the terms above.

[seanturner]

Can I get a volunteer to draft up a PR? See email.