Subject: Fee Budgets: A Possible Path Towards Unified Cost Functions For Lightning Pathfinding Problems
Introduction ============ What is the cost of a failed LN payment? Presumably, if a user wants to pay in exchange for something, that user values that thing higher than the Bitcoin they spend on that thing. This is a central assumption of free market economics, that all transactions are voluntary and that all participants in the transaction get more utility out of the transaction than what they put in. Note that ***value is subjective***. For example, a farmer values the food they sell less than the buyer of that food, because the farmer has leet farming skillz that actually let them **grow food** from literal shit, sunlight, and water, and presumably the buyer does not have those leet skillz0rs to convert literal shit to food using sunlight and water (otherwise they would be growing their own food). This applies for all production, given that you puny humans have such limited time to learn and train leet skillz. Thus, for a buyer, there is a difference in value between the product they are buying, and the BTC they are sacrificing to the elder gods (i.e. the payment network and the seller) in order to get the product. The buyer must value the product more than the BTC. This difference, then, is the cost of a failed payment. If the attempt to pay fails, then obviously the seller will not be willing to send the product (as it can receive no money for it) and the buyer loses the (buyer-subjective) value of the product minus the value of the BTC they wanted to use to pay. This difference in value, while subjective, is quantifiable (consider how judges at a beauty contest must convert their subjective judgment of beauty to a number; indeed, horny humans do this all the time at bars, suggesting that even judgment-impaired humans intuitively understand that subjective values can be quantified). And that quantifiable subjective value can be measured in units of bitcoin. Thus, this difference in value is the cost of failure of an LN payment. And due to the relationship of failure and success, the cost of failure is the value of success. Pickhardt-Richter Payments ========================== Why is the cost of failure/value of success even relevant? In [a 2021 paper](https://arxiv.org/abs/2107.05322) Pickhardt and Richter present a method of estimating the probability of payment success, and using that probability-of-success as a cost function for a generalization of pathfinding algorithms (specifically minimum cost flow). Of course, probabilities of success are not the only concern that actual pathfinding algorithms need to worry about. Another two concerns are: * Actual fees (measured in bitcoin units). * Actual total cltv-delta (measured in blocks). It is possible to convert total cltv-delta to a "Fee". Basically, the cost of the total cltv-delta is the value of your funds being locked and unuseable for that many blocks. This can be represented as an expected annual return on investment if those funds were instead locked into some investment. In C-Lightning this is the `riskfactor` parameter. This implies that total cltv-delta can be converted to an equivalent amount of BTCs. Now, the issue is, how can we convert probability of success to some equivalent amount of BTCs? This is why the value of success --- i.e. the cost of payment failure --- is relevant. By multiplying the cost of failure by the probability of failure, we can acquire a bitcoins-measured quantity that can be added directly to expected fees. Fee Budgets =========== Long ago, some weird rando with an unpronouncable name decided to add a "fee budget" to his implementation of C-Lightning pay algorithm (back when C-Lightning did not even have a `pay` algorithm). For some reason (possibly dark ritual), that rando managed to get that code into the actual C-Lightning, and the fee budget --- known as `maxfeepercent` --- has been retained to this day, even though none of the original code has survived (dark rituals tend to consume anything involved in their rites, I would not be surprised if that includes source code). Now consider --- how would a buyer assign a fee budget for a particular payment? As we noted, a rational buyer will only buy if they believe the value of the product being bought is higher than the value of the BTCs they sacrifice to buy that product. This difference is the cost of failure (equivalent to value of success). And a rational buyer will be willing to pay, as fee, any value up to this cost of failure/value of success. For example, if the buyer is not willing to pay more than half the cost of failure, then if there is no way to succeed payments at half the cost of failure, then the payment simply fails and the buyer loses the entire cost of failure. Logically, the buyer must be willing to pay, as fees, up to the cost of failure. Similarly, if the buyer is willing to pay up to twice the cost of failure, then if it succeeds only by paying up to twice the cost of failure, even if the payment pushes through and the buyer gets the product, the buyer still lost the cost of failure because it paid more fees than the value of the payment success was. Logically, then, the buyer must specify as fee budget, its expected value from acquiring the product minus the price of the product. Thus, it so happens that the fee budget is, in fact, the value of payment success/cost of payment failure, subjectively determined by the payer, quantified, and provided to the C-Lightning payment algorithm! Unified Cost Function ===================== The cost of failure is then: fee_budget * (1 - success_probability) The `fee_budget` is the above fee budget, an input from the user. `success_probability` is the estimate as determined using the Pickhardt-Richter algorithm. The cost of a channel that charges `fee` is: fee + fee_budget * (1 - success_probability) However, we should note that the above cost function is really the expected cost for the *entire payment*. In particular, `success_probability` is multiplicative along a path, whereas `fee` is additive. When we consider multipath payments, we should also observe that the `success_probability` of each sub-payment are multiplied together (since all sub-payments must succeed) while `fee` is again additive in nature. Because of this, there is probably no *existing* pathfinding algorithm which can actually *use* this cost function. Every pathfinding algorithm uses addition to compute total costs. The Pickhardt-Richter paper gets around this by using the logarithm of the probability. As addition of logarithms is equivalent to multiplication (`log A + log B = log (A * B)`), this converts the addition operations of existing pathfinding algos to multiplication of the probabilities. This technique cannot work with the above unified cost function, unfortunately. However, we can consider that, if we neglect `fee`, and use only the logarithms of the cost function, then the `fee_budget` term is effectively a constant cost for all channels on the network. That is, `log (fee_budget * success_probability) = log fee_budget + log success_probability` for all channels on the network, and we can subtract `log fee_budget` on all channels without changing the result of any pathfinding algorithms (provided we do not get into zero or negative costs). Thus, this instance of the Pickhard-Richter technique is equivalent to neglecting both the `fee` and the `fee_budget` in our unified cost function. Generalized `#zerobasefee` ========================== If `fee` is small compared to `fee_budget`, then we can consider the effect of the `fee` term to be negligible compared to `fee_budget` term. Here is how the above cost function looks like, with `fee_budget` distributed: fee + fee_budget - fee_budget * success_probability If `fee_budget` is very much higher than `fee` then we can neglect `fee` as an approximation. fee_budget - fee_budget * success_probability Since `fee_budget` is constant for all paths and for all channels, we can just use the negative logarithm of `success_probability` as the cost function. As a heuristic, we can *ignore* fees and just use nagetive log probability, as suggested in the Pickhardt-Richter paper, *after* pruning channels whose fees are very high (i.e. prune channels whose `fee`, say, exceeds 1% of the `fee_budget`). One way to view `#zerobasefee` is that this is a specialized instance of the above general heuristic, that we can prune channels with non-zero base fees in order to operate a pathfinding algorithm that uses only addition for edge costs and use negative log probability for edge costs. We can instead consider that *small enough* base fees, which are negligible compared to the `fee_budget`, should not be pruned, and not specifically that all non-zero base fees should be pruned. That is, `#zerobasefee` assumes that a 1-sat base fee is *not* negligible compared to the `fee_budget`. However, for large enough payments, the `fee_budget` may be large enough that a 1 satoshi base fee is actually negligible compared to the `fee_budget` term. This implies that `#zerobasefee` is a specific heuristic, one that potentially could be generalized. As a corollary, the higher `success_probability` is, the more small fees matter (since `success_probability` subtracts from `fee_budget`). And higher `success_probability` arises from larger channels in general. This leads to the counterintuition that larger channels should charge lower fees, since logically the `#lowbasefee` pruning level should be lower at higher `success_probability`. Alternative Pathfinding? ======================== As noted, practically every pathfinding algorithm assumes that costs along every edge are always added together. For quantities that must be multiplied --- such as probabilities --- we can use the logarithm trick to convert the addition to a multiplication. However, as noted, the unified cost function has quantities that, in order to combine, must be added (fees) and multiplied (probabilities). In essence, every pathfinding algorithm cannot use this unified cost function, as they assume cost functions that are trivially monoid. Or is it? For something like the family of pathfinding algorithms Greedy, A\*, and Dijkstra, the only operations needed on costs are: * Addition (actually, a monoidal operation). * Comparison. Rather than "add", perhaps a better term would be to "aggregate" the costs. class (Monoid type) where zero :: type `<*>` :: type -> type -> type -- laws where -- forall (a :: type) => zero <*> a = a -- forall (a :: type) => a <*> zero = a -- forall (a :: type, b :: type) => a <*> b = b <*> a -- forall (a :: type, b :: type, c :: type) => (a <*> b) <*> c = a <*> (b <*> c) In the above, `<*>` is an "aggregate" operation that replaces the simple addition `+` traditionally used in pathfinding algorithms. For typical numeric types, for example, you could derive an addition monoid or a multiplication monoid. We can consider a type that is both `Monoid` and `Ord`: -- This will be defined by an actual run of the -- pathfinding algorithm. feeBudget :: Integer feeBudget = undefined data UnifiedCost = UnifiedCost { fee :: Integer , successProbability :: Rational } -- addition instance (Monoid UnifiedCost) where zero = UnifiedCost { fee = 0 , successProbability = 0 } a <*> b = UnifiedCost { fee = fee a + fee b , successProbability = successProbability a * successProbability b } -- comparison computeCost :: UnifiedCost -> Rational computeCost c = toRational (fee c) + ( toRational feeBudget * (1.0 - successProbability c)) instance (Eq UnifiedCost) where a == b = computeCost a == computeCost b instance (Ord UnifiedCost) where compare a b = compare (computeCost a) (computeCost b) -- laws where -- forall (a :: UnifiedCost, b :: UnifiedCost) => a <*> b >= a -- forall (a :: UnifiedCost, b :: UnifiedCost) => a <*> b >= b -- -- laws could be checked with QuickCheck -- -- though we should ensure `0 <= successProbability <= 1` That type would work well to replace the type of the cost in the Dijkstra-A\*-Greedy family of algortihms; they only need comparison and a monoid operation, but the actual structure of the cost type is immaterial to the algorithm. In particular, `feeBudget` is constant for an entire run of pathfinding algorithms. The question is whether minimum cost flow algos could work with the above limited type. I probably need to go actually study those algos. _______________________________________________ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
