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

Michael Rogers michael at briarproject.org
Sun Apr 20 09:49:18 PDT 2014

Hash: SHA256

On 19/04/14 00:54, Trevor Perrin wrote:
> Aren't those algorithms more general than we need?  I think
> they're designed to track causal order when messages can be
> exchanged between individual entities.  But we're looking at chat
> protocols where every message is broadcast to the entire chat.
> In this case, I think it's sufficient for each message to declare
> its immediate predecessors (Ximin first pointed this out to me).

If we're aiming to support linear conversations rather than threaded
conversations, we may need even less information than that. We can
model a linear conversation as a series of instants, with one or more
messages per instant; messages that occur in the same instant are
considered simultaneous. (There are no empty instants - each instant
lasts until somebody speaks.)

To display such a conversation, we need some way to indicate that A
follows B, and some way to indicate that A and B are simultaneous. We
don't need threads or nesting. If we use Tom's side-by-side display,
we don't need the second, more complex diagram; the first diagram
(possibly with more than two messages side-by-side) is all we need.

To represent such a conversation at the protocol layer we can either
use pointers (i.e. hashes) or counters. If we use pointers, each
message points to the latest message displayed by its sender, where
the latest message is the one with the longest chain of predecessor
pointers back to the root. Messages with predecessor chains of the
same length are simultaneous. Messages that point to not-yet-received
messages have arrived early and aren't displayed yet.

If we use counters, we don't need vector clocks - a Lamport clock is
sufficient. The first message has timestamp 0, and each subsequent
message has a timestamp one greater than the highest timestamp
displayed by its sender. Messages with the same timestamp are
simultaneous. Messages with timestamps more than one greater than the
highest timestamp displayed so far have arrived early and aren't
displayed yet.

Both these representations allow an attacker to insert messages into
the past, but those messages will be shown as simultaneous with other
messages - it isn't possible to insert a message between two existing
messages, or between an existing message and an anticipated message,
without a collision being displayed. Maybe that's sufficient to
prevent the ice cream attack... I guess it depends on how people
interpret collisions.

Version: GnuPG v1.4.12 (GNU/Linux)


More information about the Messaging mailing list