10

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?

2

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:

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 feature).

The autopilot can be seen here. 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 in the network, and then greedily allocates funds.

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, 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.

  • 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 Feb 8 '18 at 10:07
  • @blacktemplar edited the answer. I hope it answers your query. If not please ask for more clarification. – skang404 Feb 10 '18 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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