<div dir="ltr"><div>Good morning ZmnSCPxj, and list, <br></div><div><br></div><div>the answer to your question is absolutely yes and we can can achieve this actually in a very simple and elegant way. </div><div><br></div><div>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: <a href="https://github.com/renepickhardt/Imbalance-measure-and-proactive-channel-rebalancing-algorithm-for-the-Lightning-Network/blob/master/code/mppalgo.py">https://github.com/renepickhardt/Imbalance-measure-and-proactive-channel-rebalancing-algorithm-for-the-Lightning-Network/blob/master/code/mppalgo.py</a> 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.<br></div><div><br></div><div><br></div><div>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. </div><div><br>Let us assume a node $u$ wants to pay someone for an amount $a$. <br><br>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. <br>2. For all online channel partners $\{v_1,...,v_d\}$ we compute $\zeta_{(u,v_1),...,\zeta_{(u,v_d})}$<br>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$<br>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!<br></div><div>6. set $R = sum_i r_i$</div><div>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)</div><div>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)<br></div><div><br></div><div><div>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!<br></div><div><br></div><div><div>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): <br></div><div><br></div><div>* <b>Rebalancing</b> 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. <br></div><div>* in particular a node is <b>balanced</b> 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.<br></div><div>* <b>Making payments actually changes the topology</b> 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.<br></div><div>* 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. <br></div></div><div><br></div><div>Last but not least the promised output of the example code:</div><div> <br></div><div>$ python3 mppalgo.py <br>0.3 initial imblance<br>new funds 4.8 and new node balance coefficient 0.48<br><br>Conduct the following payments: <br>channel 0 old balance: 1.00, payment amount 0.22 new balance 0.78<br>channel 1 old balance: 0.90, payment amount 0.18 new balance 0.72<br>channel 2 old balance: 0.80, payment amount 0.14 new balance 0.66<br>channel 3 old balance: 0.70, payment amount 0.10 new balance 0.60<br>channel 4 old balance: 0.60, payment amount 0.05 new balance 0.55<br>channel 5 old balance: 0.50, payment amount 0.01 new balance 0.49<br><br>---- unchanged channels as they need more funds on our side ----<br><br>channel 6 old balance: 0.40, payment amount 0.00 new balance 0.40<br>channel 7 old balance: 0.30, payment amount 0.00 new balance 0.30<br>channel 8 old balance: 0.20, payment amount 0.00 new balance 0.20<br>channel 9 old balance: 0.10, payment amount 0.00 new balance 0.10<br>total amount paid over several channels:  0.7<br>(was asked to send: 0.7)<br><br>new imbalance 0.25 and old imbalance 0.30<br></div></div><div><br></div><div>Have a nice day! Rene<br></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Jan 7, 2020 at 3:30 AM ZmnSCPxj <<a href="mailto:ZmnSCPxj@protonmail.com" target="_blank">ZmnSCPxj@protonmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Good morning Rene, and list,<br>
<br>
It seems to me that the rule used here might be useful to guide how to split a payment for multipath as well.<br>
<br>
For example, consider the case where a payer Alice has channels to Bob and Charlie.<br>
<br>
* Alice-Bob has A=0.5, B=0.5<br>
* Alice-Charlie has A=0.5, C=0.5<br>
<br>
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.<br>
<br>
Would it be possible to derive such a calculation from your published rule?<br>
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.<br>
<br>
Regards,<br>
ZmnSCPxj<br>
</blockquote></div><br clear="all"><br>-- <br><div dir="ltr"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div><a href="https://www.rene-pickhardt.de" target="_blank">https://www.rene-pickhardt.de</a></div><div><br></div><div>Skype: rene.pickhardt <br></div><div><br></div><div>mobile: +49 (0)176 5762 3618   </div></div></div></div></div></div></div>