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
signature.asc
Description: OpenPGP digital signature
_______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
