Hey, I worked in a related research field a few years ago and published some of the results. Here are some ideas I find important:
- Generally I found that overlay DHT based routing is not very scalable for large graphs. It performs well for random looking graphs, but becomes very inefficient for large planar-like graphs. If pinecone is designed for small local networks, it might work well, but it will probably not scale well to large networks with the current design.
My intention in dealing with planar networks is mostly the case of deploying a local mesh network. Most mesh networks behave like planar graphs. Not sure if this is an actual use case for matrix though.
Amazing, I've been long hoping for a popular messenger to adopt seamless mesh/p2p integration.
Being able to chat in a train/on an airplane without wifi, between a convoy of cars without cell signal etc. seems like a no-brainer, especially with medium-distance unlicensed spectrum radios becoming more widely available.
I was always expecting Apple to enable this for iMessage first, but maybe this is something that can help Matrix get more traction.
It would be great to have an mobile version of magic wormhole, though sadly I'm not an app developer so while I would really like to implement it, it's outside of my skillset.
For Android, there is one from Peter Sanford (psanford on HN). He implemented the Go version of magic-wormhole, which I think is used by people like tptacek. So I guess it can be trusted.
The biggest problem here is that Apple unfortunately doesn't provide any API for peer-to-peer wi-fi access [1], as far as I know.
This means that all solutions will either require sender and receiver being connected to the same wi-fi network (possibly provided by one of the devices involved, which is pretty awkward and also has its downsides like unintentionally sharing the internet connection [2]), or resorting to Bluetooth LE (resulting in extremely slow connection speeds not really suitable for file transfer).
Finally, any solution requiring installing a third-party app has an inherent growth impediment given that sharing the app itself is all but impossible when offline.
[1] Wi-Fi Direct would seem to be ideal for this use case but is Android only, and even there does not seem to reliably work on all devices. Even Google's native AirDrop alternative resorts to using mobile data in some circumstances/device combinations.
Apple do provide two APIs for peer-to-peer Wi-Fi access — one of them is the Multipeer Connection Framework and the other is the NetService API with the “includesPeerToPeer” parameter. This only really helps us when talking to other Apple devices though as the AWDL protocol is proprietary.
The Wi-Fi Alliance have been trying to standardise something not dissimilar to AWDL under the name “Wi-Fi Aware” (NAN/Neighbour Awareness Networking), but it is not widely implemented and will probably never be supported by Apple either, limiting cross-platform potential.
Oh, if you simply want to send files from a command line utility to a browser and vice versa, may I recommend WebWormhole [1]?
There is both a webapp (which works on mobile browsers) and a command line client. The command line client can even display ASCII QR codes for easy access on mobile devices.
The only problem is long-running background uploads/downloads, but I don't think a mobile app could help there (at least on iOS).
I've been mostly ignoring and periodically checking back on Matrix to see when they get real decentralized identity and the ability to run with only RasPi grade hardware.... Hasn't happened yet but I'm still hopeful!
Applications are definitely the big problem with mesh. No point in using mesh if the only applications either don't support it well at all, or are such bandwidth hogs you wouldn't want to use them on anything but fiber.
I have wikis and notetaking mostly working in a Yggdrasil aware manner in my HardlineP2P app(Only on the github version for now), eventually I am hoping to add chat and social media.
> If Pinecone works out, our intention is to collaborate with the libp2p and IPFS team to incorporate Pinecone routing into libp2p (if they'll have us!) while incorporating their gossipsub routing to improve Matrix federation... and get the best of both worlds :)
Wow, I cannot emphasize enough how happy I am to read this.
Networks that need to constrain themselves to limited typologies to avoid traffic magnification do so at the expense of robustness, especially against active attackers that grind their identifiers to gain privileged positions.
Maybe this is a space where efficient reconciliation ( https://github.com/sipa/minisketch/ ) could help-- certainly if the goal were to flood messages to participants reconciliation can give almost optimal communication without compromising robustness.
Hi all, author here! I haven’t really had the opportunity yet to actually sit down and document how the routing algorithm works in plain English (or indeed to write a specification for what is still not a finalised protocol), but I’d like to give a quick primer on what’s actually happening under the hood.
First of all, we actually have two topologies at play here: a global spanning tree and a snake/line. The spanning tree is very cheap to set up. Effectively the node with the highest public key becomes the root, you derive your coordinates on the tree as the path from the root down to your node, and as long as you know the coordinates of all of your direct peers, you can route “towards” a set of coordinates without really knowing anything else. This is largely what the Yggdrasil Network does today, in case you think it’s familiar.
The problem is that if the root node changes, or any of your direct ancestors between you and the root, so does the entire coordinate system and that’s fairly catastrophic. Imagine having a TCP session open but both you and the remote side’s IP addresses change at the same time — it’s very difficult to recover from that and is therefore terrible for node mobility. But for one-off bursts, like sending the odd control messages, it’s pretty much ideal given the low cost, and the stretch factor of these routes is generally super low (below 1.1) so they are quite direct in real terms.
Then we have the snake (where the SNEK acronym came from), which is effectively a line topology where all of the nodes are sorted into a line by their public keys in sequence. The actual routing paths that we use for Matrix federation traffic are built up by nodes looking for their immediate keyspace neighbours (nodes with keys that are very close to their own), even if they aren’t direct peers. Then setup messages are sent using the coordinate routing system from the spanning tree from nodes to their keyspace neighbours. These setups take fairly direct paths thanks to the low stretch of the spanning tree routing. Intermediate nodes on the path “snoop” on these setup messages to populate their own routing tables with entries for that given key.
When a node finally wants to send a packet to a public key, we consult the routing table at each hop for entries that take us to a key that is strictly closer to the destination key and then send the packet onto the peer that the setup message came from. As paths are built up between neighbours, more and more shortcuts become available to intermediate nodes so the routes become more direct. In addition to that, we also can synthesise routes up to higher keys by looking at which peer spanning tree announcements came from, since we know that the root node has the highest key and is therefore effectively the end of the line.
We believe that the scheme should scale reasonably well because we can quite effectively limit the amount of knowledge that a node needs to have about the rest of the network and still have it function (they ultimately only need to know about their keyspace neighbours, the root node and their direct peers, a handful of transitive paths to different parts of keyspace — anything else is merely a bonus) and because we’re learning most of the routing information by snooping, we can keep the amount of protocol traffic down. (At the very least, it is not artificially increased by communicating with lots of other nodes on the network). It also responds quite well to topology changes because when a node moves, it can send new setup packets to help the network build new paths, and there’s still a reasonable chance that the old paths will be roughly helpful at getting somewhere close to where the node was/is, up until the paths expire/time out.
Ultimately it is still experimental though and an active area of research for us, so we’ll see how it goes!
Does the protocol have any kinds of countermeasures for bad actors? As an attacker, it looks like I could easily insert malicious nodes into the spanning tree in-between any pair of honest nodes with relative ease. From there, I could do things like:
* Selectively drop (censor) messages
* Gather message arrival-time and size data in a bid to deanonymize users
* Partition the network, denying service
* Eclipse a set of victim nodes, thereby allowing me to decide who they talk to
If your threat model includes node operators who can do this, one way you could at least make it harder for them to pull it off is to focus on reachability. You could make it so nodes discover the full set (or near enough the full set) through a random k-regular flood network, and have them rebuild a random spanning tree in regular intervals to "shake off" attackers. In addition, you'd want to find a way to make node ID generation both slow and expensive, so the attacker can't overwhelm the flood network with garbage state. As long as the total number of node IDs is small and grows at a bound rate, peers could feasibly learn the IP addresses of all other peers, and stave off partitions and deliberate route breakage.
At the moment we don’t have much in the implementation that actively avoids these kinds of attacks. If protocol messages are dropped then this will interrupt the bootstrap and path setup processes, which also is a kind of damage limitation. If a bad actor selectively dropped traffic but kept passing protocol messages then that’s much more of an issue. In that case the logical thing to do is to try and route via another peer that may take another (albeit slightly less direct) path. Partitioning the network is also quite difficult because all it would take is a single set of good paths through the network for the spanning tree to converge on the real strongest key.
Key generation is an interesting point though - right now generating ed25519 keys is cheap and it may be possible to flood the network with lots of nodes, but it still doesn’t really constitute a complete attack, as other genuine nodes may still end up making routing decisions that repair the path. We will need to study it more and simulate it.
We do have an entire list of scenarios to work through but some of these will hopefully be solved at the Pinecone layer and others will be solved at the Matrix layer (i.e. right now full-mesh federation, like what Matrix has today, is wholly impractical for P2P so we will need to do better).
This is by no means a finished product - it’s effectively a research project at this stage and we still have a lot to do to reach the P2P Matrix goal.
I'm no expert but to this moderately-informed layperson, this sounds like a pretty resilient approach. Thank you for sharing tbese details -- and good luck!
So should you assume a linear cost (in terms of latency) in the distance in the key space ? This looks like a weird tor overlay network, to be honest, with everyone on a line…
Also: is there some white paper / RFC explaining all the rational ? It seems matrix always put the implementation before the specification, which seems a bit weird (and might be why you already have like 5 version of objects such as rooms).
Not exactly — the line topology is effectively a “minimum” topology, whereas the bulk of the actual routing knowledge is built up from keyspace neighbours searching for each other and creating virtual paths via intermediate nodes.
trying to implement it first seems sensible to me as you want to ensure you have a concept that works in practice before you put it into an official specification
yeah, the whole point is that we demonstrate that stuff works before formalising it in the spec. Pinecone itself is pretty early (and keeps changing) though and hasn’t even got an informal spec yet. But we will soon!
Briar rocks. But the point of Pinecone is to take any Matrix client/bridge/bot and make it work P2P as well as client-server, which is a slightly different proposition.
The chain is effectively ordering the nodes by public key, with the head of the line being the highest public keys and the tail of the line being the lowest ones. Nodes bootstrap by looking for their keyspace neighbours and building paths to them, which intermediate nodes will track in their routing tables, so at each hop, you effectively route “towards” a public key based on the known paths.
I’m confused. Is this designed to provide anonymity? If not, why not send messages directly to the target’s IP address rather than go through a bunch of hops?
So that you don't need n connections to communicate with n servers, which won't scale past a few thousand servers (probably even less if you also consider that the idea is have phones run the p2p server on mobile data connections).
This is not designed to provide anonymity. You don’t send messages directly to the target’s IP because they are likely not to be directly routable - eg they could be only contactable via Bluetooth Low Energy, or an adhoc wifi segment, with no clearnet IP routing connecting them to the ‘net. So you use pinecone to route instead.
there are two topologies - one is a global spanning tree, similar to yggdrasil. but then the chain (or snake) simply orders the nodes which are close on the spanning tree numerically based on their public key, and routes via them even if the spanning tree topology changes. So you’re basically swapping between the two topos based on what works best.
(This is based on word of mouth tho so I may have it totally wrong :)
It’s not just that each node has two routing table entries - there are more routes available than just the keyspace neighbours. There are also plenty of transitive paths from other nodes seeking out their keyspace neighbours, and routes to the spanning tree root and ancestors that you learn effectively for free. It is actually surprisingly robust in the testing we have performed so far (some simulation, some with real world devices).
Yes. If nodes disappear then the next bootstrap packets, which currently run at a set interval, will find the next nearest keyspace neighbours and then sending setup packets will allow the network to build new paths. Similarly, the spanning tree also recovers by creating parent-child relationships using functioning paths.
I have been working on a similar project here: https://github.com/inet256/inet256
The focus is more on establishing an upward facing API, to develop p2p applications against. You can write your p2p app in whatever language and just connect to the INET256 service. It makes it pretty easy to experiment with a new routing algorithm, and eliminates much of the peering and transport security boilerplate.
Is Pinecone intended as a Go library, or will it eventually run as a separate process like Yggdrasil?
How will this be exposed to the other matrix applications, which AFAIK are not written in Go?
The current implementation is written in Go largely because it was the obvious choice for integration into Dendrite, the next-generation Matrix homeserver, which is embedded into the Element P2P demos.
Pinecone currently exports a net.PacketConn, and for the sake of Matrix federation transport, we layer on uTP+TLS on top to give us encrypted stream-oriented connections for HTTP. If we are successful at achieving our goals then we will write a formal protocol specification and assist with the creation of other implementations.
Peer-to-peer routing is challenging because you aren't sure where to send your data to reach your peer, even if you know their cryptographic public key and address. It's hard because the network physically is splayed out in a big hub-and-spoke tree. A node might know who it's physical neighbors are, but does not necessarily know much about there locations of any of its peers.
If a router receives a peer-to-peer packet, where should it send this packet? With pinecone, this is answered by looking at a cheatsheet, where each node is assigned a specific virtual neighbor that they are in charge of finding among the physical routing tree. This cheatsheet is generated by connecting neighbors who are ordered by their cryptographic public keys.
As peers find routes to their neighbors, they are also discovering routes to other nodes along the chain, helping speed up the entire process of deciding where to send packets.
This is a great explanation. The only missing bit is that the nodes also find routes based on the spanning tree calculated over the network as well as hunting their neighbours on the snake.
I spent a solid 5 minutes trying to get what this project had to do with the Pinecone board, the BL602 based dev board by Pine64.org. In my head IoT over secure decentralized channels made sense, so it had to be a connection somewhere:)
- Generally I found that overlay DHT based routing is not very scalable for large graphs. It performs well for random looking graphs, but becomes very inefficient for large planar-like graphs. If pinecone is designed for small local networks, it might work well, but it will probably not scale well to large networks with the current design.
- With a small local hack to the Chord network, it is possible to achieve eventual connectivity, see here: https://www.freedomlayer.org/articles/chord_connected_routin...
Other pieces can be found here: https://www.freedomlayer.org/research/ Of special importance are the experiments performed to large networks, which can be found on this page: https://www.freedomlayer.org/research/landmarks-lookahead/
If anyone from the matrix team is reading this, I will be happy to help if any help if needed.