// - 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 {
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<NodeId> = 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::<usize>()];
- // 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::<usize>()];
+ // 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
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]
projects / rust-lightning / blobdiff