René Pickhardt [ARCHIVE] on Nostr: 📅 Original date posted:2020-01-07 📝 Original message: Good morning ZmnSCPxj, ...
📅 Original date posted:2020-01-07
📝 Original message:
Good morning ZmnSCPxj, and list,
the answer to your question is absolutely yes and we can can achieve this
actually in a very simple and elegant way.
Please find attached a clear and simple adaption of the algorithm described
from the paper for a general multipath payment and a small python code
example available at:
https://github.com/renepickhardt/Imbalance-measure-and-proactive-channel-rebalancing-algorithm-for-the-Lightning-Network/blob/master/code/mppalgo.py
that computes this in a model case (assuming 10 payment channels that all
have a capacity of 1 BTC just to save some lines in coding). The output of
the code is at the end of the Mail.
Algorithm to conduct payments which optimally (? I have not proved this yet
but I see no way that would be more optimal with respect to the
Ginicoefficients) reduces the imbalance of nodes when conducting a
(multipath)payment.
Let us assume a node $u$ wants to pay someone for an amount $a$.
1. We assume the payment was already achieved over some channel(s) and
compute the new node balance coefficient $\nu'_u$ after this imaginary
payment has been conducted as $\frac{\tau_u - a}{\kappa_u}$. remember
\tau_u is just the total amount of funds that node $u$ currently has and
$\kappa_u$ is the sum of the capacities of all its payment channels.
2. For all online channel partners $\{v_1,...,v_d\}$ we compute
$\zeta_{(u,v_1),...,\zeta_{(u,v_d})}$
3. Let us assume channels are ordered such that
$\zeta_{(u,v_1)>...>\zeta_{(u,v_d'})}$ and omit channels with $\zeta(u,v_i)
- \nu'_u < 0$ Those channels need more funds and should not be used to pay.
That is why we might have $d' < d$
5. Compute all $d'$ rebalancing amounts $r_i =
c(u,v_i)*(\zeta_{(u,v_i)}-\nu'_u)$ as in the paper but with the new node's
balance coefficient!
6. set $R = sum_i r_i$
7. distribute payments across channels $a_i = a*r_i/R$ being the amount
$a_i$ that should be paid on channel $i$. Recall $a_i < a$ and $sum_i a_i =
a$ and $a_i < r_i$. This means that with this computation all channel have
enough liquidity to do the subpayments and the subpayments will add up to
the amount (ignoring channel reserves)
8. probe for paths for each amount and channel (potentially split the
amount for a channel across several paths that all start with that
channel). As we don't know what the rest of the network looks like we don't
know if we will be able to find paths for each channel (as before)
Now the really nice side effect: We could compute routing hints for the
invoices in the same way! by now taking the channels where $\zeta(u,v_i) -
\nu'_u$ < 0. We could also split the amounts in that way and also give
amounts together with the routing hints. This would allow a sender to send
the payments in a way that is most benefitial too us. (The sender could
also follow the above method for their outgoing channels) Only the rest of
the network might suffer worse imbalance bus guess what they charge a
routing fee for that service!
With these nice results let me just review some notation from the paper (so
that we in future might all agree to this wording/termonology):
* *Rebalancing* is the operation of moving funds along circular paths
between channels. As pointed out in the past this does not really change
the topology of the graph as the properties like the max flow / min cut
will not be affected by this. As such some people (including myself) have
argued in the past that multipathpayments are sufficient for path finding
as they will quicker find the max flow and that rebalancing is not
necessary. However the results of my research indicate that such operations
will increase the likelihood of arbitrary payments to succeed and thus (at
least in my interpretation) increase the reliability of the network.
* in particular a node is *balanced* if the zeta values are the same and
the gini coefficient is zero. While this is the case for all channels being
50-50 there are far less strict ways of achieving a good balance than
asking for channels to be opened in such a way that everyone ha 50-50.
* *Making payments actually changes the topology* of the network (similarly
to opening and closing channels). With the notation of the paper the \tau
values change and are part of the topology. This way "rebalancing" with
submarine swaps using loop or any of those services is not a rebalancing
operation in the sense of the paper and/or the above point but in fact a
change of topology.
* combining topology changes with rebalancing operations (which is often
the goal when making submarine swaps) seems however to be a good idea. In
that sense your general thought of rebalancing while paying should be
pursued.
Last but not least the promised output of the example code:
$ python3 mppalgo.py
0.3 initial imblance
new funds 4.8 and new node balance coefficient 0.48
Conduct the following payments:
channel 0 old balance: 1.00, payment amount 0.22 new balance 0.78
channel 1 old balance: 0.90, payment amount 0.18 new balance 0.72
channel 2 old balance: 0.80, payment amount 0.14 new balance 0.66
channel 3 old balance: 0.70, payment amount 0.10 new balance 0.60
channel 4 old balance: 0.60, payment amount 0.05 new balance 0.55
channel 5 old balance: 0.50, payment amount 0.01 new balance 0.49
---- unchanged channels as they need more funds on our side ----
channel 6 old balance: 0.40, payment amount 0.00 new balance 0.40
channel 7 old balance: 0.30, payment amount 0.00 new balance 0.30
channel 8 old balance: 0.20, payment amount 0.00 new balance 0.20
channel 9 old balance: 0.10, payment amount 0.00 new balance 0.10
total amount paid over several channels: 0.7
(was asked to send: 0.7)
new imbalance 0.25 and old imbalance 0.30
Have a nice day! Rene
On Tue, Jan 7, 2020 at 3:30 AM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> Good morning Rene, and list,
>
> It seems to me that the rule used here might be useful to guide how to
> split a payment for multipath as well.
>
> For example, consider the case where a payer Alice has channels to Bob and
> Charlie.
>
> * Alice-Bob has A=0.5, B=0.5
> * Alice-Charlie has A=0.5, C=0.5
>
> In that case, in order to retain balance, if Alice has to pay 0.1, it
> should strive to split the payment into a 0.05 via Alice-Bob and 0.05 via
> Alice-Charlie.
>
> Would it be possible to derive such a calculation from your published rule?
> For example, if one of the payer channels is imbalanced in favor of the
> payer, then the payment probably should not be split, but if the payment is
> big enough that it would be imbalanced against the payer afterwards, then
> some small amount must be split out to another channel.
>
> Regards,
> ZmnSCPxj
>
--
https://www.rene-pickhardt.de
Skype: rene.pickhardt
mobile: +49 (0)176 5762 3618
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20200107/53e1fd73/attachment.html>;
📝 Original message:
Good morning ZmnSCPxj, and list,
the answer to your question is absolutely yes and we can can achieve this
actually in a very simple and elegant way.
Please find attached a clear and simple adaption of the algorithm described
from the paper for a general multipath payment and a small python code
example available at:
https://github.com/renepickhardt/Imbalance-measure-and-proactive-channel-rebalancing-algorithm-for-the-Lightning-Network/blob/master/code/mppalgo.py
that computes this in a model case (assuming 10 payment channels that all
have a capacity of 1 BTC just to save some lines in coding). The output of
the code is at the end of the Mail.
Algorithm to conduct payments which optimally (? I have not proved this yet
but I see no way that would be more optimal with respect to the
Ginicoefficients) reduces the imbalance of nodes when conducting a
(multipath)payment.
Let us assume a node $u$ wants to pay someone for an amount $a$.
1. We assume the payment was already achieved over some channel(s) and
compute the new node balance coefficient $\nu'_u$ after this imaginary
payment has been conducted as $\frac{\tau_u - a}{\kappa_u}$. remember
\tau_u is just the total amount of funds that node $u$ currently has and
$\kappa_u$ is the sum of the capacities of all its payment channels.
2. For all online channel partners $\{v_1,...,v_d\}$ we compute
$\zeta_{(u,v_1),...,\zeta_{(u,v_d})}$
3. Let us assume channels are ordered such that
$\zeta_{(u,v_1)>...>\zeta_{(u,v_d'})}$ and omit channels with $\zeta(u,v_i)
- \nu'_u < 0$ Those channels need more funds and should not be used to pay.
That is why we might have $d' < d$
5. Compute all $d'$ rebalancing amounts $r_i =
c(u,v_i)*(\zeta_{(u,v_i)}-\nu'_u)$ as in the paper but with the new node's
balance coefficient!
6. set $R = sum_i r_i$
7. distribute payments across channels $a_i = a*r_i/R$ being the amount
$a_i$ that should be paid on channel $i$. Recall $a_i < a$ and $sum_i a_i =
a$ and $a_i < r_i$. This means that with this computation all channel have
enough liquidity to do the subpayments and the subpayments will add up to
the amount (ignoring channel reserves)
8. probe for paths for each amount and channel (potentially split the
amount for a channel across several paths that all start with that
channel). As we don't know what the rest of the network looks like we don't
know if we will be able to find paths for each channel (as before)
Now the really nice side effect: We could compute routing hints for the
invoices in the same way! by now taking the channels where $\zeta(u,v_i) -
\nu'_u$ < 0. We could also split the amounts in that way and also give
amounts together with the routing hints. This would allow a sender to send
the payments in a way that is most benefitial too us. (The sender could
also follow the above method for their outgoing channels) Only the rest of
the network might suffer worse imbalance bus guess what they charge a
routing fee for that service!
With these nice results let me just review some notation from the paper (so
that we in future might all agree to this wording/termonology):
* *Rebalancing* is the operation of moving funds along circular paths
between channels. As pointed out in the past this does not really change
the topology of the graph as the properties like the max flow / min cut
will not be affected by this. As such some people (including myself) have
argued in the past that multipathpayments are sufficient for path finding
as they will quicker find the max flow and that rebalancing is not
necessary. However the results of my research indicate that such operations
will increase the likelihood of arbitrary payments to succeed and thus (at
least in my interpretation) increase the reliability of the network.
* in particular a node is *balanced* if the zeta values are the same and
the gini coefficient is zero. While this is the case for all channels being
50-50 there are far less strict ways of achieving a good balance than
asking for channels to be opened in such a way that everyone ha 50-50.
* *Making payments actually changes the topology* of the network (similarly
to opening and closing channels). With the notation of the paper the \tau
values change and are part of the topology. This way "rebalancing" with
submarine swaps using loop or any of those services is not a rebalancing
operation in the sense of the paper and/or the above point but in fact a
change of topology.
* combining topology changes with rebalancing operations (which is often
the goal when making submarine swaps) seems however to be a good idea. In
that sense your general thought of rebalancing while paying should be
pursued.
Last but not least the promised output of the example code:
$ python3 mppalgo.py
0.3 initial imblance
new funds 4.8 and new node balance coefficient 0.48
Conduct the following payments:
channel 0 old balance: 1.00, payment amount 0.22 new balance 0.78
channel 1 old balance: 0.90, payment amount 0.18 new balance 0.72
channel 2 old balance: 0.80, payment amount 0.14 new balance 0.66
channel 3 old balance: 0.70, payment amount 0.10 new balance 0.60
channel 4 old balance: 0.60, payment amount 0.05 new balance 0.55
channel 5 old balance: 0.50, payment amount 0.01 new balance 0.49
---- unchanged channels as they need more funds on our side ----
channel 6 old balance: 0.40, payment amount 0.00 new balance 0.40
channel 7 old balance: 0.30, payment amount 0.00 new balance 0.30
channel 8 old balance: 0.20, payment amount 0.00 new balance 0.20
channel 9 old balance: 0.10, payment amount 0.00 new balance 0.10
total amount paid over several channels: 0.7
(was asked to send: 0.7)
new imbalance 0.25 and old imbalance 0.30
Have a nice day! Rene
On Tue, Jan 7, 2020 at 3:30 AM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> Good morning Rene, and list,
>
> It seems to me that the rule used here might be useful to guide how to
> split a payment for multipath as well.
>
> For example, consider the case where a payer Alice has channels to Bob and
> Charlie.
>
> * Alice-Bob has A=0.5, B=0.5
> * Alice-Charlie has A=0.5, C=0.5
>
> In that case, in order to retain balance, if Alice has to pay 0.1, it
> should strive to split the payment into a 0.05 via Alice-Bob and 0.05 via
> Alice-Charlie.
>
> Would it be possible to derive such a calculation from your published rule?
> For example, if one of the payer channels is imbalanced in favor of the
> payer, then the payment probably should not be split, but if the payment is
> big enough that it would be imbalanced against the payer afterwards, then
> some small amount must be split out to another channel.
>
> Regards,
> ZmnSCPxj
>
--
https://www.rene-pickhardt.de
Skype: rene.pickhardt
mobile: +49 (0)176 5762 3618
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20200107/53e1fd73/attachment.html>;