Hi all.
usually I'm just a reader of the mailing list, but I'm preparing a presentation
about my research and I think t-bash make exactly the point of the problem that
I'm trying to solve. So I use the t-bast words because I can not do better.
>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
betterthan another.
and
>However, it's important to also take a step back and
look at whether it is economical to make such payments on lightning.
In particular, in the network, we can have different views and different usage,
like routing node, mobile node, or daily usage node, and one of the things that
I'm trying to abstract is precise "how to make the step back, and collect all I
necessary information in a common way" so in this way the own research that
each implementation makes can be shared and also verified if it is true for
other implementation.
More importantly, if we have a way to collect metrics in the node without
running a custom version of the node, we can collect data for the real
environment, extract all the information that we want, and also some fancy
benchmark for node performance.
Well there is already a draft implementation where i'm trying to build a system
to make a step back and collect some open data to make maybe some standard
metrics. https://github.com/LNOpenMetrics/lnmetrics.rfc
In addition, I think that MCF is the way to go for the path finding also
because it is just a way to use dijkstra in a different way (ok, I know it slow
because all the basic MCF algorithm use Bellman Ford), with the only think that
right now we don't know what we are trying to minimize (fee? bad channel? all
together? up to the user?)
Cheers!
Vincent.
https://github.com/vincenzopalazzo
------- Original Message -------
On Tuesday, May 17th, 2022 at 9:23 AM, Bastien TEINTURIER <bast...@acinq.fr>
wrote:
> 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-li...@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: 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
_______________________________________________
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
