MLS meets Matrix

Hubert Chathi <>

In this talk

  • What is MLS? Why is it better? How does it work?
  • How can MLS be done over Matrix? What challenges are there?
  • How would MLS interact with other things? (SSSS, cross-signing, etc)

What is MLS?

  • Messaging Layer Security
  • Upcoming IETF standard for end-to-end encryption in messaging systems
  • Designed for group messaging, rather than 1-1 messaging
    • faster with large groups
    • knows about group membership
  • Many different contributors, has been analyzed by several people, subject of academic research
  • Multiple implementations (in progress)

High-level overview of MLS

  • For more detailed explanation, see
  • 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

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:

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

or possibly type: with an algorithm indicating it's a welcome message

  • MLS messages sent as room messages


  "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> ]

Open questions

  • MLS assumes you see all commit messages, and can decrypt them in order
    • Matrix gives you the most recent messages, and allows you to backfill
    • How do you retrieve old commits to decrypt the latest ones?
  • Some parts of MLS have not been investigated yet (PSK, ReInit, external commits...)

What about other parts E2EE?

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


  • 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?


  • Shouldn't be affected directly by MLS


  • MLS (modified) in Matrix works!
  • needs to be reviewed for security
  • needs to be updated to the latest draft (and eventually, the standard)
  • needs more work on a lot of details, but most of the hard parts are done
  • needs good MLS implementation(s) to use