[Lightning-dev] Fee Budgets: A Possible Path Towards Unified Cost Functions For Lightning Pathfinding Problems

[ZmnSCPxj]

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.