ZmnSCPxj [ARCHIVE] on Nostr: 📅 Original date posted:2021-08-20 📝 Original message: Good morning Stefan, > > ...
📅 Original date posted:2021-08-20
📝 Original message:
Good morning Stefan,
> > A reason why I suggest this is that the cost function in actual implementation is *already* IMO overloaded.
> >
> > In particular, actual implementations will have some kind of conversion between cltv-delta and fees-at-node.
>
> That's an interesting aspect. Would this lead to a constant per edge if incorporated in the cost function? If so, this would lead to another generally hard problem, which, again, needs to be explored more in the concrete cases we have here to see if we can still solve/approximate it.
No, because each edge defines its own cltv-delta.
>
> > However, I think that in practice, most users cannot intuitively understand `riskfactor`.
>
> I don't think they have to. Only people like you who write actual software probably need to.
***I*** do not intuitively understand it either. (^^;)
I understand it with system 2 (expected return on investment if you were investing the money instead of having it locked due to node failure along a path) but my system 1 just goes "hmmm whut" and I just use the default, which I *hope* cdecker chose rationally.
> > Similarly, I think it is easier for users to think in terms of "fee budget" instead.
> >
> > Of course, algorithms should try to keep costs as low as possible, if there are two alternate payment plans that are both below the fee budget, the one with lower actual fee is still preferred.
> > But perhaps we should focus more on payment success *within some fee and timelock budget*.
> >
> > Indeed, as you point out, your real-world experiments you have done have involved only probability as cost.
> > However, by the paper you claim to have sent 40,000,000,000msat for a cost of 814,000msat, or 0.002035% fee percentage, far below the 0.5% default `maxfeepercent` we have, which I think is fairly reasonable argument for "let us ignore fees and timelocks unless it hits the budget".
> > (on the other hand, those numbers come from a section labelled "Simulation", so that may not reflect the real world experiments you had --- what numbers did you get for those?)
>
> René is going to publish those results very soon.
>
> Regarding payment success *within some fee and timelock budget*: the situation is a little more complex than it appears. As you have pointed out, at the moment, most of the routes are very cheap (too cheap, IMHO), so you have to be very unlucky to hit an expensive flow. So in the current environment, your approach seems to work pretty well, which is also why we first thought about it.
>
> Unfortunately, as you know, we have to think adversarially in this domain. And it is clear that if we simply disregarded fees in routing, people would try to take advantage of this. If we just set a fee budget, and try again if it is missed, then I see some problems arise: First, what edges do you exclude in the next try? Where is that boundary? Second, I am pretty sure an adversary could design a DOS vector in this way by forcing people to go through exponentially many min-cost flow rounds (which are not cheap anyway) excluding only few edges per round.
>
> Indeed, if you read the paper closely you will have seen that this kind of problem (optimizing for some cost while staying under a budget for a second cost) is (weakly) np-hard even for the single path case. So there is some intuition that this is not as simple as you might imagine it. I personally think that the Lagrangian style of combining the costs in a linear fashion is very promising, but you might be successful with more direct methods as well.
>
> > Is my suggestion not reasonable in practice?
> > Is the algorithm runtime too high?
>
> See above. I don't know, but I believe it would be hard to make safe against adversaries. Including the fees in the cost function appears to be the more holistic approach to me, since min-cost flow algorithms always give you a globally optimized answer.
Hah, yes, adversarial.
I may have a route towards a unified cost function, will clean up a write up and post in a little while on a new thread.
Regards,
ZmnSCPxj
📝 Original message:
Good morning Stefan,
> > A reason why I suggest this is that the cost function in actual implementation is *already* IMO overloaded.
> >
> > In particular, actual implementations will have some kind of conversion between cltv-delta and fees-at-node.
>
> That's an interesting aspect. Would this lead to a constant per edge if incorporated in the cost function? If so, this would lead to another generally hard problem, which, again, needs to be explored more in the concrete cases we have here to see if we can still solve/approximate it.
No, because each edge defines its own cltv-delta.
>
> > However, I think that in practice, most users cannot intuitively understand `riskfactor`.
>
> I don't think they have to. Only people like you who write actual software probably need to.
***I*** do not intuitively understand it either. (^^;)
I understand it with system 2 (expected return on investment if you were investing the money instead of having it locked due to node failure along a path) but my system 1 just goes "hmmm whut" and I just use the default, which I *hope* cdecker chose rationally.
> > Similarly, I think it is easier for users to think in terms of "fee budget" instead.
> >
> > Of course, algorithms should try to keep costs as low as possible, if there are two alternate payment plans that are both below the fee budget, the one with lower actual fee is still preferred.
> > But perhaps we should focus more on payment success *within some fee and timelock budget*.
> >
> > Indeed, as you point out, your real-world experiments you have done have involved only probability as cost.
> > However, by the paper you claim to have sent 40,000,000,000msat for a cost of 814,000msat, or 0.002035% fee percentage, far below the 0.5% default `maxfeepercent` we have, which I think is fairly reasonable argument for "let us ignore fees and timelocks unless it hits the budget".
> > (on the other hand, those numbers come from a section labelled "Simulation", so that may not reflect the real world experiments you had --- what numbers did you get for those?)
>
> René is going to publish those results very soon.
>
> Regarding payment success *within some fee and timelock budget*: the situation is a little more complex than it appears. As you have pointed out, at the moment, most of the routes are very cheap (too cheap, IMHO), so you have to be very unlucky to hit an expensive flow. So in the current environment, your approach seems to work pretty well, which is also why we first thought about it.
>
> Unfortunately, as you know, we have to think adversarially in this domain. And it is clear that if we simply disregarded fees in routing, people would try to take advantage of this. If we just set a fee budget, and try again if it is missed, then I see some problems arise: First, what edges do you exclude in the next try? Where is that boundary? Second, I am pretty sure an adversary could design a DOS vector in this way by forcing people to go through exponentially many min-cost flow rounds (which are not cheap anyway) excluding only few edges per round.
>
> Indeed, if you read the paper closely you will have seen that this kind of problem (optimizing for some cost while staying under a budget for a second cost) is (weakly) np-hard even for the single path case. So there is some intuition that this is not as simple as you might imagine it. I personally think that the Lagrangian style of combining the costs in a linear fashion is very promising, but you might be successful with more direct methods as well.
>
> > Is my suggestion not reasonable in practice?
> > Is the algorithm runtime too high?
>
> See above. I don't know, but I believe it would be hard to make safe against adversaries. Including the fees in the cost function appears to be the more holistic approach to me, since min-cost flow algorithms always give you a globally optimized answer.
Hah, yes, adversarial.
I may have a route towards a unified cost function, will clean up a write up and post in a little while on a new thread.
Regards,
ZmnSCPxj