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.