[messaging] Partial order group chat with partial history visibility

[Ximin Luo]

I've been exploring representing group chat history in terms of a partial order (directed acyclic graph) just like how modern version control systems represent history, in order to support asynchronous group chat (where it's better not to have a "captain"). Two years ago, way back in [1] I commented that:

> Extending [partial order] to dynamic groups is more tricky however, since one
> needs to figure out what happens when join/part operations interact
> with the partial-order.

The reason is: Merge algorithms[2] (like the ones that DVCSs have) require full history to work. However, in a private group chat we would like the semantics that people can't read what happened before they joined - so people only have partial views of history, a sub-graph of the full "underlying" graph.

This intuitively suggests that, given a set of messages X, members a and b will not reach the same result when executing the merge algorithm, using each of their own histories G_a and G_b. This is problematic obviously; being part of a "group" means having consistent ideas about the current situation.

However, for the longest time I couldn't construct any examples that actually concretely indicate this problem, to be able to study it further. Now finally I've proved that this is actually false, and the more counter-intuitive result holds, i.e.:

Merge-consistency theorem
=========================

Let G be a partial order (i.e. directed acyclic graph) that represents a "full history of events", where each node (event) v has a "set of members" U[v] - the members that can read (i.e. decrypt) that event. For any member u, define G_u as the subgraph with:

G_u.nodes = { v in G.nodes | u in U[v] }
G_u.edges = { e in G.edges | e.src, e.dst both in G_u.nodes }

This is the "partial history" that u is allowed to read (i.e. decrypt), of the full history G.

Our theorem states:

For all pairs of members a, b, and for all sets of messages X such that for all v in X : a, b both in U[v], then Merge[G_a](X) = Merge[G_b](X).

where Merge[G_u] is the merge algorithm "run against" the history graph G_u local to member u. This is the standard merge algorithm on partial orders, as used by git (and I'm sure other places) and restated in [3].

----

It will take me a while to write up this proof, but basically it involves constructing "equivalent" (in some sense) graphs to G_a, G_b that contain analogs to X, in a way that G'_a, G'_b are symmetric at certain critical parts that are relevant to Merge. Then we have that Merge[G_a](X) = Merge[G'_a](X') = Merge[G'_b](X') = Merge[G_b](X).

The consequence of this is that we can support partial visibilities of history (i.e. the "private" semantics mentioned earlier) much more easily than I had thought in the previous 2 years. Contrary to my previous posts, it is not "tricky" and in fact you don't need to do anything extra on top of just running the merge algorithm on your partial history.

(Note that the word "partial" in the phrases "partial order" and "partial history" are unrelated, in case anyone was confused by that.)

X

[1] https://moderncrypto.org/mail-archive/messaging/2014/000317.html

[2] This is possibly equivalent to a state-based CRDT, I will have to read more about that. It is *not* equivalent to an operation-based CRDT, which are more like "rebase" and not secure (in a strict sense) because they disassociate a diff away from the author's original and intended context.

[3] https://moderncrypto.org/mail-archive/messaging/2014/000356.html

-- 
GPG: ed25519/56034877E1F87C35
GPG: rsa4096/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: OpenPGP digital signature
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20160525/82f2b22f/attachment.sig>