Billy Tetrud [ARCHIVE] on Nostr: 📅 Original date posted:2017-08-21 📝 Original message: Hey Guys, I'm testing ...
📅 Original date posted:2017-08-21
📝 Original message:
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
<https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md>;)
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20170821/c3f18091/attachment-0001.html>;
📝 Original message:
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
<https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md>;)
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20170821/c3f18091/attachment-0001.html>;