[c-lightning] Support Plugin for optimally splitting of payment amounts and invoices for AMP payments

[ZmnSCPxj]

Good morning Rene, and other C-Lightningers,

I still admit to not really taking the time to understand the math, but in any case, let me consider the overall design.

     amp_pay_amounts amount

On success, it returns an object, each key of which is a short-channel-id, and whose value is an amount in millsatoshi.

Is that correct?
I would have preferred returning an array of objects with explicit fields, like `[{'scid' : '999x9x9', 'amount': 42}, {'scid' : '222x22x2', 'amount' : 55}]`.

What happens if the total amount is larger than all available channel capacities?

Another argument you might want to have would be a limit on number of splits.
Though I am unsure if the algorithm would work with that.

We also need an `excludes` argument to `amp_pay_amounts` which can contain a list of channels that will *not* be considered in the split.
This handles the case where the channel is a dead end or all the capacity available from the node on that channel simply is not working.
In the python impl you could probably use a list comprehension filtering the return of `listfunds`.


For the MPP `pay`, we need two loops:

* An outer loop where we start with an initial splitting plan from `amp_pay_amounts` and then modify it when we realize that some outgoing channel simply cannot be used.
* An inner loop where we get a payment part (an outgoing channel and an amount) and keep trying routes from that payment part until we fail.

When paying to legacy payees that are not yet MPP-enabled, the outer loop just selects the most appropriate channel to deduct the entire amount from (i.e. whichever one gives the biggest improvement to balance if the entire amount is deducted from this.

---

Now, because there are two loops, I propose splitting off the inner loop into a separate subsystem, accessible as JSON-RPC commands (it can be in the same plugin process, but I recommend splitting it off into its own file at least, and exposing it via JSON-RPC commands so that other methods of splitting can be experimented with).

So let me present the `partpay` system:

    startpartpay maxfee payment_hash => partpayid
    partpay partpayid outgoingscid destination amount [routehint]
    endpartpay partpayid

`startpartpay` creates a "`partpay` context".
This is a virtual object containing details:

* What channels and nodes we know are failing.
* How much budget we still have for fees.

`partpay` itself is *the* inner loop which strives to deliver the specified amount to the destination via the specified outgoing channel.
It "shares" any channels and nodes that are failing to other `partpay` using the same `partpay` context/
This lets the parallel partial payments (`partpay`) to inform each other of blockages (in the case of returned `temporary_channel_failure`, we assume this is due to capacity issues and we might mark that channel with the failing amount --- if another `partpay` with lower amount than the failing amount arrives, it would not exclude that channel unless it still returns `temporary_channel_failure`, in which case it marks it with the lower amount instead).
More importantly, it shares any fees: all `partpay` using the same `partpayid` must have fees that sum to less than the `maxfee` indicated in the `startpartpay`.

`endpartpay` is only allowed if no pending `partpay` is using the context, and deletes the context.

I think `paystatus` and `listpays` would then be implemented by the `partpay` system.
Indeed, the current `pay` would have most of its code moved into the `partpay` system.

----

The outer loop starts with an `amp_pay_amounts` to create a payment splitting plan, then creates a payment context by `startpartpay`.

Then, in a loop:

  * For every pending part in the plan, launch a `partpay`.
  * If one of the `partpay`s fails with an error indicating it ran out of possible routes to try:
    * Add that outgoing channel to its own list of excluded outgoing channels.
    * Split up that partial payment by calling `amp_pay_amounts` again with the sub-amount, and with the current set of excluded outgoing channels.
    * Add the new parts to the plan.

Further, if a `partpay` fails due to lack of fee budget, then we start waiting for other `partpay`s to fail for whatever reason.
Then we completely re-make the plan from the original outgoing amount, but with the now-excluded outgoing channels still excluded, hopefully leaving us with fewer outputs.
The most likely reason why the fee budget runs out is because we have split the payments too much, so now we need to re-merge payments, but with the excluded outgoing channels considered.
The `partpay` could cooperate with this by setting the `partpay` context into an out-of-budget condition and forcing all `partpay` loops to fail as soon as they receive a non-permanent failure from remote.
Then the outer loop can recreate the plan and the `partpay` context.

Once any single one of the `partpay`s has succeeded we can already report success to the user, since all we really care about is the proof-of-payment.
Though we still need some cleanups afterwards, so more modifications to the `libplugin` may be necessary.

Regards,
ZmnSCPxj