Bastien TEINTURIER [ARCHIVE] on Nostr: 📅 Original date posted:2022-05-17 📝 Original message: I completely agree with ...

📅 Original date posted:2022-05-17
📝 Original message:
I completely agree with Matt, these two components are completely
independent
and too often conflated. Scoring channels and estimating liquidity is
something
that has been regularly discussed by implementations for the last few years,
where every implementation did its own experiments over time.

Eclair has quite a large, configurable set of heuristics around channel
scoring,
along with an A/B testing system that we've been using for a while on
mainnet
(see [1] for details). We've also been toying with channel liquidity
estimation for
more than half a year, which you can follow in [2] and [3].

These are heuristics, and it's impossible to judge whether they work or not
until
you've tried them on mainnet with real payments, so I strongly encourage
people
to run such experiments. But when you do, you should have enough volume for
the result data to be statistically meaningful and you should do A/B
testing,
otherwise you can make the data say pretty much everything you want. What
I believe is mostly missing is the volume, the network doesn't have enough
real
payments yet IMHO for this data to accurately say that one heuristic is
better
than another.

Using an MCF algorithm instead of dijkstra is useful when relaying large
payments
that will need to be split aggressively to reach the destination. It does
make a lot
of sense in that scenario. However, it's important to also take a step back
and
look at whether it is economical to make such payments on lightning.

For a route with an aggregated proportional fee of 1000ppm, here is a rough
comparison of the fees between on-chain and lightning:

* At 1 sat/byte on-chain, payments above 2mBTC cost less on-chain than
off-chain
* At 10 sat/byte on-chain, payments above 20mBTC cost less on-chain than
off-chain
* At 25 sat/byte on-chain, payments above 50mBTC cost less on-chain than
off-chain
* And so on (just keep multiplying)

Of course, making payments on lightning has more benefits than just fees,
they
also confirm faster than on-chain payments, but I think it's important to
keep these
figures in mind.

It would be also useful to think about the shape of the network. Using an
MCF
algorithm makes sense when payments are saturating channels. But if channels
are much bigger than your payment size, this is probably overkill. If
channels are
small "at the edges of the network" and bigger than payments at the "core
of the
network", and we're using trampoline routing [4], it makes sense to run
different
path-finding algorithms depending on where we are (e.g. MCF at the edges on
a small subset of the graph and dijkstra inside the core).

I'm very happy that all this research is happening and helping lightning
payments
become more reliable, thanks for everyone involved! I think the design
space is
still quite large when we take everything into account, so I expect that
we'll see
even more innovation in the coming years.

Cheers,
Bastien

[1]
https://github.com/ACINQ/eclair/blob/10eb9e932f9c0de06cc8926230d8ad4e2d1d9e2c/eclair-core/src/main/resources/reference.conf#L237
[2] https://github.com/ACINQ/eclair/pull/2263
[3] https://github.com/ACINQ/eclair/pull/2071
[4] https://github.com/lightning/bolts/pull/829


Le lun. 16 mai 2022 à 22:59, Matt Corallo <lf-lists at mattcorallo.com> a
écrit :

> 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
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20220517/0a3105b6/attachment-0001.html>;