How are paths found in Lightning Network?

Question

I understand now how multihop payments can work in LN, but how do we discover payment paths in Lightning Network in the first place? Obviously you'd need to take into account the available capacity of the route, and you'd want to discover the cheapest path.

There shouldn't be a payment channel directory, so would it rely on a peer-based search?

Answer 1

Note: This answer was written in Spring 2016 and has since been overtaken by an actual spec and multiple implementations. I'm hoping to update this answer shortly.

---

Summarizing mostly from r/bitcoin: How are paths found in Lightning Network?, the currently suggested routing would be similar to the Border Gateway Protocol.

At intervals, the following process is initiated:

• A beacon node B is selected via a pseudo-random process.
• Neighbors of B broadcast their shortest route to B to their neighbors.
• The neighbors of neighbors of B now become aware of a route to B and in turn broadcast their shortest route to B.
• This cascades through the network until every reachable node has broadcasted their shortest route to the beacon node B.
• Whenever a node becomes aware of a new shorter route, it broadcasts this updated shortest route as well.
• After a short wait, start from top with a new beacon node B1.

Nodes remember their shortest routes to a number of previously selected beacon node.

Now, Alice wants to send 0.3BTC to Bob.
Alice has shortest routes to B, B1, and B2. Bob just came online and only knows B2. They add together their respective paths to B2 and thus find a path:

     Alice → N1 → N2 → B2 ← N3 ← Bob

If they have multiple common beacons, they can also compare different paths, and check whether any earlier nodes in their routes match. If they instead had found:

     Alice → N1 → N2 → B2 ← N2 ← Bob

They could shorten the route to:

     Alice → N1 → N2 ← Bob

Altogether, "shortest" would be some combination of reachable, sufficient liquidity, lowest fee, fewest hops, and most reliable. As Hash Time Lock Contracts are nearly trustless (only potentially locking your money for some time), and operating a routing wallet should have low resource requirements, it seems likely that the payment routing market should achieve a healthy competition, therefore discouraging nodes to lock money by establishing channels just to earn fees from routing. Payment channels between nodes that have some form of regular business relationship seem more likely as there is an immediate benefit.

---

Sources: harda, mmeijeri, mmeijeri.

Answer 2

Everything is described in detailed in the corresponding BOLT specifications:

https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md

BOLT #7: P2P Node and Channel Discovery

This specification describes simple node discovery, channel discovery, and channel update mechanisms that do not rely on a third-party to disseminate the information. Node and channel discovery serve two different purposes:

• Channel discovery allows the creation and maintenance of a local view of the network's topology, so that a node can discover routes to desired destinations.
• Node discovery allows nodes to broadcast their ID, host, and port, so that other nodes can open connections and establish payment channels with them.

To support channel discovery, peers in the network exchange channel_announcement messages containing information regarding new channels between the two nodes. They can also exchange channel_update messages, which update information about a channel. There can only be one valid channel_announcement for any channel, but at least two channel_update messages are expected.

To support node discovery, peers exchange node_announcement messages, which supply additional information about the nodes. There may be multiple node_announcement messages, in order to update the node information.

Answer 3

The Whitepaper doesn't make mention of any means to find a path without discovering the network manually. Not saying it shouldn't exist, just simply that currently in LN no data structure or filter is in place to make this scalable.