{"type":"rich","version":"1.0","author_name":"npub1zlxd3xlzjhq2ue03e5m5p2w6mp8v3dkhq5r39flsftjjsje04wvsdd2k4w","author_url":"https://nostr.ae/npub1zlxd3xlzjhq2ue03e5m5p2w6mp8v3dkhq5r39flsftjjsje04wvsdd2k4w","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2022-03-11\n📝 Original message:\nDear fellow Lightning Developers,\n\nI am pleased (and a bit proud) to be able to inform you that I finally\nfound a quick way to approximate the slow minimum convex cost flow\ncomputation. This is necessary for optimally reliable and cheap payment\nflows [0] to deliver large multi part payments over the Lightning Network.\nThe proposed solution happens via piecewise linearization [1] of the min\ncost flow problem on the uncertainty network which we face in order to\ncompute the optimal split and planning of large amount multi part payments.\nThe notion of \"optimal\" is obviously subjective with respect to the chosen\ncost function. As known we suggest to include the negative logarithm of\nsuccess probabilities based on the likelihood that enough liquidity is\navailable on a channel as a dominant feature of the used cost function. We\ngive the background for this in [2] which since then has already been\npicked up by c-lightning and LDK. The c-lightning team even published\nbenchmarks showing significant improvement in payment speed over their\npreviously used cost function [2b].\n\nLet me recall that one of the largest criticisms and concerns of our\napproach to use minimum cost flows for payment delivery back in July /\nAugust last year (especially by the folks from lightning labs) was that the\nmin cost flow approach would be impractical due to run time constrains.\nThus I am delighted that with the now published code [3] (which has exactly\n100 lines including data import and parsing and ignoring comments) we are\nable to compute a reasonable looking approximation to the optimal solution\nin a sub second run time on the complete public channel graph of the\nLightning Network. This is achieved via piecewise linearization of the\nconvex cost function and invoking of a standard linear min cost flow solver\n[4] for the linearized problem. This works quickly despite the fact that\nthe piecewise linearization adds a significant higher amount of arcs to the\nnetwork and blows up the size of the network on which we solve the min cost\nflow problem. This makes me fairly certain that with proper pruning of the\ngraph we might even reach the 100 millisecond runtime frontier, which would\nbe far faster than what I dreamed \u0026 hoped to be possible.\n\nThe currently widely deployed Dijkstra search to generate a single\ncandidate path takes roughly 100ms of runtime. It seems that with the\nruntime of the piecewise linearized problem the min cost flow approach is\nnow competitive from a runtime perspective. The flow computation is still a\nbit slower than Dijkstra in both theory and practice. However the piecewise\nlinearized min cost flow has the huge advantage that it generates several\ncandidate paths for a solid approximation of the optimal MPP split.\nRemember the exact min cost flow corresponds to the optimal MPP split. The\nlater was not used so far as the min cost flow was considered to be too\nslow. Yet the question how to split seems to be addressed as issues in\nimplementations [5][6][7] and acknowledged to be complicated (especially\nwith respect to fees) in [8]. This result is btw of particular interest for\nLSPs. If an LSP has to schedule x payments per second it can just do one\nflow computation with several sink nodes and plan all of those payments\nwith a single min cost flow computation. This globally optimizes the\npotentially heavy load that LSPs might have even if all payments were so\nsmall that no splitting was necessary.\n\nThe iPython notebook which I shared contains about 1 page to explain how to\nconduct a piecewise linear approximation. The quality of the approximation\nis not the major goal here as I am just focused to demonstrate the run time\nof the approach and the principle how to achieve this runtime. Thus I do\nthe piecewise linear approximation very roughly in the published code.\nSelecting the optimal piecewise approximation [9] will not change the the\nruntime of flow computation but only blows up the code to prepare the\nsolver. This is why I decided to keep the code as simple and short as\npossible even if that means that the approximation will be not as close to\nthe optimum as it could be in practice. For the same reason I did not\ninclude any code to update the uncertainty network from previously failed\nor successful attempts by using conditional success probabilities P(X\u003ea |\nmin_liquidity \u003c X \u003c max_liquidity ). People who are interested might look\nat my hands on instructions and explanations for coders in this\nrust-lightning issue [10]. The folks from LDK have picked this up and\nimplemented this already for single path payments in [11] which might be\nrelevant for people who prefer code over math papers. An obvious\noptimization of the piece wise linearization would be to chose the first\nsegment of the piecewise linear approximation with a capacity of the\ncertain liquidity and a unit cost of 0 for that piece.\n\nOur original papers describe everything only from a theoretical point of\nview and with simulations. However our mainnet experiments from July last\nyear [12] indicated that we easily have been able to deliver for example\n0.3679 BTC via a couple rounds of min cost flow computations through the\nLightning Network (given we accept the computational waiting time). This\nexperiment was too slow to be used in practice but confirmed our model and\napproach to deliver such large amounts. Given that the min cost flow\ncomputation is now significantly below the median onion round trip times it\nis my understanding that with these newly introduced techniques we should\nbe able to deliver substantial monetary amounts over the Lightning Network\nwithin a couple of seconds despite the uncertainty about the Liquidity in\nremote channels. While I am very excited about the result I think some\nprinciple roadblocks of the protocol are becoming more and more visible:\n\n1. The well known issue of hanging HTLCs. As of now I believe onion\nmessages would be great to acknowledge incoming HTLCs of multipart payments\nbut I certainly believe this will not be sufficient if we don't go for a\ncancelable \u0026 stuckless payment protocol as suggested in [13].\n2. I believe the Lightning Network Protocol should be able to handle\nredundant overpayments as suggested in [14] and [15] (The later paper\nderives independently of us the same success probabilities and tries to\nmaximize them!). This would allow to transform the problem of finding a\nflow that maximizes the success probability to a flow that expects to\ndeliver the amount of the invoice (when redundancy is applied) with a\nsingle round of min cost flow computation on average.\n\nLast but not least, please allow me to make a short remark on the (still to\nme very surprisingly controversial) base fee discussion: For simplicity I\ndid not include any fee considerations to the published code (besides a fee\nreport on how expensive the computed flow is). However in practice we wish\nto optimize at least for high reliability (via neg log success\nprobabilities) and cheap fees which in particular with the ppm is very\neasily possible to be included to the piece wise linearized cost function.\nWhile for small base fees it seems possible to encode the base fee into the\nfirst segment of the piecewise linearized approximation I think the base\nfee will still be tricky to be handled in practice (even with this\napproximation). For example if the base fee is too high the \"base fee\nadjusted\" unit cost of the first segment of the piecewise linearized\nproblem might be higher than the unit cost of the second segment which\neffectively would break the convexity. Thus I reiterate my earlier point\nthat from the perspective of the year long pursued goal of optimizing for\nfees (which all Dijkstra based single path implementations do) it seems to\nbe best if the non linearity that is introduced by the base fee would be\nremoved at all. According to discussions with people who crate Lightning\nNetwork explorer (and according to my last check of gossip) about 90% of\nchannels have a base fee of 1 sat or lower and ~38% of all channels already\nset their base fee away from the default value to 0 [16].\n\nI hope this mail was useful for you. Feel free to ask me anything if there\nshould be questions or if you need help to integrate those results into\nyour software!\n\nWith kind regards Rene Pickhardt\n\n[0]: https://arxiv.org/abs/2107.05322\n[1]: https://en.wikipedia.org/wiki/Piecewise_linear_function\n[2]: https://arxiv.org/abs/2103.08576\n[2b]:\nhttps://medium.com/blockstream/c-lightning-v0-10-2-bitcoin-dust-consensus-rule-33e777d58657\n\n[3]:\nhttps://github.com/renepickhardt/mpp-splitter/blob/master/Minimal%20Linearized%20min%20cost%20flow%20example%20for%20MPP.ipynb\n[4]: https://developers.google.com/optimization/flow/mincostflow\n[5]: https://github.com/lightningnetwork/lnd/issues/4203\n[6]: https://github.com/lightningdevkit/rust-lightning/issues/1276\n[7]: https://github.com/ElementsProject/lightning/issues/4753\n[8]: https://github.com/ACINQ/eclair/pull/1427\n[9]: http://www.iaeng.org/publication/WCECS2008/WCECS2008_pp1191-1194.pdf\n[10]:\nhttps://github.com/lightningdevkit/rust-lightning/issues/1170#issuecomment-972396747\n[11]: https://github.com/lightningdevkit/rust-lightning/pull/1227\n[12]: https://twitter.com/renepickhardt/status/1418849788531990530\n[13]:\nhttps://lists.linuxfoundation.org/pipermail/lightning-dev/2019-June/002029.html\n[14]: https://berkeley-defi.github.io/assets/material/1910.01834.pdf\n[15]: https://dl.acm.org/doi/10.1145/3479722.3480997\n[16]: https://lnrouter.app/graph/zero-base-fee\n\n-- \nhttps://ln.rene-pickhardt.de\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20220311/0ba5d2d0/attachment-0001.html\u003e"}