So, I’ve finally started implementing Pickhardt Payments in Core Lightning (#cln) and there are some practical complications beyond the paper which are worth noting for others who consider this!
In particular, the cost function in the paper cleverly combines the probability of success, with the fee charged by the channel, giving a cost function of:
? log( (ce + 1 ? fe) / (ce + 1)) + ? · fe · fee(e)
Which is great: bigger ? means fees matter more, smaller means they matter less. And the paper suggests various ways of adjusting them if you don’t like the initial results.
But, what’s a reasonable ? value? 1? 1000? 0.00001? Since the left term is the negative log of a probability, and the right is a value in millisats, it’s deeply unclear to me!
So it’s useful to look at the typical ranges of the first term, and the typical fees (the rest of the second term which is not ?), using stats from the real network.
If we want these two terms to be equal, we get:
? log( (ce + 1 ? fe) / (ce + 1)) = ? · fe · fee(e)
=> ? = ? log( (ce + 1 ? fe) / (ce + 1)) / ( fe · fee(e))
Let’s assume that fee(e) is the median fee: 51 parts per million. I chose to look at amounts of 1sat, 10sat, 100sat, 1000sat, 10,000sat, 100,000sat and 1M sat, and calculated the ? values for each channel. It turns out that, for almost all those values, the 10th percentile ? value is 0.125 the median, and the 90th percentile ? value is 12.5 times the median, though for 1M sats it’s 0.21 and 51x, which probably reflects that the median fee is not 51 for these channels!
Nonetheless, this suggests we can calculate the “expected ?” using the median capacity of channels we could use for a payment (i.e. those with capacity >= amount), and the median feerate of those channels. We can then bias it by a factor of 10 or so either way, to reasonably promote certainty over fees or vice versa.
So, in the internal API for the moment I accept a frugality factor, generally 0.1 (not frugal, prefer certainty to fees) to 10 (frugal, prefer fees to certainty), and derive ?:
? = -log((median_capacity_msat + 1 – amount_msat) / (median_capacity_msat + 1)) * frugality / (median_fee + 1)
The median is selected only from the channels with capacity > amount, and the +1 on the median_fee covers the case where median fee turns out to be 0 (such as in one of my tests!).
Note that it’s possible to try to send a payment larger than any channel in the network, using MPP. This is a corner case, where you generally care less about fees, so I set median_capacity_msat in the “no channels” case to amount_msat, and the resulting ? is really large, but at that point you can’t be fussy about fees!