📅 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
>
Matt Corallo [ARCHIVE] /
npub1e4…jxmcu
2023-06-09 15:04:26
in reply to nevent1q…mudu
Author Public Key
npub1e46n428mcyfwznl7nlsf6d3s7rhlwm9x3cmkuqzt3emmdpadmkaqqjxmcuPublished at
2023-06-09 15:04:26Event JSON
{
"id": "4d4a8ef14a42de6c47d0db8250d84516838a5d947bb481c37cf8d73ec72dbf4b",
"pubkey": "cd753aa8fbc112e14ffe9fe09d3630f0eff76ca68e376e004b8e77b687adddba",
"created_at": 1686315866,
"kind": 1,
"tags": [
[
"e",
"ff2b02f52b6bf2ba44fad040ebd04a11cbcc61fa7b8b2822e2b9132801128989",
"",
"root"
],
[
"e",
"857ef0b93ddbab62b9e3941573ee4cba19d25d3980a78b1e34b1f8ffd3536c97",
"",
"reply"
],
[
"p",
"2a67fa9c85955362b9fd51ebb032020693c0873f0054bc192f847df2d3ac6af9"
]
],
"content": "📅 Original date posted:2021-11-17\n📝 Original message:\nYep, this is roughly the direction we've gone in LDK - an abstract interface that gives you some \ninformation about a channel and you return \"I'm willing to pay up to X msats to avoid routing over \nthat channel as specified\".\n\nIt's obviously not perfect in the sense that it won't generate the absolute optimal route given the \nparameters, but it can do pretty well (after some additional fixes we'd like to land) and at least \noptimizes for something the user controls.\n\nSadly, of course, all of this requires a good model for failure probability, something we don't yet \nhave, so we rely on some naive guesses in our default code, and let the user plug in a more advanced \nmodel if they prefer. Long-term we'll probably add more intelligence, as others (or at least \nc-lightning) have done.\n\nMatt\n\nOn 11/15/21 14:44, Joost Jager wrote:\n\u003e One direction that I explored is to start with a statement by the user in this form:\n\u003e \n\u003e \"If there is a route with a success probability of 50%, then I am willing to pay up to 1.8x the \n\u003e routing fee for an alternative route that has a 80% success probability\"\n\u003e \n\u003e I like this because it isn't an abstract weight or factor. It is actually clear what this means.\n\u003e \n\u003e What I didn't yet succeed in is to find a model where I can plug in 50%, 80% and 1.8x and \n\u003e generalizes it to arbitrary inputs A% and B%. But it seems to me that there must be some \n\u003e probabilistic equation / law / rule / theorem / ... that can support this.\n\u003e \n\u003e Joost.\n\u003e \n\u003e On Mon, Nov 15, 2021 at 4:25 PM Joost Jager \u003cjoost.jager at gmail.com \u003cmailto:joost.jager at gmail.com\u003e\u003e \n\u003e wrote:\n\u003e \n\u003e In Lightning pathfinding the two main variables to optimize for are routing fee and reliability.\n\u003e Routing fee is concrete. It is the sat amount that is paid when a payment succeeds. Reliability\n\u003e is a property of a route that can be expressed as a probability. The probability that a route\n\u003e will be successful.\n\u003e \n\u003e During pathfinding, route options are compared against each other. So for example:\n\u003e \n\u003e Route A: fee 10 sat, success probability 50%\n\u003e Route B: fee 20 sat, success probability 80%\n\u003e \n\u003e Which one is the better route? That depends on user preference. A patient user will probably go\n\u003e for route A in the hope of saving on fees whereas for a time-sensitive payment route B looks better.\n\u003e \n\u003e It would be great to offer this trade-off to the user in a simple way. Preferably a single [0,\n\u003e 1] value that controls the selection process. At 0, the route is only optimized for fees and\n\u003e probabilities are ignored completely. At 1, the route is only optimized for reliability and fees\n\u003e are ignored completely.\n\u003e \n\u003e But how to choose between the routes A and B for a value somewhere in between 0 and 1? For\n\u003e example 0.5 - perfect balance between reliability and fee. But what does that mean exactly?\n\u003e \n\u003e Anyone got an idea on how to approach this best? I am looking for a simple formula to decide\n\u003e between routes, preferably with a reasonably sound probability-theoretical basis (whatever that\n\u003e means).\n\u003e \n\u003e Joost\n\u003e \n\u003e \n\u003e _______________________________________________\n\u003e Lightning-dev mailing list\n\u003e Lightning-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev\n\u003e",
"sig": "dc42986de64d9ce5cc37447d4e079bcc3bd57a9a052657feb9383db95719cd50c223d0316dfda0ad13f85226f2c13ab99b340f247bd33ea4767f89890ca4b4c9"
}