X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=1f143ed938dcf8435334c3c646057cee7163e200;hb=3dffe54258a374d15571d4ec72f5faa02477b770;hp=9242e98b1ab5061eca462e31b479f3e34602a8e3;hpb=ba8af2280de6ee906f4d3cc5185884d9faf31e66;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index 9242e98b..1f143ed9 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -64,7 +64,7 @@ impl< G: Deref>, L: Deref, S: Deref, SP: Sized, Sc: Sco payer: &PublicKey, params: &RouteParameters, first_hops: Option<&[&ChannelDetails]>, - inflight_htlcs: &InFlightHtlcs + inflight_htlcs: InFlightHtlcs ) -> Result { let random_seed_bytes = { let mut locked_random_seed_bytes = self.random_seed_bytes.lock().unwrap(); @@ -73,7 +73,7 @@ impl< G: Deref>, L: Deref, S: Deref, SP: Sized, Sc: Sco }; find_route( payer, params, &self.network_graph, first_hops, &*self.logger, - &ScorerAccountingForInFlightHtlcs::new(self.scorer.lock().deref_mut(), inflight_htlcs), + &ScorerAccountingForInFlightHtlcs::new(self.scorer.lock().deref_mut(), &inflight_htlcs), &self.score_params, &random_seed_bytes ) @@ -82,16 +82,24 @@ impl< G: Deref>, L: Deref, S: Deref, SP: Sized, Sc: Sco /// A trait defining behavior for routing a payment. pub trait Router { - /// Finds a [`Route`] between `payer` and `payee` for a payment with the given values. + /// Finds a [`Route`] for a payment between the given `payer` and a payee. + /// + /// The `payee` and the payment's value are given in [`RouteParameters::payment_params`] + /// and [`RouteParameters::final_value_msat`], respectively. fn find_route( &self, payer: &PublicKey, route_params: &RouteParameters, - first_hops: Option<&[&ChannelDetails]>, inflight_htlcs: &InFlightHtlcs + first_hops: Option<&[&ChannelDetails]>, inflight_htlcs: InFlightHtlcs ) -> Result; - /// Finds a [`Route`] between `payer` and `payee` for a payment with the given values. Includes - /// `PaymentHash` and `PaymentId` to be able to correlate the request with a specific payment. + /// Finds a [`Route`] for a payment between the given `payer` and a payee. + /// + /// The `payee` and the payment's value are given in [`RouteParameters::payment_params`] + /// and [`RouteParameters::final_value_msat`], respectively. + /// + /// Includes a [`PaymentHash`] and a [`PaymentId`] to be able to correlate the request with a specific + /// payment. fn find_route_with_id( &self, payer: &PublicKey, route_params: &RouteParameters, - first_hops: Option<&[&ChannelDetails]>, inflight_htlcs: &InFlightHtlcs, + first_hops: Option<&[&ChannelDetails]>, inflight_htlcs: InFlightHtlcs, _payment_hash: PaymentHash, _payment_id: PaymentId ) -> Result { self.find_route(payer, route_params, first_hops, inflight_htlcs) @@ -112,7 +120,7 @@ pub struct ScorerAccountingForInFlightHtlcs<'a, S: Score, SP: impl<'a, S: Score, SP: Sized> ScorerAccountingForInFlightHtlcs<'a, S, SP> { /// Initialize a new `ScorerAccountingForInFlightHtlcs`. - pub fn new(scorer: &'a mut S, inflight_htlcs: &'a InFlightHtlcs) -> Self { + pub fn new(scorer: &'a mut S, inflight_htlcs: &'a InFlightHtlcs) -> Self { ScorerAccountingForInFlightHtlcs { scorer, inflight_htlcs @@ -346,11 +354,9 @@ pub struct Route { /// [`BlindedTail`]s are present, then the pubkey of the last [`RouteHop`] in each path must be /// the same. pub paths: Vec, - /// The `payment_params` parameter passed to [`find_route`]. - /// This is used by `ChannelManager` to track information which may be required for retries, - /// provided back to you via [`Event::PaymentPathFailed`]. + /// The `payment_params` parameter passed via [`RouteParameters`] to [`find_route`]. /// - /// [`Event::PaymentPathFailed`]: crate::events::Event::PaymentPathFailed + /// This is used by `ChannelManager` to track information which may be required for retries. pub payment_params: Option, } @@ -358,7 +364,7 @@ impl Route { /// Returns the total amount of fees paid on this [`Route`]. /// /// This doesn't include any extra payment made to the recipient, which can happen in excess of - /// the amount passed to [`find_route`]'s `params.final_value_msat`. + /// the amount passed to [`find_route`]'s `route_params.final_value_msat`. pub fn get_total_fees(&self) -> u64 { self.paths.iter().map(|path| path.fee_msat()).sum() } @@ -419,7 +425,7 @@ impl Readable for Route { cmp::min(min_final_cltv_expiry_delta, hops.last().unwrap().cltv_expiry_delta); paths.push(Path { hops, blinded_tail: None }); } - _init_and_read_tlv_fields!(reader, { + _init_and_read_len_prefixed_tlv_fields!(reader, { (1, payment_params, (option: ReadableArgs, min_final_cltv_expiry_delta)), (2, blinded_tails, optional_vec), }); @@ -436,10 +442,7 @@ impl Readable for Route { /// Parameters needed to find a [`Route`]. /// -/// Passed to [`find_route`] and [`build_route_from_hops`], but also provided in -/// [`Event::PaymentPathFailed`]. -/// -/// [`Event::PaymentPathFailed`]: crate::events::Event::PaymentPathFailed +/// Passed to [`find_route`] and [`build_route_from_hops`]. #[derive(Clone, Debug, PartialEq, Eq)] pub struct RouteParameters { /// The parameters of the failed payment path. @@ -464,7 +467,7 @@ impl Writeable for RouteParameters { impl Readable for RouteParameters { fn read(reader: &mut R) -> Result { - _init_and_read_tlv_fields!(reader, { + _init_and_read_len_prefixed_tlv_fields!(reader, { (0, payment_params, (required: ReadableArgs, 0)), (2, final_value_msat, required), (4, final_cltv_delta, option), @@ -572,7 +575,7 @@ impl Writeable for PaymentParameters { impl ReadableArgs for PaymentParameters { fn read(reader: &mut R, default_final_cltv_expiry_delta: u32) -> Result { - _init_and_read_tlv_fields!(reader, { + _init_and_read_len_prefixed_tlv_fields!(reader, { (0, payee_pubkey, option), (1, max_total_cltv_expiry_delta, (default_value, DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA)), (2, features, (option: ReadableArgs, payee_pubkey.is_some())), @@ -649,11 +652,12 @@ impl PaymentParameters { /// [`PaymentParameters::expiry_time`]. pub fn from_bolt12_invoice(invoice: &Bolt12Invoice) -> Self { Self::blinded(invoice.payment_paths().to_vec()) - .with_bolt12_features(invoice.features().clone()).unwrap() + .with_bolt12_features(invoice.invoice_features().clone()).unwrap() .with_expiry_time(invoice.created_at().as_secs().saturating_add(invoice.relative_expiry().as_secs())) } - fn blinded(blinded_route_hints: Vec<(BlindedPayInfo, BlindedPath)>) -> Self { + /// Creates parameters for paying to a blinded payee from the provided blinded route hints. + pub fn blinded(blinded_route_hints: Vec<(BlindedPayInfo, BlindedPath)>) -> Self { Self { payee: Payee::Blinded { route_hints: blinded_route_hints, features: None }, expiry_time: None, @@ -1330,6 +1334,14 @@ impl<'a> fmt::Display for LoggedCandidateHop<'a> { " and blinding point ".fmt(f)?; hint.1.blinding_point.fmt(f) }, + CandidateRouteHop::FirstHop { .. } => { + "first hop with SCID ".fmt(f)?; + self.0.short_channel_id().unwrap().fmt(f) + }, + CandidateRouteHop::PrivateHop { .. } => { + "route hint with SCID ".fmt(f)?; + self.0.short_channel_id().unwrap().fmt(f) + }, _ => { "SCID ".fmt(f)?; self.0.short_channel_id().unwrap().fmt(f) @@ -1375,10 +1387,12 @@ fn sort_first_hop_channels( /// Finds a route from us (payer) to the given target node (payee). /// -/// If the payee provided features in their invoice, they should be provided via `params.payee`. +/// If the payee provided features in their invoice, they should be provided via the `payee` field +/// in the given [`RouteParameters::payment_params`]. /// Without this, MPP will only be used if the payee's features are available in the network graph. /// -/// Private routing paths between a public node and the target may be included in `params.payee`. +/// Private routing paths between a public node and the target may be included in the `payee` field +/// of [`RouteParameters::payment_params`]. /// /// If some channels aren't announced, it may be useful to fill in `first_hops` with the results /// from [`ChannelManager::list_usable_channels`]. If it is filled in, the view of these channels @@ -1388,15 +1402,9 @@ fn sort_first_hop_channels( /// 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. /// -/// # Note -/// -/// May be used to re-compute a [`Route`] when handling a [`Event::PaymentPathFailed`]. Any -/// adjustments to the [`NetworkGraph`] and channel scores should be made prior to calling this -/// function. -/// /// # Panics /// -/// Panics if first_hops contains channels without short_channel_ids; +/// Panics if first_hops contains channels without `short_channel_id`s; /// [`ChannelManager::list_usable_channels`] will never include such channels. /// /// [`ChannelManager::list_usable_channels`]: crate::ln::channelmanager::ChannelManager::list_usable_channels @@ -1641,6 +1649,12 @@ where L::Target: Logger { log_trace!(logger, "Building path from {} to payer {} for value {} msat.", LoggedPayeePubkey(payment_params.payee.node_id()), our_node_pubkey, final_value_msat); + // Remember how many candidates we ignored to allow for some logging afterwards. + let mut num_ignored_value_contribution = 0; + let mut num_ignored_path_length_limit = 0; + let mut num_ignored_cltv_delta_limit = 0; + let mut num_ignored_previously_failed = 0; + macro_rules! add_entry { // Adds entry which goes from $src_node_id to $dest_node_id over the $candidate hop. // $next_hops_fee_msat represents the fees paid for using all the channels *after* this one, @@ -1715,13 +1729,37 @@ where L::Target: Logger { let payment_failed_on_this_channel = scid_opt.map_or(false, |scid| payment_params.previously_failed_channels.contains(&scid)); + let should_log_candidate = match $candidate { + CandidateRouteHop::FirstHop { .. } => true, + CandidateRouteHop::PrivateHop { .. } => true, + CandidateRouteHop::Blinded { .. } => true, + _ => false, + }; + // If HTLC minimum is larger than the amount we're going to transfer, we shouldn't // bother considering this channel. If retrying with recommended_value_msat may // allow us to hit the HTLC minimum limit, set htlc_minimum_limit so that we go // around again with a higher amount. - if !contributes_sufficient_value || exceeds_max_path_length || - exceeds_cltv_delta_limit || payment_failed_on_this_channel { - // Path isn't useful, ignore it and move on. + if !contributes_sufficient_value { + if should_log_candidate { + log_trace!(logger, "Ignoring {} due to insufficient value contribution.", LoggedCandidateHop(&$candidate)); + } + num_ignored_value_contribution += 1; + } else if exceeds_max_path_length { + if should_log_candidate { + log_trace!(logger, "Ignoring {} due to exceeding maximum path length limit.", LoggedCandidateHop(&$candidate)); + } + num_ignored_path_length_limit += 1; + } else if exceeds_cltv_delta_limit { + if should_log_candidate { + log_trace!(logger, "Ignoring {} due to exceeding CLTV delta limit.", LoggedCandidateHop(&$candidate)); + } + num_ignored_cltv_delta_limit += 1; + } else if payment_failed_on_this_channel { + if should_log_candidate { + log_trace!(logger, "Ignoring {} due to a failed previous payment attempt.", LoggedCandidateHop(&$candidate)); + } + num_ignored_previously_failed += 1; } else if may_overpay_to_meet_path_minimum_msat { hit_minimum_limit = true; } else if over_path_minimum_msat { @@ -1999,8 +2037,14 @@ where L::Target: Logger { our_node_pubkey); for details in first_channels { let first_hop_candidate = CandidateRouteHop::FirstHop { details }; - add_entry!(first_hop_candidate, our_node_id, intro_node_id, 0, path_contribution_msat, 0, - 0_u64, 0, 0); + let blinded_path_fee = match compute_fees(path_contribution_msat, candidate.fees()) { + Some(fee) => fee, + None => continue + }; + add_entry!(first_hop_candidate, our_node_id, intro_node_id, blinded_path_fee, + path_contribution_msat, candidate.htlc_minimum_msat(), 0_u64, + candidate.cltv_expiry_delta(), + candidate.blinded_path().map_or(1, |bp| bp.blinded_hops.len() as u8)); } } } @@ -2323,6 +2367,12 @@ where L::Target: Logger { } } + let num_ignored_total = num_ignored_value_contribution + num_ignored_path_length_limit + + num_ignored_cltv_delta_limit + num_ignored_previously_failed; + if num_ignored_total > 0 { + log_trace!(logger, "Ignored {} candidate hops due to insufficient value contribution, {} due to path length limit, {} due to CLTV delta limit, {} due to previous payment failure. Total: {} ignored candidates.", num_ignored_value_contribution, num_ignored_path_length_limit, num_ignored_cltv_delta_limit, num_ignored_previously_failed, num_ignored_total); + } + // Step (5). if payment_paths.len() == 0 { return Err(LightningError{err: "Failed to find a path to the given destination".to_owned(), action: ErrorAction::IgnoreError}); @@ -2681,7 +2731,6 @@ mod tests { inbound_scid_alias: None, channel_value_satoshis: 0, user_channel_id: 0, - balance_msat: 0, outbound_capacity_msat, next_outbound_htlc_limit_msat: outbound_capacity_msat, next_outbound_htlc_minimum_msat: 0, @@ -3854,7 +3903,7 @@ mod tests { fn available_amount_while_routing_test() { // Tests whether we choose the correct available channel amount while routing. - let (secp_ctx, network_graph, mut gossip_sync, chain_monitor, logger) = build_graph(); + let (secp_ctx, network_graph, gossip_sync, chain_monitor, logger) = build_graph(); let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); let scorer = ln_test_utils::TestScorer::new(); let keys_manager = ln_test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet); @@ -6667,6 +6716,159 @@ mod tests { } assert_eq!(total_amount_paid_msat, 100_000); } + + #[test] + fn direct_to_intro_node() { + // This previously caused a debug panic in the router when asserting + // `used_liquidity_msat <= hop_max_msat`, because when adding first_hop<>blinded_route_hint + // direct channels we failed to account for the fee charged for use of the blinded path. + + // Build a graph: + // node0 -1(1)2 - node1 + // such that there isn't enough liquidity to reach node1, but the router thinks there is if it + // doesn't account for the blinded path fee. + + let secp_ctx = Secp256k1::new(); + let logger = Arc::new(ln_test_utils::TestLogger::new()); + let network_graph = Arc::new(NetworkGraph::new(Network::Testnet, Arc::clone(&logger))); + let gossip_sync = P2PGossipSync::new(Arc::clone(&network_graph), None, Arc::clone(&logger)); + let scorer = ln_test_utils::TestScorer::new(); + let keys_manager = ln_test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet); + let random_seed_bytes = keys_manager.get_secure_random_bytes(); + + let amt_msat = 10_000_000; + let (_, _, privkeys, nodes) = get_nodes(&secp_ctx); + add_channel(&gossip_sync, &secp_ctx, &privkeys[0], &privkeys[1], + ChannelFeatures::from_le_bytes(id_to_feature_flags(1)), 1); + update_channel(&gossip_sync, &secp_ctx, &privkeys[0], UnsignedChannelUpdate { + chain_hash: genesis_block(Network::Testnet).header.block_hash(), + short_channel_id: 1, + timestamp: 1, + flags: 0, + cltv_expiry_delta: 42, + htlc_minimum_msat: 1_000, + htlc_maximum_msat: 10_000_000, + fee_base_msat: 800, + fee_proportional_millionths: 0, + excess_data: Vec::new() + }); + update_channel(&gossip_sync, &secp_ctx, &privkeys[1], UnsignedChannelUpdate { + chain_hash: genesis_block(Network::Testnet).header.block_hash(), + short_channel_id: 1, + timestamp: 1, + flags: 1, + cltv_expiry_delta: 42, + htlc_minimum_msat: 1_000, + htlc_maximum_msat: 10_000_000, + fee_base_msat: 800, + fee_proportional_millionths: 0, + excess_data: Vec::new() + }); + let first_hops = vec![ + get_channel_details(Some(1), nodes[1], InitFeatures::from_le_bytes(vec![0b11]), 10_000_000)]; + + let blinded_path = BlindedPath { + introduction_node_id: nodes[1], + blinding_point: ln_test_utils::pubkey(42), + blinded_hops: vec![ + BlindedHop { blinded_node_id: ln_test_utils::pubkey(42 as u8), encrypted_payload: Vec::new() }, + BlindedHop { blinded_node_id: ln_test_utils::pubkey(42 as u8), encrypted_payload: Vec::new() } + ], + }; + let blinded_payinfo = BlindedPayInfo { + fee_base_msat: 1000, + fee_proportional_millionths: 0, + htlc_minimum_msat: 1000, + htlc_maximum_msat: MAX_VALUE_MSAT, + cltv_expiry_delta: 0, + features: BlindedHopFeatures::empty(), + }; + let blinded_hints = vec![(blinded_payinfo.clone(), blinded_path)]; + + let payment_params = PaymentParameters::blinded(blinded_hints.clone()); + + let netgraph = network_graph.read_only(); + if let Err(LightningError { err, .. }) = get_route(&nodes[0], &payment_params, &netgraph, + Some(&first_hops.iter().collect::>()), amt_msat, Arc::clone(&logger), &scorer, &(), + &random_seed_bytes) { + assert_eq!(err, "Failed to find a path to the given destination"); + } else { panic!("Expected error") } + + // Sending an exact amount accounting for the blinded path fee works. + let amt_minus_blinded_path_fee = amt_msat - blinded_payinfo.fee_base_msat as u64; + let route = get_route(&nodes[0], &payment_params, &netgraph, + Some(&first_hops.iter().collect::>()), amt_minus_blinded_path_fee, + Arc::clone(&logger), &scorer, &(), &random_seed_bytes).unwrap(); + assert_eq!(route.get_total_fees(), blinded_payinfo.fee_base_msat as u64); + assert_eq!(route.get_total_amount(), amt_minus_blinded_path_fee); + } + + #[test] + fn direct_to_matching_intro_nodes() { + // This previously caused us to enter `unreachable` code in the following situation: + // 1. We add a route candidate for intro_node contributing a high amount + // 2. We add a first_hop<>intro_node route candidate for the same high amount + // 3. We see a cheaper blinded route hint for the same intro node but a much lower contribution + // amount, and update our route candidate for intro_node for the lower amount + // 4. We then attempt to update the aforementioned first_hop<>intro_node route candidate for the + // lower contribution amount, but fail (this was previously caused by failure to account for + // blinded path fees when adding first_hop<>intro_node candidates) + // 5. We go to construct the path from these route candidates and our first_hop<>intro_node + // candidate still thinks its path is contributing the original higher amount. This caused us + // to hit an `unreachable` overflow when calculating the cheaper intro_node fees over the + // larger amount + let secp_ctx = Secp256k1::new(); + let logger = Arc::new(ln_test_utils::TestLogger::new()); + let network_graph = Arc::new(NetworkGraph::new(Network::Testnet, Arc::clone(&logger))); + let scorer = ln_test_utils::TestScorer::new(); + let keys_manager = ln_test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet); + let random_seed_bytes = keys_manager.get_secure_random_bytes(); + let config = UserConfig::default(); + + // Values are taken from the fuzz input that uncovered this panic. + let amt_msat = 21_7020_5185_1403_2640; + let (_, _, _, nodes) = get_nodes(&secp_ctx); + let first_hops = vec![ + get_channel_details(Some(1), nodes[1], channelmanager::provided_init_features(&config), + 18446744073709551615)]; + + let blinded_path = BlindedPath { + introduction_node_id: nodes[1], + blinding_point: ln_test_utils::pubkey(42), + blinded_hops: vec![ + BlindedHop { blinded_node_id: ln_test_utils::pubkey(42 as u8), encrypted_payload: Vec::new() }, + BlindedHop { blinded_node_id: ln_test_utils::pubkey(42 as u8), encrypted_payload: Vec::new() } + ], + }; + let blinded_payinfo = BlindedPayInfo { + fee_base_msat: 5046_2720, + fee_proportional_millionths: 0, + htlc_minimum_msat: 4503_5996_2737_0496, + htlc_maximum_msat: 45_0359_9627_3704_9600, + cltv_expiry_delta: 0, + features: BlindedHopFeatures::empty(), + }; + let mut blinded_hints = vec![ + (blinded_payinfo.clone(), blinded_path.clone()), + (blinded_payinfo.clone(), blinded_path.clone()), + ]; + blinded_hints[1].0.fee_base_msat = 419_4304; + blinded_hints[1].0.fee_proportional_millionths = 257; + blinded_hints[1].0.htlc_minimum_msat = 280_8908_6115_8400; + blinded_hints[1].0.htlc_maximum_msat = 2_8089_0861_1584_0000; + blinded_hints[1].0.cltv_expiry_delta = 0; + + let bolt12_features: Bolt12InvoiceFeatures = channelmanager::provided_invoice_features(&config).to_context(); + let payment_params = PaymentParameters::blinded(blinded_hints.clone()) + .with_bolt12_features(bolt12_features.clone()).unwrap(); + + let netgraph = network_graph.read_only(); + let route = get_route(&nodes[0], &payment_params, &netgraph, + Some(&first_hops.iter().collect::>()), amt_msat, + Arc::clone(&logger), &scorer, &(), &random_seed_bytes).unwrap(); + assert_eq!(route.get_total_fees(), blinded_payinfo.fee_base_msat as u64); + assert_eq!(route.get_total_amount(), amt_msat); + } } #[cfg(all(any(test, ldk_bench), not(feature = "no-std")))] @@ -6750,7 +6952,6 @@ pub(crate) mod bench_utils { outbound_scid_alias: None, channel_value_satoshis: 10_000_000_000, user_channel_id: 0, - balance_msat: 10_000_000_000, outbound_capacity_msat: 10_000_000_000, next_outbound_htlc_minimum_msat: 0, next_outbound_htlc_limit_msat: 10_000_000_000,