X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Fscoring.rs;h=458a24d9f1bbd7ff83434837d6cd8c83d05a19af;hb=b0e8b739b73cc25f3e1ab00695a14d972162a140;hp=54400624dce63a30ec0e506bfc1c87800a6bac4a;hpb=0017bc88a84fa7f253bede430fbb147f6e60c50b;p=rust-lightning diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index 54400624..458a24d9 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -28,7 +28,7 @@ //! # impl Logger for FakeLogger { //! # fn log(&self, record: &Record) { unimplemented!() } //! # } -//! # fn find_scored_route(payer: PublicKey, route_params: RouteParameters, network_graph: NetworkGraph) { +//! # fn find_scored_route(payer: PublicKey, route_params: RouteParameters, network_graph: NetworkGraph<&FakeLogger>) { //! # let logger = FakeLogger {}; //! # //! // Use the default channel penalties. @@ -102,6 +102,12 @@ pub trait Score $(: $supertrait)* { /// Handles updating channel penalties after successfully routing along a path. fn payment_path_successful(&mut self, path: &[&RouteHop]); + + /// Handles updating channel penalties after a probe over the given path failed. + fn probe_failed(&mut self, path: &[&RouteHop], short_channel_id: u64); + + /// Handles updating channel penalties after a probe over the given path succeeded. + fn probe_successful(&mut self, path: &[&RouteHop]); } impl $(+ $supertrait)*> Score for T { @@ -118,6 +124,14 @@ impl $(+ $supertrait)*> Score for T { fn payment_path_successful(&mut self, path: &[&RouteHop]) { self.deref_mut().payment_path_successful(path) } + + fn probe_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) { + self.deref_mut().probe_failed(path, short_channel_id) + } + + fn probe_successful(&mut self, path: &[&RouteHop]) { + self.deref_mut().probe_successful(path) + } } } } @@ -241,6 +255,10 @@ impl Score for FixedPenaltyScorer { fn payment_path_failed(&mut self, _path: &[&RouteHop], _short_channel_id: u64) {} fn payment_path_successful(&mut self, _path: &[&RouteHop]) {} + + fn probe_failed(&mut self, _path: &[&RouteHop], _short_channel_id: u64) {} + + fn probe_successful(&mut self, _path: &[&RouteHop]) {} } impl Writeable for FixedPenaltyScorer { @@ -293,7 +311,8 @@ pub type ProbabilisticScorer = ProbabilisticScorerUsingTime::, L: Deref, T: Time> where L::Target: Logger { +pub struct ProbabilisticScorerUsingTime>, L: Deref, T: Time> +where L::Target: Logger { params: ProbabilisticScoringParameters, network_graph: G, logger: L, @@ -305,7 +324,7 @@ pub struct ProbabilisticScorerUsingTime, L: Dere /// /// Used to configure base, liquidity, and amount penalties, the sum of which comprises the channel /// penalty (i.e., the amount in msats willing to be paid to avoid routing through the channel). -#[derive(Clone, Copy)] +#[derive(Clone)] pub struct ProbabilisticScoringParameters { /// A fixed penalty in msats to apply to each channel. /// @@ -360,6 +379,40 @@ pub struct ProbabilisticScoringParameters { /// /// Default value: 256 msat pub amount_penalty_multiplier_msat: u64, + + /// Manual penalties used for the given nodes. Allows to set a particular penalty for a given + /// node. Note that a manual penalty of `u64::max_value()` means the node would not ever be + /// considered during path finding. + /// + /// (C-not exported) + pub manual_node_penalties: HashMap, + + /// This penalty is applied when `htlc_maximum_msat` is equal to or larger than half of the + /// channel's capacity, which makes us prefer nodes with a smaller `htlc_maximum_msat`. We + /// treat such nodes preferentially as this makes balance discovery attacks harder to execute, + /// thereby creating an incentive to restrict `htlc_maximum_msat` and improve privacy. + /// + /// Default value: 250 msat + pub anti_probing_penalty_msat: u64, + + /// This penalty is applied when the amount we're attempting to send over a channel exceeds our + /// current estimate of the channel's available liquidity. + /// + /// Note that in this case all other penalties, including the + /// [`liquidity_penalty_multiplier_msat`] and [`amount_penalty_multiplier_msat`]-based + /// penalties, as well as the [`base_penalty_msat`] and the [`anti_probing_penalty_msat`], if + /// applicable, are still included in the overall penalty. + /// + /// If you wish to avoid creating paths with such channels entirely, setting this to a value of + /// `u64::max_value()` will guarantee that. + /// + /// Default value: 1_0000_0000_000 msat (1 Bitcoin) + /// + /// [`liquidity_penalty_multiplier_msat`]: Self::liquidity_penalty_multiplier_msat + /// [`amount_penalty_multiplier_msat`]: Self::amount_penalty_multiplier_msat + /// [`base_penalty_msat`]: Self::base_penalty_msat + /// [`anti_probing_penalty_msat`]: Self::anti_probing_penalty_msat + pub considered_impossible_penalty_msat: u64, } /// Accounting for channel liquidity balance uncertainty. @@ -389,7 +442,7 @@ struct DirectedChannelLiquidity, T: Time, U: Deref, L: Deref, T: Time> ProbabilisticScorerUsingTime where L::Target: Logger { +impl>, L: Deref, T: Time> ProbabilisticScorerUsingTime where L::Target: Logger { /// Creates a new scorer using the given scoring parameters for sending payments from a node /// through a network graph. pub fn new(params: ProbabilisticScoringParameters, network_graph: G, logger: L) -> Self { @@ -433,6 +486,49 @@ impl, L: Deref, T: Time> ProbabilisticScorerUsin } } } + + /// Query the estimated minimum and maximum liquidity available for sending a payment over the + /// channel with `scid` towards the given `target` node. + pub fn estimated_channel_liquidity_range(&self, scid: u64, target: &NodeId) -> Option<(u64, u64)> { + let graph = self.network_graph.read_only(); + + if let Some(chan) = graph.channels().get(&scid) { + if let Some(liq) = self.channel_liquidities.get(&scid) { + if let Some((directed_info, source)) = chan.as_directed_to(target) { + let amt = directed_info.effective_capacity().as_msat(); + let dir_liq = liq.as_directed(source, target, amt, self.params.liquidity_offset_half_life); + return Some((dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat())); + } + } + } + None + } + + /// Marks the node with the given `node_id` as banned, i.e., + /// it will be avoided during path finding. + pub fn add_banned(&mut self, node_id: &NodeId) { + self.params.manual_node_penalties.insert(*node_id, u64::max_value()); + } + + /// Removes the node with the given `node_id` from the list of nodes to avoid. + pub fn remove_banned(&mut self, node_id: &NodeId) { + self.params.manual_node_penalties.remove(node_id); + } + + /// Sets a manual penalty for the given node. + pub fn set_manual_penalty(&mut self, node_id: &NodeId, penalty: u64) { + self.params.manual_node_penalties.insert(*node_id, penalty); + } + + /// Removes the node with the given `node_id` from the list of manual penalties. + pub fn remove_manual_penalty(&mut self, node_id: &NodeId) { + self.params.manual_node_penalties.remove(node_id); + } + + /// Clears the list of manual penalties that are applied during path finding. + pub fn clear_manual_penalties(&mut self) { + self.params.manual_node_penalties = HashMap::new(); + } } impl ProbabilisticScoringParameters { @@ -443,6 +539,17 @@ impl ProbabilisticScoringParameters { liquidity_penalty_multiplier_msat: 0, liquidity_offset_half_life: Duration::from_secs(3600), amount_penalty_multiplier_msat: 0, + manual_node_penalties: HashMap::new(), + anti_probing_penalty_msat: 0, + considered_impossible_penalty_msat: 0, + } + } + + /// Marks all nodes in the given list as banned, i.e., + /// they will be avoided during path finding. + pub fn add_banned_from_list(&mut self, node_ids: Vec) { + for id in node_ids { + self.manual_node_penalties.insert(id, u64::max_value()); } } } @@ -454,6 +561,9 @@ impl Default for ProbabilisticScoringParameters { liquidity_penalty_multiplier_msat: 40_000, liquidity_offset_half_life: Duration::from_secs(3600), amount_penalty_multiplier_msat: 256, + manual_node_penalties: HashMap::new(), + anti_probing_penalty_msat: 250, + considered_impossible_penalty_msat: 1_0000_0000_000, } } } @@ -525,23 +635,18 @@ const AMOUNT_PENALTY_DIVISOR: u64 = 1 << 20; impl, T: Time, U: Deref> DirectedChannelLiquidity { /// Returns a penalty for routing the given HTLC `amount_msat` through the channel in this /// direction. - fn penalty_msat(&self, amount_msat: u64, params: ProbabilisticScoringParameters) -> u64 { + fn penalty_msat(&self, amount_msat: u64, params: &ProbabilisticScoringParameters) -> u64 { let max_liquidity_msat = self.max_liquidity_msat(); let min_liquidity_msat = core::cmp::min(self.min_liquidity_msat(), max_liquidity_msat); if amount_msat <= min_liquidity_msat { 0 } else if amount_msat >= max_liquidity_msat { - if amount_msat > max_liquidity_msat { - u64::max_value() - } else if max_liquidity_msat != self.capacity_msat { - // Avoid using the failed channel on retry. - u64::max_value() - } else { - // Equivalent to hitting the else clause below with the amount equal to the - // effective capacity and without any certainty on the liquidity upper bound. - let negative_log10_times_2048 = NEGATIVE_LOG10_UPPER_BOUND * 2048; - self.combined_penalty_msat(amount_msat, negative_log10_times_2048, params) - } + // Equivalent to hitting the else clause below with the amount equal to the effective + // capacity and without any certainty on the liquidity upper bound, plus the + // impossibility penalty. + let negative_log10_times_2048 = NEGATIVE_LOG10_UPPER_BOUND * 2048; + self.combined_penalty_msat(amount_msat, negative_log10_times_2048, params) + .saturating_add(params.considered_impossible_penalty_msat) } else { let numerator = (max_liquidity_msat - amount_msat).saturating_add(1); let denominator = (max_liquidity_msat - min_liquidity_msat).saturating_add(1); @@ -562,7 +667,7 @@ impl, T: Time, U: Deref> DirectedChannelLiqui #[inline(always)] fn combined_penalty_msat( &self, amount_msat: u64, negative_log10_times_2048: u64, - params: ProbabilisticScoringParameters + params: &ProbabilisticScoringParameters ) -> u64 { let liquidity_penalty_msat = { // Upper bound the liquidity penalty to ensure some channel is selected. @@ -650,16 +755,29 @@ impl, T: Time, U: DerefMut> DirectedChanne } } -impl, L: Deref, T: Time> Score for ProbabilisticScorerUsingTime where L::Target: Logger { +impl>, L: Deref, T: Time> Score for ProbabilisticScorerUsingTime where L::Target: Logger { fn channel_penalty_msat( &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage ) -> u64 { - if let EffectiveCapacity::ExactLiquidity { liquidity_msat } = usage.effective_capacity { - if usage.amount_msat > liquidity_msat { - return u64::max_value(); - } else { - return self.params.base_penalty_msat; - }; + if let Some(penalty) = self.params.manual_node_penalties.get(target) { + return *penalty; + } + + let mut anti_probing_penalty_msat = 0; + match usage.effective_capacity { + EffectiveCapacity::ExactLiquidity { liquidity_msat } => { + if usage.amount_msat > liquidity_msat { + return u64::max_value(); + } else { + return self.params.base_penalty_msat; + } + }, + EffectiveCapacity::Total { capacity_msat, htlc_maximum_msat: Some(htlc_maximum_msat) } => { + if htlc_maximum_msat >= capacity_msat/2 { + anti_probing_penalty_msat = self.params.anti_probing_penalty_msat; + } + }, + _ => {}, } let liquidity_offset_half_life = self.params.liquidity_offset_half_life; @@ -670,7 +788,8 @@ impl, L: Deref, T: Time> Score for Probabilistic .get(&short_channel_id) .unwrap_or(&ChannelLiquidity::new()) .as_directed(source, target, capacity_msat, liquidity_offset_half_life) - .penalty_msat(amount_msat, self.params) + .penalty_msat(amount_msat, &self.params) + .saturating_add(anti_probing_penalty_msat) } fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) { @@ -738,6 +857,14 @@ impl, L: Deref, T: Time> Score for Probabilistic } } } + + fn probe_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) { + self.payment_path_failed(path, short_channel_id) + } + + fn probe_successful(&mut self, path: &[&RouteHop]) { + self.payment_path_failed(path, u64::max_value()) + } } mod approx { @@ -1050,17 +1177,17 @@ mod approx { } } -impl, L: Deref, T: Time> Writeable for ProbabilisticScorerUsingTime where L::Target: Logger { +impl>, L: Deref, T: Time> Writeable for ProbabilisticScorerUsingTime where L::Target: Logger { #[inline] fn write(&self, w: &mut W) -> Result<(), io::Error> { write_tlv_fields!(w, { - (0, self.channel_liquidities, required) + (0, self.channel_liquidities, required), }); Ok(()) } } -impl, L: Deref, T: Time> +impl>, L: Deref, T: Time> ReadableArgs<(ProbabilisticScoringParameters, G, L)> for ProbabilisticScorerUsingTime where L::Target: Logger { #[inline] fn read( @@ -1069,7 +1196,7 @@ ReadableArgs<(ProbabilisticScoringParameters, G, L)> for ProbabilisticScorerUsin let (params, network_graph, logger) = args; let mut channel_liquidities = HashMap::new(); read_tlv_fields!(r, { - (0, channel_liquidities, required) + (0, channel_liquidities, required), }); Ok(Self { params, @@ -1104,10 +1231,22 @@ impl Readable for ChannelLiquidity { (2, max_liquidity_offset_msat, required), (4, duration_since_epoch, required), }); + // On rust prior to 1.60 `Instant::duration_since` will panic if time goes backwards. + // We write `last_updated` as wallclock time even though its ultimately an `Instant` (which + // is a time from a monotonic clock usually represented as an offset against boot time). + // Thus, we have to construct an `Instant` by subtracting the difference in wallclock time + // from the one that was written. However, because `Instant` can panic if we construct one + // in the future, we must handle wallclock time jumping backwards, which we do by simply + // using `Instant::now()` in that case. + let wall_clock_now = T::duration_since_epoch(); + let now = T::now(); + let last_updated = if wall_clock_now > duration_since_epoch { + now - (wall_clock_now - duration_since_epoch) + } else { now }; Ok(Self { min_liquidity_offset_msat, max_liquidity_offset_msat, - last_updated: T::now() - (T::duration_since_epoch() - duration_since_epoch), + last_updated, }) } } @@ -1119,7 +1258,7 @@ mod tests { use util::time::tests::SinceEpoch; use ln::features::{ChannelFeatures, NodeFeatures}; - use ln::msgs::{ChannelAnnouncement, ChannelUpdate, OptionalField, UnsignedChannelAnnouncement, UnsignedChannelUpdate}; + use ln::msgs::{ChannelAnnouncement, ChannelUpdate, UnsignedChannelAnnouncement, UnsignedChannelUpdate}; use routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId}; use routing::router::RouteHop; use routing::scoring::{ChannelUsage, Score}; @@ -1163,7 +1302,7 @@ mod tests { // `ProbabilisticScorer` tests /// A probabilistic scorer for testing with time that can be manually advanced. - type ProbabilisticScorer<'a> = ProbabilisticScorerUsingTime::<&'a NetworkGraph, &'a TestLogger, SinceEpoch>; + type ProbabilisticScorer<'a> = ProbabilisticScorerUsingTime::<&'a NetworkGraph<&'a TestLogger>, &'a TestLogger, SinceEpoch>; fn sender_privkey() -> SecretKey { SecretKey::from_slice(&[41; 32]).unwrap() @@ -1191,9 +1330,9 @@ mod tests { NodeId::from_pubkey(&recipient_pubkey()) } - fn network_graph() -> NetworkGraph { + fn network_graph(logger: &TestLogger) -> NetworkGraph<&TestLogger> { let genesis_hash = genesis_block(Network::Testnet).header.block_hash(); - let mut network_graph = NetworkGraph::new(genesis_hash); + let mut network_graph = NetworkGraph::new(genesis_hash, logger); add_channel(&mut network_graph, 42, source_privkey(), target_privkey()); add_channel(&mut network_graph, 43, target_privkey(), recipient_privkey()); @@ -1201,7 +1340,7 @@ mod tests { } fn add_channel( - network_graph: &mut NetworkGraph, short_channel_id: u64, node_1_key: SecretKey, + network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_1_key: SecretKey, node_2_key: SecretKey ) { let genesis_hash = genesis_block(Network::Testnet).header.block_hash(); @@ -1228,13 +1367,14 @@ mod tests { }; let chain_source: Option<&::util::test_utils::TestChainSource> = None; network_graph.update_channel_from_announcement( - &signed_announcement, &chain_source, &secp_ctx).unwrap(); + &signed_announcement, &chain_source).unwrap(); update_channel(network_graph, short_channel_id, node_1_key, 0); update_channel(network_graph, short_channel_id, node_2_key, 1); } fn update_channel( - network_graph: &mut NetworkGraph, short_channel_id: u64, node_key: SecretKey, flags: u8 + network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_key: SecretKey, + flags: u8 ) { let genesis_hash = genesis_block(Network::Testnet).header.block_hash(); let secp_ctx = Secp256k1::new(); @@ -1245,7 +1385,7 @@ mod tests { flags, cltv_expiry_delta: 18, htlc_minimum_msat: 0, - htlc_maximum_msat: OptionalField::Present(1_000), + htlc_maximum_msat: 1_000, fee_base_msat: 1, fee_proportional_millionths: 0, excess_data: Vec::new(), @@ -1255,7 +1395,7 @@ mod tests { signature: secp_ctx.sign_ecdsa(&msghash, &node_key), contents: unsigned_update, }; - network_graph.update_channel(&signed_update, &secp_ctx).unwrap(); + network_graph.update_channel(&signed_update).unwrap(); } fn payment_path_for_amount(amount_msat: u64) -> Vec { @@ -1291,7 +1431,7 @@ mod tests { fn liquidity_bounds_directed_from_lowest_node_id() { let logger = TestLogger::new(); let last_updated = SinceEpoch::now(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let params = ProbabilisticScoringParameters::default(); let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger) .with_channel(42, @@ -1366,7 +1506,7 @@ mod tests { fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() { let logger = TestLogger::new(); let last_updated = SinceEpoch::now(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let params = ProbabilisticScoringParameters::default(); let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger) .with_channel(42, @@ -1424,7 +1564,7 @@ mod tests { fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() { let logger = TestLogger::new(); let last_updated = SinceEpoch::now(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let params = ProbabilisticScoringParameters::default(); let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger) .with_channel(42, @@ -1481,7 +1621,7 @@ mod tests { #[test] fn increased_penalty_nearing_liquidity_upper_bound() { let logger = TestLogger::new(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let params = ProbabilisticScoringParameters { liquidity_penalty_multiplier_msat: 1_000, ..ProbabilisticScoringParameters::zero_penalty() @@ -1493,20 +1633,20 @@ mod tests { let usage = ChannelUsage { amount_msat: 1_024, inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000 }, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(1_000) }, }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0); let usage = ChannelUsage { amount_msat: 10_240, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0); let usage = ChannelUsage { amount_msat: 102_400, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 47); - let usage = ChannelUsage { amount_msat: 1_024_000, ..usage }; + let usage = ChannelUsage { amount_msat: 1_023_999, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000); let usage = ChannelUsage { amount_msat: 128, inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024 }, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_000) }, }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 58); let usage = ChannelUsage { amount_msat: 256, ..usage }; @@ -1527,9 +1667,10 @@ mod tests { fn constant_penalty_outside_liquidity_bounds() { let logger = TestLogger::new(); let last_updated = SinceEpoch::now(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let params = ProbabilisticScoringParameters { liquidity_penalty_multiplier_msat: 1_000, + considered_impossible_penalty_msat: u64::max_value(), ..ProbabilisticScoringParameters::zero_penalty() }; let scorer = ProbabilisticScorer::new(params, &network_graph, &logger) @@ -1543,7 +1684,7 @@ mod tests { let usage = ChannelUsage { amount_msat: 39, inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::Total { capacity_msat: 100 }, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 100, htlc_maximum_msat: Some(1_000) }, }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0); let usage = ChannelUsage { amount_msat: 50, ..usage }; @@ -1556,7 +1697,7 @@ mod tests { #[test] fn does_not_further_penalize_own_channel() { let logger = TestLogger::new(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let params = ProbabilisticScoringParameters { liquidity_penalty_multiplier_msat: 1_000, ..ProbabilisticScoringParameters::zero_penalty() @@ -1567,7 +1708,7 @@ mod tests { let usage = ChannelUsage { amount_msat: 500, inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000 }, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) }, }; let failed_path = payment_path_for_amount(500); let successful_path = payment_path_for_amount(200); @@ -1584,7 +1725,7 @@ mod tests { #[test] fn sets_liquidity_lower_bound_on_downstream_failure() { let logger = TestLogger::new(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let params = ProbabilisticScoringParameters { liquidity_penalty_multiplier_msat: 1_000, ..ProbabilisticScoringParameters::zero_penalty() @@ -1597,7 +1738,7 @@ mod tests { let usage = ChannelUsage { amount_msat: 250, inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000 }, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) }, }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 128); let usage = ChannelUsage { amount_msat: 500, ..usage }; @@ -1618,9 +1759,10 @@ mod tests { #[test] fn sets_liquidity_upper_bound_on_failure() { let logger = TestLogger::new(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let params = ProbabilisticScoringParameters { liquidity_penalty_multiplier_msat: 1_000, + considered_impossible_penalty_msat: u64::max_value(), ..ProbabilisticScoringParameters::zero_penalty() }; let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger); @@ -1631,7 +1773,7 @@ mod tests { let usage = ChannelUsage { amount_msat: 250, inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000 }, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) }, }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 128); let usage = ChannelUsage { amount_msat: 500, ..usage }; @@ -1652,7 +1794,7 @@ mod tests { #[test] fn reduces_liquidity_upper_bound_along_path_on_success() { let logger = TestLogger::new(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let params = ProbabilisticScoringParameters { liquidity_penalty_multiplier_msat: 1_000, ..ProbabilisticScoringParameters::zero_penalty() @@ -1665,7 +1807,7 @@ mod tests { let usage = ChannelUsage { amount_msat: 250, inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000 }, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) }, }; let path = payment_path_for_amount(500); @@ -1683,10 +1825,11 @@ mod tests { #[test] fn decays_liquidity_bounds_over_time() { let logger = TestLogger::new(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let params = ProbabilisticScoringParameters { liquidity_penalty_multiplier_msat: 1_000, liquidity_offset_half_life: Duration::from_secs(10), + considered_impossible_penalty_msat: u64::max_value(), ..ProbabilisticScoringParameters::zero_penalty() }; let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger); @@ -1696,10 +1839,10 @@ mod tests { let usage = ChannelUsage { amount_msat: 0, inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024 }, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_024) }, }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0); - let usage = ChannelUsage { amount_msat: 1_024, ..usage }; + let usage = ChannelUsage { amount_msat: 1_023, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000); scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::>(), 42); @@ -1743,26 +1886,26 @@ mod tests { let usage = ChannelUsage { amount_msat: 1_023, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000); let usage = ChannelUsage { amount_msat: 1_024, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000); + assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value()); // Fully decay liquidity upper bound. SinceEpoch::advance(Duration::from_secs(10)); let usage = ChannelUsage { amount_msat: 0, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0); let usage = ChannelUsage { amount_msat: 1_024, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000); + assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value()); SinceEpoch::advance(Duration::from_secs(10)); let usage = ChannelUsage { amount_msat: 0, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0); let usage = ChannelUsage { amount_msat: 1_024, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000); + assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value()); } #[test] fn decays_liquidity_bounds_without_shift_overflow() { let logger = TestLogger::new(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let params = ProbabilisticScoringParameters { liquidity_penalty_multiplier_msat: 1_000, liquidity_offset_half_life: Duration::from_secs(10), @@ -1774,7 +1917,7 @@ mod tests { let usage = ChannelUsage { amount_msat: 256, inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024 }, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_000) }, }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125); @@ -1793,7 +1936,7 @@ mod tests { #[test] fn restricts_liquidity_bounds_after_decay() { let logger = TestLogger::new(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let params = ProbabilisticScoringParameters { liquidity_penalty_multiplier_msat: 1_000, liquidity_offset_half_life: Duration::from_secs(10), @@ -1805,7 +1948,7 @@ mod tests { let usage = ChannelUsage { amount_msat: 512, inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024 }, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_000) }, }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300); @@ -1837,19 +1980,20 @@ mod tests { #[test] fn restores_persisted_liquidity_bounds() { let logger = TestLogger::new(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let params = ProbabilisticScoringParameters { liquidity_penalty_multiplier_msat: 1_000, liquidity_offset_half_life: Duration::from_secs(10), + considered_impossible_penalty_msat: u64::max_value(), ..ProbabilisticScoringParameters::zero_penalty() }; - let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger); + let mut scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger); let source = source_node_id(); let target = target_node_id(); let usage = ChannelUsage { amount_msat: 500, inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000 }, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) }, }; scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::>(), 42); @@ -1873,19 +2017,20 @@ mod tests { #[test] fn decays_persisted_liquidity_bounds() { let logger = TestLogger::new(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let params = ProbabilisticScoringParameters { liquidity_penalty_multiplier_msat: 1_000, liquidity_offset_half_life: Duration::from_secs(10), + considered_impossible_penalty_msat: u64::max_value(), ..ProbabilisticScoringParameters::zero_penalty() }; - let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger); + let mut scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger); let source = source_node_id(); let target = target_node_id(); let usage = ChannelUsage { amount_msat: 500, inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000 }, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) }, }; scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::>(), 42); @@ -1913,7 +2058,7 @@ mod tests { // Shows the scores of "realistic" sends of 100k sats over channels of 1-10m sats (with a // 50k sat reserve). let logger = TestLogger::new(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let params = ProbabilisticScoringParameters::default(); let scorer = ProbabilisticScorer::new(params, &network_graph, &logger); let source = source_node_id(); @@ -1922,47 +2067,47 @@ mod tests { let usage = ChannelUsage { amount_msat: 100_000_000, inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::Total { capacity_msat: 950_000_000 }, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 950_000_000, htlc_maximum_msat: Some(1_000) }, }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 3613); let usage = ChannelUsage { - effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_950_000_000 }, ..usage + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1977); let usage = ChannelUsage { - effective_capacity: EffectiveCapacity::Total { capacity_msat: 2_950_000_000 }, ..usage + effective_capacity: EffectiveCapacity::Total { capacity_msat: 2_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1474); let usage = ChannelUsage { - effective_capacity: EffectiveCapacity::Total { capacity_msat: 3_950_000_000 }, ..usage + effective_capacity: EffectiveCapacity::Total { capacity_msat: 3_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1223); let usage = ChannelUsage { - effective_capacity: EffectiveCapacity::Total { capacity_msat: 4_950_000_000 }, ..usage + effective_capacity: EffectiveCapacity::Total { capacity_msat: 4_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 877); let usage = ChannelUsage { - effective_capacity: EffectiveCapacity::Total { capacity_msat: 5_950_000_000 }, ..usage + effective_capacity: EffectiveCapacity::Total { capacity_msat: 5_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 845); let usage = ChannelUsage { - effective_capacity: EffectiveCapacity::Total { capacity_msat: 6_950_000_000 }, ..usage + effective_capacity: EffectiveCapacity::Total { capacity_msat: 6_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500); let usage = ChannelUsage { - effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_450_000_000 }, ..usage + effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_450_000_000, htlc_maximum_msat: Some(1_000) }, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500); let usage = ChannelUsage { - effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_950_000_000 }, ..usage + effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500); let usage = ChannelUsage { - effective_capacity: EffectiveCapacity::Total { capacity_msat: 8_950_000_000 }, ..usage + effective_capacity: EffectiveCapacity::Total { capacity_msat: 8_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500); let usage = ChannelUsage { - effective_capacity: EffectiveCapacity::Total { capacity_msat: 9_950_000_000 }, ..usage + effective_capacity: EffectiveCapacity::Total { capacity_msat: 9_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500); } @@ -1970,13 +2115,13 @@ mod tests { #[test] fn adds_base_penalty_to_liquidity_penalty() { let logger = TestLogger::new(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let source = source_node_id(); let target = target_node_id(); let usage = ChannelUsage { amount_msat: 128, inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024 }, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_000) }, }; let params = ProbabilisticScoringParameters { @@ -1987,7 +2132,8 @@ mod tests { assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 58); let params = ProbabilisticScoringParameters { - base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000, ..Default::default() + base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000, + anti_probing_penalty_msat: 0, ..Default::default() }; let scorer = ProbabilisticScorer::new(params, &network_graph, &logger); assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 558); @@ -1996,13 +2142,13 @@ mod tests { #[test] fn adds_amount_penalty_to_liquidity_penalty() { let logger = TestLogger::new(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let source = source_node_id(); let target = target_node_id(); let usage = ChannelUsage { amount_msat: 512_000, inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000 }, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(1_000) }, }; let params = ProbabilisticScoringParameters { @@ -2025,7 +2171,7 @@ mod tests { #[test] fn calculates_log10_without_overflowing_u64_max_value() { let logger = TestLogger::new(); - let network_graph = network_graph(); + let network_graph = network_graph(&logger); let source = source_node_id(); let target = target_node_id(); let usage = ChannelUsage { @@ -2044,9 +2190,12 @@ mod tests { #[test] fn accounts_for_inflight_htlc_usage() { - let network_graph = network_graph(); let logger = TestLogger::new(); - let params = ProbabilisticScoringParameters::default(); + let network_graph = network_graph(&logger); + let params = ProbabilisticScoringParameters { + considered_impossible_penalty_msat: u64::max_value(), + ..ProbabilisticScoringParameters::zero_penalty() + }; let scorer = ProbabilisticScorer::new(params, &network_graph, &logger); let source = source_node_id(); let target = target_node_id(); @@ -2054,7 +2203,7 @@ mod tests { let usage = ChannelUsage { amount_msat: 750, inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000 }, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) }, }; assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value()); @@ -2064,10 +2213,10 @@ mod tests { #[test] fn removes_uncertainity_when_exact_liquidity_known() { - let network_graph = network_graph(); let logger = TestLogger::new(); + let network_graph = network_graph(&logger); let params = ProbabilisticScoringParameters::default(); - let scorer = ProbabilisticScorer::new(params, &network_graph, &logger); + let scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger); let source = source_node_id(); let target = target_node_id(); @@ -2085,4 +2234,49 @@ mod tests { let usage = ChannelUsage { amount_msat: 1_001, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value()); } + + #[test] + fn adds_anti_probing_penalty() { + let logger = TestLogger::new(); + let network_graph = network_graph(&logger); + let source = source_node_id(); + let target = target_node_id(); + let params = ProbabilisticScoringParameters { + anti_probing_penalty_msat: 500, + ..ProbabilisticScoringParameters::zero_penalty() + }; + let scorer = ProbabilisticScorer::new(params, &network_graph, &logger); + + // Check we receive no penalty for a low htlc_maximum_msat. + let usage = ChannelUsage { + amount_msat: 512_000, + inflight_htlc_msat: 0, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(1_000) }, + }; + assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0); + + // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity. + let usage = ChannelUsage { + amount_msat: 512_000, + inflight_htlc_msat: 0, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(1_024_000) }, + }; + assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500); + + // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity/2. + let usage = ChannelUsage { + amount_msat: 512_000, + inflight_htlc_msat: 0, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(512_000) }, + }; + assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500); + + // Check we receive no anti-probing penalty for htlc_maximum_msat == channel_capacity/2 - 1. + let usage = ChannelUsage { + amount_msat: 512_000, + inflight_htlc_msat: 0, + effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(511_999) }, + }; + assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0); + } }