ElementsProject / ElementsProject/lightning

renepay: Probability costs for small amounts zero?

Open
#6,846 2 comments 0 reactions 1 assignee Claimed by @Lagrang3 View on GitHub
Dominant language
C
Stars
3.1k
Forks
1k
Avg merge
4d 10h
Merged PRs (30d)
13

Description

Together with @stefanwouldgo we are currently reviewing `renepay` and we stumbled across this line:

https://github.com/ElementsProject/lightning/blob/02ca226f88bf91c1fc3f654d8faa5aa178f75b96/plugins/renepay/mcf.c#L492

the `cost` pointer / array is supposed to store all `s64`costs. However it seems that within this product the result will often be `0`. Let me elaborate.

* `params->cost_fraction[i]` is as far as we understand the slope of the `i`-th arc of the piecewise linearization. Given the [blog article](https://lagrang3.github.io/2023-10-28-renepay-1/) by @Lagrang3 this value is between `0` and `10`
* `params->amount.millisatoshis` This seems to be the pay amount and would be the same number multiplied to each channel. While the solution to the optimization problem should not change if all costs are multiplied with a constant number (for a single payment planning session this number is constant) in this particular case the number will in comparison with the channel size `b-a` decide weather or not the cost is above `1` meaning that the cast to `s64` doesn't make it `0`.
* `params->prob_cost_factor*1.0/(b-a)` Now this is the interesting beast. Given regular channels on the Lightning Network we expect `b-a` (at least initially) to be really large. Since the `prob_cost_factor` seems to be bound to `10'000` we most likely have a denominator that is large enough to reduce the cost to `0` for most channels. Independently of how `MU` is being learnt later this makes the `probability_cost`(which btw I like to call `uncertainty cost`) irrelevant.

I do see that some pay amounts will make this feature non 0 for some channels. However I see that in many cases even all arcs of the same channel will result in the same integer probability cost.

## Consequence
Independent of the choice of `MU` this will result in a fraction of the network having 0 cost probability channels and thus in:
https://github.com/ElementsProject/lightning/blob/02ca226f88bf91c1fc3f654d8faa5aa178f75b96/plugins/renepay/mcf.c#L546
we will have `pcost=0` resulting in `const s64 combined mu*fcost` which means that renepay will for a large fraction of the network mainly optimize for routing fees instead of probabilities. We believe in particular for small amounts this should significantly decrease the reliability and increase payment attempt failure rates

## Suggested Fix
I think the easiest fix is to replace `params->amount.millsatoshis` with the largest capacity `C` we observed on the network. With that we know that `C/(b-a) >=1` resulting in varing costs for all channels. In [my python implementation](https://github.com/renepickhardt/pickhardtpayments/blob/bd7fbc562e4c3298fe854b505b8e223f17caded0/pickhardtpayments/UncertaintyChannel.py#L34) we used a hard coded upper limit of `150 BTC` so that one doesn't have to scan gossmap over and over again. (could be premature optimization though)

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.