[c-lightning] Towards atomic multipath payments

[ZmnSCPxj]

Good morning list,

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

Algorithm Parameters
--------------------

We will need to figure out an algorithm parameter, "the decrement", a value in BTC.
Larger values mean our algorithm can search faster for routes that can fit subpayments.
Smaller values mean better granularity, making it more likely to get through routes with fewer splits (and hence lower fees).
I suggest a value of 0.2mBTC for the decrement for now.

Another algorithm parameter is "the timestep", a value in seconds.
Larger values give more time for routing failures to propagate back to the algorithm.
Smaller values mean our algorithm can search faster for routes.
I suggest a value of 250ms for the timestep for now.

We can also choose to endlessly bikeshed these parameters, or even leave it to users so they can easily worsen is  performance.


Algorithm Data Structures
-------------------------

The algorithm itself must maintain the following fields:

1.  A heap of `(estimatedcapacity, route)` pairs, called `route_candidates`.
    The heap is a max-heap keyed on `estimatedcapacity`.
    * The remaining routes we can still route through,
2.  A set or list of `(estimatedcapacity, route)` pairs, called `deferred_route_candidates`.
3.  A numeric value in millisatoshi, called `remaining_to_pay`.
4.  A numeric value in millisatoshi, called `remaining_fee_budget`.
5.  A timer, called `theTimer`.
6.  A set or list of payment attempts (described below), called `pending_payments`.
7.  A flag, called `doomed`.

A payment attempt has the fields:

1.  A `(estimatedcapacity, route)` pair.
2.  A numeric value, `to_pay`.
3.  A numeric value, `fee`.

Procedures
----------

We initialize the algorithm as below:

1.  Set the payment amount as `remaining_to_pay`.
    Assert it is nonzero.
2.  Set the maximum acceptable fee as `remaining_fee_budget`.
3.  Set `doomed` to false.
4.  Get a set of available routes to the payee.
5.  Estimate the capacity of each route.
    * We can compute exactly how much each channel would cost for fees and factor in the 1% reserve.
    * Or for simplicity just get 95% of the smallest channel along the route.
      Precision is unimportant since we cannot get accurate information about the actual state of each channel anyway.
    * For the first channel of each route, we can know more accurately the current status since it is one of our own channels; if the value we can pay on our side is less than the route capacity (as computed above), we set the channel capacity to what we can pay for the first channel.
    * We can add a little randomization here also so that route randomization is performed for the first payment attempt.
6.  Put the `(estimatedcapacity, route)` pairs into the `route_candidates` heap.
7.  Clear the `pending_payments` and the `deferred_route_candidates`.
8.  Kick the `timer` to trigger 0s from now.

When the `timer` triggers:

1.  Assert that `remaining_to_pay` is nonzero and `doomed` is false.
2.  If the `route_candidates` heap is empty, load the `deferred_route_candidates` into it and clear the `deferred_route_candidates`.
3.  If the `route_candidates` heap is *still* empty, set the `doomed` flag to true.
    If `pending_payments` is empty, signal a failure from this algorithm.
    Then just return from this procedure.
4.  Get a `(estimatedcapacity, route)` pair from the `route_candidates` heap.
    Since this is a heap, we will get the route with the largest estimated capacity.
5.  Create a new payment attempt.
    Set its `to_pay` as the smaller of `estimatedcapacity` and `remaining_to_pay`.
6.  Compute the `fee` for the payment along the `route.
7.  Check if the `fee` exceeds `remaining_fee_budget`.
    If so, drop this payment attempt and the route, then restart this procedure.
8.  Subtract the payment attempt `to_pay` from `remaining_to_pay`.
9.  Subtract the payment attempt `fee` from `remaining_fee_budget`.
10.  Actually send out the payment attempt to the network.
11.  Add the payment attempt to `pending_payments`.
12.  If `remaining_to_pay` is nonzero, set the timer to trigger again `timestep` seconds from now.

When a payment attempt fails:

1.  Add the payment attempt `to_pay` to `remaining_to_pay`.
2.  Add the payment attempt `fee` to `remaining_fee_budget`.
3.  Remove this payment attempt from `pending_payments`.
4.  If `doomed` is set:
    * If `pending_payments` is empty (this is the last pending payment), signal failure from this algorithm.
    * otherwise just return.
5.  If the attempt failed due to permanent error, drop the route.
6.  If the attempt failed due to temporary node failure at payee node, put the `(estimatedcapacity, route)` back to the `route_candidates` heap.
7.  If the attempt failed due to temporary node failure not at the payee node, put the `(estimatedcapacity, route)` to the `deferred_route_candidates` set.
8.  If the attempt failed due to temporary channel failure, recompute `estimatedcapacity`.
    Set it to `value` minus `decrement`.
    Then put the new `(estimatedcapacity, route)` to the `route_candidates` heap.
9.  Kick the `timer` to trigger immediately.

If a payment attempt succeeds:

1.  Signal success from this algorithm.


Regards,
ZmnSCPxj