search

lightningnetwork / lnd

Lightning Network Daemon ⚡️
MIT License
7.64k stars 2.08k forks source link

[feature]: Proposal for a different cutoff between InboundFee and OutboundFee in pathfinding #8945

Open feelancer21 opened 1 month ago

feelancer21 commented 1 month ago

Is your feature request related to a problem? Please describe.

I am picking up a topic that I already mentioned in #8940. In the course of #6934, a split for the total channel fees was implemented. The current cutoff results in not always finding the optimal route as mentioned here. https://github.com/lightningnetwork/lnd/pull/6934#pullrequestreview-1836184718

Here is another example from the perspective of a sender A, who can send a payment to D either through B or C. A-[out fee 0 msat | in fee -100 msat]-B-[out 150 msat | in fee 0]-D and A-[out fee 0 msat | in fee 0 msat]-C-[out 100 msat | in fee 0]-D

Since the out_fee in the outgoing channels of a source is always counted as 0, the incoming fee on this channel is completely absorbed by the current cutoff, and both source channels are considered with a weight of 0 in the pathfinding (ignoring the timelock penalty). The optimal solution is determined based on the second channel, and the result is the more expensive second route (about 50ppm). This is even though the success probability of the second route could be lower. However, if a fee_limit of 75ppm is set, the first route will be found at least after the fix of #8940.

Describe the solution you'd like

In my opinion, this behavior can be addressed if we do not base the calculation on the total channel fee, but measure the distance from the fromVertex to the target without considering the outbound fee of the fromVertex. Instead calculating thefee with https://github.com/lightningnetwork/lnd/blob/b7c59b36a74975c4e710a02ea42959053735402e/routing/pathfind.go#L805-L809

it should be calculated with fee := toNodeDist.outboundFee + inboundFee, which cannot become negative due to the construction of the inboundFee. The outbound fee of the source would be disregarded, which is unproblematic since it is currently counted as 0. Moreover, the individual fee components would add up to the totalFee again after merging #8941.

In the end, the proposal is nothing more than shifting the measurement point of the distance from the point between the involved edges to the middle of the outgoing edge of the fromVertex. Intuitively, I would even argue that we find the optimal solution in this way without transforming the graph into a line graph.

I am looking forward to your assessment or if I am missing something. The shift seems to be too simple to be true. ;)

bitromortac commented 1 month ago

I am looking forward to your assessment or if I am missing something. The shift seems to be too simple to be true. ;)

Yes, unfortunately I think that doesn't solve it, during implementation/review of https://github.com/lightningnetwork/lnd/pull/6934 this approach was tried but not documented. Here's an example graph that would lead to non-optimal outcomes with the suggested approach.

Take the following graph with outbound and inbound fees as indicated on the edges:

flowchart LR

S -->|out: 0, in: -4| A
A -->|out: 9, in: -11| B
A -->|out: 0, in: -6| C
B -->|out: 8, in: 0| T
C -->|out: 10, in: 0| T

The top route (SABT) has fees or weight of 5=8-8+9-4, the lower, optimal, route (SACT) has weight of 4=10-6+0+0, keeping in mind that the inbound discount is capped by the next hop's outbound fee, so the total node fee is not allowed to become negative.

I'll show the current approach, the suggested approach and the line-graph approach as examples.

Capped total channel fees

This is the currently implemented approach: taking the weight as the edge's inbound fee plus its outbound fee, capped from below by zero. Dijkstra's algorithm would work like this:

Inbound fee and previous outbound fee

The accumulated weights are 0 for both, so the order by which nodes are explored is non-deterministic.

  1. explore B first
    • A: 0 (prev accWeight) - 8 (capped inFee) + 8 (prev outFee) = 0
    • queue:
    • A 0 (9)
    • C 0 (10)

Both nodes in the queue have the same accumulated weight.

1.1. explore A first

1.2. explore C first

  1. explore C first
    • A: 0 - 6 + 10 = 4
    • queue:
    • B 0 (8)
    • A 4 (0)

So in some cases optimal routes are found, sometimes not. Perhaps one could apply the next outbound fee as a tie-breaker and maybe there are other edge cases, but I think the next approach is the exact one.

Inbound fee and previous outbound fee with line graph

Transforming the problem to a line graph (https://en.wikipedia.org/wiki/Line_graph) solves the problem for this example graph. The new pivots of exploration are the middle points between two nodes, which helps to keep track of weights without overriding information (a solution found by Joost Jager).

Again, we have same weights, any tuple could get picked.

  1. explore (B,T) first
    • A: 0 - 8 (capped inFee) + 8 (prev outFee) = 0
    • queue:
    • (A,B) 0 (9)
    • (C,T) 0 (10)

Both nodes in the queue both have again the same weight.

1.1. explore (A,B) first

1.2. explore (C,T) first

  1. explore (C,T) first
    • A: 0 -6 + 10 = 4
    • queue:
      • (B,T) 0 (8)
      • (A,C) 4 (0)

Next steps

So the suggestion to use the inbound fee plus the previous outbound fee makes the algo correct (at least for this toy graph) if the heap/queue is used with a node pair tuple, which is the case with https://github.com/lightningnetwork/lnd/commit/54c498870c13b25a2c6c96a0c473a711b7db6457. I'm going to explore this change and check it's execution time behavior. The exit condition can be changed by adding a fake hop (0,S) we are really looking for, I think.

feelancer21 commented 1 month ago

First of all, thank you very much for the detailed answer and the very interesting example. I already thought that the dependencies between inbound and outbound go much deeper, but haven't seen it yet.

To summarize it for me: 1.1. vs. 1.2. is about the decision of A 0 (9) vs A 4 (0). However, the optimal solution depends on the inbound discount on S. If it had been -6 or lower, A 0 (9) would have been the right choice.

I suppose you can also construct cases where it is better to choose a higher distance with a higher outbound fee, which is later improved by discounts. So the classic reason why Dijsktra does not find the optimal solution with negative weights

feelancer21 commented 1 month ago

explore A

  • S: accumulated weight = 9 - 4 + 0 = 5

  • queue:

    • S 5 (0): the current algo ends here with a non-optimal route
    • C 10 (10)

Not sure if I have really understood the current approach. I had expected accumulated weight = 9 + max(- 4 + 0; 0) = 9 because of the checkt of the signedFee

Edit: If I'm not wrong about the previous one and the conversion to the line graph is more extensive than you thought, then I would like to suggest that at least the senders can benefit better from the inbound discounts of their direct peers.

You could set tempWeight = totalFee + sumTimeLockPenalty directly in the case fromVertex == source. Here, sumTimeLockPenalty is the sum of the timeLockPenalty, which would have to be kept separately in nodeWithDist. Then the distance would be correct again, at least in the last iteration, and the chance of finding the optimum path would increase.

bitromortac commented 1 month ago

Not sure if I have really understood the current approach. I had expected accumulated weight = 9 + max(- 4 + 0; 0) = 9 because of the checkt of the signedFee

Ah yes, thank you for the correction, updated (it doesn't change the outcome)!

If I'm not wrong about the previous one and the conversion to the line graph is more extensive than you thought, then I would like to suggest that at least the senders can benefit better from the inbound discounts of their direct peers.

Changing to that approach could make sense, as it is closer to the optimal solution :+1:, but I think it's worth to explore the behavior of the line-graph approach first.