Skip to main content

๐ŸŒณ The Tree of Secret Keys

How MLS Manages Group Keys Efficientlyโ€‹

In 10 minutes: Understand ratchet trees - MLS's secret weapon
Prerequisite: None

๐ŸŽฏ The Simple Storyโ€‹

Remember how we said MLS encrypts once for the whole group?

How does everyone get the same key without sending it over and over?

The secret: A special tree called a ratchet tree

๐Ÿง  Mental Modelโ€‹

Hold this picture in your head:

Ratchet Tree (Horizontal Binary Tree):

Alice    Bob    Charlie    David
  โ”‚       โ”‚       โ”‚         โ”‚
  โ””โ”€โ”€ A โ”€โ”€โ”˜       โ””โ”€โ”€ B โ”€โ”€โ”€โ”€โ”˜
       โ”‚              โ”‚
       โ””โ”€โ”€โ”€โ”€โ”€โ”€โ”€ C โ”€โ”€โ”€โ”€โ”˜
              โ”‚
         Group Secret

Each leaf = One person (Alice, Bob, Charlie, David)
Each node = Shared secret between descendants
C = Group secret (everyone can derive it)

Think of it like a family tree on its side:

Family Tree Metaphor:

๐Ÿ‘ด Grandpa C
 โ”œโ”€ ๐Ÿ‘จ Dad A
 โ”‚  โ”œโ”€ ๐Ÿ‘ฆ Alice
 โ”‚  โ””โ”€ ๐Ÿ‘จ Bob
 โ””โ”€ ๐Ÿ‘จ Dad B
    โ”œโ”€ ๐Ÿ‘ฆ Charlie
    โ””โ”€ ๐Ÿ‘จ David

Family secret at Grandpa:
Everyone in family knows Grandpa's secret
Alice can go up to Grandpa
Bob can go up to Grandpa
Charlie can go up to Grandpa
David can go up to Grandpa

๐Ÿ“Š See How It Worksโ€‹

Let's watch how Alice sends to everyone:

Watch Alice send a message:

Step 1: Alice goes up the tree
Alice โ†’ A (her leaf)
A โ†’ AB (her parent)
AB โ†’ C (everyone's parent)

Step 2: Alice has Group Secret C
Alice encrypts message with C

Step 3: Everyone else gets C the same way
Bob โ†’ B โ†’ AB โ†’ C
Charlie โ†’ C โ†’ CD โ†’ C
David โ†’ D โ†’ CD โ†’ C

Step 4: Everyone can decrypt
All have C, so all can decrypt Alice's message

๐ŸŽญ The Magic Pathโ€‹

Each person has a path to the root:

Alice's path: Alice โ†’ A โ†’ AB โ†’ C
Bob's path:   Bob โ†’ B โ†’ AB โ†’ C
Charlie's path: Charlie โ†’ C โ†’ CD โ†’ C
David's path: David โ†’ D โ†’ CD โ†’ C

The magic: Every path leads to the same group secret

๐Ÿ—๏ธ How MLS Builds the Treeโ€‹

When Alice Creates the Groupโ€‹

Step 1: Alice creates ratchet tree
- She's the only one (leaf index 0)
- Her leaf node: A
- Tree root: C

Step 2: Bob joins
- New leaf added (leaf index 1)
- New parent node: AB
- Tree root updated: ABCD

Step 3: Charlie joins
- New leaf added (leaf index 2)
- New parent node: CD
- Tree root updated: ABCDEF

Step 4: David joins
- New leaf added (leaf index 3)
- Tree root updated (no new node needed)

๐Ÿ”„ Key Rotation with Ratchet Treesโ€‹

What Happens When Someone Leaves?โ€‹

David leaves the group:

Before David leaves:
Alice (0), Bob (1), Charlie (2), David (3)
Tree has 4 leaves

After David leaves:
Alice (0), Bob (1), Charlie (2)
Tree now has 3 leaves

MLS updates tree:
- Remove David's leaf (3)
- Update path: D โ†’ CD โ†’ ABCD
- Generate new secrets on the path
- New group secret at root

Alice sends a message after rotation:

Alice โ†’ A โ†’ AB โ†’ C (new)
Bob โ†’ B โ†’ AB โ†’ C (new)
Charlie โ†’ C โ†’ CD โ†’ C (new)

David:
โ†’ D (deleted)
โ†’ CD (deleted)
โ†’ Can't get C (new)

Result: David can't decrypt any more messages

๐ŸŽฎ Try It Yourselfโ€‹

Question 1: In a ratchet tree, Alice (index 0) wants to send a message. What's her path to the root?

Show Answer
Tree layout:
Alice(0)  Bob(1)  Charlie(2)  David(3)
   โ”‚         โ”‚        โ”‚          โ”‚
   โ””โ”€ A โ”€โ”€   โ”˜   โ””โ”€ B โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”˜
        โ”‚           โ”‚
        โ””โ”€โ”€โ”€โ”€โ”€ C โ”€โ”€โ”€โ”˜

Alice's path:
Alice (leaf 0)
  โ†“
A (parent)
  โ†“
C (root/group secret)

Answer: Alice โ†’ A โ†’ C

Question 2: David (index 3) leaves the group. Can he still read messages?

Show Answer

When David leaves:

  1. MLS removes David's leaf (3)
  2. MLS updates secrets on David's path:
    • D (David's new secret at leaf) โ†’ deleted
    • CD (parent of C and D) โ†’ new secret
    • ABCD (root) โ†’ new secret

David trying to decrypt:

  • David's leaf deleted โ†’ Can't start path
  • Old CD secret โ†’ Doesn't work (changed)
  • Old ABCD secret โ†’ Doesn't work (changed)

Answer: No, David can't read messages after key rotation

Question 3: Why use a binary tree instead of a list?

Show Answer This

Using a list (naive approach):

  • For 1000 people, need to update 999 nodes
  • Each update takes O(n) time

Using a binary tree (MLS approach):

  • For 1000 people, need to update log2(1000) = 10 nodes
  • Each update takes O(log n) time

Efficiency:

  • List: O(n) = slow
  • Tree: O(log n) = fast

Answer: Binary trees are MUCH faster for updates (O(log n) vs O(n))

๐Ÿ’ก Why Ratchet Trees Workโ€‹

Three Magic Propertiesโ€‹

  1. Everyone can reach the root

    • Every leaf has a path to the root
    • Path length: O(log n)
    • Very efficient

  2. Removing someone updates the path

    • Only need to update O(log n) nodes
    • Not O(n) nodes like a list
    • Fast๏ผ

  3. Adding someone updates the path

    • Only need to update O(log n) nodes
    • Scalable to thousands
    • Efficient๏ผ

โœ… Quick Checkโ€‹

Can you explain ratchet trees to a 5-year-old?

Try saying this out loud:

A ratchet tree is like a family tree on its side. Each person is a leaf at the bottom. The grandpa at the top has the family secret. Everyone can climb up to the grandpa and learn the secret. If someone leaves the family, we change the secret, so they can't learn new secrets!

๐ŸŽ“ Key Takeawaysโ€‹

โœ… Ratchet tree = Family tree on its side
โœ… Leaves = Group members
โœ… Root = Group secret
โœ… Path = How each person gets the group secret
โœ… Efficiency = O(log n) for updates
โœ… Rotation = Change secrets on path when someone leaves
โœ… Scalability = Works for 2 to 1000+ people

๐ŸŽ‰ What You'll Learn Nextโ€‹

Now you understand ratchet trees Next, we'll learn about MLS's concept of time:

โฐ Continue: Time Traveling Messages

We'll learn about epochs and how MLS manages message history

Now you understand how MLS manages keys with ratchet trees. Next: How MLS tracks time with epochs