X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Fscoring.rs;h=4922fad78476f56d62e6c5ebe859ce36323c93bf;hb=fda38196993b22e34ba43f0bb9c94ba842174bf1;hp=72c27fa238b7e5ec22fcd6cfc8025fa7d6c560c7;hpb=79e2af949700281b7333f202a7292e3bf81dc674;p=rust-lightning diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index 72c27fa2..4922fad7 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -43,7 +43,7 @@ //! let scorer = ProbabilisticScorer::new(params, &network_graph, &logger); //! # let random_seed_bytes = [42u8; 32]; //! -//! let route = find_route(&payer, &route_params, &network_graph.read_only(), None, &logger, &scorer, &random_seed_bytes); +//! let route = find_route(&payer, &route_params, &network_graph, None, &logger, &scorer, &random_seed_bytes); //! # } //! ``` //! @@ -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 { @@ -362,10 +380,20 @@ pub struct ProbabilisticScoringParameters { /// Default value: 256 msat pub amount_penalty_multiplier_msat: u64, - /// A list of nodes that won't be considered during path finding. + /// 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 banned_nodes: HashSet, + 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, } /// Accounting for channel liquidity balance uncertainty. @@ -460,17 +488,27 @@ impl>, L: Deref, T: Time> ProbabilisticScorerU /// 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.banned_nodes.insert(*node_id); + 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.banned_nodes.remove(node_id); + 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); } - /// Clears the list of nodes that are avoided during path finding. - pub fn clear_banned(&mut self) { - self.params.banned_nodes = HashSet::new(); + /// 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(); } } @@ -482,7 +520,8 @@ impl ProbabilisticScoringParameters { liquidity_penalty_multiplier_msat: 0, liquidity_offset_half_life: Duration::from_secs(3600), amount_penalty_multiplier_msat: 0, - banned_nodes: HashSet::new(), + manual_node_penalties: HashMap::new(), + anti_probing_penalty_msat: 0, } } @@ -490,7 +529,7 @@ impl ProbabilisticScoringParameters { /// they will be avoided during path finding. pub fn add_banned_from_list(&mut self, node_ids: Vec) { for id in node_ids { - self.banned_nodes.insert(id); + self.manual_node_penalties.insert(id, u64::max_value()); } } } @@ -502,7 +541,8 @@ impl Default for ProbabilisticScoringParameters { liquidity_penalty_multiplier_msat: 40_000, liquidity_offset_half_life: Duration::from_secs(3600), amount_penalty_multiplier_msat: 256, - banned_nodes: HashSet::new(), + manual_node_penalties: HashMap::new(), + anti_probing_penalty_msat: 250, } } } @@ -703,16 +743,25 @@ impl>, L: Deref, T: Time> Score for Probabilis fn channel_penalty_msat( &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage ) -> u64 { - if self.params.banned_nodes.contains(source) || self.params.banned_nodes.contains(target) { - return u64::max_value(); + if let Some(penalty) = self.params.manual_node_penalties.get(target) { + return *penalty; } - 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; - }; + 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; @@ -724,6 +773,7 @@ impl>, L: Deref, T: Time> Score for Probabilis .unwrap_or(&ChannelLiquidity::new()) .as_directed(source, target, capacity_msat, liquidity_offset_half_life) .penalty_msat(amount_msat, &self.params) + .saturating_add(anti_probing_penalty_msat) } fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) { @@ -791,6 +841,14 @@ impl>, L: Deref, T: Time> Score for Probabilis } } } + + 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 { @@ -1157,10 +1215,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, }) } } @@ -1547,7 +1617,7 @@ 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 }; @@ -1560,7 +1630,7 @@ mod tests { 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 }; @@ -1597,7 +1667,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 }; @@ -1621,7 +1691,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); @@ -1651,7 +1721,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 }; @@ -1685,7 +1755,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 }; @@ -1719,7 +1789,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); @@ -1750,7 +1820,7 @@ 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_000) }, }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0); let usage = ChannelUsage { amount_msat: 1_024, ..usage }; @@ -1828,7 +1898,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); @@ -1859,7 +1929,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); @@ -1903,7 +1973,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) }, }; scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::>(), 42); @@ -1939,7 +2009,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) }, }; scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::>(), 42); @@ -1976,47 +2046,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); } @@ -2030,7 +2100,7 @@ mod tests { 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 { @@ -2041,7 +2111,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); @@ -2056,7 +2127,7 @@ mod tests { 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 { @@ -2108,7 +2179,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()); @@ -2139,4 +2210,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); + } }