Growing Pinecones for P2P Matrix
CC Attribution 2.0 Belgium:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Alexander, Neil
The success of P2P Matrix depends on an overlay network which can provide good connectivity between users, and scale appropriately. For that we built Pinecone, an implementation of a new routing scheme called "SNEK", along with tools to simulate and to measure various properties such as routing table size and convergence times. This talk will explore some of the core design elements and the challenges of building a decentralised routing protocol.
 Hello, well, thanks for attending this talk today. My name is Neil and I work on the PSPianatrix project. Over the last year, spent quite a lot of time working on Pinecone, a new overlay network that will hopefully become the foundation of PSPianatrix. Pinecone is an overlay network that's designed to provide end-to-end reachability between devices in a mesh fashion. Regardless of whether you're operating over the internet, over a local area network, or using proximity-based networking like Bluetooth, it should be possible for any two nodes participating in the same mesh to communicate with each other. One of our core goals is to minimize the amount of information that a Pinecone node needs in order to operate. So they typically don't store much state. They only need information about the spanning tree, their direct peers, and network paths through the current node in order to work. And this typically means that Pinecone nodes only have a few routing table entries, and therefore they don't need much memory to run. So why are we doing this? Ultimately, we want PSPianatrix to be able to operate over a variety of transport, and we want those transports to be basically invisible into the application layer. It shouldn't matter how we connect to other nodes. The goal is ultimately the same. We just want to be able to address a node by its public key and to exchange traffic with it. This also means that we can bridge different transports together into a single network. Nodes can have peers with different link types, and the application should be able to operate without any real concern for how those links were set up. And finally, there is a very sad trend at the moment of more and more internet users being placed behind carrier-grade NATs and restrictive firewalls who don't stand a chance if being able to accept incoming connections without the assistance of either some kind of relay technology or an overlay network. So this time last year, we introduced Pinecone, and it's a re-implementation of many of the same ideas that were in development on the IGDRASOL network at the time, including tree routing, pathfinding, source routing, and a new experimental routing scheme, which we have now formed into SNAP. Our initial pass at doing this was quite scratchy, to be honest, and in the end, we also ended up just performing a complete rewrite of the Pinecone router code, which not only made it much easier to reason about and to document, but it also meant that we solved a number of performance issues and race conditions that we were seeing at the time. In addition to that, we've also been maintaining builds of the peer-to-peer matrix demos for iOS and for Android. Now, these have gone through various iterations over the last couple of years using various different routing protocols, and the latest builds are now using the latest Pinecone protocol and code. And these are available today to play with. They're linked from the topic of the peer-to-peer matrix room, which is linked in the slide. So to be honest, the experience of using the demo still isn't fantastic yet. There are still a number of Android and matrix-specific issues that we need to work on, like how we improved the Federation experience and cope with devices then coming and going, which are fairly agnostic problems to the routing algorithm that's used. The main design highlights of Pinecone are that it gives everybody a public key. Their public key is their address on the network, and their address only changes if their key is changed. It gets very close to the concept of mobile IP in that you can move around the network and roam, and yet your address stays the same. All nodes on the network are considered to be pretty much equal players. That is that everybody is forwarding traffic on behalf of the nodes around them. And that allows us to reasonably arrive at the promise that all nodes can contact other nodes. Fast convergence times are also really important, especially in a network where we're dealing with devices that move around a lot, like mobile phones, tablets, and laptops. So the network must be able to update quickly when changes happen, preferably with the smallest amount of disruption to the traffic that's already in transit on the network at that time. And we do this using proactive routing updates, which actually get us very close to that goal. As I mentioned before, we also have very small routing tables, so it doesn't really take a lot of resources to run or to embed a Pinecone node, and we're able to operate over pretty much any transport that guarantees both reliability and ordering. So we've successfully proven Pinecone working over TCP, over WebSockets, and over Bluetooth low energy on the PCP and Matrix demos, and we should reasonably be able to support any other link type that provides those same guarantees. Each Pinecone node is participating in a global spanning tree. The root node of the spanning tree is chosen by an iterative process, where the node with the highest public key wins. If that node disappears, the node with the next highest public key will be chosen to take over the role, and so on. And this means that the node that's chosen for the task will feel pretty much arbitrary a lot of the time. Now, the root node has exactly one special job. They must send out root announcement packets to all of their directly connected peers with their public key and a sequence number. Other than that, the root node is just like any other node. Now the sequence number that we send out must be increasing. If the root node sends an update that looks strange in any way, for example, the sequence number wasn't increasing, it was actually lower than the last update, or if the root node just gives up sending root announcements altogether, then the next strongest key will take over the root role after a timeout period. All nodes in the network will receive root announcements from their peers, and they must select a single parent before repeating the announcement from their chosen parent to all of their peers. And this means that the root public key and the sequence number are effectively flooded to all nodes in the network. Given that each node needs to sign the root announcement from their parent before passing it on, this means that every node on the network learns a verified path up to the root for free with the spanning tree. So as the root node is always the node with the highest public key, this means that we always have at least one worst case ascending path up through key space. Using the information in the root updates, this allows nodes to determine their own coordinates on the spanning tree relative to the root node. Now, the tree-routing algorithm is simple. We just take our coordinates and the destination coordinates, we subtract the number of hearts to the common ancestor, and then we add the lengths together. And the tree-routing generally finds paths that are quite direct. So you might be wondering, if nodes can assign themselves a locator from the spanning tree, the coordinates, and the spanning tree forwarding algorithm provides fairly direct paths, isn't that sufficient? Sadly, the downside to this system is that if the coordinates are always relative to your parent node on the spanning tree, that means if that parent disappears or a new bad parent comes along or worse, the root node changes and causes a global shift on the network, you get a new set of coordinates, and therefore you are no longer reachable at the previous coordinates that you had. And there's also the question of how you associate a public key of a node with a set of coordinates. Now, earlier versions of the addressal network worked in exactly this way, and they mapped keys to coordinates using a distributed hash table, but it was difficult to avoid the temporary disruption and packet loss that would happen if the tree shifted. That's where SNAC comes in. Now, the tree-routing gives us a suitable topology to exchange setup messages with other nodes, which we only need to do periodically. So it doesn't really matter if the tree shakes too much otherwise. The idea of the SNAC topology is to arrange nodes on the network into a virtual line, where each node has a relationship with its key space nateless, that is, nodes with the next key down from ours and nodes with the next key up. Here we show the same network in two different views. On the right-hand side, you'll see a network of nine nodes and how they are physically connected to each other. So node two is connected to nodes one, four, and eight. Node four is connected to nodes two, three, and seven, and so on. On the left-hand side, we show the SNAC topology. That is, all of the nodes on the network arranged into a line, ordered by their public keys. In this instance, the highest keys are to the left and the lowest keys are to the right. So 883e is a higher key than 701e, and 9b67 is a higher key than 883e, and so on. To illustrate how SNAC works, we're going to take a pair of nodes, five and seven, which are highlighted on the diagram to the left. These are key space neighbors. There are no other nodes on the network with a public key that falls in the middle of those two node's keys. But you'll notice from the right-hand view that they aren't physically connected to each other. There are multiple nodes between those two nodes. So what happens is that the node with the lower of the two keys, in this case node seven, sends a bootstrap message into the network. Bootstrap messages are forwarded to the node with the key that's closest to our own. So in this case, that's node five. Now, it's possible that node five already has a neighbor relationship with another node, but that's okay. If our new bootstrap message is from a node that's closer to node five's key than its existing neighbor, we'll just replace that relationship with this new one. The result is that node five's descending node entry, that is, the node with the next lower public key, becomes node seven. Likewise, node seven's ascending node entry, that is, the node with the next higher public key, becomes node five. So both nodes now reference each other. To set up this relationship, they had to exchange path set up messages, and the nodes that are in the middle, nodes one, two, and four, have forwarded those messages. The intermediate nodes populate their routing table based on those set up messages. So those three nodes will add routing table entries accordingly based on that set up. As a result, they've learned about a new path between node five's public key and node seven's public key. Now, if you imagine that every pair of nodes on the network is doing the exact same thing, as nodes set up past to their key space neighbors, the routing tables of other nodes on the network are populating with more and more information about which directions they can travel in order to reach certain keys. So the routing logic after that is quite straightforward. When we want to forward a packet, we just pick the routing table entry that has the key that's closest to the one that we want to talk to, and we forward it there. In this regard, it's not really dissimilar to how a distributed hash table relays messages in order to get closer to a target content ID. In order to keep the routing information up to date across the network, we do need to react quickly when a path breaks. So in the previous example, if one of the nodes in between nodes five and seven disappeared, we need to notify everybody else that cares about that path, that it's now a dead path. And we do this by sending dead-arm messages along the path, resulting in the routing table entries for that path being deleted. The key space neighbors then bootstrap again, using a different path if possible. And this means that the network can heal very quickly and quite often without disruption to traffic that's already in transit. If a more direct path appears, there's still likely backup paths via less direct routes available, so we'll just forward using those instead. And because the node's public keys didn't change as a result of the new topology, we don't need to scan the network in order to find the new location of that node. We just trust that we can keep forwarding until we eventually reach the node in its new location. For this to work, and to not introduce routing loops while we do it, the core rule is that the next hop for any routing decision must strictly take the packet closer to the destination public key. We will not backtrack. Nor will we forward anything to a node whose key is further away from the destination key than our own key is. To make a routing decision, we use information from both the spanning tree and the snack routing table. In addition to that, we'll also look at the public keys of our direct peers and their ancestors in the spanning tree. And this gives us a pretty good spread of public keys to select from to make a routing decision, so hopefully we can find one that's closer to the destination. We'll also try our hardest to take shortcuts, if we can. For example, if we notice that the destination key is actually one of our peers' ancestors or is very close to it, we will shortcut via that peer instead. In some cases, this helps us to shorten the path lengths that are taken in order to reach the destination. To examine how snack performs at finding paths, we measure the stretch. Now, stretch is how many times longer the path is compared to the real-world dike-strah shortest path through the network. A stretch of two means that the path is twice as long as the shortest real path, therefore lower numbers in a scenario of atta. To do this, each node effectively runs a trace route to every other node on the graph, and we measure how many hops it took. The numbers displayed on the slides are mean averages. The tree paths are used to set up snack-neighbor relationships, but really we're much more interested in the length of the snack paths, since those are the paths that actual normal traffic will take as opposed to protocol traffic. On the left, we have a network of nodes that is generated completely at random. There is no logic at all to how the nodes are connected to each other, and in this particular network simulation, we see that the snack typically found paths that are on average 1.7 times the length of the real shortest path. In the middle, we have a network that's designed to be completely uniform. It's a perfect grid. In here, snack-achieved paths on average about 1.57 times the length of the real shortest path. Finally, on the right, we have a real-world network, which is based on the Tri-Funk and Leipzig using data from the National Lab graphs. This is a sample of a real-world network topology, and here we achieved a path length that is on average only 1.18 times longer than the real shortest path. Real-world networks are actually yielding better results, which is very encouraging. Stretch varies a lot with network topology and with key distribution, but the data tells us that even in networks that aren't ideal at all, we still typically manage to find paths that are no more than double the length of the real shortest path. Moreover, we do this with nodes typically only having a handful of routing table entries. To get a sense of how the routing scheme handles mobility scenarios, we use a number of tests within the meshnet lab suite. These spin up a bunch of nodes in virtual network namespaces, wire them together appropriately, and then run scenarios on them. One of the more aggressive tests in the suite for seeing how a protocol handles nodes moving around is the mobility 2 test, which we've displayed here. It starts by randomly placing all of the nodes in a square 1 kilometer by 1 kilometer grid, and then it starts moving them around. Between each set of movements, it runs pings from every node to every other node to determine if they're all still reachable to each other after the movements have occurred. And this should be a reasonably good indicator of how well the network converges after links come and go. The test starts by making smaller movements, so to start with, they only move at 50 meters. But during the test, this increases the step distance up until we're moving as high as 400 meters, and that would significantly disrupt most wireless networks. Now, as you can see from the graph, pinecone and green perform significantly better than Batman advanced in orange and babel in red. Batman, while holding quite strongly, still regularly loses up to 30% of the pings through the test. Babel performs significantly worse than that once the step distance increases over 50 meters. The meshnet lab tests do only test a rather limited number of scenarios, and due to the fact that each pinecone node has to run in its own process there, that can increase the overheads and require quite a lot of compute resources just to run fairly small simulations. Our answer to this is an integrated pinecone simulator in which we can run large numbers of pinecone nodes within a single multithreaded process, and to be able to examine the internal state of those nodes and the network as a whole. Devon who joined our team recently has been spending quite a lot of time working on improving the simulator and adding new features to it. The web interface allows us to see how the network is forming in slow motion. We can load any shape network into the simulator with any reasonable number of nodes and view the various different topologies. And this one is showing in slow motion how the network is arranging itself into a snack, and then we'll add an additional node to show how that also merges in. In reality, this is happening in under a second for a network of this size, but the fact that the network converges on a single line means that all of the nodes on the network found their key space natives successfully. We can also simulate much bigger networks, and this is a totally random graph of 250 nodes with a whole bunch of pairings that are randomly set up between them in the spanning tree view instead of the snack view. The spanning tree forms almost instantly, which gives enough information to the nodes to start bootstrapping the snack and communicate with other nodes to do so. By the time we switch to the snack view, which at this point fairly well resembles the Windows 95 screensaver, we can see that most of the convergence has already happened, but a few more key space neighbor relationships are still being built. Being able to visualize what the network is doing in this way is actually really valuable. It gives us a lot of insight into how the network converges and responds to certain conditions. There's still quite a lot for us to do with the simulator here, but our goal is to be able to use it to research and design mitigations against classic Eclipse and Sibyl style attacks, as we'll be able to simulate how the network responds to those kinds of malicious actors. We also plant our mechanisms for detecting packet loss, particularly of protocol level traffic in the hope that we'll be able to route around nodes that deliberately cause disruption and to make the bootstrap process more robust overall. Source code for Pinecone and the simulator is available on GitHub in the Pinecone repository linked here, and there is also a wiki on the same repository which contains quite a lot of information about how the protocol itself works. It does fall short of being a complete implementation guide at the moment, but it does give a pretty good overview and rationale of how the spanning tree and the snack are set up and how they function. I've also spent quite a bit of time cleaning up and commenting the router code as well, so hopefully that would be reasonably readable too. I've also referred to the MeshNet lab multiple times and MATS linked here too. It's a really useful tool for evaluating how a routing protocol converges in scales and to be able to plot those results against other existing routing schemes. And finally, there is the Peer-to-Peer Matrix Room where you can come and talk to us, and also to find the links to the latest Peer-to-Peer damage. That's all from me today. Thank you so much for listening. All right, so I don't know if people can hear us already. It looks like there is wobbly 20, 25 seconds that we don't know if we are live or not. So in the meantime, I'm not going to ask a significant question, but you can see me dancing so you are not bored. And it looks like we are live at least. So the first question, of course, Neil, when is Peer-to-Peer going to be live? We want Peer-to-Peer Matrix right now, please. So I need to stress the point that Peer-to-Peer Matrix is still very early in development at this point. Working on Pankona is one of the ways that we're solving connectivity issues in disjoint networks, ones that aren't necessarily reliable or ones that aren't necessarily internet connected. But there's still a lot of things that we need to solve before we'll be able to really put the stamp on Peer-to-Peer Matrix and say, yeah, this is done. This is usable. All right, so we don't have Peer-to-Peer Matrix ready yet. And when we say Peer-to-Peer Matrix, most of the time people have in mind the cool demos that you have already showed on the iPhones, for example, or on Android, so mobile Peer-to-Peer. But we do have an interesting question. Is it possible to get Peer-to-Peer Matrix for the home servers, for existing home servers, and does it make sense? Yes, so this is something that's possible. When we talk about the iOS and the Android demos, what they're actually running is an embedded Android home server built into them. And effectively all that happens there is that your client is just talking to a home server that's running on the device. There is no reason that we can't do this with static home servers that are running in data centers. And indeed, we do actually have a Dendrite profile that can run in that configuration so you can just run a Dendrite process, but run it in P2P mode with Pinecone. And we believe that probably that will be the start of how we transition over to P2P Matrix in the future is that we start to provide an embedded Pinecone node or the necessary logic for P2P Matrix into static home servers. All right. And the SNEC thing you have been showing us. It's just for the transport and the connectivity of the different nodes. Do we have challenges at the Matrix protocol spec level left to solve or is it working already? Because in the demo you show we can see messages being sent using Matrix using a specific element, but it's not connected to the rest of the Federation. So do we have things to solve? Yeah. I mean, there's quite a few problems that we still need to solve with our Matrix Federation as a whole works because at the moment Matrix Federation is still very much designed around the precedent that servers are online most of the time. And of course, P2P Matrix just takes our assumption, just completely racks it. So for instance, if your server has been offline for a period of time, you need to catch up with missing state events, missing auth events, anything like that. That at the moment would rely on having other servers available in the room to ask. So our main sort of challenge here is to how do we change Matrix Federation so that it's less reliant on other servers being online all of the time. And that's the biggest challenge. You'll notice this is a problem if you use the P2P demos for any period of time and you then, you know, check the task into the background and go off and do something else and then other people are chatting away in a room and then you come back later. The way that it reconverges at the minute is still not great. So that's the biggest Matrix problem, definitely. All right. So if we want that to work, we need to abolish tunnels. We need to have network coverage all the time and we need to have very large batteries. So the phone don't die. Yeah. And the idea is we need to avoid that. You know, we need to try and do this in a way that has the least impact on people's batteries and, you know, cellular connectivity. Definitely. We had a question from RevaLiber who asked, what happens if malicious actors generate a key that is highest but refused to properly participate in the network? That's a really interesting question, actually. And the thing is, is that refusing to participate properly in the network is a vague thing. There's a lot of different ways in which you could choose not to participate. The main one being that you could just take on the root node role by having the highest key and then just not send out updates or send out updates which are just obviously not correct, you know, like we're saying in the presentation about sequence numbers not being correct or anything like that. What typically happens in that case is that other nodes on the network will just ignore those updates and eventually they will time out on that root node specifically and then the network will rearrange around something else. Another big failure mode and one of the ones that we're trying to work on, particularly when it comes to adversarial nodes, is what happens if nodes stay online but just choose to selectively drop traffic, drop protocol messages, drop whatever. And that's something that we're having to spend quite a bit of a time and effort on, you know, how we fix that problem basically because we need nodes to try and identify when a malicious actor is dropping protocol messages or trying to do something obviously bad and route around it if possible. And that's going to be one of the big areas that we're looking at, especially now that we have the Pinecone simulator up to a standard that we can actually run these kinds of scenarios without having to go out into the real world with hundreds or thousands of devices. Okay, so it's quite a complex network and there is a question which, so the answer I guess is it depends on many parameters but I'm still going to ask it anyway. What do the latency and maximum bandwidth in a Snick world look like? That really depends on the connectivity on the path that you're taking. So if you have a bunch of devices that are strung together on very fast connections and you're following the path that uses very fast connections, good bandwidth, low latency, you will get very good bandwidth and very low latency. If you're following paths that are definitely slower or much worse quality then obviously that will be what happens to traffic following that path. And also another area that we need to look at as well as if we can specifically avoid taking very slow paths if we can manage it. All right, we had a question from Timo which was very interesting. Yes, the examples for physical topologies look like each node only has a few edges but aren't most nodes connected to each other in the Internet? I'm going to interpret this question as if you were sort of talking about the matrix federations that works today which is that the matrix federation is pretty much full mesh and that means if you're federating in a room you are talking to all of those servers once and you can globally route to all of those servers. In a Pinecom network obviously that's not necessarily true, a node can have one peering, it could have 17 peering, it could have hundreds of peering. And what we need to be able to do is to route traffic based on just whatever connectivity we have available so that if you decide you need to talk to some other server with whatever public key you just use the path that are available. So I'm not really sure that there's a straightforward comparison to the Internet there. Right, you showed a graph at some point comparing Pinecone to Batman Advanced and Babel. Do you know if people who are working on this would be interested to contribute to Pinecone and if they are interested in using Pinecone? Admittedly, I have never spoken to any of the people involved in developing these routing algorithms. I would love to think that work that we're doing around Pinecone and also around the address on network because that's a very big player in this. Yeah, I'd like to think that that work will eventually spread outwards. Right, and we have just a few seconds to say that we could not ask the question about why this nickname, but there is a question and answer room which is going to open shortly so you can ask all your questions to Neil. See you in the next talk.
 Hello, well, thanks for attending this talk today.  My name is Neil and I work on the PSPianatrix project.  Over the last year, spent quite a lot of time working on Pinecone, a new overlay network  that will hopefully become the foundation of PSPianatrix.  Pinecone is an overlay network that's designed to provide end-to-end reachability between  devices in a mesh fashion.  Regardless of whether you're operating over the internet, over a local area network, or  using proximity-based networking like Bluetooth, it should be possible for any two nodes participating  in the same mesh to communicate with each other.  One of our core goals is to minimize the amount of information that a Pinecone node needs  in order to operate.  So they typically don't store much state.  They only need information about the spanning tree, their direct peers, and network paths  through the current node in order to work.  And this typically means that Pinecone nodes only have a few routing table entries, and  therefore they don't need much memory to run.  So why are we doing this?  Ultimately, we want PSPianatrix to be able to operate over a variety of transport, and  we want those transports to be basically invisible into the application layer.  It shouldn't matter how we connect to other nodes.  The goal is ultimately the same.  We just want to be able to address a node by its public key and to exchange traffic  with it.  This also means that we can bridge different transports together into a single network.  Nodes can have peers with different link types, and the application should be able to operate  without any real concern for how those links were set up.  And finally, there is a very sad trend at the moment of more and more internet users  being placed behind carrier-grade NATs and restrictive firewalls who don't stand a chance  if being able to accept incoming connections without the assistance of either some kind  of relay technology or an overlay network.  So this time last year, we introduced Pinecone, and it's a re-implementation of many of the  same ideas that were in development on the IGDRASOL network at the time, including tree  routing, pathfinding, source routing, and a new experimental routing scheme, which we  have now formed into SNAP.  Our initial pass at doing this was quite scratchy, to be honest, and in the end, we  also ended up just performing a complete rewrite of the Pinecone router code, which not only  made it much easier to reason about and to document, but it also meant that we solved  a number of performance issues and race conditions that we were seeing at the time.  In addition to that, we've also been maintaining builds of the peer-to-peer matrix demos for  iOS and for Android.  Now, these have gone through various iterations over the last couple of years using various  different routing protocols, and the latest builds are now using the latest Pinecone protocol  and code.  And these are available today to play with.  They're linked from the topic of the peer-to-peer matrix room, which is linked in the slide.  So to be honest, the experience of using the demo still isn't fantastic yet.  There are still a number of Android and matrix-specific issues that we need to work on, like how we  improved the Federation experience and cope with devices then coming and going, which  are fairly agnostic problems to the routing algorithm that's used.  The main design highlights of Pinecone are that it gives everybody a public key.  Their public key is their address on the network, and their address only changes if their key  is changed.  It gets very close to the concept of mobile IP in that you can move around the network  and roam, and yet your address stays the same.  All nodes on the network are considered to be pretty much equal players.  That is that everybody is forwarding traffic on behalf of the nodes around them.  And that allows us to reasonably arrive at the promise that all nodes can contact other  nodes.  Fast convergence times are also really important, especially in a network where we're dealing  with devices that move around a lot, like mobile phones, tablets, and laptops.  So the network must be able to update quickly when changes happen, preferably with the smallest  amount of disruption to the traffic that's already in transit on the network at that  time.  And we do this using proactive routing updates, which actually get us very close to that goal.  As I mentioned before, we also have very small routing tables, so it doesn't really take  a lot of resources to run or to embed a Pinecone node, and we're able to operate over pretty  much any transport that guarantees both reliability and ordering.  So we've successfully proven Pinecone working over TCP, over WebSockets, and over Bluetooth  low energy on the PCP and Matrix demos, and we should reasonably be able to support any  other link type that provides those same guarantees.  Each Pinecone node is participating in a global spanning tree.  The root node of the spanning tree is chosen by an iterative process, where the node with  the highest public key wins.  If that node disappears, the node with the next highest public key will be chosen to  take over the role, and so on.  And this means that the node that's chosen for the task will feel pretty much arbitrary  a lot of the time.  Now, the root node has exactly one special job.  They must send out root announcement packets to all of their directly connected peers with  their public key and a sequence number.  Other than that, the root node is just like any other node.  Now the sequence number that we send out must be increasing.  If the root node sends an update that looks strange in any way, for example, the sequence  number wasn't increasing, it was actually lower than the last update, or if the root  node just gives up sending root announcements altogether, then the next strongest key will  take over the root role after a timeout period.  All nodes in the network will receive root announcements from their peers, and they must  select a single parent before repeating the announcement from their chosen parent to all  of their peers.  And this means that the root public key and the sequence number are effectively flooded  to all nodes in the network.  Given that each node needs to sign the root announcement from their parent before passing  it on,  this means that every node on the network learns a verified path up to the root for  free with the spanning tree.  So as the root node is always the node with the highest public key, this means that we  always have at least one worst case ascending path up through key space.  Using the information in the root updates, this allows nodes to determine their own coordinates  on the spanning tree relative to the root node.  Now, the tree-routing algorithm is simple.  We just take our coordinates and the destination coordinates, we subtract the number of hearts  to the common ancestor, and then we add the lengths together.  And the tree-routing generally finds paths that are quite direct.  So you might be wondering, if nodes can assign themselves a locator from the spanning tree,  the coordinates, and the spanning tree forwarding algorithm provides fairly direct paths, isn't  that sufficient?  Sadly, the downside to this system is that if the coordinates are always relative to  your parent node on the spanning tree, that means if that parent disappears or a new bad  parent comes along or worse, the root node changes and causes a global shift on the network,  you get a new set of coordinates, and therefore you are no longer reachable at the previous  coordinates that you had.  And there's also the question of how you associate a public key of a node with a set of coordinates.  Now, earlier versions of the addressal network worked in exactly this way, and they mapped  keys to coordinates using a distributed hash table, but it was difficult to avoid the temporary  disruption and packet loss that would happen if the tree shifted.  That's where SNAC comes in.  Now, the tree-routing gives us a suitable topology to exchange setup messages with other nodes,  which we only need to do periodically.  So it doesn't really matter if the tree shakes too much otherwise.  The idea of the SNAC topology is to arrange nodes on the network into a virtual line,  where each node has a relationship with its key space nateless, that is, nodes with the  next key down from ours and nodes with the next key up.  Here we show the same network in two different views.  On the right-hand side, you'll see a network of nine nodes and how they are physically  connected to each other.  So node two is connected to nodes one, four, and eight.  Node four is connected to nodes two, three, and seven, and so on.  On the left-hand side, we show the SNAC topology.  That is, all of the nodes on the network arranged into a line, ordered by their public keys.  In this instance, the highest keys are to the left and the lowest keys are to the right.  So 883e is a higher key than 701e, and 9b67 is a higher key than 883e, and so on.  To illustrate how SNAC works, we're going to take a pair of nodes, five and seven, which  are highlighted on the diagram to the left.  These are key space neighbors.  There are no other nodes on the network with a public key that falls in the middle of those  two node's keys.  But you'll notice from the right-hand view that they aren't physically connected to  each other.  There are multiple nodes between those two nodes.  So what happens is that the node with the lower of the two keys, in this case node seven,  sends a bootstrap message into the network.  Bootstrap messages are forwarded to the node with the key that's closest to our own.  So in this case, that's node five.  Now, it's possible that node five already has a neighbor relationship with another node,  but that's okay.  If our new bootstrap message is from a node that's closer to node five's key than its  existing neighbor, we'll just replace that relationship with this new one.  The result is that node five's descending node entry, that is, the node with the next  lower public key, becomes node seven.  Likewise, node seven's ascending node entry, that is, the node with the next higher public  key, becomes node five.  So both nodes now reference each other.  To set up this relationship, they had to exchange path set up messages, and the nodes  that are in the middle, nodes one, two, and four, have forwarded those messages.  The intermediate nodes populate their routing table based on those set up messages.  So those three nodes will add routing table entries accordingly based on that set up.  As a result, they've learned about a new path between node five's public key and node  seven's public key.  Now, if you imagine that every pair of nodes on the network is doing the exact same thing,  as nodes set up past to their key space neighbors, the routing tables of other nodes on the network  are populating with more and more information about which directions they can travel in  order to reach certain keys.  So the routing logic after that is quite straightforward.  When we want to forward a packet, we just pick the routing table entry that has the  key that's closest to the one that we want to talk to, and we forward it there.  In this regard, it's not really dissimilar to how a distributed hash table relays messages  in order to get closer to a target content ID.  In order to keep the routing information up to date across the network, we do need to  react quickly when a path breaks.  So in the previous example, if one of the nodes in between nodes five and seven disappeared,  we need to notify everybody else that cares about that path, that it's now a dead path.  And we do this by sending dead-arm messages along the path, resulting in the routing table  entries for that path being deleted.  The key space neighbors then bootstrap again, using a different path if possible.  And this means that the network can heal very quickly and quite often without disruption  to traffic that's already in transit.  If a more direct path appears, there's still likely backup paths via less direct routes  available, so we'll just forward using those instead.  And because the node's public keys didn't change as a result of the new topology, we  don't need to scan the network in order to find the new location of that node.  We just trust that we can keep forwarding until we eventually reach the node in its  new location.  For this to work, and to not introduce routing loops while we do it, the core rule is that  the next hop for any routing decision must strictly take the packet closer to the destination  public key.  We will not backtrack.  Nor will we forward anything to a node whose key is further away from the destination key  than our own key is.  To make a routing decision, we use information from both the spanning tree and the snack  routing table.  In addition to that, we'll also look at the public keys of our direct peers and their  ancestors in the spanning tree.  And this gives us a pretty good spread of public keys to select from to make a routing  decision, so hopefully we can find one that's closer to the destination.  We'll also try our hardest to take shortcuts, if we can.  For example, if we notice that the destination key is actually one of our peers' ancestors  or is very close to it, we will shortcut via that peer instead.  In some cases, this helps us to shorten the path lengths that are taken in order to reach  the destination.  To examine how snack performs at finding paths, we measure the stretch.  Now, stretch is how many times longer the path is compared to the real-world dike-strah  shortest path through the network.  A stretch of two means that the path is twice as long as the shortest real path, therefore  lower numbers in a scenario of atta.  To do this, each node effectively runs a trace route to every other node on the graph, and  we measure how many hops it took.  The numbers displayed on the slides are mean averages.  The tree paths are used to set up snack-neighbor relationships, but really we're much more  interested in the length of the snack paths, since those are the paths that actual normal  traffic will take as opposed to protocol traffic.  On the left, we have a network of nodes that is generated completely at random.  There is no logic at all to how the nodes are connected to each other, and in this particular  network simulation, we see that the snack typically found paths that are on average  1.7 times the length of the real shortest path.  In the middle, we have a network that's designed to be completely uniform.  It's a perfect grid.  In here, snack-achieved paths on average about 1.57 times the length of the real shortest  path.  Finally, on the right, we have a real-world network, which is based on the Tri-Funk and  Leipzig using data from the National Lab graphs.  This is a sample of a real-world network topology, and here we achieved a path length that is  on average only 1.18 times longer than the real shortest path.  Real-world networks are actually yielding better results, which is very encouraging.  Stretch varies a lot with network topology and with key distribution, but the data tells  us that even in networks that aren't ideal at all, we still typically manage to find  paths that are no more than double the length of the real shortest path.  Moreover, we do this with nodes typically only having a handful of routing table entries.  To get a sense of how the routing scheme handles mobility scenarios, we use a number of tests  within the meshnet lab suite.  These spin up a bunch of nodes in virtual network namespaces, wire them together appropriately,  and then run scenarios on them.  One of the more aggressive tests in the suite for seeing how a protocol handles nodes moving  around is the mobility 2 test, which we've displayed here.  It starts by randomly placing all of the nodes in a square 1 kilometer by 1 kilometer grid,  and then it starts moving them around.  Between each set of movements, it runs pings from every node to every other node to determine  if they're all still reachable to each other after the movements have occurred.  And this should be a reasonably good indicator of how well the network converges after links  come and go.  The test starts by making smaller movements, so to start with, they only move at 50 meters.  But during the test, this increases the step distance up until we're moving as high as  400 meters, and that would significantly disrupt most wireless networks.  Now, as you can see from the graph, pinecone and green perform significantly better than  Batman advanced in orange and babel in red.  Batman, while holding quite strongly, still regularly loses up to 30% of the pings through  the test.  Babel performs significantly worse than that once the step distance increases over 50 meters.  The meshnet lab tests do only test a rather limited number of scenarios, and due to the  fact that each pinecone node has to run in its own process there, that can increase the  overheads and require quite a lot of compute resources just to run fairly small simulations.  Our answer to this is an integrated pinecone simulator in which we can run large numbers  of pinecone nodes within a single multithreaded process, and to be able to examine the internal  state of those nodes and the network as a whole.  Devon who joined our team recently has been spending quite a lot of time working on improving  the simulator and adding new features to it.  The web interface allows us to see how the network is forming in slow motion.  We can load any shape network into the simulator with any reasonable number of nodes and view  the various different topologies.  And this one is showing in slow motion how the network is arranging itself into a snack,  and then we'll add an additional node to show how that also merges in.  In reality, this is happening in under a second for a network of this size, but the fact that  the network converges on a single line means that all of the nodes on the network found  their key space natives successfully.  We can also simulate much bigger networks, and this is a totally random graph of 250  nodes with a whole bunch of pairings that are randomly set up between them in the spanning  tree view instead of the snack view.  The spanning tree forms almost instantly, which gives enough information to the nodes  to start bootstrapping the snack and communicate with other nodes to do so.  By the time we switch to the snack view, which at this point fairly well resembles the Windows  95 screensaver, we can see that most of the convergence has already happened, but a few  more key space neighbor relationships are still being built.  Being able to visualize what the network is doing in this way is actually really valuable.  It gives us a lot of insight into how the network converges and responds to certain conditions.  There's still quite a lot for us to do with the simulator here, but our goal is to be  able to use it to research and design mitigations against classic Eclipse and Sibyl style attacks,  as we'll be able to simulate how the network responds to those kinds of malicious actors.  We also plant our mechanisms for detecting packet loss, particularly of protocol level  traffic in the hope that we'll be able to route around nodes that deliberately cause  disruption and to make the bootstrap process more robust overall.  Source code for Pinecone and the simulator is available on GitHub in the Pinecone repository  linked here, and there is also a wiki on the same repository which contains quite a lot  of information about how the protocol itself works.  It does fall short of being a complete implementation guide at the moment, but it does give a pretty  good overview and rationale of how the spanning tree and the snack are set up and how they  function.  I've also spent quite a bit of time cleaning up and commenting the router code as well,  so hopefully that would be reasonably readable too.  I've also referred to the MeshNet lab multiple times and MATS linked here too.  It's a really useful tool for evaluating how a routing protocol converges in scales and  to be able to plot those results against other existing routing schemes.  And finally, there is the Peer-to-Peer Matrix Room where you can come and talk to us, and  also to find the links to the latest Peer-to-Peer damage.  That's all from me today.  Thank you so much for listening.  All right, so I don't know if people can hear us already.  It looks like there is wobbly 20, 25 seconds that we don't know if we are live or not.  So in the meantime, I'm not going to ask a significant question, but you can see me  dancing so you are not bored.  And it looks like we are live at least.  So the first question, of course, Neil, when is Peer-to-Peer going to be live?  We want Peer-to-Peer Matrix right now, please.  So I need to stress the point that Peer-to-Peer Matrix is still very early in development  at this point.  Working on Pankona is one of the ways that we're solving connectivity issues in disjoint  networks, ones that aren't necessarily reliable or ones that aren't necessarily internet  connected.  But there's still a lot of things that we need to solve before we'll be able to really  put the stamp on Peer-to-Peer Matrix and say, yeah, this is done.  This is usable.  All right, so we don't have Peer-to-Peer Matrix ready yet.  And when we say Peer-to-Peer Matrix, most of the time people have in mind the cool demos  that you have already showed on the iPhones, for example, or on Android, so mobile Peer-to-Peer.  But we do have an interesting question.  Is it possible to get Peer-to-Peer Matrix for the home servers, for existing home servers,  and does it make sense?  Yes, so this is something that's possible.  When we talk about the iOS and the Android demos, what they're actually running is an  embedded Android home server built into them.  And effectively all that happens there is that your client is just talking to a home  server that's running on the device.  There is no reason that we can't do this with static home servers that are running in data  centers.  And indeed, we do actually have a Dendrite profile that can run in that configuration  so you can just run a Dendrite process, but run it in P2P mode with Pinecone.  And we believe that probably that will be the start of how we transition over to P2P  Matrix in the future is that we start to provide an embedded Pinecone node or the necessary  logic for P2P Matrix into static home servers.  All right.  And the SNEC thing you have been showing us.  It's just for the transport and the connectivity of the different nodes.  Do we have challenges at the Matrix protocol spec level left to solve or is it working  already?  Because in the demo you show we can see messages being sent using Matrix using a specific element,  but it's not connected to the rest of the Federation.  So do we have things to solve?  Yeah.  I mean, there's quite a few problems that we still need to solve with our Matrix Federation  as a whole works because at the moment Matrix Federation is still very much designed around  the precedent that servers are online most of the time.  And of course, P2P Matrix just takes our assumption, just completely racks it.  So for instance, if your server has been offline for a period of time, you need to catch up  with missing state events, missing auth events, anything like that.  That at the moment would rely on having other servers available in the room to ask.  So our main sort of challenge here is to how do we change Matrix Federation so that it's  less reliant on other servers being online all of the time.  And that's the biggest challenge.  You'll notice this is a problem if you use the P2P demos for any period of time and you  then, you know, check the task into the background and go off and do something else and then  other people are chatting away in a room and then you come back later.  The way that it reconverges at the minute is still not great.  So that's the biggest Matrix problem, definitely.  All right.  So if we want that to work, we need to abolish tunnels.  We need to have network coverage all the time and we need to have very large batteries.  So the phone don't die.  Yeah.  And the idea is we need to avoid that.  You know, we need to try and do this in a way that has the least impact on people's batteries  and, you know, cellular connectivity.  Definitely.  We had a question from RevaLiber who asked, what happens if malicious actors generate  a key that is highest but refused to properly participate in the network?  That's a really interesting question, actually.  And the thing is, is that refusing to participate properly in the network is a vague thing.  There's a lot of different ways in which you could choose not to participate.  The main one being that you could just take on the root node role by having the highest  key and then just not send out updates or send out updates which are just obviously not  correct, you know, like we're saying in the presentation about sequence numbers not being  correct or anything like that.  What typically happens in that case is that other nodes on the network will just ignore  those updates and eventually they will time out on that root node specifically and then  the network will rearrange around something else.  Another big failure mode and one of the ones that we're trying to work on, particularly  when it comes to adversarial nodes, is what happens if nodes stay online but just choose  to selectively drop traffic, drop protocol messages, drop whatever.  And that's something that we're having to spend quite a bit of a time and effort on,  you know, how we fix that problem basically because we need nodes to try and identify  when a malicious actor is dropping protocol messages or trying to do something obviously  bad and route around it if possible.  And that's going to be one of the big areas that we're looking at, especially now that  we have the Pinecone simulator up to a standard that we can actually run these kinds of scenarios  without having to go out into the real world with hundreds or thousands of devices.  Okay, so it's quite a complex network and there is a question which, so the answer I  guess is it depends on many parameters but I'm still going to ask it anyway.  What do the latency and maximum bandwidth in a Snick world look like?  That really depends on the connectivity on the path that you're taking.  So if you have a bunch of devices that are strung together on very fast connections and  you're following the path that uses very fast connections, good bandwidth, low latency,  you will get very good bandwidth and very low latency.  If you're following paths that are definitely slower or much worse quality then obviously  that will be what happens to traffic following that path.  And also another area that we need to look at as well as if we can specifically avoid  taking very slow paths if we can manage it.  All right, we had a question from Timo which was very interesting.  Yes, the examples for physical topologies look like each node only has a few edges but  aren't most nodes connected to each other in the Internet?  I'm going to interpret this question as if you were sort of talking about the matrix  federations that works today which is that the matrix federation is pretty much full  mesh and that means if you're federating in a room you are talking to all of those servers  once and you can globally route to all of those servers.  In a Pinecom network obviously that's not necessarily true, a node can have one peering,  it could have 17 peering, it could have hundreds of peering.  And what we need to be able to do is to route traffic based on just whatever connectivity  we have available so that if you decide you need to talk to some other server with whatever  public key you just use the path that are available.  So I'm not really sure that there's a straightforward comparison to the Internet there.  Right, you showed a graph at some point comparing Pinecone to Batman Advanced and Babel.  Do you know if people who are working on this would be interested to contribute to Pinecone  and if they are interested in using Pinecone?  Admittedly, I have never spoken to any of the people involved in developing these routing  algorithms.  I would love to think that work that we're doing around Pinecone and also around the  address on network because that's a very big player in this.  Yeah, I'd like to think that that work will eventually spread outwards.  Right, and we have just a few seconds to say that we could not ask the question about  why this nickname, but there is a question and answer room which is going to open shortly  so you can ask all your questions to Neil.  See you in the next talk.
matrix_p2p_pinecone_0_323.png matrix_p2p_pinecone_324_395.png matrix_p2p_pinecone_396_779.png matrix_p2p_pinecone_780_3227.png matrix_p2p_pinecone_3228_7475.png matrix_p2p_pinecone_7476_10619.png matrix_p2p_pinecone_10620_12755.png matrix_p2p_pinecone_12756_23567.png matrix_p2p_pinecone_23568_25775.png matrix_p2p_pinecone_25776_26723.png matrix_p2p_pinecone_26724_26771.png matrix_p2p_pinecone_26772_26819.png matrix_p2p_pinecone_26820_27731.png matrix_p2p_pinecone_27732_28247.png matrix_p2p_pinecone_28248_28295.png matrix_p2p_pinecone_28296_31715.png matrix_p2p_pinecone_31716_31919.png matrix_p2p_pinecone_31920_32027.png matrix_p2p_pinecone_32028_32255.png matrix_p2p_pinecone_32256_32891.png matrix_p2p_pinecone_32892_34103.png matrix_p2p_pinecone_34104_34607.png matrix_p2p_pinecone_34608_35207.png matrix_p2p_pinecone_35208_35387.png matrix_p2p_pinecone_35388_36875.png matrix_p2p_pinecone_36876_37091.png matrix_p2p_pinecone_37092_37139.png matrix_p2p_pinecone_37140_37355.png matrix_p2p_pinecone_37356_37667.png matrix_p2p_pinecone_37668_39803.png matrix_p2p_pinecone_39804_40139.png matrix_p2p_pinecone_40140_40223.png matrix_p2p_pinecone_40224_41207.png matrix_p2p_pinecone_41208_41483.png matrix_p2p_pinecone_41484_42863.png matrix_p2p_pinecone_42864_43283.png matrix_p2p_pinecone_43284_43739.png matrix_p2p_pinecone_43740_44237.png