Add an option to make the success probability estimation nonlinear
authorMatt Corallo <git@bluematt.me>
Mon, 24 Apr 2023 01:52:41 +0000 (01:52 +0000)
committerMatt Corallo <git@bluematt.me>
Wed, 20 Sep 2023 18:32:21 +0000 (18:32 +0000)
commit259ceb0ebfe7082e2dfebc39a2ad7edefea56b19
tree4e0562a93831a484b794939479704c85a940f171
parentdf52da7b31494c7ec77a705cca4c44bc840f8a95
Add an option to make the success probability estimation nonlinear

Our "what is the success probability of paying over a channel with
the given liquidity bounds" calculation currently assumes the
probability of where the liquidity lies in a channel is constant
across the entire capacity of a channel. This is obviously a
somewhat dubious assumption given most nodes don't materially
rebalance and flows within the network often push liquidity
"towards the edges".

Here we add an option to consider this when scoring channels during
routefinding. Specifically, if a new `linear_success_probability`
flag is unset on `ProbabilisticScoringFeeParameters`, rather than
assuming a PDF of `1` (across the channel's capacity scaled from 0
to 1), we use `(x - 0.5)^2`.

This assumes liquidity is likely to be near the edges, which
matches experimental results. Further, calculating the CDF (i.e.
integral) between arbitrary points on the PDF is trivial, which we
do as our main scoring function.

While this (finally) introduces floats in our scoring, its not
practical to exponentiate using fixed-precision, and benchmarks
show this is a performance regression, but not a huge one, more
than made up for by the increase in payment success rates.
bench/benches/bench.rs
lightning/src/routing/router.rs
lightning/src/routing/scoring.rs