Elias Rohrer [ARCHIVE] on Nostr: 📅 Original date posted:2021-03-18 📝 Original message: Dear René, ah, it seems ...
đź“… Original date posted:2021-03-18
đź“ť Original message:
Dear René,
ah, it seems I overlooked that sentence. Thanks for clearing this up. I
agree, filtering based on probability and then weighing based on cost is
probably very similar to doing it vice versa.
Kind Regards,
Elias
On 18 Mar 2021, at 10:12, René Pickhardt wrote:
> 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/c071a113/attachment-0001.html>;
đź“ť Original message:
Dear René,
ah, it seems I overlooked that sentence. Thanks for clearing this up. I
agree, filtering based on probability and then weighing based on cost is
probably very similar to doing it vice versa.
Kind Regards,
Elias
On 18 Mar 2021, at 10:12, René Pickhardt wrote:
> 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/c071a113/attachment-0001.html>;