From bb4364192aeb47a12186ea89a8600cefa73c2311 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Thu, 25 Feb 2021 16:56:40 -0500 Subject: [PATCH] Track full-path htlc-minimum-msat while routing Previously, we'd happily send funds through a path where, while generating the path, in some middle hope we reduce the value being sent to meet an htlc_maximum, making a later hop invalid due to it no longer meeting its htlc_minimum. Instead, we need to track the path's htlc-minimum while we're transiting the graph. --- lightning/src/routing/router.rs | 39 ++++++++++++++++++++------------- 1 file changed, 24 insertions(+), 15 deletions(-) diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index 8c892e695..ac7576b00 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -141,7 +141,10 @@ struct RouteGraphNode { // - how much is needed for a path being constructed // - how much value can channels following this node (up to the destination) can contribute, // considering their capacity and fees - value_contribution_msat: u64 + value_contribution_msat: u64, + /// The maximum htlc_minimum_msat along the path, taking into consideration the fees required + /// to meet the minimum over the hops required to get there. + path_htlc_minimum_msat: u64, } impl cmp::Ord for RouteGraphNode { @@ -433,7 +436,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // $next_hops_fee_msat represents the fees paid for using all the channel *after* this one, // since that value has to be transferred over this channel. ( $chan_id: expr, $src_node_id: expr, $dest_node_id: expr, $directional_info: expr, $capacity_sats: expr, $chan_features: expr, $next_hops_fee_msat: expr, - $next_hops_value_contribution: expr ) => { + $next_hops_value_contribution: expr, $incl_fee_next_hops_htlc_minimum_msat: expr ) => { // Channels to self should not be used. This is more of belt-and-suspenders, because in // practice these cases should be caught earlier: // - for regular channels at channel announcement (TODO) @@ -495,6 +498,8 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // Can't overflow due to how the values were computed right above. None => unreachable!(), }; + let over_path_minimum_msat = amount_to_transfer_over_msat >= $directional_info.htlc_minimum_msat && + amount_to_transfer_over_msat >= $incl_fee_next_hops_htlc_minimum_msat; // If HTLC minimum is larger than the amount we're going to transfer, we shouldn't // bother considering this channel. @@ -502,7 +507,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // be only reduced later (not increased), so this channel should just be skipped // as not sufficient. // TODO: Explore simply adding fee to hit htlc_minimum_msat - if contributes_sufficient_value && amount_to_transfer_over_msat >= $directional_info.htlc_minimum_msat { + if contributes_sufficient_value && over_path_minimum_msat { let hm_entry = dist.entry(&$src_node_id); let old_entry = hm_entry.or_insert_with(|| { // If there was previously no known way to access @@ -574,6 +579,10 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye lowest_fee_to_peer_through_node: total_fee_msat, lowest_fee_to_node: $next_hops_fee_msat as u64 + hop_use_fee_msat, value_contribution_msat: value_contribution_msat, + path_htlc_minimum_msat: match compute_fees($incl_fee_next_hops_htlc_minimum_msat, $directional_info.fees) { + Some(fee_msat) => cmp::max(fee_msat, $directional_info.htlc_minimum_msat), + None => u64::max_value(), + }, }; // Update the way of reaching $src_node_id with the given $chan_id (from $dest_node_id), @@ -633,10 +642,10 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // meaning how much will be paid in fees after this node (to the best of our knowledge). // This data can later be helpful to optimize routing (pay lower fees). macro_rules! add_entries_to_cheapest_to_target_node { - ( $node: expr, $node_id: expr, $fee_to_target_msat: expr, $next_hops_value_contribution: expr ) => { + ( $node: expr, $node_id: expr, $fee_to_target_msat: expr, $next_hops_value_contribution: expr, $incl_fee_next_hops_htlc_minimum_msat: expr ) => { if first_hops.is_some() { if let Some(&(ref first_hop, ref features, ref outbound_capacity_msat)) = first_hop_targets.get(&$node_id) { - add_entry!(first_hop, *our_node_id, $node_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), $fee_to_target_msat, $next_hops_value_contribution); + add_entry!(first_hop, *our_node_id, $node_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), $fee_to_target_msat, $next_hops_value_contribution, $incl_fee_next_hops_htlc_minimum_msat); } } @@ -656,7 +665,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye if first_hops.is_none() || chan.node_two != *our_node_id { if let Some(two_to_one) = chan.two_to_one.as_ref() { if two_to_one.enabled { - add_entry!(chan_id, chan.node_two, chan.node_one, two_to_one, chan.capacity_sats, chan.features, $fee_to_target_msat, $next_hops_value_contribution); + add_entry!(chan_id, chan.node_two, chan.node_one, two_to_one, chan.capacity_sats, chan.features, $fee_to_target_msat, $next_hops_value_contribution, $incl_fee_next_hops_htlc_minimum_msat); } } } @@ -664,7 +673,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye if first_hops.is_none() || chan.node_one != *our_node_id { if let Some(one_to_two) = chan.one_to_two.as_ref() { if one_to_two.enabled { - add_entry!(chan_id, chan.node_one, chan.node_two, one_to_two, chan.capacity_sats, chan.features, $fee_to_target_msat, $next_hops_value_contribution); + add_entry!(chan_id, chan.node_one, chan.node_two, one_to_two, chan.capacity_sats, chan.features, $fee_to_target_msat, $next_hops_value_contribution, $incl_fee_next_hops_htlc_minimum_msat); } } @@ -690,7 +699,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // place where it could be added. if first_hops.is_some() { if let Some(&(ref first_hop, ref features, ref outbound_capacity_msat)) = first_hop_targets.get(&payee) { - add_entry!(first_hop, *our_node_id, payee, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, recommended_value_msat); + add_entry!(first_hop, *our_node_id, payee, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, recommended_value_msat, 0); } } @@ -703,7 +712,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // If not, targets.pop() will not even let us enter the loop in step 2. None => {}, Some(node) => { - add_entries_to_cheapest_to_target_node!(node, payee, 0, recommended_value_msat); + add_entries_to_cheapest_to_target_node!(node, payee, 0, recommended_value_msat, 0); }, } @@ -722,7 +731,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // bit lazy here. In the future, we should pull them out via our // ChannelManager, but there's no reason to waste the space until we // need them. - add_entry!(first_hop, *our_node_id , hop.src_node_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, recommended_value_msat); + add_entry!(first_hop, *our_node_id , hop.src_node_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, recommended_value_msat, 0); true } else { // In any other case, only add the hop if the source is in the regular network @@ -732,17 +741,17 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye if have_hop_src_in_graph { // BOLT 11 doesn't allow inclusion of features for the last hop hints, which // really sucks, cause we're gonna need that eventually. - let last_hop_htlc_minimum_msat: u64 = match hop.htlc_minimum_msat { + let last_path_htlc_minimum_msat: u64 = match hop.htlc_minimum_msat { Some(htlc_minimum_msat) => htlc_minimum_msat, None => 0 }; let directional_info = DummyDirectionalChannelInfo { cltv_expiry_delta: hop.cltv_expiry_delta as u32, - htlc_minimum_msat: last_hop_htlc_minimum_msat, + htlc_minimum_msat: last_path_htlc_minimum_msat, htlc_maximum_msat: hop.htlc_maximum_msat, fees: hop.fees, }; - add_entry!(hop.short_channel_id, hop.src_node_id, payee, directional_info, None::, ChannelFeatures::empty(), 0, recommended_value_msat); + add_entry!(hop.short_channel_id, hop.src_node_id, payee, directional_info, None::, ChannelFeatures::empty(), 0, recommended_value_msat, 0); } } @@ -759,7 +768,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // Both these cases (and other cases except reaching recommended_value_msat) mean that // paths_collection will be stopped because found_new_path==false. // This is not necessarily a routing failure. - 'path_construction: while let Some(RouteGraphNode { pubkey, lowest_fee_to_node, value_contribution_msat, .. }) = targets.pop() { + 'path_construction: while let Some(RouteGraphNode { pubkey, lowest_fee_to_node, value_contribution_msat, path_htlc_minimum_msat, .. }) = targets.pop() { // Since we're going payee-to-payer, hitting our node as a target means we should stop // traversing the graph and arrange the path out of what we found. @@ -856,7 +865,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye match network.get_nodes().get(&pubkey) { None => {}, Some(node) => { - add_entries_to_cheapest_to_target_node!(node, &pubkey, lowest_fee_to_node, value_contribution_msat); + add_entries_to_cheapest_to_target_node!(node, &pubkey, lowest_fee_to_node, value_contribution_msat, path_htlc_minimum_msat); }, } } -- 2.39.5