[HN Gopher] The Pinecone Overlay Network
___________________________________________________________________
The Pinecone Overlay Network
Author : vanburen
Score : 178 points
Date : 2021-05-07 16:27 UTC (6 hours ago)
(HTM) web link (matrix.org)
(TXT) w3m dump (matrix.org)
| lxgr wrote:
| 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.
| the_duke wrote:
| Sharing files is also a great use case.
|
| We still don't have a good cross-platform way of doing that.
| squarefoot wrote:
| 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:)
| Arathorn wrote:
| (also https://news.ycombinator.com/item?id=27061804)
| realcr wrote:
| 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.
|
| - 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.
| neilalexander wrote:
| This is an interesting set of resources, I shall certainly be
| reviewing them. Thanks!
| neilalexander wrote:
| 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!
| jude- wrote:
| Thanks for taking the time to write this primer!
|
| 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.
| neilalexander wrote:
| 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.
| cpr wrote:
| Is there some ELI5 overview for this intriguing work?
| kickscondor wrote:
| Perhaps look here (at the 7:52 mark):
| https://fosdem.org/2021/schedule/event/matrix_pinecones/
| thelucky41 wrote:
| 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.
| Arathorn wrote:
| 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.
| anticensor wrote:
| Matrix desparately needs a superstabilising server-to-
| server link establishment and breakup algorithm.
| brendoncarroll wrote:
| 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?
| neilalexander wrote:
| 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.
| Reventlov wrote:
| 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).
| kitkat_new wrote:
| 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
| Arathorn wrote:
| 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!
|
| 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.
| neilalexander wrote:
| 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.
| yjftsjthsd-h wrote:
| I'm confused - their p2p model forms a chain with each node only
| using 2 peers? Isn't that really fragile?
| [deleted]
| Arathorn wrote:
| 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 :)
| anticensor wrote:
| That is still fragile.
| neilalexander wrote:
| 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).
| anticensor wrote:
| Is it self-stabilising?
| neilalexander wrote:
| 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.
| neilalexander wrote:
| 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.
| goodpoint wrote:
| How is this better than Briar? https://briarproject.org/
|
| Besides, Briar also protects your traffic by using Tor. Pinecone
| does not.
| Arathorn wrote:
| 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.
___________________________________________________________________
(page generated 2021-05-07 23:00 UTC)