renepay: Probability costs for small amounts zero? about lightning HOT 2 OPEN

In this blog post I explain why I chose the amount as part of the proportional factor that scales the uncertainty cost.
If we neglect for a moment of the mu weight, and we are asked to combine the fee cost and the uncertainty cost linearly (in order to preserve linearity function of the flow and hence be able to apply MCF optimization) we can do it for example by multiplying the uncertainty cost by a constant k:

Cost(x) = fee(x) - k log P(x)

where x represents a routing solution, fee(x) is the fee associated with it, and P(x) is the probability of success of that set of routes.

The algorithm will try to find x such that Cost(x) is minimal.

Now image that there are two optimal solutions x_1 and x_2, that is
Cost(x_1)=Cost(x_2), furthermore there isn't any other solution with a smaller cost than that (possibly equal).
The MCF algorithm can return either x_1 or x_2, one is as good as the other.
But there are not necessarily the same in the sense that fee(x_1) could be different from fee(x_2). Hence consider the cost evaluated at x_1 and x_2:

Cost(x_1) = fee(x_1) - k log P(x_1)
Cost(x_2) = fee(x_2) - k log P(x_2)

substract both equations and assume x_1 and x_2 are topologically close
to the other in a weak sense, so that we can take differentials:

0 = d fee - k / P  dP

hence

dfee = k/P dP

in other words, in the space of optimal solutions one unit of success probability is as good as k/P units of fee. This seems very abstract but I explain it in the blog with an example.

If k was a fixed number of sats, for instance 150 BTC or 1.5 Gsats we would have that 0.1% change is probability would be equivalent to 1.5Gsats * 0.001=1.5Msats in fees, assuming P approximately 1.
That means we are expressing that we are willing to pay
1.5 Msats in order to improve our success probability by just 0.1%.

Instead I thought of defining k as the payment amount times some number so that k/P dP becomes a fraction of amount. One could tune it so that in the space of optimal solutions a 0.1% change in probability could correspond to
a reasonable number of PPM of the payment amount.
In renepay we have hard coded k = amount*prob_cost_factor/1000,
with prob_cost_factor a parameter with default value 10. This implies that
a 0.1% change in probability is equivalent to a fee of:

dfee = amount*prob_cost_factor/1000*0.001 = amount * prob_cost_factor/1M
     = amount * 10/1M

The prob_cost_factor becomes the PPM of the amount that one would consider reasonable to exchange for each 0.1% of probability.

I am not claiming this idea is 100% correct. I am just communicating this is the motivation behind the choices made.

Yes, this implies that for some arcs the slope of the linearized uncertainty cost will be zero. With the numbers given above the first non-trivial arc of a channel
with liquidity bounded in the range [a,b) will have a slope (cost per unit of flow):

cost_unit = k*1.38/(b-a) = amount*prob_cost_factor/1000 * 1.38/(b-a)

1.38 comes from the piecewise linearization.
But the entire cost function is multiplied by 1M, because flows are in units of sats and for the cost we wanted micro-sats in order to be able to consider proportional_fees of at least 1PPM and still work in integer numbers.
So numerically (also in the code) we have

cost_unit = k*1.38/(b-a) * 1M = amount*prob_cost_factor * 1000 * 1.38/(b-a)

In order for this to be zero, one would need

amount < (b-a)/10000

Even in the case of a channel with a=0, with all the payment amount going through it, the probability of failure would be

P_fail = amount / (b-a) < 0.0001

That's why neglecting the uncertainty cost for this channel does not incur much loss in accuracy, IMO.

from lightning.

Channels with a failure probability of forwarding the entire payment p(amount) that fall below 0.001/prob_cost_factor have a zero uncertainty cost, because our limited precision working with integer numbers.

from lightning.