X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=5bb81a033eb697193cde37776c8f9a9dadde04c8;hb=1fd6c6fb9f7e58e8c0cf6539e7a9451e57a2b6fd;hp=dc094b9b6e0309a8fc51cd01a75a1ad480c3d432;hpb=b5a63070f52dbd2a9cadaf638de3f0b3d702bee7;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index dc094b9b..5bb81a03 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -17,9 +17,9 @@ 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; @@ -65,11 +65,10 @@ impl_writeable_tlv_based!(RouteHop, { #[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>, /// The `payment_params` parameter passed to [`find_route`]. /// This is used by `ChannelManager` to track information which may be required for retries, @@ -152,8 +151,8 @@ impl Readable for Route { /// 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)] @@ -177,9 +176,23 @@ impl_writeable_tlv_based!(RouteParameters, { /// 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 { @@ -327,6 +340,8 @@ struct RouteGraphNode { /// 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 { @@ -399,6 +414,16 @@ impl<'a> CandidateRouteHop<'a> { } } + 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 { @@ -466,7 +491,8 @@ struct PathBuildingHop<'a> { 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) @@ -475,8 +501,11 @@ impl<'a> core::fmt::Debug for PathBuildingHop<'a> { .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() } } @@ -647,16 +676,11 @@ pub fn find_route( ) -> Result 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( @@ -796,11 +820,11 @@ where L::Target: Logger { // 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 = 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 = 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 @@ -815,12 +839,12 @@ where L::Target: Logger { 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 `next_outbound_htlc_limit_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); @@ -860,8 +884,8 @@ where L::Target: Logger { // 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 @@ -870,9 +894,7 @@ where L::Target: Logger { // - 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 @@ -881,7 +903,14 @@ where L::Target: Logger { // 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: // @@ -905,6 +934,9 @@ where L::Target: Logger { }; // 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 @@ -939,9 +971,11 @@ where L::Target: Logger { // 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 @@ -1027,9 +1061,16 @@ where L::Target: Logger { } } - 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, @@ -1038,6 +1079,7 @@ where L::Target: Logger { 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), @@ -1121,7 +1163,9 @@ where L::Target: Logger { // 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; @@ -1138,7 +1182,10 @@ where L::Target: Logger { 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); } } @@ -1161,7 +1208,12 @@ where L::Target: Logger { 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); } } } @@ -1176,9 +1228,8 @@ where L::Target: Logger { // 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; @@ -1188,8 +1239,10 @@ where L::Target: Logger { 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()); } } @@ -1202,7 +1255,7 @@ where L::Target: Logger { // 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); }, } @@ -1229,6 +1282,7 @@ where L::Target: Logger { 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); @@ -1242,25 +1296,45 @@ where L::Target: Logger { 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); } } @@ -1271,7 +1345,7 @@ where L::Target: Logger { // 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)); @@ -1296,7 +1370,13 @@ where L::Target: Logger { 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); } } } @@ -1319,13 +1399,13 @@ where L::Target: Logger { // 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; @@ -1397,26 +1477,30 @@ where L::Target: Logger { // 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: @@ -1441,7 +1525,9 @@ where L::Target: Logger { 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); }, } } @@ -1612,7 +1698,9 @@ where L::Target: Logger { // 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(); @@ -1694,16 +1782,92 @@ fn add_random_cltv_offset(route: &mut Route, payment_params: &PaymentParameters, } } +/// 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( + our_node_pubkey: &PublicKey, hops: &[PublicKey], route_params: &RouteParameters, network: &NetworkGraph, + logger: L, random_seed_bytes: &[u8; 32] +) -> Result +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( + 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 where L::Target: Logger { + + struct HopScorer { + our_node_id: NodeId, + hop_ids: [Option; 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(&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; @@ -1836,7 +2000,7 @@ mod tests { } fn get_nodes(secp_ctx: &Secp256k1) -> (SecretKey, PublicKey, Vec, Vec) { - let privkeys: Vec = (2..10).map(|i| { + let privkeys: Vec = (2..22).map(|i| { SecretKey::from_slice(&hex::decode(format!("{:02x}", i).repeat(32)).unwrap()[..]).unwrap() }).collect(); @@ -1863,6 +2027,57 @@ mod tests { } } + fn build_line_graph() -> ( + Secp256k1, sync::Arc, NetGraphMsgHandler, + sync::Arc, sync::Arc>, + sync::Arc, sync::Arc, + ) { + 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, sync::Arc, @@ -5039,7 +5254,7 @@ mod tests { fn write(&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 } } @@ -5057,7 +5272,7 @@ mod tests { } 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 } } @@ -5213,6 +5428,35 @@ mod tests { } } + #[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::>(); + 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(); @@ -5313,6 +5557,26 @@ mod tests { 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::>(); + 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.