[messaging] Minimal requirements for group chat

[Michael Rogers]

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

If the master isn't trusted then the other members need to check that
the master has given them the same transcript - so I think this just
shifts the problem from achieving consensus about the order to
achieving consensus about what order the master chose.

In either case, I think you're right that we need a broadcast
primitive so that inconsistent behaviour can be detected (though not
proven, since we're aiming for repudiability). We can build broadcast
on top of pairwise connections, but it's expensive: O(n^2)
transmissions to ensure a piece of information reaches every member.

Cheers,
Michael

On 16/04/14 23:19, Geoffroy Couprie wrote:
> 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 
> <mailto: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: 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
>> _______________________________________________ Messaging mailing
>> list Messaging at moderncrypto.org
>> <mailto:Messaging at moderncrypto.org> 
>> https://moderncrypto.org/mailman/listinfo/messaging
>> 
>> 
> 
> -- http://www.thoughtcrime.org 
> _______________________________________________ Messaging mailing
> list Messaging at moderncrypto.org
> <mailto:Messaging at moderncrypto.org> 
> https://moderncrypto.org/mailman/listinfo/messaging
> 
> 
> 
> _______________________________________________ Messaging mailing
> list Messaging at moderncrypto.org 
> https://moderncrypto.org/mailman/listinfo/messaging
> 
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iQEcBAEBCAAGBQJTT6/3AAoJEBEET9GfxSfM12MIALqM1RMHiRlBJPDu6Jvck6AQ
a5ww8e7/6i8urTIAC8D6sER2JPYC149RWmriG+sPRLKLlfUAa5OMBrgPcmKSCpao
TDV7adkMU7NVBnEYd1NHP9DrWX3IC09iLZ5hotB9Tj0FLkzprdMwLwiVSmwrVGev
/jPhPR2m2uFURs7wc9gp/wvEGjX+Ts3iRW0T2Ke7Iq/DvMbPGdk682RGPdcSzS9t
fEbnW2Ae8907UG3aTZhVFfign/zKf16PmK4FJRnrkysjIidizqVehCdChk/jjEPl
vI+Q4jMvlcLmbkgwGegSUBGsTQE2dTJWvs1yc9e0bJcC70Vmx4SYsOILpijTW7w=
=vz0d
-----END PGP SIGNATURE-----