TreeKEM Explained: How MLS Updates a Group's Keys in log(n) Steps

TreeKEM is the part of MLS (Messaging Layer Security, RFC 9420) that lets a group agree on a new shared secret every time someone joins, leaves or refreshes their keys. It arranges members as the leaves of a binary tree, gives every internal node its own key pair, and lets a member replace all the keys from its leaf to the root in one message. In a full tree, that message carries one encrypted secret per level, so about log2(n) ciphertexts for n members, instead of n - 1. This post walks through how that works, where the log(n) bound breaks down, and what TreeKEM does not do.

Most explanations of TreeKEM live in IACR papers and the RFC itself. Here we stay close to the RFC's own terms and section numbers, so you can check every step against the spec. One naming note: RFC 9420 never uses the word "TreeKEM". It describes "an asynchronous key-encapsulation mechanism for tree structures" (Section 1) and specifies it in Sections 4 and 7. TreeKEM is the name from the original proposal, and libraries such as mls-rs still use it (its module is called tree_kem).

The Problem: Pairwise, Sender Keys or a Tree

A group needs a shared key, and it needs to change that key whenever membership changes or a device might have been compromised. There are three broad ways to do it.

The simplest is pairwise: pick a new secret and encrypt it to every other member over a 1:1 channel. That is n - 1 encryptions per change. Signal-style sender keys improve the cost of sending messages, since each member encrypts once with their own sender key, but they make recovery expensive. RFC 9420's introduction puts it plainly: post-compromise security with sender keys needs "a number of key update messages that scales as the square of the group size", and an attacker who learns a sender key "can often indefinitely and passively eavesdrop on that member's messages." We compare the two families in more depth in libsignal vs MLS.

A tree cuts the cost. If every subtree has a key that only its members know, you can reach "everyone except me" by encrypting to a handful of subtrees instead of to each person. Section 4 of the RFC states the goal: encrypting to all but one member "requires only log(N) encryptions to subtrees, instead of the N-1 encryptions that would be needed to encrypt to each participant individually."

Source: RFC 9420, Sections 1 and 4. Groups bring other problems too (membership changes, offline devices, admins); see why group chat security is different.

Where TreeKEM Came From

The tree idea in MLS started with Asynchronous Ratcheting Trees (ART), from Cohn-Gordon, Cremers, Garratt, Millican and Milner (ePrint 2017/666), which RFC 9420 cites as its starting point. ART built the tree from Diffie-Hellman key exchanges. Karthikeyan Bhargavan, Richard Barnes and Eric Rescorla then proposed TreeKEM (2018), which replaces the Diffie-Hellman steps with a key encapsulation mechanism: a member derives a chain of secrets up its path and encrypts each one to the other side of the tree. That is the design MLS adopted, with HPKE (RFC 9180) as the encryption.

It was also analysed before it was finished. Alwen, Coretti, Dodis and Tselekounis (ePrint 2019/1189) showed that the TreeKEM draft of the time achieved post-compromise security but "does not provide an adequate form of FS" (forward secrecy), and proposed a modification that reaches both with almost no efficiency cost. The draft kept changing for years afterwards; the RFC was published in July 2023.

The Ratchet Tree

MLS calls the structure a ratchet tree (Section 4.1). It is a perfect binary tree: every parent has exactly two children and all leaves sit at the same depth, so a tree has 2^d leaves and 2^(d+1) - 1 nodes. Leaves are numbered from 0 on the left.

• Leaves are members. Each member's leaf holds an HPKE public key, a credential that says who they are, and a signature (Section 7.2).
• Parent nodes hold HPKE key pairs for subgroups. The public key is visible to everyone; the private key is known only to the members whose leaves are below that node. Section 7.1 defines a parent as an encryption_key, a parent_hash and a list of unmerged_leaves.
• Any node can be blank, meaning it holds no key at all (Section 4.1.1). Blanks appear after removals and at the empty right edge of a growing tree.

Section 4.2 calls the central rule the tree invariant: "The private key for a node in the tree is known to a member of the group only if the node's subtree contains that member's leaf." Every member therefore knows the private keys on the way from its leaf to the root (or a subset of them), and nothing else. The root's key is known to the whole group, and the secret that produced it is what feeds the key schedule.

Direct Path and Copath

Two lists of nodes, defined in Section 4.1.2, drive everything that follows. A leaf's direct path is its parent, its parent's parent, and so on up to the root. Its copath is the sibling of the leaf plus the sibling of every node on the direct path, stopping below the root. The copath is exactly the set of subtrees that together cover every other member.

                              root*
                  ______________|______________
                 /                             \
              ABCD*                          EFGH(o)
          ______|______                   ______|______
         /             \                 /             \
      AB(o)            CD*             EF              GH
      __|__           __|__           __|__           __|__
     /     \         /     \         /     \         /     \
    A       B      [C]    D(o)      E       F       G       H
    0       1       2       3       4       5       6       7

  [C]  the member sending the commit (leaf 2)
   *   C's direct path:  CD, ABCD, root
  (o)  C's copath:       D, AB, EFGH

For C at leaf 2, the direct path is CD, ABCD and the root. The copath is D, AB and EFGH. D is a single member, AB covers A and B, EFGH covers the right half. Those three subtrees hold everyone except C, and each has a public key C can encrypt to.

The RFC also defines a filtered direct path: the direct path with any node removed whose copath child has nobody in it. If an entire sibling subtree is empty, there is no one to send that node's secret to, so it does not need a key. In a full tree the filtered direct path equals the direct path.

How an UpdatePath Works

When a member commits (Section 12.4), it can include an UpdatePath: a new leaf for itself and new keys for every node on its filtered direct path. Section 7.4 gives the procedure. The member picks one random secret for the first parent above its leaf and hashes its way up:

// RFC 9420, Sections 7.4 and 12.4.1
path_secret[0] is sampled at random
path_secret[n] = DeriveSecret(path_secret[n-1], "path")

node_secret[n] = DeriveSecret(path_secret[n], "node")
node_priv[n], node_pub[n] = KEM.DeriveKeyPair(node_secret[n])

// one step past the root:
commit_secret  = DeriveSecret(path_secret[last], "path")

Each path secret produces one node's key pair, and each is derived from the one below it. Anyone who learns the path secret for a node can compute every path secret above it, but none below it. That one-way chain is what makes the tree efficient.

Now the member has to tell the group. For each node on its filtered direct path, it encrypts that node's path secret to the copath child on the other side, using HPKE. In the diagram, C sends:

• path_secret[0] (for CD) encrypted to D's public key,
• path_secret[1] (for ABCD) encrypted to AB's public key,
• path_secret[2] (for the root) encrypted to EFGH's public key.

D decrypts the first and derives the rest, so D ends up with the new keys for CD, ABCD and the root. A or B decrypts the second with AB's private key and derives the keys for ABCD and the root, but not CD, which is not above them. E, F, G or H decrypts the third and gets only the root. Every member learns exactly the new keys the tree invariant allows. Section 7.5 spells out this flow, and Section 7.6 defines the wire format:

// RFC 9420, Section 7.6
struct {
    opaque kem_output<V>;
    opaque ciphertext<V>;
} HPKECiphertext;

struct {
    HPKEPublicKey encryption_key;
    HPKECiphertext encrypted_path_secret<V>;  // one per node in the copath child's resolution
} UpdatePathNode;

struct {
    LeafNode leaf_node;
    UpdatePathNode nodes<V>;                  // one per node on the filtered direct path
} UpdatePath;

Each encryption is bound to the provisional GroupContext of the new epoch (EncryptWithLabel(node_public_key, "UpdatePathNode", group_context, path_secret)), and receivers check that the public keys they derive from the decrypted secret match the ones in the UpdatePath. Afterwards, everyone must delete the old path secrets, node secrets and replaced private keys (Section 7.5).

Why It Costs log(n), and When It Does Not

In a full, balanced tree, every copath node is non-blank and has no unmerged leaves, so each node on the direct path needs exactly one ciphertext. The direct path has one node per level, so a commit carries log2(n) ciphertexts plus the same number of new public keys.

That is the best case. The real count is the sum, over the filtered direct path, of the size of each copath node's resolution (next section). Blanks and unmerged leaves make resolutions longer. In the worst case, a tree full of holes, the resolutions cover every other member individually and the cost falls back towards n - 1, the same as pairwise. MLS stays efficient as long as members keep committing with paths, because each UpdatePath fills its direct path back in.

Blanks, Resolution and Unmerged Leaves

Why removes blank the path

A removed member knew the private keys on its direct path. Leaving those keys in place would let it read the next epoch's secrets. So Section 12.1.3 says applying a Remove replaces the leaf with a blank and blanks every intermediate node from that leaf to the root. A Remove also requires the commit to carry an UpdatePath (Section 12.4), so the committer immediately puts new keys on its own path and the group gets a new commit secret the removed member cannot compute. An Update proposal (Section 12.1.2) blanks the sender's path the same way.

Resolution

You cannot encrypt to a blank node, so you encrypt to whatever is below it. Section 4.1.1 defines the resolution of a node as the nearest non-blank nodes that together cover its subtree: a non-blank node resolves to itself plus its unmerged leaves, a blank leaf resolves to nothing, and a blank parent resolves to its left child's resolution followed by its right child's.

                              root*
                  ______________|______________
                 /                             \
              ABCD*                           _(o)
          ______|______                   ______|______
         /             \                 /             \
       AB*            CD(o)             _              GH
      __|__           __|__           __|__           __|__
     /     \         /     \         /     \         /     \
  A(o)     [B]      C       D       E       _       G       H
    0       1       2       3       4       5       6       7

  B removes F. F's leaf and its whole direct path (EF, EFGH, root) are blanked.
  B's UpdatePath then refills AB, ABCD and root.
  The root's copath child is blank, so its resolution is [E, GH]: 2 ciphertexts.

Here B removes F. The commit blanks F, EF, EFGH and the root, then applies B's UpdatePath. B encrypts the new AB secret to A and the new ABCD secret to CD, one ciphertext each. The root's copath child is EFGH, which is now blank, so B encrypts the root secret to its resolution: E (because EF is blank and F is empty) and GH. Four ciphertexts instead of three. EF and EFGH stay blank until a member below them commits with a path.

Unmerged leaves

Adding a member works the other way round. The new member goes into the leftmost empty leaf (or the tree grows to the right), and its leaf index is added to the unmerged_leaves list of every non-blank node above it (Section 12.1.1). The new member does not know those nodes' private keys, so anyone encrypting to such a node must also encrypt to each unmerged leaf listed in it. When an UpdatePath later replaces a node's key, its unmerged list is cleared.

Add does not require a path, so an Add-only commit can skip the UpdatePath entirely. When the committer does include one, the new member is excluded from the resolutions in that UpdatePath and receives a path secret in its Welcome message instead, for the lowest common ancestor of its leaf and the committer's (Section 12.4.3.1), and derives the keys above it from there.

Tree Hashes and Parent Hashes

Keys alone do not stop a member from being handed a doctored tree. MLS hashes the tree in two ways.

Tree hashes (Section 7.8) summarise the current state. Each leaf hashes its index and contents; each parent hashes its contents and the tree hashes of its two children. The root's tree hash goes into the GroupContext (Section 8.1), and the GroupContext is an input to the key schedule. If two members disagree about any node in the tree, they derive different epoch secrets and their messages fail to decrypt or verify.

Parent hashes (Section 7.9) record how keys got there. When a member builds an UpdatePath it computes a chain of hashes from the root down to its leaf, each covering a node's public key, the parent hash of the node above it, and the tree hash of its copath sibling as it was at that moment. The member signs the last link inside its leaf. A new member joining with a full copy of the tree can then check that every non-blank parent node was set by an UpdatePath from a real member, not inserted by whoever handed over the tree. Appendix B of the RFC walks through an example.

From commit_secret to the Epoch Secret

The ratchet tree's only output into the rest of MLS is one value: the commit_secret. Section 12.4.1 defines it as one more "path" derivation past the root's path secret. If the commit has no UpdatePath, the commit secret is all zeros. The key schedule (Section 8) then mixes it with the previous epoch's init_secret and the new GroupContext:

// RFC 9420, Section 8 (simplified)
joiner_secret = ExpandWithLabel(
                  KDF.Extract(init_secret[n-1], commit_secret),
                  "joiner", GroupContext[n], KDF.Nh)

epoch_secret  = ExpandWithLabel(
                  KDF.Extract(joiner_secret, psk_secret or 0),
                  "epoch", GroupContext[n], KDF.Nh)

encryption_secret = DeriveSecret(epoch_secret, "encryption")  // feeds the secret tree
confirmation_key  = DeriveSecret(epoch_secret, "confirm")
init_secret[n]    = DeriveSecret(epoch_secret, "init")        // input to the next epoch

From epoch_secret come the secrets for the epoch: encryption_secret, which seeds the secret tree that gives each member its own message keys (Section 9), plus secrets for sender data, exporters, confirmation and membership MACs, resumption PSKs and the epoch authenticator (Table 4). The chain through init_secret means each epoch depends on every earlier one. A commit without a path still moves the group to a new epoch with new keys, but it adds no fresh randomness: only commits with an UpdatePath do that.

Forward Secrecy and Post-Compromise Security

Section 16.6 defines both terms for groups. Forward secrecy means messages sent before a compromise stay safe. Post-compromise security (PCS) means the group recovers after one.

• PCS comes from UpdatePaths. Once a member commits with a path, the keys on its direct path are new and were never encrypted to anything an attacker held. The RFC notes an Update proposal alone does not give PCS until someone commits it, and that the guarantee starts when members process the commit, not when it is created.
• Forward secrecy comes from deletion. Between epochs, it depends on everyone deleting old tree private keys; within an epoch, on deleting message keys after use. Because these secrets are shared, forward secrecy is at risk "as long as any member has not deleted these keys", and the RFC says applications SHOULD evict members that have been offline too long.

The tree changes the cost of PCS, not the need for it. Groups only heal if members actually commit with paths. A member who never commits keeps the same leaf key for as long as it stays in the group.

What TreeKEM Does Not Do

• It does not order commits. An UpdatePath is computed against one specific tree. If two members commit from the same epoch, only one can win, and RFC 9420 Section 14 leaves the choice to the application. We describe how Lupyd's server makes that choice in MLS commit ordering and epoch races.
• It does not hide membership. Section 16.4.3: the ratchet tree is the membership list, since every leaf carries a credential. Applications that expose the tree outside the group leak membership, and Add and Remove proposals sent as PublicMessage leak membership changes. Deployments where the delivery service reads commits so it can validate them, as Lupyd's server does, give that service the group's membership.
• It does not authenticate identities by itself. The tree carries credentials and signatures, but deciding whether a credential belongs to the right person is the job of the authentication service and the application (Section 5.3).
• It does not protect devices. Malware on a member's device can read what that member reads. TreeKEM limits how long a stolen key stays useful; it does not stop the theft.

TreeKEM in mls-rs and Lupyd

Lupyd's group channels use MLS through mls-rs 0.54, inside our open-source engine Firefly. Application code never touches path secrets directly: it builds a commit, and mls-rs decides whether the commit needs an UpdatePath using the same rule as the RFC:

// mls-rs 0.54.0: src/group/message_processor.rs (feature flags trimmed)
pub(crate) fn path_update_required(proposals: &ProposalBundle) -> bool {
    let res = !proposals.external_init_proposals().is_empty();
    let res = res || !proposals.update_proposals().is_empty();
    res || proposals.length() == 0
        || proposals.group_context_extensions_proposal().is_some()
        || !proposals.remove_proposals().is_empty()
}

// mls-rs 0.54.0: src/group/commit.rs
let perform_path_update = commit_options.path_required
    || path_update_required(&provisional_state.applied_proposals);

path_required comes from the application's MlsRules. Firefly does not set it, so it stays at the mls-rs default of false and the RFC's rules apply. In practice that gives three kinds of commit:

// firefly: crates/core/src/lib.rs (trimmed)

// Adding a member: an Add-only commit. Add does not require a path,
// and Firefly keeps mls-rs's default of path_required = false.
commit_builder = commit_builder.add_member(key_package)?;
let commit = commit_builder.build().await?;

// Removing devices: Remove requires a path, so mls-rs builds an UpdatePath.
let mut builder = group.commit_builder();
for index in indices {
    builder = builder.remove_member(index)?;
}
let commit = builder.build().await?;

// Renewing this device's credential: a commit with no proposals,
// which always carries an UpdatePath for the committer's direct path.
let commit = group
    .commit_builder()
    .set_new_signing_identity(secret, signing_identity)
    .build()
    .await?;

Adding someone is an Add-only commit with no UpdatePath; the new device starts as an unmerged leaf. Removing a device, either by an admin or when a device is gone, carries an UpdatePath that refreshes the remover's path. Renewing a device's credential is a commit with no proposals, which mls-rs always sends with a path, so it also refreshes that device's leaf key and every key above it. The resulting CommitOutput has a contains_update_path flag if you want to log which kind you sent. The server, which runs as an MLS external client, processes these commits to track the tree, which is why it sees group membership but not message content.

Frequently Asked Questions

Final Takeaway

TreeKEM turns "send a new key to everyone else" into "send one secret per level of a tree". A committer hashes a random secret up its direct path, encrypts each step to the matching copath subtree, and the secret one step past the root becomes the commit secret that drives the next epoch. Removes blank paths so old keys die, unmerged leaves let new members in cheaply, and tree and parent hashes keep everyone's view of the tree honest. The log(n) cost is a best case that depends on members committing regularly, and the tree says nothing about ordering or metadata, which the application has to handle.

Lupyd's group channels run on this through mls-rs, and the code is open in Firefly. Try Lupyd if you want to see MLS group channels in use.

Last updated: 4 November 2026.