-----BEGIN PGP SIGNED MESSAGE----- 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. Cheers, Michael -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) iQEcBAEBCAAGBQJTU/qOAAoJEBEET9GfxSfM1AcIAMUcLCqRCX9L+UHD6oPvAN+q mMa76xN1Sr3d3qFyinRP5mV+kr7U/dahh99PnWBcJoiiUXq/JbJsFxhsx6sx2vgR KbLMNHvcLHtMF8dvGJR8GzjxE3J3fmzdLvmppAKne4tlVm1hLDaRoiKDQYN8xhK4 uZlRIRXHZd54hJgS6Z7j7W19WKQSvzRjfckkpYrzWWl/9lCOMhyXnwsLq/hAyswS l2oT5cS3z/kOxl0T02IayBO8kKsgC7Pu71XBCF1FOVsg3KqqYGwxe57DpjJwtu7U zacm6M7IPRFoi4qQYIXh/XH8eJXU/XeeupiO5+HzBieDNci4+Li6h9L7ajLcooE= =YCZZ -----END PGP SIGNATURE----- _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
