René Pickhardt [ARCHIVE] on Nostr: 📅 Original date posted:2021-08-26 📝 Original message: Dear fellow lightning ...
📅 Original date posted:2021-08-26
📝 Original message:
Dear fellow lightning developers,
with a mixture of shock and disbelief I have been following the (semi)
public discussions for the last 6 weeks and the reaction of some companies
/ people that reached out to me. I have to say I am really surprised by the
amount of hesitation that - despite obvious and overwhelming mathematical
evidence - a small group of people demonstrated in response to our
results. While I cannot make any sense of this I decided to post here
despite the fact that I believe everything that needed to be said is
already written and explained clearly in our paper [0] about optimally
reliable and cheap payment flows on the Lightning Network. My hope is that
this mail can help us to
* clarify a few misunderstandings
* stop having opinionated discussions about mathematical facts
* find a quick agreement on how to move on
As far as I can tell currently all implementations use some form of
Dijkstra algorithm in payment delivery with a strong emphasize on finding
paths with cheap fees. The reason seems to be that it is a well established
assumption that users would prefer a cheap solution on the market of
offered routing fees. (while routing nodes of course try to offer fees that
maximize their earnings)
If we look at the mentioned paper there are several results (I will soon
publish a separate mail here discussing some of the more interesting
results and consequences but I decided to split it and put this one here
first as it seemed to be more urgent). One of the results which I will
discuss now is the realization that - given the current fee function -
finding the cheapest payment flow is an NP-hard problem because the fee
function is neither linear nor convex.
Our fee function is `f(x) = rx + b` where `r`= fee rate, `b`=base fee and
`x` is the amount we want to send.
As we thought it was obvious that the function is not linear we only
explained in the paper how the jump from f(0)=0 to f(1) = ppm+base_fee
breaks convexity. But as the question came up several times (for example
here [1]) I want to stress that the fee function - despite looking like a
straight line - is **not linear**. While writing this post I realized that
the issue might be that the concept of linearity [2] from the field of
linear algebra seems to be intermixed in the english language and American
school system with the concept of linear polynomials / linear functions
[3]. So maybe that is part of the problem that emerged in previous
discussions.
When I write linear here I am referring back to the concept of linearity
from linear algebra (c.f.: [2]) which btw seems to be also the main reason
why schnorr signatures [2b] are so powerful that everyone is happy they
will find their way into bitcoin. We know that a necessary condition for a
function to be called linear is that the following property holds:
f(x+y)=f(x)+f(y)
however if we look at our setting we see that:
f(x+y) = r(x+y) + b
and
f(x)+f(y) = rx+b + ry+b = r(x+y) + 2b
equality (and thus linearity) only holds if
r(x+y)+b = r(x+y) + 2b <==> b = 2b
the later is true if and only if `b=0`. In other words: **Our current fee
function is only linear if we set the base fee to zero.**
On the other side we refer to research in our paper that shows that an
optimal solution (in this case optimal means cheapest) cannot be found if
the fee function is neither linear nor convex. I think one of the biggest
misunderstandings that I saw in the discussions is that people seem to have
thought this has something to do with our new / proposed method. But as far
as I can tell it does absolutely not have any connection to it. Instead and
as most of you probably know the property to be an NP-hard problem is
completely independent of the used algorithm. This is why in the paper we
suggested to drop the base_fee and mentioned in the German Podcast that the
same effect could already be achieved by node operators today by setting
their base fee to 0. it is also the reason why we asked before we published
the paper why the base fee was introduced and what purpose it served [4].
I am so surprised by some of the resistance because some of the biggest
talking points by Lightning Network critics in the past have been that
routing is either not solved or if it was solved it would be NP-hard. In
our paper we show that delivering a payment can always be modeled as a min
cost flow and the resulting optimization problem will indeed be NP-hard
depending on the cost function. Given the current fee function with a non
zero base fee and the goal of minimizing fees that is followed by all
implementations I have to agree with such critics and say yes, in that
particular case delivering a payment optimally is an NP-hard problem.
Luckily there are things we can do about it:
1.) we can decide to have a different optimization goal. For example in the
Paper we used a previously introduced probabilisitic model that optimizes
for reliability instead of fees and we show that in that case the function
is convex and a polynomial exact algorithm is known and exists.
2.) If we want to optimize for fees which - given current implementations
for single payments and the overwhelming feedback of users - seems to be
the case we can modify the fee function to be either convex or linear. As
everyone who read until here knows the later can be achieved by just
removing the base fee.
3.) Of course we can follow the ideas of Matt Corallo and Olaoluwa
Osuntokun to do more research. I mean there is a nice 1 million dollar
bounty [5] for the person who finds a polynomial solution to NP-hard
problems or proofs that such solutions cannot be found in polynomial time
(which if you ask me personally is way more probable to happen but I
usually try not to make wild conjectures about the future).
4.) We can try to find linear approximations so that we can have more
efficient algorithms to approximate such problems which I guess is what
Matt and Olaoluwa might have meant when they suggested to do more research.
As I was struggeling with the problem for over two years I personally have
a pretty strong opinion about the 4 potentials paths:
@1: We already describe in the paper that reliability should be included
when deciding which channels to use while fees should not be neglected.
Thus I tend to say: Yes let's modify the goal in a way that we still keep
optimizing for cheap delivery which by the end means keep a fee function
but NOT the current fee function.
@2: Seems like a total no-brainer to modify the fee function to drop the
base fee because I believe nobody wants to drop the cheap requirement for
payments and because of what I will say in reply to 3 & 4.
@3: If you want to find solutions to hard problems I suggest to find a
solution to the discrete logarithm instead of studying P=NP. The bounty is
the the security of bitcoin and thus much higher than just the million
dollar that you might get for the the solution to the P=NP problem. Ok,
jokes aside of course doing research is always a good idea and we laid out
a clear roadmap for further R&D in the paper that still holds even if we
all agree that zerobasefee is a good thing. I am still seeking funding from
the bitcoin / lightning network community to be able to continue research
and development in this field so I full appreciate the suggestion by Matt
and Olaoluwa who asked for more research and I hope the community will
entrust me to lead such research. I can understand that people hesitated to
support my work back in 2019 when I decided to focus on the reliability
question and it was a gamble if I could deliver but I sincerely hope with
my achievements that I lay out in full on https://ln.rene-pickhardt.de that
there will be more support in the future (not only for me).
@4: People in operation research have tried this for many years. In
practice problems are being linearized all the time. But in the best case
the models are already chosen to be linear and one hopes that such models
are close enough to reality. We have been given a gift that the uncertainty
in our channels naturally came as a convex cost function which makes the
reliability goal somewhat easy to compute. More importantly it is a huge
gift that it is just for us (users and developers) to decide how we want to
have the fee structure on the Lightning network. A linear solution could
just be agreed upon / recommended but of course we can keep a non-linear
version and struggle around with approximations to handle np-hardness. For
me it is so obvious what one would want to do that I will conclude with the
subject line of this mail as a rethorical question "Do we really want users
to solve an NP-hard problem when they wish to find a cheap way of paying
each other on the Lightning Network?"
In the recent Optech newsletter [6] Olaoluwa Osuntokun is said to have
"emphasized a point made earlier that there’s no clear current need for
node operators to change a parameter today for a new pathfinding algorithm
that nobody is currently ready to use in production". First of all I want
to emphasize that Stefan and I have used this in production and have
verified that our method works - as predicted in the paper - much better
than the pay implementation used in LND (I will write more about that in
the other mail that I already mentioned) But way more importantly (and as
explained in this mail and our paper) this parameter change is not about
some novel algorithm that we propose but rather about the mathematical
structure of the optimization problem that we want(?) users to face when
delivering payments (and that all implementations already presented to the
users in the single path payment case). So I very strongly disagree with
the statement that there is no clear need to change something. Actually I
think there is an exceptionally strong need to change something and very
good reason to do so rather sooner than later.
That being said the high reliability and large amounts that we could
deliver through the use of our method with a standard min convex cost flow
solver as the algorithm comes from the fact that we used probablistic path
finding [7] as the cost function. As demonstrated last march this already
works much better for single paths when used as a weight in dijsktra than
the stuff current implementations do. Also it did not create such a
discussion when I shared the results about probabilisitic pathfinding last
march and already mentioned that I only need to finish the work on optimal
splitting. So for the higher reliability and larger amounts alone that our
method can do, we do not even need a zerobasefee. This is because
probabilistic path finding merely models the uncertainty of the liquidity
in the channels to decide which channels to use with what amounts in
payment delivery to maximize the success probability. The only reason why
we mention (zerobase)fees is because of @1 and the assumption that node
operators would arbitrarily increase their fees on channels if we would not
take fees into consideration when deciding which channels to use. Since the
basefee kicks in and breaks the nice mathematical properties we addressed
it.
Btw I have a suggestion to node operators who seek channel partners and
nodes with whom to open channels. If you don't want your customers / users
be required to solve or approximate NP-hard problems you could open your
channels with other nodes who already support zero base fee on their
channels. As of now this seems to be a clear indicator that those nodes
care about reliability and try to provide a good & honest service to the
network. As more and more wallets should use optimal payment flows it is
also reasonable to expect that a lot of routing is likely to happen in the
#zerobasefee part of the network which is already pretty large [8]. At
least when I make a payment this part of the network is where I look first
to deliver the payment. Also connecting to nodes that indicate via
zerobasefee that they care seems at least to me personally way more
reasonable than following some random intransparent score that assigns
numbers to nodes.
As said initially I thought I already had said everything which is why -
unless substential new information comes up - I will most likely not engage
into further bike shedding discussions on the zero base fee discussions.
This is now for the community to decide and not for me to argue.
with kind regards Rene
[0]: https://arxiv.org/abs/2107.05322
[1]:
https://bitcoin.stackexchange.com/questions/108018/would-a-min-fee-setting-for-lightning-channels-make-sense#comment124039_108325
[2]: https://en.wikipedia.org/wiki/Linearity
[2b]:
https://courses.csail.mit.edu/6.857/2020/projects/4-Elbahrawy-Lovejoy-Ouyang-Perez.pdf
[3]: https://en.wikipedia.org/wiki/Linear_function
[4]:
https://bitcoin.stackexchange.com/questions/107311/why-was-the-base-fee-for-the-routing-fee-calculation-of-the-lightning-network-in
[5]:
https://en.wikipedia.org/wiki/P_versus_NP_problem#Results_about_difficulty_of_proof
[6]: https://bitcoinops.org/en/newsletters/2021/08/25/
[7]:
https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-March/002984.html
[8]: https://lnrouter.app/graph/zero-base-fee
--
https://www.rene-pickhardt.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20210826/7fde2220/attachment-0001.html>;
📝 Original message:
Dear fellow lightning developers,
with a mixture of shock and disbelief I have been following the (semi)
public discussions for the last 6 weeks and the reaction of some companies
/ people that reached out to me. I have to say I am really surprised by the
amount of hesitation that - despite obvious and overwhelming mathematical
evidence - a small group of people demonstrated in response to our
results. While I cannot make any sense of this I decided to post here
despite the fact that I believe everything that needed to be said is
already written and explained clearly in our paper [0] about optimally
reliable and cheap payment flows on the Lightning Network. My hope is that
this mail can help us to
* clarify a few misunderstandings
* stop having opinionated discussions about mathematical facts
* find a quick agreement on how to move on
As far as I can tell currently all implementations use some form of
Dijkstra algorithm in payment delivery with a strong emphasize on finding
paths with cheap fees. The reason seems to be that it is a well established
assumption that users would prefer a cheap solution on the market of
offered routing fees. (while routing nodes of course try to offer fees that
maximize their earnings)
If we look at the mentioned paper there are several results (I will soon
publish a separate mail here discussing some of the more interesting
results and consequences but I decided to split it and put this one here
first as it seemed to be more urgent). One of the results which I will
discuss now is the realization that - given the current fee function -
finding the cheapest payment flow is an NP-hard problem because the fee
function is neither linear nor convex.
Our fee function is `f(x) = rx + b` where `r`= fee rate, `b`=base fee and
`x` is the amount we want to send.
As we thought it was obvious that the function is not linear we only
explained in the paper how the jump from f(0)=0 to f(1) = ppm+base_fee
breaks convexity. But as the question came up several times (for example
here [1]) I want to stress that the fee function - despite looking like a
straight line - is **not linear**. While writing this post I realized that
the issue might be that the concept of linearity [2] from the field of
linear algebra seems to be intermixed in the english language and American
school system with the concept of linear polynomials / linear functions
[3]. So maybe that is part of the problem that emerged in previous
discussions.
When I write linear here I am referring back to the concept of linearity
from linear algebra (c.f.: [2]) which btw seems to be also the main reason
why schnorr signatures [2b] are so powerful that everyone is happy they
will find their way into bitcoin. We know that a necessary condition for a
function to be called linear is that the following property holds:
f(x+y)=f(x)+f(y)
however if we look at our setting we see that:
f(x+y) = r(x+y) + b
and
f(x)+f(y) = rx+b + ry+b = r(x+y) + 2b
equality (and thus linearity) only holds if
r(x+y)+b = r(x+y) + 2b <==> b = 2b
the later is true if and only if `b=0`. In other words: **Our current fee
function is only linear if we set the base fee to zero.**
On the other side we refer to research in our paper that shows that an
optimal solution (in this case optimal means cheapest) cannot be found if
the fee function is neither linear nor convex. I think one of the biggest
misunderstandings that I saw in the discussions is that people seem to have
thought this has something to do with our new / proposed method. But as far
as I can tell it does absolutely not have any connection to it. Instead and
as most of you probably know the property to be an NP-hard problem is
completely independent of the used algorithm. This is why in the paper we
suggested to drop the base_fee and mentioned in the German Podcast that the
same effect could already be achieved by node operators today by setting
their base fee to 0. it is also the reason why we asked before we published
the paper why the base fee was introduced and what purpose it served [4].
I am so surprised by some of the resistance because some of the biggest
talking points by Lightning Network critics in the past have been that
routing is either not solved or if it was solved it would be NP-hard. In
our paper we show that delivering a payment can always be modeled as a min
cost flow and the resulting optimization problem will indeed be NP-hard
depending on the cost function. Given the current fee function with a non
zero base fee and the goal of minimizing fees that is followed by all
implementations I have to agree with such critics and say yes, in that
particular case delivering a payment optimally is an NP-hard problem.
Luckily there are things we can do about it:
1.) we can decide to have a different optimization goal. For example in the
Paper we used a previously introduced probabilisitic model that optimizes
for reliability instead of fees and we show that in that case the function
is convex and a polynomial exact algorithm is known and exists.
2.) If we want to optimize for fees which - given current implementations
for single payments and the overwhelming feedback of users - seems to be
the case we can modify the fee function to be either convex or linear. As
everyone who read until here knows the later can be achieved by just
removing the base fee.
3.) Of course we can follow the ideas of Matt Corallo and Olaoluwa
Osuntokun to do more research. I mean there is a nice 1 million dollar
bounty [5] for the person who finds a polynomial solution to NP-hard
problems or proofs that such solutions cannot be found in polynomial time
(which if you ask me personally is way more probable to happen but I
usually try not to make wild conjectures about the future).
4.) We can try to find linear approximations so that we can have more
efficient algorithms to approximate such problems which I guess is what
Matt and Olaoluwa might have meant when they suggested to do more research.
As I was struggeling with the problem for over two years I personally have
a pretty strong opinion about the 4 potentials paths:
@1: We already describe in the paper that reliability should be included
when deciding which channels to use while fees should not be neglected.
Thus I tend to say: Yes let's modify the goal in a way that we still keep
optimizing for cheap delivery which by the end means keep a fee function
but NOT the current fee function.
@2: Seems like a total no-brainer to modify the fee function to drop the
base fee because I believe nobody wants to drop the cheap requirement for
payments and because of what I will say in reply to 3 & 4.
@3: If you want to find solutions to hard problems I suggest to find a
solution to the discrete logarithm instead of studying P=NP. The bounty is
the the security of bitcoin and thus much higher than just the million
dollar that you might get for the the solution to the P=NP problem. Ok,
jokes aside of course doing research is always a good idea and we laid out
a clear roadmap for further R&D in the paper that still holds even if we
all agree that zerobasefee is a good thing. I am still seeking funding from
the bitcoin / lightning network community to be able to continue research
and development in this field so I full appreciate the suggestion by Matt
and Olaoluwa who asked for more research and I hope the community will
entrust me to lead such research. I can understand that people hesitated to
support my work back in 2019 when I decided to focus on the reliability
question and it was a gamble if I could deliver but I sincerely hope with
my achievements that I lay out in full on https://ln.rene-pickhardt.de that
there will be more support in the future (not only for me).
@4: People in operation research have tried this for many years. In
practice problems are being linearized all the time. But in the best case
the models are already chosen to be linear and one hopes that such models
are close enough to reality. We have been given a gift that the uncertainty
in our channels naturally came as a convex cost function which makes the
reliability goal somewhat easy to compute. More importantly it is a huge
gift that it is just for us (users and developers) to decide how we want to
have the fee structure on the Lightning network. A linear solution could
just be agreed upon / recommended but of course we can keep a non-linear
version and struggle around with approximations to handle np-hardness. For
me it is so obvious what one would want to do that I will conclude with the
subject line of this mail as a rethorical question "Do we really want users
to solve an NP-hard problem when they wish to find a cheap way of paying
each other on the Lightning Network?"
In the recent Optech newsletter [6] Olaoluwa Osuntokun is said to have
"emphasized a point made earlier that there’s no clear current need for
node operators to change a parameter today for a new pathfinding algorithm
that nobody is currently ready to use in production". First of all I want
to emphasize that Stefan and I have used this in production and have
verified that our method works - as predicted in the paper - much better
than the pay implementation used in LND (I will write more about that in
the other mail that I already mentioned) But way more importantly (and as
explained in this mail and our paper) this parameter change is not about
some novel algorithm that we propose but rather about the mathematical
structure of the optimization problem that we want(?) users to face when
delivering payments (and that all implementations already presented to the
users in the single path payment case). So I very strongly disagree with
the statement that there is no clear need to change something. Actually I
think there is an exceptionally strong need to change something and very
good reason to do so rather sooner than later.
That being said the high reliability and large amounts that we could
deliver through the use of our method with a standard min convex cost flow
solver as the algorithm comes from the fact that we used probablistic path
finding [7] as the cost function. As demonstrated last march this already
works much better for single paths when used as a weight in dijsktra than
the stuff current implementations do. Also it did not create such a
discussion when I shared the results about probabilisitic pathfinding last
march and already mentioned that I only need to finish the work on optimal
splitting. So for the higher reliability and larger amounts alone that our
method can do, we do not even need a zerobasefee. This is because
probabilistic path finding merely models the uncertainty of the liquidity
in the channels to decide which channels to use with what amounts in
payment delivery to maximize the success probability. The only reason why
we mention (zerobase)fees is because of @1 and the assumption that node
operators would arbitrarily increase their fees on channels if we would not
take fees into consideration when deciding which channels to use. Since the
basefee kicks in and breaks the nice mathematical properties we addressed
it.
Btw I have a suggestion to node operators who seek channel partners and
nodes with whom to open channels. If you don't want your customers / users
be required to solve or approximate NP-hard problems you could open your
channels with other nodes who already support zero base fee on their
channels. As of now this seems to be a clear indicator that those nodes
care about reliability and try to provide a good & honest service to the
network. As more and more wallets should use optimal payment flows it is
also reasonable to expect that a lot of routing is likely to happen in the
#zerobasefee part of the network which is already pretty large [8]. At
least when I make a payment this part of the network is where I look first
to deliver the payment. Also connecting to nodes that indicate via
zerobasefee that they care seems at least to me personally way more
reasonable than following some random intransparent score that assigns
numbers to nodes.
As said initially I thought I already had said everything which is why -
unless substential new information comes up - I will most likely not engage
into further bike shedding discussions on the zero base fee discussions.
This is now for the community to decide and not for me to argue.
with kind regards Rene
[0]: https://arxiv.org/abs/2107.05322
[1]:
https://bitcoin.stackexchange.com/questions/108018/would-a-min-fee-setting-for-lightning-channels-make-sense#comment124039_108325
[2]: https://en.wikipedia.org/wiki/Linearity
[2b]:
https://courses.csail.mit.edu/6.857/2020/projects/4-Elbahrawy-Lovejoy-Ouyang-Perez.pdf
[3]: https://en.wikipedia.org/wiki/Linear_function
[4]:
https://bitcoin.stackexchange.com/questions/107311/why-was-the-base-fee-for-the-routing-fee-calculation-of-the-lightning-network-in
[5]:
https://en.wikipedia.org/wiki/P_versus_NP_problem#Results_about_difficulty_of_proof
[6]: https://bitcoinops.org/en/newsletters/2021/08/25/
[7]:
https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-March/002984.html
[8]: https://lnrouter.app/graph/zero-base-fee
--
https://www.rene-pickhardt.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20210826/7fde2220/attachment-0001.html>;