[messaging] Merging partially-ordered membership operations was Re: Message order in group chat (attempt at summary)

[Ximin Luo]

On 21/04/14 16:22, Trevor Perrin wrote:
> On Mon, Apr 21, 2014 at 6:24 AM, Ximin Luo <infinity0 at pwned.gg> wrote:
>>
>> I think this does work, but I see a few issues. It leaks some information about previous members in the session - I don't think the garbage-collection would be enough to hide this.
> 
> Wouldn't you need to send new joiners some history in both approaches?
>  (Either they need M and D, or they need enough of the graph to
> compute your "latest common ancestors").
> 

I *think* I can get around this, though my current mental justification for this is not very satisfactory, so apologies in advance for some very imprecise arguments:

In the idea I have, a user performs the normal merge on their subjective view of the graph, which may miss out some edges and past history. In this case, their calculation of the LCA may differ from others'. However, the algorithm itself is still well-defined, from the perspective of each user.

The algorithm will generate new correct-by-definition info, from old correct-by-definition info (the member-set at each message). The difference, then, is how other users *interpret* what they just did.

Say we have two branches with different memberships. Bob who sees both branches does a merge message. Then to him (and others with similar vision), the message will look like a normal "neutral" merge commit, i.e. one that follows the merge algorithm. But Alice, who only sees one branch, will interpret the message as Bob adding/removing a bunch of other people to the conversation. I believe this is intuitive - if we are not aware of a parallel conversation, then we will see the entity doing the merge as responsible for any changes that occurred outside of our knowledge.

(However, it may not play nicely with the case where there is a policy restricting membership operations. I am ignoring this feature for now.)

By contrast, in the M/D scheme (without alerts), Carol (from the example in my previous email) generates new incorrect-redundant info, by trusting old malicious redundant info she was unable to verify. Other people then use this new incorrect info, to do things (the incorrect merge A,G -> H) that is *different* from the case if all the redundant info had been correct.

Again, I apologise for the imprecise arguments and I will work on making these more precise.

> 
>> Here is the pseudocode with type annotations, but it will take me a lot longer to write up the justification:
> 
> I have trouble following this.  I guess you're doing some "recursive
> merge" thing and constructing "virtual ancestors" per [1]?
> 
> [1] http://codicesoftware.blogspot.com/2011/09/merge-recursive-strategy.html
> 

Yes, it's very similar to [1], and you gave a good summary. The foldr() handles the >2 case, and is what git does elsewhere.

> 
> I'm worried about how complex our algorithms are getting.
> 

You are right to question the complexity of this - I understand that unwarranted complexity is the enemy of security. However, I do believe this algorithm can be explained in terms of a derivation from some basic principles, and I've also explored a few similar tweaks that turned out not to work.

Complexity isn't *inherently* a bad thing, especially if the problem is complex - we have lots of examples of algorithms more complex than this.

> Suppose a simpler policy:  a member-delete message takes priority over
> member-add even if they're siblings.  Since siblings only arise in the
> "simultaneous send" case, where it's sort of ambiguous what's going to
> happen anyways, I argue this policy is reasonable.
> 
> In this case, clients can track M and D member-sets, but don't have to
> associate members with the messageIDs that added the member.
> 
> A member-add message adds a new member to M, and removes that member
> from D (if present).
> 
> A member-delete message adds a new member to D, and removes that
> member from M (if present).
> 
> A merge sets D=union(D from predecessors), M = union(M from predecessors) - D
> 
> ?
> 

I will think some more about this and get back.

-- 
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/20140421/723f5c5d/attachment.sig>