Groups, members and epochs
MLS is a standard from the IETF, published as RFC 9420 in July 2023, for agreeing encryption keys in a group whose members may not be online at the same time. Its two organising ideas are groups and epochs.
A group is a set of clients, usually devices, that share a secret. The group’s history is a linear sequence of epochs. In each epoch, the authenticated members agree on an epoch secret known only to them, and derive from it the keys that encrypt messages and authenticate membership. When the membership or keys change, the group moves to a new epoch with a new secret. Someone who was removed in the last change does not get the new one.
The creator starts the first epoch alone, with no messages exchanged. Everything after that happens through four kinds of MLS message.
Key packages and Welcome messages
To be added to a group, a client first needs a KeyPackage: a signed object that describes its capabilities and carries a public key that others can use to add it. Clients publish key packages ahead of time, so they can be added while offline. A key package is meant to be used once and then deleted, because reuse can enable replay attacks.
When a member adds someone, it fetches their key package, updates the group, and sends the newcomer a Welcome message. The Welcome carries what the new member needs to set up the group state for the epoch they join, encrypted to their key package with HPKE, a standard public-key encryption scheme. The new member can read and send new messages, but cannot read anything sent before they were added.
Proposals and Commits
Changes go through two steps. A Proposal suggests a change for the next epoch: add a member, remove one, or update a member’s own keys. A proposal alone changes nothing. A Commit applies one or more proposals, provides fresh randomness, and starts the next epoch.
This creates the one ordering rule MLS insists on. Most messages can arrive in any order, but every member must apply the same single Commit to end each epoch. If two members commit at once from the same epoch, only one can win. The architecture RFC says the delivery system usually handles this by ordering Commits so that everyone accepts the first valid one and rejects the rest.
Application messages are sent encrypted and authenticated as a PrivateMessage. Proposals and Commits can be sent the same way, or as a PublicMessage that is signed but not encrypted.
The ratchet tree
The ratchet tree is what makes MLS work for large groups. Members sit at the leaves of a balanced binary tree. Each node can hold a public key, and a member may know a node’s private key only if that node sits above its own leaf. So a parent node’s key is shared by members below it and by nobody else.
That arrangement makes it cheap to send a secret to “everyone except” someone. RFC 9420 gives the example of encrypting to all but one member of a group of N: with the tree, it takes about log(N) encryptions to subtrees instead of the N minus 1 needed to encrypt to each member separately.
When a member commits with fresh keys, it generates a new secret for its leaf and derives a chain of new secrets for each node on its path to the root. It encrypts each of those to the subtree hanging off that path, so every other member can decrypt exactly the one it needs and compute the rest. The result feeds the key schedule, which produces the next epoch secret. The architecture RFC cites the research behind this design under the name TreeKEM.
The Delivery Service and Authentication Service
MLS assumes two services around it, described in RFC 9750, the MLS architecture document.
- The Delivery Service stores and hands out key packages and routes MLS messages among clients. MLS is designed so that even a compromised Delivery Service cannot read group messages, forge them, or add itself to a group. It can still delay, drop or reorder messages, block a member, and, if it orders Commits, influence which one is applied.
- The Authentication Service issues credentials that bind identities to signature keys, and lets members check each other’s credentials. It is trusted far more: a compromised Authentication Service can impersonate users.
Neither has to be a central server. RFC 9750 notes that clients on a peer-to-peer network can form a decentralised Delivery Service, and that an Authentication Service can be as simple as people comparing key fingerprints. Offline Protocol’s mesh SDK runs MLS on the devices themselves: inviting a user sends an MLS Welcome to the invitee and a Commit to existing members, and groups hold up to 256 members by default in v0.27.0.
Forward secrecy and post-compromise security
MLS aims for two properties. Forward secrecy means messages sent now stay safe if a member’s keys are stolen later. MLS provides it by deleting old tree keys after each epoch and deleting each message key once it has been used.
Post-compromise security means the group recovers after a member was compromised. A member gets it by updating its leaf key, and the protection takes effect once the others process the Commit that carries the update. RFC 9420 says members should send updates regularly while a group is active, usually on the order of hours or days, and that groups should eventually remove members that stop updating, because a member that stays offline for a long time holds old keys that weaken forward secrecy for everyone.