From lnml at tnull.de Thu Mar 18 09:36:23 2021 From: lnml at tnull.de (Elias Rohrer) Date: Thu, 18 Mar 2021 10:36:23 +0100 Subject: [Lightning-dev] Towards more reliable payment path finding via probabilistic modeling the uncertainty of channel balance In-Reply-To: References: Message-ID: Dear Ren?, ah, it seems I overlooked that sentence. Thanks for clearing this up. I agree, filtering based on probability and then weighing based on cost is probably very similar to doing it vice versa. Kind Regards, Elias On 18 Mar 2021, at 10:12, Ren? Pickhardt wrote: > Dear Elias, > > Thanks for your kind words! > > In the paper we suggest clients sort paths by probability but skip the > ones > that charge fees that are too high for a user, which could be defined > in a > user setting. I should have repeated that when I expressed that > implicitly > with this sentence in my mail: > > "This means that nodes which provide a lot of liquidity and thus > utility > might be able to charge higher fees (as long as they are small enough > so > that users are willing to pay them)" > > I think that is very similar to your suggestion and of course one > could > include not only fees but other criteria while filtering. > > In general I think it is reasonable to be aware of the most likely > path as > the inverse probability is the number of expected attempts. This if > due to > failures and updating the knowledge and channel probabilities the > remaining > path probabilities drop below a certain (configurable) value one might > want > to stop trying or consider a more expensive path. > > So if for example a user was to say I am willing to pay up to 0.5% of > the > amount in routing fees but after a few attempts the likeliest path has > only > a 0.01% chance a client could say something like: "it is very unlikely > to > deliver the payment but if you pay 0.7% fees there is a chance (want > to > try?)" Of course at some point onchain / opening a new channel might > be > cheaper which would contribute to the potential emerging fee market. > > Instead of filtering paths by fees one could also weight the > probabilities > with the fees. An easy (but maybe not optimal) approach for that would > be > to multiply the log probabilities (which have to be low for high > success) > with the fees. That being said I think the main important result is > that we > should always be aware of (multi)path probabilities during the trial > and > error phase especially in order to make splitting decisions and to > determine when to stop trying > > Best Rene > > Elias Rohrer schrieb am Do., 18. M?rz 2021, 09:34: > >> Dear Ren?, >> >> thank you for the great work! >> >> One quick question regarding the consequence you mentioned: it seems >> plausible that manipulating the path choices would become harder, if >> the >> ability of doing so was correlated with the capacity locked in the >> network. >> However, if paths were only chosen regarding the probability of >> payment >> success (and neglecting accruing fees), couldn't high-capacity nodes >> in >> absence of competition simply raise their fee levels indefinitely, >> since >> they would be chosen regardless? Do you have any ideas how to protect >> against this? >> >> I imagine that some kind of 'mixed' strategy could be reasonable, in >> which >> certain paths are pre-filtered based on the probability of payment >> success, >> and then the final path is selected along the lines of the currently >> deployed fee rate/CLTV risk assessment? >> >> Kind Regards, >> >> Elias >> >> On 17 Mar 2021, at 13:50, Ren? Pickhardt via Lightning-dev wrote: >> >> Dear fellow Lightning Network developers, >> >> I am very pleased to share with you some research progress [0] with >> respect to achieving better payment path finding and a better >> reliability >> of the payment process. >> >> TL;DR summary: In payment (multi)path finding use the (multi)paths >> with >> the highest success probability instead of the shortest or cheapest >> ones. >> (multi)path success probability is the product of channel success >> probabilities. Given current data crawled on the Network the channel >> success probability grows with the capacity of the channel and with >> smaller >> amounts that are to be sent (which is both intuitively obvious). >> (Multi)path success probability thus declines exponentially the more >> uncertain channels are included. >> >> I understand that the actual payment path finding is not part of the >> spec >> but I think my results should be relevant to the list since: >> >> a) The payment pathfinding is currently based on trial and error >> approach >> which has consequences that have not been studied well in the context >> of >> the Lightning Network >> b) All implementations will use some heuristics in order to achieve >> pathfinding. >> c) Quick path finding is a crucial for a good user experience. >> d) The uncertainty of payment paths is frequently quoted as a major >> criticism of the Lightning Network (c.f. [1]) and I believe the >> methodology >> of this paper can be used to address this. >> >> The main breakthrough is that a very simple model that puts the >> uncertainty of channel balances at its heart. We belief the >> uncertainty of >> channel balance values is the main reason why some payments take >> several >> attempts and thus take more time. With the help of probability >> theory we >> are able to define the channel success and failure probabilities and >> similarly (multi)path success and failure probabilities. Other >> Failure >> reasons could also be included to the probability distributions. >> >> With the help of crawling small samples of the network we observe >> that the >> probability distributions of the channel balances can be estimated >> well >> with a uniform distribution (which was a little bit surprising) but >> leads >> to surprisingly easy formulas. We are able to quantify the >> uncertainty in >> the channels and use negative Bernoulli trials to compute the >> expected >> number of attempts that are necessary to deliver a payment of a >> particular >> amount from one node to another participant of the network. This can >> be >> used to abort the trial and error path finding if the probability >> becomes >> to low (expected number of attempts too high) >> >> We can mathematically show what people already knew (and draw >> conclusions >> like the mentioned ones from it): >> >> a) smaller amounts have higher success probabilities >> b) the success probability declines exponentially with the number of >> uncertain channels in a (multi)path. >> c) depending on the payment pair, amount and splitting strategy it >> can be >> decided into how many parts a payment should be split to achieve the >> highest success probability. >> d) In particular for small amounts splitting almost never makes >> sense. >> >> We demonstrate that sorting paths by their descending success >> probability >> during the trial and error payment process (instead of currently used >> heuristics like fees or route length) and updating the probabilities >> from >> current failures decreases the number of average attempts and >> produces a >> much faster delivery of payments. >> >> Additionally we looked what happened if BOLT14 [2] was implemented or >> nodes otherwise would pro-actively rebalance their channels according >> to >> previous research [3] and realized that the observed prior >> distribution >> changes from uniform to normal. This is great as small payments >> become even >> more likely (as one would intuitively assume and as previously >> showed) Our >> results show that probabilisitic path finding on a rebalanced network >> works >> even better (as in fewer failed attempts) which is yet another hint >> why >> BOLT14 might be a good idea. However as mentioned the results can be >> implemented even without BOLT14 or without other protocol changes by >> any >> implementation. >> >> One consequence from the paper that is not discussed heavily within >> the >> paper that I find pretty interesting is that if implementations >> follow the >> recommendation to use a probabilistic approach they will tend to >> route >> payments along high capacity channels. While the fee based routing >> can >> easily be gamed by dumping fees it is much harder to provide more >> liquidity. And if done this would actually provide a service to the >> network. This means that nodes which provide a lot of liquidity and >> thus >> utility might be able to charge higher fees (as long as they are >> small >> enough so that users are willing to pay them) which would probably >> allow >> the emergence of a real routing fee market. >> >> One note on the question of MPP: In the last couple weeks I have been >> collaborating with Christian Decker. I belief (by using the >> methodology >> from this paper) to also have a definite solution to the question of: >> >> How to split a payment into k parts and how many funds to allocate to >> each >> path to increase the (multi)path success probability. >> >> While this is is not addressed in the attached paper as we still need >> to >> run evaluations I can already share that an equal sized split as used >> in >> the paper (and by some implementations) is not preferable as one can >> easily >> see from this example: >> Imagine one is to deliver 100 satoshi and has to paths with 1 >> uncertain >> channel on each path. The first of capacity 101 and the second of >> 51. >> Obviously trying to send 100 satoshi along the 101 capacity channel >> is bad. >> Similarly splitting 50/50 and sending 50 Satoshi along the 51 satoshi >> capacity channel is also bad. Thus a split that allocates for example >> 67 >> Satoshi to the 101 capacity and 33 to the 51 satoshi channel seems >> way more >> reasonable. Actually 75/25 would probably be the best solution for >> such a >> setting. And no it is only random coincident that a binary splitter >> would >> have arrived at that split eventually (after potential miss trials) >> There is way more math theory of how to actually solve the >> optimization >> problem in the general case and how to find a split and paths that >> maximizes the probability of the attempts. I cannot share these >> results yet >> but I am pretty confident that there will be updates on that end very >> soon. >> >> with kind regards Rene >> >> [0]: https://arxiv.org/abs/2103.08576 Security and Privacy of >> Lightning >> Network Payments with Uncertain Channel Balances >> [1]: >> https://www.whatbitcoindid.com/podcast/peter-rizuns-lightning-critique-fud-or-fair >> [2]: https://github.com/lightningnetwork/lightning-rfc/pull/780 >> [3]: >> https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-December/002406.html >> >> -- >> https://www.rene-pickhardt.de >> >> Skype: rene.pickhardt >> >> _______________________________________________ >> 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: