Scaling End-to-End Encrypted Groups at Tula
Encrypting a message is only one part of the system. At scale, we also have to handle membership changes, key distribution, offline users, message fan-out, recovery after failures, database growth,
At Tula, group messaging is designed to remain end-to-end encrypted even as groups become large.
That creates an interesting engineering problem.
Encrypting a message is only one part of the system. At scale, we also have to handle membership changes, key distribution, offline users, message fan-out, recovery after failures, database growth, retries, and low-end mobile devices.
Before launching encrypted groups publicly, we wanted evidence rather than assumptions.
So we built a qualification suite around our OpenMLS implementation and Tula's backend delivery service, and tested the system at:
100 members
500 members
1,000 members
2,500 members
5,000 members
Our initial public group limit will be 1,000 members.
We are architecting for 5,000, but we are deliberately not promising that as a production limit yet.
This post explains what we measured, what surprised us, and what remains to be proven after launch.
Architecture: OpenMLS stays on the device
Tula's backend does not participate in MLS cryptography.
The architecture is deliberately split:
Tula mobile client
│
│ OpenMLS
│
├── group secrets
├── epoch state
├── ratchet state
├── encryption/decryption
└── membership cryptography
│
│ opaque protocol artifacts
▼
Tula backend
│
├── KeyPackage delivery
├── Commit sequencing
├── Welcome delivery
├── public ratchet-tree delivery
├── durable message fan-out
└── offline delivery
The Go backend remains an opaque delivery service.
It never receives MLS epoch secrets, ratchet secrets, private signature keys, or private group state.
This separation matters because we do not want scaling the backend to quietly turn the server into a trusted cryptographic participant.
Why our launch limit is 1,000
There is an important difference between:
Can the protocol represent 5,000 members?
and:
Are we comfortable promising a reliable 5,000-member experience to real users?
Our tests show that the architecture can operate at 5,000 MLS leaves.
But 1,000 gives us substantially more operating margin.
The clearest example is Commit size.
Tula currently caps an individual MLS Commit or Welcome at:
61,440 bytes
Our largest measured Add Commit was:
| Members | Largest Add Commit |
|---|---|
| 100 | 23,149 B |
| 500 | 38,970 B |
| 1,000 | 44,255 B |
| 2,500 | 54,821 B |
| 5,000 | 60,104 B |
At 1,000 members:
Hard cap 61,440 B
Measured maximum 44,255 B
Headroom 17,185 B
≈ 28% headroom
At 5,000:
Hard cap 61,440 B
Measured maximum 60,104 B
Headroom 1,336 B
≈ 2.2% headroom
That difference is why our launch decision is conservative.
1,000 members looks comfortable.
5,000 works under the tested conditions, but the margin is too small for us to call it a product guarantee yet.
The public ratchet tree scales differently
Tula does not embed the full public MLS ratchet tree in every Welcome.
Instead, clients fetch it out-of-band and OpenMLS verifies it against the authenticated tree hash.
Our measured serialized public-tree sizes were:
| Members | Public tree |
|---|---|
| 100 | 25,402 B |
| 500 | 125,286 B |
| 1,000 | 251,481 B |
| 2,500 | 629,451 B |
| 5,000 | 1,259,948 B |
At 1,000 members, the tree is roughly 251 KB.
At 5,000, it is roughly 1.26 MB.
That is very manageable as a network artifact, but it is also why we did not want the tree duplicated inside every Welcome.
Real OpenMLS, not simulated membership
The cryptographic qualification uses OpenMLS 0.8.1 with a committed Cargo lockfile.
The tests perform real group operations, including:
- group creation;
- KeyPackage-based additions;
- out-of-band tree joins;
- application-message encryption and decryption;
- exporter-secret equality checks;
- offline Commit catch-up;
- member removal;
- member re-addition;
- provider-state reload.
At 1,000 members and above, the harness additionally removes and re-adds 100 real leaves.
The full cryptographic scenario measured:
| Members | Whole scenario |
|---|---|
| 100 | 0.18 s |
| 500 | 1.15 s |
| 1,000 | 4.21 s |
| 2,500 | 21.78 s |
| 5,000 | 83.09 s |
These are desktop qualification measurements, not mobile latency promises.
They are useful because they tell us the cryptographic architecture still behaves correctly as the tree grows.
An important 5,000-member limitation
The tests also found something useful that a design document probably would not have revealed.
Repeatedly adding members from only the original owner eventually accumulates enough sibling-tree material that later Commit sizes can exceed the individual Commit limit.
The 5,000-member scenario therefore uses rotating online representatives performing maintenance updates.
That means we can accurately say:
Coordinated 5,000-member onboarding:
QUALIFIED in the desktop harness
Arbitrary/offline 5,000-member onboarding:
NOT QUALIFIED
This is exactly why we test.
The result did not make us raise the size cap.
Instead, it gave us a concrete requirement for the future native onboarding orchestrator.
Backend fan-out: encryption is not the expensive part
MLS allows a sender to encrypt one group message efficiently.
But the server still needs to deliver that message to the members who should receive it.
For a 1,000-member group, one message means roughly:
1 shared ciphertext
↓
999 durable recipient deliveries
We tested that separately using the real Go service and PostgreSQL.
First-send results
| Members | Delivery rows | First send |
|---|---|---|
| 100 | 99 | 34.12 ms |
| 500 | 499 | 48.71 ms |
| 1,000 | 999 | 71.06 ms |
| 2,500 | 2,499 | 170.57 ms |
| 5,000 | 4,999 | 298.48 ms |
The scale test also verifies that after an MLS member is removed:
new delivery rows for removed device = 0
That sounds obvious, but it is an important privacy and correctness property.
A user who is no longer part of the MLS group should not continue receiving encrypted traffic or notification metadata simply because they remain somewhere in a broader conversation record.
The 1,000-member latency question
During an earlier qualification pass we observed an approximately 232 ms first-send result at 1,000 members.
That raised an obvious question:
Why isn't a local send closer to 10 ms?
Instead of immediately rewriting the fan-out architecture, we instrumented the send path.
We now trace:
chat.mls.send
├── authorization
├── generation lookup
├── roster lookup
├── budget checks
├── backlog admission
├── message insert
├── delivery insert
├── push-target preparation
└── transaction commit
Then we reran a warm small-to-large sweep.
Final send-latency sweep
| Members | p50 | p95 | max |
|---|---|---|---|
| 2 | 6.53 ms | 8.94 ms | 9.38 ms |
| 10 | 6.44 ms | 8.35 ms | 8.51 ms |
| 25 | 8.54 ms | 12.71 ms | 16.85 ms |
| 50 | 9.78 ms | 14.94 ms | 15.22 ms |
| 100 | 13.91 ms | 19.74 ms | 26.36 ms |
| 250 | 25.55 ms | 40.20 ms | 42.18 ms |
| 500 | 37.14 ms | 75.56 ms | 283.74 ms |
| 750 | 52.13 ms | 175.02 ms | 195.51 ms |
| 1,000 | 66.24 ms | 124.61 ms | 142.81 ms |
This was the curve we wanted to see.
Small groups are inexpensive.
The cost rises primarily with recipient fan-out rather than from a large fixed overhead applied to every send.
Where does the 1K cost go?
At 1,000 members, median phase timings looked approximately like this:
| Phase | Median |
|---|---|
| Authorization | 1.12 ms |
| Generation lookup | 0.70 ms |
| Roster lookup | 4.34 ms |
| Budget checks | 0.73 ms |
| Backlog admission | 3.68 ms |
| Message insert | 0.72 ms |
| Delivery insertion | 50.60 ms |
| Push preparation | 0.60 ms |
| Transaction commit | 1.00 ms |
The dominant operation is not MLS cryptography.
It is:
creating durable delivery state for 999 recipients.
That is expected.
Tula currently keeps this work synchronous because we want a strong acceptance invariant:
Once a send is accepted, the durable recipient-delivery state already exists.
We could make sender acknowledgement faster in the future by moving fan-out to asynchronous workers.
But doing so would introduce another durable queue, recovery logic, idempotent materialization, crash-window handling, and roster-snapshot semantics.
At the current numbers, we do not believe that complexity is justified yet.
What happens under a large offline backlog?
We also wanted to understand a much uglier case.
We created a 5,000-member group and sent 100 messages while intentionally allowing a very large offline delivery backlog.
The result was:
499,900 recipient delivery rows
102,400 bytes of shared ciphertext
The important detail is that Tula stores one shared group ciphertext per logical message, rather than duplicating that ciphertext 4,999 times.
Recipient delivery state is separate.
On a final disk-backed PostgreSQL run:
100 messages
499,900 recipient rows
~102 seconds total burst
After ACK/recovery:
504,899 retained audience rows
499,900 still pending
The delivery table plus indexes occupied roughly:
145 MB
This is intentionally a stress case, not a normal operating target.
The backlog admission query is something we will watch
At approximately 500,000 pending rows, we have observed the bounded backlog-admission query taking roughly:
~345 ms
in an earlier environment and:
~164 ms
in a later warm disk-backed run.
We are deliberately not presenting one number as a production benchmark.
What matters is that the work becomes material as the backlog gets very large.
Before increasing the public group limit beyond 1,000 members, this is one of the areas we plan to evaluate again using production-like storage and real production traffic patterns.
Reliability mattered more than a pretty benchmark
Several failure modes were deliberately tested.
Examples include:
- exact Commit retries;
- lost Commit responses;
- stale MLS generations;
- malformed/invalid Commit recovery through explicit generation reboot;
- member removal;
- offline control catch-up;
- KeyPackage exhaustion;
- stale Welcomes;
- retry audience expansion;
- queue capacity;
- group-size enforcement.
We also run mutation tests.
For example, if we deliberately remove the active-MLS-roster predicate from delivery routing, our test suite fails because a removed MLS member receives a new application message.
That kind of regression test is important to us.
A green test is more meaningful when we have also demonstrated that the test turns red when the security property is intentionally broken.
Observability is part of the feature
We already operate OpenTelemetry, Prometheus, dashboards, scraping and Slack alerting at Tula.
Large encrypted groups are integrated into that stack rather than receiving their own monitoring system.
We now measure things such as:
send latency by group-size bucket
MLS roster lookup latency
delivery insertion latency
backlog admission latency
recipient fan-out size
Commit size
public-tree size
control catch-up depth
stale-generation frequency
group reboot frequency
KeyPackage exhaustion
backlog rejection
send/fan-out rejection
We deliberately avoid high-cardinality Prometheus labels such as:
user IDs
device IDs
conversation IDs
group IDs
phone numbers
group names
Instead we use bounded group-size buckets such as:
1–10
11–25
26–50
51–100
101–250
251–500
501–750
751–1000
1001–2500
2501–5000
Large groups do not alert merely because they are large
A 900-member group is not an incident.
Bad behavior is.
For example, our provisional alerting includes sustained conditions around:
- elevated p95 send latency in the 501–1,000 member tier;
- slow backlog admission;
- repeated Commit sizes approaching the hard limit;
- backlog admission refusals;
- abnormal stale-generation rates;
- repeated group reboots;
- KeyPackage exhaustion;
- sustained deep control catch-up.
We expect to tune these thresholds once production gives us a real baseline.
Why we are still launching at 1,000
The tests might make it tempting to simply enable 5,000-member groups.
We are not doing that.
At 1,000 members we have:
~28% Commit-size headroom
~251 KB public tree
real 100-member churn tests
p50 send around 66 ms
p95 send around 125 ms
999-recipient durable fan-out proven
At 5,000:
only ~2.2% Commit-size headroom
~1.26 MB public tree
coordinated onboarding requirements
much larger queue/fan-out amplification
The architecture is deliberately not hard-coded around 1,000.
But launch limits are product promises, not theoretical protocol limits.
For that reason:
Tula launch group maximum:
1,000 members
Engineering target:
up to 5,000 members
We would rather raise a limit after observing real systems than lower one after users depend on it.
What these tests do not prove
These results are deliberately narrow.
They do not prove:
- production p95 or p99 latency;
- 5,000 simultaneously connected phones;
- 5,000 physical devices running OpenMLS;
- mobile RAM behavior;
- Android battery behavior;
- iPhone battery behavior;
- performance of our future encrypted native MLS StorageProvider;
- APNs throughput;
- FCM throughput;
- production-database power-loss behavior;
- arbitrary offline onboarding of 5,000 members.
The cryptographic benchmarks ran on Apple Silicon.
The database qualification used local PostgreSQL environments.
Some stress tests intentionally used synthetic push capture rather than external push providers.
Those are qualification environments, not production.
What remains before encrypted groups ship
Backend work is only half of the system.
Before public release we still need to qualify the mobile side, including:
- authenticated binding of MLS signing keys to Tula device identity;
- Rust/UniFFI OpenMLS integration;
- dedicated device-bound encrypted MLS storage;
- backup exclusion;
- per-group native operation serialization;
- byte-bounded onboarding orchestration;
- large-group maintenance coordination;
- leave/recovery UX;
- physical Android testing;
- physical iPhone testing;
- mobile RAM and CPU behavior;
- battery impact;
- foreground/background transitions;
- long-offline recovery.
The backend can be ready while the product is not ready.
We are intentionally keeping those gates separate.
What happens after launch?
This is probably the part we are most interested in.
Lab qualification gives us controlled evidence.
Production gives us reality.
After launch we want to compare these results against questions such as:
What is the real distribution of Tula group sizes?
How many groups actually cross 100, 500 or 750 members?
What does p95 send latency look like at each tier?
How often do groups churn membership?
How large do real MLS Commits become?
How frequently do users stay offline long enough to build deep catch-up queues?
How often do KeyPackage pools become exhausted?
How much battery and memory does OpenMLS consume on low-end Android phones?
Does a 1,000-member group behave the way our desktop qualification predicted?
We intend to publish that comparison.
That second post will probably be more valuable than this one.
Engineering limits should be evidence, not folklore
One of the biggest lessons from this work is that it is easy to choose arbitrary limits.
Someone can say:
“Encrypted groups should probably stop at 100.”
Someone else can say:
“MLS supports huge groups, so 10,000 should be fine.”
Neither statement tells us much about our implementation.
Instead, we wanted to know:
How large are our actual Commits?
How large is our actual tree?
What happens to PostgreSQL fan-out?
What does retry behavior look like?
What happens with 500,000 pending deliveries?
Can a removed member accidentally keep receiving traffic?
Can the system recover after a bad Commit?
Where does sender latency actually come from?
Those questions gave us a much more useful answer.
For Tula today, that answer is:
1,000 members is the launch limit we are comfortable standing behind.
And:
5,000 remains a real engineering target that our architecture has already exercised, but not yet a public promise.
Once Tula is carrying real traffic, we will come back with the numbers that matter most:
what actually happened in production.
