Re: [Lightning-dev] Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0
Good morning Ariel and Rene and list, I have started to consider how best to attack the modified Luaces-Pickhardt JIT-Routing, which reuses the same payment hash as the message to forward. (In the case where JIT-Routing is used by the ultimate source of a payment, the payment hash of the invoice being paid.) And it seems that, unless hop routes are given more time than their reported `cltv_delta`, then either: 1. JIT-Routing cannot be done since the rebalancing requires more blocks than is allocated to the hop, 2. OR, JIT-Routing is done despite the lack of blocks, at the major risk of possibly getting attacked by fooling around with lock times. Decorrelation could remove the risk in #2. -- So let us consider the below simple network graph: A - B - D - E | | | | +-- C --+ Let us pretend that C-Lightning has taken over the world and that everyone uses a sensible 14-block `cltv_delta`. The node B receives an onion from A, with the specs: 1. A offers an HTLC to B with value 1001 msat, and timelocked in 70 blocks from now. 2. B should offer an HTLC to D with value 1000 msat, and timelocked in 56 blocks from now. As it happens, B has not enough money in channel B-D, but can augment it with money from B-C by rebalancing. If it's the original Pickhardt JIT-Routing, then B takes on the risk that a later hop in the onion will fail, however it can complete the rebalancing without caring about the timelocks of the "actual" route. However, if we reuse the payment preimage, and use the "reverse the polarity" operation proposed by Pickhardt in response to Luaces, then we need to respect the timelocks. In particular, even the rebalance nodes C and D will impose `cltv_delta`. Note that C and D have 14 blocks each, but what is allocated to B is only 14 blocks for itself. Suppose we consider --- since the "reverse the polarity" operation means there are HTLCs from B->D and B->C->D, then it should be safe to have the B->C->D->B path have a longer timelock on the first HTLC; the B->D direct HTLC would still allow B to claim the money from A. So B would do: 1. It receives the onion from A and finds it has insufficient capacity on B-D channel. 2. It creates a new onion B->C->D->B, with timelocks: a. D->B now+56 (this will be reversed into a B->D HTLC with timelock now+56) b. C->D now+70 c. B->C now+84 3. B sends the above onion, using the same payment hash as the original onion. Now suppose A, D, and C are actually controlled by an evil person Eve. Eve knows the original onion and in particular knows the original payment hash and preimage. In addition, it knows the condition of channels B-C and B-D. So Eve attacks as below: 1. C stalls until now+71. a. The original A->N HTLC (with timeout now+70) is invalidated. b. The B->C HTLC (with timeout now+84) is still valid. 2. C claims the amount in the B->C HTLC. Even if B refuses, C can always settle it onchain. Now of course B might not choose the specific C controlled by Eve in the rebalance. But note that D can keep failing incoming HTLCs from all nodes until either B selects the C that Eve controls, or B gives up (in which case Eve loses nothing anyway). So B cannot safely use the "reverse the polarity" operation, unless the onion gives it much more time than its `cltv_delta` declares. But if nodes boost their `cltv_delta`s, then it also becomes impossible to JIT-route. And if we give each hop node more than their declared `cltv_delta`, then that increases the risk on the source node (since the total time it gives to all hop nodes is the maximum amount of time that its money could be locked in the worst case). A similar attack on D can be mounted (by B, C, and E) if we adjust the timelocks in the opposite direction. In conclusion, the "reverse the polarity" operation is not feasible for JIT-Routing. Instead, the hop node B needs to incur the entire risk in rebalancing. It also means that the JIT-Routing technique cannot be used by unidirectional-only implementations like Eclair Mobile. -- > An intermediate route node could decide for any reason to re-route a payment > through any subset of nodes to arrive at the next hop. This is similar to > Rene's local AMP idea where friend-of-a-friend nodes are used. But instead > this system could allow arbitraryly long paths to the next hop by finding a > new sub-route and re-layering the onion packet with the new sub-route > prepended. This requires "Rendezvous Routing", which cdecker and cjp are working on; there is something something math involved. In particular it requires switching to some other point in the onion encryption; sorry, I am not enough of a mathist to tell you what that means. The problem with this is again that timelocks need to be respected. If a hop node cannot find a route that fits its own time risk and the time risk allocated to it by the source payer. R
Re: [Lightning-dev] Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0
Good morning list I have been thinking about how JIT-Routing can allow the network to be more private and scalable than it currently is today. Rene has mentioned that JIT-Routing allows channel balance information to affect pathing decisions without the source node being aware. I would take this further and suggest that JIT-Routing can allow routing over sub-paths that are only visible to neighbour nodes and are entirely hidden from the source node or plublic view. An intermediate route node could decide for any reason to re-route a payment through any subset of nodes to arrive at the next hop. This is similar to Rene's local AMP idea where friend-of-a-friend nodes are used. But instead this system could allow arbitraryly long paths to the next hop by finding a new sub-route and re-layering the onion packet with the new sub-route prepended. The same pre-image would be used and this process would be completely invisible to the next hop (original next hop, not the new next hop in the sub-route, I would instead call those the sub-hops). It's unfortunate that the intermediate nodes along the sub-route would be aware that a sub-route is being attempted because they could observe extra hop packets prepended to the minimum twenty and I don't see of a way to fix this. But maybe it doesn't need fixing since the original twenty encryption layers are arguably private enough. The sub-route could also employ base AMP since the same pre-image is used. The next hop node would still never even know that a subroute was attempted if no "wait for more payments" flag is added to the per_hop field and we implement the "wait for timeout if HTLC is less than amt_to_forward" rule. Public nodes could advertise channels which don't actually exist directly but are instead hidden paths that the source node doesn't need to know or care about. The fees advertised for these aggregate-channels would be the aggregate fees expected from the sub-route. I think the biggest gain from this system is that the network can be more abstract. This abstraction allows all possible subsets of public nodes to be a clique since all subsets of nodes can be maximally connected with aggregate-channels as long as the entire network is well connected. This new property of the network could allow a source node to select a random privacy-clique and rely on payments to be routed along aggregate-channels without the source node needing to compute or even know the exact sub-routes. Futhermore, the source node could exclusively download and listen to the privacy-clique and ignore the rest of the network structure thus reducing the burden of keeping up to date network information. Cheers Ariel Lorenzo-Luaces On Mar 22, 2019, 4:44 AM, at 4:44 AM, ZmnSCPxj via Lightning-dev wrote: >Good morning list, > >I have been thinking of JIT-Routing in the context of unidirectional >channels, as for example in Eclair Mobile. >Now of course unidirectional-only nodes as in Eclair Mobile cannot >forward and cannot be intermediate nodes. >However, as I pointed out in previous email, the same JIT-Routing can >be used also when the node is the ultimate source of the payment. > >The original formulation, which requires a separate, completed >rebalance, before performing a payment, cannot be used in >unidirectional mode. >It requires that the channel to be boosted by the rebalance, must first >receive the value, which is disallowed in unidirectional mode. > >However, the Luaces-Pickhardt JIT-Routing, which has a conditional >rebalance, does not require that the channel receive. >So it seems to me, that the Luaces-Pickhardt JIT-Routing can work with >Eclair. > >Let us consider the following history: > >1. An Eclair Mobile client creates a 1mBTC channel. >2. The client successfully pays an unrelated payment of 0.5 mBTC. >3. The client has to make another payment of 0.6 mBTC, to be passed by >this channel. >The client has another channel which can pay out the needed 0.15mBTC >(additional 0.05mBTC needed for the channel reserve). >4. The second payment passes. > >In the below sequence of states, A is the Eclair Mobile client node, >while B is the counterparty. > >1. A = 1.0, B = 0.0 ; starting state. >2. A = 0.5, B = 0.0, A->HTLC->B = 0.5 ; client offers payment in #2 >above. >3. A = 0.5, B = 0.5 ; payee accepts payment. >4. A = 0.5, B = 0.35, B->HTLC->A = 0.15 ; the rebalance from another >channel of A, initiated by #3 above. >5. A = 0.05, B = 0.5, A->HTLC->B = 0.45 ; HTLC polarity reversed by A >offering an HTLC of 0.6 BTC (the new mechanism proposed by Rene). >6. A = 0.05, B = 0.95 ; payee accepts payment. > >As can be seen from above, A will never have an increase in its money. > >Thus, the new Luaces-Pickhardt formulation of JIT-Routing, which >requires the new "reverse HTLC polarity" mechanism to reuse the same >hash as the actual payment, should be safe for unidirectional Eclair >Mobile nodes. > >Let us consider the following seque
Re: [Lightning-dev] Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0
Good morning list, I have been thinking of JIT-Routing in the context of unidirectional channels, as for example in Eclair Mobile. Now of course unidirectional-only nodes as in Eclair Mobile cannot forward and cannot be intermediate nodes. However, as I pointed out in previous email, the same JIT-Routing can be used also when the node is the ultimate source of the payment. The original formulation, which requires a separate, completed rebalance, before performing a payment, cannot be used in unidirectional mode. It requires that the channel to be boosted by the rebalance, must first receive the value, which is disallowed in unidirectional mode. However, the Luaces-Pickhardt JIT-Routing, which has a conditional rebalance, does not require that the channel receive. So it seems to me, that the Luaces-Pickhardt JIT-Routing can work with Eclair. Let us consider the following history: 1. An Eclair Mobile client creates a 1mBTC channel. 2. The client successfully pays an unrelated payment of 0.5 mBTC. 3. The client has to make another payment of 0.6 mBTC, to be passed by this channel. The client has another channel which can pay out the needed 0.15mBTC (additional 0.05mBTC needed for the channel reserve). 4. The second payment passes. In the below sequence of states, A is the Eclair Mobile client node, while B is the counterparty. 1. A = 1.0, B = 0.0 ; starting state. 2. A = 0.5, B = 0.0, A->HTLC->B = 0.5 ; client offers payment in #2 above. 3. A = 0.5, B = 0.5 ; payee accepts payment. 4. A = 0.5, B = 0.35, B->HTLC->A = 0.15 ; the rebalance from another channel of A, initiated by #3 above. 5. A = 0.05, B = 0.5, A->HTLC->B = 0.45 ; HTLC polarity reversed by A offering an HTLC of 0.6 BTC (the new mechanism proposed by Rene). 6. A = 0.05, B = 0.95 ; payee accepts payment. As can be seen from above, A will never have an increase in its money. Thus, the new Luaces-Pickhardt formulation of JIT-Routing, which requires the new "reverse HTLC polarity" mechanism to reuse the same hash as the actual payment, should be safe for unidirectional Eclair Mobile nodes. Let us consider the following sequence of events: 1. An Eclair Mobile client creates a 1mBTC channel. 2. The client successfully pays an unrelated payment of 0.5 mBTC. 3. The client has to make another payment of 0.6 mBTC, to be passed by this channel. The client has another channel which can pay out the needed 0.15mBTC (additional 0.05mBTC needed for the channel reserve). 4. The second payment fails. Then the sequence of states is: 1. A = 1.0, B = 0.0 ; starting state. 2. A = 0.5, B = 0.0, A->HTLC->B = 0.5 ; client offers payment in #2 above. 3. A = 0.5, B = 0.5 ; payee accepts payment. 4. A = 0.5, B = 0.35, B->HTLC->A = 0.15 ; the rebalance from another channel of A, initiated by #3 above. 5. A = 0.05, B = 0.5, A->HTLC->B = 0.45 ; HTLC polarity reversed by A offering an HTLC of 0.6 BTC (the new mechanism proposed by Rene). 6. A = 0.5, B = 0.5 ; payment fails. Now in the above, the only state that has A own less money than in a later state is state 5. However, even if we are at state 6, and B replays state 5, B cannot claim the A->HTLC->B (if it had the hash, it would have claimed the HTLC instead of failing it), so it will revert back to A when it times out. This is the same as existing cases of payment failure in Eclair Mobile, so presumably if it has a problem here, it would have a problem in existing Eclair Mobile unidirectional channels. Thus, it should be safe to use the Luaces-Pickhardt JIT-Routing in unidirectional-only nodes, even if the original Pickhardt JIT-Routing is unsafe for unidirectional-only nodes. Thus this is a plausible replacement for all forms of multipart payments. In effect, instead of a multipart payment being decided by the source to the destination, we have each hop, including the source, deciding to split or not split the payment according to how much fee it has to devote to rebalance attempts. Regards, ZmnSCPxj ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0
Good morning all, I have been thinking further about JIT-Routing. Particularly, the extension of Rene of the idea from Ariel, to use the same payment hash (payment point in the future). I observe that this effectively creates a sort of "local bass amplifier" multipath payment. >From this idea, also: > > If a node N offers an htlc to a partner with an amount x from whom the node > > already received an htlc y (where y is smaller than x) the nodes must > > create a new channel state discarding the old htlc but having a new offer > > from N with the amount x-y. I think we should consider also the possibility of multiple HTLCs "y" above. For instance, the node may not have enough liquidity in any single channel to fulfill the forward, or even augment its channel(s) to that node from a single other channel. However the node may have multiple channels, which in aggregate may have enough liquidity to fulfill the forward on the channel(s) to the next node in the onion hop. Implementation-wise, it means: 1. An outgoing HTLC may need to be associated with multiple incoming HTLCs. 2. An incoming payment may need to be associated with multiple incoming HTLCs (this is a prerequisite of all forms of multipath payment, whether bass amplifier or AMP). 3. An outgoing HTLC may need to be deleted, and all its associated incoming HTLCs re-associated to either a new outgoing HTLC or an incoming payment. 3.1. Multiple such outgoing HTLCs may be deleted in a single step, and all their incoming HTLCs will be re-assocaited. In future, when moving to points/scalars, we need to reveal for each HTLC we want to reverse, the total decorrelation secret that makes them each claimable by knowledge of the point, of the new HTLC we want to reverse. --- But first, let us consider, is there a need for JIT-Routing? I have always held that failure of a single routing attempt is not very important, as multiple routing attempts can be performed in sequence, and as long as any *single* attempt completes, then the payment succeeds. However, in a world where some kind of multipart payment (whether bass amplifier or AMP) is in frequent use, this changes. A failure of a single routing attempt may delay the completion of a multipart payment, as it means that the source has to retry that branch of the multipart payment. In short, *all* attempts must succeed for a multipart payment to succeed. It would be nice if we can perform re-routing in order to help multipart payments succeed without so much coordination at the source. This is why Rendezvous Routing is of interest to me, since (naively) it seems to me that re-routing is possible with Rendezvous. However, it seems that JIT-Routing, as modified by Rene based on idea of Ariel, does much of what Rendezvous Routing would do for re-routing. (Rendezvous Routing is still independently of value for privacy of receivers as well as moving fee payment from senders to receivers in the "withdrawal from custodial wallet" case.) So I think this JIT-Routing would synergize quite well with bass amplifier and AMP. It effectively allows forwarding nodes to independently split a forwarding attempt across multiple paths, without participation of source. -- Now, we can also consider how to better support JIT-Routing. I observe that in C-Lightning, the high-level `pay` command provides a `maxfeepercent` argument. C-Lightning considers "fee" here as "anything we send out beyond the face value of the invoice". Currently, in addition to capping fees, it is also used to do small overpayments at the receiver. Now of course an intermediate node will only do JIT-Routing if the cost of rebalancing is less than the fee it receives for that forward. So one thing the source node can do, to help JIT-routing, is to overpay fees at each intermediate node a little. Obviously this overpayment should be capped by the overall `maxfeepercent`. This improves the probability that it is practical for an intermediate node to do JIT-routing. -- I now put forward the most radical idea of all. *Multipart payment support is **not necessary** if we have widespread JIT-Routing support.* The motivating problem for proposing AMP, and its improvement bass amplifier, is to simplify user experience by not having the user consider the balance of each channel. Instead, ideally the user only cares about the total spendable balance they have, without a care about how it is distributed in its channels. I observe that this is an extremely local condition. I also observe that a core insight in JIT-Routing is that an intermediate node knows more about its local conditions than the source node. So from the start, the source node can start its thinking as if it is an intermediate node. Thus, if the source node wants to make a payment of 1mBTC, but has 1.5mBTC scattered in various channels, it can act as if it is forwarding 1mBTC. Then it can perform the conditional rebalances in the modified JIT
Re: [Lightning-dev] Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0
Good morning Rene and Ariel, > Hey everyone, > > I am glad the suggestion is being picked up. At this time I want to respond > to two of the concerns that have been thrown in. I have some other comments > and ideas but would like to hold them back so that we can have more people > joining the discussion without bias also this mail will already be quite long. > > ZmnSCPxj suggested to introduce a `success_rate` for JIT routing. While this > success_rate can obviously only be estimated or configured I would advice > against including this to the protocol. As I mentioned before I suggested to > include JIT Routing as a MAY Recommendation so it is up to the node to decide > if it cannot earn `offered_fee_amount` to engage in the JIT-rebalancing > operation. I think it is beyond the scope of the protocol specs to specify this. However, we should remember that it is not the protocol specs that is running on the actual network, but actual implementations. Thus the exact rule may need discussion nevertheless, as it may affect the ability to attack actual implementations on the network. > A node operator might be willing in general to to pay a fee for rebalancing > even if there is not an outstanding routing event taking place. So even while > `rebalancing_fee_amount` > `offered_fee_amount` the node could see the > offered_fee_amount as a discount for the planned rebalancing amount. We don't > know that and I honestly believe that the protocol should not make economical > decisions for the node. In any case rebalancing will overall increase the > likelihood for successful routing but it makes sense to defer the rebalancing > operation to a moment in which the liquidity is actually needed. > > Regarding Ariels suggestion about reusing the payment hash with JIT Routing I > have some more thoughts: > Reusing the payment hash indeed seems like a good idea. However it produces > some technical issues which in my opinion can all be mitigated. it is just a > question with these challenges if it is worthwhile doing it? > > I have drawn several situations and tried to construct an example in which > using the same payment hash for the JIT-rebalancing would result in a severe > problem with the payment process in the sense that it would be compromised or > somebody could steal funds. It could however be a privacy issue as more nodes > are being aware of the same payment (but that is also the case with base-AMP) This would be fixable when we switch to points and scalars (from hashes and preimages) and enable route decorrelation, just as it would improve base-AMP. > I was not able to construct such a situation (under the assumption that the > rebalancing amount does not exceed the original payment amount). My feeling > (though I have not done this yet) is that one should be able to proof that > taking the same payment hash would always work and in fact create a situation > in which at least the rebalancing only takes place if the entire payment was > routed successfully. > > Assuming someone will be able to proof that using the same payment hash for > JIT Routing is not an issue we still run into another problem (which I > believe can be fixed with another MUST rule but comes with quite some > implementation overhead.) > > The deadlock problem when doing JIT Routing with the same payment hash: > When using the same payment hash there will be two htlc's (potentially of > different amounts) in opposing directions on the same channel (or in the lnd > case maybe between separate channels between the same two peers). Unluckily > without a novel rule this can produce a deadlock. > > As an example take the situation from my initial email with an additional > recipient R1: > > 100 / 110 80 / 200 150/180 > S --> B > R --> R1 > \ / > 80/200 \ / 100/200 > \ / > T > > Meaning we have the following channels: > S ---> B capacity: 110 A funds: 100 B funds: 10 > B ---> R capacity: 200 B funds: 80 R funds: 120 > B ---> T capacity: 200 B funds: 80 T funds: 120 > T ---> R capacity: 200 T funds: 100 R funds: 100 > R ---> R1 capacity: 180 R funds: 150 R1 funds: 30 > > neglecting fees the following htlcs would be offered > 1.) S-->B amount: 90 > 2.) B-->T amount:50 > 3.) T-->R amount:50 > 4.) R-->B amount: 50 > 5.) B-->R amount: 90 (difficult to set up before 4. settles) > 6.) R-->R1 amount: 90 > > while 1,5 and 6 are the original path 2,3,4 are the JIT rebalancing. > > We see that in this situation using the same preimage results in a problem. > Since the rebalancing is not settled R will not accept the 5th htlc (B--->R > amount: 90) as there is not enough liquidity on B's side producing a deadlock > However since the same payment hash is used it is save to combine the 4th and > 5th htlc to have the following situation: > > 1.) S-->B amount: 90 > 2.) B-->T amount:5
Re: [Lightning-dev] Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0
Hey everyone, I am glad the suggestion is being picked up. At this time I want to respond to two of the concerns that have been thrown in. I have some other comments and ideas but would like to hold them back so that we can have more people joining the discussion without bias also this mail will already be quite long. ZmnSCPxj suggested to introduce a `success_rate` for JIT routing. While this success_rate can obviously only be estimated or configured I would advice against including this to the protocol. As I mentioned before I suggested to include JIT Routing as a MAY Recommendation so it is up to the node to decide if it cannot earn `offered_fee_amount` to engage in the JIT-rebalancing operation. A node operator might be willing in general to to pay a fee for rebalancing even if there is not an outstanding routing event taking place. So even while `rebalancing_fee_amount` > `offered_fee_amount` the node could see the offered_fee_amount as a discount for the planned rebalancing amount. We don't know that and I honestly believe that the protocol should not make economical decisions for the node. In any case rebalancing will overall increase the likelihood for successful routing but it makes sense to defer the rebalancing operation to a moment in which the liquidity is actually needed. Regarding Ariels suggestion about reusing the payment hash with JIT Routing I have some more thoughts: Reusing the payment hash indeed seems like a good idea. However it produces some technical issues which in my opinion can all be mitigated. it is just a question with these challenges if it is worthwhile doing it? I have drawn several situations and tried to construct an example in which using the same payment hash for the JIT-rebalancing would result in a severe problem with the payment process in the sense that it would be compromised or somebody could steal funds. It could however be a privacy issue as more nodes are being aware of the same payment (but that is also the case with base-AMP) I was not able to construct such a situation (under the assumption that the rebalancing amount does not exceed the original payment amount). My feeling (though I have not done this yet) is that one should be able to proof that taking the same payment hash would always work and in fact create a situation in which at least the rebalancing only takes place if the entire payment was routed successfully. Assuming someone will be able to proof that using the same payment hash for JIT Routing is not an issue we still run into another problem (which I believe can be fixed with another MUST rule but comes with quite some implementation overhead.) The deadlock problem when doing JIT Routing with the same payment hash: When using the same payment hash there will be two htlc's (potentially of different amounts) in opposing directions on the same channel (or in the lnd case maybe between separate channels between the same two peers). Unluckily without a novel rule this can produce a deadlock. As an example take the situation from my initial email with an additional recipient R1: 100 / 110 80 / 200 150/180 S --> B > R --> R1 \ / 80/200 \ / 100/200 \ / T Meaning we have the following channels: S ---> B capacity: 110 A funds: 100 B funds: 10 B ---> R capacity: 200 B funds: 80 R funds: 120 B ---> T capacity: 200 B funds: 80 T funds: 120 T ---> R capacity: 200 T funds: 100 R funds: 100 R ---> R1 capacity: 180 R funds: 150 R1 funds: 30 neglecting fees the following htlcs would be offered 1.) S-->B amount: 90 2.) B-->T amount:50 3.) T-->R amount:50 4.) R-->B amount: 50 5.) B-->R amount: 90 (difficult to set up before 4. settles) 6.) R-->R1 amount: 90 while 1,5 and 6 are the original path 2,3,4 are the JIT rebalancing. We see that in this situation using the same preimage results in a problem. Since the rebalancing is not settled R will not accept the 5th htlc (B--->R amount: 90) as there is not enough liquidity on B's side producing a deadlock However since the same payment hash is used it is save to combine the 4th and 5th htlc to have the following situation: 1.) S-->B amount: 90 2.) B-->T amount:50 3.) T-->R amount:50 4.) R-->B will be removed or settled or replaced by the 5th htlcs with a different amount (90 - 50) 5.) B-->R amount: 40 6.) R-->R1 amount: 90 Note that while theoretically it seems tempting to just have two htlc outputs as the second node could always claim the htlc if the first claims theirs. However this will not work onchain as potentially more funds are spend than exist. Therefor we need a MUST-rule to fix the deadlock problem (which could probably also be formulated in a symmetric way): If a node N offers an htlc to a partner with an amount x from whom the node already received an htlc y (where y is smaller than x) the nodes must create a new channel state discarding the old htlc but
Re: [Lightning-dev] Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0
Hello Rene, ZmnSCPxj, and list I really like the proposal and I'm sure it's the correct way forward for reducing payment failures and increasing privacy (through mitigating probing based network analysis) However I am concerned that this proposal could introduce a vulnerability to a spoofed-payment attack. An adversary could create a malicious payment that's guaranteed to fail, for free. Any intermediary nodes on the path of the payment before it fails could lose fees due to rebalancing if the rebalancing path's success is not dependent on the original payment's success. Could anyone speak to this and confirm whether it would be possible for the rebalancing step to reuse the original payment hash? If this is possible then it should explicitly be included in this proposal. If reusing the payment hash is not possible on the routing path then JIT routing would need some other mitigation for the spoofed-payment attack. Cheers Ariel Lorenzo-Luaces On Mar 14, 2019, 7:45 AM, at 7:45 AM, ZmnSCPxj via Lightning-dev wrote: >Good morning Rene and list, > >Let us consider then the rule *when* a rebalancing would be beneficial >to the node. > >The node is offered a fee amount (`offered_fee_amount`) for the >forwarding. >It knows that, under current channel states, it will definitely have to >fail and earn 0 fees. > >If it engages in JIT-routing, it must pay some fee >(`rebalancing_fee_amount`) for the rebalancing operation. >But even if it successfully forwards its hop, it is still possible that >the route will fail anyway and it will earn 0 fees. > >So let us consider the probability of success (`success_rate`), a value >between 0 to 1.0. >This is the estimated probability that we will succeed the route after >we forward it. > >We should only engage in JIT-routing if: > >offered_fee_amount * success_rate - rebalancing_fee_amount > 0 > >The LHS of the subtraction is the expected earning, while the RHS of >the subtraction is the expected cost. >The above is trivial accounting for determining net earnings. > >The fee amounts are trivially computable. >Presumably the rebalancing code can compute the fee given a particular >rebalance path, and thus can provide `rebalancing_fee_amount`. > >The `success_rate` can be computed statically from some node data. >Better, is for the node to start with this precomputed static >information, but augment this over time with its own experienced >`success_rate` for all forwards. > >Regards, >ZmnSCPxj >___ >Lightning-dev mailing list >Lightning-dev@lists.linuxfoundation.org >https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0
Good morning Rene and list, Let us consider then the rule *when* a rebalancing would be beneficial to the node. The node is offered a fee amount (`offered_fee_amount`) for the forwarding. It knows that, under current channel states, it will definitely have to fail and earn 0 fees. If it engages in JIT-routing, it must pay some fee (`rebalancing_fee_amount`) for the rebalancing operation. But even if it successfully forwards its hop, it is still possible that the route will fail anyway and it will earn 0 fees. So let us consider the probability of success (`success_rate`), a value between 0 to 1.0. This is the estimated probability that we will succeed the route after we forward it. We should only engage in JIT-routing if: offered_fee_amount * success_rate - rebalancing_fee_amount > 0 The LHS of the subtraction is the expected earning, while the RHS of the subtraction is the expected cost. The above is trivial accounting for determining net earnings. The fee amounts are trivially computable. Presumably the rebalancing code can compute the fee given a particular rebalance path, and thus can provide `rebalancing_fee_amount`. The `success_rate` can be computed statically from some node data. Better, is for the node to start with this precomputed static information, but augment this over time with its own experienced `success_rate` for all forwards. Regards, ZmnSCPxj ___ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Re: [Lightning-dev] Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0
Good morning Rene, The base idea is good at first glance. However, let us consider this situation: 0.1 1.0 A - B 1.5 | / 0.5 |/ | / | / | / |/ | / | / 0.5 | / 0.75 C A must pay B, 1.0 BTC. A knows the exact state of AB and AC channels, but only knows that BC has total 1.25 capacity. A sends via route A->C->B. It knows that it has sufficient capacity in AC. It also knows that the total capacity in CB has a chance of transferring 1.0BTC. So what happens (let us assume Lightning fees are negligible). 1. A locks 1.0 in AC in an HTLC. 2. C cannot forward since it has only 0.75 in CB. It initiates a rebalance. 3. C notices it has 0.5 BTC in AC. It can transfer 0.25BTC from AC to CB to be able to get 1.0 in CB that it can forward. So it routes 0.25 BTC via C->A->B->C. 4. C locks 0.25 in CA in an HTLC. 5. A cannot forward the C->A->B->C payment since it only has 0.1BTC in AB. It initiates a rebalance. 6. A notices it has 0.5 BTC in AC (1.0 is currently locked in an HTLC, leaving it 0.5BTC). It can transfer 0.15BTC in AC to AB to be able to get 0.25 in AC that it can forward. So it routes 0.15 BTC via A->C->B->C. 7. A locks 0.15 in AC in an HTLC. 8. C is now in a bind. If it forwards the 0.15 BTC, then it will still fail the earlier A->C->B 1.0 payment. This is because it will lose 0.15 BTC from its side here, leading to 0.6 BTC, then receive 0.25 BTC from the rebalance, only having 0.85 BTC. If it does not forward, A is unable to rebalance and fails the rebalance of C, which fails the original payment from A->C->B. Thus it seems to me, that precisely because of the lack of a global view, such kinds of complicated HTLC networks will form, then still lead to payment failure. -- Perhaps it is better to consider that a high-level payment failure requires failure of all possible routes. From that point of view, a failure of a single payment attempt is not a big deal. -- With that said, it may still be valuable to try doing this. It will massively increase the complexity in c-lightning. We would need a new persistent db table (meaning not in Python, at least until we make c-lightning into a bus connecting its actual running components that send commands to each other via the same bus that external commands and plugins use). Then we can evaluate a small network of such nodes on mainnet LN and see how often rebalance failures occur. Regards, ZmnSCPxj ‐‐‐ Original Message ‐‐‐ On Tuesday, March 5, 2019 9:47 PM, René Pickhardt via Lightning-dev wrote: > Hey everyone, > > In this mail I introduce the Just in Time Routing schema (aka JIT Routing). > Its main idea is to mitigate the disadvantages from our current source based > routing (i.e.: guessing a route that will work in the sense that it has > enough liquidity in each channel) and make the routing process a little bit > more like the best effort routing that we know from IP-forwarding. As far as > I know this will not decrease the privacy of the nodes. As part of this > Routing scheme nodes need to be able to quickly rebalance their channels. > Thus in this mail I also propose a heuristic for doing this efficiently which > I have implemented and seems to provide pretty good results. Obviously the > heuristic should be tested with the help of a simulation. I did not have the > chance to do that yet. Partly also because I am lacking a proper dataset and > I don't want to do this on artificial data. > > The advantages of JIT Routing are: > * it is possible to do now without any protocol modification. In particular > no modifications of the onions are necessary. > * routing nodes can already easily implement it. By implementing it they will > increase the routing success even for nodes which are running older > implementations > * it seems to be logically equivalent to AMP Routing. In particular its > properties will also help base AMP once it is part of the protocol. > * local channel balance information along the route can now be part of the > path finding process while not decreasing the privacy by sharing information > about channel balances with others. In fact the privacy of nodes is even > being increased. > > The disadvantages seem: > * it might economically not be incentivized for a routing node in every > situation. Theoretically it can even happen that a node pays a fee in order > to use this technique but can't earn the routing fee as the onion fails > later. Nodes can implement risk management strategies to mitigate this issue. > * The routing process might take a longer time as it starts sub routing > processes. > * While doing JIT routing the capacity for channels should be reserved even > before HTLCs are set up (to prevent hostile recursive chains of rebalancing > operations) > > Obviously routing single big