[messaging] Message order in group chat (attempt at summary)

[Ximin Luo]

On 19/04/14 16:45, Trevor Perrin wrote:
> On Sat, Apr 19, 2014 at 6:53 AM, Ximin Luo <infinity0 at pwned.gg> 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

-------------- 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/20140419/7de379c4/attachment.sig>