This design specification is dependent on the BACAP and Pigeonhole protocol designs from our paper Echomix: A Strong Anonymity System with Messaging, which describes

The source code and API docs for BACAP are available on pkg.go.dev.

The Pigeonhole protocol establishes anonymous cryptographic communication channels which have a readcap (read capability) and a writecap (write capability). For example, if Alice and Bob want to communicate, they can each create their own Pigeonhole/BACAP channels and exchange readcaps on those channels. Now when Bob writes to his channel, Alice can read those messages because she has Bob’s readcap. Likewise, when Alice writes to her channel, Bob can read those messages because he has Alice’s readcap. This is the most basic construction using BACAP and Pigeonhole.

Here we extend this basic design to work as a minimal group-chat protocol, without key rotation.

BACAP primitives give us two message types:

The group state consists of:

The group chat is completely decentralized. Each member must keep track of every other member.

All messages are SingleMessage if they fit in one BACAP slot, or an AllOrNothingMessage if they are too big.

// TextPayload encapsulates a normal text message.
type TextPayload struct {
    // Payload contains a normal UTF-8 text message to be displayed inline.
    Payload []byte
}

// Introduction introduces a new member to the group.
type Introduction struct {
    // DisplayName is the party's name to be displayed in chat clients.
    DisplayName string
    
    // UniversalReadCap is the BACAP UniversalReadCap
    // which lets you read all messages posted by this user.
    UniversalReadCap *bacap.UniversalReadCap
}

A FileUpload can be used for various purposes such as uploading an image to be displayed inline by the chat client. Likewise, a sound bite could be made visible in the chat along with a play-button. Beyond that, we can support arbitrary file attachments.

// FileUpload encapsulates several file types
// which result in different client behaviors.
type FileUpload struct {
    // Payload contains the file payload.
    Payload []byte
    
    // FileType is the identifier for each file type.
    // Valid file types are:
    // "image"
    // "sound"
    // "arbitrary"
    FileType string
}

The Who message type is used to query who is currently in the group.

// Who is used to query the group chat to find out the member read capabilities.
type Who struct {}

The ReplyWho message answers the Who query with an AllOrNothingMessage BACAP stream containing readcaps for all group chat members, each with the index to start reading at.

type ReplyWho struct {
    Payload *bacap.BacapStream
}

The GroupChatMessage message encapsulates all of the above-mentioned message types and is serialized with CBOR.

// GroupChatMessage encapsulates all chat message types.
type GroupChatMessage struct {
    // Version is used to ensure we can change this message type in the future.
    Version int

    // MembershipHash is the sender's view of who is in the group.
    MembershipHash [32]byte

    TextPayload *TextPayload
    Introduction *Introduction
    FileUpload *FileUpload
    Who *Who
    ReplyWho *ReplyWho
}

Every message carries the sender’s MembershipHash: SHA-256 over the domain separator KP:membership:v1 followed by the 32-byte public key of each active member’s read cap, the sender’s own included, without repeats and in ascending byte order. An Introduction carries the hash of the group as it stood before the member it introduces, and a reader compares it with its own view less that member, whether or not it holds the member yet: the reader may be the member introduced. A reader reports a mismatch; it never drops a message for one. It is the one sign that two members disagree about who is in the group.

The protocol flow for making a new group from scratch (using whatever authentication protocol) is essentially for everybody to exchange PleaseAdd messages.

// PleaseAdd is a message used by a client to try and gain access to a chat group.
type PleaseAdd struct {
    // DisplayName is the party's name to be displayed in chat clients.
    DisplayName string
    
    // UniversalReadCap is the BACAP UniversalReadCap
    // which lets you read all messages posted by this user.
    UniversalReadCap *bacap.UniversalReadCap
}

type SignedPleaseAdd struct {
    // PleaseAdd contains the CBOR serialized PleaseAdd struct.
    PleaseAdd []byte
    
    // Signature contains the cryptographic signature over the PleaseAdd field.
    Signature []byte
}

For introduction to an existing group over an existing channel between an introducer member and new member, an Invitation message is used.

type Invitation struct {
    GroupName string
}

The Invitation protocol flow works as follows.

Pigeonhole boxes are garbage-collected after one to two weeks (see “Ephemeral” in Understanding Pigeonhole). After that, only the author has the content. Acknowledgements tell the author what to restore.

Any group message may carry acknowledgements. None is sent on its own. GroupChatMessage gains one field:

type GroupChatMessage struct {
    Version int
    MembershipHash [32]byte

    TextPayload *TextPayload
    Introduction *Introduction
    FileUpload *FileUpload
    Who *Who
    ReplyWho *ReplyWho

    Acks []byte
    Numbers []byte
    IntroducedAt []byte
}

This new Acks field is a mapping from roster indexes (see Rosters below) to BACAP Idx64 values. Its encoding is described in Acks wire format. Acks is nil when we don’t have anything to acknowledge. Numbers and IntroducedAt keep rosters in step; they are described under Rosters below.

TextPayload and FileUpload are content. Introduction, Numbers and IntroducedAt are control. A message carries either content or control, never both. The retention policy deletes content only (see Disappearing messages), so a message that changes a roster stays readable for as long as its Sent-box record lasts.

Throughout this specification we use roster indexes as the channel identities. Alice keeps a list of the channels she has numbered and refers to each by its place in that list, counting from 0: 0 is Alice herself, 1 is the next member she numbered, and so on. One byte names a member, which keeps acknowledgements small.

A MessageBoxIndex is the whole BACAP derivation state for one box. Its first 8 bytes, little-endian, are the box’s Idx64. BACAP’s derivation adds one to the Idx64 at each step and never wraps: a stream ends rather than reach 2⁶⁴. On one stream an Idx64 therefore names exactly one box, and orders the stream’s boxes as they were written. Every member holds every member’s read cap, and so each stream’s first index, from which BACAP’s AdvanceIndexTo derives the box at any later Idx64. An acknowledgement names a box by its Idx64, 8 bytes instead of 104. An Idx64 means nothing without the stream it belongs to, so a reader MUST resolve an acknowledgement’s roster index before reading its value. IntroducedAt and the reply to a new member name a box by its whole MessageBoxIndex.

Rosters. Members are named by one-byte roster indexes, not public keys, to save bytes on constrained transports such as LoRa.

Sent-box records. A stream owner records, for each box it wrote and under its Idx64, its MessageBoxIndex and its plaintext until every member has acknowledged it or its retention policy deletes the plaintext (see Disappearing messages). How far each member has acknowledged the owner’s stream is the Idx64 of the last box it acknowledged.

Joining. A new member receives its introducer’s view of the group as of the Introduction, privately in the introducer’s VoucherReply: a read cap and a start index for every member’s stream in the introducer’s roster, the rosters the introducer knew about, and the Introductions it had read (see Reply to a new member). Read caps are sent unchanged; the index travels beside them and is advanced separately.

A reader cannot tell a quiet stream from one stuck behind a garbage-collected box by reading it: both return BoxIDNotFound. Nor can it tell when a missing box will read again: that happens only once its owner, who may be offline, rewrites it. So a client never scans on its own.

A reader’s acknowledgements of a stream stop just before the first box it has not read, so the owner keeps that box’s plaintext and goes on rewriting it until its Sent-box record is discarded. A scan the user asks for before then delivers it. Two members stuck behind gaps in each other’s streams resynchronise once both scan within the owners’ retention windows. A box gone for good is lost to the reader: after a scan it reads on past it, and its acknowledgements of that stream stay before it.

Disappearing messages is the feature that causes a user’s client to remove messages from the client’s state database based on a user specified message retention policy. For example, a client’s message retention policy could keep decrypted plaintext messages from other members for X number of days. Likewise policy could retain sent message plaintext for Y number of days.

The retention policy applies to content only. Control messages are kept for as long as their Sent-box records last, so a message that disappears never takes a roster change with it.

Once a client makes a message “disappear” as per this feature, then after that point in time the client can never retransmit that box. Backfill rewrites it as a tombstone instead. The tombstone in place of the box is still very useful for resyncing. A member that reaches a tombstone in place of a box it has not yet read can also tell from it that it didn’t read your message in time before your client’s retention policy purged the plaintext data.

GOOD QUESTION: If we are adding a lot of people at once,do we really need to upload all of the members n times?

OPEN PROBLEM: Our BACAP API defines a ReadCap type as containing the master public key AND the start index. Therefore whenever we send a readcap over the wire we are needlessly sending a start index even when we don’t need it anymore. We should probably fix this, especially given that our goal is to be as bandwidth efficient as possible.

FUTURE WORK: Forward secrecy. We can add two extensions that allow transmitting public keys + stuff encrypted under those public keys. We can also refer to the Reunion protocol which is a n-way PAKE with strong anonymity properties. Reunion is described in Communication in a world of pervasive surveillance: Sources and methods: Counter-strategies against pervasive surveillance architecture. Currently, Python and Go implementations of Reunion are available.