[c-lightning] Towards atomic multipath payments

[ZmnSCPxj]

Good morning list,

I would like to propose also some motivating test cases for AMP.
Also, this is good "test-drive design" practice.

In the below, channels indicate how much each side owns, and values are in units of mBTC.

## `test_amp_simple`

        5
     O ---> ldst
     ^   _
    5|   /|
     |  / 5
     lsrc

    pay: lsrc -> 6 -> ldst

This simple case serves as baseline functionality.
This basic functionality means we can probably safely run this in VALGRIND mode, which the others might be too big (involving more than 3 lightning nodes) to run in without madly increasing our test run time.

## `test_amp_unequal`

      10     10
    O ---> <--- ldst
    ^             |
    |             | 19
    |             v
    |20           ^
    |      20     | 1
    lsrc -------> O

    pay: lsrc -> 10.1 -> ldst

This tests the possibility that there is a path with almost good capacity, while another path has bad capacity, but the two paths combined can reach sufficient capacity.
Any algorithm we devise should be able to discover this uneven split.

## `test_amp_uneven_local`

         10
      O ---> ldst
      ^   _
    10|   /|
      |  / 1
      lsrc

    pay: lsrc -> 10.8 -> ldst

Local information may be useful to determine splitting.
Of course, a general algorithm that can handle `test_amp_uneven` should be able to handle this case too.

## `test_amp_3way`

        2     8
      O --> <--------- ldst
      ^             8 /  |
      |              /   | 8
      |            |/    |
      |           _      |
      |10       2 /|     |
      |          /       |
      |        _O        |
      |        /|        |
      |       /          v
      |   10 /           ^
      |     /            |
      |    /             | 2
      |   /     10       |
      lsrc ------------> O

    pay: lsrc -> 4.5 -> ldst

A naive algorithm would try a single payment, then split in half if that fails, with the same logic (split in half) again if each half fails.
Such a naive algorithm would not work well with a non-even prime number of paths with about equal capacity that we can use to pay.
(such a naive algorithm would also not work well with `test_amp_uneven`, but somebody might make an argument that we expect paths to be roughly equal in available capacity, so we still want to protect against this naive algorithm)

## `test_amp_5way`

     (please do not ask me to draw graphic)

    pay: lsrc -> 8.5 -> ldst

Similar setup to `test_amp_3way`, except with 5 intermediate nodes.
This prevents us from just passing `test_amp_3way` using the above naive algorithm with a "split 3 ways" variation, and really force us to consider the case properly.

## `test_amp_wumbopay`

           100          100
    lsrc ---------> O ---------> ldst

    pay: lsrc -> 50 -> ldst

Payments above the 42.9 mBTC limit can be implemented in AMP with intervening nodes unaware of the limit violation.


Regards,
ZmnSCPxj