[messaging] Matrix.org: Decentralized group chat

[Ximin Luo]

On 10/03/15 19:36, Jeff Burdges wrote:
> On 10 Mar 2015, at 17:08, Ximin Luo <infinity0 at pwned.gg> wrote:
>> Merge the unordered set of members. 
>>
>> In the following diagrams, the node labels (e.g. "bd") represent the set of members ("b", "d") at a given message/node/event. Someone wants to merge the blue nodes, which are the same message in both diagrams. Black edges are 1-parent messages, grey edges represent merge messages that don't include a further membership operation. (If it is unrealistic to imagine membership operations taking only one event to complete, then instead imagine extra messages in between the nodes.)
>>
>> From b's point of view, they have full visibility of the history, and can execute the merge as normal:
>>
>> https://people.torproject.org/~infinity0/res/mcrypt/partial-vis-1.png [1]
>>
>> But when d executes the merge, they have an incomplete view of history, giving a different result:
>>
>> https://people.torproject.org/~infinity0/res/mcrypt/partial-vis-0.png [0]
>>
>> The problem is to resolve this difference, somehow. I suspect it's impossible in the general case; the "solution" I had been playing with is (roughly) to detect "impossible" conditions and wait until it is possible.
>>
>> I agree with the rest of what you said, and have implemented it in a prototype.
> 
> 
> You’re aren’t *only* merging an unordered set of members though, even if the issue is visible at that level, because you’ve some ambient application that imposes some semantics on the merge operations.  
> 

I created the scenario, I define the semantics. :p There's no other application that runs on top of "private group chat". Each message/event stands by itself and we never try to merge "two messages", only their membership (visibility) sets. Collaborative applications by contrast don't treat an event as a "message" but some sort of operation on the "shared state". That's a separate problem outside of the scope of this scenario.

> 
> There are three separate conversations from b’s perspective before the blue nodes, and a, c, and d only know about the ones they’re involved in, so some action by b precipitated the merges that occur in the blue nodes.  
> 

No, it's the same conversation. Different membership were initiated by different people at different times. (Possibly I didn't explicitly define enough members to be able do these concurrent operations, but you can just imagine an extra constant set of members "xyz" at each node doing these operations, which are the black edges labelled +a etc.)

> Said differently, what do your grey arrows from the blue nodes to the bd grey node mean?  You didn’t label them like you labeled the black arrow between grey nodes.
> 

I tried to explain the difference between grey/black arrows in the previous email. Was the wording unclear?

> 
> If we interpret your diagrams as connectivity difficulties rather than intentional privacy operations then we observe that b should be happy with whatever merges can be accomplished.  I’ll therefore interpret all the +/- arrows an intentional operations by the users. 
> 

Yes, they are intentional logical (cryptographically-enforced) operations. Connectivity difficulties are not directly relevant on this layer, IMNSHO it's up to the transport layer to fix those.

> 
> A priori, I’d expect b added d to both the ab and bc conversations to make the blue nodes, as b adding a and c to the bd conversation has a different semantics, so..  
> 

Ah, I missed this out: the "+a" and "-d" etc are *inferred* from the membership-set at the parent vs child nodes - each message/node has a known, unique and well-defined membership-set. This avoids transmitting redundant information, which complicates verification.

> Those arrows could hypothesize that d’s client mysteriously detected the common history back to b’s first message to merge these separate branches.  How?  Why?  Isn’t that already a violation of users not seeing previous history?  I guess this isn’t the situation. 
> 
> Yeah, if b set a unique thread id way back in the beginning, then obviously d’s client might merge the two threads in that way, but that’s loony since b already split the thread.  And such a thread id dictates that d’s merge is correct anyways. 
> 

I don't understand what you're saying here - but there is no "split" in the thread. It is just people inviting/kicking others at the same time and temporarily not seeing each others' actions.

> 
> Instead, those blue nodes with two parents must represent b executing conscious merge operations, yes?  
> 

The blue nodes are the parents that we are trying to merge. In both diagrams, b and d have the blue nodes in their view as their "latest messages". If b tries the merge (from his view of history), he gets bd, but if d tries the merge (from his view of history) he gets abcd. (The merge operation is well-defined, it would take me a long time to explain; but intuitively you just "apply" all the operations from the black edges).

One observation is that d mis-infers some merge edges to be "membership operation" edges, because some other parents (of the blue nodes) are not visible. Maybe this fact could help to work towards a solution.

> We might for-example have a private shared git-like system where the blue nodes represent two new branches along with an assertion that they should both supersede the bd grey branch.  In this case, the green node represents another conscious merge operation by d, which screws up b because b failed to warn d to keep the branches separate.  Meh, not surprising.  Op sec is hard. 
> 
> We should not imho worry about anonymizing distributed version control like this.  If an application like git benefits significantly from shared history then share the required history, including the user’s social graph when necessary.  Any users who require more privacy can pass through snapshots or even use diff & patch manually. 
> 

Yes, I agreed with this from my very first post :p ("For a private dynamic group chat, the merging requirements are not exactly the same as in a collaborative environment.") However I do not rule out the *possibility* that maybe in the future we could have private and dynamic collaborative applications, in which case yes they would indeed need to merge extra things on top of membership sets. At this moment in time however, I'm satisfied to keep them apart - it's not clear what private collaboration really means or whether it satisfies a real-world need.

X

-- 
GPG: 4096R/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git