//! You probably want to create a NetGraphMsgHandler and use that as your RoutingMessageHandler and then
//! interrogate it to get routes for your own payments.
-use bitcoin::secp256k1::key::PublicKey;
+use bitcoin::secp256k1::PublicKey;
use ln::channelmanager::ChannelDetails;
use ln::features::{ChannelFeatures, InvoiceFeatures, NodeFeatures};
use ln::msgs::{DecodeError, ErrorAction, LightningError, MAX_VALUE_MSAT};
-use routing::scoring::Score;
+use routing::scoring::{ChannelUsage, Score};
use routing::network_graph::{DirectedChannelInfoWithUpdate, EffectiveCapacity, NetworkGraph, ReadOnlyNetworkGraph, NodeId, RoutingFees};
-use util::ser::{Writeable, Readable};
+use util::ser::{Writeable, Readable, Writer};
use util::logger::{Level, Logger};
use util::chacha20::ChaCha20;
#[derive(Clone, Hash, PartialEq, Eq)]
pub struct Route {
/// The list of routes taken for a single (potentially-)multi-part payment. The pubkey of the
- /// last RouteHop in each path must be the same.
- /// Each entry represents a list of hops, NOT INCLUDING our own, where the last hop is the
- /// destination. Thus, this must always be at least length one. While the maximum length of any
- /// given path is variable, keeping the length of any path to less than 20 should currently
- /// ensure it is viable.
+ /// last RouteHop in each path must be the same. Each entry represents a list of hops, NOT
+ /// INCLUDING our own, where the last hop is the destination. Thus, this must always be at
+ /// least length one. While the maximum length of any given path is variable, keeping the length
+ /// of any path less or equal to 19 should currently ensure it is viable.
pub paths: Vec<Vec<RouteHop>>,
/// The `payment_params` parameter passed to [`find_route`].
/// This is used by `ChannelManager` to track information which may be required for retries,
/// Parameters needed to find a [`Route`].
///
-/// Passed to [`find_route`] and also provided in [`Event::PaymentPathFailed`] for retrying a failed
-/// payment path.
+/// Passed to [`find_route`] and [`build_route_from_hops`], but also provided in
+/// [`Event::PaymentPathFailed`] for retrying a failed payment path.
///
/// [`Event::PaymentPathFailed`]: crate::util::events::Event::PaymentPathFailed
#[derive(Clone, Debug)]
/// Maximum total CTLV difference we allow for a full payment path.
pub const DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA: u32 = 1008;
-/// The median hop CLTV expiry delta currently seen in the network.
+// The median hop CLTV expiry delta currently seen in the network.
const MEDIAN_HOP_CLTV_EXPIRY_DELTA: u32 = 40;
+// During routing, we only consider paths shorter than our maximum length estimate.
+// In the legacy onion format, the maximum number of hops used to be a fixed value of 20.
+// However, in the TLV onion format, there is no fixed maximum length, but the `hop_payloads`
+// field is always 1300 bytes. As the `tlv_payload` for each hop may vary in length, we have to
+// estimate how many hops the route may have so that it actually fits the `hop_payloads` field.
+//
+// We estimate 3+32 (payload length and HMAC) + 2+8 (amt_to_forward) + 2+4 (outgoing_cltv_value) +
+// 2+8 (short_channel_id) = 61 bytes for each intermediate hop and 3+32
+// (payload length and HMAC) + 2+8 (amt_to_forward) + 2+4 (outgoing_cltv_value) + 2+32+8
+// (payment_secret and total_msat) = 93 bytes for the final hop.
+// Since the length of the potentially included `payment_metadata` is unknown to us, we round
+// down from (1300-93) / 61 = 19.78... to arrive at a conservative estimate of 19.
+const MAX_PATH_LENGTH_ESTIMATE: u8 = 19;
+
/// The recipient of a payment.
#[derive(Clone, Debug, Hash, PartialEq, Eq)]
pub struct PaymentParameters {
/// All penalties incurred from this hop on the way to the destination, as calculated using
/// channel scoring.
path_penalty_msat: u64,
+ /// The number of hops walked up to this node.
+ path_length_to_node: u8,
}
impl cmp::Ord for RouteGraphNode {
impl<'a> CandidateRouteHop<'a> {
fn short_channel_id(&self) -> u64 {
match self {
- CandidateRouteHop::FirstHop { details } => details.short_channel_id.unwrap(),
+ CandidateRouteHop::FirstHop { details } => details.get_outbound_payment_scid().unwrap(),
CandidateRouteHop::PublicHop { short_channel_id, .. } => *short_channel_id,
CandidateRouteHop::PrivateHop { hint } => hint.short_channel_id,
}
}
}
+ fn htlc_maximum_msat(&self) -> u64 {
+ match self {
+ CandidateRouteHop::FirstHop { details } => details.next_outbound_htlc_limit_msat,
+ CandidateRouteHop::PublicHop { info, .. } => info.htlc_maximum_msat(),
+ CandidateRouteHop::PrivateHop { hint } => {
+ hint.htlc_maximum_msat.unwrap_or(u64::max_value())
+ },
+ }
+ }
+
fn fees(&self) -> RoutingFees {
match self {
CandidateRouteHop::FirstHop { .. } => RoutingFees {
fn effective_capacity(&self) -> EffectiveCapacity {
match self {
CandidateRouteHop::FirstHop { details } => EffectiveCapacity::ExactLiquidity {
- liquidity_msat: details.outbound_capacity_msat,
+ liquidity_msat: details.next_outbound_htlc_limit_msat,
},
CandidateRouteHop::PublicHop { info, .. } => info.effective_capacity(),
CandidateRouteHop::PrivateHop { .. } => EffectiveCapacity::Infinite,
impl<'a> core::fmt::Debug for PathBuildingHop<'a> {
fn fmt(&self, f: &mut core::fmt::Formatter) -> Result<(), core::fmt::Error> {
- f.debug_struct("PathBuildingHop")
+ let mut debug_struct = f.debug_struct("PathBuildingHop");
+ debug_struct
.field("node_id", &self.node_id)
.field("short_channel_id", &self.candidate.short_channel_id())
.field("total_fee_msat", &self.total_fee_msat)
.field("total_fee_msat - (next_hops_fee_msat + hop_use_fee_msat)", &(&self.total_fee_msat - (&self.next_hops_fee_msat + &self.hop_use_fee_msat)))
.field("path_penalty_msat", &self.path_penalty_msat)
.field("path_htlc_minimum_msat", &self.path_htlc_minimum_msat)
- .field("cltv_expiry_delta", &self.candidate.cltv_expiry_delta())
- .finish()
+ .field("cltv_expiry_delta", &self.candidate.cltv_expiry_delta());
+ #[cfg(all(not(feature = "_bench_unstable"), any(test, fuzzing)))]
+ let debug_struct = debug_struct
+ .field("value_contribution_msat", &self.value_contribution_msat);
+ debug_struct.finish()
}
}
) -> Result<Route, LightningError>
where L::Target: Logger {
let network_graph = network.read_only();
- match get_route(
- our_node_pubkey, &route_params.payment_params, &network_graph, first_hops, route_params.final_value_msat,
- route_params.final_cltv_expiry_delta, logger, scorer, random_seed_bytes
- ) {
- Ok(mut route) => {
- add_random_cltv_offset(&mut route, &route_params.payment_params, &network_graph, random_seed_bytes);
- Ok(route)
- },
- Err(err) => Err(err),
- }
+ let mut route = get_route(our_node_pubkey, &route_params.payment_params, &network_graph, first_hops,
+ route_params.final_value_msat, route_params.final_cltv_expiry_delta, logger, scorer,
+ random_seed_bytes)?;
+ add_random_cltv_offset(&mut route, &route_params.payment_params, &network_graph, random_seed_bytes);
+ Ok(route)
}
pub(crate) fn get_route<L: Deref, S: Score>(
HashMap::with_capacity(if first_hops.is_some() { first_hops.as_ref().unwrap().len() } else { 0 });
if let Some(hops) = first_hops {
for chan in hops {
- if chan.short_channel_id.is_none() {
+ if chan.get_outbound_payment_scid().is_none() {
panic!("first_hops should be filled in with usable channels, not pending ones");
}
if chan.counterparty.node_id == *our_node_pubkey {
// The main heap containing all candidate next-hops sorted by their score (max(A* fee,
// htlc_minimum)). Ideally this would be a heap which allowed cheap score reduction instead of
// adding duplicate entries when we find a better path to a given node.
- let mut targets = BinaryHeap::new();
+ let mut targets: BinaryHeap<RouteGraphNode> = BinaryHeap::new();
// Map from node_id to information about the best current path to that node, including feerate
// information.
- let mut dist = HashMap::with_capacity(network_nodes.len());
+ let mut dist: HashMap<NodeId, PathBuildingHop> = HashMap::with_capacity(network_nodes.len());
// During routing, if we ignore a path due to an htlc_minimum_msat limit, we set this,
// indicating that we may wish to try again with a higher value, potentially paying to meet an
let recommended_value_msat = final_value_msat * ROUTE_CAPACITY_PROVISION_FACTOR as u64;
let mut path_value_msat = final_value_msat;
- // We don't want multiple paths (as per MPP) share liquidity of the same channels.
- // This map allows paths to be aware of the channel use by other paths in the same call.
- // This would help to make a better path finding decisions and not "overbook" channels.
- // It is unaware of the directions (except for `outbound_capacity_msat` in `first_hops`).
- let mut bookkept_channels_liquidity_available_msat = HashMap::with_capacity(network_nodes.len());
+ // Keep track of how much liquidity has been used in selected channels. Used to determine
+ // if the channel can be used by additional MPP paths or to inform path finding decisions. It is
+ // aware of direction *only* to ensure that the correct htlc_maximum_msat value is used. Hence,
+ // liquidity used in one direction will not offset any used in the opposite direction.
+ let mut used_channel_liquidities: HashMap<(u64, bool), u64> =
+ HashMap::with_capacity(network_nodes.len());
// Keeping track of how much value we already collected across other paths. Helps to decide:
// - how much a new path should be transferring (upper bound);
// 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 {
+ if chan_b.next_outbound_htlc_limit_msat < recommended_value_msat || chan_a.next_outbound_htlc_limit_msat < recommended_value_msat {
// Sort in descending order
- chan_b.outbound_capacity_msat.cmp(&chan_a.outbound_capacity_msat)
+ chan_b.next_outbound_htlc_limit_msat.cmp(&chan_a.next_outbound_htlc_limit_msat)
} else {
// Sort in ascending order
- chan_a.outbound_capacity_msat.cmp(&chan_b.outbound_capacity_msat)
+ chan_a.next_outbound_htlc_limit_msat.cmp(&chan_b.next_outbound_htlc_limit_msat)
}
});
}
// since that value has to be transferred over this channel.
// Returns whether this 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_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, via this:
let mut did_add_update_path_to_src_node = false;
// Channels to self should not be used. This is more of belt-and-suspenders, because in
// - for first and last hops early in get_route
if $src_node_id != $dest_node_id {
let short_channel_id = $candidate.short_channel_id();
- let available_liquidity_msat = bookkept_channels_liquidity_available_msat
- .entry(short_channel_id)
- .or_insert_with(|| $candidate.effective_capacity().as_msat());
+ let htlc_maximum_msat = $candidate.htlc_maximum_msat();
// 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
// fees caused by one expensive channel, but then this channel could have been used
// if the amount being transferred over this path is lower.
// We do this for now, but this is a subject for removal.
- if let Some(available_value_contribution_msat) = available_liquidity_msat.checked_sub($next_hops_fee_msat) {
+ if let Some(mut available_value_contribution_msat) = htlc_maximum_msat.checked_sub($next_hops_fee_msat) {
+ let used_liquidity_msat = used_channel_liquidities
+ .get(&(short_channel_id, $src_node_id < $dest_node_id))
+ .map_or(0, |used_liquidity_msat| {
+ available_value_contribution_msat = available_value_contribution_msat
+ .saturating_sub(*used_liquidity_msat);
+ *used_liquidity_msat
+ });
// Routing Fragmentation Mitigation heuristic:
//
};
// Verify the liquidity offered by this channel complies to the minimal contribution.
let contributes_sufficient_value = available_value_contribution_msat >= minimal_value_contribution_msat;
+ // Do not consider candidate hops that would exceed the maximum path length.
+ let path_length_to_node = $next_hops_path_length + 1;
+ let doesnt_exceed_max_path_length = path_length_to_node <= MAX_PATH_LENGTH_ESTIMATE;
// Do not consider candidates that exceed the maximum total cltv expiry limit.
// In order to already account for some of the privacy enhancing random CLTV
// 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 {
+ if contributes_sufficient_value && doesnt_exceed_max_path_length &&
+ 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 && over_path_minimum_msat {
+ } else if contributes_sufficient_value && doesnt_exceed_max_path_length &&
+ 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 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 channel_usage = ChannelUsage {
+ amount_msat: amount_to_transfer_over_msat,
+ inflight_htlc_msat: used_liquidity_msat,
+ effective_capacity: $candidate.effective_capacity(),
+ };
+ let channel_penalty_msat = scorer.channel_penalty_msat(
+ short_channel_id, &$src_node_id, &$dest_node_id, channel_usage
+ );
+ 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_peer_through_node: total_fee_msat,
value_contribution_msat: 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),
// meaning how much will be paid in fees after this node (to the best of our knowledge).
// This data can later be helpful to optimize routing (pay lower fees).
macro_rules! add_entries_to_cheapest_to_target_node {
- ( $node: expr, $node_id: expr, $fee_to_target_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 ) => {
+ ( $node: expr, $node_id: expr, $fee_to_target_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 ) => {
let skip_node = if let Some(elem) = dist.get_mut(&$node_id) {
let was_processed = elem.was_processed;
elem.was_processed = true;
if let Some(first_channels) = first_hop_targets.get(&$node_id) {
for details in first_channels {
let candidate = CandidateRouteHop::FirstHop { details };
- add_entry!(candidate, our_node_id, $node_id, $fee_to_target_msat, $next_hops_value_contribution, $next_hops_path_htlc_minimum_msat, $next_hops_path_penalty_msat, $next_hops_cltv_delta);
+ add_entry!(candidate, our_node_id, $node_id, $fee_to_target_msat,
+ $next_hops_value_contribution,
+ $next_hops_path_htlc_minimum_msat, $next_hops_path_penalty_msat,
+ $next_hops_cltv_delta, $next_hops_path_length);
}
}
info: directed_channel.with_update().unwrap(),
short_channel_id: *chan_id,
};
- add_entry!(candidate, *source, $node_id, $fee_to_target_msat, $next_hops_value_contribution, $next_hops_path_htlc_minimum_msat, $next_hops_path_penalty_msat, $next_hops_cltv_delta);
+ add_entry!(candidate, *source, $node_id,
+ $fee_to_target_msat,
+ $next_hops_value_contribution,
+ $next_hops_path_htlc_minimum_msat,
+ $next_hops_path_penalty_msat,
+ $next_hops_cltv_delta, $next_hops_path_length);
}
}
}
// TODO: diversify by nodes (so that all paths aren't doomed if one node is offline).
'paths_collection: loop {
- // For every new path, start from scratch, except
- // bookkept_channels_liquidity_available_msat, which will improve
- // the further iterations of path finding. Also don't erase first_hop_targets.
+ // For every new path, start from scratch, except for used_channel_liquidities, which
+ // helps to avoid reusing previously selected paths in future iterations.
targets.clear();
dist.clear();
hit_minimum_limit = false;
if let Some(first_channels) = first_hop_targets.get(&payee_node_id) {
for details in first_channels {
let candidate = CandidateRouteHop::FirstHop { details };
- let added = add_entry!(candidate, our_node_id, payee_node_id, 0, path_value_msat, 0, 0u64, 0);
- log_trace!(logger, "{} direct route to payee via SCID {}", if added { "Added" } else { "Skipped" }, candidate.short_channel_id());
+ let added = add_entry!(candidate, our_node_id, payee_node_id, 0, path_value_msat,
+ 0, 0u64, 0, 0);
+ log_trace!(logger, "{} direct route to payee via SCID {}",
+ if added { "Added" } else { "Skipped" }, candidate.short_channel_id());
}
}
// If not, targets.pop() will not even let us enter the loop in step 2.
None => {},
Some(node) => {
- add_entries_to_cheapest_to_target_node!(node, payee_node_id, 0, path_value_msat, 0, 0u64, 0);
+ add_entries_to_cheapest_to_target_node!(node, payee_node_id, 0, path_value_msat, 0, 0u64, 0, 0);
},
}
let mut aggregate_next_hops_path_htlc_minimum_msat: u64 = 0;
let mut aggregate_next_hops_path_penalty_msat: u64 = 0;
let mut aggregate_next_hops_cltv_delta: u32 = 0;
+ let mut aggregate_next_hops_path_length: u8 = 0;
for (idx, (hop, prev_hop_id)) in hop_iter.zip(prev_hop_iter).enumerate() {
let source = NodeId::from_pubkey(&hop.src_node_id);
short_channel_id: hop.short_channel_id,
})
.unwrap_or_else(|| CandidateRouteHop::PrivateHop { hint: hop });
- let capacity_msat = candidate.effective_capacity().as_msat();
+
+ 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, aggregate_next_hops_path_length) {
+ // If this hop was not used then there is no use checking the preceding
+ // hops in the RouteHint. We can break by just searching for a direct
+ // channel between last checked hop and first_hop_targets.
+ hop_used = false;
+ }
+
+ let used_liquidity_msat = used_channel_liquidities
+ .get(&(hop.short_channel_id, source < target)).copied().unwrap_or(0);
+ let channel_usage = ChannelUsage {
+ amount_msat: final_value_msat + aggregate_next_hops_fee_msat,
+ inflight_htlc_msat: used_liquidity_msat,
+ effective_capacity: candidate.effective_capacity(),
+ };
+ let channel_penalty_msat = scorer.channel_penalty_msat(
+ hop.short_channel_id, &source, &target, channel_usage
+ );
aggregate_next_hops_path_penalty_msat = aggregate_next_hops_path_penalty_msat
- .saturating_add(scorer.channel_penalty_msat(hop.short_channel_id, final_value_msat, capacity_msat, &source, &target));
+ .saturating_add(channel_penalty_msat);
aggregate_next_hops_cltv_delta = aggregate_next_hops_cltv_delta
.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
- // in the RouteHint. We can break by just searching for a direct channel between
- // last checked hop and first_hop_targets
- hop_used = false;
- }
+ aggregate_next_hops_path_length = aggregate_next_hops_path_length
+ .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(&NodeId::from_pubkey(&prev_hop_id)) {
for details in first_channels {
let candidate = CandidateRouteHop::FirstHop { details };
- add_entry!(candidate, our_node_id, NodeId::from_pubkey(&prev_hop_id), 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);
+ add_entry!(candidate, our_node_id, NodeId::from_pubkey(&prev_hop_id),
+ 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,
+ aggregate_next_hops_path_length);
}
}
// In the next values of the iterator, the aggregate fees already reflects
// the sum of value sent from payer (final_value_msat) and routing fees
// for the last node in the RouteHint. We need to just add the fees to
- // route through the current node so that the preceeding node (next iteration)
+ // route through the current node so that the preceding node (next iteration)
// can use it.
let hops_fee = compute_fees(aggregate_next_hops_fee_msat + final_value_msat, hop.fees)
.map_or(None, |inc| inc.checked_add(aggregate_next_hops_fee_msat));
if let Some(first_channels) = first_hop_targets.get(&NodeId::from_pubkey(&hop.src_node_id)) {
for details in first_channels {
let candidate = CandidateRouteHop::FirstHop { details };
- add_entry!(candidate, our_node_id, NodeId::from_pubkey(&hop.src_node_id), 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);
+ add_entry!(candidate, our_node_id,
+ NodeId::from_pubkey(&hop.src_node_id),
+ 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,
+ aggregate_next_hops_path_length);
}
}
}
// Both these cases (and other cases except reaching recommended_value_msat) mean that
// paths_collection will be stopped because found_new_path==false.
// This is not necessarily a routing failure.
- 'path_construction: while let Some(RouteGraphNode { node_id, lowest_fee_to_node, total_cltv_delta, value_contribution_msat, path_htlc_minimum_msat, path_penalty_msat, .. }) = targets.pop() {
+ 'path_construction: while let Some(RouteGraphNode { node_id, lowest_fee_to_node, total_cltv_delta, value_contribution_msat, path_htlc_minimum_msat, path_penalty_msat, path_length_to_node, .. }) = targets.pop() {
// Since we're going payee-to-payer, hitting our node as a target means we should stop
// 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(), default_node_features.clone()));
+ let mut ordered_hops: Vec<(PathBuildingHop, NodeFeatures)> = vec!((new_entry.clone(), default_node_features.clone()));
'path_walk: loop {
let mut features_set = false;
if let Some(first_channels) = first_hop_targets.get(&ordered_hops.last().unwrap().0.node_id) {
for details in first_channels {
- if details.short_channel_id.unwrap() == ordered_hops.last().unwrap().0.candidate.short_channel_id() {
+ if details.get_outbound_payment_scid().unwrap() == ordered_hops.last().unwrap().0.candidate.short_channel_id() {
ordered_hops.last_mut().unwrap().1 = details.counterparty.features.to_context();
features_set = true;
break;
// Remember that we used these channels so that we don't rely
// on the same liquidity in future paths.
let mut prevented_redundant_path_selection = false;
- for (payment_hop, _) in payment_path.hops.iter() {
- let channel_liquidity_available_msat = bookkept_channels_liquidity_available_msat.get_mut(&payment_hop.candidate.short_channel_id()).unwrap();
- let mut spent_on_hop_msat = value_contribution_msat;
- let next_hops_fee_msat = payment_hop.next_hops_fee_msat;
- spent_on_hop_msat += next_hops_fee_msat;
- if spent_on_hop_msat == *channel_liquidity_available_msat {
+ let prev_hop_iter = core::iter::once(&our_node_id)
+ .chain(payment_path.hops.iter().map(|(hop, _)| &hop.node_id));
+ for (prev_hop, (hop, _)) in prev_hop_iter.zip(payment_path.hops.iter()) {
+ let spent_on_hop_msat = value_contribution_msat + hop.next_hops_fee_msat;
+ let used_liquidity_msat = used_channel_liquidities
+ .entry((hop.candidate.short_channel_id(), *prev_hop < hop.node_id))
+ .and_modify(|used_liquidity_msat| *used_liquidity_msat += spent_on_hop_msat)
+ .or_insert(spent_on_hop_msat);
+ if *used_liquidity_msat == hop.candidate.htlc_maximum_msat() {
// If this path used all of this channel's available liquidity, we know
// this path will not be selected again in the next loop iteration.
prevented_redundant_path_selection = true;
}
- *channel_liquidity_available_msat -= spent_on_hop_msat;
+ debug_assert!(*used_liquidity_msat <= hop.candidate.htlc_maximum_msat());
}
if !prevented_redundant_path_selection {
// 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()) / 2].0.candidate.short_channel_id();
+ let exhausted = u64::max_value();
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;
+ *used_channel_liquidities.entry((victim_scid, false)).or_default() = exhausted;
+ *used_channel_liquidities.entry((victim_scid, true)).or_default() = exhausted;
}
// Track the total amount all our collected paths allow to send so that we:
match network_nodes.get(&node_id) {
None => {},
Some(node) => {
- add_entries_to_cheapest_to_target_node!(node, node_id, lowest_fee_to_node, value_contribution_msat, path_htlc_minimum_msat, path_penalty_msat, total_cltv_delta);
+ add_entries_to_cheapest_to_target_node!(node, node_id, lowest_fee_to_node,
+ value_contribution_msat, path_htlc_minimum_msat, path_penalty_msat,
+ total_cltv_delta, path_length_to_node);
},
}
}
// destination, if the remaining CLTV expiry delta exactly matches a feasible path in the network
// graph. In order to improve privacy, this method obfuscates the CLTV expiry deltas along the
// payment path by adding a randomized 'shadow route' offset to the final hop.
-fn add_random_cltv_offset(route: &mut Route, payment_params: &PaymentParameters, network_graph: &ReadOnlyNetworkGraph, random_seed_bytes: &[u8; 32]) {
+fn add_random_cltv_offset(route: &mut Route, payment_params: &PaymentParameters,
+ network_graph: &ReadOnlyNetworkGraph, random_seed_bytes: &[u8; 32]
+) {
let network_channels = network_graph.channels();
let network_nodes = network_graph.nodes();
}
}
+/// Construct a route from us (payer) to the target node (payee) via the given hops (which should
+/// exclude the payer, but include the payee). This may be useful, e.g., for probing the chosen path.
+///
+/// Re-uses logic from `find_route`, so the restrictions described there also apply here.
+pub fn build_route_from_hops<L: Deref>(
+ our_node_pubkey: &PublicKey, hops: &[PublicKey], route_params: &RouteParameters, network: &NetworkGraph,
+ logger: L, random_seed_bytes: &[u8; 32]
+) -> Result<Route, LightningError>
+where L::Target: Logger {
+ let network_graph = network.read_only();
+ let mut route = build_route_from_hops_internal(
+ our_node_pubkey, hops, &route_params.payment_params, &network_graph,
+ route_params.final_value_msat, route_params.final_cltv_expiry_delta, logger, random_seed_bytes)?;
+ add_random_cltv_offset(&mut route, &route_params.payment_params, &network_graph, random_seed_bytes);
+ Ok(route)
+}
+
+fn build_route_from_hops_internal<L: Deref>(
+ our_node_pubkey: &PublicKey, hops: &[PublicKey], payment_params: &PaymentParameters,
+ network_graph: &ReadOnlyNetworkGraph, final_value_msat: u64, final_cltv_expiry_delta: u32,
+ logger: L, random_seed_bytes: &[u8; 32]
+) -> Result<Route, LightningError> where L::Target: Logger {
+
+ struct HopScorer {
+ our_node_id: NodeId,
+ hop_ids: [Option<NodeId>; MAX_PATH_LENGTH_ESTIMATE as usize],
+ }
+
+ impl Score for HopScorer {
+ fn channel_penalty_msat(&self, _short_channel_id: u64, source: &NodeId, target: &NodeId,
+ _usage: ChannelUsage) -> u64
+ {
+ let mut cur_id = self.our_node_id;
+ for i in 0..self.hop_ids.len() {
+ if let Some(next_id) = self.hop_ids[i] {
+ if cur_id == *source && next_id == *target {
+ return 0;
+ }
+ cur_id = next_id;
+ } else {
+ break;
+ }
+ }
+ u64::max_value()
+ }
+
+ fn payment_path_failed(&mut self, _path: &[&RouteHop], _short_channel_id: u64) {}
+
+ fn payment_path_successful(&mut self, _path: &[&RouteHop]) {}
+ }
+
+ impl<'a> Writeable for HopScorer {
+ #[inline]
+ fn write<W: Writer>(&self, _w: &mut W) -> Result<(), io::Error> {
+ unreachable!();
+ }
+ }
+
+ if hops.len() > MAX_PATH_LENGTH_ESTIMATE.into() {
+ return Err(LightningError{err: "Cannot build a route exceeding the maximum path length.".to_owned(), action: ErrorAction::IgnoreError});
+ }
+
+ let our_node_id = NodeId::from_pubkey(our_node_pubkey);
+ let mut hop_ids = [None; MAX_PATH_LENGTH_ESTIMATE as usize];
+ for i in 0..hops.len() {
+ hop_ids[i] = Some(NodeId::from_pubkey(&hops[i]));
+ }
+
+ let scorer = HopScorer { our_node_id, hop_ids };
+
+ get_route(our_node_pubkey, payment_params, network_graph, None, final_value_msat,
+ final_cltv_expiry_delta, logger, &scorer, random_seed_bytes)
+}
+
#[cfg(test)]
mod tests {
use routing::network_graph::{NetworkGraph, NetGraphMsgHandler, NodeId};
- 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 routing::router::{get_route, build_route_from_hops_internal, add_random_cltv_offset, default_node_features,
+ PaymentParameters, Route, RouteHint, RouteHintHop, RouteHop, RoutingFees,
+ DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA, MAX_PATH_LENGTH_ESTIMATE};
+ use routing::scoring::{ChannelUsage, Score};
use chain::transaction::OutPoint;
use chain::keysinterface::KeysInterface;
use ln::features::{ChannelFeatures, InitFeatures, InvoiceFeatures, NodeFeatures};
use ln::msgs::{ErrorAction, LightningError, OptionalField, UnsignedChannelAnnouncement, ChannelAnnouncement, RoutingMessageHandler,
- NodeAnnouncement, UnsignedNodeAnnouncement, ChannelUpdate, UnsignedChannelUpdate};
+ NodeAnnouncement, UnsignedNodeAnnouncement, ChannelUpdate, UnsignedChannelUpdate};
use ln::channelmanager;
use util::test_utils;
use util::chacha20::ChaCha20;
use hex;
- use bitcoin::secp256k1::key::{PublicKey,SecretKey};
+ use bitcoin::secp256k1::{PublicKey,SecretKey};
use bitcoin::secp256k1::{Secp256k1, All};
use prelude::*;
funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
channel_type: None,
short_channel_id,
+ outbound_scid_alias: None,
inbound_scid_alias: None,
channel_value_satoshis: 0,
user_channel_id: 0,
balance_msat: 0,
outbound_capacity_msat,
+ next_outbound_htlc_limit_msat: outbound_capacity_msat,
inbound_capacity_msat: 42,
unspendable_punishment_reserve: None,
confirmations_required: None,
force_close_spend_delay: None,
- is_outbound: true, is_funding_locked: true,
+ is_outbound: true, is_channel_ready: true,
is_usable: true, is_public: true,
inbound_htlc_minimum_msat: None,
inbound_htlc_maximum_msat: None,
let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
let valid_announcement = ChannelAnnouncement {
- node_signature_1: secp_ctx.sign(&msghash, node_1_privkey),
- node_signature_2: secp_ctx.sign(&msghash, node_2_privkey),
- bitcoin_signature_1: secp_ctx.sign(&msghash, node_1_privkey),
- bitcoin_signature_2: secp_ctx.sign(&msghash, node_2_privkey),
+ node_signature_1: secp_ctx.sign_ecdsa(&msghash, node_1_privkey),
+ node_signature_2: secp_ctx.sign_ecdsa(&msghash, node_2_privkey),
+ bitcoin_signature_1: secp_ctx.sign_ecdsa(&msghash, node_1_privkey),
+ bitcoin_signature_2: secp_ctx.sign_ecdsa(&msghash, node_2_privkey),
contents: unsigned_announcement.clone(),
};
match net_graph_msg_handler.handle_channel_announcement(&valid_announcement) {
) {
let msghash = hash_to_message!(&Sha256dHash::hash(&update.encode()[..])[..]);
let valid_channel_update = ChannelUpdate {
- signature: secp_ctx.sign(&msghash, node_privkey),
+ signature: secp_ctx.sign_ecdsa(&msghash, node_privkey),
contents: update.clone()
};
};
let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
let valid_announcement = NodeAnnouncement {
- signature: secp_ctx.sign(&msghash, node_privkey),
+ signature: secp_ctx.sign_ecdsa(&msghash, node_privkey),
contents: unsigned_announcement.clone()
};
}
fn get_nodes(secp_ctx: &Secp256k1<All>) -> (SecretKey, PublicKey, Vec<SecretKey>, Vec<PublicKey>) {
- let privkeys: Vec<SecretKey> = (2..10).map(|i| {
+ let privkeys: Vec<SecretKey> = (2..22).map(|i| {
SecretKey::from_slice(&hex::decode(format!("{:02x}", i).repeat(32)).unwrap()[..]).unwrap()
}).collect();
}
}
+ fn build_line_graph() -> (
+ Secp256k1<All>, sync::Arc<NetworkGraph>, NetGraphMsgHandler<sync::Arc<NetworkGraph>,
+ sync::Arc<test_utils::TestChainSource>, sync::Arc<crate::util::test_utils::TestLogger>>,
+ sync::Arc<test_utils::TestChainSource>, sync::Arc<test_utils::TestLogger>,
+ ) {
+ let secp_ctx = Secp256k1::new();
+ let logger = Arc::new(test_utils::TestLogger::new());
+ let chain_monitor = Arc::new(test_utils::TestChainSource::new(Network::Testnet));
+ let network_graph = Arc::new(NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash()));
+ let net_graph_msg_handler = NetGraphMsgHandler::new(Arc::clone(&network_graph), None, Arc::clone(&logger));
+
+ // Build network from our_id to node 19:
+ // our_id -1(1)2- node0 -1(2)2- node1 - ... - node19
+ let (our_privkey, _, privkeys, _) = get_nodes(&secp_ctx);
+
+ for (idx, (cur_privkey, next_privkey)) in core::iter::once(&our_privkey)
+ .chain(privkeys.iter()).zip(privkeys.iter()).enumerate() {
+ let cur_short_channel_id = (idx as u64) + 1;
+ add_channel(&net_graph_msg_handler, &secp_ctx, &cur_privkey, &next_privkey,
+ ChannelFeatures::from_le_bytes(id_to_feature_flags(1)), cur_short_channel_id);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &cur_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: cur_short_channel_id,
+ timestamp: idx as u32,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Absent,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &next_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: cur_short_channel_id,
+ timestamp: (idx as u32)+1,
+ flags: 1,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Absent,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ add_or_update_node(&net_graph_msg_handler, &secp_ctx, next_privkey,
+ NodeFeatures::from_le_bytes(id_to_feature_flags(1)), 0);
+ }
+
+ (secp_ctx, network_graph, net_graph_msg_handler, chain_monitor, logger)
+ }
+
fn build_graph() -> (
Secp256k1<All>,
sync::Arc<NetworkGraph>,
assert_eq!(path.last().unwrap().fee_msat, 250_000_000);
}
- // Check that setting outbound_capacity_msat in first_hops limits the channels.
+ // Check that setting next_outbound_htlc_limit_msat in first_hops limits the channels.
// Disable channel #1 and use another first hop.
update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
chain_hash: genesis_block(Network::Testnet).header.block_hash(),
excess_data: Vec::new()
});
- // Now, limit the first_hop by the outbound_capacity_msat of 200_000 sats.
+ // Now, limit the first_hop by the next_outbound_htlc_limit_msat of 200_000 sats.
let our_chans = vec![get_channel_details(Some(42), nodes[0].clone(), InitFeatures::from_le_bytes(vec![0b11]), 200_000_000)];
{
fn write<W: Writer>(&self, _w: &mut W) -> Result<(), ::io::Error> { unimplemented!() }
}
impl Score for BadChannelScorer {
- fn channel_penalty_msat(&self, short_channel_id: u64, _send_amt: u64, _capacity_msat: u64, _source: &NodeId, _target: &NodeId) -> u64 {
+ fn channel_penalty_msat(&self, short_channel_id: u64, _: &NodeId, _: &NodeId, _: ChannelUsage) -> u64 {
if short_channel_id == self.short_channel_id { u64::max_value() } else { 0 }
}
}
impl Score for BadNodeScorer {
- fn channel_penalty_msat(&self, _short_channel_id: u64, _send_amt: u64, _capacity_msat: u64, _source: &NodeId, target: &NodeId) -> u64 {
+ fn channel_penalty_msat(&self, _: u64, _: &NodeId, target: &NodeId, _: ChannelUsage) -> u64 {
if *target == self.node_id { u64::max_value() } else { 0 }
}
}
}
+ #[test]
+ fn limits_path_length() {
+ let (secp_ctx, network, _, _, logger) = build_line_graph();
+ let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
+ let network_graph = network.read_only();
+
+ let scorer = test_utils::TestScorer::with_penalty(0);
+ let keys_manager = test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet);
+ let random_seed_bytes = keys_manager.get_secure_random_bytes();
+
+ // First check we can actually create a long route on this graph.
+ let feasible_payment_params = PaymentParameters::from_node_id(nodes[18]);
+ let route = get_route(&our_id, &feasible_payment_params, &network_graph, None, 100, 0,
+ Arc::clone(&logger), &scorer, &random_seed_bytes).unwrap();
+ let path = route.paths[0].iter().map(|hop| hop.short_channel_id).collect::<Vec<_>>();
+ assert!(path.len() == MAX_PATH_LENGTH_ESTIMATE.into());
+
+ // But we can't create a path surpassing the MAX_PATH_LENGTH_ESTIMATE limit.
+ let fail_payment_params = PaymentParameters::from_node_id(nodes[19]);
+ match get_route(&our_id, &fail_payment_params, &network_graph, None, 100, 0,
+ Arc::clone(&logger), &scorer, &random_seed_bytes)
+ {
+ Err(LightningError { err, .. } ) => {
+ assert_eq!(err, "Failed to find a path to the given destination");
+ },
+ Ok(_) => panic!("Expected error"),
+ }
+ }
+
#[test]
fn adds_and_limits_cltv_offset() {
let (secp_ctx, network_graph, _, _, logger) = build_graph();
assert!(path_plausibility.iter().all(|x| *x));
}
+ #[test]
+ fn builds_correct_path_from_hops() {
+ let (secp_ctx, network, _, _, logger) = build_graph();
+ let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
+ let network_graph = network.read_only();
+
+ let keys_manager = test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet);
+ let random_seed_bytes = keys_manager.get_secure_random_bytes();
+
+ let payment_params = PaymentParameters::from_node_id(nodes[3]);
+ let hops = [nodes[1], nodes[2], nodes[4], nodes[3]];
+ let route = build_route_from_hops_internal(&our_id, &hops, &payment_params,
+ &network_graph, 100, 0, Arc::clone(&logger), &random_seed_bytes).unwrap();
+ let route_hop_pubkeys = route.paths[0].iter().map(|hop| hop.pubkey).collect::<Vec<_>>();
+ assert_eq!(hops.len(), route.paths[0].len());
+ for (idx, hop_pubkey) in hops.iter().enumerate() {
+ assert!(*hop_pubkey == route_hop_pubkeys[idx]);
+ }
+ }
+
#[cfg(not(feature = "no-std"))]
pub(super) fn random_init_seed() -> u64 {
// Because the default HashMap in std pulls OS randomness, we can use it as a (bad) RNG.
let payment_params = PaymentParameters::from_node_id(dst);
let amt = seed as u64 % 200_000_000;
let params = ProbabilisticScoringParameters::default();
- let scorer = ProbabilisticScorer::new(params, &graph);
- if get_route(src, &payment_params, &graph.read_only(), None, amt, 42, &test_utils::TestLogger::new(), &scorer, &random_seed_bytes).is_ok() {
+ let logger = test_utils::TestLogger::new();
+ let scorer = ProbabilisticScorer::new(params, &graph, &logger);
+ if get_route(src, &payment_params, &graph.read_only(), None, amt, 42, &logger, &scorer, &random_seed_bytes).is_ok() {
continue 'load_endpoints;
}
}
let payment_params = PaymentParameters::from_node_id(dst).with_features(InvoiceFeatures::known());
let amt = seed as u64 % 200_000_000;
let params = ProbabilisticScoringParameters::default();
- let scorer = ProbabilisticScorer::new(params, &graph);
- if get_route(src, &payment_params, &graph.read_only(), None, amt, 42, &test_utils::TestLogger::new(), &scorer, &random_seed_bytes).is_ok() {
+ let logger = test_utils::TestLogger::new();
+ let scorer = ProbabilisticScorer::new(params, &graph, &logger);
+ if get_route(src, &payment_params, &graph.read_only(), None, amt, 42, &logger, &scorer, &random_seed_bytes).is_ok() {
continue 'load_endpoints;
}
}
use ln::features::{InitFeatures, InvoiceFeatures};
use routing::scoring::{FixedPenaltyScorer, ProbabilisticScorer, ProbabilisticScoringParameters, Scorer};
use util::logger::{Logger, Record};
+ use util::test_utils::TestLogger;
use test::Bencher;
channel_type: None,
short_channel_id: Some(1),
inbound_scid_alias: None,
+ outbound_scid_alias: None,
channel_value_satoshis: 10_000_000,
user_channel_id: 0,
balance_msat: 10_000_000,
outbound_capacity_msat: 10_000_000,
+ next_outbound_htlc_limit_msat: 10_000_000,
inbound_capacity_msat: 0,
unspendable_punishment_reserve: None,
confirmations_required: None,
force_close_spend_delay: None,
is_outbound: true,
- is_funding_locked: true,
+ is_channel_ready: true,
is_usable: true,
is_public: true,
inbound_htlc_minimum_msat: None,
#[bench]
fn generate_routes_with_probabilistic_scorer(bench: &mut Bencher) {
+ let logger = TestLogger::new();
let network_graph = read_network_graph();
let params = ProbabilisticScoringParameters::default();
- let scorer = ProbabilisticScorer::new(params, &network_graph);
+ let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
generate_routes(bench, &network_graph, scorer, InvoiceFeatures::empty());
}
#[bench]
fn generate_mpp_routes_with_probabilistic_scorer(bench: &mut Bencher) {
+ let logger = TestLogger::new();
let network_graph = read_network_graph();
let params = ProbabilisticScoringParameters::default();
- let scorer = ProbabilisticScorer::new(params, &network_graph);
+ let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
generate_routes(bench, &network_graph, scorer, InvoiceFeatures::known());
}
projects / rust-lightning / blobdiff