[messaging] Minimal requirements for group chat

Wed Apr 16 15:19:38 PDT 2014

A git-like scheme with an elected master could make the transcript totally
ordered. Basically, all the peers would receive the messages and still keep
them in an unstaged area, partially ordered so still useful for the UI.
Then the master would chime in and provide the definite  message order,
kind of like a merge in git. The peers then reorder their transcript
accordingly.

If you do not trust the master, it is not a problem: he is only in charge
of the transcript, and clients would verify that what he broadcasts is
alright (example: messages include the "current commit" hash). Once a peer
detects the master is malicious, a new election could be called.
Le 16 avr. 2014 22:58, "Moxie Marlinspike" <moxie at thoughtcrime.org> a écrit
:

>
> TextSecure supports group messaging.  I've been meaning to write up a
> blog post about it, but if I understand correctly, you're mostly asking
> about transcript consistency in a "pairwise group" model.
>
> We believe this can be as simple as including the truncated hash of the
> (sender, plaintext, counter) tuple for the last messages seen with every
> message sent.
>
> This allows each client to build a view of a message transcript that's
> reminiscent of a git commit log, where each message is a commit.  One
> could imagine visualizing this like an old-school email client
> visualizes conversation threads, which would make transcript
> inconsistencies and "reply intent" clear.  That way if Bob sends a
> message to everyone that says "Who wants to kill the president?" except
> Alice, who Bob instead sends "Who wants to get some ice cream?," when
> Alice responds "I do, how about this afternoon!" -- it'd be clear to
> everyone in the conversation that Alice is responding to something they
> didn't see.
>
> Unfortunately, that type of UI isn't really possible on mobile devices,
> and even desktop communication apps are moving away from those types of
> threaded views.  For now, TextSecure conversations are "linearized," and
> the way to *display* transcript consistency for untrusted groups like
> these remains an open UI/UX question for us.
>
> But at least at the protocol level, it's pretty simple even in an
> asynchronous environment.
>
> - moxie
>
>
> On 04/16/2014 08:36 AM, Michael Rogers wrote:
> > -----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-----
> > _______________________________________________
> > Messaging mailing list
> > Messaging at moderncrypto.org
> > https://moderncrypto.org/mailman/listinfo/messaging
> >
> >
>
> --
> http://www.thoughtcrime.org
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140417/42227439/attachment.html>