Include the Uncertainty Network into the Payment Session and potentially acrosse payment sessions

[renepickhardt]

In a recent PR #4771 c-lightning was the first implementation to include probabilistic path finding. While the mainnet tests and user feedback seemed overwhelmingly positive there is clear room for improvement.

As of now c-lightning seems to not incorperate gained information from previous attempts probperly. I think you only exclude channels with temporary channel failure during a payment session. Yet the papers clearly state that this is an easy apple to pick and especially when computing min cost flows and delivering really large payments this step is absolutely crucial.

As I just spend quite some time to summarize the two papers to concrete formulas for the rust-lighting project in lightningdevkit/rust-lightning#1170 (comment) I thought it is time to request this feature for c-lightning.

I will quote the most important formulas from the discussion in the rust-lightning issue here for easier reference. But in case the formulas should not speak for themselves I suggest you head over to lightningdevkit/rust-lightning#1170 (comment) or look at section 3 and 4.3 of https://arxiv.org/pdf/2103.08576.pdf and section 2.2. and 3 of https://arxiv.org/pdf/2107.05322.pdf

Let's say a payment delivery algorithm selects a route and wants to add an HTLC with amount h to a channel of capacity c there are several cases that we can observe to update our uncertainty about the network

1. Payment failed at an upstream channel: P(X>=a) = (c+1-a)/(c+1)
2. Payment failed at the channel: P(X>=a | X < h) = (h+1 -a) / (h+1).
3. Payment failed at a downstream channel: P(X>=a)/P(X>=h) = [...] = (c+1-a)/(c+1-h)
4. The case that the payment was successfull or did not return an error. P(X>=a + h | X >=h) = ( (c-h) + 1 - a)/( (c - h) + 1)

I suggest for simplicity and to allow future tests to not forget the gained knowledge within a single payment session but forget it completely without decay afterwards.

as with the probabilistic payments I am happy to help and answer questions!

[renepickhardt]

Btw ldk has landed this in lightningdevkit/rust-lightning#1227 sometimes code is easier to read than papers with explanations