Re: [Lightning-dev] Code for sub second runtime of piecewise linarization to quickly approximate the minimum convex cost flow problem (makes fast multi part payments with large amounts possible)
Hello Stefan, hello Lightning Devs, > As to Martin's approximation research, I have asked myself similar > > questions. Unfortunately, the paper you cite is paywalled and not > > available at sci-hub, so I haven't read it. Sorry for the paywalled link, without paywall you can read the article on Google Books preview: https://books.google.de/books?id=hbXsCgAAQBAJ=PA63=gbs_toc_r#v=onepage I like your neat and simple proof idea for approximation preservation! Cheers, Martin ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Code for sub second runtime of piecewise linarization to quickly approximate the minimum convex cost flow problem (makes fast multi part payments with large amounts possible)
Good morning everyone, with regards to zerobasefee, I think that the argument that HTLCs are costly doesn't quite hold up because they are always free to an attacker as it stands. However, I fully agree with Zmn's opinion that it's not necessary to bang our head against any opposition to this because we can simply follow his excellent method for overweighing base fee. I believe this is a very natural approach to let the market decide on the relative importance of optimized routing vs base fees. As to Martin's approximation research, I have asked myself similar questions. Unfortunately, the paper you cite is paywalled and not available at sci-hub, so I haven't read it. FWIW, I believe I have a simple proof that minimum cost flow preserves approximation FACTORS: Let O be the original problem and A the approximated problem such that every flow in O can be mapped 1:1 to a flow in A and vice versa. Let every edge e in O be represented by a set of edges in A whose total cost is within a factor (1+epsilon) for every possible flow (could be over- or underestimating). Note that this means that every flow in O has cost within a factor (1+epsilon) for the corresponding flow in A and vice versa. Now let f_a be the min cost flow in A and f_o the min cost flow in O. Assume that c(f_o)(1+epsilon): > > Dear Carsten, Rene and fellow lightning developers, > > Regarding the approximation quality of the minimum convex cost flow > formulation for multi-part payments on the lightning network [1] and > Carsten's discussion points on Twitter [2] and on the mailing list: > > > 8) Quality of Approximation > > > > There are some problems in computer science that are hard/impossible to > > approximate, in the sense that any kind of deviation from the optimum > > could cause the computed results to be extremely bad. Do you have some > > idea (or proof) that your kind of approximation isn't causing a major > > issue? I guess a piece-wise linearization with an infinite number of > > pieces corresponds to the optimal result. Given a finite number of > > pieces, how large is the difference to the optimum? > > I did some literature research and came across an insightful paper [3] by > Dorit Hochbaum from 1993, that proves proximity results for integer and > continuous optimal solutions of the minimum convex cost flow as well as > proximity results of the optimal solutions for a piecewise linear > approximation and the original problem. > > Admittedly theoretical results, however, it further underpins that a > piecewise linear approximation is a reasonable approach to find optimal flows > and even shows that searching for optimal solutions on the continuous domain > (e.g. with descent methods from convex optimization) also gives near-optimal > solutions on the integer domain. > > Cheers, > Martin > > [1] https://arxiv.org/abs/2107.05322 > [2] https://twitter.com/renepickhardt/status/1502293438498234371 > [3] https://www.worldscientific.com/doi/abs/10.1142/9789812798190_0005 > ___ > Lightning-dev mailing list > Lightning-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Code for sub second runtime of piecewise linarization to quickly approximate the minimum convex cost flow problem (makes fast multi part payments with large amounts possible)
Dear Carsten, Rene and fellow lightning developers, Regarding the approximation quality of the minimum convex cost flow formulation for multi-part payments on the lightning network [1] and Carsten's discussion points on Twitter [2] and on the mailing list: > 8) Quality of Approximation > > There are some problems in computer science that are hard/impossible to > approximate, in the sense that any kind of deviation from the optimum > could cause the computed results to be extremely bad. Do you have some > idea (or proof) that your kind of approximation isn't causing a major > issue? I guess a piece-wise linearization with an infinite number of > pieces corresponds to the optimal result. Given a finite number of > pieces, how large is the difference to the optimum? I did some literature research and came across an insightful paper [3] by Dorit Hochbaum from 1993, that proves proximity results for integer and continuous optimal solutions of the minimum convex cost flow as well as proximity results of the optimal solutions for a piecewise linear approximation and the original problem. Admittedly theoretical results, however, it further underpins that a piecewise linear approximation is a reasonable approach to find optimal flows and even shows that searching for optimal solutions on the continuous domain (e.g. with descent methods from convex optimization) also gives near-optimal solutions on the integer domain. Cheers, Martin [1] https://arxiv.org/abs/2107.05322 [2] https://twitter.com/renepickhardt/status/1502293438498234371 [3] https://www.worldscientific.com/doi/abs/10.1142/9789812798190_0005___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Code for sub second runtime of piecewise linarization to quickly approximate the minimum convex cost flow problem (makes fast multi part payments with large amounts possible)
Good morning Rene, sorry for the lateness, > Last but not least, please allow me to make a short remark on the (still to > me very surprisingly controversial) base fee discussion: For simplicity I did > not include any fee considerations to the published code (besides a fee > report on how expensive the computed flow is). However in practice we wish to > optimize at least for high reliability (via neg log success probabilities) > and cheap fees which in particular with the ppm is very easily possible to be > included to the piece wise linearized cost function. While for small base > fees it seems possible to encode the base fee into the first segment of the > piecewise linearized approximation I think the base fee will still be tricky > to be handled in practice (even with this approximation). For example if the > base fee is too high the "base fee adjusted" unit cost of the first segment > of the piecewise linearized problem might be higher than the unit cost of the > second segment which effectively would break the convexity. Thus I reiterate > my e arlier point that from the perspective of the year long pursued goal of optimizing for fees (which all Dijkstra based single path implementations do) it seems to be best if the non linearity that is introduced by the base fee would be removed at all. According to discussions with people who crate Lightning Network explorer (and according to my last check of gossip) about 90% of channels have a base fee of 1 sat or lower and ~38% of all channels already set their base fee away from the default value to 0 [16]. I think the issue against 0-base-fee is that, to a forwarding node operator, every HTLC in-flight is a potential cost center (there is always some probability that the channel has to be forced onchain with the HTLC in-flight, and every HTLC has to be published on the commitment tx), and that cost is *not* proportional to the value of the HTLC (because onchain fees do not work that way). Thus, it seems reasonable for a forwarding node to decide to pass on that cost to their customers, the payers, in the form of base fees. The response of customers would be to boycott non-0-base fees, by e.g. using a heuristic that overweighs non-0-base-fee and reducing usage of such channels (but if every forwarding node *has* a base fee, going through them anyway, which is why you just overweigh them, not eliminate them from the graph outright). Then forwarding nodes will economically move towards 0-base fee. So I think you would find it impossible to remove the base fee field, but you can strongly encourage 0-base-fee usage by integrating the base fee but overweighted. (I think my previous formulation --- treat the base fee as a proportional fee --- would do some overweighing of the base fee.) Which reminds me, I have not gotten around to make a 0-base-fee flag for `clboss`, haha. And I might need to figure out a learning algorithm that splits base and proportional fees as well, *sigh*. Regards, ZmnSCPxj ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Code for sub second runtime of piecewise linarization to quickly approximate the minimum convex cost flow problem (makes fast multi part payments with large amounts possible)
Dear Carsten and fellow lightning developers, thanks for going into such detail and discovering some of the minor inaccuracies of my very rough piecewise linearization! On Mon, Mar 14, 2022 at 1:53 PM Carsten Otto wrote: > 1.2) The Mission Control information provided by lnd [...] > > I think you talk a about a maximum available balance of a channel (and > not > > min available balance)? > > Yes, although MC also has information about "known" amounts (due to > failures that only happened further down the road). > I am unsure how mission control stores and handles that data. In my understanding they are mainly interested in a statistic of the ratio of successfull payments over the past X attempts on a channel given a certain time interval. But I assume they should have all the relevant data to produce a proper conditional proability to utilize our learnt knowledge. In any case from the probabilistic model we can do it mathematically precise by just looking at the conditional probabilities. As said I have written hands on instructions in the rust repo https://github.com/lightningdevkit/rust-lightning/issues/1170#issuecomment-972396747 and they have been fully implemented in https://github.com/lightningdevkit/rust-lightning/pull/1227. Also in our mainnet test and simulations we have updated the priors according to those rules and this revealed the full power of the approach. To summarize: Basically we need to know the effective uncertainty by only looking at the effective amount that goes above the minimum certain liquidity (that we might know from a prior attempt) and the effective capacity (somebody recently suggested that conditional capacity might be a better wording) > Assuming that routing nodes indeed do so we would have learnt that neither > > channel has an effective capacity of N. So the combined virtual channel > > could be seen as 2N-1. > > You mean 2(N-1) = 2N-2? > Probably though the difference would be neglectable and if I understood you correctly you will just keep parallel channels separate anyway. > > 4) Leftovers after Piecewise Linearization > > I am not sure if I understand your question / issue here. The splitting > > works by selecting N points on the domain of the function and splitting > the > > domain into segments at those points. This should never leave sats over. > > With quantization of 10,000 a channel of size 123,456 ends up as an arc > with a capacity of 12 units. Cutting this into 5 pieces gives us > 5*2 with 2 units not ending up in any of those pieces. Or am I missing > something here, and we should split into 5 pieces of size 2.4 = 12/5? > Your observation is correct! Indeed I think my code rounds down the capacity instead of going to the correct points and using all of the capacity in the segmentation by making some channels 1 unit larger than others which would happen if actually finding points on the domain to build the segments. This could easily be fixed. However as always: Fully saturated channels mean very low probabilities so even in my situation where I may cut off a significant part of the channel I'd say in the extreme case where we would need to saturate even those sats the flow will and should most likely fail as the min cust is probably just lower than the amount we would attempt to send. Probably opening a new channel or doing an on chain transaction will be more useful. Though of course we should build the piecewise linearization correctly by the end of the day without throughing away some capacity. > If the quantization however makes a channel so small that we cannot > > even create 5 (or N) disjoint segments then I guess the likelihood for > > being included into the final result is too small anyway. > > It may not be very likely, but flat-out ignoring 20k sat (in my > contrived example above) or up to 4*quantization sats (which is the case > you described) doesn't feel right. > See above. I agree it is not 100% accurate. but in practice I doubt it would ever become a problem as this will only be an issue when the payment amount is very close to the min cut which would make flows so unlikely to begin with that we would use other ways to conduct the payment anyway. witch kind regards Rene ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Code for sub second runtime of piecewise linarization to quickly approximate the minimum convex cost flow problem (makes fast multi part payments with large amounts possible)
Hi Rene, On Mon, Mar 14, 2022 at 12:56:24PM +0100, René Pickhardt via Lightning-dev wrote: > > 1) What's the reasoning behind combining parallel channels? > I think that should work and especially when including fees to the > cost function and considering how nodes handle routing requests on > parallel channels we might have to do so anyway. I think lnd accepts the minimum fee of all parallel channels, even if a higher fee rate is configured for the channel that is actually used. I'm not too sure about this, though. Having parallel channels with different fee settings seems weird to me, anyway. > 1.1) A payment of size 2 needs to be split into 1+1 to fit through > However I believe in practice one cannot just send a 2 satoshi onion and > expect the routing node to split the amount correctly / accordingly > between the two parallel channels. (I might be wrong here). Exactly. This kind of split could be possible in theory, but at least lnd doesn't do it. I guess there are lots of interesting questions to answer before this becomes reality (channel jamming?). > So in that case > modelling and computing probabilities for parallel channels might be > necessary anyway though the math indicates that splitting liquidity in > parallel channels will get you selected less frequently for routing. Which is OK, as in reality it IS less likely to succeed. > 1.2) The Mission Control information provided by lnd [...] > I think you talk a about a maximum available balance of a channel (and not > min available balance)? Yes, although MC also has information about "known" amounts (due to failures that only happened further down the road). > In the case of parallel channels I am not even sure if such information is > accurate as it is my understanding that the routing node may decide to use > the parallel channel to forward the amount even though the other channel > was specified in the onion. The routing node is free to pick any of the parallel channels, yes. The MC data only reasons about pairs of nodes, though, not individual channels. > Assuming that routing nodes indeed do so we would have learnt that neither > channel has an effective capacity of N. So the combined virtual channel > could be seen as 2N-1. You mean 2(N-1) = 2N-2? > However if routing nodes don't locally split a > forwarding request across both channels we would know that calaculating > with 2N-1 is bad as a request of N could not be fulfilled. Exactly, also for 2N-2. Only N-1 would be a reasonable assumption. Based on your responses I'll treat parallel channels individually, and see how it works out. > > 3) Size of Piecewise Linearization > The main difference here is that a channel of 1 BTC is highly preferable > from a probabilistic payment delivery perspective over a channel of 0.01 > BTC. Even approximating the 1 BTC channel with 1000 intervalls of 0.001 BTC > should still have a lower unit cost in all pieces of the first 0.01 BTC of > the liquidity than the first piece of the 0.01 BTC channel. So I think > splitting all channels in the equal number of pieces is pretty well > motivated but let me elaborate on this: OK great, got it. > > 4) Leftovers after Piecewise Linearization > I am not sure if I understand your question / issue here. The splitting > works by selecting N points on the domain of the function and splitting the > domain into segments at those points. This should never leave sats over. With quantization of 10,000 a channel of size 123,456 ends up as an arc with a capacity of 12 units. Cutting this into 5 pieces gives us 5*2 with 2 units not ending up in any of those pieces. Or am I missing something here, and we should split into 5 pieces of size 2.4 = 12/5? > If the quantization however makes a channel so small that we cannot > even create 5 (or N) disjoint segments then I guess the likelihood for > being included into the final result is too small anyway. It may not be very likely, but flat-out ignoring 20k sat (in my contrived example above) or up to 4*quantization sats (which is the case you described) doesn't feel right. > Again this yield interesting pruning opportunities to reduce the seize of > the network before doing the expensive min cost flow computation. For > example I could prune channels with high unit costs on the first segment. > Especially if they are further away from the source and destination node. > This would overall reduce the size of the graph and improve runtime. Let's talk about optimizations later :) > 5) Fees (and other properties?) > arcs.append((src,dest,int(cap/(N*QUANTIZATION)),(i+1)*unit_cost + > mu*fee_rate_ppm)) Great, that helps! Thanks alot! > Note two things: > 1. the only requirement for the solver to work is that \mu*fee_rate_ppm > needs to be an integer. So in case \mu was smaller than 1 we could also > scale the term from the linearized log probabilities by putting a larger mu > to the feature arising from the cost of the uncertainty. Good to know! Bye,
Re: [Lightning-dev] Code for sub second runtime of piecewise linarization to quickly approximate the minimum convex cost flow problem (makes fast multi part payments with large amounts possible)
Dear Carsten, Martin and fellow lightning developers, first of all thank you very much for independently verifying and acknowledging my recent findings about the runtime of finding a pieceweise linearized approximation to the min cost flow problem, for working on integrating them into lnd-manageJ and for your excellent questions & thoughts. On Sun, Mar 13, 2022 at 8:17 PM Carsten Otto via Lightning-dev < lightning-dev@lists.linuxfoundation.org> wrote: > 1) What's the reasoning behind combining parallel channels? > Generally speaking this is pure pragmatism on my end to simplify my life as handling parallel channels in some cases blows up complexity of code and simulations. However I think from a probabilistic point of view ( see below ) the combination is more accurate to reflect the actual likelihood that the liquidity is available. I agree that parallel channels make things a lot more complicated, but I > also see the benefit from a node operator's point of view. That being > said, wouldn't it suffice to treat parallel channels individually? > I think that should work and especially when including fees to the cost function and considering how nodes handle routing requests on parallel channels we might have to do so anyway. The suggested flows will probably change in a way that disfavors parallel channels even if their virtual capacity is larger than an alternative single channel (see below) 1.1) A payment of size 2 needs to be split into 1+1 to fit through > parallel channels of size 1+1. Combining the 1+1 channels into a virtual > channel of size 2 only complicates the code that has to do come up with > a MPP that doesn't over-saturate the actual channels. On the other hand, > I don't think the probability for the virtual channel of size 2 is more > realistic than reasoning about two individual channels and their > probabilities - but I didn't even try to see the math behind that. > Please prove me wrong? :) > * The likelihood that a 1 Satoshi capacity channel has 1 Satoshi to route is 1/2. * The likelihood that 2 channels of capacity 1 have each 1 satoshi available to route is 1/2*1/2 = 1/4 * Combining both parallel channels to one virtual channel of capacity 2 and asking if 2 satoshis are available to route gives a likelihood of 1/3 which is larger than 1/4. However I believe in practice one cannot just send a 2 satoshi onion and expect the routing node to split the amount correctly / accordingly between the two parallel channels. (I might be wrong here). So in that case modelling and computing probabilities for parallel channels might be necessary anyway though the math indicates that splitting liquidity in parallel channels will get you selected less frequently for routing. 1.2) The Mission Control information provided by lnd can be used to > place a minimum available balance on each of the parallel channels. If > we know that node A isn't able to forward N sats to node B, we can treat > all parallel channels between A and B (in that direction) to have a > capacity of at most N-1 sats. How would this look like if we combined > the parallel channels into a virtual one? Note that it may still be > possible to route two individual payments/onions of size N-1 sats from A > to B, given two parallel channels with that many sats on A's side. > I think you talk a about a maximum available balance of a channel (and not min available balance)? In the case of parallel channels I am not even sure if such information is accurate as it is my understanding that the routing node may decide to use the parallel channel to forward the amount even though the other channel was specified in the onion. Assuming that routing nodes indeed do so we would have learnt that neither channel has an effective capacity of N. So the combined virtual channel could be seen as 2N-1. However if routing nodes don't locally split a forwarding request across both channels we would know that calaculating with 2N-1 is bad as a request of N could not be fulfilled. I guess it is for the implementations that support parallel channels to figure out the details here. 2) Optimal Piecewise Linearization > > See Twitter [3]. > > Is it worth it cutting a channel into pieces of different sizes, instead > of just having (as per your example) 5 pieces of the same size? If it > makes a noticeable difference, adding some complexity to the code might > be worth it. > I will certainly do experiments or be happy if others are faster to do them which compare the quality of the approximation with optimal piecewise linearization to my choice of fixed intervals and the selection of various numbers of segments. As long as we don't have numbers it is hard to guess if it is worthwhile adding the complexity. Looking at the current results it seems that my (geometricly motivated but) arbitrary choice might end up to be good and easy enough. However we might very well see quite an improvement of the approximation if we find better piecewise
[Lightning-dev] Code for sub second runtime of piecewise linarization to quickly approximate the minimum convex cost flow problem (makes fast multi part payments with large amounts possible)
Dear Lightning Developer, Rene & Carsten, The min-cost flow formulation for MPP of Rene and Stefan [1] intrigued me and brought me to think about how this optimization problem can be solved efficiently in order to contribute to practically relevant reliable payments on the Lightning network. Applying linear approximation to the convex non-linear cost function C(f) brings runtime improvements [2], however an approximation can deteriorate the solution quality. This brought me to think about the approximation quality/error of a piecewise linear approximation for the cost function C(f) and how that translate to the original success probability of a flow P(f). After some back and forth with Rene over the last couple of days, I summarized some preliminary insights in the following: [3] https://raw.githubusercontent.com/drmartinberger/mpp-approx-pf/main/approxPf.pdf The main (admittedly, mostly theoretical) outcome is, that a piecewise linear approximation of C(f) with given approximation error, also gives an approximation of the function P(f) with lower/upper bound. However, [3] further underpins the "goodness" of the approach [1] and might address some of Carsten's concerns [4] and of the previous post of Carsten (especially 8) ). Feedback of any kind is warmly welcome and feel free to reach out in case of questions. Thank you! Cheers, Martin [1] https://arxiv.org/abs/2107.05322 [2] https://github.com/renepickhardt/mpp-splitter/blob/master/Minimal%20Linearized%20min%20cost%20flow%20example%20for%20MPP.ipynb [3] https://raw.githubusercontent.com/drmartinberger/mpp-approx-pf/main/approxPf.pdf [4] https://twitter.com/c_otto83/status/1502329970349248521 ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Code for sub second runtime of piecewise linarization to quickly approximate the minimum convex cost flow problem (makes fast multi part payments with large amounts possible)
Hi Rene, thanks a lot for your contribution! This is exactly what I needed to start coding again :) I intend to release a somewhat usable version of your approach in lnd-manageJ [1] soon. Preliminary results indicate that results (i.e. MPPs to try) can be computed in less than a second, which is great! Important remark: my code can only be used for real MPPs once a usable MPP gRPC call is made available, see lnd issue #5746 [2]. While working on my implementation, a few questions came to mind: 1) What's the reasoning behind combining parallel channels? I agree that parallel channels make things a lot more complicated, but I also see the benefit from a node operator's point of view. That being said, wouldn't it suffice to treat parallel channels individually? 1.1) A payment of size 2 needs to be split into 1+1 to fit through parallel channels of size 1+1. Combining the 1+1 channels into a virtual channel of size 2 only complicates the code that has to do come up with a MPP that doesn't over-saturate the actual channels. On the other hand, I don't think the probability for the virtual channel of size 2 is more realistic than reasoning about two individual channels and their probabilities - but I didn't even try to see the math behind that. Please prove me wrong? :) 1.2) The Mission Control information provided by lnd can be used to place a minimum available balance on each of the parallel channels. If we know that node A isn't able to forward N sats to node B, we can treat all parallel channels between A and B (in that direction) to have a capacity of at most N-1 sats. How would this look like if we combined the parallel channels into a virtual one? Note that it may still be possible to route two individual payments/onions of size N-1 sats from A to B, given two parallel channels with that many sats on A's side. 2) Optimal Piecewise Linearization See Twitter [3]. Is it worth it cutting a channel into pieces of different sizes, instead of just having (as per your example) 5 pieces of the same size? If it makes a noticeable difference, adding some complexity to the code might be worth it. 3) Size of Piecewise Linearization My gut feeling is that cutting a 1 BTC channel into 5 pieces is different from cutting a 0.01 BTC channel into 5 pieces. Would it make sense to use different values of N depending on the channel size? 4) Leftovers after Piecewise Linearization If I cut some channel into N pieces, I might end up with up to N-1 sats that don't end up in any of the N pieces, effectively making the channel look smaller than it is. For smaller values of N that's obviously not an issue (given the uncertainty we're dealing with), but it might be more problematic if quantization is used with larger values. Any thoughts on this? 5) Fees (and other properties?) How can we integrate fees into the function? I must admit, I haven't even thought about that, yet. A copy-paste answer would be great, though! :) Maybe it's also a good idea to punish channels based on their CLTV delta? Ratio of enabled channels? Age? Manual punishment score? ... 6) Non-Zero Base Fee See Twitter [4]. According to Stefan [5] it should be possible to integrate ZmnSCPxj's ideas to make this work with non-zero base fees. How? Simpler approach: Twitter [6]. 7) Private Channels [very niche topic, not really that interesting nor urgent] I'm a fan of adding private channels to provide more outbound liquidity, mainly to reduce gossip and hide my intentions. If my total liquidity to some peer is below the amount announced in public channels, I don't see any meaningful complication. However, I might have a public channel of size N and several private channels bringing my local liquidity to some value >N. It's rather obvious that not announcing this fact is a bad idea, as any #pickhardtpayments implementation would think I have 0-N on my side of the channel(s). Assuming I'm willing to accept this tradeoff, do you see other complications or issues with hidden liquidity? My gut feeling is that this isn't an issue, at all, as channel balances change all the time, which is something the algorithm already has to deal with. 8) Quality of Approximation There are some problems in computer science that are hard/impossible to approximate, in the sense that any kind of deviation from the optimum could cause the computed results to be extremely bad. Do you have some idea (or proof) that your kind of approximation isn't causing a major issue? I guess a piece-wise linearization with an infinite number of pieces corresponds to the optimal result. Given a finite number of pieces, how large is the difference to the optimum? Bye, Carsten 1: https://github.com/C-Otto/lnd-manageJ/issues/6 2: https://github.com/lightningnetwork/lnd/issues/5746 3: https://twitter.com/c_otto83/status/1502329970349248521 4: https://twitter.com/c_otto83/status/1502329271964033027 5: https://twitter.com/stefanwouldgo/status/1502681455918473217 6:
[Lightning-dev] Code for sub second runtime of piecewise linarization to quickly approximate the minimum convex cost flow problem (makes fast multi part payments with large amounts possible)
Dear fellow Lightning Developers, I am pleased (and a bit proud) to be able to inform you that I finally found a quick way to approximate the slow minimum convex cost flow computation. This is necessary for optimally reliable and cheap payment flows [0] to deliver large multi part payments over the Lightning Network. The proposed solution happens via piecewise linearization [1] of the min cost flow problem on the uncertainty network which we face in order to compute the optimal split and planning of large amount multi part payments. The notion of "optimal" is obviously subjective with respect to the chosen cost function. As known we suggest to include the negative logarithm of success probabilities based on the likelihood that enough liquidity is available on a channel as a dominant feature of the used cost function. We give the background for this in [2] which since then has already been picked up by c-lightning and LDK. The c-lightning team even published benchmarks showing significant improvement in payment speed over their previously used cost function [2b]. Let me recall that one of the largest criticisms and concerns of our approach to use minimum cost flows for payment delivery back in July / August last year (especially by the folks from lightning labs) was that the min cost flow approach would be impractical due to run time constrains. Thus I am delighted that with the now published code [3] (which has exactly 100 lines including data import and parsing and ignoring comments) we are able to compute a reasonable looking approximation to the optimal solution in a sub second run time on the complete public channel graph of the Lightning Network. This is achieved via piecewise linearization of the convex cost function and invoking of a standard linear min cost flow solver [4] for the linearized problem. This works quickly despite the fact that the piecewise linearization adds a significant higher amount of arcs to the network and blows up the size of the network on which we solve the min cost flow problem. This makes me fairly certain that with proper pruning of the graph we might even reach the 100 millisecond runtime frontier, which would be far faster than what I dreamed & hoped to be possible. The currently widely deployed Dijkstra search to generate a single candidate path takes roughly 100ms of runtime. It seems that with the runtime of the piecewise linearized problem the min cost flow approach is now competitive from a runtime perspective. The flow computation is still a bit slower than Dijkstra in both theory and practice. However the piecewise linearized min cost flow has the huge advantage that it generates several candidate paths for a solid approximation of the optimal MPP split. Remember the exact min cost flow corresponds to the optimal MPP split. The later was not used so far as the min cost flow was considered to be too slow. Yet the question how to split seems to be addressed as issues in implementations [5][6][7] and acknowledged to be complicated (especially with respect to fees) in [8]. This result is btw of particular interest for LSPs. If an LSP has to schedule x payments per second it can just do one flow computation with several sink nodes and plan all of those payments with a single min cost flow computation. This globally optimizes the potentially heavy load that LSPs might have even if all payments were so small that no splitting was necessary. The iPython notebook which I shared contains about 1 page to explain how to conduct a piecewise linear approximation. The quality of the approximation is not the major goal here as I am just focused to demonstrate the run time of the approach and the principle how to achieve this runtime. Thus I do the piecewise linear approximation very roughly in the published code. Selecting the optimal piecewise approximation [9] will not change the the runtime of flow computation but only blows up the code to prepare the solver. This is why I decided to keep the code as simple and short as possible even if that means that the approximation will be not as close to the optimum as it could be in practice. For the same reason I did not include any code to update the uncertainty network from previously failed or successful attempts by using conditional success probabilities P(X>a | min_liquidity < X < max_liquidity ). People who are interested might look at my hands on instructions and explanations for coders in this rust-lightning issue [10]. The folks from LDK have picked this up and implemented this already for single path payments in [11] which might be relevant for people who prefer code over math papers. An obvious optimization of the piece wise linearization would be to chose the first segment of the piecewise linear approximation with a capacity of the certain liquidity and a unit cost of 0 for that piece. Our original papers describe everything only from a theoretical point of view and with simulations. However our mainnet experiments
