Code for sub second runtime of piecewise linarization to quickly approximate the minimum convex cost flow problem (makes fast multi part payments with large amounts possible)

Summary:

The given context discusses various topics related to Lightning Network routing. The author suggests pruning channels with high unit costs on the first segment, especially if they are further away from the source and destination node, to reduce the size of the graph and improve runtime. They have also worked on a heuristic that could throw away about 90% of all channels and found the same flow in the pruned network as on the full network.The author explains how to integrate fees into the function by linearizing the cost function between two features, which would change the line accordingly. However, this trick for CLTV or latency-based features will not work for the base fee because one has to pay the full base fee at the end. Regarding private channels, the author notes that from a probabilistic payment delivery point of view, hiding liquidity can be detrimental. However, the author never rejected the idea to extend the current probabilistic model with a probabilistic node or channel provenance value. Finally, the author talks about the quality of approximation and how it is possible to find a solution without error by using a finite number that corresponds to the channels capacity and making segments of 1 satoshi each encoding what this satoshi would actually cost in the original function. However, the author has not spent time expressing the error in dependence of the number of segments N, but the results indicate that the error should be small enough in practice.In this message, the author thanks Carsten, Martin, and fellow lightning developers for verifying and acknowledging their recent findings about the runtime of finding a piecewise linearized approximation to the min cost flow problem. They also discuss the combination of parallel channels and its probabilistic benefits in terms of liquidity availability. The conversation then moves on to the optimal piecewise linearization and the size of each piece. The author explains that splitting all channels into the same number of pieces is well-motivated from a probabilistic point of view and discusses the potential benefits of studying the optimal piecewise linear approximation. Finally, the issue of leftovers after piecewise linearization is addressed, with the author stating that this should not be an issue as long as the domain is larger than N.The email contains a long list of transactions with various details such as source node, target node, probability, and fee rate. The total probability of the entire flow is 0.0032, the total fee is 248793.763 sats, and the effective fee rate is 0.498%. There are 39 arcs included in the payment flow. The writer advises not to get confused by the low probability as the first attempt always has high uncertainty and they will learn fast in each consequent round. The email signature includes the name and contact information of Rene Pickhardt, a website URL, and the Lightning-dev mailing list information.

Updated on: 2023-06-03T07:51:46.903373+00:00