6

Here is all we can find in the Lightning Network whitepaper about payment routing process that it is completely unclear to me (at least it is not enough to know what happens exactly at time of finding the best optimized path for a payment between two users):

"It is theoretically possible to build a route map implicitly from observing 2-of-2 multisigs on the blockchain to build a routing table. Note, however, this is not feasible with pay-to-script-hash transaction outputs, which can be resolved out-of-band from the bitcoin protocol via a third party routing service. Building a routing table will become necessary for large operators (e.g. BGP, Cjdns). Eventually, with optimizations, the network will look a lot like the correspondent banking network, or Tier-1 ISPs. Similar to how packets still reach their destination on your home network connection, not all participants need to have a full routing table. The core Tier-1 routes can be online all the time —while nodes at the edges, such as average users, would be connected intermittently. Node discovery can occur along the edges by pre-selecting and offering partial routes to well-known nodes."

I am looking for a document explaining step by step the current routing process used in current Lightning Network to know the steps for finding the best optimized path when user A wants to send an off-chain payment to user B.

P.S. I know that it is possible to use any other routing algorithm as a plug-in; however, I would like to know the current routing protocol used in the current Lightning Network in details (step by step). I also appreciate it if you could propose a document explaining the current routing algorithm in Lightning Network. Thank you

Improve this question

1 Answer 1

Reset to default
9

There's no document explaining step-by-step, because the routing decisions are not part of the protocol (the BOLTs). It is purely client-side decision making about how to find a route through the graph, and any client can choose to implement their own mechanisms. There is no compatibility issues because only the payer makes routing decisions, and intermediate hops merely forward packets as requested.

If you wish to know the specific details of how LND, c-lightning etc implement it, you will need to dig into the code and documentation for those projects.

As far as I'm aware, the current implementations all use a variant of Dijstra's algorithm, or A*, taking the routing fees as the heuristic to minimize when calculating the weights of each path, and c-lightning uses the Bellman-Ford modification in the link above.

Once a path has been calculated by the payer, there is a standard process by which the path and the packets for it are constructed, defined in BOLT#4.

Improve this answer
11
  • And do you know if this approach has been already used/implemented in Lightning Network? (bitfury.com/content/downloads/…) Thank you
    – Questioner
    Dec 19, 2018 at 10:03
  • 2
    The primary issue with source based routing is that the payee needs a full copy of the routing table, or needs to query information about channels and nodes from somebody who does have it, which leaks information and is bad for privacy. While the network is small with limited growth, this isn't really a problem because the routing information is only a few MB. When we start to get node counts in millions and channel counts of billions, it is obviously not going to be practical for each node to have a fully copy of the routing information, and nor will they have the bandwidth to transfer it.
    – Mark H
    Dec 20, 2018 at 14:51
  • 1
    Flare has possible issues w.r.t privacy, and it also treats some nodes as a kind of "privileged" node. People involved in the LN development wish to avoid this and are therefore not likely to make a rash decision to implement something like Flare, which would be premature optimisation.
    – Mark H
    Dec 20, 2018 at 14:56
  • 2
    IMO, a more reasonable solution to scaling routing would be to use something like a DHT, where nodes keep local routing information, where local is information about node public keys (or hashes of) who are lexically close to their own node.
    – Mark H
    Dec 20, 2018 at 14:57
  • 1
    (1) I meant MiB (megabytes). Nodes need to store the full signed gossip messages for nodes, channels and channel_updates (2 per channel) in order to forward them on to other peers. This information also needs refreshing every 2 weeks. (2) Flare proposes a hub and spoke network, which means "hubs" are effectively privileged nodes and spokes are less privileged, and also less fault tolerant because they depend on hubs to route for them. (3) I've not read the paper yet, I'll have to get back to you on that one.
    – Mark H
    Dec 20, 2018 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.