Routing algorithm applies redundant routing fees per MPP shard

[MaxFangX]

For a single path, two-hop payment Sender -> LSP -> Receiver, define the max_sendable amount as

sum(next_outbound_htlc_limit) / (1 + lsp_prop_feerate)

We've have confirmed in our tests that if the LSP has 0 base fee, we are actually able to send precisely this amount.

Rearranging, the equality is

max_sendable * (1 + lsp_prop_feerate) = sum(next_outbound_htlc_limit) (summing over usable channels).

However, if the sender's payment is split across two Sender -> LSP channels, we aren't able to send max_sendable as it fails to find a route. We ran a binary search to find the highest payment amount, accurate to the satoshi, for which routing succeeds in this MPP configuration - let's call this result max_flow. We then get the following equality:

max_flow * (1 + 2 * lsp_prop_feerate) = sum(next_outbound_htlc_limit).

However, we expect max_flow = max_sendable. In other words, the routing algorithm appears to charge the LSP's feerate twice (according to max_flow), even though the Route it returns correctly charges the LSP proportional feerate only once for each Path. This can be further generalized - if a user's liquidity is routed over num_shards shards, the equality becomes:

max_flow * (1 + num_shards * lsp_prop_feerate) = sum(next_outbound_htlc_limit).

So the routing algorithm seems to somehow reapply the proportional fee rate once per shard even though it should only be applied once.

[tnull]

As mentioned on Discord: Yes, this is likely due to our routing algorithm internally first collecting candidates. As we keep track of the overall used liquidity in the first step (but not in detail), we might not be able to apply the "discount" for the follow-up parts that run over the same paths. We only later detect the overpayment and adjust the fees when we choose the best paths and recalculate fees. This might be a limitation of our multi-step approach, and one reason why exploring a 'true' flow-based algorithm could still make sense in the future IMO