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

[Ximin Luo]

On 19/04/14 00:54, Trevor Perrin wrote:
> On Fri, Apr 18, 2014 at 2:32 PM, Alexandre Carmel-Veilleux
> <acv at miniguru.ca> wrote:
>>
>> On Fri, Apr 18, 2014 at 5:07 PM, Tony Arcieri <bascule at gmail.com> wrote:
>>>
>>> On Fri, Apr 18, 2014 at 1:42 PM, Trevor Perrin <trevp at trevp.net> wrote:
>>>>
>>>>  (1) It seems feasible to put messages into a causal/partial order by
>>>> having them piggyback references and hashes to their parents (aka
>>>> "causal predecessors").
>>>
>>>
>>> I think that vector clocks (which wouldn't necessarily refer to previous
>>> messages, perhaps just message counts since joining a conversation) are the
>>> best bet at getting a realistic *partial* (not total) ordering of events
>>
>>
>> And Interval Tree Clocks should be able to handle join and parts as well.
> 
> 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.
> 

AIUI, when using ITC, one would encode the member-set in terms of join/part events. This can get a bit inefficient, as well as perhaps leaking information about who was previously in the chat (everyone sees all events). In an adversarial setting, this redundant information also forces you to add extra checks - i.e. that the "event component" never has elements removed.

The scheme I have in mind implicitly works out the partial-order of operations, from the explicit list of members (sender+recipients) at each message, which is correct by definition so you don't need to do extra checks. It's basically like a VCS merge, except because it works on unordered sets, there are never any merge conflicts.

> In this case, I think it's sufficient for each message to declare its
> immediate predecessors (Ximin first pointed this out to me).
> 
> There might be advantages to piggybacking information about the
> complete set of predecessors, however.  That way, a recipient who
> receives a message before all its predecessors have arrived knows the
> entirety of what it's waiting for and could indicate missing messages
> in the GUI, or request retransmission.
> 
> If we assume the message-stream from one participant to another is
> ordered, conveying the complete set of predecessors could be
> accomplished by piggybacking a vector of messages counts from each
> participant.
> 

The point above about checking redundant information applies here too, and is why I favour the sparse form. For example, using the syntax id{author}:

A{p} <-- B{p} <-- C{q} <-- D{r}

In D, r could falsely declare their vector-clock to be {p: A, q: C}. The severity of any attacks depends on what you actually do with this unverified information (and granted, I can't think of any horrible attacks right now), but it seems prudent to actually check the indirect predecessors when one receives the missing parts. In the sparse form, declaring direct predecessors is correct by definition (with a few caveats not relevant here), so you don't need those extra checks.

> ---
> 
> To handle "join" and "part" events, I think we can assume these
> actions are represented as messages which operate on the "member-set"
> each participant recognizes.  The question Ximin has thought about
> earlier is how to handle "merging" partially-ordered changes to the
> member-set
> 
> I don't know if we have a good answer to that yet, but it seems like a
> good question.
> 

I have an algorithm (with source code and a few test cases) for this, plus a semi-formal argument on why it works, and also why it's the unique solution. It would be good to formalise it. It's probably a little too technical to post here but I can explain it in more detail next time we meet. (For those interested, I did post a technical description of an incorrect version of the algorithm a while back; I've fixed it with a slight tweak.)

The open problem is how you use this information to actually get the new members into the session securely. The hard part is that in a merge, the parents themselves may have different member-sets to start any key-exchange processes from (which is why I think GKEs can't handle this scenario).

An alternative direction (also discussed earlier) is not do join/part operations in the partial-order at all, but outside of it as a synchronized step between all members.

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/20140419/f8014d88/attachment.sig>