<div dir="ltr">Hey Guys,<div><br></div><div>I&#39;m testing this mailing list out for the first time, so I&#39;m probably gonna be doing it wrong.</div><div><br></div><div>I want to talk about route discovery and route generation in the lightning network. It seems there&#39;s a couple types of things going on with routing:</div><div><ul><li>Super basic flood-the-network style routing to get things up and running, as I believe is implicitly proposed here: <a href="https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md">https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md</a><br></li><li>More involved research projects that may not reach fruition any time soon. Eg this: <a href="http://bitfury.com/content/5-white-papers-research/whitepaper_flare_an_approach_to_routing_in_lightning_network_7_7_2016.pdf">http://bitfury.com/content/5-white-papers-research/whitepaper_flare_an_approach_to_routing_in_lightning_network_7_7_2016.pdf</a><br></li></ul><div>I&#39;d like to discuss a near-term approach that can replace the basic flood-the-network style route discovery, but isn&#39;t so complicated that it needs a ton of study and work. This won&#39;t be the end-all solution to route discovery, but should take us a lot further than flood-the-network.</div></div><div><br></div><div>I propose a protocol where each node knows about its own local network topology, and to find a final route, a transaction originator queries a number of its connections for routes to the intended destination. By doing this, it means that nodes are *not* receiving or storing the entire network topology, which makes route discovery a lot less taxing on the network (in terms of bandwidth and storage space). </div><div><br></div><div>To go into more detail...</div><div><br></div><div>When a node joins the network:</div><div>1. it broadcasts its information to all its channels (pretty much <a href="https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md">as proposed here</a>) announcing its relevant channel information</div><div>2. it requests local network topology information from all its channels for information about channels 1 hop beyond its direct connection (ie it will receive information about which addresses those channels are connected to, and their related fee info / etc)</div><div>3. it then requests topology information for channels 2 hops beyond, etc until it has filled its cache to its satisfaction (the user can choose some amount of megabytes as its limit of network topology data to store)</div><div>4. it also subscribes to topology changes for nodes at those distances (eg if a node has requested information from 3 hops away, it will receive info about any new channels or removed channels that fall within that distance)</div><div><br></div><div>When a node receives an announcement message from a node joining the network:</div><div>1. it will store that node&#39;s info in its cache</div><div>2. it will also forward that info to any node that&#39;s subscribed to topology changes that fall within the relevant distance</div><div><br></div><div>When a node wants to construct a route for a transaction:</div><div>1. It checks to see if it has a path to that node in its cache. If it does, it finds the cost of the cheapest path it has.</div><div>2. It asks all the channels on the edge of its cached local view for their cheapest path (however you want to define cheapest), specifying that it only care about paths with a maximum cost of the cheapest path it has already found in its cache. For example, if the node has nodes up to 3 hops away in its cache, it will *only* ask the nodes 3 hops away (it will not ask its direct connections, nor nodes 2 hops away, since it already has enough information to ignore them)</div><div>3. When it gets all its responses, it constructs a path</div><div><br></div><div>When a node receives a path request from a node:</div><div>1. It checks its cache for its cheapest cache-only path </div><div>2. It asks nodes on the edge of its cached local view for their cheapest path, specifying that it only cares about paths with a maximum cost of either its cheapest cache-only path or the max-cost specified by the requesting node minus the channel cost between it and the requesting node (whichever is cheaper). A node on the edge of its cached local view is *not* asked for route information if the cost to that node exceeds the max-cost this relay node would specify.</div><div>3. It reports the results that satisfy the max-cost requirements of the requesting node</div><div><br></div><div>And that&#39;s it. All the route information can be encrypted and signed so relaying nodes can&#39;t read the information inside, and so the requesting source node can verify which nodes sent that information. </div><div><br></div><div>This protocol should keep both node-announcement messages *and* route request messages highly localized.</div><div><br></div><div>Thoughts? </div><div><br></div><div>~BT</div><div><br></div><div><br></div><div><br></div></div>