📅 Original date posted:2017-09-04
📝 Original message:
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 <billy.tetrud at gmail.com> 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
> <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
>
>
>
> _______________________________________________
> 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: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20170904/fe7bbb32/attachment-0001.html>;
Olaoluwa Osuntokun [ARCHIVE] /
npub19h…zkvn4
2023-06-09 12:47:32
in reply to nevent1q…p87s
Author Public Key
npub19helcfnqgk2jrwzjex2aflq6jwfc8zd9uzzkwlgwhve7lykv23mq5zkvn4Published at
2023-06-09 12:47:32Event JSON
{
"id": "05be27a2ddcbfdea4d2e90906967c020113f59e18b91cbd86dcf4c612b1f75a9",
"pubkey": "2df3fc2660459521b852c995d4fc1a93938389a5e085677d0ebb33ef92cc5476",
"created_at": 1686314852,
"kind": 1,
"tags": [
[
"e",
"5aeaee9ddc15df9f8a70950a328dd6303a385b4f9ef45240f6429a4f3d212c82",
"",
"root"
],
[
"e",
"6af01b84c1fb3754c698e9e543dcc3092f94d1ffe5abe52a8a67626135f81c70",
"",
"reply"
],
[
"p",
"0866a9dfe968ace2a1cf22ff20e534684828184e3a538212dddae2abbb41465f"
]
],
"content": "📅 Original date posted:2017-09-04\n📝 Original message:\nHi,\n\nWelcome to the mailing list!\n\nReplying here rather than the issue you filed on the lighting-rfc repo as\nI'd say this is a better venue to discuss matters such as this. The\nstructure of the mailing list may be a bit strange initially, but once you\nget over that hump, I think you'll find it's rather pleasant to use. Also,\nif you stick around, you'll find that most members of the Bitcoin\ndevelopment community use technical mailing lists such as this one to\nshare ideas, propose new solutions, analyze existing schemes, etc.\n\nThis list has been a bit lower traffic recently than compared to the past\nas many of us have locked ourselves in dungeons coding without pants as\nwe're rapidly approaching the first mainnet release of our various\nlightning node software. As a result, replies may have a bit of delay, but\nthat's nothing to fret about!\n\n\u003e I propose a protocol where each node knows about its own local network\n\u003e topology, and to find a final route, a transaction originator queries a\n\u003e number of its connections for routes to the intended destination.\n\nFor color, I'm one of the co-authors of the Flare paper. What you've\ndescribed in this email is close to the approach, but it utilizes a blind\nall-the-links flood towards the destination, rather than a DFS search\nguided by the distance metric proposed in the paper. One thing to note is\nthat Flare utilizes HORNET to allow senders to query their beacon nodes,\nand also nodes beyond the horizon of their beacon nodes in a private\nmanner. By using the bi-directional communication circuit, we maintain\nrequester anonymity, and don't force those performing search to reveal\ntheir identity nor intent. Also note that Flare itself also uses an\ninitial routing cache for a neighborhood of N nodes.\n\nWhat you've described here is essentially Dynamic Source Routing (DSR)[1],\nwith a mix of components from Fisheye State Routing (FSR) making it a\nhybrid protocol that combines reactive and proactive elements in order to\nachieve its goals.\n\nOur current stop-gap is a pure proactive protocol, meaning that nodes\ngather all link state data and then make forwarding and\nrouting decisions based off of that. The clear trade off (as you point\nout), is the increase in table state and bandwidth incurred due to keeping\nup with the announcements. The upside is that the latency observed when\nattempting payments to random sections of the graphs are minimized.\nAdditionally, as we have complete information, we can make more\nintelligent path finding decisions, and also ensure that we collect a\nredundant set of routes for each payment. By ensuring that we collect a\nset of routes with high path diversity, we have many options to fall back\nto in the case of a routing failure with one of the earlier routes in our\nset.\n\nHowever, protocols that have a reactive element for each circuit\nestablishment may not necessarily scale better. This is due to the\ncomputational overhead of circuit establishment. Particularly in your\nDSR+FSR combo as the flood proceeds in all directions. As a result,\ncircuit establishment may have latency in the seconds as each random\npayment may potentially need to flood out in the graph in search of the\ndestination. Without a sort of distance metric to guide the search, it\nmay wastefully explore non-relevant sections, further increasing payment\nlatency and overhead for all other nodes. Finally, one aspect to consider\nis how DoS-able schemes like this that require flooding for each circuit\nestablishment are.\n\n\u003e When a node wants to construct a route for a transaction:\n\u003e 2. It asks all the channels on the edge of its cached local view for\n\u003e their cheapest path\n\nSimply _asking_ nodes for a path to a destination defeats the point of\nusing onion routing at all. If one is prepared to make that tradeoff, then\nfar more scalable routing protocols can be explored as at that point, one\nwould move to distance vector based algorithms.\n\nVery happy to see that more folks are exploring alternative\nrouting/discovery solutions! In the future we'll definitely need to scale\nup the network.\n\nOne beauty of the way the system is laid out is that multiple\nheterogeneous routing protocols can be used within the network just as\nwithin the Internet (eBGP vs iBGP), so different sub-graphs can chose\nprotocols that achieve their goals in light of the various tradeoffs. I\nthink I'll follow up this post with a general survey of potential\napproaches I've come up with and come across in the literature along with\ntheir various tradeoffs, and possible paths forward for the network as a\nwhole.\n\n\n-- Laolu\n\n\n[1]: https://arxiv.org/pdf/1507.05724.pdf\n[2]: http://www.utdallas.edu/~ksarac/Papers/DSR.pdf\n[3]:\nhttp://nrlweb.cs.ucla.edu/publication/download/203/05_75_fisheye-state-routing-in.pdf\n\n\nOn Mon, Aug 21, 2017 at 6:09 PM Billy Tetrud \u003cbilly.tetrud at gmail.com\u003e wrote:\n\n\u003e Hey Guys,\n\u003e\n\u003e I'm testing this mailing list out for the first time, so I'm probably\n\u003e gonna be doing it wrong.\n\u003e\n\u003e I want to talk about route discovery and route generation in the lightning\n\u003e network. It seems there's a couple types of things going on with routing:\n\u003e\n\u003e - Super basic flood-the-network style routing to get things up and\n\u003e running, as I believe is implicitly proposed here:\n\u003e https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md\n\u003e - More involved research projects that may not reach fruition any time\n\u003e soon. Eg this:\n\u003e http://bitfury.com/content/5-white-papers-research/whitepaper_flare_an_approach_to_routing_in_lightning_network_7_7_2016.pdf\n\u003e\n\u003e I'd like to discuss a near-term approach that can replace the basic\n\u003e flood-the-network style route discovery, but isn't so complicated that it\n\u003e needs a ton of study and work. This won't be the end-all solution to route\n\u003e discovery, but should take us a lot further than flood-the-network.\n\u003e\n\u003e I propose a protocol where each node knows about its own local network\n\u003e topology, and to find a final route, a transaction originator queries a\n\u003e number of its connections for routes to the intended destination. By doing\n\u003e this, it means that nodes are *not* receiving or storing the entire network\n\u003e topology, which makes route discovery a lot less taxing on the network (in\n\u003e terms of bandwidth and storage space).\n\u003e\n\u003e To go into more detail...\n\u003e\n\u003e When a node joins the network:\n\u003e 1. it broadcasts its information to all its channels (pretty much as\n\u003e proposed here\n\u003e \u003chttps://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md\u003e)\n\u003e announcing its relevant channel information\n\u003e 2. it requests local network topology information from all its channels\n\u003e for information about channels 1 hop beyond its direct connection (ie it\n\u003e will receive information about which addresses those channels are connected\n\u003e to, and their related fee info / etc)\n\u003e 3. it then requests topology information for channels 2 hops beyond, etc\n\u003e until it has filled its cache to its satisfaction (the user can choose some\n\u003e amount of megabytes as its limit of network topology data to store)\n\u003e 4. it also subscribes to topology changes for nodes at those distances (eg\n\u003e if a node has requested information from 3 hops away, it will receive info\n\u003e about any new channels or removed channels that fall within that distance)\n\u003e\n\u003e When a node receives an announcement message from a node joining the\n\u003e network:\n\u003e 1. it will store that node's info in its cache\n\u003e 2. it will also forward that info to any node that's subscribed to\n\u003e topology changes that fall within the relevant distance\n\u003e\n\u003e When a node wants to construct a route for a transaction:\n\u003e 1. It checks to see if it has a path to that node in its cache. If it\n\u003e does, it finds the cost of the cheapest path it has.\n\u003e 2. It asks all the channels on the edge of its cached local view for their\n\u003e cheapest path (however you want to define cheapest), specifying that it\n\u003e only care about paths with a maximum cost of the cheapest path it has\n\u003e already found in its cache. For example, if the node has nodes up to 3 hops\n\u003e away in its cache, it will *only* ask the nodes 3 hops away (it will not\n\u003e ask its direct connections, nor nodes 2 hops away, since it already has\n\u003e enough information to ignore them)\n\u003e 3. When it gets all its responses, it constructs a path\n\u003e\n\u003e When a node receives a path request from a node:\n\u003e 1. It checks its cache for its cheapest cache-only path\n\u003e 2. It asks nodes on the edge of its cached local view for their cheapest\n\u003e path, specifying that it only cares about paths with a maximum cost of\n\u003e either its cheapest cache-only path or the max-cost specified by the\n\u003e requesting node minus the channel cost between it and the requesting node\n\u003e (whichever is cheaper). A node on the edge of its cached local view is\n\u003e *not* asked for route information if the cost to that node exceeds the\n\u003e max-cost this relay node would specify.\n\u003e 3. It reports the results that satisfy the max-cost requirements of the\n\u003e requesting node\n\u003e\n\u003e And that's it. All the route information can be encrypted and signed so\n\u003e relaying nodes can't read the information inside, and so the requesting\n\u003e source node can verify which nodes sent that information.\n\u003e\n\u003e This protocol should keep both node-announcement messages *and* route\n\u003e request messages highly localized.\n\u003e\n\u003e Thoughts?\n\u003e\n\u003e ~BT\n\u003e\n\u003e\n\u003e\n\u003e _______________________________________________\n\u003e Lightning-dev mailing list\n\u003e Lightning-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev\n\u003e\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20170904/fe7bbb32/attachment-0001.html\u003e",
"sig": "e4054fe5827cf213754f2cd31aee3682697a74990d49144df9269182ac2c6086412440ebb123fb82ed83ebbe051519a195142c19b725fb4adfcf83256f2ff5c5"
}