/mpp-splitter

We investigate how to split payments in multiple parts to improve payment reliability

Primary LanguageTeXApache License 2.0Apache-2.0

Optimally Reliable & Cheap Payment Flows on the Lightning Network

This is joint work work with Stefan Richter. It was initiated as follow-up research of the probabilistic payment routing 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.

Source Code

Since we did not find any open source min-cost flow solver for a general convex cost function we have implemented them in Scala and Python.

Due to illness I have to delay the upload of the code but we plan to share the code latest after July 19th

Funding & Future Work

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 commercalize 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:

More on Min-cost Flows

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 specificially 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

Media and Public