Revamp feesetting and rebalancing heuristics

[ZmnSCPxj]

Had a long and fruitful email conversation with @devastgh, here are some summaries of what we think would be useful.

The main thrust here is to approach better some dieal of economic rationality.

• Getting the median of incoming feerates to the peer as the
  starting point for our own feerate seems fairly weak.
  While median is more resistant to outliers than the mean,
  we could instead use a "corrected" average that is more
  explicitly resistant against outliers:
  • First take a normal weighted average of all peers of the
    peer.
  • Then determine the standard deviation.
  • Redo the weighted average, but skip all channels whose
    feerates are above 3 standard deviations from the mean,
    and channels whose feerates are below the 3 standard
    deviations from the mean.
• EarningsRebalancer is nice and all, but it is willing to
  consume the entire earnings on rebalances, which translates
  to not earning money at all.
  Instead, it should compute X% of the current earnings, and
  only become willing to spend on rebalance up to that amount.
  Then (100% - X%) is the expected net earnings in the long
  run of the node operator.
  • X% was initially proposed as 80% with the ability to
    specify the amount via --clboss- or a lightning-cli
    command; for example a larger node might want a lower
    target, while a smaller node might not even be able to
    rebalance unless it uses a higher target.
    However, we should really avoid configuration!
  • My counterproposal: we can start at 80%, but move this
    depending on FundsMover results.
    If the FundsMover outright fails, we can try raising
    this target value (but only up to a maximum --- 99%?).
    If the FundsMover succeeds, we can try reducing this
    target value.
    Over time, we can try randomly reducing the target
    value as well, speculatively increasing our earnings.
    A new module would have to be built that holds this in
    the database.
• JitRebalancer seems good, it could also use the above
  rebalancing budget target as well (currently it uses a
  hardcoded rebalancing budget target).
• InitialRebalancer definitely deserves to be removed
  from CLBOSS and the hard disk it is on must be burned and
  then exorcised and then the ashes scattered into deep space
  as a protection against invading aliens who, we hope, end
  up running it and losing all their money before they can
  invade.
• FeeModderBySize is probably a dumb idea and can probably
  be outright disabled.
• We may need to overhaul the feemodder system, which
  currently solicits single multipliers from multiple modules.
• Instead, consider a single fee-setting module.
  • If the balance drops below some Y% on our side, switch to
    "by-balance" mode and jack up the fees, with the fees
    rising exponentially as we approach 0% on our side.
    • Alternate thought: the so-called "balance" is really the
      supply of a particular good, i.e. liquidity.
      We can consider the economic-theory relationship of price
      vs. supply with a certain fixed demand, on the assumption
      that the global demand for the good is relatively constant
      over time, and jack up the prices as our supply of the
      good drops (and if we happen to get more goods, also lower
      the supply --- this may explain why the feeadjuster can be
      reasonably good at earning funds).
      Given this, we might think that the FeeModderByPriceTheory
      is really discovering the demand, and the
      FeeModderByBalance is setting the feerate according to
      the demand divided by the supply.
  • Otherwise, use a different fee-setting algorithm (more
    details below).
• The current FeeModderByPriceTheory naively neglects the
  simple fact that liquidity we send out has to be replenished
  somehow, either by "passive rebalancing" by jacking the fees
  once we run out, or by active rebalancing via
  EarningsRebalancer.
  Thus, it would be biased towards low fees that do not charge
  enough per forward to compensate for the inevitable rebalancing
  you need to perform later.
  • In retrospect this reflects the idea that the forwarding
    node business is really in the business of aggregating
    payments.
    It facilitates multiple smaller payments (and probably
    earning mostly via the base fee) and then makes a single
    large payment (the rebalance) that aggregates the smaller
    payment.
  • The proposal was to score based on the fee earned per
    msatoshi forwarded, instead of the raw fee.
  • My counterproposal: the cost of future rebalancing is
    that: a cost.
    Correct accounting requires that it be deducted from the
    gross income.
    Raw earned fee is the gross income.
    We can estimate the cost of future rebalancing: we can
    try a bunch of getroutes from our node to the channel
    and average out the cost of the route in order to get
    some measure of "millisatoshis lost per millisatoshi
    rebalanced"; and once we have any rebalances, we can
    use that historical data for estimation.
    Then the score used by the learning algorithm should be
    earned_fee - estimated_cost_of_rebalance, i.e. the
    expected net income once the inevitable future rebalance
    is factored in.
    • More precisely, we consider a single large rebalance
      that is a good bit larger than the forward, and
      take the proportion of the forward vs expected
      rebalance and use only that proportion for the fees
      of the forward, on the assumption that in the future
      we will make fewer rebalances than the forwards we
      actually serve.
  • Tweak: if the learning algorithm finds the score of a
    particular forward is negative, this implies we have
    undercharged the user.
    It should abort the current learning round (i.e.
    discard all the cards) and recreate a new learning
    round which does not include the current card (i.e.
    set the center higher so the spread does not include
    the current card), and also immediately trigger a
    recalc of the feerate for the outgoing channel to keep
    our loss down.
    If price-theory is more integrated to the fee setting
    algorithm (i.e. it does not just emit a single real
    multiplier as it currently does now) it could also
    pre-estimate feerates which simply will give negative
    net income if a forward of a particular "standard
    value" is seen, and automatically arrange for cards
    with feerates higher than that.
  • Tweak: If in a learning round, none of the cards get
    positive score, decrement the center.
• The current step range of the FeeModderByPriceTheory
  seems large.
  • The reason is, this is a learning algorithm and it
    takes time for it to settle.
    Larger steps make it reach the optimum faster.
  • However, the large step range means that it may
    dominate over the tiny (100% - X%) that is reflected
    in the rebalance budget.
  • Instead, we can consider a smaller step, but also
    implement a typical heuristic for hill-climbing
    algorithms like FeeModderByPriceTheory: mostly do
    small steps, but insert a random card with a large
    step every now and then, to give a chance to escape
    local maxima (which will not exist given the
    economics of optimum price theory) and to speed up
    discovery of the global optima (the large step has
    some chance of being much better than any of the
    small steps).

[ZmnSCPxj]

Concrete coding thoughts:

• New Boss::Mod::RebalanceBudgetManager.
  • Keep track of a single number in the db, initialized to 0.8.
  • Whenever a FundsMover attempt fails, increase this number but never higher than 0.99.
  • Periodically, say at the twice-daily, optimistically reduce this number but never lower than say 0.5
  • Rebalancers should not budget more than this number times the earnings, minus the expenditures: (number * earnings) - expenditures, if the result is 0 or negative then we should not rebalance at all.
  • As a convenience, provide Request/ResponseGetRebalanceBudget which takes the source and destination nodes (either may be nullptr) and returns an Ln::Amount that is the maximum feebudget for the rebalance, which may be 0 if rebalancing is impractical.
    • Edit: add a "tweak" argument, a signed integer. Take the raw multiplier and convert it to log-ratio log(p / (1 - p)) add the tweak, then convert back to multiplier with exp(n) / (1 + exp(n)). Rebalancer is supposed to make a positive tweak to signal "strong" pressure to rebalance, negative for "weak" pressure to rebalance, possibly by basing on actual current balance. Or just query the balance ourself?
    • Evaluate source using in earnings and in expenditures, evaluate destination using out earnings and out expenditures, give the lower of the budgets between them.
    • If the result was negative, consider also bumping up the budget percentage.
• New Boss::Mod::RebalanceCostEstimator
  • Estimates the cost of rebalancing.
  • Keeps track of any successful FundsMover events, looking at actual cost of rebalance vs size of value rebalanced, keeping such events in the db from the past 1 week or so.
  • Provide Request/ResponseEstimateRebalanceCost, which takes an outgoing node and an amount, and returns the prorated estimated cost to rebalance that amount later.
  • If there are at least 10 (?) successful events, just take the average of the %fees of the events. Otherwise, simulate using getroute how much it would take to rebalance to the outgoing node, and add these simulations to any recorded successful events to augment the data. If fuzzpercent still worked it would be good to (ab)use it to simulate random network conditions, but NOOOO, they disabled it without even deprecating it or documenting the disablement, sigh..
• New Stats::CorrectedMean which does the average-filter-average dance.

[ZmnSCPxj]

A few more insights from additional discussion with @devastgh:

• We can roughly classify activity on the network into two things:
  • Actual economic payments: need to be FAST and RELIABLE, so okay to overpay fees a little.
  • Rebalances: need to be CHEAP to preserve our funds, so okay to fail and take a long time.
• We can think of forwarders as similar to makers in JoinMarket / Teleport:
  • Takers in JoinMarket / Teleport pay for privacy via an explicit payment to makers.
  • Makers in JoinMarket / Teleport pay for privacy via keeping their funds ready in a JoinMarket / Teleport wallet and waiting for a long time.
• Similarly, normal economic payments on LN are like takers, they want the service (in the LN case, payments) RIGHT NOW and are willing to pay to the waiting existing forwarding node network for speedy, reliable delivery of payments. Forwarding nodes are like makers because they keep their funds in various channels, ready to be used by actual economic actors.
• Thus, while we expect rebalances to be UNLIKELY (i.e. most surviving paths will be expensive), we should still try to rebalance (but with a strict limit on allowable fee paid!) over time.

[pira]

Nice proposals; would like to add couple points about proposed fee modder logic. The fee should grow for new channels as our liquidity is drained in case we opened a channel to a liquidity sink (double from initial for every halving of our side?), but it should also aggressively retract for any returned liquidity. Not sure what the good function here would be, but if the channel starts returning liquidity it has the potential of becoming a real workhorse self-balancing channel and should not be choked.

Absolute goal should be to have a channel where our fees ~match the peers fee If the sent and returned amounts are similar, grow the fees until the flow stops in a liquidity sink channels, and drop the fees to ~zero for liquidity provider channels.

[devastgh]

Absolute goal should be to have a channel where our fees ~match the peers fee If the sent and returned amounts are similar, grow the fees until the flow stops in a liquidity sink channels, and drop the fees to ~zero for liquidity provider channels.

I'm not so sure about that. I mean that feemodderbybalance should be active when our outbound liquidity is depleting, that's a given. If our outbound is lower on a channel, than our ideal outbound:inbound ratio we should overprice it. That means that if traffic still happens after that, we have a better chance to actively rebalance, since we sold liqudity overpriced. I did price some of my sources to 0 fee as an experiment. Now some traffic goes that way, but it comes back fast. And it almost always uses one of my cheap routes, mostly traffic happens between my 0 fee routes... A better strategy might be to not let any incoming traffic escape our node cheap, like 150-300ppm minimum depending on channel size. So if traffic happens from this source type channels, we're making enough on the outgoing part, that it's possible for us to rebalance the source channel economically. This will slow down routing, but probably keep our node and channels in a more ideal shape. From a node standpoint if we have no inbound from source channels, that means we have no/less outbound on some other channels.

[pira]

by having small fee on a source channel you are replenishing it while also getting more outbound capacity on other, more expensive, channels. that should help converge towards 50-50 balanced channels.

I am trying to put my instinct into formulae and it is not easy! But I would definitely lower fees on a bidirectionally actively flowing channel, to '0 0' if my outbound is >90% and then increasing slowly to max when it's <10%. it benefits the node greatly via other channels, so forwards into such channel are basically free rebalancing for your node.

[devastgh]

If your outbound is 90%+ on a source channel then you already lost. The economic value of that channel is to have inbound from it.
The theory sounds fascinating, but in real life it won't work out like that. At least, it's not working out for me. I have 0 fees to selected source channels. Sometimes traffic does move towards them, actually i get quite a lot of traffic. But as soon as i have inbound from them it quickly pushes back using either my other 0 fee channel, or one of my very low fee channels, and the waiting starts again. You cannot react fast enogh with your fees, since once a good rebalancing implementation founds a viable route, it will keep sending sats over that until it's depleted. Your only hope is that other channels in the route deplete faster than your own channel. Also, you'll get hundreds of thousands failed forwards in your log. If we're zerobasefee than having a baseline minimum ppm fee for our node makes sense (or some base fee if we're fine with that). Then you can keep source channels in an economically useful state.

edit: As a bonus fact if we overprice routes, that would probably make JIT rebalancing a viable option further increasing our routing reliability.

by having small fee on a source channel you are replenishing it while also getting more outbound capacity on other, more expensive, channels. that should help converge towards 50-50 balanced channels.

I am trying to put my instinct into formulae and it is not easy! But I would definitely lower fees on a bidirectionally actively flowing channel, to '0 0' if my outbound is >90% and then increasing slowly to max when it's <10%. it benefits the node greatly via other channels, so forwards into such channel are basically free rebalancing for your node.

[pira]

You cannot react fast enogh with your fees

That's why I hoped for an automated fee setter! But I would stop disagreeing here, some small fee makes sense even for good channels with all liquidity on your side. I just dislike the current situation of everyone sitting with jumbo 1000+ppm channels waiting for a bigger fool to rebalance. Would rather prefer contributing what I can towards sub-100ppm balanced network, really high hopes for automated tooling and liquidity ads.

[devastgh]

You cannot react fast enogh with your fees

That's why I hoped for an automated fee setter! But I would stop disagreeing here, some small fee makes sense even for good channels with all liquidity on your side. I just dislike the current situation of everyone sitting with jumbo 1000+ppm channels waiting for a bigger fool to rebalance. Would rather prefer contributing what I can towards sub-100ppm balanced network, really high hopes for automated tooling and liquidity ads.

There's no such thing as sub-100ppm balanced network in the current state. Tooling and liquditiy ads won't help with this. A lot of nodes have too much inbound, or too much outbound capacity, some of their channels must be useless. Do you want those useless channels to be yours? As we are the makers in this market, our value is having liquidity ready in the direction where demands is, reliably. Reliability is the key here. If you don't have it, real payments will avoid your node, and all you'll route will be other nodes rebalancing attempts. That wouldn't be a problem, if those rebalancing traffic wouldn't make your channels unbalanced and useless. You would need orders of magnitude more traffic if you set sub-100ppm fees than 1000ppm to be at the same earnings, but that simply will not happen since once you sold your outbound liquidity where demand is, your natural traffic will mostly halt. The current network is in such a state, that some nodes have to be the fools. I'm sorry, but there's simply no way around this at this time. Unless you can magically make all nodes have symmetric inbound-outbound capacity.