Re: [Lightning-dev] Fee Budgets: A Possible Path Towards Unified Cost Functions For Lightning Pathfinding Problems
Good morning Stefan, > Hi Zmn! That is some amazing lateral thinking you have been applying there. > I'm quite certain I haven't understood everything fully, but it has been > highly entertaining to read. Will have to give it a closer read when I get > some time. > > As a first impression, here are some preliminary observations: While I highly > like the Haskell-style datatype, and the algorithm we use does mostly use > Dijkstra pathfinding, I think what is really important in your definition is > the computeCost definition. This is what we would call the cost function > IIUC, and in order to be able to solve min-cost flow problems it generally > has to be separable and convex. I believe your datatype merely hides the fact > that it is neither. Well, it really depends on what min flow cost algorithms actually assume of the "numbers" being used. For instance, it is well known that the Dijkstra-A\*-Greedy family of algorithms do not handle "negative costs". What it really means is that the algorithms assume: a + b >= a a + b >= b This holds if `a` and `b` are naturals (0 or positive), but not if they are integers. 1 + -1 = 0, and 0 >= 1 is not true, thus the type for costs in those algorithms cannot be integer types, they have to be naturals. However if you restrict the type to naturals, `a + b >= a` holds, and thus Dijkstra and its family of algorithms work. Thus, if you are going to use Dijkstra-A\*-Greedy, you "only" need to have the following "operations": `+` :: Cost -> Cost -> Cost `<` :: Cost -> Cost -> Bool zero :: Cost With the following derived operations: a > b = b < a a >= b = not (a < b) a <= b = not (b < a) a == b = (a >= b) && (a <= b) a /= b = (a < b) || (a > b) And following the laws: forall (a :: Cost) => a + zero == a forall (a :: Cost) => zero + a == a forall (a :: Cost, b :: Cost) => a + b == b + a forall (a :: Cost, b :: Cost, c :: Cost) => (a + b) + c == a + (b + c) forall (a :: Cost, b :: Cost) => a + b >= a forall (a :: Cost, b :: Cost) => a + b >= b As a non-mathist I have no idea what "separable" and "convex" actually mean. Basic search for "convex" and "concave" tends to show up information in geometry, which I think is not related (though it is possible there is some extension of the geometric concept to pure number theory?). And definitions on "separable" are not understandable by me, either. What exactly are the operations involved, and what are the laws those operations must follow, for the data type to be "separable" and "convex" (vs."concave")? I guess my problem as well is that I cannot find easy-to-understand algorithms for min cost flow --- I can find discussions on the min cost flow "problem", and some allusions to solutions to that problem, but once I try looking into algorithms it gets quite a bit more complicated. Basically: do I need these operations? `*` :: Cost -> Cost -> Cost `/` :: Cost -> Cost -> Cost --- or Maybe Cost If not, then why cannot `type Cost = UnifiedCost`? For example, this page: https://www.topcoder.com/thrive/articles/Minimum%20Cost%20Flow%20Part%20Two:%20Algorithms Includes this pseudocode: Transform network G by adding source and sink Initial flow x is zero while ( Gx contains a path from s to t ) do Find any shortest path P from s to t Augment current flow x along P update Gx If "find any shortest path" is implemented using Dijkstra-A\*-Greedy, then that does not require `Cost` to be an actual numeric type, they just require a type that provides `+`, `<`, and `zero`, all of which follow the laws I pointed out, *and no more than those*. `UnifiedCost` follows those laws (tough note that my definition of `zero` has a bug, `successProbability` should be `1.0` not `0`). In short --- the output of the cost function is a `UnifiedCost` structure and ***not*** a number (in the traditional sense). Basically, I am deconstructing numbers here and trying to figure out what makes them tick, and seeing if I can use a different type to provide the "tick". Regards, ZmnSCPxj ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Lightning-dev Digest, Vol 72, Issue 18
The dust limit is required to prevent massive UTXO expansion. The details around miner incentives to process dust are irrelevant to this because there simply needs to be a buffer of friction to prevent spamming the UTXO set to be much, much larger, as an *attack* and long-term overhead on both storage size and resources in purposing UTXO data within applications/servers. Even if I were wrong, it is still silly to propose changing a thing no one actually needs or wants changed for any practical application. It ain't broke, don't fix it. On Fri, Aug 20, 2021 at 7:00 AM < lightning-dev-requ...@lists.linuxfoundation.org> wrote: > Send Lightning-dev mailing list submissions to > lightning-dev@lists.linuxfoundation.org > > To subscribe or unsubscribe via the World Wide Web, visit > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > or, via email, send a message with subject or body 'help' to > lightning-dev-requ...@lists.linuxfoundation.org > > You can reach the person managing the list at > lightning-dev-ow...@lists.linuxfoundation.org > > When replying, please edit your Subject line so it is more specific > than "Re: Contents of Lightning-dev digest..." > > > Today's Topics: > >1. Re: [bitcoin-dev] Removing the Dust Limit (Jeremy) > > > -- > > Message: 1 > Date: Thu, 19 Aug 2021 23:51:31 -0500 > From: Jeremy > To: Bitcoin Protocol Discussion > > Cc: lightning-dev > Subject: Re: [Lightning-dev] [bitcoin-dev] Removing the Dust Limit > Message-ID: > < > cad5xwhieda2kjf265idz1ism4afzh3s3d4cjsesvvknwv9l...@mail.gmail.com> > Content-Type: text/plain; charset="utf-8" > > one interesting point that came up at the bitdevs in austin today that > favors remove that i believe is new to this discussion (it was new to me): > > the argument can be reduced to: > > - dust limit is a per-node relay policy. > - it is rational for miners to mine dust outputs given their cost of > maintenance (storing the output potentially forever) is lower than their > immediate reward in fees. > - if txn relaying nodes censor something that a miner would mine, users > will seek a private/direct relay to the miner and vice versa. > - if direct relay to miner becomes popular, it is both bad for privacy and > decentralization. > - therefore the dust limit, should there be demand to create dust at > prevailing mempool feerates, causes an incentive to increase network > centralization (immediately) > > the tradeoff is if a short term immediate incentive to promote network > centralization is better or worse than a long term node operator overhead. > > > /// > > my take is that: > > 1) having a dust limit is worse since we'd rather not have an incentive to > produce or roll out centralizing software, whereas not having a dust limit > creates an mild incentive for node operators to improve utreexo > decentralizing software. > 2) it's hard to quantify the magnitude of the incentives, which does > matter. > -- next part -- > An HTML attachment was scrubbed... > URL: < > http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20210819/831b9608/attachment-0001.html > > > > -- > > Subject: Digest Footer > > ___ > Lightning-dev mailing list > Lightning-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > > > -- > > End of Lightning-dev Digest, Vol 72, Issue 18 > * > -- ~ John Carvalho Schedule: https://calendly.com/bitcoinerrorlog Chat: https://t.me/bitcoinerrorlog Social: https://twitter.com/bitcoinerrorlog ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Zero Fee Routing
How is this related to the youtube video posted? Can you link to a specific time in it where it is discussed? On Sun, 15 Aug 2021 at 00:30, Daki Carnhof wrote: > This text was brought to life by repelling magnet forces of reading > ZmnSCPxj's Algorithm For Channel Fee Settings. Thank you, Zmn! Bitcoin > has taught me to just do nothing and it would probably be preferable in > this case as well, but here is my 5msat. > > # Introduction > > Zero Fee Lightning Network Routing (both 0/0) is an alternative way of > looking at channel fee settings. The philosophical idea behind it is based > on the fact that by encouraging individuals to do their own (automated) fee > management we are actually forcing everyone individually to do the > decisions which are are currently done in fiat (and altcoin) standard > through interventions. And which we oppose by Bitcoin. > > # Reasoning > > See discussion with Jordan P. Peterson and guests at > https://www.youtube.com/embed/iVym9wtopqs > > Our computers are running anyway for the Bitcoin nodes. They do quite a > lot of simple computations for free* already. If it did not make sense, > the nodes would not be run. The same reasoning extends to zero fee routing > on LN. In our opinion it is much more straightforward to not ask for fees > on LN. The higher interest of the community will just melt into the overall > price, like Proof-of-Work does. Using an algorithm like Hill Climbing would > just make our computers compute even more and with uncertain results. > > * Without any immediate effect on the amount of satoshi the operator of > the node owns. > > That's it. If I Had More Time, I Would Have Written a Shorter Letter. > > Regards, > Daki > ___ > Lightning-dev mailing list > Lightning-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
