Matt Corallo [ARCHIVE] on Nostr: 📅 Original date posted:2021-11-17 📝 Original message: Yep, this is roughly the ...
📅 Original date posted:2021-11-17
📝 Original message:
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 <joost.jager at gmail.com <mailto:joost.jager at 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
📝 Original message:
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 <joost.jager at gmail.com <mailto:joost.jager at 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>