Re: [Lightning-dev] Route reliability<->fee trade-off control parameter
On Mon, Nov 22, 2021 at 5:11 PM Stefan Richter wrote: > I also don't believe putting a choice of more or less seconds expectation > in the UI makes for a great user experience. IMHO the goal should just be: > give the user an estimate of fees necessary to succeed within a reasonable > time. Maybe give them an option to optimize for fees only if they are > really cheap and don't care at all if the payment succeeds. > In the ideal world, I'd agree to this. But how close to that are we today? Suppose we'd define reasonable time as 3 seconds to complete the payment. And to stay below that, we need to use a short, expensive, high success probability route that amounts to a fee of 1%. Would users be happy with a take it or leave it approach or rather pay 0.1% and wait 30 seconds? I think that for the state of Lightning as it is currently, some kind of control lever is useful to bridge the gap to payments that are always fast and cheap. The checkbox that you propose is also a control lever, but it is pretty minimalistic. Joost ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Route reliability<->fee trade-off control parameter
On Mon, Nov 22, 2021 at 7:53 AM ZmnSCPxj wrote: > Good morning Dave, > > > If LN software speculatively chooses a series of attempts with a similar > > 95%, accounting for things like the probability of a stuck payment (made > > worse by longer CLTV timeouts on some paths), it could present users > > with the same sort of options: > > > > ~1 second, x fee > > ~3 seconds, y fee > > ~10 seconds, z fee > > > > This allows the software to use its reliability scoring efficiently in > > choosing what series of payment attempts to make and presents to the > > user the information they need to make a choice appropriate for their > > situation. As a bonus, it makes it easier for wallet software to move > > towards a world where there is no user-visible difference between > > onchain and offchain payments, e.g.: > > > > ~1 second, w fee > > ~15 seconds, x fee > > ~10 minutes, y fee > > ~60 minutes, z fee > > This may not match ideally, as in the worst case a forwarding might be > struck by literal lightning and dropped off the network while your HTLC is > on that node, only for the relevant channel to be dropped onchain days > later when the timeout comes due. > Providing this "seconds" estimate does not prepare users for the > possibility of such black swan events where a high fee transaction gets > stalled due to an accident on the network. > I like the idea of providing the user with such choices, similar to how for example Uber presents its options. But I also agree with Z that it is probably impossible to get a number of seconds there that comes close to the actual time it would take. For LND, I am currently proposing a fuzzy "time preference" parameter that is vaguely indicative of the time that the payment is expected to take ( https://github.com/lightningnetwork/lnd/pull/6024). On the UI level this can either be surfaced as a slider or the cost for three predefined values for time preference can be shown: Slow: 10 msat Normal: 150 msat Fast: 4000 msat > Why not just ask for a fee budget for a payment, and avoid committing > ourselves to paying within some number of seconds, given that the seconds > estimate may very well vary depending on local CPU load? > Would users really complain overmuch if the number of seconds is not > provided, given that we cannot really estimate this well? > A fee budget indeed expresses the time preference indirectly. But how does the user know what a reasonable value is to set this to? It is depend on network conditions. They may accidentally set it to a value that is too low and get an unexpectedly slow payment. Joost ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Route reliability<->fee trade-off control parameter
I also don't believe putting a choice of more or less seconds expectation in the UI makes for a great user experience. IMHO the goal should just be: give the user an estimate of fees necessary to succeed within a reasonable time. Maybe give them an option to optimize for fees only if they are really cheap and don't care at all if the payment succeeds. Cheers Stefan ZmnSCPxj via Lightning-dev schrieb am Mo., 22. Nov. 2021, 00:53: > Good morning Dave, > > > If LN software speculatively chooses a series of attempts with a similar > > 95%, accounting for things like the probability of a stuck payment (made > > worse by longer CLTV timeouts on some paths), it could present users > > with the same sort of options: > > > > ~1 second, x fee > > ~3 seconds, y fee > > ~10 seconds, z fee > > > > This allows the software to use its reliability scoring efficiently in > > choosing what series of payment attempts to make and presents to the > > user the information they need to make a choice appropriate for their > > situation. As a bonus, it makes it easier for wallet software to move > > towards a world where there is no user-visible difference between > > onchain and offchain payments, e.g.: > > > > ~1 second, w fee > > ~15 seconds, x fee > > ~10 minutes, y fee > > ~60 minutes, z fee > > This may not match ideally, as in the worst case a forwarding might be > struck by literal lightning and dropped off the network while your HTLC is > on that node, only for the relevant channel to be dropped onchain days > later when the timeout comes due. > Providing this "seconds" estimate does not prepare users for the > possibility of such black swan events where a high fee transaction gets > stalled due to an accident on the network. > > On the other hand, humans never really handle black swan events in any > reasonably way anyway, and 95% of the time it will probably achieve that > number of estimated seconds or less. > Even the best onchain estimators fail when a thundering herd of > speculators decides to trade Bitcoin based on random crap from the > noosphere. > > The processing to figure out a payment plan also becomes significant at > the "seconds" level, especially if you switch to mincostflow rather than > shortestpath. > This means the CPU speed of the local node may become significant, or if > you are delegating pathfinding to a trusted server, the load on that > trusted server becomes significant. > Sigh. > > Why not just ask for a fee budget for a payment, and avoid committing > ourselves to paying within some number of seconds, given that the seconds > estimate may very well vary depending on local CPU load? > Would users really complain overmuch if the number of seconds is not > provided, given that we cannot really estimate this well? > > Regards, > ZmnSCPxj > > ___ > Lightning-dev mailing list > Lightning-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Route reliability<->fee trade-off control parameter
Good morning Dave, > If LN software speculatively chooses a series of attempts with a similar > 95%, accounting for things like the probability of a stuck payment (made > worse by longer CLTV timeouts on some paths), it could present users > with the same sort of options: > > ~1 second, x fee > ~3 seconds, y fee > ~10 seconds, z fee > > This allows the software to use its reliability scoring efficiently in > choosing what series of payment attempts to make and presents to the > user the information they need to make a choice appropriate for their > situation. As a bonus, it makes it easier for wallet software to move > towards a world where there is no user-visible difference between > onchain and offchain payments, e.g.: > > ~1 second, w fee > ~15 seconds, x fee > ~10 minutes, y fee > ~60 minutes, z fee This may not match ideally, as in the worst case a forwarding might be struck by literal lightning and dropped off the network while your HTLC is on that node, only for the relevant channel to be dropped onchain days later when the timeout comes due. Providing this "seconds" estimate does not prepare users for the possibility of such black swan events where a high fee transaction gets stalled due to an accident on the network. On the other hand, humans never really handle black swan events in any reasonably way anyway, and 95% of the time it will probably achieve that number of estimated seconds or less. Even the best onchain estimators fail when a thundering herd of speculators decides to trade Bitcoin based on random crap from the noosphere. The processing to figure out a payment plan also becomes significant at the "seconds" level, especially if you switch to mincostflow rather than shortestpath. This means the CPU speed of the local node may become significant, or if you are delegating pathfinding to a trusted server, the load on that trusted server becomes significant. Sigh. Why not just ask for a fee budget for a payment, and avoid committing ourselves to paying within some number of seconds, given that the seconds estimate may very well vary depending on local CPU load? Would users really complain overmuch if the number of seconds is not provided, given that we cannot really estimate this well? Regards, ZmnSCPxj ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Route reliability<->fee trade-off control parameter
On Mon, Nov 15, 2021 at 04:25:26PM +0100, Joost Jager wrote: > Reliability is a property of a route that can > be expressed as a probability. The probability that a route will be > successful. I don't think users care about the abstract concept of reliability that's being returned by the pathfinding code here. What users care about is "how long will it take for my payment to make the point-of-sale terminal turn green so I can walk away with my warm beverage?" This is basically analogous to the fee optimization question that onchain wallets have been asking users for years: how many blocks do you want to wait for [the first] confirmation? The way that's presented to users in software like Bitcoin Core is, 2 blocks (~20 minutes), x fee 6 blocks (~60 minutes), y fee 36 blocks (~6 hours), z fee etc... The onchain estimates in Bitcoin Core are based[1] on a 95% threshold. If LN software speculatively chooses a series of attempts with a similar 95%, accounting for things like the probability of a stuck payment (made worse by longer CLTV timeouts on some paths), it could present users with the same sort of options: ~1 second, x fee ~3 seconds, y fee ~10 seconds, z fee This allows the software to use its reliability scoring efficiently in choosing what series of payment attempts to make and presents to the user the information they need to make a choice appropriate for their situation. As a bonus, it makes it easier for wallet software to move towards a world where there is no user-visible difference between onchain and offchain payments, e.g.: ~1 second, w fee ~15 seconds, x fee ~10 minutes, y fee ~60 minutes, z fee -Dave [1] https://gist.github.com/morcos/d3637f015bc4e607e1fd10d8351e9f41 signature.asc Description: PGP signature ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Route reliability<->fee trade-off control parameter
Yep, this is roughly the direction we've gone in LDK - an abstract interface that gives you some information about a channel and you return "I'm willing to pay up to X msats to avoid routing over that channel as specified". It's obviously not perfect in the sense that it won't generate the absolute optimal route given the parameters, but it can do pretty well (after some additional fixes we'd like to land) and at least optimizes for something the user controls. Sadly, of course, all of this requires a good model for failure probability, something we don't yet have, so we rely on some naive guesses in our default code, and let the user plug in a more advanced model if they prefer. Long-term we'll probably add more intelligence, as others (or at least c-lightning) have done. Matt On 11/15/21 14:44, Joost Jager wrote: One direction that I explored is to start with a statement by the user in this form: "If there is a route with a success probability of 50%, then I am willing to pay up to 1.8x the routing fee for an alternative route that has a 80% success probability" I like this because it isn't an abstract weight or factor. It is actually clear what this means. What I didn't yet succeed in is to find a model where I can plug in 50%, 80% and 1.8x and generalizes it to arbitrary inputs A% and B%. But it seems to me that there must be some probabilistic equation / law / rule / theorem / ... that can support this. Joost. On Mon, Nov 15, 2021 at 4:25 PM Joost Jager mailto:joost.ja...@gmail.com>> wrote: In Lightning pathfinding the two main variables to optimize for are routing fee and reliability. Routing fee is concrete. It is the sat amount that is paid when a payment succeeds. Reliability is a property of a route that can be expressed as a probability. The probability that a route will be successful. During pathfinding, route options are compared against each other. So for example: Route A: fee 10 sat, success probability 50% Route B: fee 20 sat, success probability 80% Which one is the better route? That depends on user preference. A patient user will probably go for route A in the hope of saving on fees whereas for a time-sensitive payment route B looks better. It would be great to offer this trade-off to the user in a simple way. Preferably a single [0, 1] value that controls the selection process. At 0, the route is only optimized for fees and probabilities are ignored completely. At 1, the route is only optimized for reliability and fees are ignored completely. But how to choose between the routes A and B for a value somewhere in between 0 and 1? For example 0.5 - perfect balance between reliability and fee. But what does that mean exactly? Anyone got an idea on how to approach this best? I am looking for a simple formula to decide between routes, preferably with a reasonably sound probability-theoretical basis (whatever that means). Joost ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Route reliability<->fee trade-off control parameter
Good morning Joost, > What I did in lnd is to work with so called 'payment attempt cost'. A virtual > satoshi amount that represents the cost of a failed attempt. https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-August/003191.html And I quote: > Introduction > > > What is the cost of a failed LN payment? See link for more. Regards, ZmnSCPxj ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Route reliability<->fee trade-off control parameter
It seems to me there can be no such law unless P=NP. Which would also imply Bitcoin is worthless. Joost Jager schrieb am Mo., 15. Nov. 2021, 13:44: > One direction that I explored is to start with a statement by the user in > this form: > > "If there is a route with a success probability of 50%, then I am willing > to pay up to 1.8x the routing fee for an alternative route that has a 80% > success probability" > > I like this because it isn't an abstract weight or factor. It is actually > clear what this means. > > What I didn't yet succeed in is to find a model where I can plug in 50%, > 80% and 1.8x and generalizes it to arbitrary inputs A% and B%. But it seems > to me that there must be some probabilistic equation / law / rule / theorem > / ... that can support this. > > Joost. > > On Mon, Nov 15, 2021 at 4:25 PM Joost Jager wrote: > >> In Lightning pathfinding the two main variables to optimize for are >> routing fee and reliability. Routing fee is concrete. It is the sat amount >> that is paid when a payment succeeds. Reliability is a property of a route >> that can be expressed as a probability. The probability that a route will >> be successful. >> >> During pathfinding, route options are compared against each other. So for >> example: >> >> Route A: fee 10 sat, success probability 50% >> Route B: fee 20 sat, success probability 80% >> >> Which one is the better route? That depends on user preference. A patient >> user will probably go for route A in the hope of saving on fees whereas for >> a time-sensitive payment route B looks better. >> >> It would be great to offer this trade-off to the user in a simple way. >> Preferably a single [0, 1] value that controls the selection process. At 0, >> the route is only optimized for fees and probabilities are ignored >> completely. At 1, the route is only optimized for reliability and fees are >> ignored completely. >> >> But how to choose between the routes A and B for a value somewhere in >> between 0 and 1? For example 0.5 - perfect balance between reliability and >> fee. But what does that mean exactly? >> >> Anyone got an idea on how to approach this best? I am looking for a >> simple formula to decide between routes, preferably with a reasonably sound >> probability-theoretical basis (whatever that means). >> >> Joost >> > ___ > Lightning-dev mailing list > Lightning-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Route reliability<->fee trade-off control parameter
One direction that I explored is to start with a statement by the user in this form: "If there is a route with a success probability of 50%, then I am willing to pay up to 1.8x the routing fee for an alternative route that has a 80% success probability" I like this because it isn't an abstract weight or factor. It is actually clear what this means. What I didn't yet succeed in is to find a model where I can plug in 50%, 80% and 1.8x and generalizes it to arbitrary inputs A% and B%. But it seems to me that there must be some probabilistic equation / law / rule / theorem / ... that can support this. Joost. On Mon, Nov 15, 2021 at 4:25 PM Joost Jager wrote: > In Lightning pathfinding the two main variables to optimize for are > routing fee and reliability. Routing fee is concrete. It is the sat amount > that is paid when a payment succeeds. Reliability is a property of a route > that can be expressed as a probability. The probability that a route will > be successful. > > During pathfinding, route options are compared against each other. So for > example: > > Route A: fee 10 sat, success probability 50% > Route B: fee 20 sat, success probability 80% > > Which one is the better route? That depends on user preference. A patient > user will probably go for route A in the hope of saving on fees whereas for > a time-sensitive payment route B looks better. > > It would be great to offer this trade-off to the user in a simple way. > Preferably a single [0, 1] value that controls the selection process. At 0, > the route is only optimized for fees and probabilities are ignored > completely. At 1, the route is only optimized for reliability and fees are > ignored completely. > > But how to choose between the routes A and B for a value somewhere in > between 0 and 1? For example 0.5 - perfect balance between reliability and > fee. But what does that mean exactly? > > Anyone got an idea on how to approach this best? I am looking for a simple > formula to decide between routes, preferably with a reasonably sound > probability-theoretical basis (whatever that means). > > Joost > ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Route reliability<->fee trade-off control parameter
Actually, if you look into our paper, the theory tells us the following: 1) A weighted sum of different cost aspects is attractive because it remains convex if all the aspects are convex themselves. This cannot be said of other methods like the harmonic mean, which kind of forces our hand if we aim to really calculate optimal flows. 2) even in the single path case, finding a route that optimizes one goal (say, reliability) while ensuring that another cost aspect remains under some boundary, is a (weakly) NP hard problem. My interpretation of this fact is that while it is certainly possible to find suitable factors for the linear combination (by, say, gradient descent methods), we cannot expect a method that is simple and works for every conceivable graph every time. In practice, we have observed that the factor needs to be varied over multiple orders of magnitude to make a meaningful impact. Mapping this onto an easy user interface (e.g. your suggestion of a linearly feeling value between 0 and 1) will need some trial and error engineering, IMHO. Cheers, Stefan René Pickhardt via Lightning-dev schrieb am Mo., 15. Nov. 2021, 12:50: > Dear Joost, > > First I am happy that you also agree that reliability can and should be > expressed as a probability as discussed in [0]. > > The problem that you address is that of feature engineering[1]. Which > consists of two (or even more) steps: > > 1.) Feature selection: That means in payment delivery we will compute a > min cost flow [2] with a chosen cost function (historically people used > dijkstra seach for single paths with the cost function representing the > weights on the edges of the graph -which is what most folks currently still > do). While [2] and I personally agree with you that the cost function > should be a combination the two features fees and reliability (as in > successprobability) Matt Corallo righfully pointed out [3] that other > features might be chosen in the future to deliver more optimal results. For > example implementations currently often use CLTV as a feature (which I > honestly find horrible) and I am currently investigating if one could add > latency of channels or - for known IP addresses - either the geo distance > or IP distance. > > 2.) Combining features: This is the question that you are asking. Often > people use a linear weighted sum to combine features. This is what often > happens implicitly in neural networks. While this is often good enough and > while it is often practical to either learn the weights or give users a > choice there are many situation where the weighted linear sum does not work > well with the selected features. An example for the weighted sum is the > risk-factor in c-lightning that could have been used to decide if one > wanted the dijkstra seach to either optimize for CLTV delta or for paid > routing fees. Also in our paper [2] in which we discuss the same two > features that you mentioned we explain how a linear sum of two features can > be optimal due to the lagrangian bounding principle. However in practice > (of machine learning) it has been shown that using the harmonic mean [4] > between features often works very well without the necessity to learn a > weight / parameter. This has for example been done when c-lightnign > recently switched to probabilistic path finding [5]. In this thread you > find a long discussion and evaluation how the harmonic mean outperformed > the linear sum. > > I think the main issue that you address here is that there is no universal > truth for situations like this. In practice only tests and experience will > help us to make good decisions. > > with kind Regards Rene > > [0]: > https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-March/002984.html > [1]: https://en.wikipedia.org/wiki/Feature_engineering > [2]: https://arxiv.org/abs/2107.05322 > [3]: > https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-September/003219.html > [4]: https://en.wikipedia.org/wiki/Harmonic_mean > [5]: https://github.com/ElementsProject/lightning/pull/4771 > > > > > On Mon, Nov 15, 2021 at 4:26 PM Joost Jager wrote: > >> In Lightning pathfinding the two main variables to optimize for are >> routing fee and reliability. Routing fee is concrete. It is the sat amount >> that is paid when a payment succeeds. Reliability is a property of a route >> that can be expressed as a probability. The probability that a route will >> be successful. >> >> During pathfinding, route options are compared against each other. So for >> example: >> >> Route A: fee 10 sat, success probability 50% >> Route B: fee 20 sat, success probability 80% >> >> Which one is the better route? That depends on user preference. A patient >> user will probably go for route A in the hope of saving on fees whereas for >> a time-sensitive payment route B looks better. >> >> It would be great to offer this trade-off to the user in a simple way. >> Preferably a single [0, 1] value that controls the
Re: [Lightning-dev] Route reliability<->fee trade-off control parameter
Hi Rene, > First I am happy that you also agree that reliability can and should be > expressed as a probability as discussed in [0]. > Probability based routing is not new to me. I've implemented a form of that in lnd in march 2019: https://github.com/lightningnetwork/lnd/pull/2802, followed by several rounds of refinement. > The problem that you address is that of feature engineering[1]. Which > consists of two (or even more) steps: > > 1.) Feature selection: That means in payment delivery we will compute a > min cost flow [2] with a chosen cost function (historically people used > dijkstra seach for single paths with the cost function representing the > weights on the edges of the graph -which is what most folks currently still > do). While [2] and I personally agree with you that the cost function > should be a combination the two features fees and reliability (as in > successprobability) Matt Corallo righfully pointed out [3] that other > features might be chosen in the future to deliver more optimal results. For > example implementations currently often use CLTV as a feature (which I > honestly find horrible) and I am currently investigating if one could add > latency of channels or - for known IP addresses - either the geo distance > or IP distance. > I am aware that there are more candidate features, but my question is specifically about the ones that I mentioned. 2.) Combining features: This is the question that you are asking. Often > people use a linear weighted sum to combine features. This is what often > happens implicitly in neural networks. While this is often good enough and > while it is often practical to either learn the weights or give users a > choice there are many situation where the weighted linear sum does not work > well with the selected features. An example for the weighted sum is the > risk-factor in c-lightning that could have been used to decide if one > wanted the dijkstra seach to either optimize for CLTV delta or for paid > routing fees. Also in our paper [2] in which we discuss the same two > features that you mentioned we explain how a linear sum of two features can > be optimal due to the lagrangian bounding principle. However in practice > (of machine learning) it has been shown that using the harmonic mean [4] > between features often works very well without the necessity to learn a > weight / parameter. This has for example been done when c-lightnign > recently switched to probabilistic path finding [5]. In this thread you > find a long discussion and evaluation how the harmonic mean outperformed > the linear sum. > Obviously features can be combined in a multitude of ways, but I am looking for something that is anchored to some kind of understandable starting point. What I did in lnd is to work with so called 'payment attempt cost'. A virtual satoshi amount that represents the cost of a failed attempt. If you put a high price on failed attempts, pathfinding will tend towards more reliable routes even if they require a higher fee. To me, the idea of putting a (virtual) cost on a payment attempt is tangible and ideally the math should follow from that. I don't want zero parameters, because I think that ultimately the fee/reliability trade-off is up to the user to decide on. Joost > ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Route reliability<->fee trade-off control parameter
Dear Joost, First I am happy that you also agree that reliability can and should be expressed as a probability as discussed in [0]. The problem that you address is that of feature engineering[1]. Which consists of two (or even more) steps: 1.) Feature selection: That means in payment delivery we will compute a min cost flow [2] with a chosen cost function (historically people used dijkstra seach for single paths with the cost function representing the weights on the edges of the graph -which is what most folks currently still do). While [2] and I personally agree with you that the cost function should be a combination the two features fees and reliability (as in successprobability) Matt Corallo righfully pointed out [3] that other features might be chosen in the future to deliver more optimal results. For example implementations currently often use CLTV as a feature (which I honestly find horrible) and I am currently investigating if one could add latency of channels or - for known IP addresses - either the geo distance or IP distance. 2.) Combining features: This is the question that you are asking. Often people use a linear weighted sum to combine features. This is what often happens implicitly in neural networks. While this is often good enough and while it is often practical to either learn the weights or give users a choice there are many situation where the weighted linear sum does not work well with the selected features. An example for the weighted sum is the risk-factor in c-lightning that could have been used to decide if one wanted the dijkstra seach to either optimize for CLTV delta or for paid routing fees. Also in our paper [2] in which we discuss the same two features that you mentioned we explain how a linear sum of two features can be optimal due to the lagrangian bounding principle. However in practice (of machine learning) it has been shown that using the harmonic mean [4] between features often works very well without the necessity to learn a weight / parameter. This has for example been done when c-lightnign recently switched to probabilistic path finding [5]. In this thread you find a long discussion and evaluation how the harmonic mean outperformed the linear sum. I think the main issue that you address here is that there is no universal truth for situations like this. In practice only tests and experience will help us to make good decisions. with kind Regards Rene [0]: https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-March/002984.html [1]: https://en.wikipedia.org/wiki/Feature_engineering [2]: https://arxiv.org/abs/2107.05322 [3]: https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-September/003219.html [4]: https://en.wikipedia.org/wiki/Harmonic_mean [5]: https://github.com/ElementsProject/lightning/pull/4771 On Mon, Nov 15, 2021 at 4:26 PM Joost Jager wrote: > In Lightning pathfinding the two main variables to optimize for are > routing fee and reliability. Routing fee is concrete. It is the sat amount > that is paid when a payment succeeds. Reliability is a property of a route > that can be expressed as a probability. The probability that a route will > be successful. > > During pathfinding, route options are compared against each other. So for > example: > > Route A: fee 10 sat, success probability 50% > Route B: fee 20 sat, success probability 80% > > Which one is the better route? That depends on user preference. A patient > user will probably go for route A in the hope of saving on fees whereas for > a time-sensitive payment route B looks better. > > It would be great to offer this trade-off to the user in a simple way. > Preferably a single [0, 1] value that controls the selection process. At 0, > the route is only optimized for fees and probabilities are ignored > completely. At 1, the route is only optimized for reliability and fees are > ignored completely. > > But how to choose between the routes A and B for a value somewhere in > between 0 and 1? For example 0.5 - perfect balance between reliability and > fee. But what does that mean exactly? > > Anyone got an idea on how to approach this best? I am looking for a simple > formula to decide between routes, preferably with a reasonably sound > probability-theoretical basis (whatever that means). > > Joost > ___ > Lightning-dev mailing list > Lightning-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > -- https://www.rene-pickhardt.de ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Route reliability<->fee trade-off control parameter
Hi Joost, A quick way to resolve this is to normalize the payment fees to a [0,1] scale. Two natural ways to do this are the following. 0 in both of them is some maximum set by the user (maybe with some reasonable default), 1 could be either the cheapest path or simply 0 sat. Once we have normalized the fees to a [0,1] scale, we can proceed. Let [image: \alpha] be the chosen balance parameter, [image: f] the fee and [image: p] the success probability. Then the score of a channel will be [image: \alpha\cdot f + (1-\alpha)\cdot p] Clara On Mon, Nov 15, 2021 at 10:26 AM Joost Jager wrote: > In Lightning pathfinding the two main variables to optimize for are > routing fee and reliability. Routing fee is concrete. It is the sat amount > that is paid when a payment succeeds. Reliability is a property of a route > that can be expressed as a probability. The probability that a route will > be successful. > > During pathfinding, route options are compared against each other. So for > example: > > Route A: fee 10 sat, success probability 50% > Route B: fee 20 sat, success probability 80% > > Which one is the better route? That depends on user preference. A patient > user will probably go for route A in the hope of saving on fees whereas for > a time-sensitive payment route B looks better. > > It would be great to offer this trade-off to the user in a simple way. > Preferably a single [0, 1] value that controls the selection process. At 0, > the route is only optimized for fees and probabilities are ignored > completely. At 1, the route is only optimized for reliability and fees are > ignored completely. > > But how to choose between the routes A and B for a value somewhere in > between 0 and 1? For example 0.5 - perfect balance between reliability and > fee. But what does that mean exactly? > > Anyone got an idea on how to approach this best? I am looking for a simple > formula to decide between routes, preferably with a reasonably sound > probability-theoretical basis (whatever that means). > > Joost > ___ > Lightning-dev mailing list > Lightning-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
