From billy.tetrud at gmail.com Mon Sep 4 20:48:54 2017 From: billy.tetrud at gmail.com (Billy Tetrud) Date: Mon, 4 Sep 2017 13:48:54 -0700 Subject: [Lightning-dev] Route finding and route generation In-Reply-To: References: Message-ID: Thanks for the information Laolu! I'm glad people smarter than me are working on this : ) . Do you have any idea when Flare might be ready for real-world use? ~BT On Mon, Sep 4, 2017 at 1:02 PM, Olaoluwa Osuntokun wrote: > Hi, > > Welcome to the mailing list! > > Replying here rather than the issue you filed on the lighting-rfc repo as > I'd say this is a better venue to discuss matters such as this. The > structure of the mailing list may be a bit strange initially, but once you > get over that hump, I think you'll find it's rather pleasant to use. Also, > if you stick around, you'll find that most members of the Bitcoin > development community use technical mailing lists such as this one to > share ideas, propose new solutions, analyze existing schemes, etc. > > This list has been a bit lower traffic recently than compared to the past > as many of us have locked ourselves in dungeons coding without pants as > we're rapidly approaching the first mainnet release of our various > lightning node software. As a result, replies may have a bit of delay, but > that's nothing to fret about! > > > 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. > > For color, I'm one of the co-authors of the Flare paper. What you've > described in this email is close to the approach, but it utilizes a blind > all-the-links flood towards the destination, rather than a DFS search > guided by the distance metric proposed in the paper. One thing to note is > that Flare utilizes HORNET to allow senders to query their beacon nodes, > and also nodes beyond the horizon of their beacon nodes in a private > manner. By using the bi-directional communication circuit, we maintain > requester anonymity, and don't force those performing search to reveal > their identity nor intent. Also note that Flare itself also uses an > initial routing cache for a neighborhood of N nodes. > > What you've described here is essentially Dynamic Source Routing (DSR)[1], > with a mix of components from Fisheye State Routing (FSR) making it a > hybrid protocol that combines reactive and proactive elements in order to > achieve its goals. > > Our current stop-gap is a pure proactive protocol, meaning that nodes > gather all link state data and then make forwarding and > routing decisions based off of that. The clear trade off (as you point > out), is the increase in table state and bandwidth incurred due to keeping > up with the announcements. The upside is that the latency observed when > attempting payments to random sections of the graphs are minimized. > Additionally, as we have complete information, we can make more > intelligent path finding decisions, and also ensure that we collect a > redundant set of routes for each payment. By ensuring that we collect a > set of routes with high path diversity, we have many options to fall back > to in the case of a routing failure with one of the earlier routes in our > set. > > However, protocols that have a reactive element for each circuit > establishment may not necessarily scale better. This is due to the > computational overhead of circuit establishment. Particularly in your > DSR+FSR combo as the flood proceeds in all directions. As a result, > circuit establishment may have latency in the seconds as each random > payment may potentially need to flood out in the graph in search of the > destination. Without a sort of distance metric to guide the search, it > may wastefully explore non-relevant sections, further increasing payment > latency and overhead for all other nodes. Finally, one aspect to consider > is how DoS-able schemes like this that require flooding for each circuit > establishment are. > > > When a node wants to construct a route for a transaction: > > 2. It asks all the channels on the edge of its cached local view for > > their cheapest path > > Simply _asking_ nodes for a path to a destination defeats the point of > using onion routing at all. If one is prepared to make that tradeoff, then > far more scalable routing protocols can be explored as at that point, one > would move to distance vector based algorithms. > > Very happy to see that more folks are exploring alternative > routing/discovery solutions! In the future we'll definitely need to scale > up the network. > > One beauty of the way the system is laid out is that multiple > heterogeneous routing protocols can be used within the network just as > within the Internet (eBGP vs iBGP), so different sub-graphs can chose > protocols that achieve their goals in light of the various tradeoffs. I > think I'll follow up this post with a general survey of potential > approaches I've come up with and come across in the literature along with > their various tradeoffs, and possible paths forward for the network as a > whole. > > > -- Laolu > > > [1]: https://arxiv.org/pdf/1507.05724.pdf > [2]: http://www.utdallas.edu/~ksarac/Papers/DSR.pdf > [3]: http://nrlweb.cs.ucla.edu/publication/download/203/05_ > 75_fisheye-state-routing-in.pdf > > > On Mon, Aug 21, 2017 at 6:09 PM Billy Tetrud > wrote: > >> Hey Guys, >> >> I'm testing this mailing list out for the first time, so I'm probably >> gonna be doing it wrong. >> >> I want to talk about route discovery and route generation in the >> lightning network. It seems there's a couple types of things going on with >> routing: >> >> - Super basic flood-the-network style routing to get things up and >> running, as I believe is implicitly proposed here: https://github.com/ >> lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md >> >> - More involved research projects that may not reach fruition any >> time soon. Eg this: http://bitfury.com/content/5-white-papers- >> research/whitepaper_flare_an_approach_to_routing_in_ >> lightning_network_7_7_2016.pdf >> >> >> I'd like to discuss a near-term approach that can replace the basic >> flood-the-network style route discovery, but isn't so complicated that it >> needs a ton of study and work. This won't be the end-all solution to route >> discovery, but should take us a lot further than flood-the-network. >> >> 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). >> >> To go into more detail... >> >> When a node joins the network: >> 1. it broadcasts its information to all its channels (pretty much as >> proposed here >> ) >> announcing its relevant channel information >> 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) >> 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) >> 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) >> >> When a node receives an announcement message from a node joining the >> network: >> 1. it will store that node's info in its cache >> 2. it will also forward that info to any node that's subscribed to >> topology changes that fall within the relevant distance >> >> When a node wants to construct a route for a transaction: >> 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. >> 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) >> 3. When it gets all its responses, it constructs a path >> >> When a node receives a path request from a node: >> 1. It checks its cache for its cheapest cache-only path >> 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. >> 3. It reports the results that satisfy the max-cost requirements of the >> requesting node >> >> And that's it. All the route information can be encrypted and signed so >> relaying nodes can't read the information inside, and so the requesting >> source node can verify which nodes sent that information. >> >> This protocol should keep both node-announcement messages *and* route >> request messages highly localized. >> >> Thoughts? >> >> ~BT >> >> >> >> _______________________________________________ >> Lightning-dev mailing list >> Lightning-dev at lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev >> > -------------- next part -------------- An HTML attachment was scrubbed... URL: