On Sunday, March 8, 2015 00:13 GMT, [email protected] (Ximin Luo) wrote:
For a private dynamic group chat, the merging requirements are not exactly the
same as in a collaborative environment like Google Wave:
- for a basic application, one does not *need* to merge arbitrary state. The
only thing you need to merge is an unordered set (the membership set).
- merging unordered sets is easy and a solved problem if you have full history. However, the fact
that this set represents "who has permission to see what history" makes the problem hard
again, in the context of the other constraints (secure, casually-consistent, decentralised). Merge
algorithms require history, but if someone can't see past history (e.g. after joining) then they
don't have enough information to execute the merge algorithm, nor to verify others' claimed merges.
(This is not necessarily an impossible problem, and indeed is the "last missing piece" in
the bundle of ideas I haven't yet written down.)
Briefly skimming over their spec: http://matrix.org/docs/spec/ "The state of the
room at a given point is calculated by considering all events preceding and including a
given event in the graph. Where events describe the same state, a merge conflict
algorithm is applied."
My impression too is that they underestimate how hard this will be. Also, their security practises
are questionable - they do have a list of threats in the spec, but there are no suggestions or even
hints on techniques on how they will defend against these threats. I guess they will add this stuff
in later, but as I'm sure everyone on this list knows, you can't just "add security
later". It sounds like they just did the equivalent of adding partial ordering to a federated
protocol similar to XMPP, using TLS "for security", and hoping that everything will be
naturally straightforward to conceptually lock down as they write the code.
X
--
GPG: 4096R/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git
I've been working on a lot of the federation side of Matrix since its
inception, and I can assure everyone that we really do know how hard
these sorts of generic merge algorithms are. Hence why we've promptly
not tried to solve them.
What we have done is attempted to solve a much simpler subset of the
general problem. The basic requirement is along the lines of: "All
servers in the group chat (that can talk to each other) will
/eventually/ agree what the state of the room is." Note the careful
omission of the word "correct".
(The state of the room, or more accurately the state of the room at any
given event according to a given server, is simply a mapping between
keys and nodes/events in the directed acyclic graph. The key is included
in the event.)
The main points to note are:
- We differentiate "auth events", i.e. events that affect
authorization of "new" events. There are very few types of auth events,
and Matrix doesn't support custom auth events.
- The merge algorithm of non auth events, as Ximin points out, is
relatively easy.
- The merge algorithm for auth events is designed so that maliciously
branching and re-merging does not allow circumvention of auth changes.
This is the hardest part of merging, and is heavily special cased.
- Each event points to the auth events that allow that event to
happen, separately to the full event DAG.
- All events are signed by the originating server, and all event
relationships are protected by hashes (à la git).
- Events can be "redacted" by servers, where all non protocol relevant
keys are stripped, e.g. message contents. This allows servers to
effectively "delete" nasty messages without leaving a whole in the
graph. This is possible since we include a hash of the full event, but
servers only sign the hash and protocol relevant keys rather than the
full event.
- Every server is required to store the full auth chain of the events
it sends (for at least as long as it stores the original event). The
auth chain is simply all the auth events for that event, and the auth
events for those, etc.
- The auth chain is enough for a server to accept that an event could
have happened.
- Servers can tell each other if they think another server shouldn't
have accepted an event and why. (For example the sender of the event had
been kicked between, in topological terms, the join event and the
message event)
- When a server joins the room, it gets given (by the server it is
joining via) the other servers view of the current state and associated
auth chains.
- Servers can throw away old history/events. They still have to keep
all the auth events.
Thus, different servers can have different views of what the current
state is if buggy or malicious servers are involved; for example, when
joining a room your server can be given an incorrect view of the current
state. However, the auth chain ensures that these views can only be
incomplete or stale, servers cannot simply include arbitrary synthesized
events.
If two servers discover that they disagree on the state (which they
quickly will), then they will exchange their views and attempt to prove
the other side wrong; by the end of this process two correctly
functioning servers will come to an agreement of the current state. In
effect providing a "healing" mechanism.
(This does mean that servers may initially accept an event, only to be
subsequently shown that the event should have been rejected.)
The outcome of all this is (hopefully) that the subgroup of correctly
functioning servers *will* eventually agree on the current state, and so
which events should accepted and rejected.
Hopefully this clarifies a little what Matrix is trying to do and what
the federation protocol does and doesn't aim to provide and guarantee.
Erik.
_______________________________________________
Messaging mailing list
[email protected]
https://moderncrypto.org/mailman/listinfo/messaging
