[messaging] Minimal requirements for group chat

[Michael Rogers]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Hi all,

I've been thinking about ways to cut down the forward-secret group
chat problem to a manageable size. I'm looking for a core problem
that's big enough to be worth solving, but small enough to be solved;
then we can think up some solutions, prototype them, and see whether
we can extend them to solve bigger problems.

Here's a suggestion for a core problem we could start with:

* Small groups, so O(n^2) bandwidth or processing cost is OK
* Group membership is fixed for the duration of the chat
* All members know the membership of the group somehow
* All members have pairwise OTR connections to all other members
* We accept that any member can prevent the chat from making progress

Goals:

* Messages are forward secret
* Messages can be authenticated by group members
* Messages are repudiable
* All members agree about which messages are part of the chat
* All members agree about the order of the messages in the chat
* Messages can only be added to the end of the chat

In some ways this is an easier problem than mpOTR, but I think a tool
that met these goals would be worth having. As far as I know, that
tool doesn't exist yet.

Here's a sketch of one possible approach to solving this problem. It's
basically an append-only log with two-phase commit. Messages aren't
shown in the UI until they've been committed. (If used over a
high-latency transport there would need to be some intermediate UI
state for messages that had been sent but not yet committed.)

Each member of the group has a copy of the log and a staging area for
uncommitted messages. Messages in the log are numbered sequentially,
and each message has a retransmission counter. When a member wants to
send a message, she assigns the first unused sequence number to the
message, stages the message, and sends a copy of the numbered message
to every other member. Each member who receives the message stages it
and sends an ack to every other member, including the author. The ack
includes a hash over the author's identity, the sequence number, the
retransmission counter and the content, so everyone knows whether
everyone else is acking the same message. Each member who receives an
ack from every other member except the author commits the staged
message to the log.

If a member receives a message with the same sequence number as a
staged message, she sends a nack to every other member and discards
both messages. Anyone who receives a nack for a staged message
discards the message, except the author, who unstages the message. If
two or more authors try to send messages with the same sequence
number, every colliding message will be nacked by at least one member,
unstaged by its author and discarded by everyone else, and the
sequence number will remain unused. Each author waits for a random
interval and then resends her message with an incremented
retransmission counter and the first unused sequence number, which may
be the same as before, or higher if another message has been committed
in the meantime.

The retransmission counter prevents confusion between acks or nacks
for different transmissions of the same message. The retransmission
interval increases exponentially to avoid repeated collisions.

What do you reckon - is this a problem worth tackling, and does this
solution seem sound?

Cheers,
Michael
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iQEcBAEBCAAGBQJTTqNnAAoJEBEET9GfxSfMaRsH/1rcIdMBh2X/z07EWMcGzA2T
HenJNsz0KjrYixmUnvCRTwaHnf6QZh5OhJq8Mc8ULZLJH6rRdXP9K4YB/XDeDHqx
NuLgbtGj3lQcGgn31VPyOJiFSWBu+5qHss4/NHfH5MRR9CDydBeZY/lllDYVJDH7
mLBnjhVfJOEINcjXJfv7TY5ayG0iYLVmb0fBeTDqXi4ylHTyzAIYro5boODiutcn
RpFshVB5wXj2SpB3PVXpgAfuMAWGzhkc5XRbBBsvz7wryWyImPaKPgLxZqvwIA5H
5zpY+Hv9pJh0HvQSsMyimLKvXoE/y+gqIhaUBm3ZGHSwSYZggky2PFUxnDaSh74=
=/TKv
-----END PGP SIGNATURE-----