X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=7abca061f3b480cfd9d011b9bd70cdbc53778b76;hb=b315856e686dd9e72a7ff93616f314ca6a037b56;hp=15f43d2975dcd37aae08105a0615127c29cda748;hpb=47cb45ed32c09f39418abd200cfc1f7d402964e4;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index 15f43d29..7abca061 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -16,9 +16,9 @@ use bitcoin::hashes::sha256::Hash as Sha256; use crate::blinded_path::{BlindedHop, BlindedPath}; use crate::ln::PaymentHash; use crate::ln::channelmanager::{ChannelDetails, PaymentId}; -use crate::ln::features::{Bolt12InvoiceFeatures, ChannelFeatures, InvoiceFeatures, NodeFeatures}; +use crate::ln::features::{Bolt11InvoiceFeatures, Bolt12InvoiceFeatures, ChannelFeatures, NodeFeatures}; use crate::ln::msgs::{DecodeError, ErrorAction, LightningError, MAX_VALUE_MSAT}; -use crate::offers::invoice::{BlindedPayInfo, Invoice as Bolt12Invoice}; +use crate::offers::invoice::{BlindedPayInfo, Bolt12Invoice}; use crate::routing::gossip::{DirectedChannelInfo, EffectiveCapacity, ReadOnlyNetworkGraph, NetworkGraph, NodeId, RoutingFees}; use crate::routing::scoring::{ChannelUsage, LockableScore, Score}; use crate::util::ser::{Writeable, Readable, ReadableArgs, Writer}; @@ -27,15 +27,15 @@ use crate::util::chacha20::ChaCha20; use crate::io; use crate::prelude::*; -use crate::sync::{Mutex, MutexGuard}; +use crate::sync::{Mutex}; use alloc::collections::BinaryHeap; use core::{cmp, fmt}; -use core::ops::Deref; +use core::ops::{Deref, DerefMut}; /// A [`Router`] implemented using [`find_route`]. pub struct DefaultRouter>, L: Deref, S: Deref, SP: Sized, Sc: Score> where L::Target: Logger, - S::Target: for <'a> LockableScore<'a, Locked = MutexGuard<'a, Sc>>, + S::Target: for <'a> LockableScore<'a, Score = Sc>, { network_graph: G, logger: L, @@ -46,7 +46,7 @@ pub struct DefaultRouter>, L: Deref, S: Deref, impl>, L: Deref, S: Deref, SP: Sized, Sc: Score> DefaultRouter where L::Target: Logger, - S::Target: for <'a> LockableScore<'a, Locked = MutexGuard<'a, Sc>>, + S::Target: for <'a> LockableScore<'a, Score = Sc>, { /// Creates a new router. pub fn new(network_graph: G, logger: L, random_seed_bytes: [u8; 32], scorer: S, score_params: SP) -> Self { @@ -55,16 +55,16 @@ impl>, L: Deref, S: Deref, SP: Sized, Sc: Scor } } -impl< G: Deref>, L: Deref, S: Deref, SP: Sized, Sc: Score> Router for DefaultRouter where +impl< G: Deref>, L: Deref, S: Deref, SP: Sized, Sc: Score> Router for DefaultRouter where L::Target: Logger, - S::Target: for <'a> LockableScore<'a, Locked = MutexGuard<'a, Sc>>, + S::Target: for <'a> LockableScore<'a, Score = Sc>, { fn find_route( &self, 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: Sc }; find_route( payer, params, &self.network_graph, first_hops, &*self.logger, - &ScorerAccountingForInFlightHtlcs::new(self.scorer.lock(), 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: Sc /// 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) @@ -104,15 +112,15 @@ pub trait Router { /// [`find_route`]. /// /// [`Score`]: crate::routing::scoring::Score -pub struct ScorerAccountingForInFlightHtlcs<'a, S: Score> { - scorer: S, +pub struct ScorerAccountingForInFlightHtlcs<'a, S: Score, SP: Sized> { + scorer: &'a mut S, // Maps a channel's short channel id and its direction to the liquidity used up. inflight_htlcs: &'a InFlightHtlcs, } -impl<'a, S: Score> ScorerAccountingForInFlightHtlcs<'a, S> { +impl<'a, S: Score, SP: Sized> ScorerAccountingForInFlightHtlcs<'a, S, SP> { /// Initialize a new `ScorerAccountingForInFlightHtlcs`. - pub fn new(scorer: S, inflight_htlcs: &'a InFlightHtlcs) -> Self { + pub fn new(scorer: &'a mut S, inflight_htlcs: &'a InFlightHtlcs) -> Self { ScorerAccountingForInFlightHtlcs { scorer, inflight_htlcs @@ -121,11 +129,11 @@ impl<'a, S: Score> ScorerAccountingForInFlightHtlcs<'a, S> { } #[cfg(c_bindings)] -impl<'a, S: Score> Writeable for ScorerAccountingForInFlightHtlcs<'a, S> { +impl<'a, S: Score, SP: Sized> Writeable for ScorerAccountingForInFlightHtlcs<'a, S, SP> { fn write(&self, writer: &mut W) -> Result<(), io::Error> { self.scorer.write(writer) } } -impl<'a, S: Score> Score for ScorerAccountingForInFlightHtlcs<'a, S> { +impl<'a, S: Score, SP: Sized> Score for ScorerAccountingForInFlightHtlcs<'a, S, SP> { type ScoreParams = S::ScoreParams; fn channel_penalty_msat(&self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage, score_params: &Self::ScoreParams) -> u64 { if let Some(used_liquidity) = self.inflight_htlcs.used_liquidity_msat( @@ -204,6 +212,15 @@ impl InFlightHtlcs { } } + /// Adds a known HTLC given the public key of the HTLC source, target, and short channel + /// id. + pub fn add_inflight_htlc(&mut self, source: &NodeId, target: &NodeId, channel_scid: u64, used_msat: u64){ + self.0 + .entry((channel_scid, source < target)) + .and_modify(|used_liquidity_msat| *used_liquidity_msat += used_msat) + .or_insert(used_msat); + } + /// Returns liquidity in msat given the public key of the HTLC source, target, and short channel /// id. pub fn used_liquidity_msat(&self, source: &NodeId, target: &NodeId, channel_scid: u64) -> Option { @@ -262,9 +279,9 @@ impl_writeable_tlv_based!(RouteHop, { }); /// The blinded portion of a [`Path`], if we're routing to a recipient who provided blinded paths in -/// their BOLT12 [`Invoice`]. +/// their [`Bolt12Invoice`]. /// -/// [`Invoice`]: crate::offers::invoice::Invoice +/// [`Bolt12Invoice`]: crate::offers::invoice::Bolt12Invoice #[derive(Clone, Debug, Hash, PartialEq, Eq)] pub struct BlindedTail { /// The hops of the [`BlindedPath`] provided by the recipient. @@ -283,7 +300,7 @@ pub struct BlindedTail { } impl_writeable_tlv_based!(BlindedTail, { - (0, hops, vec_type), + (0, hops, required_vec), (2, blinding_point, required), (4, excess_final_cltv_expiry_delta, required), (6, final_value_msat, required), @@ -337,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, } @@ -349,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() } @@ -427,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. @@ -550,10 +562,10 @@ impl Writeable for PaymentParameters { (1, self.max_total_cltv_expiry_delta, required), (2, self.payee.features(), option), (3, self.max_path_count, required), - (4, *clear_hints, vec_type), + (4, *clear_hints, required_vec), (5, self.max_channel_saturation_power_of_half, required), (6, self.expiry_time, option), - (7, self.previously_failed_channels, vec_type), + (7, self.previously_failed_channels, required_vec), (8, *blinded_hints, optional_vec), (9, self.payee.final_cltv_expiry_delta(), option), }); @@ -568,14 +580,13 @@ impl ReadableArgs for PaymentParameters { (1, max_total_cltv_expiry_delta, (default_value, DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA)), (2, features, (option: ReadableArgs, payee_pubkey.is_some())), (3, max_path_count, (default_value, DEFAULT_MAX_PATH_COUNT)), - (4, route_hints, vec_type), + (4, clear_route_hints, required_vec), (5, max_channel_saturation_power_of_half, (default_value, DEFAULT_MAX_CHANNEL_SATURATION_POW_HALF)), (6, expiry_time, option), - (7, previously_failed_channels, vec_type), + (7, previously_failed_channels, optional_vec), (8, blinded_route_hints, optional_vec), (9, final_cltv_expiry_delta, (default_value, default_final_cltv_expiry_delta)), }); - let clear_route_hints = route_hints.unwrap_or(vec![]); let blinded_route_hints = blinded_route_hints.unwrap_or(vec![]); let payee = if blinded_route_hints.len() != 0 { if clear_route_hints.len() != 0 || payee_pubkey.is_some() { return Err(DecodeError::InvalidValue) } @@ -632,7 +643,7 @@ impl PaymentParameters { /// [`RecipientOnionFields::secret_only`]: crate::ln::channelmanager::RecipientOnionFields::secret_only pub fn for_keysend(payee_pubkey: PublicKey, final_cltv_expiry_delta: u32, allow_mpp: bool) -> Self { Self::from_node_id(payee_pubkey, final_cltv_expiry_delta) - .with_bolt11_features(InvoiceFeatures::for_keysend(allow_mpp)) + .with_bolt11_features(Bolt11InvoiceFeatures::for_keysend(allow_mpp)) .expect("PaymentParameters::from_node_id should always initialize the payee as unblinded") } @@ -672,7 +683,7 @@ impl PaymentParameters { /// [`PaymentParameters::from_bolt12_invoice`]. /// /// This is not exported to bindings users since bindings don't support move semantics - pub fn with_bolt11_features(self, features: InvoiceFeatures) -> Result { + pub fn with_bolt11_features(self, features: Bolt11InvoiceFeatures) -> Result { match self.payee { Payee::Blinded { .. } => Err(()), Payee::Clear { route_hints, node_id, final_cltv_expiry_delta, .. } => @@ -758,7 +769,7 @@ pub enum Payee { /// does not contain any features. /// /// [`for_keysend`]: PaymentParameters::for_keysend - features: Option, + features: Option, /// The minimum CLTV delta at the end of the route. This value must not be zero. final_cltv_expiry_delta: u32, }, @@ -811,11 +822,11 @@ impl Payee { } enum FeaturesRef<'a> { - Bolt11(&'a InvoiceFeatures), + Bolt11(&'a Bolt11InvoiceFeatures), Bolt12(&'a Bolt12InvoiceFeatures), } enum Features { - Bolt11(InvoiceFeatures), + Bolt11(Bolt11InvoiceFeatures), Bolt12(Bolt12InvoiceFeatures), } @@ -826,7 +837,7 @@ impl Features { _ => None, } } - fn bolt11(self) -> Option { + fn bolt11(self) -> Option { match self { Self::Bolt11(f) => Some(f), _ => None, @@ -1322,6 +1333,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) @@ -1367,10 +1386,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 @@ -1380,15 +1401,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 @@ -1633,6 +1648,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, @@ -1707,13 +1728,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 { @@ -2315,6 +2360,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}); @@ -3846,7 +3897,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); @@ -6096,7 +6147,7 @@ mod tests { let params = ProbabilisticScoringFeeParameters::default(); let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &graph, &logger); - let features = super::InvoiceFeatures::empty(); + let features = super::Bolt11InvoiceFeatures::empty(); super::bench_utils::generate_test_routes(&graph, &mut scorer, ¶ms, features, random_init_seed(), 0, 2); } @@ -6672,7 +6723,7 @@ pub(crate) mod bench_utils { use crate::chain::transaction::OutPoint; use crate::sign::{EntropySource, KeysManager}; use crate::ln::channelmanager::{self, ChannelCounterparty, ChannelDetails}; - use crate::ln::features::InvoiceFeatures; + use crate::ln::features::Bolt11InvoiceFeatures; use crate::routing::gossip::NetworkGraph; use crate::util::config::UserConfig; use crate::util::ser::ReadableArgs; @@ -6764,7 +6815,7 @@ pub(crate) mod bench_utils { } pub(crate) fn generate_test_routes(graph: &NetworkGraph<&TestLogger>, scorer: &mut S, - score_params: &S::ScoreParams, features: InvoiceFeatures, mut seed: u64, + score_params: &S::ScoreParams, features: Bolt11InvoiceFeatures, mut seed: u64, starting_amount: u64, route_count: usize, ) -> Vec<(ChannelDetails, PaymentParameters, u64)> { let payer = payer_pubkey(); @@ -6845,7 +6896,7 @@ pub mod benches { use super::*; use crate::sign::{EntropySource, KeysManager}; use crate::ln::channelmanager; - use crate::ln::features::InvoiceFeatures; + use crate::ln::features::Bolt11InvoiceFeatures; use crate::routing::gossip::NetworkGraph; use crate::routing::scoring::{FixedPenaltyScorer, ProbabilisticScorer, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters}; use crate::util::config::UserConfig; @@ -6863,7 +6914,7 @@ pub mod benches { let logger = TestLogger::new(); let network_graph = bench_utils::read_network_graph(&logger).unwrap(); let scorer = FixedPenaltyScorer::with_penalty(0); - generate_routes(bench, &network_graph, scorer, &(), InvoiceFeatures::empty(), 0, + generate_routes(bench, &network_graph, scorer, &(), Bolt11InvoiceFeatures::empty(), 0, "generate_routes_with_zero_penalty_scorer"); } @@ -6881,7 +6932,7 @@ pub mod benches { let network_graph = bench_utils::read_network_graph(&logger).unwrap(); let params = ProbabilisticScoringFeeParameters::default(); let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); - generate_routes(bench, &network_graph, scorer, ¶ms, InvoiceFeatures::empty(), 0, + generate_routes(bench, &network_graph, scorer, ¶ms, Bolt11InvoiceFeatures::empty(), 0, "generate_routes_with_probabilistic_scorer"); } @@ -6907,7 +6958,7 @@ pub mod benches { fn generate_routes( bench: &mut Criterion, graph: &NetworkGraph<&TestLogger>, mut scorer: S, - score_params: &S::ScoreParams, features: InvoiceFeatures, starting_amount: u64, + score_params: &S::ScoreParams, features: Bolt11InvoiceFeatures, starting_amount: u64, bench_name: &'static str, ) { let payer = bench_utils::payer_pubkey();