Good morning Lightning world,
This was originally written for C-Lightning, hence the C-Lightning-isms, but I
realized the general principles were valid for all LN implementations.
---
First, let us consider some C-Lightning node who, for some reason, only has
unpublished channels to the network (note: in my opinion, ***unpublished
channels delenda est!***). Let us suppose this node wishes to receive some
amount of funds, from multiple different payers.
Now, the payee node knows MPP exists, and thus, it is not very concerned that
it has insufficient incoming capacity in a ***single*** channel to accept one
of the payments. Reasoning that MPP exists, it considers instead the *sum
total* of all incoming capacities. It sees that it has sufficient *sum total*
incoming capacity that it can accept all payments from all payers, with some to
spare.
However, at the channel-level detail, *none* of the channels has sufficient
capacity to accept a single one of the payments the C-Lightning node now
expects to receive, in full. So, what should the C-Lightning node put as
routehints in a generated invoice?
Another, is that we should note that I described "payers" with an "s" at the
end. In the English language as commonly used by puny humans, adding an "s" at
the end of a noun is a common (but not universal) convention implying that the
subject under discussion is actually composed of more than one item. So not
only must the C-Lightning node (all of whose channels are unpublished, thus
cannot be paid unless it reveals at least some of the channels as routehints in
the invoice) make an invoice with sufficient routehints to get an MPP
delivered, it must make *multiple* invoices, such that the invoices it issues
have as little overlap in their routehints as possible
Otherwise, if we provide the **same** set of routehints in invoices to two
**different** payers, both of them will interfere with each other, possibly to
the point that neither can pay to the payee (since e.g. some of the available
capacity is taken up by parts of one payment while the rest is taken up by
parts of the other payment, and neither payment can then complete in full due
to this deadlock).
This is important in case the C-Lightning node receiver is completely
unannounced (i.e. has only unpublished channels). The payers cannot fall back
to just trying directly routing on a different incoming channel of the
receiver, as they may not have any knowledge of such channels.
I suggest, then, that the C-Lightning node that wants to get paid, and uses
only unpublished channels, should use a Round-Robin strategy for selecting
routehints.
To implement this, the `invoice` command maintains a persistent list of all
channels the node has. When a newly funded channel is locked-in by both sides
(transitions to `CHANNELD_NORMAL`) it is simply appended to this list. When a
channel leaves `CHANNELD_NORMAL`it is simply removed from this list. Let us
call this the round-robin list.
Then, when the `invoice` command is invoked, it generates routehints by
executing a loop:
* Maintain variables: a removed list (initially empty), a running sum amount
(initially `AMOUNT_MSAT(0)`), and a set of proposed routehints (initially empty)
* Round-robin: Remove a channel from the front of the round-robin list and put
it in the end of the removed list.
* If the channel has no incoming capacity, skip to the top of the loop again
(`continue;`).
* If the channel is a dead end (i.e. connects to a node which has no published
channels elsewhere), skip as well (`continue;`).
* Copy the scid and any other details to the set of proposed routehints.
* Add the incoming capacity of the taken channel to the running sum. If the
running sum now exceeds the amount to be paid, append the removed list to the
current round-robin list and leave the loop.
* If the round-robin list is now empty, exit the loop (append the removed list
to the current empty round-robin list) and report a `warning_capacity` that it
looks like there is insufficient incoming capacity for this invoice.
On exit of the above loop, we sort the set of proposed routehints, from highest
incoming capacity to lowest, and use that set as the routehints for the invoice.
(It would probably be a good idea as well to persist the round-robin list)
The above ensures that as much as possible, different invoices will have
different sets of channels routehinted (due to the round-robin behavior), but
gracefully degrades (some overlap in routehints) if the number of channels
available is low.
An issue is privacy. A probing fake payer could spam the receiver with
multiple requests for invoices it never intends to pay. This can let the fake
payer discover, at minimum, the entry points used by the payee to connect to
the public network (which cannot be removed, even if you somehow obscure the
actual short-channel-IDs of the payee, since the payer has to know *what* node
to reach to get to the payee), which the payer can then probe or otherwise hack
or buy out in order to extract information about the economic activity of the
payee (due to the Axiom of Terminus, any forward that goes *to* an unpublished
channel, *is* the final hop to the actual final destination, so the entry
points have accurate data on incoming payments of the unpublished payee via the
channel with them). If the payer simulates multiple payers (i.e. Sybils) the
payee cannot attempt to reuse channels in routehints to the different simulated
payers, as that would degrade the ability to pay since th
e capaci
ty of the channels has to be shared by the different payers if those payers
were not sockpuppets. Thus the lie of improved privacy by unpublished channels
is revealed, and therefore, in my opinion, unpublished channels delenda est.
----
Now, let us turn our attention to the payer of such an invoice.
Currently, our `paymod` system uses a single sequence of routehints for all
sub-payments of an MPP.
Thus, if a payment is split in two, both sub-payments will start executing on
the same routehint.
Yet as considered above, the point of multiple routehints is that not a single
one has sufficient capacity to receive, and the multiple routehints are
provided which in total are needed to receive all the incoming funds.
Thus, I suggest as well, that sub-payments should have different sequences of
routehints to try.
For example, currently, for sub-payments 0 and 1, they will try routehints A,
B, C, D in this order:
0 1
A A
B B
C C
D D
Instead of using the same shared sequence of routehints, on splitting, the
split payments should use:
0 1
A B
C D
B A
D C
That is, sub-payment 0 should try routehints in the order A, C, B, D, while the
sub-payment 1 should try routehints in the order B, D, A, C.
The reasoning is the same as with the argument for round-robin routehint
selection: by having different sub-payments initially try different routehints,
we improve our success by reducing their overlap in the use of shared
resources, and therefore reduce the risk of deadlock (especially if the
sub-payments are adaptively split into even more sub-payments).
We can do this by a sort of round-robin, as well. For each sub-payment we
initially create an empty list of routehints. Then we "spread" the routehints
to each sub-payment.
* If there are more sub-payments than routehints, then we repeat the routehints
until we have given one routehint to each sub-payment.
* If there are more routehints than sub-payments, then we repeat the
sub-payments until we have completed the routehints.
After the above initial distribution, we then go through all sub-payments, and
for each sub-payment, append routehints in the original order, but skipping
those that were already given to that sub-payment in the above initial
distribution.
For example, suppose we are distributing 3 routehints A B C to two sub-payments
0 1. We do the initial distribution:
0 1
A B
C
And then we give each sub-payment the rest of the routehints:
0 1
A B
C A
B C
Another example, where we are distributing 2 routehints A B to four
sub-payments 0 1 2 3. Our initial distribution is:
0 1 2 3
A B A B
Then we give each sub-payment the rest of the routehints:
0 1 2 3
A B A B
B A B A
Thus, each sub-payment gets the entire list of routehints, but in a different
order.
----
Finally: the same argument --- that sub-payments should avoid using the same
set of resources as much as possible -- applies to the *first* hop just as much
as the *last* hop.
Thus, one possibility is to also maintain a list of outgoing channels for each
sub-payment, which sub-payments try in round-robin order. And again, each
sub-payment should get a different order from each other in a coordinated
fashion which reduces their interference.
We do this by, at the *start* of the payment before we split it up, taking all
local channels and shuffling them. Then we distribute the outgoing channels
with the same algorithm as the above.
Then, when a sub-payment executes, we use a similar algorithm as the `invoice`
case where it selects routehints.
* Maintain a removed list (initially empty).
* Round-robin: Remove the channel at the front of the round-robin list, append
to removed list.
* If the round-robin list is empty, then we should append the removed list to
the round-robin list and consider splitting the payment.
* If it has insufficient outgoing capacity, skip.
* If it is a dead end, skip.
* Otherwise it has sufficient capacity, break out of the loop (append the
removed list to the round-robin list) and try routing via that channel.
--
Regards,
ZmnSCPxj
_______________________________________________
Lightning-dev mailing list
[email protected]
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
