Multi-path payments in Lightning - question \ stacker news ~bitcoin

pull down to refresh

Multi-path payments in Lightning - question

2543 sats \ 14 comments \ @tolot 18 Jul bitcoin

Hi all!

Lately I've been working on a small python project to try approaching the pathfinding problem in lightning as a Min-cost network flow problem.

I know Renè Pickhardt already used this approach in order to prove the superiority of the Zero base fee approach, in fact I read his papers and got the gist of it.

Now I'm trying to model the problem mathematically - using the pyomo package in python - but I came up with a question that I couldn't find an answer for:

in a multi-path payment (MPP), can two HTLCs go though the same channel?

More specifically, I'm interested in understanding if the following situation can happen or not:

Nodes = {S, A, B, C, E, F, G, I, D} # S source, D destination

With S being the source node (aka the payer), D being the destination node (aka the payee). The scope of the question does not include considerations about base or rate fees. Node S computes the optimal path that minimises the fees for an amount and finds out that the optimal choice is to execute a MPP that follows this path(s):

     B    E  
A ->   ->   -> G -> D
     C    F

h0   h1   h2   h3  h4

where the first two hops (h1 and h2) see two parallel payments going on, then at the hop h3 the MPP converges to the node G and then procedes with the last hop to destination.

As far as I know, in classical MPP the preimage is the same for every parallel path (correct me if I'm wrong), thus I'm wondering if that thing is possible or not. Moreover, if there was an another hop such that:

          B     E  
A -> I ->   ->    -> G -> D
          C     F

h0   h1   h2   h3    h4   h5

would that be possible too? That meaning two HTLCs flowing in the same channel for the first hop, then splitting and the riconverging.

Hope the question is clear enough, otherwise I'm open to clarifications.

Thanks!

view all related items

199 sats \ 2 replies \ @TonyGiorgio 18 Jul

I call this 'splintered payments' but it is currently not possible: https://lightningprivacy.com/en/routing-analysis

You can send multiple MPPs down the same/similar paths but you can't make them split and/or come back together at any point.

0 sats \ 0 replies \ @tolot OP 18 Jul

As a side note: it would be very interesting to investigate further the impact of zero base fees on this splintered payments concept. That's clearly not about privacy, but about the computational time needed to solve near-optimally the pathfinding problem by minimising the fees.

0 sats \ 0 replies \ @tolot OP 18 Jul

Good one, so an HTLC cannot be "splintered" but multiple HTLCs can go through the same path independently. I wasn't aware of that lightningprivacy.com website, thanks for the reference

132 sats \ 6 replies \ @nullcount 18 Jul

Multi-path payments (MPP) is a general term for payment splitting. There are many implementations of MPP with different attributes: https://www.gijsvandam.nl/post/all-types-of-multi-part-payments-in-lightning-network-explained/

321 sats \ 1 reply \ @nullcount 18 Jul

@tolot Assuming we're only talking about Base MPP... In your first scenario:

     B    E  
A ->   ->   -> G -> D
     C    F

h0   h1   h2   h3  h4

NodeD creates an invoice and signals support for base_mpp. NodeA creates two HTLCs using the same payment hash in NodeD's invoice for each HTLC. HTLC-1 is routed B->E->G->D and HTLC-2 is routed C->F->G->D. Remember, only NodeD knows the preimage for this invoice.

NodeA sends both HTLCs at the same time, but they arrive at NodeD at slightly different times. NodeD gets the first HTLC and they have the preimage to redeem it, but they also know that there is a second HTLC incoming. They don't want to redeem HTLC-1 until they have HTLC-2 also. If they did prematurely redeem it, then they would have to reveal the preimage to NodeG who is also responsible for forwarding HTLC-2 and NodeG could use that same preimage to prematurely redeem HTLC-2 without actually forwarding it to NodeD.

Once NodeD has both HTLCs, they can safely redeem both of them by revealing the preimage to NodeG, etc.

Your second senario would happen in a similar way:

         B     E  
A -> I ->   ->    -> G -> D
          C     F

h0   h1   h2   h3    h4   h5

I think the confusion lies in this statement: "meaning two HTLCs flowing in the same channel for the first hop, then splitting and the riconverging."

The HTLC's don't "split" and "recombine". They are two seperate HTLCs. Its just like making two separate payments that happen to use some different hops and some of the same hops. Only the receiver has to worry about "combining" these HTLCs into a single payment.

Every LN channel has a limit to the number of "in-flight" HTLCs allowed on that channel. The default is 400+ HTLCs so most nodes should have no problem holding two HTLCs. It does not matter that those HTLCs happen to have the same payment hash (preimage).

10 sats \ 0 replies \ @tolot OP 18 Jul

Thanks a lot for the complete answer, this explains everything I needed.

100 sats \ 3 replies \ @tolot OP 18 Jul

Thanks for the reference!

My question precisely refers to the basic MPP part

The receiver does this by offering the basic_mpp feature in the invoice. The sender can now use multiple payments to pay the invoice. It should try to use diverse paths to the receiver, to increase the chances of success. The receiver, upon receiving the first HTLC out of the set, waits for at least 60 seconds for the other HTLCs from that set. If it receives them all, it reveals the pre-image to collect all of them. If it doesn't receive all HTLCs in time, it fails all HTLCs it did receive.

Where specifically I'm focused on

It should try to use diverse paths to the receiver, to increase the chances of success

It's not clear to me if using different paths is done simply to maximise the probability of success or also because it's not possible to have two HTLCs going through the same channel if the first is not settled yet.

21 sats \ 2 replies \ @nullcount 18 Jul

More paths means smaller value HTLCs. Payment success probability is higher with smaller payments. LN channels can hold hundreds of "in-flight" HTLCs simultaneously.

10 sats \ 1 reply \ @tolot OP 18 Jul

LN channels can hold hundreds of "in-flight" HTLCs simultaneously

THIS! Can you point to some resources explaining that? this was the point of the question really

21 sats \ 0 replies \ @nullcount 18 Jul

https://bitcoin.stackexchange.com/questions/93720/lightning-network-how-was-the-maximum-allowed-htlcs-in-flight-computed

21 sats \ 3 replies \ @DarthCoin 18 Jul

Interesting proposal. MPP definitely need more improvements. I try to use MPP as much is possible and yes sometimes fails.

150 sats \ 0 replies \ @tolot OP 18 Jul

The understanding of that part of MPP is somehow still blurred in my mind. I know that, for example Atomic Multipath Payments reason a bit differently and have one HTLC for every chunck of amount sent out there, but still I cannot grasp if the amounts can flow in the same channel or not.

My understanding of lightning is that the HTLC is stucked until the preimage of the hash doesn't arrive to the payer (source node). Thus, MPP with two HTLCs is only possible if the HTLCs are accomplished sequentially, not in parallel. But that would mean that the payment could suffer from being partially paid, because once the first HTLC is completed, every hop of the path knows the preimage for the hash, so if a second HTLC is triggered on the same path, the nodes can claim the funds without bringing the payment to the actual receiver.

This is what I can understand of MPP, I don't know if my understanding is correct or not. If it's correct, we shall wait for Atomic Multipath Payments for that "covergence" to happen.

Which means that, for my modelling problem at hand, a MPP payment is correctly modeled as a Min-cost network flow problem only if all the hops never converge to a single node (other than the destination)

23 sats \ 1 reply \ @quark 18 Jul

What to do if it fails? Just keep retrying until it works? Nothing is lost if it fails right?

21 sats \ 0 replies \ @tolot OP 18 Jul

According to the BOLT standards, if a basic MPP fails within the 60seconds interval, the sender tries it again. If 60 seconds pass, then the payment fails as a whole, meaning that also all the other chuncks of the payment fail and the preimage of the HTLC is not released.