René Pickhardt [ARCHIVE] on Nostr: 📅 Original date posted:2022-09-23 📝 Original message: Dear Matt and Lightning ...
📅 Original date posted:2022-09-23
📝 Original message:
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 <lf-lists at mattcorallo.com>
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 <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: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20220923/b0791f3f/attachment-0001.html>;
📝 Original message:
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 <lf-lists at mattcorallo.com>
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 <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: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20220923/b0791f3f/attachment-0001.html>;