<p>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.</p>

<hr>

<p>Summarizing mostly from <a href="https://np.reddit.com/r/Bitcoin/comments/4ea1s8/how_are_paths_found_in_lightning_network/" rel="nofollow noreferrer">r/bitcoin: How are paths found in Lightning Network?</a>, the currently suggested routing would be similar to the <a href="https://en.wikipedia.org/wiki/Border_Gateway_Protocol" rel="nofollow noreferrer">Border Gateway Protocol</a>.</p>

<p>At intervals, the following process is initiated:</p>

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

<p>Nodes remember their shortest routes to a number of previously selected beacon node.</p>

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

<pre><code>     Alice → N1 → N2 → B2 ← N3 ← Bob
</code></pre>

<p>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:</p>

<pre><code>     Alice → N1 → N2 → B2 ← N2 ← Bob
</code></pre>

<p>They could shorten the route to:</p>

<pre><code>     Alice → N1 → N2 ← Bob
</code></pre>

<p>Altogether, "shortest" would be some combination of <em>reachable, sufficient liquidity, lowest fee, fewest hops, and most reliable</em>. 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.</p>

<hr>

<p>Sources: <a href="https://np.reddit.com/r/Bitcoin/comments/4ea1s8/how_are_paths_found_in_lightning_network/d1yl55e" rel="nofollow noreferrer">harda</a>, <a href="https://np.reddit.com/r/Bitcoin/comments/4ea1s8/how_are_paths_found_in_lightning_network/d1ylvve" rel="nofollow noreferrer">mmeijeri</a>, <a href="https://np.reddit.com/r/Bitcoin/comments/4ea1s8/how_are_paths_found_in_lightning_network/d22sgga" rel="nofollow noreferrer">mmeijeri</a>.</p>

CC BY-SA 4.0
2018-12-14T14:28:55.090Z
In case of using **beacon** nodes that have a richer information
about the geometry of the LN network (even when selected randomly and renewed regularly), a kind **centralization** is not inherent ? (When, even the global knowledge of the geometry of the network can be a vector of attack.) Thanks (More info: https://arxiv.org/abs/1807.00151)
Questioner
CC BY-SA 4.0
2019-03-07T00:01:49.547Z
@murch Does this method take into account local and remote balances of a channel? For example, how do you know if a channel can handle a certain capacity _in a given direction_?
arshbot
CC BY-SA 4.0
2019-03-07T00:05:30.100Z
@arshbot: That is not public information. You only know these figures for channels that you co-own.
Murch
CC BY-SA 4.0
2019-08-23T15:09:23.023Z
The bit about Alice and Bob comparing paths seems inaccurate at this point. My read of the BOLT standard is that Alice and Bob's nodes never directly communicate. Invoices (Bolt-11) only have "limited routing assistance" for private channels, for now.
blee
CC BY-SA 4.0
2019-08-23T18:55:03.597Z
@isuldor: You're right, I really need to update this.
Murch
CC BY-SA 4.0
2016-04-14T20:52:52.320Z
2019-08-30T21:52:05.063Z
2019-08-30T21:52:05.063Z
Murch
<p>Everything is described in detailed in the corresponding BOLT specifications:</p>

<p><a href="https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md" rel="noreferrer">https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md</a></p>

<p><strong>BOLT #7: P2P Node and Channel Discovery</strong></p>

<p>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:</p>

<ul>
<li>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.</li>
<li>Node discovery allows nodes to broadcast their ID, host, and port, so that other nodes can open connections and establish payment channels with them.</li>
</ul>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2018-03-16T10:44:13.710Z
2018-03-16T10:44:13.710Z
mably
<p>The <a href="https://lightning.network/lightning-network-paper.pdf" rel="nofollow">Whitepaper</a> 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.</p>

CC BY-SA 3.0
2016-04-11T19:57:37.220Z
2016-04-11T19:57:37.220Z
Kristopher Ives
<p>I understand now <a href="https://bitcoin.stackexchange.com/q/43184/5406">how multihop payments can work in LN</a>, but <strong>how do we discover payment paths in Lightning Network in the first place?</strong>  Obviously you'd need to take into account the available capacity of the route, and you'd want to discover the cheapest path.</p>

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

CC BY-SA 3.0
2016-04-11T14:48:44.933Z
I believe the whitepaper mentioned using something similar to Border Gateway Protocol (https://en.wikipedia.org/wiki/Border_Gateway_Protocol), however I'm not sure if an actual solution has been decided upon or implemented.  As of right now, Bitcoin Core is making the necessary fixes for transaction malleability that will allow for the LN to be implemented.  I'd love to hear how this particular problem will be solved.
Jestin
CC BY-SA 3.0
2016-04-11T16:53:06.653Z
It looks like this has been reposted to Reddit, where there are some good comments:  https://www.reddit.com/r/Bitcoin/comments/4ea1s8/how_are_paths_found_in_lightning_network/
Jestin
CC BY-SA 3.0
2016-04-11T18:47:40.997Z
@Jestin: Yes, but I still hope that somebody writes a good answer here, where it will be much easier to find in the future as well.
Murch
<lightning-network><lightning-routing>
How are paths found in Lightning Network?
Murch
# How are paths found in Lightning Network?

(Asked by: username_0 on 2016-04-11)

I understand now [how multihop payments can work in LN](https://bitcoin.stackexchange.com/q/43184/5406), 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?

**Tags:** lightning-network, lightning-routing

> **Comments:**
> **username_1**: I believe the whitepaper mentioned using something similar to Border Gateway Protocol (https://en.wikipedia.org/wiki/Border_Gateway_Protocol), however I'm not sure if an actual solution has been decided upon or implemented.  As of right now, Bitcoin Core is making the necessary fixes for transaction malleability that will allow for the LN to be implemented.  I'd love to hear how this particular problem will be solved.  
> **username_1**: It looks like this has been reposted to Reddit, where there are some good comments:  https://www.reddit.com/r/Bitcoin/comments/4ea1s8/how_are_paths_found_in_lightning_network/  
> **username_0**: @username_1: Yes, but I still hope that somebody writes a good answer here, where it will be much easier to find in the future as well.  

---

## 3 answers

### Answer by username_0 on 2016-04-14. Score: 22

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?](https://np.reddit.com/r/Bitcoin/comments/4ea1s8/how_are_paths_found_in_lightning_network/), the currently suggested routing would be similar to the [Border Gateway Protocol](https://en.wikipedia.org/wiki/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](https://np.reddit.com/r/Bitcoin/comments/4ea1s8/how_are_paths_found_in_lightning_network/d1yl55e), [mmeijeri](https://np.reddit.com/r/Bitcoin/comments/4ea1s8/how_are_paths_found_in_lightning_network/d1ylvve), [mmeijeri](https://np.reddit.com/r/Bitcoin/comments/4ea1s8/how_are_paths_found_in_lightning_network/d22sgga).

> **Comments:**
> **username_2**: In case of using **beacon** nodes that have a richer information about the geometry of the LN network (even when selected randomly and renewed regularly), a kind **centralization** is not inherent ? (When, even the global knowledge of the geometry of the network can be a vector of attack.) Thanks (More info: https://arxiv.org/abs/1807.00151)  
> **username_3**: @username_0 Does this method take into account local and remote balances of a channel? For example, how do you know if a channel can handle a certain capacity _in a given direction_?  
> **username_0**: @username_3: That is not public information. You only know these figures for channels that you co-own.  
> **username_4**: The bit about Alice and Bob comparing paths seems inaccurate at this point. My read of the BOLT standard is that Alice and Bob's nodes never directly communicate. Invoices (Bolt-11) only have "limited routing assistance" for private channels, for now.  
> **username_0**: @isuldor: You're right, I really need to update this.  

---

### Answer by username_5 on 2018-03-16. Score: 7

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 by username_6 on 2016-04-11. Score: 3

The [Whitepaper](https://lightning.network/lightning-network-paper.pdf) 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.


---

