René Pickhardt [ARCHIVE] on Nostr: 📅 Original date posted:2021-03-18 📝 Original message: Dear Elias, Thanks for ...
đź“… Original date posted:2021-03-18
đź“ť Original message:
Dear Elias,
Thanks for your kind words!
In the paper we suggest clients sort paths by probability but skip the ones
that charge fees that are too high for a user, which could be defined in a
user setting. I should have repeated that when I expressed that implicitly
with this sentence in my mail:
"This means that nodes which provide a lot of liquidity and thus utility
might be able to charge higher fees (as long as they are small enough so
that users are willing to pay them)"
I think that is very similar to your suggestion and of course one could
include not only fees but other criteria while filtering.
In general I think it is reasonable to be aware of the most likely path as
the inverse probability is the number of expected attempts. This if due to
failures and updating the knowledge and channel probabilities the remaining
path probabilities drop below a certain (configurable) value one might want
to stop trying or consider a more expensive path.
So if for example a user was to say I am willing to pay up to 0.5% of the
amount in routing fees but after a few attempts the likeliest path has only
a 0.01% chance a client could say something like: "it is very unlikely to
deliver the payment but if you pay 0.7% fees there is a chance (want to
try?)" Of course at some point onchain / opening a new channel might be
cheaper which would contribute to the potential emerging fee market.
Instead of filtering paths by fees one could also weight the probabilities
with the fees. An easy (but maybe not optimal) approach for that would be
to multiply the log probabilities (which have to be low for high success)
with the fees. That being said I think the main important result is that we
should always be aware of (multi)path probabilities during the trial and
error phase especially in order to make splitting decisions and to
determine when to stop trying
Best Rene
Elias Rohrer <lnml at tnull.de> schrieb am Do., 18. März 2021, 09:34:
> Dear René,
>
> thank you for the great work!
>
> One quick question regarding the consequence you mentioned: it seems
> plausible that manipulating the path choices would become harder, if the
> ability of doing so was correlated with the capacity locked in the network.
> However, if paths were only chosen regarding the probability of payment
> success (and neglecting accruing fees), couldn't high-capacity nodes in
> absence of competition simply raise their fee levels indefinitely, since
> they would be chosen regardless? Do you have any ideas how to protect
> against this?
>
> I imagine that some kind of 'mixed' strategy could be reasonable, in which
> certain paths are pre-filtered based on the probability of payment success,
> and then the final path is selected along the lines of the currently
> deployed fee rate/CLTV risk assessment?
>
> Kind Regards,
>
> Elias
>
> On 17 Mar 2021, at 13:50, René Pickhardt via Lightning-dev wrote:
>
> Dear fellow Lightning Network developers,
>
> I am very pleased to share with you some research progress [0] with
> respect to achieving better payment path finding and a better reliability
> of the payment process.
>
> TL;DR summary: In payment (multi)path finding use the (multi)paths with
> the highest success probability instead of the shortest or cheapest ones.
> (multi)path success probability is the product of channel success
> probabilities. Given current data crawled on the Network the channel
> success probability grows with the capacity of the channel and with smaller
> amounts that are to be sent (which is both intuitively obvious).
> (Multi)path success probability thus declines exponentially the more
> uncertain channels are included.
>
> I understand that the actual payment path finding is not part of the spec
> but I think my results should be relevant to the list since:
>
> a) The payment pathfinding is currently based on trial and error approach
> which has consequences that have not been studied well in the context of
> the Lightning Network
> b) All implementations will use some heuristics in order to achieve
> pathfinding.
> c) Quick path finding is a crucial for a good user experience.
> d) The uncertainty of payment paths is frequently quoted as a major
> criticism of the Lightning Network (c.f. [1]) and I believe the methodology
> of this paper can be used to address this.
>
> The main breakthrough is that a very simple model that puts the
> uncertainty of channel balances at its heart. We belief the uncertainty of
> channel balance values is the main reason why some payments take several
> attempts and thus take more time. With the help of probability theory we
> are able to define the channel success and failure probabilities and
> similarly (multi)path success and failure probabilities. Other Failure
> reasons could also be included to the probability distributions.
>
> With the help of crawling small samples of the network we observe that the
> probability distributions of the channel balances can be estimated well
> with a uniform distribution (which was a little bit surprising) but leads
> to surprisingly easy formulas. We are able to quantify the uncertainty in
> the channels and use negative Bernoulli trials to compute the expected
> number of attempts that are necessary to deliver a payment of a particular
> amount from one node to another participant of the network. This can be
> used to abort the trial and error path finding if the probability becomes
> to low (expected number of attempts too high)
>
> We can mathematically show what people already knew (and draw conclusions
> like the mentioned ones from it):
>
> a) smaller amounts have higher success probabilities
> b) the success probability declines exponentially with the number of
> uncertain channels in a (multi)path.
> c) depending on the payment pair, amount and splitting strategy it can be
> decided into how many parts a payment should be split to achieve the
> highest success probability.
> d) In particular for small amounts splitting almost never makes sense.
>
> We demonstrate that sorting paths by their descending success probability
> during the trial and error payment process (instead of currently used
> heuristics like fees or route length) and updating the probabilities from
> current failures decreases the number of average attempts and produces a
> much faster delivery of payments.
>
> Additionally we looked what happened if BOLT14 [2] was implemented or
> nodes otherwise would pro-actively rebalance their channels according to
> previous research [3] and realized that the observed prior distribution
> changes from uniform to normal. This is great as small payments become even
> more likely (as one would intuitively assume and as previously showed) Our
> results show that probabilisitic path finding on a rebalanced network works
> even better (as in fewer failed attempts) which is yet another hint why
> BOLT14 might be a good idea. However as mentioned the results can be
> implemented even without BOLT14 or without other protocol changes by any
> implementation.
>
> One consequence from the paper that is not discussed heavily within the
> paper that I find pretty interesting is that if implementations follow the
> recommendation to use a probabilistic approach they will tend to route
> payments along high capacity channels. While the fee based routing can
> easily be gamed by dumping fees it is much harder to provide more
> liquidity. And if done this would actually provide a service to the
> network. This means that nodes which provide a lot of liquidity and thus
> utility might be able to charge higher fees (as long as they are small
> enough so that users are willing to pay them) which would probably allow
> the emergence of a real routing fee market.
>
> One note on the question of MPP: In the last couple weeks I have been
> collaborating with Christian Decker. I belief (by using the methodology
> from this paper) to also have a definite solution to the question of:
>
> How to split a payment into k parts and how many funds to allocate to each
> path to increase the (multi)path success probability.
>
> While this is is not addressed in the attached paper as we still need to
> run evaluations I can already share that an equal sized split as used in
> the paper (and by some implementations) is not preferable as one can easily
> see from this example:
> Imagine one is to deliver 100 satoshi and has to paths with 1 uncertain
> channel on each path. The first of capacity 101 and the second of 51.
> Obviously trying to send 100 satoshi along the 101 capacity channel is bad.
> Similarly splitting 50/50 and sending 50 Satoshi along the 51 satoshi
> capacity channel is also bad. Thus a split that allocates for example 67
> Satoshi to the 101 capacity and 33 to the 51 satoshi channel seems way more
> reasonable. Actually 75/25 would probably be the best solution for such a
> setting. And no it is only random coincident that a binary splitter would
> have arrived at that split eventually (after potential miss trials)
> There is way more math theory of how to actually solve the optimization
> problem in the general case and how to find a split and paths that
> maximizes the probability of the attempts. I cannot share these results yet
> but I am pretty confident that there will be updates on that end very soon.
>
> with kind regards Rene
>
> [0]: https://arxiv.org/abs/2103.08576 Security and Privacy of Lightning
> Network Payments with Uncertain Channel Balances
> [1]:
> https://www.whatbitcoindid.com/podcast/peter-rizuns-lightning-critique-fud-or-fair
> [2]: https://github.com/lightningnetwork/lightning-rfc/pull/780
> [3]:
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-December/002406.html
>
> --
> https://www.rene-pickhardt.de
>
> Skype: rene.pickhardt
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20210318/8089a750/attachment.html>;
đź“ť Original message:
Dear Elias,
Thanks for your kind words!
In the paper we suggest clients sort paths by probability but skip the ones
that charge fees that are too high for a user, which could be defined in a
user setting. I should have repeated that when I expressed that implicitly
with this sentence in my mail:
"This means that nodes which provide a lot of liquidity and thus utility
might be able to charge higher fees (as long as they are small enough so
that users are willing to pay them)"
I think that is very similar to your suggestion and of course one could
include not only fees but other criteria while filtering.
In general I think it is reasonable to be aware of the most likely path as
the inverse probability is the number of expected attempts. This if due to
failures and updating the knowledge and channel probabilities the remaining
path probabilities drop below a certain (configurable) value one might want
to stop trying or consider a more expensive path.
So if for example a user was to say I am willing to pay up to 0.5% of the
amount in routing fees but after a few attempts the likeliest path has only
a 0.01% chance a client could say something like: "it is very unlikely to
deliver the payment but if you pay 0.7% fees there is a chance (want to
try?)" Of course at some point onchain / opening a new channel might be
cheaper which would contribute to the potential emerging fee market.
Instead of filtering paths by fees one could also weight the probabilities
with the fees. An easy (but maybe not optimal) approach for that would be
to multiply the log probabilities (which have to be low for high success)
with the fees. That being said I think the main important result is that we
should always be aware of (multi)path probabilities during the trial and
error phase especially in order to make splitting decisions and to
determine when to stop trying
Best Rene
Elias Rohrer <lnml at tnull.de> schrieb am Do., 18. März 2021, 09:34:
> Dear René,
>
> thank you for the great work!
>
> One quick question regarding the consequence you mentioned: it seems
> plausible that manipulating the path choices would become harder, if the
> ability of doing so was correlated with the capacity locked in the network.
> However, if paths were only chosen regarding the probability of payment
> success (and neglecting accruing fees), couldn't high-capacity nodes in
> absence of competition simply raise their fee levels indefinitely, since
> they would be chosen regardless? Do you have any ideas how to protect
> against this?
>
> I imagine that some kind of 'mixed' strategy could be reasonable, in which
> certain paths are pre-filtered based on the probability of payment success,
> and then the final path is selected along the lines of the currently
> deployed fee rate/CLTV risk assessment?
>
> Kind Regards,
>
> Elias
>
> On 17 Mar 2021, at 13:50, René Pickhardt via Lightning-dev wrote:
>
> Dear fellow Lightning Network developers,
>
> I am very pleased to share with you some research progress [0] with
> respect to achieving better payment path finding and a better reliability
> of the payment process.
>
> TL;DR summary: In payment (multi)path finding use the (multi)paths with
> the highest success probability instead of the shortest or cheapest ones.
> (multi)path success probability is the product of channel success
> probabilities. Given current data crawled on the Network the channel
> success probability grows with the capacity of the channel and with smaller
> amounts that are to be sent (which is both intuitively obvious).
> (Multi)path success probability thus declines exponentially the more
> uncertain channels are included.
>
> I understand that the actual payment path finding is not part of the spec
> but I think my results should be relevant to the list since:
>
> a) The payment pathfinding is currently based on trial and error approach
> which has consequences that have not been studied well in the context of
> the Lightning Network
> b) All implementations will use some heuristics in order to achieve
> pathfinding.
> c) Quick path finding is a crucial for a good user experience.
> d) The uncertainty of payment paths is frequently quoted as a major
> criticism of the Lightning Network (c.f. [1]) and I believe the methodology
> of this paper can be used to address this.
>
> The main breakthrough is that a very simple model that puts the
> uncertainty of channel balances at its heart. We belief the uncertainty of
> channel balance values is the main reason why some payments take several
> attempts and thus take more time. With the help of probability theory we
> are able to define the channel success and failure probabilities and
> similarly (multi)path success and failure probabilities. Other Failure
> reasons could also be included to the probability distributions.
>
> With the help of crawling small samples of the network we observe that the
> probability distributions of the channel balances can be estimated well
> with a uniform distribution (which was a little bit surprising) but leads
> to surprisingly easy formulas. We are able to quantify the uncertainty in
> the channels and use negative Bernoulli trials to compute the expected
> number of attempts that are necessary to deliver a payment of a particular
> amount from one node to another participant of the network. This can be
> used to abort the trial and error path finding if the probability becomes
> to low (expected number of attempts too high)
>
> We can mathematically show what people already knew (and draw conclusions
> like the mentioned ones from it):
>
> a) smaller amounts have higher success probabilities
> b) the success probability declines exponentially with the number of
> uncertain channels in a (multi)path.
> c) depending on the payment pair, amount and splitting strategy it can be
> decided into how many parts a payment should be split to achieve the
> highest success probability.
> d) In particular for small amounts splitting almost never makes sense.
>
> We demonstrate that sorting paths by their descending success probability
> during the trial and error payment process (instead of currently used
> heuristics like fees or route length) and updating the probabilities from
> current failures decreases the number of average attempts and produces a
> much faster delivery of payments.
>
> Additionally we looked what happened if BOLT14 [2] was implemented or
> nodes otherwise would pro-actively rebalance their channels according to
> previous research [3] and realized that the observed prior distribution
> changes from uniform to normal. This is great as small payments become even
> more likely (as one would intuitively assume and as previously showed) Our
> results show that probabilisitic path finding on a rebalanced network works
> even better (as in fewer failed attempts) which is yet another hint why
> BOLT14 might be a good idea. However as mentioned the results can be
> implemented even without BOLT14 or without other protocol changes by any
> implementation.
>
> One consequence from the paper that is not discussed heavily within the
> paper that I find pretty interesting is that if implementations follow the
> recommendation to use a probabilistic approach they will tend to route
> payments along high capacity channels. While the fee based routing can
> easily be gamed by dumping fees it is much harder to provide more
> liquidity. And if done this would actually provide a service to the
> network. This means that nodes which provide a lot of liquidity and thus
> utility might be able to charge higher fees (as long as they are small
> enough so that users are willing to pay them) which would probably allow
> the emergence of a real routing fee market.
>
> One note on the question of MPP: In the last couple weeks I have been
> collaborating with Christian Decker. I belief (by using the methodology
> from this paper) to also have a definite solution to the question of:
>
> How to split a payment into k parts and how many funds to allocate to each
> path to increase the (multi)path success probability.
>
> While this is is not addressed in the attached paper as we still need to
> run evaluations I can already share that an equal sized split as used in
> the paper (and by some implementations) is not preferable as one can easily
> see from this example:
> Imagine one is to deliver 100 satoshi and has to paths with 1 uncertain
> channel on each path. The first of capacity 101 and the second of 51.
> Obviously trying to send 100 satoshi along the 101 capacity channel is bad.
> Similarly splitting 50/50 and sending 50 Satoshi along the 51 satoshi
> capacity channel is also bad. Thus a split that allocates for example 67
> Satoshi to the 101 capacity and 33 to the 51 satoshi channel seems way more
> reasonable. Actually 75/25 would probably be the best solution for such a
> setting. And no it is only random coincident that a binary splitter would
> have arrived at that split eventually (after potential miss trials)
> There is way more math theory of how to actually solve the optimization
> problem in the general case and how to find a split and paths that
> maximizes the probability of the attempts. I cannot share these results yet
> but I am pretty confident that there will be updates on that end very soon.
>
> with kind regards Rene
>
> [0]: https://arxiv.org/abs/2103.08576 Security and Privacy of Lightning
> Network Payments with Uncertain Channel Balances
> [1]:
> https://www.whatbitcoindid.com/podcast/peter-rizuns-lightning-critique-fud-or-fair
> [2]: https://github.com/lightningnetwork/lightning-rfc/pull/780
> [3]:
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-December/002406.html
>
> --
> https://www.rene-pickhardt.de
>
> Skype: rene.pickhardt
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20210318/8089a750/attachment.html>;