PigeonPigeon Download

Group encryption (MLS) and ordering

Every Pigeon conversation, including one-to-one chats, is an MLS group. MLS gives forward secrecy and post-compromise security, but it needs everyone to agree on one order of changes to the group. Pigeon gets that order without a central server.

MLS in Pigeon Built

  • Protocol: Messaging Layer Security, RFC 9420, through the OpenMLS 0.9 line.
  • Ciphersuite: MLS_128_DHKEMX25519_AES128GCM_SHA256_Ed25519.
  • Every device is a full member of the group. There's no primary phone that others depend on.
  • There's no admin role: any member may add or remove members.
  • The ratchet tree travels inside the Welcome message.

Pigeon's own outer seal (see architecture) adds a post-quantum hybrid KEM on top of MLS's own encryption.

Group size

A Welcome is capped at 1 MiB, which today fits about 685 members' devices: roughly 230 people with three devices each. The desktop alpha caps groups lower, at the largest size we've tested. Much larger groups and channels are designed but Planned.

One history per epoch Built

In MLS, a commit moves the group from one epoch to the next. If two members commit at once, the group can split into two histories. Pigeon prevents that with a sealed, write-once commit slot per epoch, held on the same five replicas as the mailbox:

  1. Round 1: a commit wins once it's found in four of the five slots.
  2. If round 1 doesn't decide (a split vote, or 5 seconds pass), round 2 runs with one designated committer, the lowest-numbered member allowed to commit, and decides at three of five.

This is Fast Paxos with two ballots. Slots are written to disk before they're acknowledged. Each epoch also has a fork beacon, an address both sides of a split can read, so a fork that slips through is detected and shown to members rather than silently tolerated. The node can't tell which member wrote a slot.

Model-checked

The ordering protocol is specified in TLA+ (specs/GroupOrdering.tla) and checked with TLC over five replicas and three members, with crashes, recoveries, and lost, duplicated and reordered messages. It checks that at most one commit is accepted per epoch, that an honest member who sees conflicting histories flags a fork, that no member applies a commit from an older epoch, that honest members' histories agree, and liveness. Each fix has a mutation that must produce a counterexample.

Not yet checked: more than three members, several epochs in the race configurations, and a malicious designated committer.

Sources: ADR-0006 (groups and ordering), ADR-0005 (Welcome size), docs/OPENMLS_NOTES.md, specs/GroupOrdering.tla, specs/README.md.