[messaging] Minimal requirements for group chat

[Ximin Luo]

On 17/04/14 22:23, Ben Laurie wrote:
> On 17 April 2014 22:13, Tony Arcieri <bascule at gmail.com> wrote:
>> On Thu, Apr 17, 2014 at 2:07 PM, Joseph Bonneau <jbonneau at gmail.com> wrote:
>>>
>>>  We could design a chat protocol where every participant has a Lamport
>>> clock and these are committed to in each message as an alternative to the
>>> "git commit history" formulation considered above.
>>
>>
>> I was actually thinking about proposing exactly this when I saw Moxie's
>> original description, but I began to worry about the details, like:
>>
>> - If someone joins a conversation later, who do they inherit their vector
>> clocks from? Someone who invited them to the conversation?
> 
> When someone joins a conversation, its actually a new conversation, so
> everyone starts again.
> 

This sounds like strategy (a) I mentioned in [1], and is conceptually straightforward. However, it's incapable of independent parallel join/part operations (ignoring for now whether that's an important thing to support).

[1] <534FD8CC.40103 at pwned.gg> http://moderncrypto.org/mail-archive/messaging/2014/000317.html

Strategy (b) would store everything in the same transcript, as hinted at by Tony's post. Using the analogy of a git history DAG, each commit now has a set of recipients. Each parent pointer, is only visible to a recipient, if they are also a recipient (or the sender) of the dereferenced parent message. The consequence is that each user now only sees a subgraph of the entire DAG.

I'm not sure this can be translated directly into a vector clock model, but one can do it with a tweak. Instead of sequence numbers, you have message ids (where each message's id is determined by its contents). The vector clock within that message, contains the id of the previous message from the same sender, so we can still work out the chain of ids, though this takes more effort than simply counting the sequence of integers in the standard vector clock model. (I think ids provide better verifiability, though.)

When a new invitee M joins, its vector clock just says "NULL" for existing members for whom M hasn't seen any messages yet. This is, I believe, is equivalent to the DAG-with-recipients model above. For now I'll hand-wave over a more precise proof :p, but feel free to follow-up on this.

Talking more about strategy (b), today I convinced myself that it's not achievable using a GKE (which I define as any process that lets you derive a k for member-set M from an older k' for set M' <= M). This is the case, even if you allow the GKE to do some powerful, potentially impossible, things, e.g. it can use some information from partial/causal ordering, and/or proceed with not-all members' participation.

TL;DR: it seems impossible (at least, harder than I care to explore) to have dynamic group membership, a group-based key exchange, *and* support parallel join/part operations. I don't have a formal proof, but a hand-wavy argument that still, I should write up at some point.

OTOH, said strategy (b) does appear to be possible for a pairwise keying scheme, so I'll be exploring this in a bit more detail.

>> - What about siblings? (same problem as git)
> 
> Siblings appear in different orders for different people.
> 
>> - Could this actually result in confusing/deceptive output?
> 
> Yes. :-)

Does the following look confusing?

Alice: Who can tell me about ZKP?
Bob: Not me...
Carol: Me [2]
Dave: I thought you knew! [2]
Alice: excellent, only one person is enough [1, 2]

When you hover over a message, it highlights all the messages at index -i, -j, ... relative to that message. If there is no [*] displayed, this by default means [-1], like a normal linear order.

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/20140418/c49e8af9/attachment.sig>