rich1.0npub1zlxd3xlzjhq2ue03e5m5p2w6mp8v3dkhq5r39flsftjjsje04wvsdd2k4whttps://nostr.ae/npub1zlxd3xlzjhq2ue03e5m5p2w6mp8v3dkhq5r39flsftjjsje04wvsdd2k4wnjumphttps://nostr.ae📅 Original date posted:2022-03-14 📝 Original message: 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 at 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 linearizations. > 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? > 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: The motivation of splitting all channels into the same number of pieces comes from the observation that from a probabilistic point of view (and very roughly speaking!) we want to find a flow that puts the same (high) success probability on all edges. Using 20% of the capacity gives an 80% probability that the liquidity is available. This in turn has a 51.2% chance to be successful on a three hop path which in my experience is a good probability to aim for as on average one is expected to need two attempts. Since the linearized pieces - if included in the flow - tend to be fully saturated I decided that it makes sense to put them in 5 buckets of 20% each. If you read the code carefully I don't even approximate the cost correctly at the 2nd, 3rd, 4th and 5th piece. I just multiplied the linearized unit cost of the first piece with 2,3,4 and 5 respectively Which approximates the negative log probability with a quadratic cost function. But as we can see those geometrically motivated choices work already pretty well. Again I plan to invest more time to find a better approximation and we might end up using it. But I don't expect too much gain from doing so. If you look at the output of the flow in the iPython notebook (Which I will copy to the end of the mail for your convenience) you see that most channels did not fully saturate the first piece and have a likelihood between 80% and 100% where as some channels saturated the first piece producing a likelihood of 80% and few channels saturated also the second piece giving a likelihood of 60%. Thus I expect that the real value from studying the optimal piece wise linear approximation will give us a better understanding of where to prune segments away. If we note that in this flow not a single channel used the third, forth and fifth piece we could have removed 60% of all edges and doubled the runtime and still compute the same resulting flow. > 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? > 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. The quantization which doesn't boost the runtime too much anyway happens before piecewise linearization. So as long as the domain is larger than N the piecewiese linearization should not bring up a situation where sats are left over. 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. But I agree that an actual implementation might have to watch out for such edge cases. 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. Already last July I had a pretty well working heurist that was able to through away about 90% of all channels and would pretty much always find the same flow in the pruned network as on the full network. I should really prioritize the pruning work again now that we have fast solvers. 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? ... > plugging in fees (assuming only channels that set a base fee of zero) is very easy and straight forward. Let's recall from the code that the piecewise linearized unit cost is computed as follows unit_cost = int(max_cap/cap)for i in range(N): #arc format is src, dest, capacity, unit_cost arcs.append((src,dest,int(cap/(N*QUANTIZATION)),(i+1)*unit_cost)) As described in our paper for a good (and to be determined) value of \mu we could just create the linear combination between the two features which would change the line to: arcs.append((src,dest,int(cap/(N*QUANTIZATION)),(i+1)*unit_cost + mu*fee_rate_ppm)) 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. arcs.append((src,dest,int(cap/(N*QUANTIZATION)),mu*(i+1)*unit_cost + fee_rate_ppm)) 2. the cost from the routing fees is the same on each segment of the piecewise linearization which makes a lot of sense because the current feerate is indeed a unit cost that does not change with how heavily you plan to use a channel independently how the cost that comes from the probability grows. With respect to other features I guess the entire topic of feature engineering for our cost function should be a separate threat / topic and line of research but as you asked I will give you some short thoughts on this here: As pointed out to the c-lightning team in https://github.com/ElementsProject/lightning/pull/4771#issuecomment-930173831 and the following comment I believe that optimizing for CLTV is a poor choice and in min cost flow computations it might very well be non linear anyway and thus tricky to include in a meaningful way.Sure one could transform it to a unit cost by doing something like CLTV*max_cap/cap and add it to the cost function like the ppm. But I still do not really see why this is useful. On the other hand I very much believe we should start to investigate features that predict channel latency to setup / settle an HTLC as suggested in the last paragraph of this comment https://github.com/lightningdevkit/rust-lightning/issues/1170#issuecomment-972396747 However I fear that latency measures again are non linear though they could again be translated to a unit cost with the same trick as the CLTV. > 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]. > I don't have much to add to the base fee discussion at this point besides the emphasize that the above described linearization trick for CLTV or latency based features will not properly work for the base fee because one actually has to pay the full base fee at the end - independently of how much you saturate the channel. This might mess up the optimization. > 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. > As you noted from a probabilistic payment delivery point of view I might be interested in signaling all the liquidity that is being provided between two peers and I shoot myself if I hide it. That being said you might have reasons to do so and additionally I never rejected the idea to extend the current probabilistic model with a probabilistic node or channel provenance value that would be similar to the ideas in lnd's mission control or the routescore by https://lnrouter.app. Given the fact that with hidden liquidity the probabilities are constantly underestimated such a provenance score will probably be higher than the one of other channels fixing the "introduced issue" of hidden liquidity 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? > We don't have to go to infinite to find a solution without error. We can stay with the finite number that corresponds to the channels capacity and make segments of 1 satoshi each encoding what this satoshi would actually cost in the original function (assuming all values in the original function were integers). I have not spent the time to properly express the error in dependence of the number of segments N or even empirically study its tradeoffs in practice (as I haven't even included the optimal piecewise linearization yet) However the actual flow (see below) as well as the results from Dr. Martin Berger https://lists.linuxfoundation.org/pipermail/lightning-dev/2022-March/003513.html indicate that the error should be possible to be managed and stay small enough in practice. That being said and as above it certainly makes sense to invest a bit of time on how to conduct the piecewise linearization properly. Output of the computed flow from the iPython notebok with a piece wise linearization of 5 equal sized segments per channel Planning to deliver 0.50 BTC from 5051(03efccf...) to 13006 (021c97a...) via an approximated optimally reliable payment flow... Runtime of flow computation: 0.85 sec Minimum approximated quadratic cost: 815932 Arc Flow / Capacity probability Fee (sats) 5051 -> 8463 6700000 / 16777215 0.600649 8957.900000 5051 -> 3437 1800000 / 9000000 0.800000 2406.600000 5051 -> 9162 1240000 / 6200000 0.800000 1657.880000 5051 -> 14746 6700000 / 16777215 0.600649 8957.900000 5051 -> 14832 2000000 / 10000000 0.800000 2674.000000 6257 -> 14832 3350000 / 2411344242 0.998611 335.100000 14832 -> 12446 5350000 / 6200000000 0.999137 6.350000 7870 -> 6257 3350000 / 20000000 0.832500 34.500000 14746 -> 12446 6700000 / 100000000 0.933000 3350.000000 7914 -> 13006 6700000 / 200000000 0.966500 33501.000000 5051 -> 550 3300000 / 15000000 0.780000 4412.100000 11396 -> 13192 6700000 / 1000000000 0.993300 2010.000000 5051 -> 11396 6700000 / 16777215 0.600649 8957.900000 7199 -> 9162 3350000 / 445000000 0.992472 848.550000 9162 -> 12446 16590000 / 3900000000 0.995746 17.590000 5051 -> 13287 2000000 / 10000000 0.800000 2674.000000 5051 -> 1843 6700000 / 16777215 0.600649 8957.900000 5051 -> 11257 3350000 / 16777215 0.800324 4478.950000 1953 -> 12446 2160000 / 750000000 0.997120 1080.000000 550 -> 1843 3300000 / 30000000 0.890000 1155.000000 12756 -> 12446 2000000 / 16775679 0.880780 301.000000 5051 -> 12756 2000000 / 10000000 0.800000 2674.000000 3437 -> 12446 1800000 / 400000000 0.995500 225.001000 6713 -> 7914 6700000 / 200000000 0.966500 837.501000 11257 -> 7199 3350000 / 16777215 0.800324 663.300000 10914 -> 9162 2000000 / 500000000 0.996000 1000.001000 5051 -> 7870 3350000 / 16777215 0.800324 3.781000 8463 -> 5288 6700000 / 500000000 0.986600 837.501000 2781 -> 10914 2000000 / 500000000 0.996000 401.000000 13192 -> 6713 6700000 / 500000000 0.986600 16750.000000 32 -> 2781 2000000 / 210000000 0.990476 200.000000 5051 -> 9530 2160000 / 10811137 0.800206 2.591000 9530 -> 1953 2160000 / 16777215 0.871254 438.336000 1843 -> 9162 10000000 / 300000000 0.966667 2500.000000 5051 -> 14642 2000000 / 10000000 0.800000 2.431000 14642 -> 13006 2000000 / 50000000 0.960000 6001.000000 13287 -> 32 2000000 / 16777215 0.880791 500.000000 12446 -> 13006 34600000 / 200000000 0.827000 103766.400000 5288 -> 13006 6700000 / 100000000 0.933000 15216.700000 Probability of entire flow: 0.0032 Total fee: 248793.763 sats Effective fee rate: 0.498 % Arcs included in payment flow: 39 Don't get confused by a low probability. The first attampt always has high uncertainty. We will learn fast in each consequitive round. With kind regards Rene Pickhardt -- > Dr. Carsten Otto > carsten at c-otto.de > https://c-otto.de > _______________________________________________ > Lightning-dev mailing list > Lightning-dev at lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > -- https://www.rene-pickhardt.de -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20220314/77da14bd/attachment-0001.html>