On 19/04/14 16:45, Trevor Perrin wrote: > On Sat, Apr 19, 2014 at 6:53 AM, Ximin Luo <[email protected]> wrote: >> On 19/04/14 00:54, Trevor Perrin wrote: >>> >>> 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 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. > > Thinking more: if a group chat allows member-add but not > member-delete, then this is is easy, right? The merged member-set is > just the union of the parent member-sets? > > With delete, there's not a perfect solution: what if one parent branch > adds Bob, and another adds Bob, then deletes him? Since these > branches aren't ordered, I think it's ambiguous whether the merge > should contain Bob or not. >
I'd argue the correct merge is that it should contain Bob. Perhaps I'm biased in my assessment, since this is what my algorithm does :p My reasoning is that when you merge, you want to incorporate changes in both branches. The branch that add-then-deletes Bob effectively makes no changes. A more formal justification is that, for a parent P of a merge M, we want the diff(P to M) to represent all operations (i.e. edges) made by ancestors(M) - ancestors(P). FWIW, git agrees with me: $ git init test && cd test Initialized empty Git repository in /home/infinity0/tmp/.git/ $ echo "Alice" >> members.txt $ git add members.txt && git commit -m "start conversation" [master (root-commit) e66e62f] start conversation 1 file changed, 1 insertion(+) create mode 100644 members.txt $ git branch other-branch # will branch from here later $ echo "Bob" >> members.txt $ git add members.txt && git commit -m "join Bob" [master 86d18ee] join Bob 1 file changed, 1 insertion(+) $ echo "Alice" > members.txt $ git add members.txt && git commit -m "part Bob" [master 50e5e40] part Bob 1 file changed, 1 deletion(-) $ git checkout other-branch Switched to branch 'other-branch' $ echo "Bob" >> members.txt $ git add members.txt && git commit -m "join Bob" [other-branch 891ff65] join Bob 1 file changed, 1 insertion(+) $ git merge master Already up-to-date! Merge made by the 'recursive' strategy. $ cat members.txt Alice Bob >> 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). > > Agreed that pairwise key agreement (instead of group key agreement) > makes this simpler. > > FWIW, this is the road TextSecure is going down - group chat is a > notion layered on top of pairwise communication between participants, > and deleting members from a group chat requires creating a new one. > Hopefully this will make the "transcript consistency" problem > tractable. > > > Trevor > -- GPG: 4096R/1318EFAC5FBBDBCE git://github.com/infinity0/pubkeys.git
signature.asc
Description: OpenPGP digital signature
_______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
