Proof of Concept implementation of the Dijkstra Overpayment MPP Splitter

[renepickhardt]

This PR introduces 2 things:

1. A new technique to generate an MPP split in a greedy way that is both cheap and aims for reliability.
2. A potential answer to the question of how to plan and design a redundant overpayment which has been shown to be an effective technique to increase reliability.

WARNING!!! very experimental work in progress! Only use with caution and wait for the proper release

The DijkstraOverPayment class aims to find Dijkstra paths in a pragmatic way for redundant overpayments. In particular it is a proof of concept to generate an MPP-Split in an ad hoc way that seems to be more resonable than existing splitters which either do devide an conquorer or split to a certain amount or split to a predefined number of parts. This splitter finds low cost paths and greedly allocates as many sats as long as the reliability stays abvove a threshold

The main ideas are the following:

With respect to the cost function for candidate selection:

We use dijkstra to compute candidate paths as shortest paths with respect to our cost function

1.) Use a cost function for a unit that is the combination of linearized routing cost and linearized uncertainty cost 2.) smooth the routing cost (currently laplace smoothing with +100. The exact value needs to be found 3.) cost = (ppm + 100) * 1/capacity 4.) after a path is planned increase cost of each edge with a multiplier

with respect to allocation of funds to paths

The cost function favors paths with low routing costs thus the only question is how many sats to allocate? The following idea shall be used for motivation:

• We want each path to have a success probability of at least x%
• Thus let l be the length of the planned path and c be the capacity of the smallest channel.
• Then s = (c+1-a)/(c+1) is the success probability for the allocated amount a
• We require s >= x ** (1/l) which means the path has a probability of at least x
• For now we ignore prior knowledge and believe (Thus one reason for this to be WIP)
• knowing s at equality we solve for a --> a = (c+1) - s*(c+1) = (c+1)*(1-s)
• we allocate a sats to the candidate path

Number of generated / planned candidate paths

• for each path we compute it's expected value of delivered sats as its actual success probability mutitplied by the allocated sats
• As the expected value is linear we generate paths until the sum of the EVs is larger than our target total EV
• the target total EV is the amount we wish to deliver (e.g. given by an invoice) multiplied with a reliability factor (>= 1.0)

known short commings:

• subset of generated paths does not add to payment amount
• base fee is ignored
• learnt knowledge is ignored
• magic numbers are hard coded and not configureable (requires refactoring of the lib)
• output / api fits more to MCF approach
• handeling of edge cases
• assumes uniform distribution (which is actually easily fixable)

[renepickhardt]

An example where this patch is being used can be seen at: https://github.com/renepickhardt/Maximum-Expected-Value-Flows-For-Redundant-Overpayments/blob/main/code/Maximizing%20expected%20values.ipynb