katzenqt1 chat over Reticulum

katzenqt1 is the group chat protocol of katzenqt, hushphone, jam, frank_chat and katzenrns. It is CBOR messages of a few types, each written as one BACAP box in the writer’s own stream. A client keeps a read capability and an index for every member and reads each member’s next box; acknowledgements inside the messages tell it where others have got to. All of that logic is in a sans-IO state machine, written once per language, and the same machine runs on the Katzenpost mixnet and on a Reticulum mesh. What differs is the transport beneath it: on the mixnet the client daemon does BACAP and carries the boxes; on a mesh the transport does BACAP itself and sends the boxes of Pigeonhole protocols over Reticulum. So a new mesh client is a transport, or a transport and a state machine that matches these:

The transports written so far, one interface per language, which the state machine’s engine drives:

The interface itself: Rust transport/mod.rs, Go transport/transport.go, Python transport/base.py, Lean GroupChatKatzenqt1/Backend.lean.

The protocol’s rules, rosters, acknowledgements, backfill, numbering and rewrite, are the Group chat specification; vouchers are the Contact voucher specification.

This document gives versions 4 and 5 of the wire format. Version 5 is version 4 with one more message type, packed texts. Readers accept version 3 as well, whose encodings are at the end. A client has one setting, the wire version it writes, 3, 4 or 5 (default 5): it chooses the encoding of the messages and ReplyWho the client writes and the voucher form it mints, compact under 4 and 5. Answering someone else’s voucher always follows that voucher’s form. A group can mix members writing any of these versions; a reader of version 4 cannot show packed texts.

Model

• A member is a BACAP stream that it alone writes. Its key is the first 32 bytes of its read capability.
• A group is a set of members. Reading the group is reading every member’s stream from the position given for it.
• Membership changes are Introductions written in members’ streams. Every box carries its writer’s membership hash.
• A newcomer joins through a voucher that a member answers.
• The mesh has no copy command: every box is written directly, in the order given here.

What the state machine asks of the transport

Vouchers

The newcomer:

1. Makes a stream S and a seal keypair (sk, pk).
2. Signs [S’s read capability, pk, display name], as CBOR, with S’s root key (Ed25519), and builds VoucherPayload [S’s read capability, pk, display name, signature]. voucher = BLAKE2b-256 of its bytes.
3. Writes the VoucherPayload to box 0, at the smallest allowed box size that holds it, 1549 on a mesh. Gives the voucher away.
4. Reads box 1, then each next box while the one before began with C. NOT_FOUND: wait. TOMBSTONE: withdrawn, the join failed. The boxes’ bytes after their first byte, joined, are the sealed reply: open with sk, giving VoucherReply [WhoReply, salt].
5. Mutates S’s write capability KDF state by the salt and writes the group there from its first index. WhoReply is a ReplyWho: reads each member from the position it gives.

A member answering the voucher:

1. Derives the voucher stream and reads box 0. NOT_FOUND: wait. TOMBSTONE: withdrawn.
2. Checks BLAKE2b-256(payload) = voucher, and the signature under the root key in the payload’s read capability. Otherwise stops.
3. Draws a 32 byte salt. The newcomer’s live read capability is the payload’s read capability with its KDF state mutated by the salt. Builds the ReplyWho: every member with the position the newcomer starts from, its own stream at the index its Introduction will occupy.
4. Writes Introduction [display name, live read capability] to its own stream at that index, ahead of anything queued.
5. Seals VoucherReply [WhoReply, salt] to pk, cuts the sealed bytes into pieces of the box size less one, and writes them from box 1 on, each behind C, the last behind F, each until a replica holds it. ALREADY_EXISTS on box 1: another member answered; stop.
6. Reads the newcomer at the live read capability from its first index.

A member answers one voucher at a time. Box 0 is left as written; the voucher is spent once box 1 exists. A payload in the version 3 form, a CBOR map, is answered wholly in version 3: the map form of the ReplyWho, sealed with the MKEM, unframed, in box 1 alone.

ReplyWho

A CBOR array of one to five elements; trailing Nones are left out.

struct ReplyWho(
    /// One per place: `None` for a member the sender cannot name.
    Vec<Option<PleaseAdd>>,
    /// One per place, the member's roster; `None` while unknown.
    Option<Vec<Option<Vec<RosterEntry>>>>,
    Option<Vec<IntroAt>>,
    /// The sender's place.
    Option<usize>,
    /// The newcomer's place: the number of places.
    Option<usize>,
);
struct PleaseAdd(String, [u8; 136]);        // [display_name of 1 to 30 characters, read_cap]: key, then the start index
struct RosterEntry(usize, Option<usize>);   // [roster index, place]
struct IntroAt(usize, [u8; 104], usize);    // [by, index, member]

A reply is refused when a place’s name is empty or longer than 30 characters or its read capability is not 136 bytes. Without rosters, the newcomer takes the places named, the first as introducer, every roster unknown. With rosters, the reply is refused when the newcomer’s place is not the number of places, the introducer’s is not below it, there are 256 places or more, two places share a key, a roster names a place that does not exist, or the introducer’s place is None.

A pigeonhole service that admits a client answers with one place and no rosters.

Boxes

A message fits the box size less one byte. A reader that does not fetch chunks steps past an I box.

GroupChatMessage, a CBOR array of four to seven elements; trailing Nones are left out:

struct GroupChatMessage(
    u64,                 // version: 4 or 5
    [u8; 32],            // membership_hash
    u64,                 // msg_type, below
    Body,                // the type's payload; None for control
    Option<Vec<u8>>,     // acks, layout under Encoding
    Option<Vec<u8>>,     // numbers, layout under Encoding
    Option<Vec<u8>>,     // introduced_at, layout under Encoding
);
enum Body {
    Text(String),                                   // type 0
    Introduction(String, [u8; 136]),                // type 1: [display_name, read_cap]
    FileUpload(Vec<u8>, String, String),            // type 2: [payload, filetype, basename]
    Who(Value), ReplyWho(Value), Tally(Value),      // types 3, 4, 5 to 9: as the app defines
    None,                                           // types 10 and 11
    Packed(Vec<String>),                            // type 12, version 5
}

Any message may carry acks, numbers and introduced_at. A ping is content with no body: its readers play their ping sound and show that the sender pinged, instead of a line of text.

A packed box holds several texts in the order they were sent, and reads as that many messages.

A reader refuses a message of a version above its own, of a type above 12, or of type 12 in a version below 5; a reader built for version 4 therefore refuses a packed box, with the texts and acknowledgements in it. When a refused message is in the array form and its first three elements are a version, a byte string and a type, the client tells the user who sent it, its type and its version, and that the app needs updating, rather than dropping it silently.

membership_hash = SHA-256(KP:membership:v1 ‖ the members’ keys, each once, in byte order, one’s own included). The sentinel for an unknown membership is 32 zero bytes; readers also accept TODO repeated to 32 bytes. Content carries the hash as written; control messages and Introductions carry the writer’s current membership, or the sentinel.

Geometry

B is the box size of Pigeonhole protocols over Reticulum. A member’s box holds B − 1 bytes of GroupChatMessage CBOR; each box of a sealed reply holds B − 1 bytes of it. The costs below are measured on the encoders. h is a string’s CBOR header: 1, 2 or 3 bytes below 24, 256 and 65536 bytes.

Version 3 cost 70 for the fixed fields, 5 + h + n for a text, 174 + h + n for an introduction, 451 + h + n for a VoucherPayload and 359 for the seal, so version 4 saves 33 bytes on every box, 35 on an introduction, 84 on a voucher and 146 on its reply. With B = 1000: a text is at most 959 bytes; a control message acknowledges up to 117 members; a sealed reply that fits box 1 alone holds a WhoReply of 786 bytes, five places without rosters or three with; a larger reply continues in box 2 and on. With B = 256, the mesh size: a text is at most 216 bytes, and a sealed reply always spans several boxes.

Reading

• Each member’s stream from the position given: a box or a tombstone advances, NOT_FOUND waits with the backoff.
• On a replica that serves push, a NOT_FOUND also subscribes to that box, and the stream waits for the push instead, reading again every 5 minutes in case the push was lost.
• acks, numbers and introduced_at let a reader jump and backfill, as the state machine does.
• Replicas keep a box for one to two weeks; older boxes are recovered only through acknowledgements.

Sending

• A text sent while the box before it still waits to be written goes into that box, as a packed box, as long as the texts fit the box size. Only a client writing version 5 packs.
• What a member has read is acknowledged in its next message. When it has sent nothing 30 seconds after reading something, a control message carries the acknowledgements alone.
• A box that carries no content, such as a control message, is not acknowledged on its own, so receipts do not answer receipts.

Vectors

In katzenpost/pigeonhole_protocols: testdata/katzenqt1/groupchat_wire_vectors_v5.json and groupchat_wire_vectors_v4.json (messages, written boxes, membership hashes, replies, refused arrays) for versions 5 and 4, testdata/katzenqt1/groupchat_wire_vectors.json for version 3, and testdata/katzenqt1/acks_vectors.json. Voucher vectors are voucher/testdata/voucher_vectors_v2.json in katzenpost/hpqc, beside the version 3 file; BACAP vectors are in the same repository. katzenrns is a client of this protocol on meshes: match the above, not its storage or interface. pigeonhole_protocols main writes version 5. The compact voucher form is on the branch katzenqt1-v4 of hpqc (hpqc#154, not merged), which the Go module of pigeonhole_protocols pins; the deployed version 3 is the branch katzenqt1-v3 of hpqc, cryptlib, group_chat_client, katzenqt and katzenrns.

Encoding

Byte fields are CBOR byte strings; names are text strings; integers are unsigned.

Acks

Empty when nothing is acknowledged. Otherwise:

• one byte, the number of members acknowledged, less one,
• the members by roster index, ascending: a list of one byte each when no longer than the bitmap, else a bitmap, most significant bit first, as many bytes as the highest index needs,
• one 8 byte little endian counter per member, same order: the counter of the acknowledged box.

A naming as long as the count is a list, shorter is a bitmap. Refused: a list out of order, a bitmap ending in a zero byte, a bitmap naming other than the count.

Numbers

• one byte, the first roster index assigned,
• one 8 byte key prefix per member numbered, consecutive indexes.

A single byte is the roster index of the member the same message’s Introduction introduces. Refused when the indexes would pass 255 or a prefix repeats.

IntroducedAt

• one byte, the introducer’s roster index in the sender’s roster,
• the 104 byte index of the Introduction in the introducer’s stream.

Voucher stream

• VoucherPayload, box 0: array [read_cap 136 bytes, seal public key 160 bytes, display_name, signature 64 bytes]; the signature is Ed25519 by the read cap’s root key over the CBOR array of the first three.
• Voucher: BLAKE2b-256 of the VoucherPayload’s bytes.
• VoucherReply: array [WhoReply, the ReplyWho’s CBOR; salt 32 bytes]. Sealed as a sealed box to the seal public key: the sender’s ephemeral hybrid public key, 160 bytes, then XSalsa20-Poly1305 of the plaintext under a key and nonce derived from the shared secret, as hpqc’s sealedbox defines, with the NIKE named CTIDH1024-X25519.
• Boxes 1 on: the sealed bytes in pieces of B − 1, each behind one byte, C for a piece that continues, F for the last.

Version 3

Readers accept these as well; a version 3 message is a CBOR map, a version 4 one an array, which the first byte tells apart.

GroupChatMessage: map version 3, membership_hash, msg_type, then the type’s field under its name, text, introduction (map display_name, read_cap), file_upload (map payload, filetype, basename), who, reply_who, tally, and optional acks, numbers, introduced_at. A map without msg_type has the type of the field it carries, text when none.

ReplyWho: map please_adds (array of map display_name, read_cap, or null), rosters, introductions, introducer, newcomer, the last four absent when unknown.

Vouchers: PleaseAdd is map DisplayName, MessageReadCap; SignedPleaseAdd map PleaseAdd (its CBOR), Signature (64 bytes, Ed25519 by the stream’s root key over the PleaseAdd bytes); VoucherPayload map SignedPleaseAdd (its CBOR), VoucherPubKey; all canonical CBOR. VoucherReply is map WhoReply, VoucherSalt, sealed with hpqc’s MKEM to the seal public key and written unframed to box 1 alone. A member answers a version 3 payload in this form, with the map form of the ReplyWho inside.