X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=bf7c29487ee83d8a1a03724e76557a0b377f53fd;hb=16a6e9c5c8f694750e87c3f4ea0acb6d74ca8b44;hp=47a261786c370f8dbd9ae3904005b72b28a44e2a;hpb=1efc0c85eb94e6ac8251bcb059432acd32a6a55e;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index 47a26178..bf7c2948 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -15,7 +15,7 @@ use bitcoin::secp256k1::key::PublicKey; use ln::channelmanager::ChannelDetails; -use ln::features::{ChannelFeatures, NodeFeatures}; +use ln::features::{ChannelFeatures, InvoiceFeatures, NodeFeatures}; use ln::msgs::{DecodeError, ErrorAction, LightningError, MAX_VALUE_MSAT}; use routing::network_graph::{NetworkGraph, RoutingFees}; use util::ser::{Writeable, Readable}; @@ -143,7 +143,10 @@ struct RouteGraphNode { // - how much is needed for a path being constructed // - how much value can channels following this node (up to the destination) can contribute, // considering their capacity and fees - value_contribution_msat: u64 + value_contribution_msat: u64, + /// The effective htlc_minimum_msat at this hop. If a later hop on the path had a higher HTLC + /// minimum, we use it, plus the fees required at each earlier hop to meet it. + path_htlc_minimum_msat: u64, } impl cmp::Ord for RouteGraphNode { @@ -314,6 +317,9 @@ fn compute_fees(amount_msat: u64, channel_fees: RoutingFees) -> Option { /// Gets a route from us (payer) to the given target node (payee). /// +/// If the payee provided features in their invoice, they should be provided via payee_features. +/// Without this, MPP will only be used if the payee's features are available in the network graph. +/// /// Extra routing hops between known nodes and the target will be used if they are included in /// last_hops. /// @@ -328,7 +334,7 @@ fn compute_fees(amount_msat: u64, channel_fees: RoutingFees) -> Option { /// The fees on channels from us to next-hops are ignored (as they are assumed to all be /// equal), however the enabled/disabled bit on such channels as well as the /// htlc_minimum_msat/htlc_maximum_msat *are* checked as they may change based on the receiving node. -pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, payee: &PublicKey, first_hops: Option<&[&ChannelDetails]>, +pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, payee: &PublicKey, payee_features: Option, first_hops: Option<&[&ChannelDetails]>, last_hops: &[&RouteHint], final_value_msat: u64, final_cltv: u32, logger: L) -> Result where L::Target: Logger { // TODO: Obviously *only* using total fee cost sucks. We should consider weighting by // uptime/success in using a node in the past. @@ -369,8 +375,43 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // 8. Choose the best route by the lowest total fee. // As for the actual search algorithm, - // we do a payee-to-payer Dijkstra's sorting by each node's distance from the payee - // plus the minimum per-HTLC fee to get from it to another node (aka "shitty A*"). + // we do a payee-to-payer pseudo-Dijkstra's sorting by each node's distance from the payee + // plus the minimum per-HTLC fee to get from it to another node (aka "shitty pseudo-A*"). + // + // We are not a faithful Dijkstra's implementation because we can change values which impact + // earlier nodes while processing later nodes. Specifically, if we reach a channel with a lower + // liquidity limit (via htlc_maximum_msat, on-chain capacity or assumed liquidity limits) then + // the value we are currently attempting to send over a path, we simply reduce the value being + // sent along the path for any hops after that channel. This may imply that later fees (which + // we've already tabulated) are lower because a smaller value is passing through the channels + // (and the proportional fee is thus lower). There isn't a trivial way to recalculate the + // channels which were selected earlier (and which may still be used for other paths without a + // lower liquidity limit), so we simply accept that some liquidity-limited paths may be + // de-preferenced. + // + // One potentially problematic case for this algorithm would be if there are many + // liquidity-limited paths which are liquidity-limited near the destination (ie early in our + // graph walking), we may never find a path which is not liquidity-limited and has lower + // proportional fee (and only lower absolute fee when considering the ultimate value sent). + // Because we only consider paths with at least 5% of the total value being sent, the damage + // from such a case should be limited, however this could be further reduced in the future by + // calculating fees on the amount we wish to route over a path, ie ignoring the liquidity + // limits for the purposes of fee calculation. + // + // Alternatively, we could store more detailed path information in the heap (targets, below) + // and index the best-path map (dist, below) by node *and* HTLC limits, however that would blow + // up the runtime significantly both algorithmically (as we'd traverse nodes multiple times) + // and practically (as we would need to store dynamically-allocated path information in heap + // objects, increasing malloc traffic and indirect memory access significantly). Further, the + // results of such an algorithm would likely be biased towards lower-value paths. + // + // Further, we could return to a faithful Dijkstra's algorithm by rejecting paths with limits + // outside of our current search value, running a path search more times to gather candidate + // paths at different values. While this may be acceptable, further path searches may increase + // runtime for little gain. Specifically, the current algorithm rather efficiently explores the + // graph for candidate paths, calculating the maximum value which can realistically be sent at + // the same time, remaining generic across different payment values. + // // TODO: There are a few tweaks we could do, including possibly pre-calculating more stuff // to use as the A* heuristic beyond just the cost to get one node further than the current // one. @@ -388,13 +429,29 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye let mut targets = BinaryHeap::new(); //TODO: Do we care about switching to eg Fibbonaci heap? let mut dist = HashMap::with_capacity(network.get_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 + // htlc_minimum with extra fees while still finding a cheaper path. + let mut hit_minimum_limit; + // When arranging a route, we select multiple paths so that we can make a multi-path payment. - // Don't stop searching for paths when we think they're - // sufficient to transfer a given value aggregately. - // Search for higher value, so that we collect many more paths, - // and then select the best combination among them. + // We start with a path_value of the exact amount we want, and if that generates a route we may + // return it immediately. Otherwise, we don't stop searching for paths until we have 3x the + // amount we want in total across paths, selecting the best subset at the end. const ROUTE_CAPACITY_PROVISION_FACTOR: u64 = 3; let recommended_value_msat = final_value_msat * ROUTE_CAPACITY_PROVISION_FACTOR as u64; + let mut path_value_msat = final_value_msat; + + // Allow MPP only if we have a features set from somewhere that indicates the payee supports + // it. If the payee supports it they're supposed to include it in the invoice, so that should + // work reliably. + let allow_mpp = if let Some(features) = &payee_features { + features.supports_basic_mpp() + } else if let Some(node) = network.get_nodes().get(&payee) { + if let Some(node_info) = node.announcement_info.as_ref() { + node_info.features.supports_basic_mpp() + } else { false } + } else { false }; // Step (1). // Prepare the data we'll use for payee-to-payer search by @@ -434,7 +491,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // $next_hops_fee_msat represents the fees paid for using all the channel *after* this one, // since that value has to be transferred over this channel. ( $chan_id: expr, $src_node_id: expr, $dest_node_id: expr, $directional_info: expr, $capacity_sats: expr, $chan_features: expr, $next_hops_fee_msat: expr, - $next_hops_value_contribution: expr ) => { + $next_hops_value_contribution: expr, $next_hops_path_htlc_minimum_msat: expr ) => { // 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) @@ -484,8 +541,13 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // the absolute liquidity contribution is lowered, // thus increasing the number of potential channels to be selected. - // Derive the minimal liquidity contribution with a ratio of 20 (5%, rounded up). - let minimal_value_contribution_msat: u64 = (recommended_value_msat - already_collected_value_msat + 19) / 20; + // Derive the minimal liquidity contribution with a ratio of 20 (5%, rounded up) + // or 100% if we're not allowed to do multipath payments. + let minimal_value_contribution_msat: u64 = if allow_mpp { + (recommended_value_msat - already_collected_value_msat + 19) / 20 + } else { + final_value_msat + }; // Verify the liquidity offered by this channel complies to the minimal contribution. let contributes_sufficient_value = available_value_contribution_msat >= minimal_value_contribution_msat; @@ -496,18 +558,27 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // Can't overflow due to how the values were computed right above. None => unreachable!(), }; + #[allow(unused_comparisons)] // $next_hops_path_htlc_minimum_msat is 0 in some calls so rustc complains + let over_path_minimum_msat = amount_to_transfer_over_msat >= $directional_info.htlc_minimum_msat && + amount_to_transfer_over_msat >= $next_hops_path_htlc_minimum_msat; // If HTLC minimum is larger than the amount we're going to transfer, we shouldn't // bother considering this channel. // Since we're choosing amount_to_transfer_over_msat as maximum possible, it can // be only reduced later (not increased), so this channel should just be skipped // as not sufficient. - // TODO: Explore simply adding fee to hit htlc_minimum_msat - if contributes_sufficient_value && amount_to_transfer_over_msat >= $directional_info.htlc_minimum_msat { + if !over_path_minimum_msat { + hit_minimum_limit = true; + } else if contributes_sufficient_value { // 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 // path fees knowing the final path contribution after constructing it. + let path_htlc_minimum_msat = match compute_fees($next_hops_path_htlc_minimum_msat, $directional_info.fees) + .map(|fee_msat| fee_msat.checked_add($next_hops_path_htlc_minimum_msat)) { + Some(Some(value_msat)) => cmp::max(value_msat, $directional_info.htlc_minimum_msat), + _ => u64::max_value() + }; 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 @@ -579,6 +650,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye lowest_fee_to_peer_through_node: total_fee_msat, lowest_fee_to_node: $next_hops_fee_msat as u64 + hop_use_fee_msat, value_contribution_msat: value_contribution_msat, + path_htlc_minimum_msat, }; // Update the way of reaching $src_node_id with the given $chan_id (from $dest_node_id), @@ -638,10 +710,10 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // 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 ) => { + ( $node: expr, $node_id: expr, $fee_to_target_msat: expr, $next_hops_value_contribution: expr, $next_hops_path_htlc_minimum_msat: expr ) => { if first_hops.is_some() { if let Some(&(ref first_hop, ref features, ref outbound_capacity_msat)) = first_hop_targets.get(&$node_id) { - add_entry!(first_hop, *our_node_id, $node_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), $fee_to_target_msat, $next_hops_value_contribution); + add_entry!(first_hop, *our_node_id, $node_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), $fee_to_target_msat, $next_hops_value_contribution, $next_hops_path_htlc_minimum_msat); } } @@ -661,7 +733,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye if first_hops.is_none() || chan.node_two != *our_node_id { if let Some(two_to_one) = chan.two_to_one.as_ref() { if two_to_one.enabled { - add_entry!(chan_id, chan.node_two, chan.node_one, two_to_one, chan.capacity_sats, chan.features, $fee_to_target_msat, $next_hops_value_contribution); + add_entry!(chan_id, chan.node_two, chan.node_one, two_to_one, chan.capacity_sats, chan.features, $fee_to_target_msat, $next_hops_value_contribution, $next_hops_path_htlc_minimum_msat); } } } @@ -669,7 +741,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye if first_hops.is_none() || chan.node_one != *our_node_id { if let Some(one_to_two) = chan.one_to_two.as_ref() { if one_to_two.enabled { - add_entry!(chan_id, chan.node_one, chan.node_two, one_to_two, chan.capacity_sats, chan.features, $fee_to_target_msat, $next_hops_value_contribution); + add_entry!(chan_id, chan.node_one, chan.node_two, one_to_two, chan.capacity_sats, chan.features, $fee_to_target_msat, $next_hops_value_contribution, $next_hops_path_htlc_minimum_msat); } } @@ -690,12 +762,13 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // the further iterations of path finding. Also don't erase first_hop_targets. targets.clear(); dist.clear(); + hit_minimum_limit = false; // If first hop is a private channel and the only way to reach the payee, this is the only // place where it could be added. if first_hops.is_some() { if let Some(&(ref first_hop, ref features, ref outbound_capacity_msat)) = first_hop_targets.get(&payee) { - add_entry!(first_hop, *our_node_id, payee, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, recommended_value_msat); + add_entry!(first_hop, *our_node_id, payee, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, path_value_msat, 0); } } @@ -708,7 +781,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // 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, 0, recommended_value_msat); + add_entries_to_cheapest_to_target_node!(node, payee, 0, path_value_msat, 0); }, } @@ -727,7 +800,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // bit lazy here. In the future, we should pull them out via our // ChannelManager, but there's no reason to waste the space until we // need them. - add_entry!(first_hop, *our_node_id , hop.src_node_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, recommended_value_msat); + add_entry!(first_hop, *our_node_id , hop.src_node_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, path_value_msat, 0); true } else { // In any other case, only add the hop if the source is in the regular network @@ -747,7 +820,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye htlc_maximum_msat: hop.htlc_maximum_msat, fees: hop.fees, }; - add_entry!(hop.short_channel_id, hop.src_node_id, payee, directional_info, None::, ChannelFeatures::empty(), 0, recommended_value_msat); + add_entry!(hop.short_channel_id, hop.src_node_id, payee, directional_info, None::, ChannelFeatures::empty(), 0, path_value_msat, 0); } } @@ -764,7 +837,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // 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 { pubkey, lowest_fee_to_node, value_contribution_msat, .. }) = targets.pop() { + 'path_construction: while let Some(RouteGraphNode { pubkey, lowest_fee_to_node, value_contribution_msat, path_htlc_minimum_msat, .. }) = 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. @@ -821,7 +894,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // on some channels we already passed (assuming dest->source direction). Here, we // recompute the fees again, so that if that's the case, we match the currently // underpaid htlc_minimum_msat with fees. - payment_path.update_value_and_recompute_fees(value_contribution_msat); + payment_path.update_value_and_recompute_fees(cmp::min(value_contribution_msat, final_value_msat)); // Since a path allows to transfer as much value as // the smallest channel it has ("bottleneck"), we should recompute @@ -832,6 +905,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // might have been computed considering a larger value. // 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 = bookkeeped_channels_liquidity_available_msat.get_mut(&payment_hop.route_hop.short_channel_id).unwrap(); let mut spent_on_hop_msat = value_contribution_msat; @@ -842,8 +916,22 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // trying to avoid cases when a hop is not usable due to the fee situation. break 'path_construction; } + if spent_on_hop_msat == *channel_liquidity_available_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; } + 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_liquidity = bookkeeped_channels_liquidity_available_msat.get_mut( + &payment_path.hops[(payment_path.hops.len() - 1) / 2].route_hop.short_channel_id).unwrap(); + *victim_liquidity = 0; + } + // Track the total amount all our collected paths allow to send so that we: // - know when to stop looking for more paths // - know which of the hops are useless considering how much more sats we need @@ -861,18 +949,33 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye match network.get_nodes().get(&pubkey) { None => {}, Some(node) => { - add_entries_to_cheapest_to_target_node!(node, &pubkey, lowest_fee_to_node, value_contribution_msat); + add_entries_to_cheapest_to_target_node!(node, &pubkey, lowest_fee_to_node, value_contribution_msat, path_htlc_minimum_msat); }, } } + if !allow_mpp { + // If we don't support MPP, no use trying to gather more value ever. + break 'paths_collection; + } + // Step (3). - // Stop either when recommended value is reached, - // or if during last iteration no new path was found. - // In the latter case, making another path finding attempt could not help, - // because we deterministically terminate the search due to low liquidity. + // Stop either when the recommended value is reached or if no new path was found in this + // iteration. + // In the latter case, making another path finding attempt won't help, + // because we deterministically terminated the search due to low liquidity. if already_collected_value_msat >= recommended_value_msat || !found_new_path { break 'paths_collection; + } else if found_new_path && already_collected_value_msat == final_value_msat && payment_paths.len() == 1 { + // Further, if this was our first walk of the graph, and we weren't limited by an + // htlc_minimum_msat, return immediately because this path should suffice. If we were + // limited by an htlc_minimum_msat value, find another path with a higher value, + // potentially allowing us to pay fees to meet the htlc_minimum on the new path while + // still keeping a lower total fee than this path. + if !hit_minimum_limit { + break 'paths_collection; + } + path_value_msat = recommended_value_msat; } } @@ -961,21 +1064,27 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // Step (8). // Select the best route by lowest total fee. drawn_routes.sort_by_key(|paths| paths.iter().map(|path| path.get_total_fee_paid_msat()).sum::()); - let mut selected_paths = vec![]; + let mut selected_paths = Vec::>::new(); for payment_path in drawn_routes.first().unwrap() { selected_paths.push(payment_path.hops.iter().map(|payment_hop| payment_hop.route_hop.clone()).collect()); } + if let Some(features) = &payee_features { + for path in selected_paths.iter_mut() { + path.last_mut().unwrap().node_features = features.to_context(); + } + } + let route = Route { paths: selected_paths }; log_trace!(logger, "Got route: {}", log_route!(route)); - return Ok(route); + Ok(route) } #[cfg(test)] mod tests { use routing::router::{get_route, RouteHint, RoutingFees}; use routing::network_graph::{NetworkGraph, NetGraphMsgHandler}; - use ln::features::{ChannelFeatures, InitFeatures, NodeFeatures}; + use ln::features::{ChannelFeatures, InitFeatures, InvoiceFeatures, NodeFeatures}; use ln::msgs::{ErrorAction, LightningError, OptionalField, UnsignedChannelAnnouncement, ChannelAnnouncement, RoutingMessageHandler, NodeAnnouncement, UnsignedNodeAnnouncement, ChannelUpdate, UnsignedChannelUpdate}; use ln::channelmanager; @@ -1404,11 +1513,11 @@ mod tests { // Simple route to 2 via 1 - if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 0, 42, Arc::clone(&logger)) { + if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 0, 42, Arc::clone(&logger)) { assert_eq!(err, "Cannot send a payment of 0 msat"); } else { panic!(); } - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths[0].len(), 2); assert_eq!(route.paths[0][0].pubkey, nodes[1]); @@ -1443,13 +1552,14 @@ mod tests { outbound_capacity_msat: 100000, inbound_capacity_msat: 100000, is_live: true, + counterparty_forwarding_info: None, }]; - if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::>()), &Vec::new(), 100, 42, Arc::clone(&logger)) { + if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::>()), &Vec::new(), 100, 42, Arc::clone(&logger)) { assert_eq!(err, "First hop cannot have our_node_id as a destination."); } else { panic!(); } - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths[0].len(), 2); } @@ -1553,7 +1663,7 @@ mod tests { }); // Not possible to send 199_999_999, because the minimum on channel=2 is 200_000_000. - if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 199_999_999, 42, Arc::clone(&logger)) { + if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 199_999_999, 42, Arc::clone(&logger)) { assert_eq!(err, "Failed to find a path to the given destination"); } else { panic!(); } @@ -1572,7 +1682,7 @@ mod tests { }); // A payment above the minimum should pass - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 199_999_999, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 199_999_999, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths[0].len(), 2); } @@ -1649,7 +1759,8 @@ mod tests { excess_data: Vec::new() }); - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 60_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), None, &Vec::new(), 60_000, 42, Arc::clone(&logger)).unwrap(); // Overpay fees to hit htlc_minimum_msat. let overpaid_fees = route.paths[0][0].fee_msat + route.paths[1][0].fee_msat; // TODO: this could be better balanced to overpay 10k and not 15k. @@ -1694,14 +1805,16 @@ mod tests { excess_data: Vec::new() }); - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 60_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), None, &Vec::new(), 60_000, 42, Arc::clone(&logger)).unwrap(); // Fine to overpay for htlc_minimum_msat if it allows us to save fee. assert_eq!(route.paths.len(), 1); assert_eq!(route.paths[0][0].short_channel_id, 12); let fees = route.paths[0][0].fee_msat; assert_eq!(fees, 5_000); - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 50_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), None, &Vec::new(), 50_000, 42, Arc::clone(&logger)).unwrap(); // Not fine to overpay for htlc_minimum_msat if it requires paying more than fee on // the other channel. assert_eq!(route.paths.len(), 1); @@ -1742,7 +1855,7 @@ mod tests { }); // If all the channels require some features we don't understand, route should fail - if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 100, 42, Arc::clone(&logger)) { + if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 100, 42, Arc::clone(&logger)) { assert_eq!(err, "Failed to find a path to the given destination"); } else { panic!(); } @@ -1757,8 +1870,9 @@ mod tests { outbound_capacity_msat: 250_000_000, inbound_capacity_msat: 0, is_live: true, + counterparty_forwarding_info: None, }]; - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths[0].len(), 2); assert_eq!(route.paths[0][0].pubkey, nodes[7]); @@ -1789,7 +1903,7 @@ mod tests { add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[7], unknown_features.clone(), 1); // If all nodes require some features we don't understand, route should fail - if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 100, 42, Arc::clone(&logger)) { + if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 100, 42, Arc::clone(&logger)) { assert_eq!(err, "Failed to find a path to the given destination"); } else { panic!(); } @@ -1804,8 +1918,9 @@ mod tests { outbound_capacity_msat: 250_000_000, inbound_capacity_msat: 0, is_live: true, + counterparty_forwarding_info: None, }]; - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths[0].len(), 2); assert_eq!(route.paths[0][0].pubkey, nodes[7]); @@ -1833,7 +1948,7 @@ mod tests { let (_, our_id, _, nodes) = get_nodes(&secp_ctx); // Route to 1 via 2 and 3 because our channel to 1 is disabled - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[0], None, &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[0], None, None, &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths[0].len(), 3); assert_eq!(route.paths[0][0].pubkey, nodes[1]); @@ -1868,8 +1983,9 @@ mod tests { outbound_capacity_msat: 250_000_000, inbound_capacity_msat: 0, is_live: true, + counterparty_forwarding_info: None, }]; - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths[0].len(), 2); assert_eq!(route.paths[0][0].pubkey, nodes[7]); @@ -1942,12 +2058,12 @@ mod tests { let mut invalid_last_hops = last_hops(&nodes); invalid_last_hops.push(invalid_last_hop); { - if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, &invalid_last_hops.iter().collect::>(), 100, 42, Arc::clone(&logger)) { + if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, None, &invalid_last_hops.iter().collect::>(), 100, 42, Arc::clone(&logger)) { assert_eq!(err, "Last hop cannot have a payee as a source."); } else { panic!(); } } - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, &last_hops(&nodes).iter().collect::>(), 100, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, None, &last_hops(&nodes).iter().collect::>(), 100, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths[0].len(), 5); assert_eq!(route.paths[0][0].pubkey, nodes[1]); @@ -2004,9 +2120,10 @@ mod tests { outbound_capacity_msat: 250_000_000, inbound_capacity_msat: 0, is_live: true, + counterparty_forwarding_info: None, }]; let mut last_hops = last_hops(&nodes); - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], Some(&our_chans.iter().collect::>()), &last_hops.iter().collect::>(), 100, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, Some(&our_chans.iter().collect::>()), &last_hops.iter().collect::>(), 100, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths[0].len(), 2); assert_eq!(route.paths[0][0].pubkey, nodes[3]); @@ -2026,7 +2143,7 @@ mod tests { last_hops[0].fees.base_msat = 1000; // Revert to via 6 as the fee on 8 goes up - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, &last_hops.iter().collect::>(), 100, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, None, &last_hops.iter().collect::>(), 100, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths[0].len(), 4); assert_eq!(route.paths[0][0].pubkey, nodes[1]); @@ -2060,7 +2177,7 @@ mod tests { assert_eq!(route.paths[0][3].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly // ...but still use 8 for larger payments as 6 has a variable feerate - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, &last_hops.iter().collect::>(), 2000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, None, &last_hops.iter().collect::>(), 2000, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths[0].len(), 5); assert_eq!(route.paths[0][0].pubkey, nodes[1]); @@ -2132,8 +2249,9 @@ mod tests { outbound_capacity_msat: 100000, inbound_capacity_msat: 100000, is_live: true, + counterparty_forwarding_info: None, }]; - let route = get_route(&source_node_id, &NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash()), &target_node_id, Some(&our_chans.iter().collect::>()), &last_hops.iter().collect::>(), 100, 42, Arc::new(test_utils::TestLogger::new())).unwrap(); + let route = get_route(&source_node_id, &NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash()), &target_node_id, None, Some(&our_chans.iter().collect::>()), &last_hops.iter().collect::>(), 100, 42, Arc::new(test_utils::TestLogger::new())).unwrap(); assert_eq!(route.paths[0].len(), 2); @@ -2220,14 +2338,16 @@ mod tests { { // Attempt to route more than available results in a failure. - if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 250_000_001, 42, Arc::clone(&logger)) { + if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), None, &Vec::new(), 250_000_001, 42, Arc::clone(&logger)) { assert_eq!(err, "Failed to find a sufficient route to the given destination"); } else { panic!(); } } { // Now, attempt to route an exact amount we have should be fine. - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 250_000_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), None, &Vec::new(), 250_000_000, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths.len(), 1); let path = route.paths.last().unwrap(); assert_eq!(path.len(), 2); @@ -2261,18 +2381,21 @@ mod tests { outbound_capacity_msat: 200_000_000, inbound_capacity_msat: 0, is_live: true, + counterparty_forwarding_info: None, }]; { // Attempt to route more than available results in a failure. - if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::>()), &Vec::new(), 200_000_001, 42, Arc::clone(&logger)) { + if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), Some(&our_chans.iter().collect::>()), &Vec::new(), 200_000_001, 42, Arc::clone(&logger)) { assert_eq!(err, "Failed to find a sufficient route to the given destination"); } else { panic!(); } } { // Now, attempt to route an exact amount we have should be fine. - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::>()), &Vec::new(), 200_000_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), Some(&our_chans.iter().collect::>()), &Vec::new(), 200_000_000, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths.len(), 1); let path = route.paths.last().unwrap(); assert_eq!(path.len(), 2); @@ -2311,14 +2434,16 @@ mod tests { { // Attempt to route more than available results in a failure. - if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 15_001, 42, Arc::clone(&logger)) { + if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), None, &Vec::new(), 15_001, 42, Arc::clone(&logger)) { assert_eq!(err, "Failed to find a sufficient route to the given destination"); } else { panic!(); } } { // Now, attempt to route an exact amount we have should be fine. - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 15_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), None, &Vec::new(), 15_000, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths.len(), 1); let path = route.paths.last().unwrap(); assert_eq!(path.len(), 2); @@ -2380,14 +2505,16 @@ mod tests { { // Attempt to route more than available results in a failure. - if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 15_001, 42, Arc::clone(&logger)) { + if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), None, &Vec::new(), 15_001, 42, Arc::clone(&logger)) { assert_eq!(err, "Failed to find a sufficient route to the given destination"); } else { panic!(); } } { // Now, attempt to route an exact amount we have should be fine. - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 15_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), None, &Vec::new(), 15_000, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths.len(), 1); let path = route.paths.last().unwrap(); assert_eq!(path.len(), 2); @@ -2411,14 +2538,16 @@ mod tests { { // Attempt to route more than available results in a failure. - if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 10_001, 42, Arc::clone(&logger)) { + if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), None, &Vec::new(), 10_001, 42, Arc::clone(&logger)) { assert_eq!(err, "Failed to find a sufficient route to the given destination"); } else { panic!(); } } { // Now, attempt to route an exact amount we have should be fine. - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 10_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), None, &Vec::new(), 10_000, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths.len(), 1); let path = route.paths.last().unwrap(); assert_eq!(path.len(), 2); @@ -2517,14 +2646,16 @@ mod tests { }); { // Attempt to route more than available results in a failure. - if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 60_000, 42, Arc::clone(&logger)) { + if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], + Some(InvoiceFeatures::known()), None, &Vec::new(), 60_000, 42, Arc::clone(&logger)) { assert_eq!(err, "Failed to find a sufficient route to the given destination"); } else { panic!(); } } { // Now, attempt to route 49 sats (just a bit below the capacity). - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 49_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], + Some(InvoiceFeatures::known()), None, &Vec::new(), 49_000, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths.len(), 1); let mut total_amount_paid_msat = 0; for path in &route.paths { @@ -2537,7 +2668,8 @@ mod tests { { // Attempt to route an exact amount is also fine - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 50_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], + Some(InvoiceFeatures::known()), None, &Vec::new(), 50_000, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths.len(), 1); let mut total_amount_paid_msat = 0; for path in &route.paths { @@ -2581,7 +2713,7 @@ mod tests { }); { - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 50_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 50_000, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths.len(), 1); let mut total_amount_paid_msat = 0; for path in &route.paths { @@ -2688,7 +2820,8 @@ mod tests { { // Attempt to route more than available results in a failure. - if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 300_000, 42, Arc::clone(&logger)) { + if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), + &nodes[2], Some(InvoiceFeatures::known()), None, &Vec::new(), 300_000, 42, Arc::clone(&logger)) { assert_eq!(err, "Failed to find a sufficient route to the given destination"); } else { panic!(); } } @@ -2696,7 +2829,8 @@ mod tests { { // Now, attempt to route 250 sats (just a bit below the capacity). // Our algorithm should provide us with these 3 paths. - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 250_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), None, &Vec::new(), 250_000, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths.len(), 3); let mut total_amount_paid_msat = 0; for path in &route.paths { @@ -2709,7 +2843,8 @@ mod tests { { // Attempt to route an exact amount is also fine - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 290_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), None, &Vec::new(), 290_000, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths.len(), 3); let mut total_amount_paid_msat = 0; for path in &route.paths { @@ -2859,7 +2994,8 @@ mod tests { { // Attempt to route more than available results in a failure. - if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 350_000, 42, Arc::clone(&logger)) { + if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], + Some(InvoiceFeatures::known()), None, &Vec::new(), 350_000, 42, Arc::clone(&logger)) { assert_eq!(err, "Failed to find a sufficient route to the given destination"); } else { panic!(); } } @@ -2867,7 +3003,8 @@ mod tests { { // Now, attempt to route 300 sats (exact amount we can route). // Our algorithm should provide us with these 3 paths, 100 sats each. - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 300_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], + Some(InvoiceFeatures::known()), None, &Vec::new(), 300_000, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths.len(), 3); let mut total_amount_paid_msat = 0; @@ -3023,7 +3160,8 @@ mod tests { { // Now, attempt to route 180 sats. // Our algorithm should provide us with these 2 paths. - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 180_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], + Some(InvoiceFeatures::known()), None, &Vec::new(), 180_000, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths.len(), 2); let mut total_value_transferred_msat = 0; @@ -3188,14 +3326,16 @@ mod tests { { // Attempt to route more than available results in a failure. - if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 210_000, 42, Arc::clone(&logger)) { + if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], + Some(InvoiceFeatures::known()), None, &Vec::new(), 210_000, 42, Arc::clone(&logger)) { 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 = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 200_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], + Some(InvoiceFeatures::known()), None, &Vec::new(), 200_000, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths.len(), 2); let mut total_amount_paid_msat = 0; @@ -3304,7 +3444,8 @@ mod tests { { // Attempt to route more than available results in a failure. - if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 150_000, 42, Arc::clone(&logger)) { + if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), None, &Vec::new(), 150_000, 42, Arc::clone(&logger)) { assert_eq!(err, "Failed to find a sufficient route to the given destination"); } else { panic!(); } } @@ -3312,7 +3453,8 @@ mod tests { { // Now, attempt to route 125 sats (just a bit below the capacity of 3 channels). // Our algorithm should provide us with these 3 paths. - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 125_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), None, &Vec::new(), 125_000, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths.len(), 3); let mut total_amount_paid_msat = 0; for path in &route.paths { @@ -3325,7 +3467,8 @@ mod tests { { // Attempt to route without the last small cheap channel - let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 90_000, 42, Arc::clone(&logger)).unwrap(); + let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], + Some(InvoiceFeatures::known()), None, &Vec::new(), 90_000, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths.len(), 2); let mut total_amount_paid_msat = 0; for path in &route.paths { @@ -3337,6 +3480,125 @@ mod tests { } } + #[test] + fn exact_fee_liquidity_limit() { + // Test that if, while walking the graph, we find a hop that has exactly enough liquidity + // for us, including later hop fees, we take it. In the first version of our MPP algorithm + // we calculated fees on a higher value, resulting in us ignoring such paths. + let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph(); + let (our_privkey, our_id, _, nodes) = get_nodes(&secp_ctx); + + // We modify the graph to set the htlc_maximum of channel 2 to below the value we wish to + // send. + update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate { + chain_hash: genesis_block(Network::Testnet).header.block_hash(), + short_channel_id: 2, + timestamp: 2, + flags: 0, + cltv_expiry_delta: 0, + htlc_minimum_msat: 0, + htlc_maximum_msat: OptionalField::Present(85_000), + fee_base_msat: 0, + fee_proportional_millionths: 0, + excess_data: Vec::new() + }); + + update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate { + chain_hash: genesis_block(Network::Testnet).header.block_hash(), + short_channel_id: 12, + timestamp: 2, + flags: 0, + cltv_expiry_delta: (4 << 8) | 1, + htlc_minimum_msat: 0, + htlc_maximum_msat: OptionalField::Present(270_000), + fee_base_msat: 0, + fee_proportional_millionths: 1000000, + excess_data: Vec::new() + }); + + { + // 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 = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 90_000, 42, Arc::clone(&logger)).unwrap(); + assert_eq!(route.paths.len(), 1); + assert_eq!(route.paths[0].len(), 2); + + assert_eq!(route.paths[0][0].pubkey, nodes[7]); + assert_eq!(route.paths[0][0].short_channel_id, 12); + assert_eq!(route.paths[0][0].fee_msat, 90_000*2); + assert_eq!(route.paths[0][0].cltv_expiry_delta, (13 << 8) | 1); + assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(8)); + assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(12)); + + assert_eq!(route.paths[0][1].pubkey, nodes[2]); + assert_eq!(route.paths[0][1].short_channel_id, 13); + assert_eq!(route.paths[0][1].fee_msat, 90_000); + assert_eq!(route.paths[0][1].cltv_expiry_delta, 42); + assert_eq!(route.paths[0][1].node_features.le_flags(), &id_to_feature_flags(3)); + assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(13)); + } + } + + #[test] + fn htlc_max_reduction_below_min() { + // Test that if, while walking the graph, we reduce the value being sent to meet an + // htlc_maximum_msat, we don't end up undershooting a later htlc_minimum_msat. In the + // initial version of MPP we'd accept such routes but reject them while recalculating fees, + // resulting in us thinking there is no possible path, even if other paths exist. + let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph(); + let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); + + // We modify the graph to set the htlc_minimum of channel 2 and 4 as needed - channel 2 + // gets an htlc_maximum_msat of 80_000 and channel 4 an htlc_minimum_msat of 90_000. We + // then try to send 90_000. + update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate { + chain_hash: genesis_block(Network::Testnet).header.block_hash(), + short_channel_id: 2, + timestamp: 2, + flags: 0, + cltv_expiry_delta: 0, + htlc_minimum_msat: 0, + htlc_maximum_msat: OptionalField::Present(80_000), + fee_base_msat: 0, + fee_proportional_millionths: 0, + excess_data: Vec::new() + }); + update_channel(&net_graph_msg_handler, &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: (4 << 8) | 1, + htlc_minimum_msat: 90_000, + htlc_maximum_msat: OptionalField::Absent, + fee_base_msat: 0, + fee_proportional_millionths: 0, + excess_data: Vec::new() + }); + + { + // 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 = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(InvoiceFeatures::known()), None, &Vec::new(), 90_000, 42, Arc::clone(&logger)).unwrap(); + assert_eq!(route.paths.len(), 1); + assert_eq!(route.paths[0].len(), 2); + + assert_eq!(route.paths[0][0].pubkey, nodes[7]); + assert_eq!(route.paths[0][0].short_channel_id, 12); + assert_eq!(route.paths[0][0].fee_msat, 90_000*2); + assert_eq!(route.paths[0][0].cltv_expiry_delta, (13 << 8) | 1); + assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(8)); + assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(12)); + + assert_eq!(route.paths[0][1].pubkey, nodes[2]); + assert_eq!(route.paths[0][1].short_channel_id, 13); + assert_eq!(route.paths[0][1].fee_msat, 90_000); + assert_eq!(route.paths[0][1].cltv_expiry_delta, 42); + assert_eq!(route.paths[0][1].node_features.le_flags(), InvoiceFeatures::known().le_flags()); + assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(13)); + } + } } #[cfg(all(test, feature = "unstable"))] @@ -3367,7 +3629,38 @@ mod benches { seed *= 0xdeadbeef; let dst = graph.get_nodes().keys().skip(seed % graph.get_nodes().len()).next().unwrap(); let amt = seed as u64 % 1_000_000; - if get_route(src, &graph, dst, None, &[], amt, 42, &DummyLogger{}).is_ok() { + if get_route(src, &graph, dst, None, None, &[], amt, 42, &DummyLogger{}).is_ok() { + path_endpoints.push((src, dst, amt)); + continue 'load_endpoints; + } + } + } + + // ...then benchmark finding paths between the nodes we learned. + let mut idx = 0; + bench.iter(|| { + let (src, dst, amt) = path_endpoints[idx % path_endpoints.len()]; + assert!(get_route(src, &graph, dst, None, None, &[], amt, 42, &DummyLogger{}).is_ok()); + idx += 1; + }); + } + + #[bench] + fn generate_mpp_routes(bench: &mut Bencher) { + let mut d = File::open("net_graph-2021-02-12.bin").expect("Please fetch https://bitcoin.ninja/ldk-net_graph-879e309c128-2020-02-12.bin and place it at lightning/net_graph-2021-02-12.bin"); + let graph = NetworkGraph::read(&mut d).unwrap(); + + // First, get 100 (source, destination) pairs for which route-getting actually succeeds... + let mut path_endpoints = Vec::new(); + let mut seed: usize = 0xdeadbeef; + 'load_endpoints: for _ in 0..100 { + loop { + seed *= 0xdeadbeef; + let src = graph.get_nodes().keys().skip(seed % graph.get_nodes().len()).next().unwrap(); + seed *= 0xdeadbeef; + let dst = graph.get_nodes().keys().skip(seed % graph.get_nodes().len()).next().unwrap(); + let amt = seed as u64 % 1_000_000; + if get_route(src, &graph, dst, Some(InvoiceFeatures::known()), None, &[], amt, 42, &DummyLogger{}).is_ok() { path_endpoints.push((src, dst, amt)); continue 'load_endpoints; } @@ -3378,7 +3671,7 @@ mod benches { let mut idx = 0; bench.iter(|| { let (src, dst, amt) = path_endpoints[idx % path_endpoints.len()]; - assert!(get_route(src, &graph, dst, None, &[], amt, 42, &DummyLogger{}).is_ok()); + assert!(get_route(src, &graph, dst, Some(InvoiceFeatures::known()), None, &[], amt, 42, &DummyLogger{}).is_ok()); idx += 1; }); }