Estimating Likelihood for Lightning Payments to be (in)feasible

[renepickhardt]

@harding

Businessperson Bob typically receives payments up to 0.05 BTC. His node management software occasionally runs a background job that calculates the average likelihood of feasibility of a 0.05 BTC payment from every node on the network to his node. The node management software also looks at current liquidity advertisements and simulates what would happen if Bob had a channel with the advertiser, calculating a hypothetical alternative average likelihood of feasibility. If the hypothetical alternative with a new channel has a significantly higher average likelihood of feasibility, Bob’s node management software automatically accepts the liquidity advertisement and opens the new channel.

This is a very interesting use case which I haven’t thought of so far and it certainly could be done in this way. I do have a few additional thoughts on this use case:

1. If a user was interested in the likelihood of feasibility of a payment from all other nodes he might want to look at the histogram of amounts that he could receive from any user. So for a given random wealth distribution (which can be sampled with this library as explained in this notebook) he could use this method to compute a feasible network state. From here one could use Gomory-Hu Trees to compute the all pair max flow more efficiently than computing a max flow problem from every user to Bob. Similar to this notebook one could compute the distribution of max flows / min cuts and have a more precise view. This is because besides the percentile of nodes that are below the amount which Bob wishes to receive one would also get confidence intervals (if for example this method was repeated for several random wealth distributions). Important: Assuming random liquidity in channels as I have done in the notebook to compute the min cut distribution is probably not as precise as starting from random wealth distributions.

2. Of course when sampling random wealth distributions Bob could take into account that he ownes x coins in his channels. Furthermore as Bob knows the capacity and state of his channels he could also know what wealth his peers own at least. putting these constraint to the polytope of wealth distributions from which to sample can be done with the above mentioned library.

3. Similar to 2. Bob could use his local knowledge see the receiving problem as max flow problem with his peers as sinks (assuming he has enough inbound liquidity in those channels) This knowledge would in particular be taken into account for the liquidity advertisement which he uses in his simulation. (Those are just som engineering / modelling optimizations. I am not sure how much improvement they will bring)

4. The biggest issue is that with larger lightning networks it will be always harder to successfully sample feasible wealth distributions from where to start the above described computation. That is because it seems that the likelihood for sampled Bitcoin wealth distributions to also be feasible on the lightning network declines when the network grows in size. Furthermore the test of feasibility is also rather costly. As discussed (out of band) with Stefan Richter (who was first to state this in our conversation) testing if a sampled wealth distribution has a feasible state cannot only be solved through linear integer programming but it boils down to solving a particular multi source multi sink max flow problem.

@harding

User Alice makes a regular monthly bill payment set up through BOLT12 offers. She’s configures her wallet to start to try paying 5 business days before the due date. The first try and first few automatic retries don’t succeed. Before her wallet marks the payment attempt as a failure or takes other steps, it checks the likelihood of feasibility. If it’s low but still practical, it will keep retrying at lengthening intervals for another few hours or days before finally marking the payment attempt as a failure.

Yes absolutely. Knowing the likelihood of feasibility for a payment and being able to decide how often to attempt a payment and when to give up to make an on chain transaction to either pay someone on chain or open a new channel is exactly the one application I had in mind.