X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=655a53c2dfeab3007c4660f74f04a67022066db6;hb=a316ef45960314cdfe03ab57695c1aee5d9189a6;hp=ed3c07595b0ebc39cb5d0d36506deb4c53e93ac2;hpb=eb68b5fe9d19e6909bfe3c2184b36bfd1d39e2ce;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index ed3c0759..655a53c2 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -511,6 +511,10 @@ impl<'a> PaymentPath<'a> { return result; } + fn get_cost_msat(&self) -> u64 { + self.get_total_fee_paid_msat().saturating_add(self.get_path_penalty_msat()) + } + // If the amount transferred by the path is updated, the fees should be adjusted. Any other way // to change fees may result in an inconsistency. // @@ -598,6 +602,17 @@ fn compute_fees(amount_msat: u64, channel_fees: RoutingFees) -> Option { } } +/// The default `features` we assume for a node in a route, when no `features` are known about that +/// specific node. +/// +/// Default features are: +/// * variable_length_onion_optional +fn default_node_features() -> NodeFeatures { + let mut features = NodeFeatures::empty(); + features.set_variable_length_onion_optional(); + features +} + /// Finds a route from us (payer) to the given target node (payee). /// /// If the payee provided features in their invoice, they should be provided via `params.payee`. @@ -912,14 +927,20 @@ where L::Target: Logger { let over_path_minimum_msat = amount_to_transfer_over_msat >= $candidate.htlc_minimum_msat() && amount_to_transfer_over_msat >= $next_hops_path_htlc_minimum_msat; + #[allow(unused_comparisons)] // $next_hops_path_htlc_minimum_msat is 0 in some calls so rustc complains + let may_overpay_to_meet_path_minimum_msat = + ((amount_to_transfer_over_msat < $candidate.htlc_minimum_msat() && + recommended_value_msat > $candidate.htlc_minimum_msat()) || + (amount_to_transfer_over_msat < $next_hops_path_htlc_minimum_msat && + recommended_value_msat > $next_hops_path_htlc_minimum_msat)); + // If HTLC minimum is larger than the amount we're going to transfer, we shouldn't - // bother considering this channel. - // Since we're choosing amount_to_transfer_over_msat as maximum possible, it can - // be only reduced later (not increased), so this channel should just be skipped - // as not sufficient. - if !over_path_minimum_msat && doesnt_exceed_cltv_delta_limit { + // bother considering this channel. If retrying with recommended_value_msat may + // allow us to hit the HTLC minimum limit, set htlc_minimum_limit so that we go + // around again with a higher amount. + if contributes_sufficient_value && doesnt_exceed_cltv_delta_limit && may_overpay_to_meet_path_minimum_msat { hit_minimum_limit = true; - } else if contributes_sufficient_value && doesnt_exceed_cltv_delta_limit { + } else if contributes_sufficient_value && doesnt_exceed_cltv_delta_limit && over_path_minimum_msat { // Note that low contribution here (limited by available_liquidity_msat) // might violate htlc_minimum_msat on the hops which are next along the // payment path (upstream to the payee). To avoid that, we recompute @@ -1091,7 +1112,8 @@ where L::Target: Logger { } } } - let empty_node_features = NodeFeatures::empty(); + let default_node_features = default_node_features(); + // Find ways (channels with destination) to reach a given node and store them // in the corresponding data structures (routing graph etc). // $fee_to_target_msat represents how much it costs to reach to this node from the payee, @@ -1122,7 +1144,7 @@ where L::Target: Logger { let features = if let Some(node_info) = $node.announcement_info.as_ref() { &node_info.features } else { - &empty_node_features + &default_node_features }; if !features.requires_unknown_bits() { @@ -1302,7 +1324,7 @@ where L::Target: Logger { // traversing the graph and arrange the path out of what we found. if node_id == our_node_id { let mut new_entry = dist.remove(&our_node_id).unwrap(); - let mut ordered_hops = vec!((new_entry.clone(), NodeFeatures::empty())); + let mut ordered_hops = vec!((new_entry.clone(), default_node_features.clone())); 'path_walk: loop { let mut features_set = false; @@ -1320,7 +1342,7 @@ where L::Target: Logger { if let Some(node_info) = node.announcement_info.as_ref() { ordered_hops.last_mut().unwrap().1 = node_info.features.clone(); } else { - ordered_hops.last_mut().unwrap().1 = NodeFeatures::empty(); + ordered_hops.last_mut().unwrap().1 = default_node_features.clone(); } } else { // We can fill in features for everything except hops which were @@ -1347,7 +1369,7 @@ where L::Target: Logger { // so that fees paid for a HTLC forwarding on the current channel are // associated with the previous channel (where they will be subtracted). ordered_hops.last_mut().unwrap().0.fee_msat = new_entry.hop_use_fee_msat; - ordered_hops.push((new_entry.clone(), NodeFeatures::empty())); + ordered_hops.push((new_entry.clone(), default_node_features.clone())); } ordered_hops.last_mut().unwrap().0.fee_msat = value_contribution_msat; ordered_hops.last_mut().unwrap().0.hop_use_fee_msat = 0; @@ -1390,7 +1412,7 @@ where L::Target: Logger { // If we weren't capped by hitting a liquidity limit on a channel in the path, // we'll probably end up picking the same path again on the next iteration. // Decrease the available liquidity of a hop in the middle of the path. - let victim_scid = payment_path.hops[(payment_path.hops.len() - 1) / 2].0.candidate.short_channel_id(); + let victim_scid = payment_path.hops[(payment_path.hops.len()) / 2].0.candidate.short_channel_id(); log_trace!(logger, "Disabling channel {} for future path building iterations to avoid duplicates.", victim_scid); let victim_liquidity = bookkept_channels_liquidity_available_msat.get_mut(&victim_scid).unwrap(); *victim_liquidity = 0; @@ -1502,9 +1524,8 @@ where L::Target: Logger { // prefer lower cost paths. cur_route.sort_unstable_by(|a, b| { a.get_value_msat().cmp(&b.get_value_msat()) - // Reverse ordering for fees, so we drop higher-fee paths first - .then_with(|| b.get_total_fee_paid_msat().saturating_add(b.get_path_penalty_msat()) - .cmp(&a.get_total_fee_paid_msat().saturating_add(a.get_path_penalty_msat()))) + // Reverse ordering for cost, so we drop higher-cost paths first + .then_with(|| b.get_cost_msat().cmp(&a.get_cost_msat())) }); // We should make sure that at least 1 path left. @@ -1548,8 +1569,8 @@ where L::Target: Logger { } // Step (9). - // Select the best route by lowest total fee. - drawn_routes.sort_unstable_by_key(|paths| paths.iter().map(|path| path.get_total_fee_paid_msat()).sum::()); + // Select the best route by lowest total cost. + drawn_routes.sort_unstable_by_key(|paths| paths.iter().map(|path| path.get_cost_msat()).sum::()); let mut selected_paths = Vec::>>::new(); for payment_path in drawn_routes.first().unwrap() { let mut path = payment_path.hops.iter().map(|(payment_hop, node_features)| { @@ -1675,7 +1696,7 @@ fn add_random_cltv_offset(route: &mut Route, payment_params: &PaymentParameters, #[cfg(test)] mod tests { use routing::network_graph::{NetworkGraph, NetGraphMsgHandler, NodeId}; - use routing::router::{get_route, add_random_cltv_offset, PaymentParameters, Route, RouteHint, RouteHintHop, RouteHop, RoutingFees, DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA}; + use routing::router::{get_route, add_random_cltv_offset, default_node_features, PaymentParameters, Route, RouteHint, RouteHintHop, RouteHop, RoutingFees, DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA}; use routing::scoring::Score; use chain::transaction::OutPoint; use chain::keysinterface::KeysInterface; @@ -1716,6 +1737,7 @@ mod tests { forwarding_info: None, }, funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }), + channel_type: None, short_channel_id, inbound_scid_alias: None, channel_value_satoshis: 0, @@ -2775,7 +2797,7 @@ mod tests { assert_eq!(route.paths[0][4].short_channel_id, 8); assert_eq!(route.paths[0][4].fee_msat, 100); assert_eq!(route.paths[0][4].cltv_expiry_delta, 42); - assert_eq!(route.paths[0][4].node_features.le_flags(), &Vec::::new()); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][4].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly } @@ -2851,7 +2873,7 @@ mod tests { assert_eq!(route.paths[0][4].short_channel_id, 8); assert_eq!(route.paths[0][4].fee_msat, 100); assert_eq!(route.paths[0][4].cltv_expiry_delta, 42); - assert_eq!(route.paths[0][4].node_features.le_flags(), &Vec::::new()); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][4].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly } @@ -2948,7 +2970,7 @@ mod tests { assert_eq!(route.paths[0][3].short_channel_id, last_hops[0].0[1].short_channel_id); assert_eq!(route.paths[0][3].fee_msat, 100); assert_eq!(route.paths[0][3].cltv_expiry_delta, 42); - assert_eq!(route.paths[0][3].node_features.le_flags(), &Vec::::new()); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][3].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet assert_eq!(route.paths[0][3].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly } @@ -3013,14 +3035,14 @@ mod tests { assert_eq!(route.paths[0][2].short_channel_id, last_hops[0].0[0].short_channel_id); assert_eq!(route.paths[0][2].fee_msat, 0); assert_eq!(route.paths[0][2].cltv_expiry_delta, 129); - assert_eq!(route.paths[0][2].node_features.le_flags(), &Vec::::new()); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][2].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet assert_eq!(route.paths[0][2].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly assert_eq!(route.paths[0][3].pubkey, nodes[6]); assert_eq!(route.paths[0][3].short_channel_id, last_hops[0].0[1].short_channel_id); assert_eq!(route.paths[0][3].fee_msat, 100); assert_eq!(route.paths[0][3].cltv_expiry_delta, 42); - assert_eq!(route.paths[0][3].node_features.le_flags(), &Vec::::new()); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][3].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet assert_eq!(route.paths[0][3].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly } @@ -3111,7 +3133,7 @@ mod tests { assert_eq!(route.paths[0][4].short_channel_id, 8); assert_eq!(route.paths[0][4].fee_msat, 100); assert_eq!(route.paths[0][4].cltv_expiry_delta, 42); - assert_eq!(route.paths[0][4].node_features.le_flags(), &Vec::::new()); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][4].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly } @@ -3141,7 +3163,7 @@ mod tests { assert_eq!(route.paths[0][1].short_channel_id, 8); assert_eq!(route.paths[0][1].fee_msat, 100); assert_eq!(route.paths[0][1].cltv_expiry_delta, 42); - assert_eq!(route.paths[0][1].node_features.le_flags(), &Vec::::new()); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][1].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet assert_eq!(route.paths[0][1].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly last_hops[0].0[0].fees.base_msat = 1000; @@ -3178,7 +3200,7 @@ mod tests { assert_eq!(route.paths[0][3].short_channel_id, 10); assert_eq!(route.paths[0][3].fee_msat, 100); assert_eq!(route.paths[0][3].cltv_expiry_delta, 42); - assert_eq!(route.paths[0][3].node_features.le_flags(), &Vec::::new()); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][3].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet assert_eq!(route.paths[0][3].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly // ...but still use 8 for larger payments as 6 has a variable feerate @@ -3219,7 +3241,7 @@ mod tests { assert_eq!(route.paths[0][4].short_channel_id, 8); assert_eq!(route.paths[0][4].fee_msat, 2000); assert_eq!(route.paths[0][4].cltv_expiry_delta, 42); - assert_eq!(route.paths[0][4].node_features.le_flags(), &Vec::::new()); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][4].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly } @@ -3271,7 +3293,7 @@ mod tests { assert_eq!(route.paths[0][1].short_channel_id, 8); assert_eq!(route.paths[0][1].fee_msat, 1000000); assert_eq!(route.paths[0][1].cltv_expiry_delta, 42); - assert_eq!(route.paths[0][1].node_features.le_flags(), &[0; 0]); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][1].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet assert_eq!(route.paths[0][1].channel_features.le_flags(), &[0; 0]); // We can't learn any flags from invoices, sadly } @@ -5438,6 +5460,7 @@ mod benches { funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }), + channel_type: None, short_channel_id: Some(1), inbound_scid_alias: None, channel_value_satoshis: 10_000_000,