Thank you, my name is Keegan. I'm one of the core developers who helped create matrix.
I'd like to spend some time talking to you about Federation. The aim is to give you a deeper understanding about how matrix
is Federation actually works. Isn't necessarily going to help you write a home server, or that it will be some tools that you may be able to use that will actually help you.
So, first of all, what is the Federation API? Hopefully, this is all kind of familiar. That most people have used the client's server API.
The Federation API is the way that two home servers will talk to each other. That's a bit high level, so you can go a bit deeper in that.
So, here's the server API with all the HPM points, all Jason objects, and that basically tells you everything you need to know. So, that's it. Thank you very much.
So, what is the Federation API really and what makes it hard to understand, right? Because it is a set of HPP APIs and is a way to exchange Jason.
It is also a pub sub mechanism if you have devices updates, for example.
But the main thing that makes it hard is that last one, the way to synchronize data structures. In this case, it's the rooms.
How do you synchronize rooms between servers? And that's what I'd like to talk to you about.
A few of the constraints that Matrix has is we want these kind of properties, right? So, we want it to be open to anyone who has a server.
It should be able to participate. There shouldn't be any single point to failures, and no central server that if you can't talk to it or it goes down, then you can't communicate.
Particularly communicate to other users who are on your own server. So, the fact that you can't talk to the other server shouldn't matter.
Likewise, works during networks, there's network partitions. It shouldn't matter your users and your server should still always be able to communicate.
And it needs to be by as in time fault-tolerant because, you know, the internet has a scary place, and people get up to all sorts of mischief, so you need to have a protocol that's going to tolerate time.
So, if we had more time, I would explain how I build up to see RETs, but we don't have time, so you're just going to have to go with me for now.
But if you don't want to see RETs, this is the Wikipedia definition, along with some bold and underlying bits, which detail the relevance to Matrix here.
So, the first one is mentioning, I think that's working during networks. The second one indicates there's some sort of merge algorithm for us, this is the state resolution algorithm,
and then the last one at the point there is basically saying that, if you've seen the same events, then you are in the same state, so you're room state, for example.
And the term conflict free is a little bit misleading, because in general, CRITs can't prevent conflicts, but they do give you a deterministic way to resolve those conflicts.
It's all that one of your heads, you can think it's kind of like get, but with automatic merge resolution resolution, so as a kind of way of thinking about this.
The thing with CRITs is they're quite special, because they prioritize AET of capped here, and they prioritising availability and partition tolerance.
At the cost of consistency, the consistency guarantees they can give you are quite strong, in fact they call it strong eventual consistency in the literature,
which basically consists of the two points of mention, the eventual update and convergence, so the eventual update being that, you know, if one corrects server sees some events, then everyone else is going to see the same events,
apply that event, but they will see it, and then convergence, once you've applied all the same events, you will be in the same state.
The key thing that makes this different from most other forms of distributed systems is that there's no consensus mechanism, so if familiar with blockchain and stuff, you have the idea of 51% attack with, if you have more than 51% of the hash rate, then you can kind of control the direction of where the chain goes, you can't do that with this.
Likewise, things like raft and IDFT, those are CP style systems, so the moment that you can't talk to, you don't have a majority in a network partition, then your system doesn't work.
So, we're going to be talking about Delta State CRITs. Now, if you notice the RITs that's fine, if you don't, there's a few different types of CRITs.
I'm talking about Delta State CRITs because that's actually what matrix is, and I'm also, if you look at CRITs, most of them will talk about it in a peer-to-peer-like manner.
I'm not going to do it, I'm going to talk to it in a federation-like manner, which again mirrors what actually more than a matrix actually does.
So, your A and B, who are going to be exchanges and stuff, we're going to be implementing a set as opposed to exchanging messages, but you'll see it all comes very similar.
In the middle here, you're going to see the operations that are going to be performed, some of those operations we've done concurrently, that's why it's a graph splits, and each one of these servers is going to walk along this explorer graph in a slightly different way.
So, first of all, red adds pizza to the set, which then you can see the red line as a peer at the top there to see that server has seen up to the pizza event, and then that event gets propagated over to the blue server, who then also applies it.
Then you can have the blue guy adds beer to the set, which then gets applied, and then concurrently, red does the same thing because who doesn't like beer.
And of course, now you've got two beers in existence, but it's a set, so be actually only care about it once.
And then the operations get exchanged between the two servers, and then we have applied the same updates, and therefore we're in the same states, which is that there is pizza and beer in the set.
Now what happens is a merge operation, because now the next event that happens is someone decides they don't like beer anymore, and they remove beer from the set.
Now what happens here is application defined, because we are implementing a set, we probably want to remove beer from the set entirely.
If this was a counter, in which case we've added the beer thing twice, then we might just want a decrement by one.
But because we're implementing a set, we're going to remove beer from the set entirely, and then propagate that over.
And if you can see how the two servers have explored this graph, they eventually have seen the same events, they are in the same state.
So it's worth noting that this could have gone slightly differently.
So for example, if we concurrently add those beers again, before a and b could communicate that they'd both add a beer, perhaps there was a network partition or something, they couldn't exchange updates.
And now the blue guy is going to come along and delete the beer as before.
So in this case, the graph shape is different, right?
Because the delete is not pointing to both of the add, it's only pointing to one of them, because it hasn't seen the other one.
But the state on this guy is the same as it was before, but on this guy it's going to be different, because what the blue server is now going to say is they're going to say, I'm going to add beer, and I'm going to immediately remove the beer that I just made, which affects me is a no up.
And then at some point, the red server is going to go and send the beer that they did add, and then you'll end up again converging on the same state.
Now what happens here is application defined as well.
So concurrently, you've got beer added and beer removed, but because this is a set, we want to, the fact that there were two beers added and anyone removed, there's still beer in the set.
However, if the delete here was a ban, and the ad beer was say, the person who was being banned, they're changing the red name, then you're going to want that delete to overwrite what happened.
So it's application defined exactly the semantics that's done here, and we're going to keep going back to this as you'll see in a moment.
Everything I'm described with until now is not by as in time for a tolerant, because you can choose what those IDs are, it's very sensitive to which IDs you choose.
So one of the key things that you can do is you can have a hash link tag, which is what matrix does, where the ID is the hash of the event JSON itself.
And then in that event JSON, you include the previous events, so that's forming a DAG structure, and they're all hash link together.
This is mostly to make it so you can't create an event that collides with an already existing event, because if you can do that, you can create causality.
Senders can be spoofed, so naturally you should sign your events, that's hopefully obvious lot of systems do this.
And the third one is interesting as well, because the third one is that updates can be dropped.
There are malicious servers, and you are only going to talk to certain malicious servers, they can just drop all your updates, in which case you're not going to converge, you're not going to see the same updates, and that's not good.
So matrix has a point to point architecture at the moment, which means that we get around this problem.
It obviously is not very performant, we'd like to fix that, maybe there's something that random gossiping, but at the moment we don't.
But that is partly for the security reasons.
But if you combine these things, you end up with bison time fault tolerant system, that can cope with an arbitrary number of bad actors, so it's immune to silver attacks, which I was leading to earlier with the 51% attack.
Hopefully, this is all looking very familiar at this point, because the hatchling tag, the signatures, the reading, all the little graphs with the tag forming, that's literally what matrix is at the Federation level.
And we wrote a tool, well actually Mackey wrote a tool back in 2020, called TARDIS, which is a way of effectively visualizing this graph in matrix rooms, and it looks a bit like that.
And all it does is it takes a JSON file, and then it will render the events that are in that JSON file, and the key thing, which I added in a couple months ago, was to then be able to perform state resolution on those events.
So I think, hopefully, I can go and give a quick demo of this.
So this is TARDIS.
No, this is nothing. That's awkward.
Screen mirroring, currently extending change to entire screen, this one.
Okay, cool. It's a bit weird, but okay, financial.
And now, if I do this, so you can see here's a graph of a room.
These are rooms that are fake, they're not from a real room, they're not real Alice and Bob here, but TARDIS allows you to inject fake events, and it will calculate events and do all sorts of stuff for you.
But you can see here, there are concurrent operations being done here, that's why the graph is forks.
And you can see that concurrently, what's happened is Alice has removed Bob's permissions, and on another branch, so concurrently Bob did not know this, Bob made Charlie a mod, and Charlie went and said the room name.
So what we want, semantically, is we prefer safety of a live-ness, we don't want bad things to happen.
So we're going to stop Bob making Charlie an admin, and we're going to stop Charlie from setting the room name.
So if you hit resolve state here, which actually may not work, because I'm not sure if I'm running the, yep, that's my family.
So if I hit resolve state here, you can see that some of these nodes have gone green.
So this is the result of state resolution. So what this means is that at this event, which is this end event, this is what the room state is.
So you can see at the room state, once these two forks have been merged, Bob Charlie is not a modulator, and the room name has not been set by Charlie either.
But if you, what you can do is you can go back in time and see, you know, back here before, before these operations were done, then the actions had been applied, right, because it's optimistically applying these updates.
This is why sometimes if you have concurrent behavior, and then you can talk, your service can talk to each other once again, you might see state get rolled back, because if something has happened like this, there's been a concurrent revocation that you weren't aware of, then, you know, we have to apply.
So we have to decide what's going to happen to those circumstances, and what we decide is that you're not going to be able to.
We prefer whatever the admins want to do, if actually sorted by power, but I will get on to that. Right, now if I go back to here.
Go, okay, cool. So state resolution, state resolution to hopefully I've convinced you that state resolution algorithm and CRDT's no diagrams are basically the same thing, and we just need to decide what the rules are for concurrent behavior.
And that's the fact that what the state resolution algorithm does, like I said before, it's application defined and we prefer safety over liveness.
So I'm going to go through the state resolution algorithm at like a medium-ish level.
I'm lying in a few places, but in essence, I'm mostly not lying. It's only small ethnicalities in my defense, so it makes it easier to explain.
Here you've got some, he wants two folks you want to merge, and they have some sort of shared state where they originate from, which is the stuff in yellow yarns.
The stuff in yellow yarns is perhaps, you know, obviously called uncomflected state, but it's not conflicted between the two folks.
The blue and red stuff is conflicted, but the blue and red stuff may contain events that, like if one of those was setting the root name, or that may not be conflicted, but the making the person a moderator is conflicted.
So you need to include all the authorization events in this conflicted set. So that's basically where we pull in, okay, you're changing the root name, okay, but you also now need to include the power level event that major a moderator.
It's that's all the thing.
Once you've done that, there's two stages to the state resolution algorithm. The first one only deals with the subset of the room state called power events.
So in power events, these are power levels and things that can revoke the ability for people to do certain actions.
We're going to take the events and we're going to order them. We're going to split them based on the full conflicted set, and we're going to order them based in what the specification says.
The reverse topological power ordering, which is a set of ordering rules, which initially is honoring the causal relationships, then when you, there is no causal relationship, because it's concurrent.
We're preferring power levels and then type-breaking on time-sams and event IDs.
Once we've done that, we're going to go and apply itchative forth checks.
So we're going to use the un-conflicted set as the base state, and then we're going to go through each event in turn and see if the event passes iterative forth checks.
If they don't pass, then we won't include them in the final set.
So once we've done this, we take the stuff that we did get, and that will be called the partially resolved state.
It's partially resolved because we're only dealing with a subset of the events here.
And then the second step is to handle all the other remaining events that we didn't handle before. Things like setting a rim name, setting a rim topic, that sort of thing.
And again, similarly, we need to order these events. So we're going to compare each event to where it sits from the power level main nine.
Every single state event points to a power level event, which gives it the authorization to, for that action to have taken place.
And if you use that, you can then order it, basically use that as a primary order mechanism.
Now, some of those events may have been rejected from the earlier itchative forth checks that were applied, like in this scenario that we're about to see.
If that happens, then you just go to the earlier power level event.
But if you keep doing this, then you'll end up with an ordered set of remaining state events.
Wait for the animation. There we go.
That's called the main line ordering, because it's based on the power level main line.
And then again, we're going to do a very similar thing. We're going to use the partially resolved state this time.
And again, apply it to all checks and likewise, it should all checks may reject certain events or not.
And then the result of that becomes the final result state.
And that's mostly how this algorithm works.
A few things that most of the search stuff I've touched upon, so yeah, on convicted set is things that both folks agree on.
The power events are things that may remove the ability for used to serve actions.
The power level main line, the reason why this exists is because we want to split room states and all.
Yeah, we want to split room state into epochs effectively. Like if there's concurrent behavior, you need to try to order the events in a way that isn't
just using the time stand, which can be gained. So we use the power level main line to order things roughly causally.
So the same resolution algorithm is not infallible, okay?
It isn't perfect. There are cases where it behaves in ways we do not expect it to behave.
And part of this is, well, most of this is down to the fact that servers are walking this graph in different ways.
And therefore processing events in different orders.
And this is due to connectivity issues predominantly. And you know, if we know of certain failure modes, that's great.
We can look at them in TARDIS and we can resolve them and make sure everything works or doesn't work.
But there would be nice if we could kind of discover new failure modes and discover new ways that things can break.
So this is introducing a new tool, which is only recently been released called Chaos.
Chaos uses similar stuff which I've done before with Compton Compton Crypto.
It runs home servers in Docker containers and it uses a man and middle proxy to sniff on the Federation traffic.
And it can also modify the Federation traffic to just reject the traffic entirely to cause partition faults.
Likewise, we also introduce crash faults by sig killing home servers at random or at determine times.
So the best way to do this will be to demo this one as well.
Okay, so if I, so I did manage, oh, yep, it's fine.
So can I do that? Okay, thank you.
So here is Chaos, Chaos has got two clients on different home servers.
These are real home servers, by the way. And you can hit start and what's going to happen is it's going to send lots of clients over API traffic.
And then lots of Federation traffic that you're going to see at the bottom then you can see everything's happy.
You can then hit next but which will then block the traffic so every time they try to send you a request it will say blocks.
And then you can at some point here the next but.
And then what's going to happen is it's going to reconcile the state and you'll see a bunch of extra requests being made.
There you go, which is it kind of re-synchronizing what the room state is effectively.
And then you can hit test and now what test is going to do is it's going to ensure that the room membership list on the client on home server one and home server two matches is an agreement.
Also matches what Chaos believes is the room state because they should all all three of those are match and chaos is like the gold state of what should be.
And you can see here it said success because the room state did match.
And so using this as a tool you know we can introduce net splits we can crash the home servers and we can do the idea behind this is to kind of have one of these guys running until something that happens and then we can see what went wrong.
So I will just close that down and then go to here and the other thing is obviously you can run this without the web UI in which case you just get more of a log like sort of.
So you can see the federation requests going through there each tick is the number of clients.
So if you are request and then you'll see at some point in the next split and it will block some traffic there you go.
So that's been a really useful tool for us to investigate improvements to the federation API protocol.
So yeah the kind of thing is is why why make these tools at all in the first place and mostly it's to.
Develop to to make some changes to the Federation API to make it more more secure and to make it more performance as well.
So we've been working quite closely with academia particularly far in Jakob and we're going to be making will be proposing some protocol changes to the Federation API just to make it a bit more robust to.
To various faults and if you want to read any more feel free to take a picture of this this is.
Some academic papers which talk about the artistes and more detail and particularly in relation to matrix as well.
So woods would highly recommend going through those if you're interested.
And thank you very much.
Yeah, how do you differentiate fairly much from.
Yeah, how do you differentiate fairly much from malicious attacks ultimately you can't right because a malicious cat could be just partitioning off the network.
Something like chaos only does non malicious attacks so we're talking crashing petition faults.
It's very hard to automatically model not automatically model malicious attacks because it may be altering certain fields in the event or altering signatures or like something like that so we can't automate the detect automate testing for them.
If we see stuff in the wild then obviously we can you can go and see kind of what went wrong, but there is limits to to what you can do.
And it's an automatic.
Can you use this for deterministic fuzzy and non deterministic fuzzy.
Can you can use it for us?
I'm going to make it for us.
Well, it will effectively it kind of does already because it will run until there is a failure even on the clients their API or on the Federation API.
So in that way it is already a fuzz tool.
I would like to make it deterministic so there was a talk yesterday in the testing room which I went to about deterministic simulation testing.
And if you've ever seen the tiger beetle presentation that's the sort of stuff I'm talking about and that was inspiration for chaos.
I would love to have that but to do that you need to effectively re engineer your home server so you can mock out things like your network IO your disk IO and clocks.
So that's quite an undertaking and it's something which we're going to we don't really have time to do right now.
So maybe in the future.
Yes.
We're talking about application being able or application simply to decide how to resolve the conflict.
Can we then see maybe insert the major matrix implementations or depth like that that you can then maybe as a sort of super moderator choose.
So yeah.
So the question is basically can you.
And a per room level define what the application specific merge algorithm is going to be.
And you know, let it up to be more of a social problem and say, you know, this moderator is going to say these are these are the rules ultimately know because all servers need to come to an agreement.
So just because one guy says this is what you should do to merge things the other servers all have to agree and why should they agree or your server says.
So it has to be begsens the protocol.
Yeah.
Just the kind of goes in the same direction I'm wondering.
When Matthew talks a lot about matrix and other contexts like, I don't know, I have to do whatever use case might that in the future require changes to the state resolution algorithm where these kind of applications specific conflicts solutions are not.
So is it.
Yeah.
Matthew Matthew wanting to use matrix for non messaging IoT or things like that and does it require changes to the application defined merge algorithms.
Yes.
I think so.
I think at some point we may want to have the ability to put additional CITs on top of matrix.
I mean, that's just what I think.
But I agree at some point you're going to want more complex structures which then need to have additional rules for how you how you handle matters.
You have a question.
Hello.
Are you looking mostly only at the state resolution are you also looking at how other layers of matrix possibly the server key infrastructure and stuff then affect the state resolution and.
Yes.
I mean.
Sorry.
So are we looking only at state resolution or are we looking at other parts of the Federation API as well.
We are looking at other parts of the Federation API.
We are looking at server keys.
We're also looking at the way that we reconcile state for partial synchronization.
So if you if you've been offline for a very long time and you need to catch up then you know what what we currently do versus what we could do kind of thing.
We are looking to that.
Yeah.
And chaos looks into the internal state of some home server, right?
No.
Chaos does not look into the internal state of the home server.
We have another implementation.
Yes.
So it's all it needs is the client server API and the Federation API.
And in fact the main thing it does intercept it all is you literally just said HTP proxy the environment variable.
You set that to the amount of the middle proxy that's basically all you need to do.
So it's really easy to get it working with your conduits and you don't write to the world.
So thank you again.
I really impressed by the visuals you use in the demonstration and also the tools and for the naming of the tools.
Thank you very much.
Thank you for explaining.
Thank you.