source, target, short_channel_id
) {
let usage = ChannelUsage {
- inflight_htlc_msat: usage.inflight_htlc_msat + used_liquidity,
+ inflight_htlc_msat: usage.inflight_htlc_msat.saturating_add(used_liquidity),
..usage
};
/// A route directs a payment from the sender (us) to the recipient. If the recipient supports MPP,
/// it can take multiple paths. Each path is composed of one or more hops through the network.
-#[derive(Clone, Hash, PartialEq, Eq)]
+#[derive(Clone, Debug, Hash, PartialEq, Eq)]
pub struct Route {
/// The list of [`Path`]s taken for a single (potentially-)multi-part payment. If no
/// [`BlindedTail`]s are present, then the pubkey of the last [`RouteHop`] in each path must be
}
}
+impl fmt::Display for Route {
+ fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
+ log_route!(self).fmt(f)
+ }
+}
+
const SERIALIZATION_VERSION: u8 = 1;
const MIN_SERIALIZATION_VERSION: u8 = 1;
(1, self.route_params.as_ref().map(|p| &p.payment_params), option),
(2, blinded_tails, optional_vec),
(3, self.route_params.as_ref().map(|p| p.final_value_msat), option),
+ (5, self.route_params.as_ref().map(|p| p.max_total_routing_fee_msat), option),
});
Ok(())
}
(1, payment_params, (option: ReadableArgs, min_final_cltv_expiry_delta)),
(2, blinded_tails, optional_vec),
(3, final_value_msat, option),
+ (5, max_total_routing_fee_msat, option)
});
let blinded_tails = blinded_tails.unwrap_or(Vec::new());
if blinded_tails.len() != 0 {
// If we previously wrote the corresponding fields, reconstruct RouteParameters.
let route_params = match (payment_params, final_value_msat) {
(Some(payment_params), Some(final_value_msat)) => {
- Some(RouteParameters { payment_params, final_value_msat })
+ Some(RouteParameters { payment_params, final_value_msat, max_total_routing_fee_msat })
}
_ => None,
};
/// The amount in msats sent on the failed payment path.
pub final_value_msat: u64,
+
+ /// The maximum total fees, in millisatoshi, that may accrue during route finding.
+ ///
+ /// This limit also applies to the total fees that may arise while retrying failed payment
+ /// paths.
+ ///
+ /// Note that values below a few sats may result in some paths being spuriously ignored.
+ pub max_total_routing_fee_msat: Option<u64>,
}
impl RouteParameters {
/// Constructs [`RouteParameters`] from the given [`PaymentParameters`] and a payment amount.
+ ///
+ /// [`Self::max_total_routing_fee_msat`] defaults to 1% of the payment amount + 50 sats
pub fn from_payment_params_and_value(payment_params: PaymentParameters, final_value_msat: u64) -> Self {
- Self { payment_params, final_value_msat }
+ Self { payment_params, final_value_msat, max_total_routing_fee_msat: Some(final_value_msat / 100 + 50_000) }
}
}
fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
write_tlv_fields!(writer, {
(0, self.payment_params, required),
+ (1, self.max_total_routing_fee_msat, option),
(2, self.final_value_msat, required),
// LDK versions prior to 0.0.114 had the `final_cltv_expiry_delta` parameter in
// `RouteParameters` directly. For compatibility, we write it here.
fn read<R: io::Read>(reader: &mut R) -> Result<Self, DecodeError> {
_init_and_read_len_prefixed_tlv_fields!(reader, {
(0, payment_params, (required: ReadableArgs, 0)),
+ (1, max_total_routing_fee_msat, option),
(2, final_value_msat, required),
(4, final_cltv_delta, option),
});
Ok(Self {
payment_params,
final_value_msat: final_value_msat.0.unwrap(),
+ max_total_routing_fee_msat,
})
}
}
// Note that this function is not aware of the available_liquidity limit, and thus does not
// support increasing the value being transferred beyond what was selected during the initial
// routing passes.
- fn update_value_and_recompute_fees(&mut self, value_msat: u64) {
+ //
+ // Returns the amount that this path contributes to the total payment value, which may be greater
+ // than `value_msat` if we had to overpay to meet the final node's `htlc_minimum_msat`.
+ fn update_value_and_recompute_fees(&mut self, value_msat: u64) -> u64 {
+ let mut extra_contribution_msat = 0;
let mut total_fee_paid_msat = 0 as u64;
for i in (0..self.hops.len()).rev() {
let last_hop = i == self.hops.len() - 1;
let cur_hop = &mut self.hops.get_mut(i).unwrap().0;
cur_hop.next_hops_fee_msat = total_fee_paid_msat;
+ cur_hop.path_penalty_msat += extra_contribution_msat;
// Overpay in fees if we can't save these funds due to htlc_minimum_msat.
// We try to account for htlc_minimum_msat in scoring (add_entry!), so that nodes don't
// set it too high just to maliciously take more fees by exploiting this
// Also, this can't be exploited more heavily than *announce a free path and fail
// all payments*.
cur_hop_transferred_amount_msat += extra_fees_msat;
- total_fee_paid_msat += extra_fees_msat;
- cur_hop_fees_msat += extra_fees_msat;
+
+ // We remember and return the extra fees on the final hop to allow accounting for
+ // them in the path's value contribution.
+ if last_hop {
+ extra_contribution_msat = extra_fees_msat;
+ } else {
+ total_fee_paid_msat += extra_fees_msat;
+ cur_hop_fees_msat += extra_fees_msat;
+ }
}
if last_hop {
}
}
}
+ value_msat + extra_contribution_msat
}
}
if payee_node_id_opt.map_or(false, |payee| payee == our_node_id) {
return Err(LightningError{err: "Cannot generate a route to ourselves".to_owned(), action: ErrorAction::IgnoreError});
}
+ if our_node_id == maybe_dummy_payee_node_id {
+ return Err(LightningError{err: "Invalid origin node id provided, use a different one".to_owned(), action: ErrorAction::IgnoreError});
+ }
if final_value_msat > MAX_VALUE_MSAT {
return Err(LightningError{err: "Cannot generate a route of more value than all existing satoshis".to_owned(), action: ErrorAction::IgnoreError});
|info| info.features.supports_basic_mpp()))
} else { false };
- log_trace!(logger, "Searching for a route from payer {} to {} {} MPP and {} first hops {}overriding the network graph", our_node_pubkey,
- LoggedPayeePubkey(payment_params.payee.node_id()), if allow_mpp { "with" } else { "without" },
- first_hops.map(|hops| hops.len()).unwrap_or(0), if first_hops.is_some() { "" } else { "not " });
+ let max_total_routing_fee_msat = route_params.max_total_routing_fee_msat.unwrap_or(u64::max_value());
+
+ log_trace!(logger, "Searching for a route from payer {} to {} {} MPP and {} first hops {}overriding the network graph with a fee limit of {} msat",
+ our_node_pubkey, LoggedPayeePubkey(payment_params.payee.node_id()),
+ if allow_mpp { "with" } else { "without" },
+ first_hops.map(|hops| hops.len()).unwrap_or(0), if first_hops.is_some() { "" } else { "not " },
+ max_total_routing_fee_msat);
// Step (1).
// Prepare the data we'll use for payee-to-payer search by
LoggedPayeePubkey(payment_params.payee.node_id()), our_node_pubkey, final_value_msat);
// Remember how many candidates we ignored to allow for some logging afterwards.
- let mut num_ignored_value_contribution = 0;
- let mut num_ignored_path_length_limit = 0;
- let mut num_ignored_cltv_delta_limit = 0;
- let mut num_ignored_previously_failed = 0;
+ let mut num_ignored_value_contribution: u32 = 0;
+ let mut num_ignored_path_length_limit: u32 = 0;
+ let mut num_ignored_cltv_delta_limit: u32 = 0;
+ let mut num_ignored_previously_failed: u32 = 0;
+ let mut num_ignored_total_fee_limit: u32 = 0;
+ let mut num_ignored_avoid_overpayment: u32 = 0;
+ let mut num_ignored_htlc_minimum_msat_limit: u32 = 0;
macro_rules! add_entry {
// Adds entry which goes from $src_node_id to $dest_node_id over the $candidate hop.
// $next_hops_fee_msat represents the fees paid for using all the channels *after* this one,
// since that value has to be transferred over this channel.
- // Returns whether this channel caused an update to `targets`.
+ // Returns the contribution amount of $candidate if the channel caused an update to `targets`.
( $candidate: expr, $src_node_id: expr, $dest_node_id: expr, $next_hops_fee_msat: expr,
$next_hops_value_contribution: expr, $next_hops_path_htlc_minimum_msat: expr,
$next_hops_path_penalty_msat: expr, $next_hops_cltv_delta: expr, $next_hops_path_length: expr ) => { {
// We "return" whether we updated the path at the end, and how much we can route via
// this channel, via this:
- let mut did_add_update_path_to_src_node = None;
+ let mut hop_contribution_amt_msat = None;
// Channels to self should not be used. This is more of belt-and-suspenders, because in
// practice these cases should be caught earlier:
// - for regular channels at channel announcement (TODO)
#[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()) ||
+ 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));
+ recommended_value_msat >= $next_hops_path_htlc_minimum_msat));
let payment_failed_on_this_channel = scid_opt.map_or(false,
|scid| payment_params.previously_failed_channels.contains(&scid));
CandidateRouteHop::FirstHop { .. } => true,
CandidateRouteHop::PrivateHop { .. } => true,
CandidateRouteHop::Blinded { .. } => true,
+ CandidateRouteHop::OneHopBlinded { .. } => true,
_ => false,
};
}
num_ignored_previously_failed += 1;
} else if may_overpay_to_meet_path_minimum_msat {
+ if should_log_candidate {
+ log_trace!(logger,
+ "Ignoring {} to avoid overpaying to meet htlc_minimum_msat limit.",
+ LoggedCandidateHop(&$candidate));
+ }
+ num_ignored_avoid_overpayment += 1;
hit_minimum_limit = true;
} else if 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
// path fees knowing the final path contribution after constructing it.
- let path_htlc_minimum_msat = cmp::max(
- compute_fees_saturating($next_hops_path_htlc_minimum_msat, $candidate.fees())
- .saturating_add($next_hops_path_htlc_minimum_msat),
- $candidate.htlc_minimum_msat());
+ let curr_min = cmp::max(
+ $next_hops_path_htlc_minimum_msat, $candidate.htlc_minimum_msat()
+ );
+ let path_htlc_minimum_msat = compute_fees_saturating(curr_min, $candidate.fees())
+ .saturating_add(curr_min);
let hm_entry = dist.entry($src_node_id);
let old_entry = hm_entry.or_insert_with(|| {
// If there was previously no known way to access the source node
total_fee_msat = total_fee_msat.saturating_add(hop_use_fee_msat);
}
- let channel_usage = ChannelUsage {
- amount_msat: amount_to_transfer_over_msat,
- inflight_htlc_msat: used_liquidity_msat,
- effective_capacity,
- };
- let channel_penalty_msat = scid_opt.map_or(0,
- |scid| scorer.channel_penalty_msat(scid, &$src_node_id, &$dest_node_id,
- channel_usage, score_params));
- let path_penalty_msat = $next_hops_path_penalty_msat
- .saturating_add(channel_penalty_msat);
- let new_graph_node = RouteGraphNode {
- node_id: $src_node_id,
- lowest_fee_to_node: total_fee_msat,
- total_cltv_delta: hop_total_cltv_delta,
- value_contribution_msat,
- path_htlc_minimum_msat,
- path_penalty_msat,
- path_length_to_node,
- };
-
- // Update the way of reaching $src_node_id with the given short_channel_id (from $dest_node_id),
- // if this way is cheaper than the already known
- // (considering the cost to "reach" this channel from the route destination,
- // the cost of using this channel,
- // and the cost of routing to the source node of this channel).
- // Also, consider that htlc_minimum_msat_difference, because we might end up
- // paying it. Consider the following exploit:
- // we use 2 paths to transfer 1.5 BTC. One of them is 0-fee normal 1 BTC path,
- // and for the other one we picked a 1sat-fee path with htlc_minimum_msat of
- // 1 BTC. Now, since the latter is more expensive, we gonna try to cut it
- // by 0.5 BTC, but then match htlc_minimum_msat by paying a fee of 0.5 BTC
- // to this channel.
- // Ideally the scoring could be smarter (e.g. 0.5*htlc_minimum_msat here),
- // but it may require additional tracking - we don't want to double-count
- // 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)
- .saturating_add(old_entry.path_penalty_msat);
- let new_cost = cmp::max(total_fee_msat, path_htlc_minimum_msat)
- .saturating_add(path_penalty_msat);
-
- if !old_entry.was_processed && new_cost < old_cost {
- targets.push(new_graph_node);
- old_entry.next_hops_fee_msat = $next_hops_fee_msat;
- old_entry.hop_use_fee_msat = hop_use_fee_msat;
- old_entry.total_fee_msat = total_fee_msat;
- old_entry.node_id = $dest_node_id.clone();
- old_entry.candidate = $candidate.clone();
- old_entry.fee_msat = 0; // This value will be later filled with hop_use_fee_msat of the following channel
- old_entry.path_htlc_minimum_msat = path_htlc_minimum_msat;
- old_entry.path_penalty_msat = path_penalty_msat;
- #[cfg(all(not(ldk_bench), any(test, fuzzing)))]
- {
- old_entry.value_contribution_msat = value_contribution_msat;
+ // Ignore hops if augmenting the current path to them would put us over `max_total_routing_fee_msat`
+ if total_fee_msat > max_total_routing_fee_msat {
+ if should_log_candidate {
+ log_trace!(logger, "Ignoring {} due to exceeding max total routing fee limit.", LoggedCandidateHop(&$candidate));
}
- did_add_update_path_to_src_node = Some(value_contribution_msat);
- } else if old_entry.was_processed && new_cost < old_cost {
- #[cfg(all(not(ldk_bench), any(test, fuzzing)))]
- {
- // If we're skipping processing a node which was previously
- // processed even though we found another path to it with a
- // cheaper fee, check that it was because the second path we
- // found (which we are processing now) has a lower value
- // contribution due to an HTLC minimum limit.
- //
- // e.g. take a graph with two paths from node 1 to node 2, one
- // through channel A, and one through channel B. Channel A and
- // B are both in the to-process heap, with their scores set by
- // a higher htlc_minimum than fee.
- // Channel A is processed first, and the channels onwards from
- // node 1 are added to the to-process heap. Thereafter, we pop
- // Channel B off of the heap, note that it has a much more
- // restrictive htlc_maximum_msat, and recalculate the fees for
- // all of node 1's channels using the new, reduced, amount.
- //
- // This would be bogus - we'd be selecting a higher-fee path
- // with a lower htlc_maximum_msat instead of the one we'd
- // already decided to use.
- debug_assert!(path_htlc_minimum_msat < old_entry.path_htlc_minimum_msat);
- debug_assert!(
- value_contribution_msat + path_penalty_msat <
- old_entry.value_contribution_msat + old_entry.path_penalty_msat
- );
+ num_ignored_total_fee_limit += 1;
+ } else {
+ let channel_usage = ChannelUsage {
+ amount_msat: amount_to_transfer_over_msat,
+ inflight_htlc_msat: used_liquidity_msat,
+ effective_capacity,
+ };
+ let channel_penalty_msat = scid_opt.map_or(0,
+ |scid| scorer.channel_penalty_msat(scid, &$src_node_id, &$dest_node_id,
+ channel_usage, score_params));
+ let path_penalty_msat = $next_hops_path_penalty_msat
+ .saturating_add(channel_penalty_msat);
+ let new_graph_node = RouteGraphNode {
+ node_id: $src_node_id,
+ lowest_fee_to_node: total_fee_msat,
+ total_cltv_delta: hop_total_cltv_delta,
+ value_contribution_msat,
+ path_htlc_minimum_msat,
+ path_penalty_msat,
+ path_length_to_node,
+ };
+
+ // Update the way of reaching $src_node_id with the given short_channel_id (from $dest_node_id),
+ // if this way is cheaper than the already known
+ // (considering the cost to "reach" this channel from the route destination,
+ // the cost of using this channel,
+ // and the cost of routing to the source node of this channel).
+ // Also, consider that htlc_minimum_msat_difference, because we might end up
+ // paying it. Consider the following exploit:
+ // we use 2 paths to transfer 1.5 BTC. One of them is 0-fee normal 1 BTC path,
+ // and for the other one we picked a 1sat-fee path with htlc_minimum_msat of
+ // 1 BTC. Now, since the latter is more expensive, we gonna try to cut it
+ // by 0.5 BTC, but then match htlc_minimum_msat by paying a fee of 0.5 BTC
+ // to this channel.
+ // Ideally the scoring could be smarter (e.g. 0.5*htlc_minimum_msat here),
+ // but it may require additional tracking - we don't want to double-count
+ // 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)
+ .saturating_add(old_entry.path_penalty_msat);
+ let new_cost = cmp::max(total_fee_msat, path_htlc_minimum_msat)
+ .saturating_add(path_penalty_msat);
+
+ if !old_entry.was_processed && new_cost < old_cost {
+ targets.push(new_graph_node);
+ old_entry.next_hops_fee_msat = $next_hops_fee_msat;
+ old_entry.hop_use_fee_msat = hop_use_fee_msat;
+ old_entry.total_fee_msat = total_fee_msat;
+ old_entry.node_id = $dest_node_id.clone();
+ old_entry.candidate = $candidate.clone();
+ old_entry.fee_msat = 0; // This value will be later filled with hop_use_fee_msat of the following channel
+ old_entry.path_htlc_minimum_msat = path_htlc_minimum_msat;
+ old_entry.path_penalty_msat = path_penalty_msat;
+ #[cfg(all(not(ldk_bench), any(test, fuzzing)))]
+ {
+ old_entry.value_contribution_msat = value_contribution_msat;
+ }
+ hop_contribution_amt_msat = Some(value_contribution_msat);
+ } else if old_entry.was_processed && new_cost < old_cost {
+ #[cfg(all(not(ldk_bench), any(test, fuzzing)))]
+ {
+ // If we're skipping processing a node which was previously
+ // processed even though we found another path to it with a
+ // cheaper fee, check that it was because the second path we
+ // found (which we are processing now) has a lower value
+ // contribution due to an HTLC minimum limit.
+ //
+ // e.g. take a graph with two paths from node 1 to node 2, one
+ // through channel A, and one through channel B. Channel A and
+ // B are both in the to-process heap, with their scores set by
+ // a higher htlc_minimum than fee.
+ // Channel A is processed first, and the channels onwards from
+ // node 1 are added to the to-process heap. Thereafter, we pop
+ // Channel B off of the heap, note that it has a much more
+ // restrictive htlc_maximum_msat, and recalculate the fees for
+ // all of node 1's channels using the new, reduced, amount.
+ //
+ // This would be bogus - we'd be selecting a higher-fee path
+ // with a lower htlc_maximum_msat instead of the one we'd
+ // already decided to use.
+ debug_assert!(path_htlc_minimum_msat < old_entry.path_htlc_minimum_msat);
+ debug_assert!(
+ value_contribution_msat + path_penalty_msat <
+ old_entry.value_contribution_msat + old_entry.path_penalty_msat
+ );
+ }
}
}
}
+ } else {
+ if should_log_candidate {
+ log_trace!(logger,
+ "Ignoring {} due to its htlc_minimum_msat limit.",
+ LoggedCandidateHop(&$candidate));
+ }
+ num_ignored_htlc_minimum_msat_limit += 1;
}
}
}
- did_add_update_path_to_src_node
+ hop_contribution_amt_msat
} }
}
// in the regular network graph.
first_hop_targets.get(&intro_node_id).is_some() ||
network_nodes.get(&intro_node_id).is_some();
- if !have_intro_node_in_graph { continue }
+ if !have_intro_node_in_graph || our_node_id == intro_node_id { continue }
let candidate = if hint.1.blinded_hops.len() == 1 {
CandidateRouteHop::OneHopBlinded { hint, hint_idx }
} else { CandidateRouteHop::Blinded { hint, hint_idx } };
Some(fee) => fee,
None => continue
};
+ let path_min = candidate.htlc_minimum_msat().saturating_add(
+ compute_fees_saturating(candidate.htlc_minimum_msat(), candidate.fees()));
add_entry!(first_hop_candidate, our_node_id, intro_node_id, blinded_path_fee,
- path_contribution_msat, candidate.htlc_minimum_msat(), 0_u64,
- candidate.cltv_expiry_delta(),
+ path_contribution_msat, path_min, 0_u64, candidate.cltv_expiry_delta(),
candidate.blinded_path().map_or(1, |bp| bp.blinded_hops.len() as u8));
}
}
for route in payment_params.payee.unblinded_route_hints().iter()
.filter(|route| !route.0.is_empty())
{
- let first_hop_in_route = &(route.0)[0];
- let have_hop_src_in_graph =
- // Only add the hops in this route to our candidate set if either
- // we have a direct channel to the first hop or the first hop is
- // in the regular network graph.
- first_hop_targets.get(&NodeId::from_pubkey(&first_hop_in_route.src_node_id)).is_some() ||
- network_nodes.get(&NodeId::from_pubkey(&first_hop_in_route.src_node_id)).is_some();
- if have_hop_src_in_graph {
+ let first_hop_src_id = NodeId::from_pubkey(&route.0.first().unwrap().src_node_id);
+ let first_hop_src_is_reachable =
+ // Only add the hops in this route to our candidate set if either we are part of
+ // the first hop, we have a direct channel to the first hop, or the first hop is in
+ // the regular network graph.
+ our_node_id == first_hop_src_id ||
+ first_hop_targets.get(&first_hop_src_id).is_some() ||
+ network_nodes.get(&first_hop_src_id).is_some();
+ if first_hop_src_is_reachable {
// We start building the path from reverse, i.e., from payee
// to the first RouteHintHop in the path.
let hop_iter = route.0.iter().rev();
for (idx, (hop, prev_hop_id)) in hop_iter.zip(prev_hop_iter).enumerate() {
let source = NodeId::from_pubkey(&hop.src_node_id);
let target = NodeId::from_pubkey(&prev_hop_id);
+
+ if let Some(first_channels) = first_hop_targets.get(&target) {
+ if first_channels.iter().any(|d| d.outbound_scid_alias == Some(hop.short_channel_id)) {
+ log_trace!(logger, "Ignoring route hint with SCID {} (and any previous) due to it being a direct channel of ours.",
+ hop.short_channel_id);
+ break;
+ }
+ }
+
let candidate = network_channels
.get(&hop.short_channel_id)
.and_then(|channel| channel.as_directed_to(&target))
.saturating_add(1);
// Searching for a direct channel between last checked hop and first_hop_targets
- if let Some(first_channels) = first_hop_targets.get_mut(&NodeId::from_pubkey(&prev_hop_id)) {
+ if let Some(first_channels) = first_hop_targets.get_mut(&target) {
sort_first_hop_channels(first_channels, &used_liquidities,
recommended_value_msat, our_node_pubkey);
for details in first_channels {
let first_hop_candidate = CandidateRouteHop::FirstHop { details };
- add_entry!(first_hop_candidate, our_node_id, NodeId::from_pubkey(&prev_hop_id),
+ add_entry!(first_hop_candidate, our_node_id, target,
aggregate_next_hops_fee_msat, aggregate_path_contribution_msat,
aggregate_next_hops_path_htlc_minimum_msat, aggregate_next_hops_path_penalty_msat,
aggregate_next_hops_cltv_delta, aggregate_next_hops_path_length);
.map_or(None, |inc| inc.checked_add(aggregate_next_hops_fee_msat));
aggregate_next_hops_fee_msat = if let Some(val) = hops_fee { val } else { break; };
- let hop_htlc_minimum_msat = candidate.htlc_minimum_msat();
- let hop_htlc_minimum_msat_inc = if let Some(val) = compute_fees(aggregate_next_hops_path_htlc_minimum_msat, hop.fees) { val } else { break; };
- let hops_path_htlc_minimum = aggregate_next_hops_path_htlc_minimum_msat
- .checked_add(hop_htlc_minimum_msat_inc);
- aggregate_next_hops_path_htlc_minimum_msat = if let Some(val) = hops_path_htlc_minimum { cmp::max(hop_htlc_minimum_msat, val) } else { break; };
+ // The next channel will need to relay this channel's min_htlc *plus* the fees taken by
+ // this route hint's source node to forward said min over this channel.
+ aggregate_next_hops_path_htlc_minimum_msat = {
+ let curr_htlc_min = cmp::max(
+ candidate.htlc_minimum_msat(), aggregate_next_hops_path_htlc_minimum_msat
+ );
+ let curr_htlc_min_fee = if let Some(val) = compute_fees(curr_htlc_min, hop.fees) { val } else { break };
+ if let Some(min) = curr_htlc_min.checked_add(curr_htlc_min_fee) { min } else { break }
+ };
if idx == route.0.len() - 1 {
// The last hop in this iterator is the first hop in
// recompute the fees again, so that if that's the case, we match the currently
// underpaid htlc_minimum_msat with fees.
debug_assert_eq!(payment_path.get_value_msat(), value_contribution_msat);
- value_contribution_msat = cmp::min(value_contribution_msat, final_value_msat);
- payment_path.update_value_and_recompute_fees(value_contribution_msat);
+ let desired_value_contribution = cmp::min(value_contribution_msat, final_value_msat);
+ value_contribution_msat = payment_path.update_value_and_recompute_fees(desired_value_contribution);
// Since a path allows to transfer as much value as
// the smallest channel it has ("bottleneck"), we should recompute
// because we deterministically terminated the search due to low liquidity.
if !found_new_path && channel_saturation_pow_half != 0 {
channel_saturation_pow_half = 0;
+ } else if !found_new_path && hit_minimum_limit && already_collected_value_msat < final_value_msat && path_value_msat != recommended_value_msat {
+ log_trace!(logger, "Failed to collect enough value, but running again to collect extra paths with a potentially higher limit.");
+ path_value_msat = recommended_value_msat;
} else if already_collected_value_msat >= recommended_value_msat || !found_new_path {
log_trace!(logger, "Have now collected {} msat (seeking {} msat) in paths. Last path loop {} a new path.",
already_collected_value_msat, recommended_value_msat, if found_new_path { "found" } else { "did not find" });
log_trace!(logger, "Collected exactly our payment amount on the first pass, without hitting an htlc_minimum_msat limit, exiting.");
break 'paths_collection;
}
- log_trace!(logger, "Collected our payment amount on the first pass, but running again to collect extra paths with a potentially higher limit.");
+ log_trace!(logger, "Collected our payment amount on the first pass, but running again to collect extra paths with a potentially higher value to meet htlc_minimum_msat limit.");
path_value_msat = recommended_value_msat;
}
}
let num_ignored_total = num_ignored_value_contribution + num_ignored_path_length_limit +
- num_ignored_cltv_delta_limit + num_ignored_previously_failed;
+ num_ignored_cltv_delta_limit + num_ignored_previously_failed +
+ num_ignored_avoid_overpayment + num_ignored_htlc_minimum_msat_limit +
+ num_ignored_total_fee_limit;
if num_ignored_total > 0 {
- log_trace!(logger, "Ignored {} candidate hops due to insufficient value contribution, {} due to path length limit, {} due to CLTV delta limit, {} due to previous payment failure. Total: {} ignored candidates.", num_ignored_value_contribution, num_ignored_path_length_limit, num_ignored_cltv_delta_limit, num_ignored_previously_failed, num_ignored_total);
+ log_trace!(logger,
+ "Ignored {} candidate hops due to insufficient value contribution, {} due to path length limit, {} due to CLTV delta limit, {} due to previous payment failure, {} due to htlc_minimum_msat limit, {} to avoid overpaying, {} due to maximum total fee limit. Total: {} ignored candidates.",
+ num_ignored_value_contribution, num_ignored_path_length_limit,
+ num_ignored_cltv_delta_limit, num_ignored_previously_failed,
+ num_ignored_htlc_minimum_msat_limit, num_ignored_avoid_overpayment,
+ num_ignored_total_fee_limit, num_ignored_total);
}
// Step (5).
}
let route = Route { paths, route_params: Some(route_params.clone()) };
+
+ // Make sure we would never create a route whose total fees exceed max_total_routing_fee_msat.
+ if let Some(max_total_routing_fee_msat) = route_params.max_total_routing_fee_msat {
+ if route.get_total_fees() > max_total_routing_fee_msat {
+ return Err(LightningError{err: format!("Failed to find route that adheres to the maximum total fee limit of {}msat",
+ max_total_routing_fee_msat), action: ErrorAction::IgnoreError});
+ }
+ }
+
log_info!(logger, "Got route: {}", log_route!(route));
Ok(route)
}
Arc::clone(&logger), &scorer, &Default::default(), &random_seed_bytes) {
assert_eq!(err, "First hop cannot have our_node_pubkey as a destination.");
} else { panic!(); }
-
+
let route = get_route(&our_id, &route_params, &network_graph.read_only(), None,
Arc::clone(&logger), &scorer, &Default::default(), &random_seed_bytes).unwrap();
assert_eq!(route.paths[0].hops.len(), 2);
excess_data: Vec::new()
});
- let route_params = RouteParameters::from_payment_params_and_value(
+ let mut route_params = RouteParameters::from_payment_params_and_value(
payment_params.clone(), 60_000);
+ route_params.max_total_routing_fee_msat = Some(15_000);
let route = get_route(&our_id, &route_params, &network_graph.read_only(), None,
Arc::clone(&logger), &scorer, &Default::default(), &random_seed_bytes).unwrap();
// Overpay fees to hit htlc_minimum_msat.
assert_eq!(fees, 5_000);
}
+ #[test]
+ fn htlc_minimum_recipient_overpay_test() {
+ let (secp_ctx, network_graph, gossip_sync, _, logger) = build_graph();
+ let (_, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
+ let config = UserConfig::default();
+ let payment_params = PaymentParameters::from_node_id(nodes[2], 42).with_bolt11_features(channelmanager::provided_invoice_features(&config)).unwrap();
+ let scorer = ln_test_utils::TestScorer::new();
+ let keys_manager = ln_test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet);
+ let random_seed_bytes = keys_manager.get_secure_random_bytes();
+
+ // Route to node2 over a single path which requires overpaying the recipient themselves.
+
+ // First disable all paths except the us -> node1 -> node2 path
+ update_channel(&gossip_sync, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 13,
+ timestamp: 2,
+ flags: 3,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: 0,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Set channel 4 to free but with a high htlc_minimum_msat
+ update_channel(&gossip_sync, &secp_ctx, &privkeys[1], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 4,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 15_000,
+ htlc_maximum_msat: MAX_VALUE_MSAT,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Now check that we'll fail to find a path if we fail to find a path if the htlc_minimum
+ // is overrun. Note that the fees are actually calculated on 3*payment amount as that's
+ // what we try to find a route for, so this test only just happens to work out to exactly
+ // the fee limit.
+ let mut route_params = RouteParameters::from_payment_params_and_value(
+ payment_params.clone(), 5_000);
+ route_params.max_total_routing_fee_msat = Some(9_999);
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id,
+ &route_params, &network_graph.read_only(), None, Arc::clone(&logger), &scorer,
+ &Default::default(), &random_seed_bytes) {
+ assert_eq!(err, "Failed to find route that adheres to the maximum total fee limit of 9999msat");
+ } else { panic!(); }
+
+ let mut route_params = RouteParameters::from_payment_params_and_value(
+ payment_params.clone(), 5_000);
+ route_params.max_total_routing_fee_msat = Some(10_000);
+ let route = get_route(&our_id, &route_params, &network_graph.read_only(), None,
+ Arc::clone(&logger), &scorer, &Default::default(), &random_seed_bytes).unwrap();
+ assert_eq!(route.get_total_fees(), 10_000);
+ }
+
#[test]
fn disable_channels_test() {
let (secp_ctx, network_graph, gossip_sync, _, logger) = build_graph();
} else { panic!(); }
}
+ {
+ // Attempt to route while setting max_total_routing_fee_msat to 149_999 results in a failure.
+ let route_params = RouteParameters { payment_params: payment_params.clone(), final_value_msat: 200_000,
+ max_total_routing_fee_msat: Some(149_999) };
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(
+ &our_id, &route_params, &network_graph.read_only(), None, Arc::clone(&logger),
+ &scorer, &(), &random_seed_bytes) {
+ assert_eq!(err, "Failed to find a sufficient route to the given destination");
+ } else { panic!(); }
+ }
+
{
// Now, attempt to route 200 sats (exact amount we can route).
- let route_params = RouteParameters::from_payment_params_and_value(payment_params, 200_000);
+ let route_params = RouteParameters { payment_params: payment_params.clone(), final_value_msat: 200_000,
+ max_total_routing_fee_msat: Some(150_000) };
let route = get_route(&our_id, &route_params, &network_graph.read_only(), None,
Arc::clone(&logger), &scorer, &Default::default(), &random_seed_bytes).unwrap();
assert_eq!(route.paths.len(), 2);
{
// Now, attempt to route 90 sats, which is exactly 90 sats at the last hop, plus the
// 200% fee charged channel 13 in the 1-to-2 direction.
- let route_params = RouteParameters::from_payment_params_and_value(
+ let mut route_params = RouteParameters::from_payment_params_and_value(
payment_params, 90_000);
+ route_params.max_total_routing_fee_msat = Some(90_000*2);
let route = get_route(&our_id, &route_params, &network_graph.read_only(), None,
Arc::clone(&logger), &scorer, &Default::default(), &random_seed_bytes).unwrap();
assert_eq!(route.paths.len(), 1);
// Now, attempt to route 90 sats, hitting the htlc_minimum on channel 4, but
// overshooting the htlc_maximum on channel 2. Thus, we should pick the (absurdly
// expensive) channels 12-13 path.
- let route_params = RouteParameters::from_payment_params_and_value(
+ let mut route_params = RouteParameters::from_payment_params_and_value(
payment_params, 90_000);
+ route_params.max_total_routing_fee_msat = Some(90_000*2);
let route = get_route(&our_id, &route_params, &network_graph.read_only(), None,
Arc::clone(&logger), &scorer, &Default::default(), &random_seed_bytes).unwrap();
assert_eq!(route.paths.len(), 1);
// Make sure we'll error if our route hints don't have enough liquidity according to their
// htlc_maximum_msat.
- let route_params = RouteParameters::from_payment_params_and_value(
+ let mut route_params = RouteParameters::from_payment_params_and_value(
payment_params, max_htlc_msat + 1);
+ route_params.max_total_routing_fee_msat = None;
if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id,
&route_params, &netgraph, None, Arc::clone(&logger), &scorer, &Default::default(),
&random_seed_bytes)
let payment_params = PaymentParameters::from_node_id(dest_node_id, 42)
.with_route_hints(vec![route_hint_1, route_hint_2]).unwrap()
.with_bolt11_features(channelmanager::provided_invoice_features(&config)).unwrap();
- let route_params = RouteParameters::from_payment_params_and_value(
+ let mut route_params = RouteParameters::from_payment_params_and_value(
payment_params, max_htlc_msat + 1);
+ route_params.max_total_routing_fee_msat = Some(max_htlc_msat * 2);
let route = get_route(&our_id, &route_params, &netgraph, None, Arc::clone(&logger),
&scorer, &Default::default(), &random_seed_bytes).unwrap();
assert_eq!(route.paths.len(), 2);
let payment_params = PaymentParameters::blinded(blinded_hints.clone())
.with_bolt12_features(bolt12_features.clone()).unwrap();
- let route_params = RouteParameters::from_payment_params_and_value(payment_params, 100_000);
+ let mut route_params = RouteParameters::from_payment_params_and_value(payment_params, 100_000);
+ route_params.max_total_routing_fee_msat = Some(100_000);
let route = get_route(&our_id, &route_params, &network_graph, None, Arc::clone(&logger),
&scorer, &Default::default(), &random_seed_bytes).unwrap();
assert_eq!(route.paths.len(), 2);
assert_eq!(route.get_total_fees(), blinded_payinfo.fee_base_msat as u64);
assert_eq!(route.get_total_amount(), amt_msat);
}
+
+ #[test]
+ fn we_are_intro_node_candidate_hops() {
+ // This previously led to a panic in the router because we'd generate a Path with only a
+ // BlindedTail and 0 unblinded hops, due to the only candidate hops being blinded route hints
+ // where the origin node is the intro node. We now fully disallow considering candidate hops
+ // where the origin node is the intro node.
+ let (secp_ctx, network_graph, _, _, logger) = build_graph();
+ let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
+ let scorer = ln_test_utils::TestScorer::new();
+ let keys_manager = ln_test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet);
+ let random_seed_bytes = keys_manager.get_secure_random_bytes();
+ let config = UserConfig::default();
+
+ // Values are taken from the fuzz input that uncovered this panic.
+ let amt_msat = 21_7020_5185_1423_0019;
+
+ let blinded_path = BlindedPath {
+ introduction_node_id: our_id,
+ blinding_point: ln_test_utils::pubkey(42),
+ blinded_hops: vec![
+ BlindedHop { blinded_node_id: ln_test_utils::pubkey(42 as u8), encrypted_payload: Vec::new() },
+ BlindedHop { blinded_node_id: ln_test_utils::pubkey(42 as u8), encrypted_payload: Vec::new() }
+ ],
+ };
+ let blinded_payinfo = BlindedPayInfo {
+ fee_base_msat: 5052_9027,
+ fee_proportional_millionths: 0,
+ htlc_minimum_msat: 21_7020_5185_1423_0019,
+ htlc_maximum_msat: 1844_6744_0737_0955_1615,
+ cltv_expiry_delta: 0,
+ features: BlindedHopFeatures::empty(),
+ };
+ let mut blinded_hints = vec![
+ (blinded_payinfo.clone(), blinded_path.clone()),
+ (blinded_payinfo.clone(), blinded_path.clone()),
+ ];
+ blinded_hints[1].1.introduction_node_id = nodes[6];
+
+ let bolt12_features: Bolt12InvoiceFeatures = channelmanager::provided_invoice_features(&config).to_context();
+ let payment_params = PaymentParameters::blinded(blinded_hints.clone())
+ .with_bolt12_features(bolt12_features.clone()).unwrap();
+
+ let netgraph = network_graph.read_only();
+ let route_params = RouteParameters::from_payment_params_and_value(
+ payment_params, amt_msat);
+ if let Err(LightningError { err, .. }) = get_route(
+ &our_id, &route_params, &netgraph, None, Arc::clone(&logger), &scorer, &(), &random_seed_bytes
+ ) {
+ assert_eq!(err, "Failed to find a path to the given destination");
+ } else { panic!() }
+ }
+
+ #[test]
+ fn we_are_intro_node_bp_in_final_path_fee_calc() {
+ // This previously led to a debug panic in the router because we'd find an invalid Path with
+ // 0 unblinded hops and a blinded tail, leading to the generation of a final
+ // PaymentPathHop::fee_msat that included both the blinded path fees and the final value of
+ // the payment, when it was intended to only include the final value of the payment.
+ let (secp_ctx, network_graph, _, _, logger) = build_graph();
+ let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
+ let scorer = ln_test_utils::TestScorer::new();
+ let keys_manager = ln_test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet);
+ let random_seed_bytes = keys_manager.get_secure_random_bytes();
+ let config = UserConfig::default();
+
+ // Values are taken from the fuzz input that uncovered this panic.
+ let amt_msat = 21_7020_5185_1423_0019;
+
+ let blinded_path = BlindedPath {
+ introduction_node_id: our_id,
+ blinding_point: ln_test_utils::pubkey(42),
+ blinded_hops: vec![
+ BlindedHop { blinded_node_id: ln_test_utils::pubkey(42 as u8), encrypted_payload: Vec::new() },
+ BlindedHop { blinded_node_id: ln_test_utils::pubkey(42 as u8), encrypted_payload: Vec::new() }
+ ],
+ };
+ let blinded_payinfo = BlindedPayInfo {
+ fee_base_msat: 10_4425_1395,
+ fee_proportional_millionths: 0,
+ htlc_minimum_msat: 21_7301_9934_9094_0931,
+ htlc_maximum_msat: 1844_6744_0737_0955_1615,
+ cltv_expiry_delta: 0,
+ features: BlindedHopFeatures::empty(),
+ };
+ let mut blinded_hints = vec![
+ (blinded_payinfo.clone(), blinded_path.clone()),
+ (blinded_payinfo.clone(), blinded_path.clone()),
+ (blinded_payinfo.clone(), blinded_path.clone()),
+ ];
+ blinded_hints[1].0.fee_base_msat = 5052_9027;
+ blinded_hints[1].0.htlc_minimum_msat = 21_7020_5185_1423_0019;
+ blinded_hints[1].0.htlc_maximum_msat = 1844_6744_0737_0955_1615;
+
+ blinded_hints[2].1.introduction_node_id = nodes[6];
+
+ let bolt12_features: Bolt12InvoiceFeatures = channelmanager::provided_invoice_features(&config).to_context();
+ let payment_params = PaymentParameters::blinded(blinded_hints.clone())
+ .with_bolt12_features(bolt12_features.clone()).unwrap();
+
+ let netgraph = network_graph.read_only();
+ let route_params = RouteParameters::from_payment_params_and_value(
+ payment_params, amt_msat);
+ if let Err(LightningError { err, .. }) = get_route(
+ &our_id, &route_params, &netgraph, None, Arc::clone(&logger), &scorer, &(), &random_seed_bytes
+ ) {
+ assert_eq!(err, "Failed to find a path to the given destination");
+ } else { panic!() }
+ }
+
+ #[test]
+ fn min_htlc_overpay_violates_max_htlc() {
+ do_min_htlc_overpay_violates_max_htlc(true);
+ do_min_htlc_overpay_violates_max_htlc(false);
+ }
+ fn do_min_htlc_overpay_violates_max_htlc(blinded_payee: bool) {
+ // Test that if overpaying to meet a later hop's min_htlc and causes us to violate an earlier
+ // hop's max_htlc, we don't consider that candidate hop valid. Previously we would add this hop
+ // to `targets` and build an invalid path with it, and subsquently hit a debug panic asserting
+ // that the used liquidity for a hop was less than its available liquidity limit.
+ let secp_ctx = Secp256k1::new();
+ let logger = Arc::new(ln_test_utils::TestLogger::new());
+ let network_graph = Arc::new(NetworkGraph::new(Network::Testnet, Arc::clone(&logger)));
+ let scorer = ln_test_utils::TestScorer::new();
+ let keys_manager = ln_test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet);
+ let random_seed_bytes = keys_manager.get_secure_random_bytes();
+ let config = UserConfig::default();
+
+ // Values are taken from the fuzz input that uncovered this panic.
+ let amt_msat = 7_4009_8048;
+ let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
+ let first_hop_outbound_capacity = 2_7345_2000;
+ let first_hops = vec![get_channel_details(
+ Some(200), nodes[0], channelmanager::provided_init_features(&config),
+ first_hop_outbound_capacity
+ )];
+
+ let base_fee = 1_6778_3453;
+ let htlc_min = 2_5165_8240;
+ let payment_params = if blinded_payee {
+ let blinded_path = BlindedPath {
+ introduction_node_id: nodes[0],
+ blinding_point: ln_test_utils::pubkey(42),
+ blinded_hops: vec![
+ BlindedHop { blinded_node_id: ln_test_utils::pubkey(42 as u8), encrypted_payload: Vec::new() },
+ BlindedHop { blinded_node_id: ln_test_utils::pubkey(42 as u8), encrypted_payload: Vec::new() }
+ ],
+ };
+ let blinded_payinfo = BlindedPayInfo {
+ fee_base_msat: base_fee,
+ fee_proportional_millionths: 0,
+ htlc_minimum_msat: htlc_min,
+ htlc_maximum_msat: htlc_min * 1000,
+ cltv_expiry_delta: 0,
+ features: BlindedHopFeatures::empty(),
+ };
+ let bolt12_features: Bolt12InvoiceFeatures = channelmanager::provided_invoice_features(&config).to_context();
+ PaymentParameters::blinded(vec![(blinded_payinfo, blinded_path)])
+ .with_bolt12_features(bolt12_features.clone()).unwrap()
+ } else {
+ let route_hint = RouteHint(vec![RouteHintHop {
+ src_node_id: nodes[0],
+ short_channel_id: 42,
+ fees: RoutingFees {
+ base_msat: base_fee,
+ proportional_millionths: 0,
+ },
+ cltv_expiry_delta: 10,
+ htlc_minimum_msat: Some(htlc_min),
+ htlc_maximum_msat: None,
+ }]);
+
+ PaymentParameters::from_node_id(nodes[1], 42)
+ .with_route_hints(vec![route_hint]).unwrap()
+ .with_bolt11_features(channelmanager::provided_invoice_features(&config)).unwrap()
+ };
+
+ let netgraph = network_graph.read_only();
+ let route_params = RouteParameters::from_payment_params_and_value(
+ payment_params, amt_msat);
+ if let Err(LightningError { err, .. }) = get_route(
+ &our_id, &route_params, &netgraph, Some(&first_hops.iter().collect::<Vec<_>>()),
+ Arc::clone(&logger), &scorer, &(), &random_seed_bytes
+ ) {
+ assert_eq!(err, "Failed to find a path to the given destination");
+ } else { panic!() }
+ }
+
+ #[test]
+ fn previously_used_liquidity_violates_max_htlc() {
+ do_previously_used_liquidity_violates_max_htlc(true);
+ do_previously_used_liquidity_violates_max_htlc(false);
+
+ }
+ fn do_previously_used_liquidity_violates_max_htlc(blinded_payee: bool) {
+ // Test that if a candidate first_hop<>route_hint_src_node channel does not have enough
+ // contribution amount to cover the next hop's min_htlc plus fees, we will not consider that
+ // candidate. In this case, the candidate does not have enough due to a previous path taking up
+ // some of its liquidity. Previously we would construct an invalid path and hit a debug panic
+ // asserting that the used liquidity for a hop was less than its available liquidity limit.
+ let secp_ctx = Secp256k1::new();
+ let logger = Arc::new(ln_test_utils::TestLogger::new());
+ let network_graph = Arc::new(NetworkGraph::new(Network::Testnet, Arc::clone(&logger)));
+ let scorer = ln_test_utils::TestScorer::new();
+ let keys_manager = ln_test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet);
+ let random_seed_bytes = keys_manager.get_secure_random_bytes();
+ let config = UserConfig::default();
+
+ // Values are taken from the fuzz input that uncovered this panic.
+ let amt_msat = 52_4288;
+ let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
+ let first_hops = vec![get_channel_details(
+ Some(161), nodes[0], channelmanager::provided_init_features(&config), 486_4000
+ ), get_channel_details(
+ Some(122), nodes[0], channelmanager::provided_init_features(&config), 179_5000
+ )];
+
+ let base_fees = [0, 425_9840, 0, 0];
+ let htlc_mins = [1_4392, 19_7401, 1027, 6_5535];
+ let payment_params = if blinded_payee {
+ let blinded_path = BlindedPath {
+ introduction_node_id: nodes[0],
+ blinding_point: ln_test_utils::pubkey(42),
+ blinded_hops: vec![
+ BlindedHop { blinded_node_id: ln_test_utils::pubkey(42 as u8), encrypted_payload: Vec::new() },
+ BlindedHop { blinded_node_id: ln_test_utils::pubkey(42 as u8), encrypted_payload: Vec::new() }
+ ],
+ };
+ let mut blinded_hints = Vec::new();
+ for (base_fee, htlc_min) in base_fees.iter().zip(htlc_mins.iter()) {
+ blinded_hints.push((BlindedPayInfo {
+ fee_base_msat: *base_fee,
+ fee_proportional_millionths: 0,
+ htlc_minimum_msat: *htlc_min,
+ htlc_maximum_msat: htlc_min * 100,
+ cltv_expiry_delta: 10,
+ features: BlindedHopFeatures::empty(),
+ }, blinded_path.clone()));
+ }
+ let bolt12_features: Bolt12InvoiceFeatures = channelmanager::provided_invoice_features(&config).to_context();
+ PaymentParameters::blinded(blinded_hints.clone())
+ .with_bolt12_features(bolt12_features.clone()).unwrap()
+ } else {
+ let mut route_hints = Vec::new();
+ for (idx, (base_fee, htlc_min)) in base_fees.iter().zip(htlc_mins.iter()).enumerate() {
+ route_hints.push(RouteHint(vec![RouteHintHop {
+ src_node_id: nodes[0],
+ short_channel_id: 42 + idx as u64,
+ fees: RoutingFees {
+ base_msat: *base_fee,
+ proportional_millionths: 0,
+ },
+ cltv_expiry_delta: 10,
+ htlc_minimum_msat: Some(*htlc_min),
+ htlc_maximum_msat: Some(htlc_min * 100),
+ }]));
+ }
+ PaymentParameters::from_node_id(nodes[1], 42)
+ .with_route_hints(route_hints).unwrap()
+ .with_bolt11_features(channelmanager::provided_invoice_features(&config)).unwrap()
+ };
+
+ let netgraph = network_graph.read_only();
+ let route_params = RouteParameters::from_payment_params_and_value(
+ payment_params, amt_msat);
+
+ let route = get_route(
+ &our_id, &route_params, &netgraph, Some(&first_hops.iter().collect::<Vec<_>>()),
+ Arc::clone(&logger), &scorer, &(), &random_seed_bytes
+ ).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ assert_eq!(route.get_total_amount(), amt_msat);
+ }
+
+ #[test]
+ fn candidate_path_min() {
+ // Test that if a candidate first_hop<>network_node channel does not have enough contribution
+ // amount to cover the next channel's min htlc plus fees, we will not consider that candidate.
+ // Previously, we were storing RouteGraphNodes with a path_min that did not include fees, and
+ // would add a connecting first_hop node that did not have enough contribution amount, leading
+ // to a debug panic upon invalid path construction.
+ let secp_ctx = Secp256k1::new();
+ let logger = Arc::new(ln_test_utils::TestLogger::new());
+ let network_graph = Arc::new(NetworkGraph::new(Network::Testnet, Arc::clone(&logger)));
+ let gossip_sync = P2PGossipSync::new(network_graph.clone(), None, logger.clone());
+ let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), network_graph.clone(), logger.clone());
+ let keys_manager = ln_test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet);
+ let random_seed_bytes = keys_manager.get_secure_random_bytes();
+ let config = UserConfig::default();
+
+ // Values are taken from the fuzz input that uncovered this panic.
+ let amt_msat = 7_4009_8048;
+ let (_, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
+ let first_hops = vec![get_channel_details(
+ Some(200), nodes[0], channelmanager::provided_init_features(&config), 2_7345_2000
+ )];
+
+ add_channel(&gossip_sync, &secp_ctx, &privkeys[0], &privkeys[6], ChannelFeatures::from_le_bytes(id_to_feature_flags(6)), 6);
+ update_channel(&gossip_sync, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 6,
+ timestamp: 1,
+ flags: 0,
+ cltv_expiry_delta: (6 << 4) | 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: MAX_VALUE_MSAT,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ add_or_update_node(&gossip_sync, &secp_ctx, &privkeys[0], NodeFeatures::from_le_bytes(id_to_feature_flags(1)), 0);
+
+ let htlc_min = 2_5165_8240;
+ let blinded_hints = vec![
+ (BlindedPayInfo {
+ fee_base_msat: 1_6778_3453,
+ fee_proportional_millionths: 0,
+ htlc_minimum_msat: htlc_min,
+ htlc_maximum_msat: htlc_min * 100,
+ cltv_expiry_delta: 10,
+ features: BlindedHopFeatures::empty(),
+ }, BlindedPath {
+ introduction_node_id: nodes[0],
+ blinding_point: ln_test_utils::pubkey(42),
+ blinded_hops: vec![
+ BlindedHop { blinded_node_id: ln_test_utils::pubkey(42 as u8), encrypted_payload: Vec::new() },
+ BlindedHop { blinded_node_id: ln_test_utils::pubkey(42 as u8), encrypted_payload: Vec::new() }
+ ],
+ })
+ ];
+ let bolt12_features: Bolt12InvoiceFeatures = channelmanager::provided_invoice_features(&config).to_context();
+ let payment_params = PaymentParameters::blinded(blinded_hints.clone())
+ .with_bolt12_features(bolt12_features.clone()).unwrap();
+ let route_params = RouteParameters::from_payment_params_and_value(
+ payment_params, amt_msat);
+ let netgraph = network_graph.read_only();
+
+ if let Err(LightningError { err, .. }) = get_route(
+ &our_id, &route_params, &netgraph, Some(&first_hops.iter().collect::<Vec<_>>()),
+ Arc::clone(&logger), &scorer, &ProbabilisticScoringFeeParameters::default(),
+ &random_seed_bytes
+ ) {
+ assert_eq!(err, "Failed to find a path to the given destination");
+ } else { panic!() }
+ }
+
+ #[test]
+ fn path_contribution_includes_min_htlc_overpay() {
+ // Previously, the fuzzer hit a debug panic because we wouldn't include the amount overpaid to
+ // meet a last hop's min_htlc in the total collected paths value. We now include this value and
+ // also penalize hops along the overpaying path to ensure that it gets deprioritized in path
+ // selection, both tested here.
+ let secp_ctx = Secp256k1::new();
+ let logger = Arc::new(ln_test_utils::TestLogger::new());
+ let network_graph = Arc::new(NetworkGraph::new(Network::Testnet, Arc::clone(&logger)));
+ let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), network_graph.clone(), logger.clone());
+ let keys_manager = ln_test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet);
+ let random_seed_bytes = keys_manager.get_secure_random_bytes();
+ let config = UserConfig::default();
+
+ // Values are taken from the fuzz input that uncovered this panic.
+ let amt_msat = 562_0000;
+ let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
+ let first_hops = vec![
+ get_channel_details(
+ Some(83), nodes[0], channelmanager::provided_init_features(&config), 2199_0000,
+ ),
+ ];
+
+ let htlc_mins = [49_0000, 1125_0000];
+ let payment_params = {
+ let blinded_path = BlindedPath {
+ introduction_node_id: nodes[0],
+ blinding_point: ln_test_utils::pubkey(42),
+ blinded_hops: vec![
+ BlindedHop { blinded_node_id: ln_test_utils::pubkey(42 as u8), encrypted_payload: Vec::new() },
+ BlindedHop { blinded_node_id: ln_test_utils::pubkey(42 as u8), encrypted_payload: Vec::new() }
+ ],
+ };
+ let mut blinded_hints = Vec::new();
+ for htlc_min in htlc_mins.iter() {
+ blinded_hints.push((BlindedPayInfo {
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ htlc_minimum_msat: *htlc_min,
+ htlc_maximum_msat: *htlc_min * 100,
+ cltv_expiry_delta: 10,
+ features: BlindedHopFeatures::empty(),
+ }, blinded_path.clone()));
+ }
+ let bolt12_features: Bolt12InvoiceFeatures = channelmanager::provided_invoice_features(&config).to_context();
+ PaymentParameters::blinded(blinded_hints.clone())
+ .with_bolt12_features(bolt12_features.clone()).unwrap()
+ };
+
+ let netgraph = network_graph.read_only();
+ let route_params = RouteParameters::from_payment_params_and_value(
+ payment_params, amt_msat);
+ let route = get_route(
+ &our_id, &route_params, &netgraph, Some(&first_hops.iter().collect::<Vec<_>>()),
+ Arc::clone(&logger), &scorer, &ProbabilisticScoringFeeParameters::default(),
+ &random_seed_bytes
+ ).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ assert_eq!(route.get_total_amount(), amt_msat);
+ }
+
+ #[test]
+ fn first_hop_preferred_over_hint() {
+ // Check that if we have a first hop to a peer we'd always prefer that over a route hint
+ // they gave us, but we'd still consider all subsequent hints if they are more attractive.
+ let secp_ctx = Secp256k1::new();
+ let logger = Arc::new(ln_test_utils::TestLogger::new());
+ let network_graph = Arc::new(NetworkGraph::new(Network::Testnet, Arc::clone(&logger)));
+ let gossip_sync = P2PGossipSync::new(Arc::clone(&network_graph), None, Arc::clone(&logger));
+ let scorer = ln_test_utils::TestScorer::new();
+ let keys_manager = ln_test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet);
+ let random_seed_bytes = keys_manager.get_secure_random_bytes();
+ let config = UserConfig::default();
+
+ let amt_msat = 1_000_000;
+ let (our_privkey, our_node_id, privkeys, nodes) = get_nodes(&secp_ctx);
+
+ add_channel(&gossip_sync, &secp_ctx, &our_privkey, &privkeys[0],
+ ChannelFeatures::from_le_bytes(id_to_feature_flags(1)), 1);
+ update_channel(&gossip_sync, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 1,
+ timestamp: 1,
+ flags: 0,
+ cltv_expiry_delta: 42,
+ htlc_minimum_msat: 1_000,
+ htlc_maximum_msat: 10_000_000,
+ fee_base_msat: 800,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&gossip_sync, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 1,
+ timestamp: 1,
+ flags: 1,
+ cltv_expiry_delta: 42,
+ htlc_minimum_msat: 1_000,
+ htlc_maximum_msat: 10_000_000,
+ fee_base_msat: 800,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ add_channel(&gossip_sync, &secp_ctx, &privkeys[0], &privkeys[1],
+ ChannelFeatures::from_le_bytes(id_to_feature_flags(1)), 2);
+ update_channel(&gossip_sync, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 2,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 42,
+ htlc_minimum_msat: 1_000,
+ htlc_maximum_msat: 10_000_000,
+ fee_base_msat: 800,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&gossip_sync, &secp_ctx, &privkeys[1], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 2,
+ timestamp: 2,
+ flags: 1,
+ cltv_expiry_delta: 42,
+ htlc_minimum_msat: 1_000,
+ htlc_maximum_msat: 10_000_000,
+ fee_base_msat: 800,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ let dest_node_id = nodes[2];
+
+ let route_hint = RouteHint(vec![RouteHintHop {
+ src_node_id: our_node_id,
+ short_channel_id: 44,
+ fees: RoutingFees {
+ base_msat: 234,
+ proportional_millionths: 0,
+ },
+ cltv_expiry_delta: 10,
+ htlc_minimum_msat: None,
+ htlc_maximum_msat: Some(5_000_000),
+ },
+ RouteHintHop {
+ src_node_id: nodes[0],
+ short_channel_id: 45,
+ fees: RoutingFees {
+ base_msat: 123,
+ proportional_millionths: 0,
+ },
+ cltv_expiry_delta: 10,
+ htlc_minimum_msat: None,
+ htlc_maximum_msat: None,
+ }]);
+
+ let payment_params = PaymentParameters::from_node_id(dest_node_id, 42)
+ .with_route_hints(vec![route_hint]).unwrap()
+ .with_bolt11_features(channelmanager::provided_invoice_features(&config)).unwrap();
+ let route_params = RouteParameters::from_payment_params_and_value(
+ payment_params, amt_msat);
+
+ // First create an insufficient first hop for channel with SCID 1 and check we'd use the
+ // route hint.
+ let first_hop = get_channel_details(Some(1), nodes[0],
+ channelmanager::provided_init_features(&config), 999_999);
+ let first_hops = vec![first_hop];
+
+ let route = get_route(&our_node_id, &route_params.clone(), &network_graph.read_only(),
+ Some(&first_hops.iter().collect::<Vec<_>>()), Arc::clone(&logger), &scorer,
+ &Default::default(), &random_seed_bytes).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ assert_eq!(route.get_total_amount(), amt_msat);
+ assert_eq!(route.paths[0].hops.len(), 2);
+ assert_eq!(route.paths[0].hops[0].short_channel_id, 44);
+ assert_eq!(route.paths[0].hops[1].short_channel_id, 45);
+ assert_eq!(route.get_total_fees(), 123);
+
+ // Now check we would trust our first hop info, i.e., fail if we detect the route hint is
+ // for a first hop channel.
+ let mut first_hop = get_channel_details(Some(1), nodes[0], channelmanager::provided_init_features(&config), 999_999);
+ first_hop.outbound_scid_alias = Some(44);
+ let first_hops = vec![first_hop];
+
+ let route_res = get_route(&our_node_id, &route_params.clone(), &network_graph.read_only(),
+ Some(&first_hops.iter().collect::<Vec<_>>()), Arc::clone(&logger), &scorer,
+ &Default::default(), &random_seed_bytes);
+ assert!(route_res.is_err());
+
+ // Finally check we'd use the first hop if has sufficient outbound capacity. But we'd stil
+ // use the cheaper second hop of the route hint.
+ let mut first_hop = get_channel_details(Some(1), nodes[0],
+ channelmanager::provided_init_features(&config), 10_000_000);
+ first_hop.outbound_scid_alias = Some(44);
+ let first_hops = vec![first_hop];
+
+ let route = get_route(&our_node_id, &route_params.clone(), &network_graph.read_only(),
+ Some(&first_hops.iter().collect::<Vec<_>>()), Arc::clone(&logger), &scorer,
+ &Default::default(), &random_seed_bytes).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ assert_eq!(route.get_total_amount(), amt_msat);
+ assert_eq!(route.paths[0].hops.len(), 2);
+ assert_eq!(route.paths[0].hops[0].short_channel_id, 1);
+ assert_eq!(route.paths[0].hops[1].short_channel_id, 45);
+ assert_eq!(route.get_total_fees(), 123);
+ }
}
#[cfg(all(any(test, ldk_bench), not(feature = "no-std")))]
projects / rust-lightning / blobdiff