<p>Even if you did find such a route successfully, what guarantees that B WILL use its payment channel? B can deny at any moment, because decentralization.</p>

<p>Also, from <a href="https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md#recommendations-for-routing" rel="nofollow noreferrer">routing recommendations</a>:</p>

<blockquote>
  <p>When calculating a route for an HTLC, the <code>cltv_expiry_delta</code> and <strong>the
  fee</strong> both need to be considered: the <code>cltv_expiry_delta</code> contributes to
  the time that funds will be unavailable on worst-case failure. <strong>The
  tradeoff between these two is unclear, as it depends on the
  reliability of nodes.</strong></p>
</blockquote>

<p>Goes on to explain that the problem is deeper:</p>

<blockquote>
  <p>If a route is computed by simply routing to the intended recipient,
  summing up the <code>cltv_expiry_deltas</code>, then nodes along the route may
  guess their position in the route. Knowing the CLTV of the HTLC and
  the surrounding topology with the <code>cltv_expiry_deltas</code> gives an attacker
  a way to guess the intended recipient. Therefore it is highly
  suggested to add a random offset to the CLTV that the intended
  recipient will receive, bumping all CLTVs along the route. In order to
  create a plausible offset the sender MAY start a limited random walk
  on the graph, starting from the intended recipient, sum the
  <code>cltv_expiry_deltas</code>, and then use the sum as the offset. This
  effectively creates a <em>shadow route extension</em> to the actual route,
  providing better protection against this kind of attack than simply
  picking a random offset.</p>
</blockquote>

<p>Importantly for this answer, it ends at:</p>

<blockquote>
  <p>Other <strong>more advanced considerations</strong> involve diversity of routes to
  avoid single points of failure and detection and channel balance of
  local channels.</p>
</blockquote>

<p>So the answer would be, that LN just provides discovery, doesn't build a path(because a channel cannot be guaranteed to be online in a decentralized network??) so 'tries' is not a feature of core LN(but of the <a href="https://github.com/lightningnetwork/lnd/tree/master/autopilot" rel="nofollow noreferrer">autopilot</a> feature).</p>

<p>The autopilot can be seen <a href="https://github.com/lightningnetwork/lnd/commit/306c4aef8e3af44fb3f2d8f52fc887f2c48e9c04" rel="nofollow noreferrer">here</a>. This is where the <code>heuristics</code> for finding the path goes. </p>

<blockquote>
  <p>The autopilot package has been signed to be as abstract as possible in
  order to allow users, developers, and researchers to plug in various
  heuristics in order to experiment with the possibilities, or attempt
  to optimize the channel sub-graph for their targeted nodes. The
  current default heuristic is a mode called <code>ConstrainedPrefAttachment</code>.</p>
</blockquote>

<p>Also,</p>

<blockquote>
  <p>This is only one example of the
  possible heuristics which could be hooked into an active
  <code>autopilot.Agent</code> instance. We look forward to the additional heuristics
  that developers/researchers will implement!</p>
</blockquote>

<p>In short, the current heuristic implementation first <a href="https://github.com/lightningnetwork/lnd/blob/master/autopilot/prefattach.go#L156" rel="nofollow noreferrer">selects a slice</a> in the network, and then <a href="https://github.com/lightningnetwork/lnd/blob/master/autopilot/prefattach.go#L250" rel="nofollow noreferrer">greedily allocates funds</a>.</p>

<pre><code>switch {
    // If we have enough available funds to distribute the maximum channel
    // size for each of the selected peers to attach to, then we'll
    // allocate the maximum amount to each peer.
    case int64(fundsAvailable) &gt;= numSelectedNodes*int64(p.maxChanSize):
        for i := 0; i &lt; int(numSelectedNodes); i++ {
            directives[i].ChanAmt = p.maxChanSize
        }

        return directives, nil

    // Otherwise, we'll greedily allocate our funds to the channels
    // successively until we run out of available funds, or can't create a
    // channel above the min channel size.
    case int64(fundsAvailable) &lt; numSelectedNodes*int64(p.maxChanSize):
        i := 0
        for fundsAvailable &gt; p.minChanSize {
            // We'll attempt to allocate the max channel size
            // initially. If we don't have enough funds to do this,
            // then we'll allocate the remainder of the funds
            // available to the channel.
            delta := p.maxChanSize
            if fundsAvailable-delta &lt; 0 {
                delta = fundsAvailable
            }

            directives[i].ChanAmt = delta

            fundsAvailable -= delta
            i++
        }

        // We'll slice the initial set of directives to properly
        // reflect the amount of funds we were able to allocate.
return directives[:i:i], nil
</code></pre>

<p>[EDIT:straight answer]</p>

<blockquote>
  <p>So the heuristic only uses the channel capacity to find a route?</p>
</blockquote>

<p>"based on the current internal state, the state of the channel graph, the set of nodes we should exclude, and the amount of funds available"</p>

<blockquote>
  <p>Does the path finding heuristic have the information which side of a channel in the network owns how much, or does it only compute a route based on the capacity of channels?</p>
</blockquote>

<p>Looking at the <a href="https://github.com/lightningnetwork/lnd/blob/master/routing/testdata/spec_example.json" rel="nofollow noreferrer">spec example</a>, we only get info of "capacity" of an "edge" in the graph and <strong>not how much each party owns</strong>; only the amount they are willing to transmit. As explained above, yes, it depends on capacity, but it has more properties and not just amounts.</p>

CC BY-SA 3.0
2018-02-08T10:07:22.250Z
Thanks for your answer, I don't really understand how the heuristic works. So the heuristic only uses the channel capacity to find a route? So what my initial question was: Does the path finding heuristic have the information which side of a channel in the network owns how much, or does it only compute a route based on the capacity of channels?
blacktemplar
CC BY-SA 3.0
2018-02-10T00:50:04.603Z
@blacktemplar edited the answer. I hope it answers your query. If not please ask for more clarification.
skang404
CC BY-SA 3.0
2018-02-07T23:57:12.107Z
2018-02-10T00:49:17.973Z
2018-02-10T00:49:17.973Z
skang404
<p>So i have a question how routing works in the LN. I read partly through the RFC described in <a href="https://github.com/lightningnetwork/lightning-rfc" rel="noreferrer">https://github.com/lightningnetwork/lightning-rfc</a> but I have still this open question.</p>

<p>I know every node in LN has the whole network topology information, so it knows each node and each channel and with that also the capacity of a channel. But the capacity of a channel doesn't say which side is owning how much. How can we find now a valid route and be sure that there is enough capacity in each channel for the direction which is part of our route?</p>

<p>So for an example lets say I am node A und have a channel to node B and this one has a channel to node C. Lets say each channel has a capacity of 1 BTC, I want to send now 0.4 BTC from A to C and chose the route A -> B -> C. But now it may be that in the channel B - C the node B only owns 0.3 BTC at the moment and node C owns 0.7 BTC. That would mean that B can't send 0.4 to node C. So if I send now this transaction B would return with an error.</p>

<p>If I have now a longer route the possibility of such an event increases exponentially. So at the end it is very unlikely that my chosen route is valid. How does the protocol prevent a lot of tries until one finds a really valid route?</p>

<lightning-network><lightning-routing>
Lightning Route Discovery - How to know capacity in each direction?
blacktemplar
# Lightning Route Discovery - How to know capacity in each direction?

(Asked by: username_0 on 2018-02-03)

So i have a question how routing works in the LN. I read partly through the RFC described in <https://github.com/lightningnetwork/lightning-rfc> but I have still this open question.

I know every node in LN has the whole network topology information, so it knows each node and each channel and with that also the capacity of a channel. But the capacity of a channel doesn't say which side is owning how much. How can we find now a valid route and be sure that there is enough capacity in each channel for the direction which is part of our route?

So for an example lets say I am node A und have a channel to node B and this one has a channel to node C. Lets say each channel has a capacity of 1 BTC, I want to send now 0.4 BTC from A to C and chose the route A -> B -> C. But now it may be that in the channel B - C the node B only owns 0.3 BTC at the moment and node C owns 0.7 BTC. That would mean that B can't send 0.4 to node C. So if I send now this transaction B would return with an error.

If I have now a longer route the possibility of such an event increases exponentially. So at the end it is very unlikely that my chosen route is valid. How does the protocol prevent a lot of tries until one finds a really valid route?

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


---

## 1 answers

### Answer by username_1 on 2018-02-07. Score: 3 | Accepted answer

Even if you did find such a route successfully, what guarantees that B WILL use its payment channel? B can deny at any moment, because decentralization.

Also, from [routing recommendations](https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md#recommendations-for-routing):

> When calculating a route for an HTLC, the `cltv_expiry_delta` and **the
> fee** both need to be considered: the `cltv_expiry_delta` contributes to
> the time that funds will be unavailable on worst-case failure. **The
> tradeoff between these two is unclear, as it depends on the
> reliability of nodes.**

Goes on to explain that the problem is deeper:

> If a route is computed by simply routing to the intended recipient,
> summing up the `cltv_expiry_deltas`, then nodes along the route may
> guess their position in the route. Knowing the CLTV of the HTLC and
> the surrounding topology with the `cltv_expiry_deltas` gives an attacker
> a way to guess the intended recipient. Therefore it is highly
> suggested to add a random offset to the CLTV that the intended
> recipient will receive, bumping all CLTVs along the route. In order to
> create a plausible offset the sender MAY start a limited random walk
> on the graph, starting from the intended recipient, sum the
> `cltv_expiry_deltas`, and then use the sum as the offset. This
> effectively creates a *shadow route extension* to the actual route,
> providing better protection against this kind of attack than simply
> picking a random offset.

Importantly for this answer, it ends at:

> Other **more advanced considerations** involve diversity of routes to
> avoid single points of failure and detection and channel balance of
> local channels.

So the answer would be, that LN just provides discovery, doesn't build a path(because a channel cannot be guaranteed to be online in a decentralized network??) so 'tries' is not a feature of core LN(but of the [autopilot](https://github.com/lightningnetwork/lnd/tree/master/autopilot) feature).

The autopilot can be seen [here](https://github.com/lightningnetwork/lnd/commit/306c4aef8e3af44fb3f2d8f52fc887f2c48e9c04). This is where the `heuristics` for finding the path goes.

> The autopilot package has been signed to be as abstract as possible in
> order to allow users, developers, and researchers to plug in various
> heuristics in order to experiment with the possibilities, or attempt
> to optimize the channel sub-graph for their targeted nodes. The
> current default heuristic is a mode called `ConstrainedPrefAttachment`.

Also,

> This is only one example of the
> possible heuristics which could be hooked into an active
> `autopilot.Agent` instance. We look forward to the additional heuristics
> that developers/researchers will implement!

In short, the current heuristic implementation first [selects a slice](https://github.com/lightningnetwork/lnd/blob/master/autopilot/prefattach.go#L156) in the network, and then [greedily allocates funds](https://github.com/lightningnetwork/lnd/blob/master/autopilot/prefattach.go#L250).

```
switch {
    // If we have enough available funds to distribute the maximum channel
    // size for each of the selected peers to attach to, then we'll
    // allocate the maximum amount to each peer.
    case int64(fundsAvailable) >= numSelectedNodes*int64(p.maxChanSize):
        for i := 0; i < int(numSelectedNodes); i++ {
            directives[i].ChanAmt = p.maxChanSize
        }

        return directives, nil

    // Otherwise, we'll greedily allocate our funds to the channels
    // successively until we run out of available funds, or can't create a
    // channel above the min channel size.
    case int64(fundsAvailable) < numSelectedNodes*int64(p.maxChanSize):
        i := 0
        for fundsAvailable > p.minChanSize {
            // We'll attempt to allocate the max channel size
            // initially. If we don't have enough funds to do this,
            // then we'll allocate the remainder of the funds
            // available to the channel.
            delta := p.maxChanSize
            if fundsAvailable-delta < 0 {
                delta = fundsAvailable
            }

            directives[i].ChanAmt = delta

            fundsAvailable -= delta
            i++
        }

        // We'll slice the initial set of directives to properly
        // reflect the amount of funds we were able to allocate.
return directives[:i:i], nil

```

[EDIT:straight answer]

> So the heuristic only uses the channel capacity to find a route?

"based on the current internal state, the state of the channel graph, the set of nodes we should exclude, and the amount of funds available"

> Does the path finding heuristic have the information which side of a channel in the network owns how much, or does it only compute a route based on the capacity of channels?

Looking at the [spec example](https://github.com/lightningnetwork/lnd/blob/master/routing/testdata/spec_example.json), we only get info of "capacity" of an "edge" in the graph and **not how much each party owns**; only the amount they are willing to transmit. As explained above, yes, it depends on capacity, but it has more properties and not just amounts.

> **Comments:**
> **username_0**: Thanks for your answer, I don't really understand how the heuristic works. So the heuristic only uses the channel capacity to find a route? So what my initial question was: Does the path finding heuristic have the information which side of a channel in the network owns how much, or does it only compute a route based on the capacity of channels?  
> **username_1**: @username_0 edited the answer. I hope it answers your query. If not please ask for more clarification.  

---

