📅 Original date posted:2022-05-16
📝 Original message:
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:
> 6:
> 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
Matt Corallo [ARCHIVE] /
npub1e4…jxmcu
2023-06-09 13:06:02
in reply to nevent1q…pxz2
Author Public Key
npub1e46n428mcyfwznl7nlsf6d3s7rhlwm9x3cmkuqzt3emmdpadmkaqqjxmcuPublished at
2023-06-09 13:06:02Event JSON
{
"id": "3632c44452c3d2a17581813e37612cfdf92f0e16e2b3cbd978a7c60fcbfd677f",
"pubkey": "cd753aa8fbc112e14ffe9fe09d3630f0eff76ca68e376e004b8e77b687adddba",
"created_at": 1686315962,
"kind": 1,
"tags": [
[
"e",
"8965b7a716192a7f5f8fc807387d903333f8cde5f07b362c599acf5e6453e4da",
"",
"root"
],
[
"e",
"d6bcb100fa588424a0986b5d54a72233467f1e8929c177e1618d969c6befc679",
"",
"reply"
],
[
"p",
"8a718cc163bd0c956b748cfd134e84f90a27d5fdaccac045fbc8e7693f0080b8"
]
],
"content": "📅 Original date posted:2022-05-16\n📝 Original message:\nIts probably worth somewhat disentangling the concept of switching to a minimum-cost flow routing \nalgorithm from the concept of \"scoring based on channel value and estimated available liquidity\".\n\nThese are two largely-unrelated concepts that are being mashed into one in this description - the \nfirst concept needs zero-base-fee to be exact, though its not clear to me that a heuristics-based \napproach won't give equivalent results in practice, given the noise in success rate compared to \ntheory here.\n\nThe second concept is something that LDK (and I believe CLN and maybe even eclair now) do already, \nthough lnd does not last I checked. For payments where MPP does not add much to success rate (i.e. \npayments where the amount is relatively \"low\" compared to available network liquidity) dijkstra's \nwith a liquidity/channel-size based scoring will give you the exact same result.\n\nFor cases where you're sending an amount which is \"high\" compared to available network liquidity, \ntaking a minimum-cost-flow algorithm becomes important, as you point out. Of course you're always \ngoing to suffer really slow payment and many retires in this case anyway.\n\nMatt\n\nOn 5/15/22 1:01 PM, Carsten Otto via Lightning-dev wrote:\n\u003e Dear all,\n\u003e \n\u003e the most recent version of lnd-manageJ [1] now includes basic, but usable,\n\u003e support for #PickhardtPayments. I kindly invite you to check out the code, give\n\u003e it a try, and use this work for upcoming experiments.\n\u003e \n\u003e Teaser with video: https://twitter.com/c_otto83/status/1525879972786749453\n\u003e \n\u003e The problem, heavily summarized:\n\u003e \n\u003e - Sending payments in the LN often fails, especially with larger amounts.\n\u003e - Splitting a large payment into smaller shards (using MPP) is helpful,\n\u003e as in general the smaller shards don't fail as often as a single large\n\u003e payment would. However, the success probability also drops\n\u003e exponentially with the number of channels included [2].\n\u003e - Finding routes through the LN is tricky, as the channels' liquidity is\n\u003e uncertain at the time of computing the routes and a simple \"trial and\n\u003e error\" approach might take too long.\n\u003e - There are several implementations using various heuristics, taking\n\u003e aspects like fees, previous failures, HTLC deltas, channel age, ...\n\u003e into account. Comparing these approaches is very hard.\n\u003e \n\u003e The gist of #PickhardtPayments:\n\u003e \n\u003e - The issue of finding MPP routes in the LN corresponds to the\n\u003e well-known minimum-cost flow problem in computer science (graph\n\u003e theory) with lots of related research, results, algorithms, ...\n\u003e - As shown in the paper [3] the results are optimal, no matter which\n\u003e \"cost\" function is used to reason about routing costs (fees) and/or\n\u003e reliability. However, depending on the characteristics of the\n\u003e function, actually finding optimal results can be extremely hard\n\u003e (NP-complete in some cases). By imposing the zero base fee limitation\n\u003e and assuming a uniform distribution of funds, fast implementations\n\u003e (polynomial time with sub-second runtimes) can be used.\n\u003e - Assuming (!) a uniform distribution of funds in each channel and zero\n\u003e base fee only, #PickhardtPayments offers an approach that is optimal,\n\u003e i.e. proven perfect and computationally feasible.\n\u003e - The most basic version only considers uncertainty costs for\n\u003e reliability, but it is possible (and implemented in lnd-manageJ) to\n\u003e also consider routing costs (fee rates) and optimize for both features\n\u003e to come up with reliable and cheap-ish MPPs.\n\u003e - The implementation of #PickhardtPayments in lnd-manageJ needs to\n\u003e ignore non-zero base fee channels to avoid extremely slow\n\u003e (NP-complete) computations. Furthermore, certain aspects are\n\u003e approximated [4]. As such, optimality claims are limited to the zero\n\u003e base fee subset of the LN, and real-world experiments might be tricky\n\u003e to interpret. However, as also shown in the testnet videos [5][6],\n\u003e first results are very promising!\n\u003e \n\u003e The real strength of #PickhardtPayments:\n\u003e \n\u003e - Liquidity information, for example obtained by previous failures, is\n\u003e taken into account. For each attempt, the relevant bits of information\n\u003e are obtained and will be used to guide the following attempts.\n\u003e - As the underlying algorithm is proven to be optimal, we do not need to\n\u003e rely on heuristics. Instead, the algorithm happily finds routes that\n\u003e may be very long (but very probable/cheap, for whatever reason), have\n\u003e a surprising number of shards, or rather odd amounts.\n\u003e - The underlying algorithm also deals with shared segments, i.e.\n\u003e individual channels that are used for more than one shard of the MPP,\n\u003e without oversaturating it.\n\u003e \n\u003e The code in lnd-manageJ:\n\u003e \n\u003e - Highly experimental, but it's a start!\n\u003e - lnd + gRPC middleware + Java/Spring + PostgreSQL is a bit more complex\n\u003e than necessary.\n\u003e - Only works with lnd.\n\u003e - Doesn't really work with lnd until issue #5746 [7] is fixed. I'd be\n\u003e very happy for someone to have a look at my proposal (PR #6543 [8])!\n\u003e - The code doesn't handle all corner cases, especially the\n\u003e less-than-usual failure codes. For example, if a node decides to raise\n\u003e the fee rate, the corresponding channel will be ignored for a while as\n\u003e I'm too lazy to think about how to update the information in the data\n\u003e structure used to compute the MPP.\n\u003e - Pending shards (neither failed nor settled) just cause the whole MPP\n\u003e to hang until something times out. Most likely this can't be fixed\n\u003e without stuckless payments?\n\u003e \n\u003e I'd be very happy to discuss implementation details (not on this list, I\n\u003e guess?) and help with upcoming (mainnet?) benchmarks and experiments\n\u003e (René Pickhardt is also interested in helping with this). Given a fix\n\u003e for the blocking lnd issue, I'd be happy to let my node c-otto.de take\n\u003e part in some experiments.\n\u003e \n\u003e Last but not least, a huge thank you to René Pickhardt for lots of\n\u003e insightful discussions, proof reading, and of course (together with\n\u003e Stefan Richter) the actual work of coming up with #PickhardtPayments!\n\u003e \n\u003e Best regards,\n\u003e Carsten\n\u003e \n\u003e 1: https://github.com/C-Otto/lnd-manageJ/blob/main/PickhardtPayments.md\n\u003e 2: https://arxiv.org/abs/2103.08576\n\u003e 3: https://arxiv.org/abs/2107.05322\n\u003e 4: https://lists.linuxfoundation.org/pipermail/lightning-dev/2022-March/003510.html\n\u003e 5: https://c-otto.de/pp/pp.mp4\n\u003e 6: https://c-otto.de/pp/lnd.mp4\n\u003e 7: https://github.com/lightningnetwork/lnd/issues/5746\n\u003e 8: https://github.com/lightningnetwork/lnd/pull/6543\n\u003e \n\u003e \n\u003e _______________________________________________\n\u003e Lightning-dev mailing list\n\u003e Lightning-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev",
"sig": "395634b147d9493f38de86bdddaf00ca3a5c1c00c73b77df8234eeb69f258703ece1e97ebc9cec6713e320ebee24278d6c539bc02f102a38c6caab578177b75b"
}