{"type":"rich","version":"1.0","author_name":"npub1g5zswf6y48f7fy90jf3tlcuwdmjn8znhzaa4vkmtxaeskca8hpss23ms3l","author_url":"https://nostr.ae/npub1g5zswf6y48f7fy90jf3tlcuwdmjn8znhzaa4vkmtxaeskca8hpss23ms3l","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2021-08-20\n📝 Original message:\nSubject: Fee Budgets: A Possible Path Towards Unified Cost Functions For Lightning Pathfinding Problems\n\nIntroduction\n============\n\nWhat is the cost of a failed LN payment?\n\nPresumably, if a user wants to pay in exchange for something,\nthat user values that thing higher than the Bitcoin they spend\non that thing.\nThis is a central assumption of free market economics, that\nall transactions are voluntary and that all participants in\nthe transaction get more utility out of the transaction than\nwhat they put in.\n\nNote that ***value is subjective***.\nFor example, a farmer values the food they sell less than\nthe buyer of that food, because the farmer has leet farming\nskillz that actually let them **grow food** from literal shit,\nsunlight, and water, and presumably the buyer does not have\nthose leet skillz0rs to convert literal shit to food\nusing sunlight and water (otherwise they would be growing\ntheir own food).\nThis applies for all production, given that you puny humans\nhave such limited time to learn and train leet skillz.\n\nThus, for a buyer, there is a difference in value between\nthe product they are buying, and the BTC they are sacrificing\nto the elder gods (i.e. the payment network and the seller) in\norder to get the product.\nThe buyer must value the product more than the BTC.\n\nThis difference, then, is the cost of a failed payment.\nIf the attempt to pay fails, then obviously the seller\nwill not be willing to send the product (as it can receive\nno money for it) and the buyer loses the (buyer-subjective)\nvalue of the product minus the value of the BTC they wanted\nto use to pay.\n\nThis difference in value, while subjective, is quantifiable\n(consider how judges at a beauty contest must convert\ntheir subjective judgment of beauty to a number; indeed,\nhorny humans do this all the time at bars, suggesting that\neven judgment-impaired humans intuitively understand that\nsubjective values can be quantified).\nAnd that quantifiable subjective value can be measured in\nunits of bitcoin.\n\nThus, this difference in value is the cost of failure of an\nLN payment.\nAnd due to the relationship of failure and success, the\ncost of failure is the value of success.\n\nPickhardt-Richter Payments\n==========================\n\nWhy is the cost of failure/value of success even relevant?\n\nIn [a 2021 paper](https://arxiv.org/abs/2107.05322)\nPickhardt and Richter present a method of estimating\nthe probability of payment success, and using that\nprobability-of-success as a cost function for a\ngeneralization of pathfinding algorithms (specifically\nminimum cost flow).\n\nOf course, probabilities of success are not the only\nconcern that actual pathfinding algorithms need to\nworry about.\nAnother two concerns are:\n\n* Actual fees (measured in bitcoin units).\n* Actual total cltv-delta (measured in blocks).\n\nIt is possible to convert total cltv-delta to a \"Fee\".\nBasically, the cost of the total cltv-delta is the value\nof your funds being locked and unuseable for that many\nblocks.\nThis can be represented as an expected annual return on\ninvestment if those funds were instead locked into some\ninvestment.\nIn C-Lightning this is the `riskfactor` parameter.\n\nThis implies that total cltv-delta can be converted\nto an equivalent amount of BTCs.\n\nNow, the issue is, how can we convert probability of\nsuccess to some equivalent amount of BTCs?\n\nThis is why the value of success --- i.e. the cost\nof payment failure --- is relevant.\n\nBy multiplying the cost of failure by the probability\nof failure, we can acquire a bitcoins-measured\nquantity that can be added directly to expected fees.\n\nFee Budgets\n===========\n\nLong ago, some weird rando with an unpronouncable name\ndecided to add a \"fee budget\" to his implementation of\nC-Lightning pay algorithm (back when C-Lightning did not\neven have a `pay` algorithm).\nFor some reason (possibly dark ritual), that rando managed\nto get that code into the actual C-Lightning, and the\nfee budget --- known as `maxfeepercent` --- has been\nretained to this day, even though none of the original\ncode has survived (dark rituals tend to consume anything\ninvolved in their rites, I would not be surprised if\nthat includes source code).\n\nNow consider --- how would a buyer assign a fee budget\nfor a particular payment?\n\nAs we noted, a rational buyer will only buy if they\nbelieve the value of the product being bought is higher\nthan the value of the BTCs they sacrifice to buy that\nproduct.\nThis difference is the cost of failure (equivalent to\nvalue of success).\n\nAnd a rational buyer will be willing to pay, as fee,\nany value up to this cost of failure/value of success.\n\nFor example, if the buyer is not willing to pay more\nthan half the cost of failure, then if there is no\nway to succeed payments at half the cost of failure,\nthen the payment simply fails and the buyer loses\nthe entire cost of failure.\nLogically, the buyer must be willing to pay, as\nfees, up to the cost of failure.\n\nSimilarly, if the buyer is willing to pay up to twice\nthe cost of failure, then if it succeeds only by\npaying up to twice the cost of failure, even if the\npayment pushes through and the buyer gets the product,\nthe buyer still lost the cost of failure because it\npaid more fees than the value of the payment success\nwas.\n\nLogically, then, the buyer must specify as fee budget,\nits expected value from acquiring the product minus\nthe price of the product.\n\nThus, it so happens that the fee budget is, in fact,\nthe value of payment success/cost of payment failure,\nsubjectively determined by the payer, quantified, and\nprovided to the C-Lightning payment algorithm!\n\nUnified Cost Function\n=====================\n\nThe cost of failure is then:\n\n    fee_budget * (1 - success_probability)\n\nThe `fee_budget` is the above fee budget, an input\nfrom the user.\n`success_probability` is the estimate as determined\nusing the Pickhardt-Richter algorithm.\n\nThe cost of a channel that charges `fee` is:\n\n    fee + fee_budget * (1 - success_probability)\n\nHowever, we should note that the above cost function\nis really the expected cost for the *entire\npayment*.\nIn particular, `success_probability` is multiplicative\nalong a path, whereas `fee` is additive.\n\nWhen we consider multipath payments, we should also\nobserve that the `success_probability` of each\nsub-payment are multiplied together (since all\nsub-payments must succeed) while `fee` is again\nadditive in nature.\n\nBecause of this, there is probably no *existing*\npathfinding algorithm which can actually *use*\nthis cost function.\nEvery pathfinding algorithm uses addition\nto compute total costs.\n\nThe Pickhardt-Richter paper gets around this by\nusing the logarithm of the probability.\nAs addition of logarithms is equivalent to\nmultiplication (`log A + log B = log (A * B)`),\nthis converts the addition operations of\nexisting pathfinding algos to multiplication of the\nprobabilities.\n\nThis technique cannot work with the above unified\ncost function, unfortunately.\n\nHowever, we can consider that, if we neglect\n`fee`, and use only the logarithms of the cost\nfunction, then the `fee_budget` term is\neffectively a constant cost for all channels on\nthe network.\nThat is, `log (fee_budget * success_probability) =\nlog fee_budget + log success_probability`\nfor all channels on the network, and we can\nsubtract `log fee_budget` on all channels\nwithout changing the result of any pathfinding\nalgorithms (provided we do not get into zero or\nnegative costs).\nThus, this instance of the Pickhard-Richter\ntechnique is equivalent to neglecting both the\n`fee` and the `fee_budget` in our unified cost\nfunction.\n\nGeneralized `#zerobasefee`\n==========================\n\nIf `fee` is small compared to `fee_budget`, then\nwe can consider the effect of the `fee` term to\nbe negligible compared to `fee_budget` term.\n\nHere is how the above cost function looks like,\nwith `fee_budget` distributed:\n\n    fee + fee_budget - fee_budget * success_probability\n\nIf `fee_budget` is very much higher than `fee`\nthen we can neglect `fee` as an approximation.\n\n    fee_budget - fee_budget * success_probability\n\nSince `fee_budget` is constant for all paths and\nfor all channels, we can just use the negative\nlogarithm of `success_probability` as the cost\nfunction.\n\nAs a heuristic, we can *ignore* fees and\njust use nagetive log probability, as suggested\nin the Pickhardt-Richter paper, *after* pruning\nchannels whose fees are very high (i.e. prune\nchannels whose `fee`, say, exceeds 1% of the\n`fee_budget`).\n\nOne way to view `#zerobasefee` is that this is\na specialized instance of the above general\nheuristic, that we can prune channels with\nnon-zero base fees in order to operate a\npathfinding algorithm that uses only addition\nfor edge costs and use negative log probability\nfor edge costs.\n\nWe can instead consider that *small enough*\nbase fees, which are negligible compared to\nthe `fee_budget`, should not be pruned, and\nnot specifically that all non-zero base fees\nshould be pruned.\nThat is, `#zerobasefee` assumes that a 1-sat\nbase fee is *not* negligible compared to the\n`fee_budget`.\n\nHowever, for large enough payments, the\n`fee_budget` may be large enough that a 1\nsatoshi base fee is actually negligible\ncompared to the `fee_budget` term.\nThis implies that `#zerobasefee` is a\nspecific heuristic, one that potentially\ncould be generalized.\n\nAs a corollary, the higher `success_probability`\nis, the more small fees matter (since\n`success_probability` subtracts from `fee_budget`).\nAnd higher `success_probability` arises from\nlarger channels in general.\nThis leads to the counterintuition that\nlarger channels should charge lower fees,\nsince logically the `#lowbasefee` pruning level\nshould be lower at higher `success_probability`.\n\nAlternative Pathfinding?\n========================\n\nAs noted, practically every pathfinding algorithm\nassumes that costs along every edge are always\nadded together.\n\nFor quantities that must be multiplied --- such\nas probabilities --- we can use the logarithm\ntrick to convert the addition to a multiplication.\n\nHowever, as noted, the unified cost function\nhas quantities that, in order to combine, must\nbe added (fees) and multiplied (probabilities).\n\nIn essence, every pathfinding algorithm cannot\nuse this unified cost function, as they assume\ncost functions that are trivially monoid.\n\nOr is it?\n\nFor something like the family of pathfinding\nalgorithms Greedy, A\\*, and Dijkstra, the only\noperations needed on costs are:\n\n* Addition (actually, a monoidal operation).\n* Comparison.\n\nRather than \"add\", perhaps a better term\nwould be to \"aggregate\" the costs.\n\n    class (Monoid type) where\n         zero :: type\n         `\u003c*\u003e` :: type -\u003e type -\u003e type\n         -- laws where\n         --     forall (a :: type) =\u003e zero \u003c*\u003e a = a\n         --     forall (a :: type) =\u003e a \u003c*\u003e zero = a\n         --     forall (a :: type, b :: type) =\u003e a \u003c*\u003e b = b \u003c*\u003e a\n         --     forall (a :: type, b :: type, c :: type) =\u003e (a \u003c*\u003e b) \u003c*\u003e c = a \u003c*\u003e (b \u003c*\u003e c)\n\nIn the above, `\u003c*\u003e` is an \"aggregate\" operation\nthat replaces the simple addition `+` traditionally\nused in pathfinding algorithms.\nFor typical numeric types, for example, you could\nderive an addition monoid or a multiplication\nmonoid.\n\nWe can consider a type that is both `Monoid`\nand `Ord`:\n\n    -- This will be defined by an actual run of the\n    -- pathfinding algorithm.\n    feeBudget :: Integer\n    feeBudget = undefined\n\n    data UnifiedCost = UnifiedCost { fee :: Integer\n                                   , successProbability :: Rational\n                                   }\n\n    -- addition\n    instance (Monoid UnifiedCost) where\n        zero = UnifiedCost { fee = 0\n                           , successProbability = 0\n                           }\n        a \u003c*\u003e b = UnifiedCost { fee = fee a + fee b\n                              , successProbability = successProbability a\n                                                   * successProbability b\n                              }\n\n    -- comparison\n    computeCost :: UnifiedCost -\u003e Rational\n    computeCost c = toRational (fee c)\n                  + ( toRational feeBudget\n                    * (1.0 - successProbability c))\n    instance (Eq UnifiedCost) where\n        a == b = computeCost a == computeCost b\n    instance (Ord UnifiedCost) where\n        compare a b = compare (computeCost a) (computeCost b)\n\n    -- laws where\n    --    forall (a :: UnifiedCost, b :: UnifiedCost) =\u003e a \u003c*\u003e b \u003e= a\n    --    forall (a :: UnifiedCost, b :: UnifiedCost) =\u003e a \u003c*\u003e b \u003e= b\n    -- -- laws could be checked with QuickCheck\n    -- -- though we should ensure `0 \u003c= successProbability \u003c= 1`\n\nThat type would work well to replace the type of the\ncost in the Dijkstra-A\\*-Greedy family of algortihms;\nthey only need comparison and a monoid operation, but\nthe actual structure of the cost type is immaterial\nto the algorithm.\n\nIn particular, `feeBudget` is constant for an entire\nrun of pathfinding algorithms.\n\nThe question is whether minimum cost flow algos\ncould work with the above limited type.\nI probably need to go actually study those algos."}