Author: Stefan Richter 2021-08-30 12:28:01
Published on: 2021-08-30T12:28:01+00:00
In a Lightning-dev email thread, Stefan Reitshamer addressed some misunderstandings regarding the min-cost flow problem with concave functions. While it is NP-hard when the cost-function is of this form, it does not mean that finding good solutions for a subset of problems is impossible. Approximations will be easier to find and the LN-graph may have certain structures that make finding a solution easier.Additionally, ZmnSCPxj weighed in on the issue of non-zero base fees and proposed an alternative solution: optimizing for a maximum fee instead of optimizing for the exact fee. By virtually splitting up the entire payment into smaller bunches of value, the mincostflow algorithm solves individual bunches rather than individual msats. This effectively converts the base fee to a proportional fee, removing the zero-base-fee requirement imposed by the disect algorithm. The approximation has a bias against non-zero base fees but at least does not require it. It may be practical to have the payment unit be adjustable by a higher-level process.The Lightning Network (LN) protocol could be modified to allow the source to instruct arbitrary intermediate nodes to join and/or split payments, which would allow the output of the mincostflow algorithm to be used directly. This would imply that for this scheme, if any hop fails, the entire payment fails and has to be restarted "from the top". In contrast, the current LN splits only at the source and joins only at the destination. If any hop of an MPP fails in the current LN, only the sub-payment(s) going through that hop will need to be retried. In addition, the cost function can be exact with a fixed payment unit, which would also increase the anonymity set of individual sub-payments. However, this approximation may be undesirable, and the payment unit could be adjusted upwards or downwards depending on its effects. Such adjustments could be helped greatly by payment decorrelation; intermediate nodes would remain uncertain that multiple HTLCs with the same amount and the same in-channel and out-channel are from the same overall payment or not. If a hop were to fail to deliver in the modified LN protocol, then some join nodes would be left hanging, waiting for an incoming HTLC that will not arrive. The failure would have to be handled by a split node, when it receives an update_fail_htlc. That split node cannot propagate the failure backwards to the source since it would still have other outgoing HTLCs in play, which it cannot safely ignore; it can only propagate the failure backward if all the other outgoing HTLCs also fail.To support this, a split node could give a request-to-fail signal to its other outgoing HTLCs. Then, any other join nodes still waiting for an incoming HTLC would fail all its incoming HTLCs. Otherwise, an intermediate node receiving a request-to-fail signal from any incoming HTLCs would simply propagate this request-to-fail outwards to all its outgoing HTLCs. The LN community needs to get together for better payment success, and supporting whole-flow payments is worse than setting basefee=0.
Updated on: 2023-06-03T05:44:39.658096+00:00