From r.pickhardt at googlemail.com Mon Jul 15 12:23:18 2019 From: r.pickhardt at googlemail.com (=?UTF-8?Q?Ren=C3=A9_Pickhardt?=) Date: Mon, 15 Jul 2019 14:23:18 +0200 Subject: [Lightning-dev] Congestion and Flow control for Multipath Routing Message-ID: Dear fellow BOLT devs, in this mail I want to suggest a congestion and flow control mechanism to improve the speed and reliability of multi path routing schemes. This is the first of a couple of emails that I will write in the following weeks as I have used my break in hospital not only to recover but to tinker quite a bit about path finding and routing algorithms on the lightning network. Problem statement =============== Currently on the lightning network we have the issue of stuck payments [0]. As soon as an onion is sent it is out of the sender's control. This problem seems to be in particular drastic if we wish to use Atomic Multi Path routing [1] (which in the described form is not compatible with my proposal. I believe my proposal should be compatible with the status quo of base-AMP). The entire payments and HTLCs of a multipath payment will only be settled once enough incoming HTLCs arrived at the recipient (meaning the sum of amounts is bigger or equal to the amount specified in the invoice). This has the following list of downsides: - One malicious actor (who is just not forwarding the onion but also not signaling an error) is enough to interrupt the entire payment process and freeze all other HTLCs even of partial payments the actor is not part of. - The entire payment process takes as long as `max_{p \in paths}(t(p))` where `t(p)` is the time it took for path `p` to set up (and settle) HTLCs - More HTLCs will be reserved by the network for a longer time. This means more liquidity is bound / reserved and channels could even become unusable if the 483 HTLC limit is reached. Protocol Goals =========== I looked at the windowing mechanism used in TCP to achieve congestion control and transferred this concept to the setting of the Lightning Network. This idea is motivated by the Spider Network paper [2] which mentions that in a simulation the success rate of payments is increased when changing the lightning network from a circuit switched payment process (which we currently have with our atomicity requirements) to a packet switched mechanism that includes congestion control (though in that publication congestion control had a different semantics than in has in my proposal). Protocol Benefits ============= - Improve the speed of multipath payments - Reduce load from the network (in particular don't lock liquidity for such a long time) - less congestion at single nodes (I assume this is not a problem at this point in time) - more privacy (different preimages are used along different paths and overall payments might become smaller or of uniform size) - usual benefits from AMP Protocol idea (base version) ===================== Disclaimer: This base version has obvious drawbacks but I decided to include it as it transports the idea. A regular payment on the Lightning Network for amount `x` has a Payment Hash `H` and a preimage `r`. If a recipient would now accept that this payment could be split over up to `n` paths the recipient would create a sha-chain of preimages and payment hashes with `n` elements ``` r_0 = rand() H_0 = H(r_0) r_{i+1} = H_i H_{i+1} = H(r_{i+1}) ``` The payment process is initiated by the recipient providing H_{n-1} and signaling (in the invoice) that up to `n` preimages are available to complete this payment. A sender can now decide to split the payment amount `x` into `n` seperate payments for example of the amounts `x/n` though different splits should be possible. Once the preimage of the first partial payment is returned the payer learns the payment hash wich can be used for the next partial payment. (One issue is that while we have a proof of payment we do not necessarily have a proof of amount - which is true for the regular lightning case though with a single atomic payment this is not an issue as the preimage will not be relased if the amount is too low. We could avoid this issue by demanding that mulipath payments have to be at least of size `x/n`) This protocol makes the AMP process sequential and reduces the load from the network. Congestion (which is a local problem of routing nodes) becomes less likely if only HTLCs are locked up for a partial payment independent of the success or failure of other partial payments. However in the base version there is a severe downside: **Sequential payments will make the payment process even longer since it is not the max time needed over all payments but the sum of times needed.** We can resolve this issue by introducing flow control via a windowing mechanism and allowing concurrency of partial payments Protocol Overview (suggested version) ============================== Let us assume the receiving node supports a window size of `s` concurrent payments. Now the payee will not only create one sha-chain of `n` payment hashes as in the base version but `s` sha-chains of `n` payment hashes. In the invoice we would now transport the following data: * `n` (we need a different letter as n is already taken) = amount of partial payments that are supported per payment hash * `s` = number of concurrent payments supported (window size) * `s` many `p` fields which contain the `s` different top elements H_{n-1} for each sha-chain Note that technically the payment amount could now be even split up into `s*n` partial payments though I would recommend to still go with `n` partial payments. The advantage with this mechanism are the following: * As long as less then `s` payments get stuck the protocol can continue to deliver partial payments. * Nodes already agree to do some overpayments to obfuscate the payment amount. If the stuck payments are really small they could be considered as overpayments (in case they eventually go through). This would work if the sender sends overall `n+k` payments where `k` is the number of currently stuck payments. Potential Improvements (for better privacy) ================================ * Instead of using a sha-chain we could xor every preimage with a sequence number making it harder for an attacker to correlate two consecutive payments in the stream of payments via ``` r_0=rand() H_0(r_0) r_{i+1} = H_0 ^ (i+1) H_{i+1} = H(r_{i+1}) ``` Instead of a sequence number we could also do something like `(i+1)*x` (as attackers should not be aware of the overall payment amount it will be hard to guess that number). I guess you folks are aware of much better cryptographic tricks to achieve what I suggest here. So please take this just as an idea from a beginner in cryptography. * If paths are reused for partial payments the sender should switch to a preimage from a different sha-chain creating some path decorellation * Even when going away from hashedpreimages when changing to MuSig and multilocks a mechanism similar to HD-wallets should be usable for this scheme Sender Requirements ================= The sender needs to keep track how many payments have been successfully sent and how many are in transition / stuck. For the privacy parts the sender additionally needs to watch out to cycle through the shachains when reusing paths Receiver Requirements ================== More data needs to be stored / held in memory. (either `s` complete sha-chains) or the `s` times the initial preimage of each chain and the current payment hash. in the later case the computational overhead will be increased. Conclusion ========= * With introduction of two new fields in BOLT 11 invoices and rather simple code changes for invoice creation / preimage releasing we have the ability to introduce flow and congestion control to multipath routing of payments. * The proposed mechanism is not atomic. It is possible that a payee receives only a fraction of all payments and stops collaborating * Less HTLCs and liquidity will be bound in multipath routing schemes resulting in a reduction of load for the network * A few stuck payments can be neglected as "cost" of operation. While I strongly support ideas from [0] we might not need them with this simple trick. * As I used the term `stream of payments` in the text this mechanism could also be extended for a streaming payments protocol. I am curios on your thoughts. With kind regards Rene [0]: https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-June/002029.html Proposal for Stuckless Payment by Hiroki [1]: https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-February/000993.html AMP: Atomic Multi-Path Payments over Lightning by Conner & Laolu [2]: https://arxiv.org/abs/1809.05088 Routing Cryptocurrency with the Spider Network by Vibhaalakshmi et. al. -- https://www.rene-pickhardt.de Skype: rene.pickhardt mobile: +49 (0)176 5762 3618 -------------- next part -------------- An HTML attachment was scrubbed... URL: