The Pinecone Overlay Network
matrix.org
matrix.org
- 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.
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.
We still don't have a good cross-platform way of doing that.
https://play.google.com/store/apps/details?id=io.sanford.wor...
https://github.com/psanford/wormhole-william-mobile
One disadvantage is that current magic wormhole doesn't support resume but they plan to implement it.
Another app that you might have heard of is croc, but it doesn't seem to be secure:
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.
[2] It seems possible to avoid this given that the Android device is providing the network: https://developer.android.com/reference/android/net/wifi/Wif...
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.
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).
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.
Wow, I cannot emphasize enough how happy I am to read this.
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.
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.
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.
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).
edit: meanwhile, https://spec.matrix.org/unstable/proposals/ is the index of all the spec changes which are in flight. and if you’re interested in understanding how the matrix spec evolves, https://m.youtube.com/watch?v=SFkZz60RRfc is an hour of yours truly trying to explain the process and its rationale.
Besides, Briar also protects your traffic by using Tor. Pinecone does not.
(This is based on word of mouth tho so I may have it totally wrong :)
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?
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.
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.