X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Fscoring.rs;h=335a6f1a23411a6ab5c4ccad2fd2a478857bc38b;hb=0357f6a8c9ce3192fb457f4082b2becde7bc58c5;hp=459303f7d87f0c988293a2360798665570607955;hpb=9596cc71103168d041adcdd4a3c247595c1d4c34;p=rust-lightning diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index 459303f7..335a6f1a 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -230,6 +230,7 @@ impl ReadableArgs for FixedPenaltyScorer { } } +#[cfg(not(feature = "no-std"))] /// [`Score`] implementation that provides reasonable default behavior. /// /// Used to apply a fixed penalty to each channel, thus avoiding long paths when shorter paths with @@ -247,12 +248,22 @@ impl ReadableArgs for FixedPenaltyScorer { since = "0.0.105", note = "ProbabilisticScorer should be used instead of Scorer.", )] -pub type Scorer = ScorerUsingTime::; - -#[cfg(not(feature = "no-std"))] -type ConfiguredTime = std::time::Instant; +pub type Scorer = ScorerUsingTime::; #[cfg(feature = "no-std")] -type ConfiguredTime = time::Eternity; +/// [`Score`] implementation that provides reasonable default behavior. +/// +/// Used to apply a fixed penalty to each channel, thus avoiding long paths when shorter paths with +/// slightly higher fees are available. Will further penalize channels that fail to relay payments. +/// +/// See [module-level documentation] for usage and [`ScoringParameters`] for customization. +/// +/// # Note +/// +/// Mixing the `no-std` feature between serialization and deserialization results in undefined +/// behavior. +/// +/// [module-level documentation]: crate::routing::scoring +pub type Scorer = ScorerUsingTime::; // Note that ideally we'd hide ScorerUsingTime from public view by sealing it as well, but rustdoc // doesn't handle this well - instead exposing a `Scorer` which has no trait implementation(s) or @@ -481,6 +492,7 @@ impl Readable for ChannelFailure { } } +#[cfg(not(feature = "no-std"))] /// [`Score`] implementation using channel success probability distributions. /// /// Based on *Optimally Reliable & Cheap Payment Flows on the Lightning Network* by Rene Pickhardt @@ -503,7 +515,31 @@ impl Readable for ChannelFailure { /// behavior. /// /// [1]: https://arxiv.org/abs/2107.05322 -pub type ProbabilisticScorer = ProbabilisticScorerUsingTime::; +pub type ProbabilisticScorer = ProbabilisticScorerUsingTime::; +#[cfg(feature = "no-std")] +/// [`Score`] implementation using channel success probability distributions. +/// +/// Based on *Optimally Reliable & Cheap Payment Flows on the Lightning Network* by Rene Pickhardt +/// and Stefan Richter [[1]]. Given the uncertainty of channel liquidity balances, probability +/// distributions are defined based on knowledge learned from successful and unsuccessful attempts. +/// Then the negative `log10` of the success probability is used to determine the cost of routing a +/// specific HTLC amount through a channel. +/// +/// Knowledge about channel liquidity balances takes the form of upper and lower bounds on the +/// possible liquidity. Certainty of the bounds is decreased over time using a decay function. See +/// [`ProbabilisticScoringParameters`] for details. +/// +/// Since the scorer aims to learn the current channel liquidity balances, it works best for nodes +/// with high payment volume or that actively probe the [`NetworkGraph`]. Nodes with low payment +/// volume are more likely to experience failed payment paths, which would need to be retried. +/// +/// # Note +/// +/// Mixing the `no-std` feature between serialization and deserialization results in undefined +/// behavior. +/// +/// [1]: https://arxiv.org/abs/2107.05322 +pub type ProbabilisticScorer = ProbabilisticScorerUsingTime::; /// Probabilistic [`Score`] implementation. /// @@ -517,7 +553,7 @@ pub struct ProbabilisticScorerUsingTime, T: Time /// Parameters for configuring [`ProbabilisticScorer`]. /// -/// Used to configure a base penalty and a liquidity penalty, the sum of which is the channel +/// 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)] pub struct ProbabilisticScoringParameters { @@ -529,9 +565,12 @@ pub struct ProbabilisticScoringParameters { /// A multiplier used in conjunction with the negative `log10` of the channel's success /// probability for a payment to determine the liquidity penalty. /// - /// The penalty is based in part by the knowledge learned from prior successful and unsuccessful + /// The penalty is based in part on the knowledge learned from prior successful and unsuccessful /// payments. This knowledge is decayed over time based on [`liquidity_offset_half_life`]. The - /// penalty is effectively limited to `2 * liquidity_penalty_multiplier_msat`. + /// penalty is effectively limited to `2 * liquidity_penalty_multiplier_msat` (corresponding to + /// lower bounding the success probability to `0.01`) when the amount falls within the + /// uncertainty bounds of the channel liquidity balance. Amounts above the upper bound will + /// result in a `u64::max_value` penalty, however. /// /// Default value: 40,000 msat /// @@ -552,6 +591,25 @@ pub struct ProbabilisticScoringParameters { /// When built with the `no-std` feature, time will never elapse. Therefore, the channel /// liquidity knowledge will never decay except when the bounds cross. pub liquidity_offset_half_life: Duration, + + /// A multiplier used in conjunction with a payment amount and the negative `log10` of the + /// channel's success probability for the payment to determine the amount penalty. + /// + /// The purpose of the amount penalty is to avoid having fees dominate the channel cost (i.e., + /// fees plus penalty) for large payments. The penalty is computed as the product of this + /// multiplier and `2^20`ths of the payment amount, weighted by the negative `log10` of the + /// success probability. + /// + /// `-log10(success_probability) * amount_penalty_multiplier_msat * amount_msat / 2^20` + /// + /// In practice, this means for 0.1 success probability (`-log10(0.1) == 1`) each `2^20`th of + /// the amount will result in a penalty of the multiplier. And, as the success probability + /// decreases, the negative `log10` weighting will increase dramatically. For higher success + /// probabilities, the multiplier will have a decreasing effect as the negative `log10` will + /// fall below `1`. + /// + /// Default value: 256 msat + pub amount_penalty_multiplier_msat: u64, } /// Accounting for channel liquidity balance uncertainty. @@ -599,12 +657,25 @@ impl, T: Time> ProbabilisticScorerUsingTime Self { + Self { + base_penalty_msat: 0, + liquidity_penalty_multiplier_msat: 0, + liquidity_offset_half_life: Duration::from_secs(3600), + amount_penalty_multiplier_msat: 0, + } + } +} + impl Default for ProbabilisticScoringParameters { fn default() -> Self { Self { base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 40_000, liquidity_offset_half_life: Duration::from_secs(3600), + amount_penalty_multiplier_msat: 256, } } } @@ -662,27 +733,63 @@ impl ChannelLiquidity { } } +/// Bounds `-log10` to avoid excessive liquidity penalties for payments with low success +/// probabilities. +const NEGATIVE_LOG10_UPPER_BOUND: u64 = 2; + +/// The divisor used when computing the amount penalty. +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, liquidity_penalty_multiplier_msat: u64) -> u64 { - let max_penalty_msat = liquidity_penalty_multiplier_msat.saturating_mul(2); + 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 > max_liquidity_msat { - max_penalty_msat - } else if amount_msat <= min_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_1024 = NEGATIVE_LOG10_UPPER_BOUND * 1024; + self.combined_penalty_msat(amount_msat, negative_log10_times_1024, params) + } } else { let numerator = (max_liquidity_msat - amount_msat).saturating_add(1); let denominator = (max_liquidity_msat - min_liquidity_msat).saturating_add(1); - let penalty_msat = approx::negative_log10_times_1024(numerator, denominator) - .saturating_mul(liquidity_penalty_multiplier_msat) / 1024; - // Upper bound the penalty to ensure some channel is selected. - penalty_msat.min(max_penalty_msat) + let negative_log10_times_1024 = + approx::negative_log10_times_1024(numerator, denominator); + self.combined_penalty_msat(amount_msat, negative_log10_times_1024, params) } } + /// Computes the liquidity and amount penalties and adds them to the base penalty. + #[inline(always)] + fn combined_penalty_msat( + &self, amount_msat: u64, negative_log10_times_1024: u64, + params: ProbabilisticScoringParameters + ) -> u64 { + let liquidity_penalty_msat = { + // Upper bound the liquidity penalty to ensure some channel is selected. + let multiplier_msat = params.liquidity_penalty_multiplier_msat; + let max_penalty_msat = multiplier_msat.saturating_mul(NEGATIVE_LOG10_UPPER_BOUND); + (negative_log10_times_1024.saturating_mul(multiplier_msat) / 1024).min(max_penalty_msat) + }; + let amount_penalty_msat = negative_log10_times_1024 + .saturating_mul(params.amount_penalty_multiplier_msat) + .saturating_mul(amount_msat) / 1024 / AMOUNT_PENALTY_DIVISOR; + + params.base_penalty_msat + .saturating_add(liquidity_penalty_msat) + .saturating_add(amount_penalty_msat) + } + /// Returns the lower bound of the channel liquidity balance in this direction. fn min_liquidity_msat(&self) -> u64 { self.decayed_offset_msat(*self.min_liquidity_offset_msat) @@ -752,14 +859,12 @@ impl, T: Time> Score for ProbabilisticScorerUsin &self, short_channel_id: u64, amount_msat: u64, capacity_msat: u64, source: &NodeId, target: &NodeId ) -> u64 { - let liquidity_penalty_multiplier_msat = self.params.liquidity_penalty_multiplier_msat; let liquidity_offset_half_life = self.params.liquidity_offset_half_life; self.channel_liquidities .get(&short_channel_id) .unwrap_or(&ChannelLiquidity::new()) .as_directed(source, target, capacity_msat, liquidity_offset_half_life) - .penalty_msat(amount_msat, liquidity_penalty_multiplier_msat) - .saturating_add(self.params.base_penalty_msat) + .penalty_msat(amount_msat, self.params) } fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) { @@ -1737,7 +1842,8 @@ mod tests { fn increased_penalty_nearing_liquidity_upper_bound() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { - base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, ..Default::default() + liquidity_penalty_multiplier_msat: 1_000, + ..ProbabilisticScoringParameters::zero_penalty() }; let scorer = ProbabilisticScorer::new(params, &network_graph); let source = source_node_id(); @@ -1762,7 +1868,8 @@ mod tests { let last_updated = SinceEpoch::now(); let network_graph = network_graph(); let params = ProbabilisticScoringParameters { - base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, ..Default::default() + liquidity_penalty_multiplier_msat: 1_000, + ..ProbabilisticScoringParameters::zero_penalty() }; let scorer = ProbabilisticScorer::new(params, &network_graph) .with_channel(42, @@ -1774,15 +1881,16 @@ mod tests { assert_eq!(scorer.channel_penalty_msat(42, 39, 100, &source, &target), 0); assert_ne!(scorer.channel_penalty_msat(42, 50, 100, &source, &target), 0); - assert_ne!(scorer.channel_penalty_msat(42, 50, 100, &source, &target), 2_000); - assert_eq!(scorer.channel_penalty_msat(42, 61, 100, &source, &target), 2_000); + assert_ne!(scorer.channel_penalty_msat(42, 50, 100, &source, &target), u64::max_value()); + assert_eq!(scorer.channel_penalty_msat(42, 61, 100, &source, &target), u64::max_value()); } #[test] fn does_not_further_penalize_own_channel() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { - base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, ..Default::default() + liquidity_penalty_multiplier_msat: 1_000, + ..ProbabilisticScoringParameters::zero_penalty() }; let mut scorer = ProbabilisticScorer::new(params, &network_graph); let sender = sender_node_id(); @@ -1803,7 +1911,8 @@ mod tests { fn sets_liquidity_lower_bound_on_downstream_failure() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { - base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, ..Default::default() + liquidity_penalty_multiplier_msat: 1_000, + ..ProbabilisticScoringParameters::zero_penalty() }; let mut scorer = ProbabilisticScorer::new(params, &network_graph); let source = source_node_id(); @@ -1825,7 +1934,8 @@ mod tests { fn sets_liquidity_upper_bound_on_failure() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { - base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, ..Default::default() + liquidity_penalty_multiplier_msat: 1_000, + ..ProbabilisticScoringParameters::zero_penalty() }; let mut scorer = ProbabilisticScorer::new(params, &network_graph); let source = source_node_id(); @@ -1839,15 +1949,16 @@ mod tests { scorer.payment_path_failed(&path.iter().collect::>(), 42); assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 300); - assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 2_000); - assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 2_000); + assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), u64::max_value()); + assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), u64::max_value()); } #[test] fn reduces_liquidity_upper_bound_along_path_on_success() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { - base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, ..Default::default() + liquidity_penalty_multiplier_msat: 1_000, + ..ProbabilisticScoringParameters::zero_penalty() }; let mut scorer = ProbabilisticScorer::new(params, &network_graph); let sender = sender_node_id(); @@ -1871,9 +1982,9 @@ mod tests { fn decays_liquidity_bounds_over_time() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { - base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, liquidity_offset_half_life: Duration::from_secs(10), + ..ProbabilisticScoringParameters::zero_penalty() }; let mut scorer = ProbabilisticScorer::new(params, &network_graph); let source = source_node_id(); @@ -1888,19 +1999,19 @@ mod tests { assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 0); assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 97); assert_eq!(scorer.channel_penalty_msat(42, 768, 1_024, &source, &target), 1_409); - assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), 2_000); + assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), u64::max_value()); SinceEpoch::advance(Duration::from_secs(9)); assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 0); assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 97); assert_eq!(scorer.channel_penalty_msat(42, 768, 1_024, &source, &target), 1_409); - assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), 2_000); + assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), u64::max_value()); SinceEpoch::advance(Duration::from_secs(1)); assert_eq!(scorer.channel_penalty_msat(42, 64, 1_024, &source, &target), 0); assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 34); assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), 1_773); - assert_eq!(scorer.channel_penalty_msat(42, 960, 1_024, &source, &target), 2_000); + assert_eq!(scorer.channel_penalty_msat(42, 960, 1_024, &source, &target), u64::max_value()); // Fully decay liquidity lower bound. SinceEpoch::advance(Duration::from_secs(10 * 7)); @@ -1923,9 +2034,9 @@ mod tests { fn decays_liquidity_bounds_without_shift_overflow() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { - base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, liquidity_offset_half_life: Duration::from_secs(10), + ..ProbabilisticScoringParameters::zero_penalty() }; let mut scorer = ProbabilisticScorer::new(params, &network_graph); let source = source_node_id(); @@ -1948,9 +2059,9 @@ mod tests { fn restricts_liquidity_bounds_after_decay() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { - base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, liquidity_offset_half_life: Duration::from_secs(10), + ..ProbabilisticScoringParameters::zero_penalty() }; let mut scorer = ProbabilisticScorer::new(params, &network_graph); let source = source_node_id(); @@ -1986,16 +2097,16 @@ mod tests { fn restores_persisted_liquidity_bounds() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { - base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, liquidity_offset_half_life: Duration::from_secs(10), + ..ProbabilisticScoringParameters::zero_penalty() }; let mut scorer = ProbabilisticScorer::new(params, &network_graph); let source = source_node_id(); let target = target_node_id(); scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::>(), 42); - assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 2_000); + assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), u64::max_value()); SinceEpoch::advance(Duration::from_secs(10)); assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 472); @@ -2016,16 +2127,16 @@ mod tests { fn decays_persisted_liquidity_bounds() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters { - base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, liquidity_offset_half_life: Duration::from_secs(10), + ..ProbabilisticScoringParameters::zero_penalty() }; let mut scorer = ProbabilisticScorer::new(params, &network_graph); let source = source_node_id(); let target = target_node_id(); scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::>(), 42); - assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 2_000); + assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), u64::max_value()); let mut serialized_scorer = Vec::new(); scorer.write(&mut serialized_scorer).unwrap(); @@ -2051,7 +2162,8 @@ mod tests { let target = target_node_id(); let params = ProbabilisticScoringParameters { - base_penalty_msat: 0, liquidity_penalty_multiplier_msat: 1_000, ..Default::default() + liquidity_penalty_multiplier_msat: 1_000, + ..ProbabilisticScoringParameters::zero_penalty() }; let scorer = ProbabilisticScorer::new(params, &network_graph); assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 58); @@ -2063,6 +2175,29 @@ mod tests { assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 558); } + #[test] + fn adds_amount_penalty_to_liquidity_penalty() { + let network_graph = network_graph(); + let source = source_node_id(); + let target = target_node_id(); + + let params = ProbabilisticScoringParameters { + liquidity_penalty_multiplier_msat: 1_000, + amount_penalty_multiplier_msat: 0, + ..ProbabilisticScoringParameters::zero_penalty() + }; + let scorer = ProbabilisticScorer::new(params, &network_graph); + assert_eq!(scorer.channel_penalty_msat(42, 512_000, 1_024_000, &source, &target), 300); + + let params = ProbabilisticScoringParameters { + liquidity_penalty_multiplier_msat: 1_000, + amount_penalty_multiplier_msat: 256, + ..ProbabilisticScoringParameters::zero_penalty() + }; + let scorer = ProbabilisticScorer::new(params, &network_graph); + assert_eq!(scorer.channel_penalty_msat(42, 512_000, 1_024_000, &source, &target), 337); + } + #[test] fn calculates_log10_without_overflowing_u64_max_value() { let network_graph = network_graph(); @@ -2070,7 +2205,8 @@ mod tests { let target = target_node_id(); let params = ProbabilisticScoringParameters { - base_penalty_msat: 0, ..Default::default() + liquidity_penalty_multiplier_msat: 40_000, + ..ProbabilisticScoringParameters::zero_penalty() }; let scorer = ProbabilisticScorer::new(params, &network_graph); assert_eq!(