Pathfinding: take channel capacity into account

[joostjager]

In c-lightning (https://github.com/ElementsProject/lightning/pull/4771/files) and rust-lightning (lightningdevkit/rust-lightning#1166), moves have been / are being made to factor in the channel capacity relative to the payment amount.

I think that makes a lot of sense and is easily added to lnd's probability estimator. The logic could be applied in the probability estimation for channels that haven't been tried before.

[renepickhardt]

Note that especially the channels which have been tried before can switch to conditional probabities as described in https://arxiv.org/abs/2103.08576 and more specifically with the concrete formulas in https://arxiv.org/abs/2107.05322

C-lightning currently ignores the uncertainty network as they would have had to change their logic and mission control does it not according to the capacity model which are suggest to create here. Of course your temporal decay of forgetting the information could persist.

I think @stefanwouldgo has code in scala that does it for lnd (even with tracking in flight htlcs) also I think @Roasbeef has seen part of the code in the repo mentioned in the second paper

[alexbosworth]

Is there a centralization effect on demanding excess capital for a route?

[Roasbeef]

Note that especially the channels which have been tried before can switch to conditional probabities as described in

We already do this and have for a few years now. Though our approach can certainly be improved, as is the system will continually update these conditional probabilities and also decay them over time to reflect the uncertainty of the network overtime since our last observation. Adding capacities to the mix should be a pretty straight forward change code wise. We'd likely add some knobs there as well to control the importance/inclusion of the new factor to make it easier to experiment with.

Is there a centralization effect on demanding excess capital for a route?

That's something we'd need to examine and way the tradeoffs for. Hopefully we'll have an initial version of the distributed A/B testing framework we're working on so we can properly test changes like this (as we've been sort of holding off to make sure our decisions are grounded in empirical evidence). Heuristically, one would say that if an amount is <<< than the channel size, then it should have a high success probability. However as you're getting at, we'd need to make sure individuals with very very large channels don't become a sort of attempt/retry sink.

[Roasbeef]

I think @stefanwouldgo has code in scala that does it for lnd (even with tracking in flight htlcs) also I think @Roasbeef has seen part of the code in the repo mentioned in the second paper

This is another (imo) important thing that we don't currently do: in-flight HTLCs in the same payment session don't propagate back any information to the main mission control instance. This ends up triggering weird scenarios where we'll continue to attempt payment amounts that we know can't work (example if a 1 BTC channel with an 0.9 BTC HTLC present, and we try > 0.1 BTC).

[xraid]

if a channel capacity is 1, any attempts above 0.5 will have a high % in failing since bandwidth of a channel in practice will most of the time only be able have a portion as available liquidity. Retry rule with other expectation if else fails.

case: 0.1 try > 0.4 paths if path not flagged in MC, equals a pragmatic 25% of channel.

[joostjager]

Is there a centralization effect on demanding excess capital for a route?

Agreeing with @xraid. Probably only lowering the probability for amounts that are a considerable part of the channel capacity is sufficient. I don't think it needs to be taken to extremes where a 1BTC channel is selected for a 10 sat payment over a 10M channel.

[renepickhardt]

Strongly disagree with @joostjager : there is a whole theory and strong emperical evidence why -log((cap+1-amt)/(cap+1)) is a good feature In pathfinding. And also on how to adopt this formular after successful, failed attempts and with htlcs logged in. Mainly 2 question remain

1. how fast to decay gained information back to the full uncertain case)
2. How strong to enorporate it with other features?

Plot this formular for a 10M channel (in the discussion of the c Lightning pr I have done it with various other combined features for a 20k sat channel) and you will see that the cost of this feature hardly triggers for small amounts anyway due to its convex nature. So why would one choose arbitrary case distinctions of not choosing this feature for low amounts if the feature itself Already encodes such behavior?

[renepickhardt]

Is there a centralization effect on demanding excess capital for a route?

Yes but that is not a consequence of the features chosen in selfish routing (c.f. Selfish routing and the price of anarchy work by Tim roughgarden https://www.amazon.de/Selfish-Routing-Price-Anarchy-Press/dp/0262182432 ) but a fundamental property of the lightning network itself that liquidity is necessary to guarantee certain service level agreements / objectives.

People who wish to send money will be selfish in making routing decisions and routing nodes / liquidity providers have to change the channel graph in adoption to the selfish behavior of users. It's the same as street planning: It needs resources so that folks who chose the fastest / quickest route can all do so without congestion. Just look at braess paradox https://en.wikipedia.org/wiki/Braess%27s_paradox which is actually an answer (to your concern) that indicates that people don't want to open too large channels if we choose this feature

Anyway I am getting nerd snipes here

[renepickhardt]

I think you might be interested in concrete formulas how to update your uncertainty / probabilities in case of failed / success full payment attempts. I have summarized the two papers in an issue of another PR lightningdevkit/rust-lightning#1170 (comment)