[messaging] Minimal requirements for group chat

[Ximin Luo]

On 16/04/14 19:34, Michael Rogers wrote:
> On 16/04/14 16:36, Michael Rogers wrote:
>> 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.
> 
> A more efficient way to handle collisions: define some transitive way
> to choose between two messages with the same sequence number (e.g.
> hash the sequence number with the author's identity and sort by hash,
> so each author takes precedence some of the time).
> 
> When a member receives a message with sequence number i, where i > the
> highest committed sequence number, she tries to stage the message in
> slot i. If the slot is empty, she stages the message and sends an ack
> to every other member. Otherwise she compares the new message with the
> staged message. If the old message wins, she increments the new
> message's sequence number and tries to stage it in slot i+1. If the
> new message wins, she stages the new message in slot i, sends an ack
> to every other member, increments the old message's sequence number
> and tries to stage it in slot i+1.
> 
> This variant doesn't require retransmissions or nacks. A message may
> be acked by some but not all of the members in one or more rounds
> before it's finally acked by everyone in the same round and committed.
> 

There are consistency issues, when you allow a message to be taken out-of-context by other members - i.e. when you allow message M to be placed strictly after message M0, when the sender of M had not seen M0 at the time of sending. This something that partial-ordering would automatically protect against.

In your example "if the new message wins, she stages the new message in slot i, sends an ack to every other member". So what happens to the old message? Its sequence number has now increased from Alice's perspective, but nobody else knows about this? Everyone still has her previous ack (old message at sequence i). OTOH, if you re-ack the old message with the new sequence number, acks are no longer binding - there is always the possibility that "someone has a higher sequence number".

The severity of this may not seem quite obvious, so I'd understand if people don't want to work on this problem. (The reason why I don't spend time developing more specific attacks, is because I believe I already have a defense.)

There's also the issue of latency. If you wait until a message is acked, to display it, then you would be at-least-doubling the latency for every message, and much more in the case of conflicts (which are very likely, with increasing members). However, if you want to display the message immediately upon receipt, you would need to accept the possibility that they may need to be re-ordered and re-drawn later.

Granted, this is a problem for the partial-order scheme I'm doing atm. Instead of re-ordering messages, I have flags that point to the real parents of a message. Which is not the most simple, but at least it retains correctness. (I imagine it'll look something like "Bob: hi there! [1] [2]" where [1] [2] are rollovers.)

X

-- 
GPG: 4096R/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 880 bytes
Desc: OpenPGP digital signature
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140416/cdfd7d36/attachment.sig>