From r.pickhardt at googlemail.com Fri Sep 23 10:27:03 2022 From: r.pickhardt at googlemail.com (=?UTF-8?Q?Ren=C3=A9_Pickhardt?=) Date: Fri, 23 Sep 2022 12:27:03 +0200 Subject: [Lightning-dev] `htlc_maximum_msat` as a valve for flow control on the Lightning Network In-Reply-To: References: Message-ID: Dear Matt and Lightning developers, those are excellent and important questions that I should probably have addressed more explicitly in the article / ml-post! Let me add what I currently know and begin with your second question as I think I think the answer will be more objective / verifiable while my response to the gossip question is a bit more speculative at this point: On Fri, Sep 23, 2022 at 10:43 AM Matt Corallo wrote: b) What are the privacy implications of the naive "update on drained > channel", and have you done any > analysis of the value of this type of gossip update at different levels of > privacy? > We know from information theory that the distribution with the highest entropy is the uniform distribution [1] which in the context of a channel with capacity of `c` means `log(c+1)` bits as shown in [2]. Now if a given drain leads to a pair of `htlc_maximum_msat` one could in deed also go the other way around and look at the pair of `htlc_maximum_msat` and estimate the *past* drain. And of course also the (the non uniform) liquidity distribution from the past. Note that now with the better `htlc_maximum_msat` pair the distribution should be closer to uniform again which is actually best from an information theoretic point of view as this maximizes the entropy in the channel. I have just created and uploaded a small python script / notebook [3] from which we can see for example how much information about the shape of the past liquidity distribution we would learn if we could induce from the `htlc_maximum_msat` pair that the drain was 0.75. So from the notebook I quote: Assume we learnt a drain of 0.75 ================================= Entropy of uniform: 20.00 bits. Entropy of the channel with drain: 19.17 bits Information gain: 0.83 bits Yes we learnt less than 1 bit of information by knowing the shape of the distribution from the last payments. This much is learnt by a single probe. Given that we expect our payment failure rates to drop by an order of magnitude and the fact that I could probably learn the drain from the on chain signal or gossip anyway I personally would consider this information leakage to be acceptable. But of course people may not agree with me and just not set their `htlc_maximum_msat` flag in the proposed manner. Also it is obvious that higher drain values produce a more heavily depleted channel and we might learn more bits (in case of a 0.95 drain we learnt about 3 bits.) a) How much gossip overhead do you expect this type of protocol to > generate/is there a useful > outcome for this type of update even if you limit gossip updates to > once/twice/thrice per day? > As written in the article I expect the setting of the valves as throtteling devices to be rather stable as I would assume the drain on channels should not be impacted too heavily by installing valves. This assumption is certainly more reasonable if nodes already used min cost flow solvers to send out payments and less reasonable if nodes still use ad-hoc splitting heuristics and restrict their path finding on channels with sufficiently large `htlc_maximum_msat` values for the amount of the partial payment. In any case I expect that once the valve is in a good setting for a particular channel / drain the setting can stay as long as the drain won't change significantly. In general I would not expect drain on channels to change heavily over time (though I certainly would not expect it to be static / stable either). Certainly fee changes in the network (and other factors) may eventually produce changes in drain on channels which would also have to eventually be reflected in new settings for the valve. The experimental algorithm idea that I presented in cell 12 of the original notebook (which I also used in the privacy consideration code from above) computes the histogram of liquidity of the last N routing requests (failed and successful ones) that a node saw on the channel and then makes a decision weather to open or close the valve a bit more. Using this greedy strategy we saw in the notebook that a node could find decent values in logarithmic many steps . So while the setup of the valve may trigger a few gossip messages (but each one only after a sufficient amount of routing requests have been processed) and while I expect dynamics in drain on the channel I don't expect such adoptions should have to happen in real time or even several times per day and put unnecessary load / spam to gossip. But I guess we can only see this by operating nodes and probably there are some nodes where updates occure more frequently than with other nodes. That being said of course if the peers of a channel work together and both exchange information / collaborate in finding a good `htlc_maximum_msat` pair (similalry as our protocol for finding fees in a mutual close) they will probably need less gossip messages than in the case where both nodes independently try to find decent settings. I am happy if people have more insights into this and challenge my expectation (because it actually really is only an expectation / intuition at this point). That being said: Yes even with only a few gossip messages per day I expect for the given reasons the setup of valves to be possible and useful! with kind regards Rene [1]: https://en.wikipedia.org/wiki/Maximum_entropy_probability_distribution#Uniform_and_piecewise_uniform_distributions [2]: https://arxiv.org/abs/2103.08576 [3]: https://github.com/lnresearch/Flow-Control-on-Lightning-Network-Channels-with-Drain-via-Control-Valves/blob/main/Privacy%20Considerations%20of%20signaling%20past%20drain%20via%20%60htlc_maximum_msat%60%20pairs.ipynb > > Thanks, > Matt > > On 9/22/22 2:40 AM, Ren? Pickhardt via Lightning-dev wrote: > > Good morning fellow Lightning Developers, > > > > I am pleased to share my most recent research results [1] with you. They > may (if at all) only have a > > small impact on protocol development / specification but are actually > mainly of concern to node > > operators and LSPs. I still thought they may be relevant for the list. > > > > While trying to estimate the expected liquidity distribution in depleted > channels due to drain via > > Markov Models I realized that we can exploit the `htlc_maxium_msat` > setting to act as a control > > valve and regulate the "pressure" coming from the drain and mitigate the > depletion of channels. Such > > ideas are btw not novel at all and heavily used in fluid networks [2]. > Thus it seems very natural > > that we do the same on the Lightning Network. > > > > In the article we show within a theoretic model how expected payment > failure rates per channel may > > drop significantly by up to an order of magnitude if channels set up > proper asymmetric > > `htlc_maximum_msat` pairs. > > > > We furthermore provide in our iPython notebook [3] two experimental > algorithmic ideas with which > > node operators can find decent `htlc_maximum_msat` values in a greedy > fashion. One of the algorithms > > does not even require to know the drain or payment size distribution or > build the Markov model but > > just looks at the liquidity distribution in the channel at the last x > routing attempts and adjusts > > the `htlc_maximum_msat` value if the distribution is to far away from a > uniform distribution. > > > > Looking forwards for your thoughts and feedback. > > > > with kind regards Rene > > > > > > [1]: > > > https://blog.bitmex.com/the-power-of-htlc_maximum_msat-as-a-control-valve-for-better-flow-control-improved-reliability-and-lower-expected-payment-failure-rates-on-the-lightning-network/ > < > https://blog.bitmex.com/the-power-of-htlc_maximum_msat-as-a-control-valve-for-better-flow-control-improved-reliability-and-lower-expected-payment-failure-rates-on-the-lightning-network/ > > > > [2]: https://en.wikipedia.org/wiki/Control_valve < > https://en.wikipedia.org/wiki/Control_valve> > > [3]: > > > https://github.com/lnresearch/Flow-Control-on-Lightning-Network-Channels-with-Drain-via-Control-Valves/blob/main/htlc_maximum_msat%20as%20a%20valve%20for%20flow%20control%20on%20the%20Lightnig%20network.ipynb > < > https://github.com/lnresearch/Flow-Control-on-Lightning-Network-Channels-with-Drain-via-Control-Valves/blob/main/htlc_maximum_msat%20as%20a%20valve%20for%20flow%20control%20on%20the%20Lightnig%20network.ipynb > > > > > > -- > > https://ln.rene-pickhardt.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: