[messaging] Matrix.org: Decentralized group chat

[Ximin Luo]

On 10/03/15 21:39, Matthew Hodgson wrote:
> So in terms of state merge resolution: yes, this is obviously a hard 
> problem to get right.  Hopefully we haven't underestimated it.  The WIP 
> draft documentation for it is at 
> https://github.com/matrix-org/matrix-doc/blob/master/drafts/erikj_federation.rst#state-resolution.  
> Meanwhile the reference python server implementation actually implements 
> this, and hasn't exploded yet.
> 

I haven't yet read the full thing, but this feels a bit naive. In a situation where your state can be said to have a "removal" operation, then the properties stated currently don't work.

   {abc}
   /   \
  /     \
{ab}   {bc}

The result of merging the two children should be {b}. Note that the history is important - if the parent state were different in the above case, e.g.:

    {b}
   /   \
  /     \
{ab}   {bc}

then the merge result should be {abc} - i.e. the "time-reversed" form of the first case. "Removal" is abstract; I think this results applies for any state that can be said to admit "inverse" operations.

But perhaps you've architected your state such that "inverse operations" don't exist? (c.f. what Trevor said before about "If group membership can be added but not deleted, then merging is easy (union of group members).")

The "hash of event_id" feature also feels a bit ugly. Say an attacker wants to screw with things, then he can generate an event_id with a greater hash, and send it pointing to the older event. Why would he want to do this? I don't know, it depends on your application, but maybe he's not allowed to explicitly reverse an operation *after* it happens. (There is something in there about not admitting certain ban operations.) I don't know if there is a *specific* attack, but the general idea of "conflict resolution via arbitrary tie-breaking" is susceptible to such things. Do you have some arguments why this is N/A for your application?

Also, what do you mean by "end-to-end encryption"? When more than 2 parties co-operate in a session, there are extra security properties we want like consistency, which is not "automatic" with a partial order since an attacker can always create two events attached to an older parent that "looks authentic" but then (with co-operation of the transport) delivers different events to different recipients.

Signing also interferes with the deniable-authentication of axolotl. But perhaps this isn't part of your threat model.

X

-- 
GPG: 4096R/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git