### Re: [Lightning-dev] Handling nonzerobasefee when using Pickhard-Richter algo variants

Dear ZmnSCPxj, thank you very much for this mail and in particular the openess to tinker about a protocol change with respect to the transport layer of HTLCs / PTLCs! I fully agree that we should think about adopting our onion transport layer in a way that supports local payment splits and merges to resemble the flowing nature of payments more closely! While an update for that might be tricky I think right now is a perfect moment for such discussions as we kind of need a full upgrade anyway when going to PTLCs (which in fact might even be helpful with a local splittling / merging logic as secrets would be additive / linear) Before I elaborate let me state a few things and correct an error in your mail about the convex nature of the fee function and the problems of the min-cost flow solver. I agree with you (and AJ) that there is a problem in the base fee that comes from overpaying when dissecting a flow into paths which share a channel. However this is not related to the convexity issue. In a recent mail [0] I conductd the calculation demonstrating why the current fee function f(x)=x*r+b is not even linear (every linear function should be convex). As described in the paper the problem is for the min cost flow solving algorithms if the cost-function (in that case the fee function) is neither linear nor convex. The issue that breaks convexity is really subtle here and comes when going from 0 flow to some flow. In that sense I apologize that the paper might be slightly misleading in its presentation. While convexity is often checked with the second derivative argument our function is in fact defined on integers and thus not even differentiable which is why the argument with the second derivative that we use to show the convexity of the negative log probabilities is not transferable. Let us better go with the wikipedia definition of convexity [1] that states: "In mathematics, a real-valued function is called convex if the line segment between any two points on the graph of the function lies above the graph between the two points." So how you would test convexity is by making sure that for any two values x_1 and x_2 the line connecting the points (x_1,f(x_1)) and (x_2,f(x_2)) lies above all other points (x,f(x)) for x \in {x_1, , x_2}. In our case because f(0)=0 and f(2)=2r+b The line connecting those two points is defined by l(x)=((2r+b)/2)*x = (r+b/2)*x which means that l(1)=r+b/2. however f(1) = r+ b which is larger than l(1) for any positive value of b. (Note that again with a zerobasefee b=0 we have f(1)=r=l(1) which would be sufficient) If you implement the capacity scaling algorithm for a min-cost flow solver you will see that the algorithm linearizes the convex costs all the time by switching to a unit cost in each delta-scaling phase (as described in section 9, 10.2 and 14.1 through 14.5 of the book [2] that we refer to in the paper and that Stefan already mentioned to you). This seems very ismilar to the thoughts you seemed to have in your mail (though even after reading them 3 times I can't verify how you turned the base_fee into a proportional term by switching to a unisized payment amount). You will also recognize that the base fee is not linearizable as a unit cost and will break the reduced cost optimality criterium in the delta phases of the algorithm. That being said in our mainnet tests we actually used 10k and 100k sats as a fixed min unit size for htlcs in flow computation but more about that in the already announced and soon to come mail about the mainnet tests. Long story short while the base fee yields indeed a problem for a flow to be dissected into paths the issues seems to be much more severe because of this non continious jump when going from f(0) to f(1). All that being said I am very delighted to see that you propose a protocol change towards "whole flow payments" (Please allow me to still call them payment flows as our paper title suggested). In my recent mail [0] I said I would want to write another mail about our mainnet test results and the the consequences for the protocol, node operators, users etc... One of the consequences goes fully along with the idea that you described here and thus I very much like / appreciate your idea / proposal! As the other mail was too long anyway let me quickly copy and past the text about the 5 consequences for the protocol that I saw from my draft and note that the second one goes fully along with your proposal: Consequences for the Protocol 1.) As we send larger amounts we confirmed what many people already knew: Stuck and hanging HTLCs are becoming more of a problem. The main reason that in our experiments we could not deliver the full amount was that we "lost" htlcs as they did neither arrive at the destination in time nor did they return as errors to the sender quickly enough before the mpp timeout. We very very much need a cancable payment mechanism [3]. I know taproot and PTLCs are coming but I

### Re: [Lightning-dev] Handling nonzerobasefee when using Pickhard-Richter algo variants

Hi Zmn! While you have some interesting thoughts about the implementation of min-cost flow based routing, I feel that there are at least two grave misunderstandings here: First, the problem with the base-fee or any similar constant is that they make the fee function concave at the point where the flow increases from 0 to 1. That is, there is a jump from 0 to base-fee+1*prop_fee or similar, and the function does increase slower from there. This is the case for any function that includes a constant per edge that is only paid IF there is non-zero flow along that edge. Second, while there might be additional problems in the disect-phase (which I am sure can be handled by a plethora of techniques), the fact remains that the min-cost flow problem itself is NP-hard when the cost-function is of this form. I realise that this is a fairly theoretical term, so let me shortly describe what it means: We know (there is a simple mathematical proof for this, see reference in our paper) that if we could find an algorithm that solves the min-cost flow problem ON ALL GRAPHS for all cost-functions of this form (basically, a constant per edge) in polynomial time, we could then use this algorithm to solve ANY problem in NP in polynomial time. This means, we would have an algorithm that can find a solution to any problem in polynomial time whose solutions can be VERIFIED in polynomial time. Because there are thousands of problems of this kind that the smartest people in the world have tried to solve for decaded without success (and just one success would be enough to solve all of them!), it is highly doubtful that such an algorithm exists. That is why we can be fairly certain that we cannot in general solve the min-cost flow problem for concave functions in polynomial time. HOWEVER, this does not mean that in practice it isn't possible to find good solutions for the subset of problems we are likely to encounter in our application. It might be that the LN-graph is of a certain structure that makes finding a solution easier. It is certain that we do not need the optimal solution at all and approximations will be easier to find. All we know is that we do know how to solve the problem generally for convex functions, and that we are very confident that we cannot in general solve it optimally for concave functions. Cheers Stefan Am Mo., 30. Aug. 2021 um 12:58 Uhr schrieb ZmnSCPxj via Lightning-dev : > > Good morning list, > > It seems to me that the cost function defined in Pickhard-Richter > can in fact include a base fee: > > -log(success_probability) + fudging_factor * amount * prop_fee + > fudging_factor * base_fee > > (Rant: why do mathists prefer single-symbol var names, in software > engineering there is a strong injunction **against** single-char > var names, with exceptions for simple numeric iteration loop vars, > I mean keeping track of the meaning of each single-symbol var name > takes up working memory space, which is fairly limited on a wetware > CPU, which is precisely why in software engineering there is an > injunction against single-char var names, srsly.) > > It seems to me that the above is "convex", as the `fudging_factor` > for a run will be constant, and the `base_fee` for the channel > would also be constant, and since it seems to me, naively, that > the paper defines "convex" as "the second derivative >= 0 for all > `amount`", and since the derivative of a constant is 0, the above > would still remain convex. > (I am not a mathist and this conjecture might be completely asinine.) > > So, it seems to me that the *real* reason for `#zerobasefee` is > not that the **mincostflow** algorithm cannot handle non-zero `base_fee`, > but rather, the **disect** phase afterwards cannot handle non-zero > `base_fee`. > > For example, suppose the minflowcost algorithm were instructed to > deliver 3,000msat from `S` to `D`, and returned the following flow: > > S -->3000--> A ->1000-> B > | | > |1000 > | v > +-->2000-> C ->3000-> D > > In the "disect" phase afterwards, the above flow solution would have > to be split into two sub-payments, a 1000 sub-payment `S-A-B-C-D` > and a 2000 sub-payment `S-A-C-D`. > > However, this does mean that the base cost for `C->D` and `S->A` in > the above flow will pay *twice* the base cost than what the above > cost function would have computed, because in reality two independent > payments pass through those channels. > > Thus, the current Pickhardt-Richter scheme cannot work with non-zero > base fees if it were modified to consider fees, but not due to the > mincostflow algorithm, rather because due to the disect algorithm. > > ### Converting Non-Zero Base Fees To Proportional Fees > > An alternative solution would be to optimize for a *maximum* fee > rather than optimize for the *exact* fee. > > We can do this by virtually splitting up the entire payment into > smaller bunches of

### [Lightning-dev] Handling nonzerobasefee when using Pickhard-Richter algo variants

Good morning list, It seems to me that the cost function defined in Pickhard-Richter can in fact include a base fee: -log(success_probability) + fudging_factor * amount * prop_fee + fudging_factor * base_fee (Rant: why do mathists prefer single-symbol var names, in software engineering there is a strong injunction **against** single-char var names, with exceptions for simple numeric iteration loop vars, I mean keeping track of the meaning of each single-symbol var name takes up working memory space, which is fairly limited on a wetware CPU, which is precisely why in software engineering there is an injunction against single-char var names, srsly.) It seems to me that the above is "convex", as the `fudging_factor` for a run will be constant, and the `base_fee` for the channel would also be constant, and since it seems to me, naively, that the paper defines "convex" as "the second derivative >= 0 for all `amount`", and since the derivative of a constant is 0, the above would still remain convex. (I am not a mathist and this conjecture might be completely asinine.) So, it seems to me that the *real* reason for `#zerobasefee` is not that the **mincostflow** algorithm cannot handle non-zero `base_fee`, but rather, the **disect** phase afterwards cannot handle non-zero `base_fee`. For example, suppose the minflowcost algorithm were instructed to deliver 3,000msat from `S` to `D`, and returned the following flow: S -->3000--> A ->1000-> B | | |1000 | v +-->2000-> C ->3000-> D In the "disect" phase afterwards, the above flow solution would have to be split into two sub-payments, a 1000 sub-payment `S-A-B-C-D` and a 2000 sub-payment `S-A-C-D`. However, this does mean that the base cost for `C->D` and `S->A` in the above flow will pay *twice* the base cost than what the above cost function would have computed, because in reality two independent payments pass through those channels. Thus, the current Pickhardt-Richter scheme cannot work with non-zero base fees if it were modified to consider fees, but not due to the mincostflow algorithm, rather because due to the disect algorithm. ### Converting Non-Zero Base Fees To Proportional Fees An alternative solution would be to optimize for a *maximum* fee rather than optimize for the *exact* fee. We can do this by virtually splitting up the entire payment into smaller bunches of value, and asking mincostflow to solve individual bunches rather than individual msats. For example, we can decide that the smallest practical HTLC would be 1000 msat. Let us call this the "payment unit", and the mincostflow algo solves for paying in these payment units instead of 1msat units. (Actual implementations would need to have some heuristic or reasoned rule-of-thumb assumption on what the smallest practical HTLC would be.) In our example, suppose we need to send 2001msat from `S` to `D`, with the payment unit being 1000 msat. Then we would actually have the mincostflow algorithm work to deliver 3 payment units (3 * 1000msat) from `S` to `D`. Let us suppose that the mincostflow algorithm returns the following flow: S -->3-> A ->1> B | | |1 | | v +-->2> C ->3> D Actually, what the mincostflow algorithm uses as a cost function would be: -log(success_probability) + fudging_factor * amount * prop_fee * payment_unit + fudging_factor * base_fee * amount == -log(success_probability) + fudging_factor * amount * (prop_fee * payment_unit + base_fee) where: amount is in units of 1000msat, our smallest practical HTLC. payment_unit is the unit, i.e. 1000msat. What the above means is that the mincostflow algorithm *allocates* `3 * base_fee` for `C->D`, since the `amount` flowing through `C->D` would be 3. However, when we pass the above flow to the disect algorithm, it would actually only split this into 2 sub-payments, so the actual payment plan would only pay `2 * base_fee` for the `C->D` leg on both sub-payments. In short, this effectively converts the base fee to a proportional fee, removing the zerobasfee requirement imposed by the disect algorithm. That is, the cost computed by the mincostflow algorithm is really a maximum cost budget that the subsequent disect algorithm could later spend. In effect, this converts the base fee to a proportional fee. This may be acceptable in practice. This approximation has a bias against non-zerobasefee --- it would treat those channels as being far more expensive than they actually would end up being in an *actual* payment attempt --- but at least does not *require* zerobasefee. It would be able to still use non-zerobasefee channels if those are absolutely required to reach the destination. This should at least help create a practical payment algorithm that handles current LN with nonzerobasefee,