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

[Trevor Perrin]

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.


> 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