From lf-lists at mattcorallo.com Mon May 16 20:59:05 2022 From: lf-lists at mattcorallo.com (Matt Corallo) Date: Mon, 16 May 2022 13:59:05 -0700 Subject: [Lightning-dev] #PickhardtPayments implemented in lnd-manageJ In-Reply-To: References: Message-ID: Its probably worth somewhat disentangling the concept of switching to a minimum-cost flow routing algorithm from the concept of "scoring based on channel value and estimated available liquidity". These are two largely-unrelated concepts that are being mashed into one in this description - the first concept needs zero-base-fee to be exact, though its not clear to me that a heuristics-based approach won't give equivalent results in practice, given the noise in success rate compared to theory here. The second concept is something that LDK (and I believe CLN and maybe even eclair now) do already, though lnd does not last I checked. For payments where MPP does not add much to success rate (i.e. payments where the amount is relatively "low" compared to available network liquidity) dijkstra's with a liquidity/channel-size based scoring will give you the exact same result. For cases where you're sending an amount which is "high" compared to available network liquidity, taking a minimum-cost-flow algorithm becomes important, as you point out. Of course you're always going to suffer really slow payment and many retires in this case anyway. Matt On 5/15/22 1:01 PM, Carsten Otto via Lightning-dev wrote: > 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 > > > _______________________________________________ > Lightning-dev mailing list > Lightning-dev at lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev