[c-lightning] Towards atomic multipath payments

[ZmnSCPxj]

Good morning c-lightningers,

> I have devised an algorithm for splitting payments that I believe handles the previously-proposed testcases well.


I have started wondering how best to implement this algorithm.

So I want to review further how our current payment system works.

Our pay implementation is a fairly conceptually-simple loop:

1.  Get a route.
2.  Try it.
3.  If it fails, report it to gossipd, then goto 1.

*Assuming* our get-a-route provides appropriate data and flexibility, the above basic loop can be extended to Bass amplifier-enabled (B-AMP) payments.

We can have a new `getroute`-like command, or add a new option to `getroute` which enables new behavior.

We have multiple new behaviors, but only those that break existing interfaces need to behave differently based on a `getroute` new option or a newer `getpartialroute` variant command.

1.  Each call of `getroute` has a high probability of giving a different route.
    - When successfully returning a route, every node and channel along that route has a `used` counter that is incremented.
    - This `used` counter increases the cost of traversing a channel/node in the basic routefinding algorithm.
    - We can schedule a timer that regularly decays the `used` counter back to 0.
    - Unparseable error onions can just further increment the `used` counter.
    - This does not break existing interface.
2.  `getroute` should pay attention to the capacity of channels.
    - Channel forwarding errors from lightningd to gossipd should also indicate how much we attempted to pass through the channel that failed.
    - This will temporarily lower the assumed capacity of the channel (in a particular direction) to be slightly lower than what we tried to forward via that channel-direction.
    - A `getroute` of an amount that is greater than the assumed channel capacity will ignore that channel.
    - This does not break existing interface.
3.  `getroute` can have an option (or alternative `getpartialroute` command) that will deliver less than the indicated `msatoshi`.
    - Instead of not trying a channel due to low capacity, it will instead lower the targeted `msatoshi` to let the capacity through.
    - If it has to lower capacity, it greatly increases the cost along that channel (the payment has to be split if we go through this route).
    - This breaks existing interface; existing `getroute` users assume that the given `msatoshi` will be what is delivered to the payee in the returned route.

Our basic loop, if bass amplifier is enabled, is then:

1.  If we have no more msatoshi to deliver, just wait for success or failure.
2.  Get a route (with `allow_partial_payment` flag on).
3.  Deduct the route final `msatoshi` from the msatoshi to deliver.
4.  Try it.
5.  If it fails, report it to gossipd, add its final `msatoshi` back to the msatoshi to deliver.
6.  Goto 1.

Regards,
ZmnSCPxj