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.
//
}
}
+/// 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`.
// - 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 {
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
} }
}
- 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,
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() {
// 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;
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
// 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;
// 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;
// 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.
}
// 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::<u64>());
+ // Select the best route by lowest total cost.
+ drawn_routes.sort_unstable_by_key(|paths| paths.iter().map(|path| path.get_cost_msat()).sum::<u64>());
let mut selected_paths = Vec::<Vec<Result<RouteHop, LightningError>>>::new();
for payment_path in drawn_routes.first().unwrap() {
let mut path = payment_path.hops.iter().map(|(payment_hop, node_features)| {
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
#[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;
node_id,
unspendable_punishment_reserve: 0,
forwarding_info: None,
+ outbound_htlc_minimum_msat: None,
+ outbound_htlc_maximum_msat: 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,
force_close_spend_delay: None,
is_outbound: true, is_funding_locked: true,
is_usable: true, is_public: true,
+ inbound_htlc_minimum_msat: None,
+ inbound_htlc_maximum_msat: None,
}
}
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::<u8>::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::<u8>::new()); // We can't learn any flags from invoices, sadly
}
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::<u8>::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::<u8>::new()); // We can't learn any flags from invoices, sadly
}
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::<u8>::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::<u8>::new()); // We can't learn any flags from invoices, sadly
}
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::<u8>::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::<u8>::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::<u8>::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::<u8>::new()); // We can't learn any flags from invoices, sadly
}
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::<u8>::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::<u8>::new()); // We can't learn any flags from invoices, sadly
}
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::<u8>::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::<u8>::new()); // We can't learn any flags from invoices, sadly
last_hops[0].0[0].fees.base_msat = 1000;
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::<u8>::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::<u8>::new()); // We can't learn any flags from invoices, sadly
// ...but still use 8 for larger payments as 6 has a variable feerate
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::<u8>::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::<u8>::new()); // We can't learn any flags from invoices, sadly
}
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
}
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]
node_id,
unspendable_punishment_reserve: 0,
forwarding_info: None,
+ outbound_htlc_minimum_msat: None,
+ outbound_htlc_maximum_msat: None,
},
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,
is_funding_locked: true,
is_usable: true,
is_public: true,
+ inbound_htlc_minimum_msat: None,
+ inbound_htlc_maximum_msat: None,
}
}