Splitting strategies of payment amount in multi path payments

renepickhardt commented 4 years ago

Looking at:

https://github.com/lightningnetwork/lnd/blob/19006b108cbb24502ca7e583607bb501dc48f686/routing/payment_session.go#L221

I see that currently the payment session route planner splits the amount into half if it was too large. While from a CS perspective I find this strategy very reasonable I believe there might be more things to consider.

As discussed with ZmnSCPxj on the Lightning dev mailinglist at: https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-January/002418.html there is the chance to use the necessity of splitting a payment to also rebalance ones own channels in order to be better equipped in future to fulfill payment requests. In that post I have referenced a small standalone python code

The main code that splits a payment amount according to ones own channels in an statistically optimal (meaning to provide best locally balanced channels) way boils down to these few lines of code which are easily implemented in go and in LND. Sorry for the weired variable naming - which follows main

# amount that is to be paid.
a = 0.7

# initial balance of channels
b = [0.1*i for i in range(10, 0, -1)]

if (a > sum(b)):
    print("not enough funds to conduct such a payment")
    exit()

new_funds = sum(b) - a

# assuming all channels have capacity of 1 btc
cap = len(b)
nu = float(new_funds) / cap
ris = [1*(float(x)/1 - nu) for x in b]

real_ris = [x for x in ris if x > 0]
s = sum(real_ris)
payments = [a*x/s for x in real_ris]

A strategy could be that if a payment won't go through instead of splitting by two one could use this initial strategy to select amounts and local channels which should be used for those amounts.

I have not simulated the effects of my strategy and did not compare them with your behaviour. However keeping the results of the original research in mind I am confident that the splitting strategy that I propose would result in overall lower routing failure rates on the lightning network.

renepickhardt commented 4 years ago

I should mention that the line ris = [1*(float(x)/1 - nu) for x in b] is a little bit missleading as I multiply by 1 and devide by 1. This is because I assumed the capacity of the channel is 1. so in reality one would have to multiply and divide by the capacity of the channel for which the payment amount is computed.

joostjager commented 4 years ago

It is an interesting thought, trying to rebalance channels as you pay. Things to keep in mind with the current implementation are:

There is no upfront planning of how to split the payment. Every time we want to send a new htlc, RequestRoute is called with the outstanding amount. As the return value, it expects a single route for either the total outstanding or a part of that. The code above would need to be adapted to that.
If you pick the amount (based on local channel info) for which you want to start pathfinding and force this through a particular channel, what do you do if it fails to find a route?
If you force paths through particular channels to be sure the rebalancing goal is met, how does this interact with other optmization goals like fee and reliability?
Pathfinding is performed from receiver back to sender. Therefore you search for a path that delivers a particular amount at the receiver. The amount to send, including fees, is higher. This gives less control over how much your channel balance will actually change. Of course an alternative forward-looking algorithm could be added.

renepickhardt commented 4 years ago

If you pick the amount (based on local channel info) for which you want to start pathfinding and force this through a particular channel, what do you do if it fails to find a route?

There could be several strategies.

Try several paths that start along that channel maybe another path will go through
Exclude that channel Recompute with the adopted payment amount for the remaining channels
Drop down to the current implementation

Regarding the second strategy I would always internally sort / prioritize paths from the most uneven one to the least uneven ones. Meaning if for example the first two channels are able to send the suggested amount and the third channel fails we could take the amount that was supposed to be send on channel 3 to 10 (assuming 10 splits) and distribute it now over channels 4 through 10 or we could distribute it via 4 through 11.

If you force paths through particular channels to be sure the rebalancing goal is met, how does this interact with other optmization goals like fee and reliability?

it doesn't out of the box. But of course one could have a strategy that looks at all of those goals. As rebalancing is usful and currently certainly not free it might make sense to rebalance at least when making a payment. In particular if this is the standard and all nodes act like this overall reliability should at least statistically increase.

The amount to send, including fees, is higher. This gives less control over how much your channel balance will actually change.

I would argue that the fees on single paths are usually less than 1% of the amount to be send along that path and could thus be neglected in the calaculation of the split. If fees are significantly higher we have other problems anyway. Of course one could compute the split not for the payment amount but for the payment amount + 1 or 2 % imaginary fees. Then reduce all computed amounts so that the sum is the actual amount and hope that the fees along each path will finally arrive at the computed split. But I think - in particular with the other considerations that you mentioned - this would be overengineered.

renepickhardt commented 4 years ago

Just dropping the c-lightning plugin that prepares the split adopted to the c-lightning plugin. maybe it helps here to see how it was done for c-lightning: https://github.com/lightningd/plugins/pull/83

renepickhardt commented 3 years ago

Thought this might be relevant with respect to that question: https://arxiv.org/abs/2107.05322

renepickhardt commented 2 years ago

Thought this might be relevant with respect to that question: https://arxiv.org/abs/2107.05322

Also there is a scala implementation of the fast min cost flow approximation at https://github.com/renepickhardt/mpp-splitter/blob/master/code/scala/mincostflow/heuristic/MinCostFlow.scala

Computing a mcf and dissecting it to parts gives the optimal split (with respect to the selected cost function) this contradicts some of the older thoughts and suggestions in this issue.

renepickhardt commented 2 years ago

I have added code for a piecewise linearized formulation of the problem that runs in less than a second and produces a reasonable approxination to the optimal solution to the same repo. You can find it at:

https://github.com/renepickhardt/mpp-splitter/blob/master/Minimal%20Linearized%20min%20cost%20flow%20example%20for%20MPP.ipynb

I think that approach - if all engineering details (propper handling of uncertainty network, channel reserves, htlc limits, pruning of piecewise linearized problem, adding fees to the cost function) are included - should be very practical for implementations and as discussed on the mailinglist allow for large payment amounts to be handled

Note: the flow approach could still be used with the original idea in this thread of rebalancing ones own channels while conducting / planning a payment. Instead of initializing the min cost flow problem with all the supply of the amount that is to be delivered on the senders node one may split and distribute the supply to one's peers such that the mpp would rebalance / keep channels balanced. The in cost flow approachwould maintain the other optimization goals. This should answer pretty much all of the concerns that @joostjager initially voiced

renepickhardt commented 2 years ago

for those not following twitter @C-Otto has posted a baseic implementation to compute splits on top of lnd even using existing mission control data at: https://github.com/C-Otto/lnd-manageJ/issues/6..

Let me just cross post from my comment at the ldk repo

So far it is only the splitting logic and not the acutal payment loop and sending of onions. He computes a split of 0.5 BTC from his node to mine into 18 onions each of which has a probability higher than 50% to be deliverd. Meaning on the first attampt we can expect far less than half the onions to fail. his split can be seen at: http://web.archive.org/web/20220322080201/https://c-otto.de/rene.txt. As he indicated before the runtime of the solver was some 230 ms

{
  "amountSat" : "50000000",
  "probability" : 2.1549649398107696E-4,
  "routes" : [ {
    "amountSat" : "1000000",
    "channelIds" : [ "726473x703x1", "723312x509x1", "695077x1924x0" ],
    "probability" : 0.7806365608992074
  }, {
    "amountSat" : "1240000",
    "channelIds" : [ "726473x703x1", "725453x2192x0", "693476x1211x1", "607678x1509x1" ],
    "probability" : 0.7832342855787678
  }, {
    "amountSat" : "150000",
    "channelIds" : [ "726473x703x1", "725453x2192x0", "700081x698x1", "695339x624x1" ],
    "probability" : 0.9765214420387514
  }, {
    "amountSat" : "3600000",
    "channelIds" : [ "726473x703x1", "725453x2192x0", "701584x2083x1", "558577x633x1" ],
    "probability" : 0.5628769427691509
  }, {
    "amountSat" : "1400000",
    "channelIds" : [ "726473x703x1", "725453x2192x0", "704776x2087x1", "558568x1324x1" ],
    "probability" : 0.782495149685495
  }, {
    "amountSat" : "2470000",
    "channelIds" : [ "726473x703x1", "725453x2192x0", "727359x1244x0", "633778x1065x0" ],
    "probability" : 0.721747937413449
  }, {
    "amountSat" : "2000000",
    "channelIds" : [ "726473x703x1", "727788x1249x1", "728428x605x1", "704834x1737x4" ],
    "probability" : 0.6813327353327034
  }, {
    "amountSat" : "1530000",
    "channelIds" : [ "726473x703x1", "727904x1129x0", "727359x1244x0", "633778x1065x0" ],
    "probability" : 0.8251278610944093
  }, {
    "amountSat" : "4000000",
    "channelIds" : [ "726473x703x1", "727904x1129x0", "676072x1060x0", "686282x1219x0", "691162x595x0" ],
    "probability" : 0.5740134573960525
  }, {
    "amountSat" : "4860000",
    "channelIds" : [ "726473x703x1", "727904x1129x0", "693476x1211x1", "689644x832x0", "691162x595x0" ],
    "probability" : 0.5006147390405348
  }, {
    "amountSat" : "2200000",
    "channelIds" : [ "726473x703x1", "727904x1129x0", "696023x1445x0", "703341x959x1", "703310x168x0" ],
    "probability" : 0.6664443121338184
  }, {
    "amountSat" : "1710000",
    "channelIds" : [ "726473x703x1", "727904x1129x0", "696023x1445x0", "717839x1372x2", "673116x1599x3" ],
    "probability" : 0.6797308387358896
  }, {
    "amountSat" : "3200000",
    "channelIds" : [ "726473x703x1", "727924x2119x1", "727724x1365x0", "711388x1010x1", "695339x624x1" ],
    "probability" : 0.5872281922328147
  }, {
    "amountSat" : "3350000",
    "channelIds" : [ "726473x703x1", "727904x1129x0", "725718x1671x0", "681034x1665x1", "723869x1660x0", "723869x1660x1" ],
    "probability" : 0.5780281931840187
  }, {
    "amountSat" : "3350000",
    "channelIds" : [ "726473x703x1", "727904x1129x0", "725718x1671x0", "693136x794x1", "701684x1234x1", "695339x624x1" ],
    "probability" : 0.5944870013390141
  }, {
    "amountSat" : "10090000",
    "channelIds" : [ "726473x703x1", "727904x1129x0", "725718x1671x0", "726475x755x1", "700845x2390x1", "550923x1215x0" ],
    "probability" : 0.31021424023863053
  }, {
    "amountSat" : "1000000",
    "channelIds" : [ "726473x703x1", "727904x1129x0", "727359x1244x0", "701970x2117x1", "701584x2093x1", "694267x2038x2" ],
    "probability" : 0.776652821615024
  }, {
    "amountSat" : "2710000",
    "channelIds" : [ "726473x703x1", "727904x1129x0", "725718x1671x0", "681034x1665x1", "706688x1385x0", "723785x2343x1", "723869x1660x1" ],
    "probability" : 0.5892691058206754
  }, {
    "amountSat" : "140000",
    "channelIds" : [ "726473x703x1", "727904x1129x0", "725718x1671x0", "689644x832x0", "691162x595x0" ],
    "probability" : 0.9827758955245893
  } ]
}

lightningnetwork / lnd

Splitting strategies of payment amount in multi path payments #4203