X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=add1726623541d11f328635b56ab3e6622ef76e4;hb=5c38e09b2616ee78ccaa257dc4502f2f373c4a9e;hp=fedad42cfb2c6468f530931c5c31a623236acb8a;hpb=db4721f3a70ab7490eee244f24049392ad854aa4;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index fedad42c..add17266 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}; @@ -39,13 +39,15 @@ pub struct RouteHop { /// to reach this node. pub channel_features: ChannelFeatures, /// The fee taken on this hop (for paying for the use of the *next* channel in the path). - /// For the last hop, this should be the full value of the payment. + /// For the last hop, this should be the full value of the payment (might be more than + /// requested if we had to match htlc_minimum_msat). pub fee_msat: u64, /// The CLTV delta added for this hop. For the last hop, this should be the full CLTV value /// expected at the destination, in excess of the current block height. pub cltv_expiry_delta: u32, } +/// (C-not exported) impl Writeable for Vec { fn write(&self, writer: &mut W) -> Result<(), ::std::io::Error> { (self.len() as u8).write(writer)?; @@ -61,6 +63,7 @@ impl Writeable for Vec { } } +/// (C-not exported) impl Readable for Vec { fn read(reader: &mut R) -> Result, DecodeError> { let hops_count: u8 = Readable::read(reader)?; @@ -186,6 +189,10 @@ struct PathBuildingHop { /// an estimated cost of reaching this hop. /// Might get stale when fees are recomputed. Primarily for internal use. total_fee_msat: u64, + /// This is useful for update_value_and_recompute_fees to make sure + /// we don't fall below the minimum. Should not be updated manually and + /// generally should not be accessed. + htlc_minimum_msat: u64, } // Instantiated with a list of hops with correct data in them collected during path finding, @@ -216,35 +223,78 @@ impl PaymentPath { return result; } - // If an amount transferred by the path is updated, the fees should be adjusted. - // Any other way to change fees may result in an inconsistency. - // The caller should make sure values don't fall below htlc_minimum_msat of the used channels. + // If the amount transferred by the path is updated, the fees should be adjusted. Any other way + // to change fees may result in an inconsistency. + // + // Sometimes we call this function right after constructing a path which has inconsistent + // (in terms of reaching htlc_minimum_msat), so that this function puts the fees in order. + // In that case we call it on the "same" amount we initially allocated for this path, and which + // could have been reduced on the way. In that case, there is also a risk of exceeding + // available_liquidity inside this function, because the function is unaware of this bound. + // In our specific recomputation cases where we never increase the value the risk is pretty low. + // This function, however, does not support arbitrarily increasing the value being transferred, + // and the exception will be triggered. fn update_value_and_recompute_fees(&mut self, value_msat: u64) { + assert!(value_msat <= self.hops.last().unwrap().route_hop.fee_msat); + let mut total_fee_paid_msat = 0 as u64; - for i in (1..self.hops.len()).rev() { - let cur_hop_amount_msat = total_fee_paid_msat + value_msat; + for i in (0..self.hops.len()).rev() { + let last_hop = i == self.hops.len() - 1; + + // For non-last-hop, this value will represent the fees paid on the current hop. It + // will consist of the fees for the use of the next hop, and extra fees to match + // htlc_minimum_msat of the current channel. Last hop is handled separately. + let mut cur_hop_fees_msat = 0; + if !last_hop { + cur_hop_fees_msat = self.hops.get(i + 1).unwrap().hop_use_fee_msat; + } + let mut cur_hop = self.hops.get_mut(i).unwrap(); cur_hop.next_hops_fee_msat = total_fee_paid_msat; - if let Some(new_fee) = compute_fees(cur_hop_amount_msat, cur_hop.channel_fees) { - cur_hop.hop_use_fee_msat = new_fee; - total_fee_paid_msat += new_fee; + // Overpay in fees if we can't save these funds due to htlc_minimum_msat. + // We try to account for htlc_minimum_msat in scoring (add_entry!), so that nodes don't + // set it too high just to maliciously take more fees by exploiting this + // match htlc_minimum_msat logic. + let mut cur_hop_transferred_amount_msat = total_fee_paid_msat + value_msat; + if let Some(extra_fees_msat) = cur_hop.htlc_minimum_msat.checked_sub(cur_hop_transferred_amount_msat) { + // Note that there is a risk that *previous hops* (those closer to us, as we go + // payee->our_node here) would exceed their htlc_maximum_msat or available balance. + // + // This might make us end up with a broken route, although this should be super-rare + // in practice, both because of how healthy channels look like, and how we pick + // channels in add_entry. + // Also, this can't be exploited more heavily than *announce a free path and fail + // all payments*. + cur_hop_transferred_amount_msat += extra_fees_msat; + total_fee_paid_msat += extra_fees_msat; + cur_hop_fees_msat += extra_fees_msat; + } + + if last_hop { + // Final hop is a special case: it usually has just value_msat (by design), but also + // it still could overpay for the htlc_minimum_msat. + cur_hop.route_hop.fee_msat = cur_hop_transferred_amount_msat; } else { - // It should not be possible because this function is called only to reduce the - // value. In that case, compute_fee was already called with the same fees for - // larger amount and there was no overflow. - unreachable!(); + // Propagate updated fees for the use of the channels to one hop back, where they + // will be actually paid (fee_msat). The last hop is handled above separately. + cur_hop.route_hop.fee_msat = cur_hop_fees_msat; } - } - // Propagate updated fees for the use of the channels to one hop back, - // where they will be actually paid (fee_msat). - // For the last hop it will represent the value being transferred over this path. - for i in 0..self.hops.len() - 1 { - let next_hop_use_fee_msat = self.hops.get(i + 1).unwrap().hop_use_fee_msat; - self.hops.get_mut(i).unwrap().route_hop.fee_msat = next_hop_use_fee_msat; + // Fee for the use of the current hop which will be deducted on the previous hop. + // Irrelevant for the first hop, as it doesn't have the previous hop, and the use of + // this channel is free for us. + if i != 0 { + if let Some(new_fee) = compute_fees(cur_hop_transferred_amount_msat, cur_hop.channel_fees) { + cur_hop.hop_use_fee_msat = new_fee; + total_fee_paid_msat += new_fee; + } else { + // It should not be possible because this function is called only to reduce the + // value. In that case, compute_fee was already called with the same fees for + // larger amount and there was no overflow. + unreachable!(); + } + } } - self.hops.last_mut().unwrap().route_hop.fee_msat = value_msat; - self.hops.last_mut().unwrap().hop_use_fee_msat = 0; } } @@ -264,6 +314,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. /// @@ -278,7 +331,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. @@ -319,8 +372,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. @@ -338,13 +426,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 @@ -354,21 +458,10 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye if let Some(hops) = first_hops { for chan in hops { let short_channel_id = chan.short_channel_id.expect("first_hops should be filled in with usable channels, not pending ones"); - if chan.remote_network_id == *payee { - return Ok(Route { - paths: vec![vec![RouteHop { - pubkey: chan.remote_network_id, - node_features: chan.counterparty_features.to_context(), - short_channel_id, - channel_features: chan.counterparty_features.to_context(), - fee_msat: final_value_msat, - cltv_expiry_delta: final_cltv, - }]], - }); - } else if chan.remote_network_id == *our_node_id { + if chan.remote_network_id == *our_node_id { return Err(LightningError{err: "First hop cannot have our_node_id as a destination.".to_owned(), action: ErrorAction::IgnoreError}); } - first_hop_targets.insert(chan.remote_network_id, (short_channel_id, chan.counterparty_features.clone())); + first_hop_targets.insert(chan.remote_network_id, (short_channel_id, chan.counterparty_features.clone(), chan.outbound_capacity_msat)); } if first_hop_targets.is_empty() { return Err(LightningError{err: "Cannot route when there are no outbound routes away from us".to_owned(), action: ErrorAction::IgnoreError}); @@ -378,8 +471,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // 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. - // TODO: we could let a caller specify this. Definitely useful when considering our own channels. + // It is unaware of the directions (except for `outbound_capacity_msat` in `first_hops`). let mut bookkeeped_channels_liquidity_available_msat = HashMap::new(); // Keeping track of how much value we already collected across other paths. Helps to decide: @@ -446,8 +538,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; @@ -459,17 +556,18 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye None => unreachable!(), }; - // If HTLC minimum is larger than the whole value we're going to transfer, we shouldn't bother - // even considering this channel, because it won't be useful. - // TODO: Explore simply adding fee to hit htlc_minimum_msat - // This is separate from checking amount_to_transfer_over_msat, which also should be - // lower-bounded by htlc_minimum_msat. Since we're choosing it as maximum possible, - // this channel should just be skipped if it's not sufficient. - // amount_to_transfer_over_msat can be both larger and smaller than final_value_msat, - // so this can't be derived. - let final_value_satisfies_htlc_minimum_msat = final_value_msat >= $directional_info.htlc_minimum_msat; - if final_value_satisfies_htlc_minimum_msat && - contributes_sufficient_value && amount_to_transfer_over_msat >= $directional_info.htlc_minimum_msat { + // If HTLC minimum is larger than the amount we're going to transfer, we shouldn't + // bother considering this channel. + // Since we're choosing amount_to_transfer_over_msat as maximum possible, it can + // be only reduced later (not increased), so this channel should just be skipped + // as not sufficient. + if amount_to_transfer_over_msat < $directional_info.htlc_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 hm_entry = dist.entry(&$src_node_id); let old_entry = hm_entry.or_insert_with(|| { // If there was previously no known way to access @@ -500,6 +598,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye next_hops_fee_msat: u64::max_value(), hop_use_fee_msat: u64::max_value(), total_fee_msat: u64::max_value(), + htlc_minimum_msat: $directional_info.htlc_minimum_msat, } }); @@ -547,7 +646,29 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // (considering the cost to "reach" this channel from the route destination, // the cost of using this channel, // and the cost of routing to the source node of this channel). - if old_entry.total_fee_msat > total_fee_msat { + // Also, consider that htlc_minimum_msat_difference, because we might end up + // paying it. Consider the following exploit: + // we use 2 paths to transfer 1.5 BTC. One of them is 0-fee normal 1 BTC path, + // and for the other one we picked a 1sat-fee path with htlc_minimum_msat of + // 1 BTC. Now, since the latter is more expensive, we gonna try to cut it + // by 0.5 BTC, but then match htlc_minimum_msat by paying a fee of 0.5 BTC + // to this channel. + // TODO: this scoring could be smarter (e.g. 0.5*htlc_minimum_msat here). + let mut old_cost = old_entry.total_fee_msat; + if let Some(increased_old_cost) = old_cost.checked_add(old_entry.htlc_minimum_msat) { + old_cost = increased_old_cost; + } else { + old_cost = u64::max_value(); + } + + let mut new_cost = total_fee_msat; + if let Some(increased_new_cost) = new_cost.checked_add($directional_info.htlc_minimum_msat) { + new_cost = increased_new_cost; + } else { + new_cost = u64::max_value(); + } + + if new_cost < old_cost { targets.push(new_graph_node); old_entry.next_hops_fee_msat = $next_hops_fee_msat; old_entry.hop_use_fee_msat = hop_use_fee_msat; @@ -561,6 +682,9 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye cltv_expiry_delta: $directional_info.cltv_expiry_delta as u32, }; old_entry.channel_fees = $directional_info.fees; + // It's probably fine to replace the old entry, because the new one + // passed the htlc_minimum-related checks above. + old_entry.htlc_minimum_msat = $directional_info.htlc_minimum_msat; } } } @@ -576,8 +700,8 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye macro_rules! add_entries_to_cheapest_to_target_node { ( $node: expr, $node_id: expr, $fee_to_target_msat: expr, $next_hops_value_contribution: expr ) => { if first_hops.is_some() { - if let Some(&(ref first_hop, ref features)) = first_hop_targets.get(&$node_id) { - add_entry!(first_hop, *our_node_id, $node_id, dummy_directional_info, None::, features.to_context(), $fee_to_target_msat, $next_hops_value_contribution); + 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); } } @@ -626,6 +750,15 @@ 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, path_value_msat); + } + } // Add the payee as a target, so that the payee-to-payer // search algorithm knows what to start with. @@ -636,7 +769,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); }, } @@ -646,7 +779,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // it matters only if the fees are exactly the same. for hop in last_hops.iter() { let have_hop_src_in_graph = - if let Some(&(ref first_hop, ref features)) = first_hop_targets.get(&hop.src_node_id) { + if let Some(&(ref first_hop, ref features, ref outbound_capacity_msat)) = first_hop_targets.get(&hop.src_node_id) { // If this hop connects to a node with which we have a direct channel, ignore // the network graph and add both the hop and our direct channel to // the candidate set. @@ -655,7 +788,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, None::, 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); true } else { // In any other case, only add the hop if the source is in the regular network @@ -675,7 +808,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); } } @@ -701,7 +834,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye let mut ordered_hops = vec!(new_entry.clone()); 'path_walk: loop { - if let Some(&(_, ref features)) = first_hop_targets.get(&ordered_hops.last().unwrap().route_hop.pubkey) { + if let Some(&(_, ref features, _)) = first_hop_targets.get(&ordered_hops.last().unwrap().route_hop.pubkey) { ordered_hops.last_mut().unwrap().route_hop.node_features = features.to_context(); } else if let Some(node) = network.get_nodes().get(&ordered_hops.last().unwrap().route_hop.pubkey) { if let Some(node_info) = node.announcement_info.as_ref() { @@ -742,7 +875,15 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye ordered_hops.last_mut().unwrap().hop_use_fee_msat = 0; ordered_hops.last_mut().unwrap().route_hop.cltv_expiry_delta = final_cltv; - let payment_path = PaymentPath {hops: ordered_hops}; + let mut payment_path = PaymentPath {hops: ordered_hops}; + + // We could have possibly constructed a slightly inconsistent path: since we reduce + // value being transferred along the way, we could have violated htlc_minimum_msat + // 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); + // Since a path allows to transfer as much value as // the smallest channel it has ("bottleneck"), we should recompute // the fees so sender HTLC don't overpay fees when traversing @@ -752,7 +893,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. - for (i, payment_hop) in payment_path.hops.iter().enumerate() { + 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; let next_hops_fee_msat = payment_hop.next_hops_fee_msat; @@ -786,13 +927,28 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye } } + 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; } } @@ -837,7 +993,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // Sort by value so that we drop many really-low values first, since // fewer paths is better: the payment is less likely to fail. // TODO: this could also be optimized by also sorting by feerate_per_sat_routed, - // so that the sender pays less fees overall. + // so that the sender pays less fees overall. And also htlc_minimum_msat. cur_route.sort_by_key(|path| path.get_value_msat()); // We should make sure that at least 1 path left. let mut paths_left = cur_route.len(); @@ -863,10 +1019,14 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // Step (7). // Now, substract the overpaid value from the most-expensive path. + // TODO: this could also be optimized by also sorting by feerate_per_sat_routed, + // so that the sender pays less fees overall. And also htlc_minimum_msat. cur_route.sort_by_key(|path| { path.hops.iter().map(|hop| hop.channel_fees.proportional_millionths as u64).sum::() }); - let expensive_payment_path = cur_route.last_mut().unwrap(); + let expensive_payment_path = cur_route.first_mut().unwrap(); + // We already dropped all the small channels above, meaning all the + // remaining channels are larger than remaining overpaid_value_msat. + // Thus, this can't be negative. let expensive_path_new_value_msat = expensive_payment_path.get_value_msat() - overpaid_value_msat; - // TODO: make sure expensive_path_new_value_msat doesn't cause to fall behind htlc_minimum_msat. expensive_payment_path.update_value_and_recompute_fees(expensive_path_new_value_msat); break; } @@ -877,21 +1037,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::>::new(); + 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; @@ -1320,11 +1486,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]); @@ -1359,13 +1525,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); } @@ -1375,33 +1542,6 @@ mod tests { let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); // Simple route to 2 via 1 - // Should fail if htlc_minimum can't be reached - - 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: 50_000, - htlc_maximum_msat: OptionalField::Absent, - fee_base_msat: 0, - fee_proportional_millionths: 0, - excess_data: Vec::new() - }); - // Make 0 fee. - 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: 0, - htlc_minimum_msat: 0, - htlc_maximum_msat: OptionalField::Absent, - fee_base_msat: 0, - fee_proportional_millionths: 0, - excess_data: Vec::new() - }); // Disable other paths update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate { @@ -1465,16 +1605,7 @@ mod tests { excess_data: Vec::new() }); - 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(), 49_999, 42, Arc::clone(&logger)) { - assert_eq!(err, "Failed to find a path to the given destination"); - } else { panic!(); } - - // 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(), 50_000, 42, Arc::clone(&logger)).unwrap(); - assert_eq!(route.paths[0].len(), 2); - - // This was a check against final_value_msat. - // Now let's check against amount_to_transfer_over_msat. + // Check against amount_to_transfer_over_msat. // Set minimal HTLC of 200_000_000 msat. update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate { chain_hash: genesis_block(Network::Testnet).header.block_hash(), @@ -1505,7 +1636,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!(); } @@ -1524,10 +1655,147 @@ 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); } + #[test] + fn htlc_minimum_overpay_test() { + let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph(); + let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); + + // A route to node#2 via two paths. + // One path allows transferring 35-40 sats, another one also allows 35-40 sats. + // Thus, they can't send 60 without overpaying. + 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: 35_000, + htlc_maximum_msat: OptionalField::Present(40_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: 3, + flags: 0, + cltv_expiry_delta: 0, + htlc_minimum_msat: 35_000, + htlc_maximum_msat: OptionalField::Present(40_000), + fee_base_msat: 0, + fee_proportional_millionths: 0, + excess_data: Vec::new() + }); + + // Make 0 fee. + update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], UnsignedChannelUpdate { + chain_hash: genesis_block(Network::Testnet).header.block_hash(), + short_channel_id: 13, + timestamp: 2, + 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, &privkeys[1], UnsignedChannelUpdate { + chain_hash: genesis_block(Network::Testnet).header.block_hash(), + short_channel_id: 4, + timestamp: 2, + flags: 0, + cltv_expiry_delta: 0, + htlc_minimum_msat: 0, + htlc_maximum_msat: OptionalField::Absent, + fee_base_msat: 0, + fee_proportional_millionths: 0, + excess_data: Vec::new() + }); + + // Disable other paths + update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate { + chain_hash: genesis_block(Network::Testnet).header.block_hash(), + short_channel_id: 1, + timestamp: 3, + flags: 2, // to disable + 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() + }); + + 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. + assert_eq!(overpaid_fees, 15_000); + + // Now, test that if there are 2 paths, a "cheaper" by fee path wouldn't be prioritized + // while taking even more fee to match htlc_minimum_msat. + 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: 4, + flags: 0, + cltv_expiry_delta: 0, + htlc_minimum_msat: 65_000, + 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, &our_privkey, UnsignedChannelUpdate { + chain_hash: genesis_block(Network::Testnet).header.block_hash(), + short_channel_id: 2, + timestamp: 3, + 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, &privkeys[1], UnsignedChannelUpdate { + chain_hash: genesis_block(Network::Testnet).header.block_hash(), + short_channel_id: 4, + timestamp: 4, + flags: 0, + cltv_expiry_delta: 0, + htlc_minimum_msat: 0, + htlc_maximum_msat: OptionalField::Absent, + fee_base_msat: 0, + fee_proportional_millionths: 100_000, + excess_data: Vec::new() + }); + + 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], + 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); + assert_eq!(route.paths[0][0].short_channel_id, 2); + let fees = route.paths[0][0].fee_msat; + assert_eq!(fees, 5_000); + } + #[test] fn disable_channels_test() { let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph(); @@ -1560,7 +1828,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!(); } @@ -1572,11 +1840,12 @@ mod tests { counterparty_features: InitFeatures::from_le_bytes(vec![0b11]), channel_value_satoshis: 0, user_id: 0, - outbound_capacity_msat: 0, + 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]); @@ -1607,7 +1876,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!(); } @@ -1619,11 +1888,12 @@ mod tests { counterparty_features: InitFeatures::from_le_bytes(vec![0b11]), channel_value_satoshis: 0, user_id: 0, - outbound_capacity_msat: 0, + 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]); @@ -1651,7 +1921,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]); @@ -1683,11 +1953,12 @@ mod tests { counterparty_features: InitFeatures::from_le_bytes(vec![0b11]), channel_value_satoshis: 0, user_id: 0, - outbound_capacity_msat: 0, + 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]); @@ -1760,12 +2031,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]); @@ -1819,12 +2090,13 @@ mod tests { counterparty_features: InitFeatures::from_le_bytes(vec![0b11]), channel_value_satoshis: 0, user_id: 0, - outbound_capacity_msat: 0, + 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]); @@ -1844,7 +2116,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]); @@ -1878,7 +2150,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]); @@ -1950,8 +2222,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); @@ -2038,14 +2311,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); @@ -2053,6 +2328,69 @@ mod tests { assert_eq!(path.last().unwrap().fee_msat, 250_000_000); } + // Check that setting outbound_capacity_msat in first_hops limits the channels. + // Disable channel #1 and use another first hop. + update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate { + chain_hash: genesis_block(Network::Testnet).header.block_hash(), + short_channel_id: 1, + timestamp: 3, + flags: 2, + cltv_expiry_delta: 0, + htlc_minimum_msat: 0, + htlc_maximum_msat: OptionalField::Present(1_000_000_000), + fee_base_msat: 0, + fee_proportional_millionths: 0, + excess_data: Vec::new() + }); + + // Now, limit the first_hop by the outbound_capacity_msat of 200_000 sats. + let our_chans = vec![channelmanager::ChannelDetails { + channel_id: [0; 32], + short_channel_id: Some(42), + remote_network_id: nodes[0].clone(), + counterparty_features: InitFeatures::from_le_bytes(vec![0b11]), + channel_value_satoshis: 0, + user_id: 0, + 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(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(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); + assert_eq!(path.last().unwrap().pubkey, nodes[2]); + assert_eq!(path.last().unwrap().fee_msat, 200_000_000); + } + + // Enable channel #1 back. + update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate { + chain_hash: genesis_block(Network::Testnet).header.block_hash(), + short_channel_id: 1, + timestamp: 4, + flags: 0, + cltv_expiry_delta: 0, + htlc_minimum_msat: 0, + htlc_maximum_msat: OptionalField::Present(1_000_000_000), + fee_base_msat: 0, + fee_proportional_millionths: 0, + excess_data: Vec::new() + }); + + // Now let's see if routing works if we know only htlc_maximum_msat. update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate { chain_hash: genesis_block(Network::Testnet).header.block_hash(), @@ -2069,14 +2407,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); @@ -2138,14 +2478,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); @@ -2169,14 +2511,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); @@ -2275,14 +2619,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 { @@ -2295,7 +2641,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 { @@ -2339,7 +2686,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 { @@ -2446,7 +2793,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!(); } } @@ -2454,7 +2802,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 { @@ -2467,7 +2816,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 { @@ -2617,7 +2967,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!(); } } @@ -2625,7 +2976,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; @@ -2781,7 +3133,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; @@ -2946,14 +3299,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; @@ -3062,7 +3417,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!(); } } @@ -3070,7 +3426,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 { @@ -3083,7 +3440,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 { @@ -3095,4 +3453,138 @@ 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)); + } + } +} + +#[cfg(all(test, feature = "unstable"))] +mod benches { + use super::*; + use util::logger::{Logger, Record}; + + use std::fs::File; + use test::Bencher; + + struct DummyLogger {} + impl Logger for DummyLogger { + fn log(&self, _record: &Record) {} + } + + #[bench] + fn generate_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, 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; + } + } + } + + // ...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, Some(InvoiceFeatures::known()), None, &[], amt, 42, &DummyLogger{}).is_ok()); + idx += 1; + }); + } }