[Lightning-dev] #PickhardtPayments implemented in lnd-manageJ

Carsten Otto bitcoin at c-otto.de
Sun May 15 20:01:58 UTC 2022


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: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20220515/d3f70c90/attachment.sig>


More information about the Lightning-dev mailing list