X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=655a53c2dfeab3007c4660f74f04a67022066db6;hb=a316ef45960314cdfe03ab57695c1aee5d9189a6;hp=677a571620ce31a329f8b046d294a8d99b1c2387;hpb=4e89e5741b81df2f0e21905826699360c61bb2d1;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index 677a5716..655a53c2 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -332,11 +332,9 @@ struct RouteGraphNode { impl cmp::Ord for RouteGraphNode { fn cmp(&self, other: &RouteGraphNode) -> cmp::Ordering { let other_score = cmp::max(other.lowest_fee_to_peer_through_node, other.path_htlc_minimum_msat) - .checked_add(other.path_penalty_msat) - .unwrap_or_else(|| u64::max_value()); + .saturating_add(other.path_penalty_msat); let self_score = cmp::max(self.lowest_fee_to_peer_through_node, self.path_htlc_minimum_msat) - .checked_add(self.path_penalty_msat) - .unwrap_or_else(|| u64::max_value()); + .saturating_add(self.path_penalty_msat); other_score.cmp(&self_score).then_with(|| other.node_id.cmp(&self.node_id)) } } @@ -495,6 +493,10 @@ impl<'a> PaymentPath<'a> { self.hops.last().unwrap().0.fee_msat } + fn get_path_penalty_msat(&self) -> u64 { + self.hops.first().map(|h| h.0.path_penalty_msat).unwrap_or(u64::max_value()) + } + fn get_total_fee_paid_msat(&self) -> u64 { if self.hops.len() < 1 { return 0; @@ -509,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. // @@ -596,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`. @@ -645,7 +662,7 @@ where L::Target: Logger { pub(crate) fn get_route( our_node_pubkey: &PublicKey, payment_params: &PaymentParameters, network_graph: &ReadOnlyNetworkGraph, first_hops: Option<&[&ChannelDetails]>, final_value_msat: u64, final_cltv_expiry_delta: u32, - logger: L, scorer: &S, _random_seed_bytes: &[u8; 32] + logger: L, scorer: &S, random_seed_bytes: &[u8; 32] ) -> Result where L::Target: Logger { let payee_node_id = NodeId::from_pubkey(&payment_params.payee_pubkey); @@ -856,7 +873,7 @@ where L::Target: Logger { .entry(short_channel_id) .or_insert_with(|| $candidate.effective_capacity().as_msat()); - // It is tricky to substract $next_hops_fee_msat from available liquidity here. + // It is tricky to subtract $next_hops_fee_msat from available liquidity here. // It may be misleading because we might later choose to reduce the value transferred // over these channels, and the channel which was insufficient might become sufficient. // Worst case: we drop a good channel here because it can't cover the high following @@ -896,8 +913,7 @@ where L::Target: Logger { .checked_sub(2*MEDIAN_HOP_CLTV_EXPIRY_DELTA) .unwrap_or(payment_params.max_total_cltv_expiry_delta - final_cltv_expiry_delta); let hop_total_cltv_delta = ($next_hops_cltv_delta as u32) - .checked_add($candidate.cltv_expiry_delta()) - .unwrap_or(u32::max_value()); + .saturating_add($candidate.cltv_expiry_delta()); let doesnt_exceed_cltv_delta_limit = hop_total_cltv_delta <= max_total_cltv_expiry_delta; let value_contribution_msat = cmp::min(available_value_contribution_msat, $next_hops_value_contribution); @@ -911,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 @@ -1004,9 +1026,9 @@ where L::Target: Logger { } } - let path_penalty_msat = $next_hops_path_penalty_msat.checked_add( - scorer.channel_penalty_msat(short_channel_id, amount_to_transfer_over_msat, *available_liquidity_msat, - &$src_node_id, &$dest_node_id)).unwrap_or_else(|| u64::max_value()); + let path_penalty_msat = $next_hops_path_penalty_msat.saturating_add( + scorer.channel_penalty_msat(short_channel_id, amount_to_transfer_over_msat, + *available_liquidity_msat, &$src_node_id, &$dest_node_id)); let new_graph_node = RouteGraphNode { node_id: $src_node_id, lowest_fee_to_peer_through_node: total_fee_msat, @@ -1034,11 +1056,9 @@ where L::Target: Logger { // the fees included in $next_hops_path_htlc_minimum_msat, but also // can't use something that may decrease on future hops. let old_cost = cmp::max(old_entry.total_fee_msat, old_entry.path_htlc_minimum_msat) - .checked_add(old_entry.path_penalty_msat) - .unwrap_or_else(|| u64::max_value()); + .saturating_add(old_entry.path_penalty_msat); let new_cost = cmp::max(total_fee_msat, path_htlc_minimum_msat) - .checked_add(path_penalty_msat) - .unwrap_or_else(|| u64::max_value()); + .saturating_add(path_penalty_msat); if !old_entry.was_processed && new_cost < old_cost { targets.push(new_graph_node); @@ -1092,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, @@ -1123,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() { @@ -1222,12 +1243,10 @@ where L::Target: Logger { .unwrap_or_else(|| CandidateRouteHop::PrivateHop { hint: hop }); let capacity_msat = candidate.effective_capacity().as_msat(); aggregate_next_hops_path_penalty_msat = aggregate_next_hops_path_penalty_msat - .checked_add(scorer.channel_penalty_msat(hop.short_channel_id, final_value_msat, capacity_msat, &source, &target)) - .unwrap_or_else(|| u64::max_value()); + .saturating_add(scorer.channel_penalty_msat(hop.short_channel_id, final_value_msat, capacity_msat, &source, &target)); aggregate_next_hops_cltv_delta = aggregate_next_hops_cltv_delta - .checked_add(hop.cltv_expiry_delta as u32) - .unwrap_or_else(|| u32::max_value()); + .saturating_add(hop.cltv_expiry_delta as u32); if !add_entry!(candidate, source, target, aggregate_next_hops_fee_msat, path_value_msat, aggregate_next_hops_path_htlc_minimum_msat, aggregate_next_hops_path_penalty_msat, aggregate_next_hops_cltv_delta) { // If this hop was not used then there is no use checking the preceding hops @@ -1305,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; @@ -1323,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 @@ -1350,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; @@ -1393,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; @@ -1465,24 +1484,31 @@ where L::Target: Logger { } // Sort by total fees and take the best paths. - payment_paths.sort_by_key(|path| path.get_total_fee_paid_msat()); + payment_paths.sort_unstable_by_key(|path| path.get_total_fee_paid_msat()); if payment_paths.len() > 50 { payment_paths.truncate(50); } // Draw multiple sufficient routes by randomly combining the selected paths. let mut drawn_routes = Vec::new(); - for i in 0..payment_paths.len() { + let mut prng = ChaCha20::new(random_seed_bytes, &[0u8; 12]); + let mut random_index_bytes = [0u8; ::core::mem::size_of::()]; + + let num_permutations = payment_paths.len(); + for _ in 0..num_permutations { let mut cur_route = Vec::::new(); let mut aggregate_route_value_msat = 0; // Step (6). - // TODO: real random shuffle - // Currently just starts with i_th and goes up to i-1_th in a looped way. - let cur_payment_paths = [&payment_paths[i..], &payment_paths[..i]].concat(); + // Do a Fisher-Yates shuffle to create a random permutation of the payment paths + for cur_index in (1..payment_paths.len()).rev() { + prng.process_in_place(&mut random_index_bytes); + let random_index = usize::from_be_bytes(random_index_bytes).wrapping_rem(cur_index+1); + payment_paths.swap(cur_index, random_index); + } // Step (7). - for payment_path in cur_payment_paths { + for payment_path in &payment_paths { cur_route.push(payment_path.clone()); aggregate_route_value_msat += payment_path.get_value_msat(); if aggregate_route_value_msat > final_value_msat { @@ -1492,12 +1518,16 @@ where L::Target: Logger { // also makes routing more reliable. let mut overpaid_value_msat = aggregate_route_value_msat - final_value_msat; - // First, drop some expensive low-value paths entirely if possible. - // Sort by value so that we drop many really-low values first, since - // fewer paths is better: the payment is less likely to fail. - // TODO: this could also be optimized by also sorting by feerate_per_sat_routed, - // so that the sender pays less fees overall. And also htlc_minimum_msat. - cur_route.sort_by_key(|path| path.get_value_msat()); + // First, we drop some expensive low-value paths entirely if possible, since fewer + // paths is better: the payment is less likely to fail. In order to do so, we sort + // by value and fall back to total fees paid, i.e., in case of equal values we + // prefer lower cost paths. + cur_route.sort_unstable_by(|a, b| { + a.get_value_msat().cmp(&b.get_value_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. let mut paths_left = cur_route.len(); cur_route.retain(|path| { @@ -1521,13 +1551,14 @@ where L::Target: Logger { assert!(cur_route.len() > 0); // Step (8). - // Now, substract the overpaid value from the most-expensive path. + // Now, subtract the overpaid value from the most-expensive path. // TODO: this could also be optimized by also sorting by feerate_per_sat_routed, // so that the sender pays less fees overall. And also htlc_minimum_msat. - cur_route.sort_by_key(|path| { path.hops.iter().map(|hop| hop.0.candidate.fees().proportional_millionths as u64).sum::() }); + cur_route.sort_unstable_by_key(|path| { path.hops.iter().map(|hop| hop.0.candidate.fees().proportional_millionths as u64).sum::() }); let expensive_payment_path = cur_route.first_mut().unwrap(); - // We already dropped all the small channels above, meaning all the - // remaining channels are larger than remaining overpaid_value_msat. + + // We already dropped all the small value paths above, meaning all the + // remaining paths are larger than remaining overpaid_value_msat. // Thus, this can't be negative. let expensive_path_new_value_msat = expensive_payment_path.get_value_msat() - overpaid_value_msat; expensive_payment_path.update_value_and_recompute_fees(expensive_path_new_value_msat); @@ -1538,8 +1569,8 @@ where L::Target: Logger { } // Step (9). - // Select the best route by lowest total fee. - drawn_routes.sort_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)| { @@ -1665,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; @@ -1706,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, @@ -2765,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 } @@ -2841,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 } @@ -2938,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 } @@ -3003,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 } @@ -3101,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 } @@ -3131,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; @@ -3168,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 @@ -3209,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 } @@ -3261,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 } @@ -5428,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,