Vincent [ARCHIVE] / is on Nostr

⚠️ This account is not associated with a real person. It's an archival account for mailing list messages.
🗓️ Active from 2021-09-16 to 2022-05-18
💬 Posted a total of 2 messages
📚 Participated in the following categories: Lightning-dev
🔇 Please do not DM this user as it's used for archive purposes only.

Last Notes

2023-06-09 13:06:03

- reply

📅 Original date posted:2022-05-18
📝 Original message:
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 <bastien at 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-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: 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 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/20220518/d8e1a803/attachment-0001.html>

2023-06-09 13:03:42

- reply

📅 Original date posted:2021-09-16
📝 Original message:
Hi.
Thanks for the reference, but I missed where you want save space with this compression on the Merkle Tree.
Regards.
Vincent.
vincenzo.palazzo at protonmail.com
https://github.com/vincenzopalazzo
‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Thursday, September 16th, 2021 at 5:15 AM, shymaa arafat <shymaa.arafat at gmail.com> wrote:
> Allow me to introduce this simple idea that could be useful ...
>
> -The Intuition was some discussion on Utreexo project about storage saving and some traversing issues in handling the UTXOS Merkle Tree/ forest; that is N internal nodes need to be stored along with 2N pointers (left&right), + maybe 1 more pointer in the leaves special nodes to handle different traversing options (insert, delete, & differently proof fetch that traverse aunt or niece node according to your implementation
> https://github.com/mit-dci/utreexo/discussions/316)
> .
>
> Then, I thought of a simple idea that gets rid of all the pointers; specially appealing when we have all trees are full (complete) in the forest, but can work for any Merkle Tree:
>
> - 2D array with variable row size; R[j] is of length (N/2^j)
> -For example when N=8 nodes
> R[0]=0,1,2,...,7
> R[1]=8,9,10,11
> R[2]=12,13
> R[3]=14
> .
> -We can see that total storage is just 2N-1 nodes,
> no need for pointers, and traversing could be neat in any direction with the right formula:
>
> -Pseudo code to fetch proof[i] ...
>
> //direction to know + or -
> If ((i mod 2)==0) drct=1;
> else drct=-1;
> // first, the sibling node
> proof[i]=R[0,i+drct]
>
> //add the rest thru loop
> For(j=1; j≤logN; j++)
> { index= i/(2^j)+drct;
> proof[i]=Add(R[j,index]);
> }
>
> -In fact it's just the simple primitive approach of transforming a recursion to an iteration, and even if Utreexo team solved their problem differently I thought it is worth telling as it can work for any Merkle Tree
> .
> Thanks for your time,
> Shymaa M Arafat
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20210916/42856a25/attachment.html>