[messaging] Message order in group chat (attempt at summary)

Ximin Luo infinity0 at pwned.gg
Sun Apr 27 07:39:31 PDT 2014

On 26/04/14 16:39, Moxie Marlinspike wrote:
> 3) Each message is displayed with a small icon or color which indicates
> that you've seen the message it is responding to.
> 4) If you long-click the message, it'll display "In reply to..."
> That way when Alice says "I do!" in reply to what she thought was "who
> wants ice cream?", but it shows up below "Who wants to kill the
> President?" for everyone else, everyone else will immediately see that
> "I do!" is in response to a message they have not seen.

I'm not so sure about displaying messages where you haven't yet seen their parents yet. This violates causality, and the principle of delivering messages in-order.

Suppose we want to prioritise a more responsive UI, over the principle of causality. We would need to deal with the following issues:

- the "last-message-seen" pointer(s) is/are no longer transitive

Say the real transcript is O-A-B-C. A user might end up in the situation O-A ?-C - if you display C to the user, then what does your next message claim for its "last-message-seen" pointer? If A, then you ought to prevent the user from using information from C. But if C, then this makes it seem like you have seen B when you haven't.

I think this would also make an implementation harder. Your DAG algorithms would need to take into account both the loss of transitivity, and the case of missing nodes.

- we need to retroactively check that a claimed parent is correct.

How long should we wait for, before denouncing the "dangling child" as malicious, and what do we do in that situation?

An alternative proposition:

My preference (when doing linear ordering of a partial order) has been to do a topological order based on receive time. That is, display messages as soon as you can, as long as all of their parents have already been displayed, and buffer dangling messages in the meantime.

This results in different orders for each recipient, but I think this is a "lesser evil" than the other issues I mentioned - and actually many existing chat systems already have this "flaw".

By default, this would "look like" a linear order just like existing chats, so you gain the correctness benefits of a partial order without incurring the supposed UI complexity cost that other people have been afraid of.

(One can add a user-activated method to display parent-pointer annotations, for advanced users. One could even display a notice if the dangling-messages buffer is non-empty.)



-------------- 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/20140427/e69ad577/attachment.sig>

More information about the Messaging mailing list