High-level overview of MLS

• For more detailed explanation, see https://www.youtube.com/watch?v=xOMUG__uEjc
• Group members (devices) have public keys stored in the leaves of a binary tree
• Internal nodes have public keys too, or are "blank"
  • Descendants know the private keys, or are marked as "unmerged"
  • Members can update their key and the keys for the nodes between
    their leaf and the root
• Root node is never "blank"

• Tree gets updated — add/remove members, update keys, etc.
• add InitKey of new members to tree, send Welcome messages to new members
• Send Commit message to room, which can be decrypted by current members (but not members who were removed)
• Changing the tree creates a new "epoch"

• Private key at root (along previous initialization secret and pre-shared key) are used to derive several other secrets
  • encryption keys
  • initialization secret
  • and others...

A big problem with MLS and Matrix

• MLS assumes that we have a linear sequence of epochs
• Matrix doesn't give a linear sequence of events

Decentralised MLS

• Add a layer on top of MLS
• Allow epochs to fork, but keep track of who created them
• When a new epoch is created, pick one to be the "base", make it agree with room membership, and merge in changes from other epochs, using normal MLS operations
• Only needs some extra bookkeeping information
• Outlined at https://gitlab.matrix.org/matrix-org/mls-ts/-/blob/decentralised2/decentralised.org

How to do MLS over Matrix

• MLS defines (binary) encoding for messages/objects 🡒 base64-encode and wrap in JSON object
• MLS identity: combination of user ID and device ID e.g. userId|deviceId
• InitKey (your leaf node when you are first added to the tree) 🡒 one-time keys
  • MLS even proposes using the equivalent to olm fallback keys

• Welcome message 🡒 sent as a to-device event

e.g. type: org.matrix.msc2883.mls.v0.welcome

{
  "welcome": <base64-encoded MLS welcome message>,
  "resolves": [ <array of epochs that the commit resolves> ]
}

or possibly type: m.room.encrypted with an algorithm indicating it's a welcome message

• MLS messages sent as room messages

type: m.room.encrypted

{
  "algorithm": <MLS_ALGORITHM>,
  "ciphertext": <base64-encoded MLS-encrypted message>,
  "epoch_creator": [<userId>, <deviceId>],
  "resolves": [ <array of epochs that the commits resolves -- if this is a commit> ]
}

What about other parts E2EE?

• verification/cross-signing
• key backup/forwarding/re-sharing
• SSSS

Verification/cross-signing

• MLS can use ed25519 keys, so we could just reuse the existing device keys

  {
    "user_id": <userId>,
    "device_id": <deviceId>,
    "algorithms": [ <MLS_ALGORITHM> ],
    "keys": {
      ["ed25519:${this.deviceId}"]: <base64 ed25519 key>
    }
  }
  

  or add another ed25519 key
• verification would not be affected much -- device keys (cross-)signed in same way, verification methods assert the public keys
• Or MLS could use ed448 keys -- should we switch to that for
  cross-signing keys?

Key backup/forwarding/re-sharing

• Need to determine the minimal information to keep about each epoch
• Do we back up our private keys too, or just the shared secrets?
• Need to be able to handle multiple algorithms/versions (e.g. a Megolm backup and an MLS backup)
• How do we determine which is the "better" key?

SSSS

• Shouldn't be affected directly by MLS