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 _______________________________________________ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
