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

2021-08-30 Thread René Pickhardt via Lightning-dev
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

2021-08-30 Thread Stefan Richter
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

2021-08-30 Thread 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 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,