Why a tree
In a group, the hard operation is removal. To shut out one member, everyone else needs a new secret that the removed member cannot learn. Sending it to each remaining member separately means one encryption per member, which grows with the group.
RFC 9420, the MLS standard, solves this with a tree. A ratchet tree assigns shared keys to subgroups, so that encrypting to all but one member takes log(N) encryptions to subtrees instead of the N-1 encryptions needed to reach each person individually, where N is the number of members. The RFC states that this lets members derive and update shared keys with costs that scale as the log of the group size. How group encryption works compares this with older approaches.
The shape of the tree
Every tree in MLS is a perfect binary tree: each parent has exactly two children, and all leaves sit at the same depth. A tree of depth d has 2^d leaves and 2^(d+1) - 1 nodes in total.
- Leaves are members. Each member occupies one leaf, which holds its public encryption key, its credential and the other details of its appearance in the group, signed by that member. In MLS a member is a client, which RFC 9750 says usually means one device.
- Parent nodes hold shared keys. A non-blank parent node holds a public key. The matching private key is shared by the members below it.
- Some nodes are blank. A blank node holds no key. Blanks appear when nodes have been cleared, for example after a removal, and members encrypt to the nearest non-blank nodes below them instead.
Every node also has a hash summarising the subtree under it. RFC 9420 says the hash of the root goes into the group context to confirm that the group agrees on the whole tree.
Who knows which keys
The rule that makes the tree work is what RFC 9420 calls the tree invariant: a member knows the private key for a node only if that node’s subtree contains the member’s own leaf.
Take a group of four, A, B, C and D. A and B share the private key of the parent above them. All four know the private key at the root. Nobody knows another member’s leaf private key. To reach every member except D, a sender can encrypt once to the parent of A and B and once to C’s leaf, rather than three times.
The RFC also tracks “unmerged” leaves. A new member does not yet know the private keys of the nodes above it, so anyone encrypting to one of those nodes must also encrypt to the new member’s own key. The RFC says leaves become merged as they receive the private keys for the nodes above them.
How a commit refreshes the tree
Changes to the group happen through Commits, and each Commit starts a new epoch. When a member commits, RFC 9420 Section 7.4 has it replace the keys on its own path to the root:
- Clear every node on the path from its leaf to the root.
- Generate a fresh key pair for its leaf.
- Pick a random secret for the first parent above it, and derive each higher node’s secret from the one below with a key derivation function.
- Turn each of those secrets into a key pair for that node.
It then sends an UpdatePath to the group: the new public keys, and for each node on the path, its secret encrypted to the subtree on the other side, the copath. A member in that subtree decrypts one secret and derives every secret above it, because each is computed from the one below.
Adding and removing members
Leaves are added and removed at the right edge. When the tree is full, MLS adds a new blank root whose left side is the old tree and whose right side is an empty subtree with room for new members. When the right half becomes empty after removals, the tree is truncated back down.
A Remove proposal names the leaf index to remove. Members applying it replace that leaf with a blank node, blank every node on its path to the root, and truncate if they can. The Commit that carries the Remove must include a fresh UpdatePath, so the removed member’s old keys no longer protect anything.
Why it matters for security
The tree is where MLS gets its two time-based properties. RFC 9420 says post-compromise security comes from members regularly updating their leaf keys, which replaces the compromised parts of the tree with keys an attacker does not have. Forward secrecy between epochs comes from deleting private keys from past versions of the tree so old group secrets cannot be derived again.
The same structure is why MLS can remove a member efficiently, and why a member that stays offline is a risk: its leaf keeps old keys until it updates or is removed. How MLS works shows how the tree fits with key packages, proposals and the key schedule, and new members are added to it from their key packages.