Proposal: `routetricks` plugin

[ZmnSCPxj]

Introduction

In https://github.com/ElementsProject/lightning/pull/2890#issuecomment-519380842 @rustyrussell expresses the opinion to move permuteroute to a plugin.

I am currently busy on getroutequick, and additionally, also in non-Bitcoin-related tasks, thus cannot do this yet.

So I add this sketch here.

routetricks is a "built=in" plugin, as it will provide some functionality that will (eventually) be done by pay, which itself is a built-in plugin.

This provides the commands below:

1. recalcroute - Recompute the fees of a route.
2. smoothenroute - Remove cycles in a route.
3. permuteroute - Modify an existing route to avoid known-failing channels / nodes.

recalcroute

Usage:

recalcroute route [msatoshi] [cltv] [fromid]

Recompute the fees and delays of the given route, or fail if any channel or node is not existing in our local routemap.

This simply does listchannels on each channel along the route to get the delay, base_fee_millisatoshi, and fee_per_millionth, starting from the end.

In addition, the route is validated so that each hop connects to the previous via the given channel, and that the first hop is directly connected to fromid (if specified), or our own node (if fromid not specified).

If msatoshi and cltv are unspecified, they will be extracted from the last hop of the input route.

Usefulness

• Needed for smoothenroute, which is needed for permuteroute.
• In the future, for multipath payments, we can recalcroute a route which fails a given amount to try to use a smaller amount, hence why msatoshi can be specified.
• In the future, if pay receives a failure_code with the UPDATE bit set, rather than add the specified channel to the current excludes set, it should attempt a recalcroute first: if recalcroute succeeds and gives a different value at the first hop than the input route, then it should re-attempt the same route with the new fee setup as long as the new setup is still within the maxfeepercent and maxdelay.
  • This is vital if in the future we want to widely deploy a "passive-rebalance" plugin, where we adjust our channel fees via setchannelfees depending on how much we own of a channel (set fee to 0 if e.g. >75% is owned by us, double the normal fee if e.g. <25% is owned by us, etc.). If commonpayimplementations cannot handleUPDATE` failures, then it would be negative utility to install such a plugin.
    • This would help us make "fee-free rebalance" needed for widespread JIT-Routing support @renepickhardt

smoothenroute

Usage:

smoothenroute route [fromid]

Eliminates cycles in the given route.

This does not require direct lookup on the routemap unless actual smoothening is done. Simply requires an O( n^2 ) loop where we compare each node (starting from fromid or our own node) with every succeeding node. If we find a match, then eliminate all hops up to and including the matched hop node.

This has to keep track of a "largest index changed" which is the largest index (of the outer loop!) that matched a later hop (and thus triggered a deletion of some hops). This is needed since we also have to recalcroute up to that section, but we probably do not want to recalcroute the entire route (in case the latter part was constructed by adding routehints).

For example, if the input was:

a ->5msat-> b ->4msat-> c ->3msat-> b ->2msat-> d ->1msat-> e

Then smoothenroute would result in:

a ->5msat-> b ->2msat-> d ->1msat-> e

But we only need to recalcroute up to the below and concatenate with the postfix:

a ->5msat-> b ->2msat-> d

(because the d->e route might be a routehint and thus not in the routemap)

Which should yield something like:

a ->3msat-> b ->2msat-> d ->1msat-> e

Usefulness

• Any routing trick that involves concatenating routes together should probably call smoothenroute afterwards.
• In particular, permuteroute needs this as it performs path splicing, creating multiple path subsections and concatenating them. smootheroute should be used afterwards to remove unnecessary cycles in the route.

permuteroute

Usage:

permuteroute route erring_index failure_code [exclude] [fromid] [max_hops]

Create an alternative route from a given route, skipping over a failing channel or node.

If the given failure_code has the NODE bit set, then this attempts to skip over the node in the erring_index - 1 index of the route (erring_index cannot be 0 in this case: this implies a local node failure). If the NODE bit is clear, then this attempts to skip over the channel in the erring_index of the route.

This basically just uses getroute starting from the node before the failing channel or node, with destination being the node after the failing channel or node. We should use a limited search: if the number of nodes that need to be scanned by getroute is too high then we early-out and just fail the permuteroute. In addition to the given exclude we should also exclude the failing node or channel (double-specifying the same node/channel should be safe).

The msatoshi and cltv args of getroute should be copied from the hop that pays to the node after the failing channel/node.

If the limited-max_nodes_scanned getroute succeeds, we just conactenate this to the route before the break, then the getroute result, then the route after the break. Then call smoothenroute on the result.

Prerequisites:

• 2894 getroute should support exclude-ing nodes too.

• Add a max_nodes_scanned limiting parameter to getroute, as described in https://github.com/ElementsProject/lightning/pull/2890#issuecomment-519499783
  • Not clear what would be a good max_nodes_scanned input for getroute, 20 sounds like a good compromise.

Usefulness

• The limited-range scan should be reasonably quick and should speed up future routefinding attempts after a payment failure.

[trueptolemy]

routetricks is a "built=in" plugin, as it will provide some functionality that will (eventually) be done by pay, which itself is a built-in plugin.

Does "built-in" means this plugin must be started by default like the pay plugin and this plugin must be writen in C?

[darosior]

routetricks is a "built=in" plugin, as it will provide some functionality that will (eventually) be done by pay, which itself is a built-in plugin.

Does "built-in" means this plugin must be started by default like the pay plugin and this plugin must be writen in C?

I think that it means it has to be placed into the plugins/ directory into this repo (thus started by default). It might be probably better to write it in C : I've thought about writing the lock plugin in Python, but plugin's requirements might differ from C-lightning's one and then make the plugin startup fail. It seems to me that C plugins are more ""binded"" with lightningd because they share the same dependencies.

[ZmnSCPxj]

Indeed. In theory we can start up C-Lightning currently with Python not installed (Python is used for tests and the plugins in the separate repo and generation of some code, but is not required for C-Lighning startup, and "should" not be required when compiling from .tgz). Though this might eventually be loosened if we have an important plugin that is already written in another language and want to add it in the out-of-the-box setup in the future.

[trueptolemy]

Analogy to RTS, the path finding algorithm must consider the path weight?

[ZmnSCPxj]

getroute already considers path weight. You just need, a limitation on how many nodes getroute will scan, because if it has to scan too many nodes it is better to just run a new getroute from the source to the destination.

[whitslack]

a "passive-rebalance" plugin, where we adjust our channel fees via setchannelfees [sic] depending on how much we own of a channel

@ZmnSCPxj: I already have a cronjob doing exactly this. Could you explain what you mean by "negative utility"? It's been working fantastically well for me.

[ZmnSCPxj]

@whitslack There is an edge case where a remote payer thinks you still have 0 channel fees but you have set already set your channel fees to non-zero (but the channel_update saying so has not reached the remote payer yet). Then it routes and pays you 0 fees. Your node will fail the payment with a fee_insufficient.

If the remote payer is C-Lightning, regardless of failure code, the channel that fails is excluded, which reduces the probability you will be routed through on the next attempt. In principle, rather than excluding the channel that returns fee_insufficient (or other failure code with UPDATE), we could recalculate the route fees with the new updated costs, then check again if the new fees are still within the maxfeepercent/maxdelay.

Do note that this passive-rebalance will be discouraged by #3064. See also: https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-September/002157.html

[whitslack]

There is an edge case where a remote payer thinks you still have 0 channel fees but you have set already set your channel fees to non-zero (but the channel_update saying so has not reached the remote payer yet). Then it routes and pays you 0 fees. Your node will fail the payment with a fee_insufficient.

@ZmnSCPxj: Doesn't this directly contradict the recommendation in BOLT #7:

The origin node:

• SHOULD accept HTLCs that pay an older fee, for some reasonable time after sending channel_update.
  • Note: this allows for any propagation delay.

?

In principle, rather than excluding the channel that returns fee_insufficient (or other failure code with UPDATE), we could recalculate the route fees with the new updated costs

Isn't this the expected behavior implied by the spec? Is there an open issue for implementing this in C-Lightning?

[ZmnSCPxj]

Doesn't this directly contradict the recommendation in BOLT #7:

It is a "SHOULD" so we are allowed to not follow it. It can probably be done. Alternatively maybe it is already implemented, I have not looked at the forwarding code for a long while already, it was a mess the last time I looked at it.

Isn't this the expected behavior implied by the spec? Is there an open issue for implementing this in C-Lightning?

Yes. Currently C-Lightning pay plugin does not check the exact failcode; it should (currently it just always excludes the channel regardless). I think not, I should probably go open one.