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