This is joint work work with Stefan Richter. It was initiated as follow-up research of the probabilistic payment delivery paper on the Lightning Network and addresses the question of how to optimally conduct a multipart payment (MPP) split. Hence the repository name mpp-splitter.
The paper that you find in this repository also exists as a pdf preprint on arxiv.org.
The 2 main ideas are to quantify the uncertainty of channel balances with the help of probability theory and to transform the problem of finding the most optimal mpp split (with respect to high likelihood and low fees) to an integer min-cost flow problem with a separable convex cost function.
This result naturally leads to a round-based algorithm of min-cost flow computations by updating the uncertainty about the balance values in the network with the feedback gained from previous splits. In a simulated environment this method enables nodes to quickly discover channels and paths with enough liquidity to deliver payments of sizes that are close to the total local balance of the sender (given the liquidity actually exists on the network, which according to tests happens in about 95% of all cases).
Thus this method allows for delivering payments that are orders of magnitude larger than what has currently been reported.
There is a python package being actively developed which can be used to conduct mainnet tests and simulations at
https://github.com/renepickhardt/pickhardtpayments.
I strongly encourage you to follow the above mentioned repository. However it is based on the observation that the miniumum cost flow problem can be speed up in computation by piece wise linearization and transforming the problem to a discrete integer cost problem. A minimal example using the google ortools lib can be found in this repo
There is also a Java based implementation of our results by Carsten Otto which currently needs a hand patched fix of lnd as lightning labs did not fix their mpp API. Additionally I helped to integrate part of our results in core lighting as they switched to probabilistic payment delivery and ldk did the same with the inclusion of the uncertainty network. While eclair is going a similar way as ldk and also switched to include the uncertainty cost in payment delivery there lnd has open issues figuring out if they want to include our results.
This research was partially funded by the Norwegian University of Science and Technology
However as described in the Paper there is a lot of work (and probably also research on the way) that needs to be done in order to make this technology deployable on the Lightning Network.
In particular after I shared that a breakthrough had been discovered by us I had many venture capitalists and commercial parties offering large sums if we would find a way to commercialize this in a proprietary way. However I believe that knowledge should be free and openly available. As Stefan shared this view we decided to take the open path for that particular path finding problem (:
As those offers and opportunity costs exceeded anything that I ever imagined to earn and as funding in academia is always a gamble and the future is unclear I would highly appreciate if you want to help me become an independent Lightning Network developer and Researcher in the future. Thus I will highly appreciate if you consider to support my future work via:
- Bitcoin / Lightning at: https://donate.ln.rene-pickhardt.de
- Funny money at: https://www.patreon.com/renepickhardt
- Pointing this issue out to Bitcoin OGs or donors!
The code in this repository implements the min-cost flow cost scaling algorithm for convex costs presented in the textbook Network Flows Network Flows: Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti and James B. Orlin
The approach mainly follows chapter 9, 10.2 and 14.5 of the textbook.
Other good resources are the Lecture series by David Karger with lecture notes and more specifically this one. Finally the relevant subset of the recorded videos can be found at this playlist
Other good resources are the lecture notes by Dorit Hochbaum
- German Speaking Bitcoin Podcast Honigdachs invited us to the show 62 titled Pickhardt-Payments.
- SLP 361: https://stephanlivera.com/episode/361/
- Bitcoin Explained (The Van Wirdum Sjorsnado) : https://getpodcast.com/de/podcast/the-van-wirdum-sjorsnado/lightning-network-channel-payments-with-rene-pickhardt-episode-47_6636b03fc6
- Andreas M. Antonopoulos has noted that our method massively improves the Lightning Network and is a game changer.
- The work has been presented on What Bitcoin Did Podcast.
- German speaking podcaster Blocktrainer has created an easy to understand article about our results.
