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 thin
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 v
