{"type":"rich","version":"1.0","title":"René Pickhardt [ARCHIVE] wrote","author_name":"René Pickhardt [ARCHIVE] (npub1zl…d2k4w)","author_url":"https://yabu.me/npub1zlxd3xlzjhq2ue03e5m5p2w6mp8v3dkhq5r39flsftjjsje04wvsdd2k4w","provider_name":"njump","provider_url":"https://yabu.me","html":"📅 Original date posted:2021-03-17\n📝 Original message:\nDear fellow Lightning Network developers,\n\nI am very pleased to share with you some research progress [0] with respect\nto achieving better payment path finding and a better reliability of the\npayment process.\n\nTL;DR summary: In payment (multi)path finding use the (multi)paths with the\nhighest success probability instead of the shortest or cheapest ones.\n(multi)path success probability is the product of channel success\nprobabilities. Given current data crawled on the Network the channel\nsuccess probability grows with the capacity of the channel and with smaller\namounts that are to be sent (which is both intuitively obvious).\n(Multi)path success probability thus declines exponentially the more\nuncertain channels are included.\n\nI understand that the actual payment path finding is not part of the spec\nbut I think my results should be relevant to the list since:\n\na) The payment pathfinding is currently based on trial and error approach\nwhich has consequences that have not been studied well in the context of\nthe Lightning Network\nb) All implementations will use some heuristics in order to achieve\npathfinding.\nc) Quick path finding is a crucial for a good user experience.\nd) The uncertainty of payment paths is frequently quoted as a major\ncriticism of the Lightning Network (c.f. [1]) and I believe the methodology\nof this paper can be used to address this.\n\nThe main breakthrough is that  a very simple model that puts the\nuncertainty of channel balances at its heart. We belief the uncertainty of\nchannel balance values is the main reason why some payments take several\nattempts and thus take more time.  With the help of probability theory we\nare able to define the channel success and failure probabilities and\nsimilarly (multi)path success and failure probabilities. Other Failure\nreasons could also be included to the probability distributions.\n\nWith the help of crawling small samples of the network we observe that the\nprobability distributions of the channel balances can be estimated well\nwith a uniform distribution (which was a little bit surprising) but leads\nto surprisingly easy formulas.  We are able to quantify the uncertainty in\nthe channels and use negative Bernoulli trials to compute the expected\nnumber of attempts that are necessary to deliver a payment of a particular\namount from one node to another participant of the network. This can be\nused to abort the trial and error path finding if the probability becomes\nto low (expected number of attempts too high)\n\nWe can mathematically show what people already knew (and draw conclusions\nlike the mentioned ones from it):\n\na) smaller amounts have higher success probabilities\nb) the success probability declines exponentially with the number of\nuncertain channels in a (multi)path.\nc) depending on the payment pair, amount and splitting strategy it can be\ndecided into how many parts a payment should be split to achieve the\nhighest success probability.\nd) In particular for small amounts splitting almost never makes sense.\n\nWe demonstrate that sorting paths by their descending success probability\nduring the trial and error payment process (instead of currently used\nheuristics like fees or route length) and updating the probabilities from\ncurrent failures decreases the number of average attempts and produces a\nmuch faster delivery of payments.\n\nAdditionally we looked what happened if BOLT14 [2] was implemented or nodes\notherwise would pro-actively rebalance their channels according to previous\nresearch [3] and realized that the observed prior distribution changes from\nuniform to normal. This is great as small payments become even more likely\n(as one would intuitively assume and as previously showed) Our results show\nthat probabilisitic path finding on a rebalanced network works even better\n(as in fewer failed attempts) which is yet another hint why BOLT14 might be\na good idea. However as mentioned the results can be implemented even\nwithout BOLT14 or without other protocol changes by any implementation.\n\nOne consequence from the paper that is not discussed heavily within the\npaper that I find pretty interesting is that if implementations follow the\nrecommendation to use a probabilistic approach they will tend to route\npayments along high capacity channels. While the fee based routing can\neasily be gamed by dumping fees it is much harder to provide more\nliquidity. And if done this would actually provide a service to the\nnetwork. This means that nodes which provide a lot of liquidity and thus\nutility might be able to charge higher fees (as long as they are small\nenough so that users are willing to pay them) which would probably allow\nthe emergence of a real routing fee market.\n\nOne note on the question of MPP: In the last couple weeks I have been\ncollaborating with Christian Decker. I belief (by using the methodology\nfrom this paper) to also have a definite solution to the question of:\n\nHow to split a payment into k parts and how many funds to allocate to each\npath to increase the (multi)path success probability.\n\nWhile this is is not addressed in the attached paper as we still need to\nrun evaluations I can already share that an equal sized split as used in\nthe paper (and by some implementations) is not preferable as one can easily\nsee from this example:\nImagine one is to deliver 100 satoshi and has to paths with 1 uncertain\nchannel on each path. The first of capacity 101 and  the second of 51.\nObviously trying to send 100 satoshi along the 101 capacity channel is bad.\nSimilarly splitting 50/50 and sending 50 Satoshi along the 51 satoshi\ncapacity channel is also bad. Thus a split that allocates for example 67\nSatoshi to the 101 capacity and 33 to the 51 satoshi channel seems way more\nreasonable. Actually 75/25 would probably be the best solution for such a\nsetting. And no it is only random coincident that a binary splitter would\nhave arrived at that split eventually (after potential miss trials)\nThere is way more math theory of how to actually solve the optimization\nproblem in the general case and how to find a split and paths that\nmaximizes the probability of the attempts. I cannot share these results yet\nbut I am pretty confident that there will be updates on that end very soon.\n\nwith kind regards Rene\n\n[0]: https://arxiv.org/abs/2103.08576 Security and Privacy of Lightning\nNetwork Payments with Uncertain Channel Balances\n[1]:\nhttps://www.whatbitcoindid.com/podcast/peter-rizuns-lightning-critique-fud-or-fair\n[2]: https://github.com/lightningnetwork/lightning-rfc/pull/780\n[3]:\nhttps://lists.linuxfoundation.org/pipermail/lightning-dev/2019-December/002406.html\n\n-- \nhttps://www.rene-pickhardt.de\n\nSkype: rene.pickhardt\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20210317/793a07dd/attachment.html\u003e"}