Decentralised MLS

1. Goals
2. Group membership
3. Identifying epochs
4. Terminology
5. KeyPackage generation number
6. Resolving forks
7. Information that needs to be kept
8. Problems
9. Todo

MLS requires that commits are made by only one participant at a time. In the MLS architecture, this is enforced by the Delivery Service. However, Matrix does not have a centralised delivery service, and so it does not have a way to ensure that multiple users do not make simultaneous (and conflicting) commits. Thus in order for MLS to be usable in Matrix, we must be able to resolve these conflicts.

In our model, each device has its own view of the state of the MLS group. A commit made by one device may not necessarily be seen by other devices within any given timeframe. However, we assume that causal relationships are preserved: if Alice receives an commit from Bob and then sends her own commit, then if Carol receives Alice's commit (and was also in the MLS group when Bob sent his commit), then she will also have received device Bob's commit. (For simplicity, in this document, we assume that each user has only one device, so when we say "Alice sends …", or "Alice receives …", we do not have to worry about specifying which device is being referred to.)

Since we do not assume there is a timeframe within which a commit will be delivered to all participants, all participants will have to keep some old group state in order to be able to decrypt messages from other users who may be using the old state.

1 Goals

The goals of the method presented here are to:

allow multiple users to create new MLS epochs concurrently,
allow users to resolve forks in the MLS epochs so that the end result is consistent between users,
avoid needing to track too much information,
avoid losing new keys from users,
avoid too many changes to MLS,
remain as secure (as possible) as standard MLS.

2 Group membership

We will assume that the application has a way to allow clients to determine the membership of the group in the face of concurrent changes to the group membership. For example, in Matrix, there is a state resolution algorithm. Clients will use this information and make changes (Add and Remove) to the MLS tree to match the membership given by the application.

3 Identifying epochs

In MLS, the epoch is identified by a counter. However, in the decentralised setting, since multiple users can create a new epoch from the same epoch, there will be multiple epochs with the same epoch number. We can identify an epoch by both the number and the user who created it. For example, if Alice starts a group, then the initial epoch is (1, Alice). If both Bob and Carol make a commit based on Alice's commit, then we would have the epochs (2, Bob) and (2, Carol). Thus, we need to ensure that no user will create two epochs with the same counter, which can be done by ensuring that the numbers of the epochs created by a user will be strictly increasing.

MLS messages identify the epoch that they refer to. The epoch creator can be identified within the application message, so that no changes to the MLS message format are needed.

4 Terminology

When two or more users try to make a commit to a given epoch at the same time, we say that they fork the epoch. The forks result in a directed acyclic graph of epochs. An extremity, from the point of view of a user, is an epoch that does not have any children that the user knows about. Each user has their own set of extremities, which they update when they create or receive Commit messages.

5 KeyPackage generation number

To ensure that epochs maintain the most recent KeyPackage for each user, a new extension is added to each KeyPackage indicating the generation number. All InitKey are generation 0, and each time a user updates their KeyPackage, they increment the generation number.

6 Resolving forks

Each user keeps their extremities. When the user wishes to send a Commit, if there is only one extremity, then they will create the new epoch as normal in MLS. Otherwise, they will choose one of the extremities as the "base" epoch, and add any updates from the other extremities. The user will reference the other extremities, so that other users will know which extremities were resolved. The other extremities can be identified within the application message.

When choosing the base epoch, the user will choose the extremity that has the highest epoch number. If multiple extremities are tied for the highest epoch number, than any of them can be chosen. (FIXME: do we want to make it deterministic anyways?)

The user will then compare the MLS group membership in the base epoch with the application's group membership:

for any user who in the MLS group, but not in the application's group, a Remove proposal is added to remove them from the MLS group.
for any user who is in both the MLS group and in the application's group, check if any extremity has a KeyPackage for that user with a higher generation number, and if so, an Update proposal is added with the user's KeyPackage with the highest generation number.
for any user who is not in the MLS group, but is in the application's group, an Add proposal is added. If the user is present in any of the extremities, then the KeyPackage with the highest generation number is used. Otherwise an InitKey is retrieved and used. FIXME: if the user was previously in the group, use their last KeyPackage (that you know about)?

FIXME: do we need any additional rules for setting UpdatePath, over what we already have in MLS?

After sending the Commit, the user sets their set of extremities to the set only containing the new epoch.

When another user receives a Commit, they should

check that all Update proposals increase the generation number,
remove the base epoch any referenced epochs from their set of extremities, and
add resulting epoch to their set of extremities.

7 Information that needs to be kept

all previous private keys
FIXME: …

8 Problems

we may lose entropy. Suppose that Alice and Bob make concurrent Updates, both setting the UpdatePath, and Carol then makes an Update, using Alice's epoch as the base. Then the entropy added by Bob will be discarded. If Carol's random number generator is good, then this may not be much of a problem. Bob will also notice this, and can make a new Update to re-add entropy from his RNG (as long as his Update isn't discarded again).

9 Todo

This method does not (yet) consider ReInit, PreSharedKey, ExternalInit, or GroupContextExtensions proposals.