-----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" <[email protected] > <mailto:[email protected]>> 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 [email protected] >> <mailto:[email protected]> >> https://moderncrypto.org/mailman/listinfo/messaging >> >> > > -- http://www.thoughtcrime.org > _______________________________________________ Messaging mailing > list [email protected] > <mailto:[email protected]> > https://moderncrypto.org/mailman/listinfo/messaging > > > > _______________________________________________ Messaging mailing > list [email protected] > 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----- _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
