From bitcoin at c-otto.de Sun May 15 20:01:58 2022 From: bitcoin at c-otto.de (Carsten Otto) Date: Sun, 15 May 2022 22:01:58 +0200 Subject: [Lightning-dev] #PickhardtPayments implemented in lnd-manageJ Message-ID: Dear all, the most recent version of lnd-manageJ [1] now includes basic, but usable, support for #PickhardtPayments. I kindly invite you to check out the code, give it a try, and use this work for upcoming experiments. Teaser with video: https://twitter.com/c_otto83/status/1525879972786749453 The problem, heavily summarized: - Sending payments in the LN often fails, especially with larger amounts. - Splitting a large payment into smaller shards (using MPP) is helpful, as in general the smaller shards don't fail as often as a single large payment would. However, the success probability also drops exponentially with the number of channels included [2]. - Finding routes through the LN is tricky, as the channels' liquidity is uncertain at the time of computing the routes and a simple "trial and error" approach might take too long. - There are several implementations using various heuristics, taking aspects like fees, previous failures, HTLC deltas, channel age, ... into account. Comparing these approaches is very hard. The gist of #PickhardtPayments: - The issue of finding MPP routes in the LN corresponds to the well-known minimum-cost flow problem in computer science (graph theory) with lots of related research, results, algorithms, ... - As shown in the paper [3] the results are optimal, no matter which "cost" function is used to reason about routing costs (fees) and/or reliability. However, depending on the characteristics of the function, actually finding optimal results can be extremely hard (NP-complete in some cases). By imposing the zero base fee limitation and assuming a uniform distribution of funds, fast implementations (polynomial time with sub-second runtimes) can be used. - Assuming (!) a uniform distribution of funds in each channel and zero base fee only, #PickhardtPayments offers an approach that is optimal, i.e. proven perfect and computationally feasible. - The most basic version only considers uncertainty costs for reliability, but it is possible (and implemented in lnd-manageJ) to also consider routing costs (fee rates) and optimize for both features to come up with reliable and cheap-ish MPPs. - The implementation of #PickhardtPayments in lnd-manageJ needs to ignore non-zero base fee channels to avoid extremely slow (NP-complete) computations. Furthermore, certain aspects are approximated [4]. As such, optimality claims are limited to the zero base fee subset of the LN, and real-world experiments might be tricky to interpret. However, as also shown in the testnet videos [5][6], first results are very promising! The real strength of #PickhardtPayments: - Liquidity information, for example obtained by previous failures, is taken into account. For each attempt, the relevant bits of information are obtained and will be used to guide the following attempts. - As the underlying algorithm is proven to be optimal, we do not need to rely on heuristics. Instead, the algorithm happily finds routes that may be very long (but very probable/cheap, for whatever reason), have a surprising number of shards, or rather odd amounts. - The underlying algorithm also deals with shared segments, i.e. individual channels that are used for more than one shard of the MPP, without oversaturating it. The code in lnd-manageJ: - Highly experimental, but it's a start! - lnd + gRPC middleware + Java/Spring + PostgreSQL is a bit more complex than necessary. - Only works with lnd. - Doesn't really work with lnd until issue #5746 [7] is fixed. I'd be very happy for someone to have a look at my proposal (PR #6543 [8])! - The code doesn't handle all corner cases, especially the less-than-usual failure codes. For example, if a node decides to raise the fee rate, the corresponding channel will be ignored for a while as I'm too lazy to think about how to update the information in the data structure used to compute the MPP. - Pending shards (neither failed nor settled) just cause the whole MPP to hang until something times out. Most likely this can't be fixed without stuckless payments? I'd be very happy to discuss implementation details (not on this list, I guess?) and help with upcoming (mainnet?) benchmarks and experiments (Ren? Pickhardt is also interested in helping with this). Given a fix for the blocking lnd issue, I'd be happy to let my node c-otto.de take part in some experiments. Last but not least, a huge thank you to Ren? Pickhardt for lots of insightful discussions, proof reading, and of course (together with Stefan Richter) the actual work of coming up with #PickhardtPayments! Best regards, Carsten 1: https://github.com/C-Otto/lnd-manageJ/blob/main/PickhardtPayments.md 2: https://arxiv.org/abs/2103.08576 3: https://arxiv.org/abs/2107.05322 4: https://lists.linuxfoundation.org/pipermail/lightning-dev/2022-March/003510.html 5: https://c-otto.de/pp/pp.mp4 6: https://c-otto.de/pp/lnd.mp4 7: https://github.com/lightningnetwork/lnd/issues/5746 8: https://github.com/lightningnetwork/lnd/pull/6543 -- Dr. Carsten Otto carsten at c-otto.de https://c-otto.de -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 195 bytes Desc: not available URL: