{"type":"rich","version":"1.0","author_name":"npub1zlxd3xlzjhq2ue03e5m5p2w6mp8v3dkhq5r39flsftjjsje04wvsdd2k4w","author_url":"https://nostr.ae/npub1zlxd3xlzjhq2ue03e5m5p2w6mp8v3dkhq5r39flsftjjsje04wvsdd2k4w","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2022-03-14\n📝 Original message:\nDear Carsten, Martin and fellow lightning developers,\n\nfirst of all thank you very much for independently verifying and\nacknowledging my recent findings about the runtime of finding a pieceweise\nlinearized approximation to the min cost flow problem, for working on\nintegrating them into lnd-manageJ and for your excellent questions \u0026\nthoughts.\n\nOn Sun, Mar 13, 2022 at 8:17 PM Carsten Otto via Lightning-dev \u003c\nlightning-dev at lists.linuxfoundation.org\u003e wrote:\n\n\n\u003e 1) What's the reasoning behind combining parallel channels?\n\u003e\n\nGenerally speaking this is pure pragmatism on my end to simplify my life as\nhandling parallel channels in some cases blows up complexity of code and\nsimulations. However I think from a probabilistic point of view ( see below\n) the combination is more accurate to reflect the actual likelihood that\nthe liquidity is available.\n\nI agree that parallel channels make things a lot more complicated, but I\n\u003e also see the benefit from a node operator's point of view. That being\n\u003e said, wouldn't it suffice to treat parallel channels individually?\n\u003e\n\nI think that should work and especially when including fees to the cost\nfunction and considering how nodes handle routing requests on parallel\nchannels we might have to do so anyway. The suggested flows will probably\nchange in a way that disfavors parallel channels even if their virtual\ncapacity is larger than an alternative single channel (see below)\n\n1.1) A payment of size 2 needs to be split into 1+1 to fit through\n\u003e parallel channels of size 1+1. Combining the 1+1 channels into a virtual\n\u003e channel of size 2 only complicates the code that has to do come up with\n\u003e a MPP that doesn't over-saturate the actual channels. On the other hand,\n\u003e I don't think the probability for the virtual channel of size 2 is more\n\u003e realistic than reasoning about two individual channels and their\n\u003e probabilities - but I didn't even try to see the math behind that.\n\u003e Please prove me wrong? :)\n\u003e\n\n* The likelihood that a 1 Satoshi capacity channel has 1 Satoshi to route\nis 1/2.\n* The likelihood that 2 channels of capacity 1 have each 1 satoshi\navailable to route is 1/2*1/2 = 1/4\n* Combining both parallel channels to one virtual channel of capacity 2 and\nasking if 2 satoshis are available to route gives a likelihood of 1/3 which\nis larger than 1/4.\n\nHowever I believe in practice one cannot just send a 2 satoshi onion and\nexpect the routing node to split the amount  correctly / accordingly\nbetween the two parallel channels. (I might be wrong here). So in that case\nmodelling and computing probabilities for parallel channels might be\nnecessary anyway though the math indicates that splitting liquidity in\nparallel channels will get you selected less frequently for routing.\n\n1.2) The Mission Control information provided by lnd can be used to\n\u003e place a minimum available balance on each of the parallel channels. If\n\u003e we know that node A isn't able to forward N sats to node B, we can treat\n\u003e all parallel channels between A and B (in that direction) to have a\n\u003e capacity of at most N-1 sats. How would this look like if we combined\n\u003e the parallel channels into a virtual one? Note that it may still be\n\u003e possible to route two individual payments/onions of size N-1 sats from A\n\u003e to B, given two parallel channels with that many sats on A's side.\n\u003e\n\nI think you talk a about a maximum available balance of a channel (and not\nmin available balance)?\nIn the case of parallel channels I am not even sure if such information is\naccurate as it is my understanding that the routing node may decide to use\nthe parallel channel to forward the amount even though the other channel\nwas specified in the onion.\nAssuming that routing nodes indeed do so we would have learnt that neither\nchannel has an effective capacity of N. So the combined virtual channel\ncould be seen as 2N-1. However if routing nodes don't locally split a\nforwarding request across both channels we would know that calaculating\nwith 2N-1 is bad as a request of N could not be fulfilled. I guess it is\nfor the implementations that support parallel channels to figure out the\ndetails here.\n\n2) Optimal Piecewise Linearization\n\u003e\n\u003e See Twitter [3].\n\u003e\n\u003e Is it worth it cutting a channel into pieces of different sizes, instead\n\u003e of just having (as per your example) 5 pieces of the same size? If it\n\u003e makes a noticeable difference, adding some complexity to the code might\n\u003e be worth it.\n\u003e\n\nI will certainly do experiments or be happy if others are faster to do them\nwhich compare the quality of the approximation with optimal piecewise\nlinearization to my choice of fixed intervals and the selection of various\nnumbers of segments. As long as we don't have numbers it is hard to guess\nif it is worthwhile adding the complexity. Looking at the current results\nit seems that my (geometricly motivated but) arbitrary choice might end up\nto be good and easy enough. However we might very well see quite an\nimprovement of the approximation if we find better piecewise linearizations.\n\n\n\u003e 3) Size of Piecewise Linearization\n\u003e\n\u003e My gut feeling is that cutting a 1 BTC channel into 5 pieces is\n\u003e different from cutting a 0.01 BTC channel into 5 pieces. Would it make\n\u003e sense to use different values of N depending on the channel size?\n\u003e\n\nThe main difference here is that a channel of 1 BTC is highly preferable\nfrom a probabilistic payment delivery perspective over a channel of 0.01\nBTC. Even approximating the 1 BTC channel with 1000 intervalls of 0.001 BTC\nshould still have a lower unit cost in all pieces of the first 0.01 BTC of\nthe liquidity than the first piece of the 0.01 BTC channel. So I think\nsplitting all channels in the equal number of pieces is pretty well\nmotivated but let me elaborate on this:\n\nThe motivation of splitting all channels into the same number of pieces\ncomes from the observation that from a probabilistic point of view (and\nvery roughly speaking!) we want to find a flow that puts the same (high)\nsuccess probability on all edges. Using 20% of the capacity gives an 80%\nprobability that the liquidity is available. This in turn has a 51.2%\nchance to be successful on a three hop path which in my experience is a\ngood probability to aim for as on average one is expected to need two\nattempts. Since the linearized pieces - if included in the flow - tend to\nbe fully saturated I decided that it makes sense to put them in 5 buckets\nof 20% each. If you read the code carefully I don't even approximate the\ncost correctly at the 2nd, 3rd, 4th and 5th piece. I just multiplied the\nlinearized unit cost of the first piece with 2,3,4 and 5 respectively Which\napproximates the negative log probability with a quadratic cost function.\nBut as we can see those geometrically motivated choices work already pretty\nwell. Again I plan to invest more time to find a better approximation and\nwe might end up using it. But I don't expect too much gain from doing so.\n\n If you look at the output of the flow in the iPython notebook (Which I\nwill copy to the end of the mail for your convenience) you see that most\nchannels did not fully saturate the first piece and have a likelihood\nbetween 80% and 100% where as some channels saturated the first piece\nproducing a likelihood of 80% and few channels saturated also the second\npiece giving a likelihood of 60%.\n\nThus I expect that the real value from studying the optimal piece wise\nlinear approximation will give us a better understanding of where to prune\nsegments away. If we note that in this flow not a single channel used the\nthird, forth and fifth piece we could have removed 60% of all edges and\ndoubled the runtime and still compute the same resulting flow.\n\n\n\u003e 4) Leftovers after Piecewise Linearization\n\u003e\n\u003e If I cut some channel into N pieces, I might end up with up to N-1 sats\n\u003e that don't end up in any of the N pieces, effectively making the channel\n\u003e look smaller than it is. For smaller values of N that's obviously not an\n\u003e issue (given the uncertainty we're dealing with), but it might be more\n\u003e problematic if quantization is used with larger values. Any thoughts on\n\u003e this?\n\u003e\n\nI am not sure if I understand your question / issue here. The splitting\nworks by selecting N points on the domain of the function and splitting the\ndomain into segments at those points. This should never leave sats over.\nThe quantization which doesn't boost the runtime too much anyway happens\nbefore piecewise linearization. So as long as the domain is larger than N\nthe piecewiese linearization should not bring up a situation where sats are\nleft over. If the quantization however makes a channel so small  that we\ncannot even create 5 (or N) disjoint segments then I guess the likelihood\nfor being included into the final result is too small anyway. But I agree\nthat an actual implementation might have to watch out for such edge cases.\n\nAgain this yield interesting pruning opportunities to reduce the seize of\nthe network before doing the expensive min cost flow computation. For\nexample I could prune channels with high unit costs on the first segment.\nEspecially if they are further away from the source and destination node.\nThis would overall reduce the size of the graph and improve runtime.\nAlready last July I had a pretty well working heurist that was able to\nthrough away about 90% of all channels and would pretty much always find\nthe same flow in the pruned network as on the full network. I should really\nprioritize the pruning work again now that we have fast solvers.\n\n5) Fees (and other properties?)\n\u003e\n\u003e How can we integrate fees into the function? I must admit, I haven't\n\u003e even thought about that, yet. A copy-paste answer would be great,\n\u003e though! :) Maybe it's also a good idea to punish channels based on their\n\u003e CLTV delta? Ratio of enabled channels? Age? Manual punishment score? ...\n\u003e\n\nplugging in fees (assuming only channels that set a base fee of zero) is\nvery easy and straight forward.\n\nLet's recall from the code that the piecewise linearized unit cost is\ncomputed as follows\n\nunit_cost = int(max_cap/cap)for i in range(N):\n     #arc format is src, dest, capacity, unit_cost\n     arcs.append((src,dest,int(cap/(N*QUANTIZATION)),(i+1)*unit_cost))\n\nAs described in our paper for a good (and to be determined) value of \\mu we\ncould just create the linear combination between the two features which\nwould change the line to:\n\n     arcs.append((src,dest,int(cap/(N*QUANTIZATION)),(i+1)*unit_cost +\nmu*fee_rate_ppm))\n\nNote two things:\n1. the only requirement for the solver to work is that \\mu*fee_rate_ppm\nneeds to be an integer. So in case \\mu was smaller than 1 we could also\nscale the term from the linearized log probabilities by putting a larger mu\nto the feature arising from the cost of the uncertainty.\n\n     arcs.append((src,dest,int(cap/(N*QUANTIZATION)),mu*(i+1)*unit_cost\n+ fee_rate_ppm))\n\n\n2. the cost from the routing fees is the same on each segment of the\npiecewise linearization which makes a lot of sense because the current\nfeerate is indeed a unit cost that does not change with how heavily you\nplan to use a channel independently how the cost that comes from the\nprobability grows.\n\nWith respect to other features I guess the entire topic of feature\nengineering for our cost function should be a separate threat / topic and\nline of research but as you asked I will give you some short thoughts on\nthis here:\n\nAs pointed out to the c-lightning team in\nhttps://github.com/ElementsProject/lightning/pull/4771#issuecomment-930173831\nand\nthe following comment I believe that optimizing for CLTV is a poor choice\nand in min cost flow computations it might very well be non linear anyway\nand thus tricky to include in a meaningful way.Sure one could transform it\nto a unit cost by doing something like CLTV*max_cap/cap and add it to the\ncost function like the ppm. But I still do not really see why this is\nuseful. On the other hand I very much believe we should start to\ninvestigate features that predict channel latency to setup / settle an HTLC\nas suggested in the last paragraph of this comment\nhttps://github.com/lightningdevkit/rust-lightning/issues/1170#issuecomment-972396747\nHowever\nI fear that latency measures again are non linear though they could again\nbe translated to a unit cost with the same trick as the CLTV.\n\n\n\u003e 6) Non-Zero Base Fee\n\u003e\n\u003e See Twitter [4].\n\u003e\n\u003e According to Stefan [5] it should be possible to integrate ZmnSCPxj's ideas\n\u003e to make this work with non-zero base fees. How?\n\u003e Simpler approach: Twitter [6].\n\u003e\n\nI don't have much to add to the base fee discussion at this point besides\nthe emphasize that the above described linearization trick for CLTV or\nlatency based features will not properly work for the base fee because one\nactually has to pay the full base fee at the end - independently of how\nmuch you saturate the channel. This might mess up the optimization.\n\n\n\u003e 7) Private Channels\n\u003e\n\u003e [very niche topic, not really that interesting nor urgent]\n\u003e\n\u003e I'm a fan of adding private channels to provide more outbound liquidity,\n\u003e mainly to reduce gossip and hide my intentions. If my total liquidity to\n\u003e some peer is below the amount announced in public channels, I don't see\n\u003e any meaningful complication. However, I might have a public channel of\n\u003e size N and several private channels bringing my local liquidity to some\n\u003e value \u003eN. It's rather obvious that not announcing this fact is a bad\n\u003e idea, as any #pickhardtpayments implementation would think I have 0-N on\n\u003e my side of the channel(s). Assuming I'm willing to accept this tradeoff,\n\u003e do you see other complications or issues with hidden liquidity?\n\u003e\n\u003e My gut feeling is that this isn't an issue, at all, as channel balances\n\u003e change all the time, which is something the algorithm already has to\n\u003e deal with.\n\u003e\n\nAs you noted from a probabilistic payment delivery point of view I might be\ninterested in signaling all the liquidity that is being provided between\ntwo peers and I shoot myself if I hide it. That being said you might have\nreasons to do so and additionally I never rejected the idea to extend the\ncurrent probabilistic model with a probabilistic node or channel provenance\nvalue that would be similar to the ideas in lnd's mission control or the\nroutescore by https://lnrouter.app. Given the fact that with hidden\nliquidity the probabilities are constantly underestimated such a provenance\nscore will probably be higher than the one of other channels fixing the\n\"introduced issue\" of hidden liquidity\n\n8) Quality of Approximation\n\u003e\n\u003e There are some problems in computer science that are hard/impossible to\n\u003e approximate, in the sense that any kind of deviation from the optimum\n\u003e could cause the computed results to be extremely bad. Do you have some\n\u003e idea (or proof) that your kind of approximation isn't causing a major\n\u003e issue? I guess a piece-wise linearization with an infinite number of\n\u003e pieces corresponds to the optimal result. Given a finite number of\n\u003e pieces, how large is the difference to the optimum?\n\u003e\n\nWe don't have to go to infinite to find a solution without error. We can\nstay with the finite number that corresponds to the channels capacity and\nmake segments of 1 satoshi each encoding what this satoshi would actually\ncost in the original function (assuming all values in the original function\nwere integers).\n\nI have not spent the time to properly express the error in dependence of\nthe number of segments N or even empirically study its tradeoffs in\npractice (as I haven't even included the optimal piecewise linearization\nyet) However the actual flow (see below) as well as the results from Dr.\nMartin Berger\nhttps://lists.linuxfoundation.org/pipermail/lightning-dev/2022-March/003513.html\nindicate\nthat the error should be possible to be managed and stay small enough in\npractice. That being said and as above it certainly makes sense to invest a\nbit of time on how to conduct the piecewise linearization properly.\n\nOutput of the computed flow from the iPython notebok with a piece wise\nlinearization of 5 equal sized segments per channel\n\n\nPlanning to deliver 0.50 BTC from 5051(03efccf...) to 13006\n(021c97a...) via an approximated optimally reliable payment flow...\n\nRuntime of flow computation: 0.85 sec\nMinimum approximated quadratic cost:  815932\n\n Arc \t\t\t      Flow / Capacity \tprobability \tFee (sats)\n5051 -\u003e 8463     \t  6700000 / 16777215 \t0.600649\t8957.900000\n5051 -\u003e 3437     \t  1800000 / 9000000 \t0.800000\t2406.600000\n5051 -\u003e 9162     \t  1240000 / 6200000 \t0.800000\t1657.880000\n5051 -\u003e 14746     \t  6700000 / 16777215 \t0.600649\t8957.900000\n5051 -\u003e 14832     \t  2000000 / 10000000 \t0.800000\t2674.000000\n6257 -\u003e 14832     \t  3350000 / 2411344242 \t0.998611\t335.100000\n14832 -\u003e 12446     \t  5350000 / 6200000000 \t0.999137\t6.350000\n7870 -\u003e 6257     \t  3350000 / 20000000 \t0.832500\t34.500000\n14746 -\u003e 12446     \t  6700000 / 100000000 \t0.933000\t3350.000000\n7914 -\u003e 13006     \t  6700000 / 200000000 \t0.966500\t33501.000000\n5051 -\u003e 550     \t  3300000 / 15000000 \t0.780000\t4412.100000\n11396 -\u003e 13192     \t  6700000 / 1000000000 \t0.993300\t2010.000000\n5051 -\u003e 11396     \t  6700000 / 16777215 \t0.600649\t8957.900000\n7199 -\u003e 9162     \t  3350000 / 445000000 \t0.992472\t848.550000\n9162 -\u003e 12446     \t  16590000 / 3900000000 \t0.995746\t17.590000\n5051 -\u003e 13287     \t  2000000 / 10000000 \t0.800000\t2674.000000\n5051 -\u003e 1843     \t  6700000 / 16777215 \t0.600649\t8957.900000\n5051 -\u003e 11257     \t  3350000 / 16777215 \t0.800324\t4478.950000\n1953 -\u003e 12446     \t  2160000 / 750000000 \t0.997120\t1080.000000\n550 -\u003e 1843     \t  3300000 / 30000000 \t0.890000\t1155.000000\n12756 -\u003e 12446     \t  2000000 / 16775679 \t0.880780\t301.000000\n5051 -\u003e 12756     \t  2000000 / 10000000 \t0.800000\t2674.000000\n3437 -\u003e 12446     \t  1800000 / 400000000 \t0.995500\t225.001000\n6713 -\u003e 7914     \t  6700000 / 200000000 \t0.966500\t837.501000\n11257 -\u003e 7199     \t  3350000 / 16777215 \t0.800324\t663.300000\n10914 -\u003e 9162     \t  2000000 / 500000000 \t0.996000\t1000.001000\n5051 -\u003e 7870     \t  3350000 / 16777215 \t0.800324\t3.781000\n8463 -\u003e 5288     \t  6700000 / 500000000 \t0.986600\t837.501000\n2781 -\u003e 10914     \t  2000000 / 500000000 \t0.996000\t401.000000\n13192 -\u003e 6713     \t  6700000 / 500000000 \t0.986600\t16750.000000\n32 -\u003e 2781     \t  2000000 / 210000000 \t0.990476\t200.000000\n5051 -\u003e 9530     \t  2160000 / 10811137 \t0.800206\t2.591000\n9530 -\u003e 1953     \t  2160000 / 16777215 \t0.871254\t438.336000\n1843 -\u003e 9162     \t  10000000 / 300000000 \t0.966667\t2500.000000\n5051 -\u003e 14642     \t  2000000 / 10000000 \t0.800000\t2.431000\n14642 -\u003e 13006     \t  2000000 / 50000000 \t0.960000\t6001.000000\n13287 -\u003e 32     \t  2000000 / 16777215 \t0.880791\t500.000000\n12446 -\u003e 13006     \t  34600000 / 200000000 \t0.827000\t103766.400000\n5288 -\u003e 13006     \t  6700000 / 100000000 \t0.933000\t15216.700000\n\nProbability of entire flow: 0.0032\nTotal fee: 248793.763 sats\nEffective fee rate: 0.498 %\nArcs included in payment flow: 39\n\nDon't get confused by a low probability. The first attampt always has\nhigh uncertainty. We will learn fast in each consequitive round.\n\n\nWith kind regards Rene Pickhardt\n\n-- \n\u003e Dr. Carsten Otto\n\u003e carsten at c-otto.de\n\u003e https://c-otto.de\n\u003e _______________________________________________\n\u003e Lightning-dev mailing list\n\u003e Lightning-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev\n\u003e\n\n\n-- \nhttps://www.rene-pickhardt.de\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20220314/77da14bd/attachment-0001.html\u003e"}