X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=9f202557ff7066d485e59c0ce0a9710ae687e1be;hb=5425b2b77e690a08a604c6d26fbd0f8a1667f045;hp=8a2aecb581c916099eeedab0a36ec6afa8c35f86;hpb=b11dcf9ba8c75b50c5915402ad8c29b972b0f8a0;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index 8a2aecb5..9f202557 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)) } } @@ -815,6 +813,29 @@ where L::Target: Logger { // - when we want to stop looking for new paths. let mut already_collected_value_msat = 0; + for (_, channels) in first_hop_targets.iter_mut() { + // Sort the first_hops channels to the same node(s) in priority order of which channel we'd + // most like to use. + // + // First, if channels are below `recommended_value_msat`, sort them in descending order, + // preferring larger channels to avoid splitting the payment into more MPP parts than is + // required. + // + // Second, because simply always sorting in descending order would always use our largest + // available outbound capacity, needlessly fragmenting our available channel capacities, + // sort channels above `recommended_value_msat` in ascending order, preferring channels + // which have enough, but not too much, capacity for the payment. + channels.sort_unstable_by(|chan_a, chan_b| { + if chan_b.outbound_capacity_msat < recommended_value_msat || chan_a.outbound_capacity_msat < recommended_value_msat { + // Sort in descending order + chan_b.outbound_capacity_msat.cmp(&chan_a.outbound_capacity_msat) + } else { + // Sort in ascending order + chan_a.outbound_capacity_msat.cmp(&chan_b.outbound_capacity_msat) + } + }); + } + log_trace!(logger, "Building path from {} (payee) to {} (us/payer) for value {} msat.", payment_params.payee_pubkey, our_node_pubkey, final_value_msat); macro_rules! add_entry { @@ -837,7 +858,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 @@ -877,8 +898,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); @@ -985,9 +1005,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, @@ -1015,11 +1035,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); @@ -1203,12 +1221,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 @@ -1446,7 +1462,7 @@ 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); } @@ -1514,13 +1530,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); @@ -1532,7 +1549,7 @@ 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::()); + drawn_routes.sort_unstable_by_key(|paths| paths.iter().map(|path| path.get_total_fee_paid_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)| { @@ -1580,45 +1597,58 @@ fn add_random_cltv_offset(route: &mut Route, payment_params: &PaymentParameters, for path in route.paths.iter_mut() { let mut shadow_ctlv_expiry_delta_offset: u32 = 0; - // Choose the last publicly known node as the starting point for the random walk - if let Some(starting_hop) = path.iter().rev().find(|h| network_nodes.contains_key(&NodeId::from_pubkey(&h.pubkey))) { - let mut cur_node_id = NodeId::from_pubkey(&starting_hop.pubkey); + // Remember the last three nodes of the random walk and avoid looping back on them. + // Init with the last three nodes from the actual path, if possible. + let mut nodes_to_avoid: [NodeId; 3] = [NodeId::from_pubkey(&path.last().unwrap().pubkey), + NodeId::from_pubkey(&path.get(path.len().saturating_sub(2)).unwrap().pubkey), + NodeId::from_pubkey(&path.get(path.len().saturating_sub(3)).unwrap().pubkey)]; + + // Choose the last publicly known node as the starting point for the random walk. + let mut cur_hop: Option = None; + let mut path_nonce = [0u8; 12]; + if let Some(starting_hop) = path.iter().rev() + .find(|h| network_nodes.contains_key(&NodeId::from_pubkey(&h.pubkey))) { + cur_hop = Some(NodeId::from_pubkey(&starting_hop.pubkey)); + path_nonce.copy_from_slice(&cur_hop.unwrap().as_slice()[..12]); + } + + // Init PRNG with the path-dependant nonce, which is static for private paths. + let mut prng = ChaCha20::new(random_seed_bytes, &path_nonce); + let mut random_path_bytes = [0u8; ::core::mem::size_of::()]; - // Init PRNG with path nonce - let mut path_nonce = [0u8; 12]; - path_nonce.copy_from_slice(&cur_node_id.as_slice()[..12]); - let mut prng = ChaCha20::new(random_seed_bytes, &path_nonce); - let mut random_path_bytes = [0u8; ::core::mem::size_of::()]; + // Pick a random path length in [1 .. 3] + prng.process_in_place(&mut random_path_bytes); + let random_walk_length = usize::from_be_bytes(random_path_bytes).wrapping_rem(3).wrapping_add(1); - // Pick a random path length in [1 .. 3] - prng.process_in_place(&mut random_path_bytes); - let random_walk_length = usize::from_be_bytes(random_path_bytes).wrapping_rem(3).wrapping_add(1); + for random_hop in 0..random_walk_length { + // If we don't find a suitable offset in the public network graph, we default to + // MEDIAN_HOP_CLTV_EXPIRY_DELTA. + let mut random_hop_offset = MEDIAN_HOP_CLTV_EXPIRY_DELTA; - for _random_hop in 0..random_walk_length { + if let Some(cur_node_id) = cur_hop { if let Some(cur_node) = network_nodes.get(&cur_node_id) { - // Randomly choose the next hop + // Randomly choose the next unvisited hop. prng.process_in_place(&mut random_path_bytes); - if let Some(random_channel) = usize::from_be_bytes(random_path_bytes).checked_rem(cur_node.channels.len()) + if let Some(random_channel) = usize::from_be_bytes(random_path_bytes) + .checked_rem(cur_node.channels.len()) .and_then(|index| cur_node.channels.get(index)) .and_then(|id| network_channels.get(id)) { random_channel.as_directed_from(&cur_node_id).map(|(dir_info, next_id)| { - dir_info.direction().map(|channel_update_info| - shadow_ctlv_expiry_delta_offset = shadow_ctlv_expiry_delta_offset - .checked_add(channel_update_info.cltv_expiry_delta.into()) - .unwrap_or(shadow_ctlv_expiry_delta_offset)); - cur_node_id = *next_id; + if !nodes_to_avoid.iter().any(|x| x == next_id) { + nodes_to_avoid[random_hop] = *next_id; + dir_info.direction().map(|channel_update_info| { + random_hop_offset = channel_update_info.cltv_expiry_delta.into(); + cur_hop = Some(*next_id); + }); + } }); } } } - } else { - // If the entire path is private, choose a random offset from multiples of - // MEDIAN_HOP_CLTV_EXPIRY_DELTA - let mut prng = ChaCha20::new(random_seed_bytes, &[0u8; 8]); - let mut random_bytes = [0u8; 4]; - prng.process_in_place(&mut random_bytes); - let random_walk_length = u32::from_be_bytes(random_bytes).wrapping_rem(3).wrapping_add(1); - shadow_ctlv_expiry_delta_offset = random_walk_length * MEDIAN_HOP_CLTV_EXPIRY_DELTA; + + shadow_ctlv_expiry_delta_offset = shadow_ctlv_expiry_delta_offset + .checked_add(random_hop_offset) + .unwrap_or(shadow_ctlv_expiry_delta_offset); } // Limit the total offset to reduce the worst-case locked liquidity timevalue @@ -1686,6 +1716,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, @@ -4910,6 +4941,32 @@ mod tests { assert_eq!(route.paths[1][0].short_channel_id, 2); assert_eq!(route.paths[1][0].fee_msat, 50_000); } + + { + // If we have a bunch of outbound channels to the same node, where most are not + // sufficient to pay the full payment, but one is, we should default to just using the + // one single channel that has sufficient balance, avoiding MPP. + // + // If we have several options above the 3xpayment value threshold, we should pick the + // smallest of them, avoiding further fragmenting our available outbound balance to + // this node. + let route = get_route(&our_id, &payment_params, &network_graph.read_only(), Some(&[ + &get_channel_details(Some(2), nodes[0], InitFeatures::known(), 50_000), + &get_channel_details(Some(3), nodes[0], InitFeatures::known(), 50_000), + &get_channel_details(Some(5), nodes[0], InitFeatures::known(), 50_000), + &get_channel_details(Some(6), nodes[0], InitFeatures::known(), 300_000), + &get_channel_details(Some(7), nodes[0], InitFeatures::known(), 50_000), + &get_channel_details(Some(8), nodes[0], InitFeatures::known(), 50_000), + &get_channel_details(Some(9), nodes[0], InitFeatures::known(), 50_000), + &get_channel_details(Some(4), nodes[0], InitFeatures::known(), 1_000_000), + ]), 100_000, 42, Arc::clone(&logger), &scorer, &random_seed_bytes).unwrap(); + assert_eq!(route.paths.len(), 1); + assert_eq!(route.paths[0].len(), 1); + + assert_eq!(route.paths[0][0].pubkey, nodes[0]); + assert_eq!(route.paths[0][0].short_channel_id, 6); + assert_eq!(route.paths[0][0].fee_msat, 100_000); + } } #[test] @@ -5382,6 +5439,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,