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@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
_______________________________________________
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
