{"type":"rich","version":"1.0","title":"Elias Rohrer [ARCHIVE] wrote","author_name":"Elias Rohrer [ARCHIVE] (npub12v…7qc6w)","author_url":"https://yabu.me/npub12v3sf3cjg33dwx6g5em2l9h0tuf3xjky5pdtuhclfaw852ukt6xqf7qc6w","provider_name":"njump","provider_url":"https://yabu.me","html":"📅 Original date posted:2021-03-18\n📝 Original message:\nDear René,\n\nthank you for the great work!\n\nOne quick question regarding the consequence you mentioned: it seems \nplausible that manipulating the path choices would become harder, if the \nability of doing so was correlated with the capacity locked in the \nnetwork. However, if paths were only chosen regarding the probability of \npayment success (and neglecting accruing fees), couldn't high-capacity \nnodes in absence of competition simply raise their fee levels \nindefinitely, since they would be chosen regardless? Do you have any \nideas how to protect against this?\n\nI imagine that some kind of 'mixed' strategy could be reasonable, in \nwhich certain paths are pre-filtered based on the probability of payment \nsuccess, and then the final path is selected along the lines of the \ncurrently deployed fee rate/CLTV risk assessment?\n\nKind Regards,\n\nElias\n\nOn 17 Mar 2021, at 13:50, René Pickhardt via Lightning-dev wrote:\n\n\u003e Dear fellow Lightning Network developers,\n\u003e\n\u003e I am very pleased to share with you some research progress [0] with \n\u003e respect\n\u003e to achieving better payment path finding and a better reliability of \n\u003e the\n\u003e payment process.\n\u003e\n\u003e TL;DR summary: In payment (multi)path finding use the (multi)paths \n\u003e with the\n\u003e highest success probability instead of the shortest or cheapest ones.\n\u003e (multi)path success probability is the product of channel success\n\u003e probabilities. Given current data crawled on the Network the channel\n\u003e success probability grows with the capacity of the channel and with \n\u003e smaller\n\u003e amounts that are to be sent (which is both intuitively obvious).\n\u003e (Multi)path success probability thus declines exponentially the more\n\u003e uncertain channels are included.\n\u003e\n\u003e I understand that the actual payment path finding is not part of the \n\u003e spec\n\u003e but I think my results should be relevant to the list since:\n\u003e\n\u003e a) The payment pathfinding is currently based on trial and error \n\u003e approach\n\u003e which has consequences that have not been studied well in the context \n\u003e of\n\u003e the Lightning Network\n\u003e b) All implementations will use some heuristics in order to achieve\n\u003e pathfinding.\n\u003e c) Quick path finding is a crucial for a good user experience.\n\u003e d) The uncertainty of payment paths is frequently quoted as a major\n\u003e criticism of the Lightning Network (c.f. [1]) and I believe the \n\u003e methodology\n\u003e of this paper can be used to address this.\n\u003e\n\u003e The main breakthrough is that  a very simple model that puts the\n\u003e uncertainty of channel balances at its heart. We belief the \n\u003e uncertainty of\n\u003e channel balance values is the main reason why some payments take \n\u003e several\n\u003e attempts and thus take more time.  With the help of probability theory \n\u003e we\n\u003e are able to define the channel success and failure probabilities and\n\u003e similarly (multi)path success and failure probabilities. Other Failure\n\u003e reasons could also be included to the probability distributions.\n\u003e\n\u003e With the help of crawling small samples of the network we observe that \n\u003e the\n\u003e probability distributions of the channel balances can be estimated \n\u003e well\n\u003e with a uniform distribution (which was a little bit surprising) but \n\u003e leads\n\u003e to surprisingly easy formulas.  We are able to quantify the \n\u003e uncertainty in\n\u003e the channels and use negative Bernoulli trials to compute the expected\n\u003e number of attempts that are necessary to deliver a payment of a \n\u003e particular\n\u003e amount from one node to another participant of the network. This can \n\u003e be\n\u003e used to abort the trial and error path finding if the probability \n\u003e becomes\n\u003e to low (expected number of attempts too high)\n\u003e\n\u003e We can mathematically show what people already knew (and draw \n\u003e conclusions\n\u003e like the mentioned ones from it):\n\u003e\n\u003e a) smaller amounts have higher success probabilities\n\u003e b) the success probability declines exponentially with the number of\n\u003e uncertain channels in a (multi)path.\n\u003e c) depending on the payment pair, amount and splitting strategy it can \n\u003e be\n\u003e decided into how many parts a payment should be split to achieve the\n\u003e highest success probability.\n\u003e d) In particular for small amounts splitting almost never makes sense.\n\u003e\n\u003e We demonstrate that sorting paths by their descending success \n\u003e probability\n\u003e during the trial and error payment process (instead of currently used\n\u003e heuristics like fees or route length) and updating the probabilities \n\u003e from\n\u003e current failures decreases the number of average attempts and produces \n\u003e a\n\u003e much faster delivery of payments.\n\u003e\n\u003e Additionally we looked what happened if BOLT14 [2] was implemented or \n\u003e nodes\n\u003e otherwise would pro-actively rebalance their channels according to \n\u003e previous\n\u003e research [3] and realized that the observed prior distribution changes \n\u003e from\n\u003e uniform to normal. This is great as small payments become even more \n\u003e likely\n\u003e (as one would intuitively assume and as previously showed) Our results \n\u003e show\n\u003e that probabilisitic path finding on a rebalanced network works even \n\u003e better\n\u003e (as in fewer failed attempts) which is yet another hint why BOLT14 \n\u003e might be\n\u003e a good idea. However as mentioned the results can be implemented even\n\u003e without BOLT14 or without other protocol changes by any \n\u003e implementation.\n\u003e\n\u003e One consequence from the paper that is not discussed heavily within \n\u003e the\n\u003e paper that I find pretty interesting is that if implementations follow \n\u003e the\n\u003e recommendation to use a probabilistic approach they will tend to route\n\u003e payments along high capacity channels. While the fee based routing can\n\u003e easily be gamed by dumping fees it is much harder to provide more\n\u003e liquidity. And if done this would actually provide a service to the\n\u003e network. This means that nodes which provide a lot of liquidity and \n\u003e thus\n\u003e utility might be able to charge higher fees (as long as they are small\n\u003e enough so that users are willing to pay them) which would probably \n\u003e allow\n\u003e the emergence of a real routing fee market.\n\u003e\n\u003e One note on the question of MPP: In the last couple weeks I have been\n\u003e collaborating with Christian Decker. I belief (by using the \n\u003e methodology\n\u003e from this paper) to also have a definite solution to the question of:\n\u003e\n\u003e How to split a payment into k parts and how many funds to allocate to \n\u003e each\n\u003e path to increase the (multi)path success probability.\n\u003e\n\u003e While this is is not addressed in the attached paper as we still need \n\u003e to\n\u003e run evaluations I can already share that an equal sized split as used \n\u003e in\n\u003e the paper (and by some implementations) is not preferable as one can \n\u003e easily\n\u003e see from this example:\n\u003e Imagine one is to deliver 100 satoshi and has to paths with 1 \n\u003e uncertain\n\u003e channel on each path. The first of capacity 101 and  the second of 51.\n\u003e Obviously trying to send 100 satoshi along the 101 capacity channel is \n\u003e bad.\n\u003e Similarly splitting 50/50 and sending 50 Satoshi along the 51 satoshi\n\u003e capacity channel is also bad. Thus a split that allocates for example \n\u003e 67\n\u003e Satoshi to the 101 capacity and 33 to the 51 satoshi channel seems way \n\u003e more\n\u003e reasonable. Actually 75/25 would probably be the best solution for \n\u003e such a\n\u003e setting. And no it is only random coincident that a binary splitter \n\u003e would\n\u003e have arrived at that split eventually (after potential miss trials)\n\u003e There is way more math theory of how to actually solve the \n\u003e optimization\n\u003e problem in the general case and how to find a split and paths that\n\u003e maximizes the probability of the attempts. I cannot share these \n\u003e results yet\n\u003e but I am pretty confident that there will be updates on that end very \n\u003e soon.\n\u003e\n\u003e with kind regards Rene\n\u003e\n\u003e [0]: https://arxiv.org/abs/2103.08576 Security and Privacy of \n\u003e Lightning\n\u003e Network Payments with Uncertain Channel Balances\n\u003e [1]:\n\u003e https://www.whatbitcoindid.com/podcast/peter-rizuns-lightning-critique-fud-or-fair\n\u003e [2]: https://github.com/lightningnetwork/lightning-rfc/pull/780\n\u003e [3]:\n\u003e https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-December/002406.html\n\u003e\n\u003e -- \n\u003e https://www.rene-pickhardt.de\n\u003e\n\u003e Skype: rene.pickhardt\n\n\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\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20210318/e55f0d5d/attachment-0001.html\u003e"}