How should group chats work in decentralized systems?
Tradeoffs that need to be addressed to provide a group-chat experience in decentralized systems
Intro
I’ve recently released the initial version of Kiyeovo - a decentralized P2P messenger desktop app.
I cannot emphasize how much time went into thinking about group chats. Each model that I came up with had a major flaw, and this was really where the “no server” aspect started to hurt. I realized that there is no “best” way to do this, and that I must choose some tradeoffs in order to keep the app fully decentralized.
Why a server makes groups easy
With a central server, you have a trusted authority that answers these questions:
Who is in this group right now?
What key encrypts the messages, and who should have it?
What order did messages happen in?
I was offline; what did I miss?
Even E2E encrypted apps that can’t read your messages still use servers for these questions.
Signal’s server stores the group roster (and forwards messages)
Matrix homeserver stores group state and orders events
They hand the group state to newly added users, and simply stop the removed users from receiving updates and messages. The content is encrypted, but the coordination - who’s in, what’s the latest state, what came first, what you missed - is answered centrally.
Delete the server and what happens? There’s no “place” that for sure knows the roster, no sequencer machine for ordering, and no 24/7 mailbox for the people who were offline.
2. How other decentralized systems handle it — and why I went another way
There’s a whole range of approaches, below are some that I considered.
(a) Keep a coordinating server (Signal, WhatsApp, Matrix)
The content is E2E encrypted, but a server (or homeserver) still holds everything described a moment ago. Group key schemes here are usually:
Sender keys: Signal - symmetric key per sender, rotates keys when a member leaves
Megolm: Matrix - per-sender ratcheting session, rotated on members leaving/joining
Why not: This one was a hard pass because it included centralization, which was one of my non-negotiables. This defeats the purpose of a serverless app - the network needs to keep working with no “privileged” points.
(b) MLS / TreeKEM (RFC 9420)
MLS is the state-of-the-art for group encryption. Every member’s key is arranged in a tree, so when you remove or add someone, it only touches a part of the tree. In other words, it’s very scalable - stays fast even in groups of thousands.
Why not: MLS requires a “Delivery Service” that hands out its key-change messages. Doing it
with no server, over a DHT, where peers can be offline… is a lot. But also, the tree only really pays off in big groups whereas Kiyeovo groups cap at 10
(c) Leaderless membership
Let any member add or remove other members, and eventually converge with some merge logic. Authority is fully decentralized — no
admin at all.
Why not: The moment two people change the membership at the same time, peers can end up with
different pictures of who’s actually in the group. You can merge those back together
eventually, but the merge rules get tricky. For example, there’s no way to answer an ordering question without a trusted clock. “Was X kicked before or
after the message they just sent?” has no answer if members don’t agree on a “global event order”. I have thought about having a proof-of-work layer, but that seemed too heavy.
(d) Fix the membership at creation (e.g. Briar-style private groups)
Some P2P apps dodge the whole problem by not supporting dynamic membership: the member set is fixed when the group is created, and you never add or remove anyone.
Why not: This was actually my initial idea. However, not having invite or kick was too big of a downside for me. While I’m writing this, I am actually thinking about how often do the groups I’m in change membership, and the answer is - not that often. This would’ve simplified things quite a bit, but now it’s done and dynamic groups work, so that’s pretty good.
3. How I actually did it
Rules: no server anywhere, make convergence trivial.
3.1 Membership: One creator
Every group has one creator, identified by an Ed25519 key. All other members have the creator’s key so they can use it to confirm that the update actually came from them. Only the creator can invite and kick. Members who want out send a signed leave request and the creator applies the removal.
Pros: There’s no “two admins kicked different people during a partition” situation to merge - there is exactly one legit writer of membership state. Convergence is simple when there’s only one author -> this is actually the opposite of approach (c).
Cons: the creator is a single point of failure. If they lose their device (identity) or are just not online - existing members can keep talking on the current key, but nobody can be added or removed (users can still leave and not receive message, but the other group members will not have a verified notification that X left the group).
3.2 Keys: Rotated Sender keys per epoch
An epoch is just a “group version”. Each epoch has one random 32-byte symmetric key shared by the whole group. Messages are XChaCha20-Poly1305 encrypted using that key. To distribute it, the creator seals the key to each member individually (public-key encryption to each member’s key) inside a signed control message, and then delivered to their private inboxes.
Pros: Rekey is O(n) sealed copies. Group limit is 10 - very lightweight.
Cost: no in-epoch rotation, so no continuous forward secrecy within a stable group.
3.3 Rotation: membership changes rotate the key
Join, leave, and kick create a new epoch. A new member is only sent the key for the epoch they joined, so they can’t read older history.
In libp2p, topics are basically “channels”. If you subscribe to a topic called “cars”, you will receive messages from that topic. That’s how group realtime messages work - you send messages to a topic. Of course, the messages are encrypted so even if someone guesses the topic (basically impossible), they won’t be able to decrypt the messages. Why do I say that guessing the topic is basically impossible? The topic name is derived from the group key, so rotating the key also rotates the topic. A removed member can’t even compute, let alone subscribe to the new topic.
3.4 Group state distribution: an append-only log in the DHT
Group metadata (membership, per-sender sequence boundaries [explained later]) lives in the DHT as two record types:
a mutable “latest version” pointer
chain of immutable, hash-chained versioned records - an append-only log, each entry signed by the creator and linking to the previous by hash.
The payload (membership update) is encrypted with the previously mentioned per-epoch key.
Pros: it gives offline members a verifiable history of the group’s “evolution”. Also, the DHT validator rejects anything not group-advancing or not creator-signed.
Cost: it’s last-writer-wins, which is only safe because there’s a single writer.
3.5 Ordering & offline: per-sender sequences, per-sender buckets
Each sender keeps a sequence number for each (group, topic/epoch) - the sequence number is basically “this is my Nth message”. Receivers can then detect gaps for a sender.
When someone is offline, their messages are stored in the DHT. However, there is no per-recipient buckets, but rather per-sender - let me explain because this is uncommon. Every send is written to the sender’s own bucket (for the current epoch). When a user comes online, he has to scan groups x members x not_closed_epochs buckets in order to fetch all offline messages. Why? Well, the alternatives are worse in my opinion:
Have a per-recipient bucket - when sending a message, the sender would need to WRITE to groups x members x not_closed_epochs buckets. On top of that, he would have to keep track of not_closed_epochs per sender, which is a whole other set of problems and inefficiencies.
Have a shared bucket - The bucket names contain the public signature of their owner in order to prevent other users from tampering with it (DHT validators enforce this). One thought I had was to just include all public signatures in the bucket name, but then I’d have to deal with users simultaneously writing into the same bucket, and even rewriting whole buckets. That gets ugly fast.
So, all in all, the option I chose seems like the best option.
Tradeoffs
Single-creator authority is the big one. Single point of failure, and centralized trust
Sender Keys, not MLS. Cross-epoch forward secrecy and post-removal security is in, but there is no ratchet within epoch. Fine for ≤10, I think..
Public-key-encryption key wrap I reused the identity pair I already had in 1:1 messages, but not the modern default
Best-effort ordering - limitation versus systems with clocks
Thank you for reading. If you have any suggestions/questions, contact me using the contact in the footer.