renepickhardt
commented
2 years ago This is a very interesting issue and I will look very closely what results you will arrive at. Obviously the best split is computed via a min cost flow but I assume you want to avoid this as min cost flow computations are more expensive than candidate path generation via dijkstra... That being said I will leave you with a few high level observations and links to the papers that might be helpful.
According to formula (8) in our paper on probabilistic path finding you can see that the expected number of attempts E[n] that are necessary to deliver k parts will be E[n]=k/s where s is the path success probability. Unfortunately s is not constant for various paths and also changes with the amount that you allocate to the path which seems to make the formula unusable. (This is actually the reason why we arrived at the formulation via min cost flows in the follow up paper) However there are still a few useful things that we can learn from it.
- if you take the full amount and compute the shortest path on the uncertainty network and its probability
syou will know that you will needE=1/sattempts without splitting. - Assuming you can identify the two most likely candidate paths (again this can be tricky as this might change with the amount) and they have a probability of
s_1(a_1)ands_2(a_2)witha_1 + a_2 = athe full amount to be sent you can compareE[n]=1/s(a)the expected number of attempt without splitting withE[n] = 2/(s_1(a_1) * s_2(a_2))the expected number necessary with2splits. Similarly you can do it with3splits and so on. We have done this in formulas (16) and (17) in the probabilistic path finding paper for strong simplified assumptions (e.g. all channels are of equal size and we split the payment also into equally sized junks) to arrive at a closed analytical formula that tells us how many parts we wish to split - Using the method of Lagrange multipliers you can actually with two candidate paths compute the exact split allocation between the most likeli and the second most likeli path. This will also work with 3,4 and more candidate paths. The only problem is that you will have to compute zeros of polynomials with increasing degrees which cannot be done analytically and becomes numerically also very quickly infeasible / instable. The problem with this approach besides the numerical instability is that with actual optimal splits you will also not have disjoint paths. If you formulate this with non disjoint paths you have actually written down exactly the min cost flow problem which you are trying to avoid which can be solved without looking at those polynomials.
- our main net experiments with the actual min cost flows solvers showed that we split into amounts that vary over several orders of magnitude meaning some payments over large channels will be larger than some payments via longer routs or smaller channels. This indicates that any splitting heuristic into disjoint paths is actually pretty far away from the optimal solution.
Given all that I guess the two most promissing approaches are the following.
- Go down the road from the second point of the above enumeration. And try to approximate the path probabilities of your splits. Again as you don't actually know optimal split amounts your approximation might be inacurate but it might still lead to some heuristic. So you could at least start with splits into equal chunks to get at least a feeling of when the expected number of attempts will be increasing again.
- Take a look at the smallest channel capacity of a reasonable path and look at the distance. Now say something like "I want always to have 90% channel success probability" which means that you can have 10% of the channel capacity. Given a 5 hop path and at least 90% channel success probability your overall probability for the path would be
0.9^5 = 0.59leading to1/0.59=1.69attempts on average. Something like this could lead to a reasonable first split amount and the others could be taken from there.
As said I will look closely what ideas you have. I was trying this for a couple of months until I arrived at a reformulation of the min cost flow problem which leads to the exact solution. I was not able to find any heuristics that I found satisfying but I will be excited if you can detect something that is easy enough and works well.
TheBlueMatt
tnull
We tend to be pretty conservative and avoid splitting payments quite a bit. That's fine, but we can probably be a bit smarter about when we split. Once we land #1227 we can maybe also adapt the scoring API to return more information, including things like "you shouldn't send more than N over this channel". One way to accomplish that may be to have a
RouterStateenum passed to the scorer that is first set toRouterState::ConservativeFirstPasswhere the scorer can be very aggressive, refusing to route more than a small % of most channels' guessed capacity. If that pass finds a route we can still take the happy path and return it immediately, if not we can do the later passes with a differentRouterStateand then do....something to combine the paths selected across the different conservatism scales.One thing I don't want to have is the state a lot of other nodes appear to have where they just always split all the time, which feels counter-productive and can cause other issues.
cc @jkczyz