X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Fscoring.rs;h=8e9a002dd519a6bef57316da1d0ed6b7ebebe811;hb=51b0652d32fd22753a384102932527b3f986e8e0;hp=173a33cdd72a4b9d26ed806309120b26029e378e;hpb=4f1b31314f3b9c5bd86ca0b83e7403155c60c5db;p=rust-lightning diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index 173a33cd..8e9a002d 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -9,8 +9,8 @@ //! Utilities for scoring payment channels. //! -//! [`Scorer`] may be given to [`find_route`] to score payment channels during path finding when a -//! custom [`Score`] implementation is not needed. +//! [`ProbabilisticScorer`] may be given to [`find_route`] to score payment channels during path +//! finding when a custom [`Score`] implementation is not needed. //! //! # Example //! @@ -19,7 +19,7 @@ //! # //! # use lightning::routing::network_graph::NetworkGraph; //! # use lightning::routing::router::{RouteParameters, find_route}; -//! # use lightning::routing::scoring::{Scorer, ScoringParameters}; +//! # use lightning::routing::scoring::{ProbabilisticScorer, ProbabilisticScoringParameters, Scorer, ScoringParameters}; //! # use lightning::util::logger::{Logger, Record}; //! # use secp256k1::key::PublicKey; //! # @@ -27,20 +27,21 @@ //! # impl Logger for FakeLogger { //! # fn log(&self, record: &Record) { unimplemented!() } //! # } -//! # fn find_scored_route(payer: PublicKey, params: RouteParameters, network_graph: NetworkGraph) { +//! # fn find_scored_route(payer: PublicKey, route_params: RouteParameters, network_graph: NetworkGraph) { //! # let logger = FakeLogger {}; //! # //! // Use the default channel penalties. -//! let scorer = Scorer::default(); +//! let params = ProbabilisticScoringParameters::default(); +//! let scorer = ProbabilisticScorer::new(params, &payer, &network_graph); //! //! // Or use custom channel penalties. -//! let scorer = Scorer::new(ScoringParameters { -//! base_penalty_msat: 1000, -//! failure_penalty_msat: 2 * 1024 * 1000, -//! ..ScoringParameters::default() -//! }); +//! let params = ProbabilisticScoringParameters { +//! liquidity_penalty_multiplier_msat: 2 * 1000, +//! ..ProbabilisticScoringParameters::default() +//! }; +//! let scorer = ProbabilisticScorer::new(params, &payer, &network_graph); //! -//! let route = find_route(&payer, ¶ms, &network_graph, None, &logger, &scorer); +//! let route = find_route(&payer, &route_params, &network_graph, None, &logger, &scorer); //! # } //! ``` //! @@ -463,7 +464,7 @@ impl Readable for ChannelFailure { /// /// [1]: https://arxiv.org/abs/2107.05322 pub struct ProbabilisticScorer> { - _params: ProbabilisticScoringParameters, + params: ProbabilisticScoringParameters, node_id: NodeId, network_graph: G, // TODO: Remove entries of closed channels. @@ -471,9 +472,19 @@ pub struct ProbabilisticScorer> { } /// Parameters for configuring [`ProbabilisticScorer`]. -pub struct ProbabilisticScoringParameters; +pub struct ProbabilisticScoringParameters { + /// A penalty applied after multiplying by the negative log of channel's success probability for + /// a payment. + /// + /// The success probability is determined by the effective channel capacity, the payment amount, + /// and knowledge learned from prior successful and unsuccessful payments. + /// + /// Default value: 1,000 msat + pub liquidity_penalty_multiplier_msat: u64, +} impl_writeable_tlv_based!(ProbabilisticScoringParameters, { + (0, liquidity_penalty_multiplier_msat, required), }); /// Accounting for channel liquidity balance uncertainty. @@ -493,22 +504,15 @@ struct DirectedChannelLiquidity> { capacity_msat: u64, } -/// The likelihood of an event occurring. -enum Probability { - Zero, - One, - Ratio { numerator: u64, denominator: u64 }, -} - impl> ProbabilisticScorer { /// Creates a new scorer using the given scoring parameters for sending payments from a node /// through a network graph. pub fn new( - _params: ProbabilisticScoringParameters, node_pubkey: PublicKey, network_graph: G + params: ProbabilisticScoringParameters, node_pubkey: &PublicKey, network_graph: G ) -> Self { Self { - _params, - node_id: NodeId::from_pubkey(&node_pubkey), + params, + node_id: NodeId::from_pubkey(node_pubkey), network_graph, channel_liquidities: HashMap::new(), } @@ -523,7 +527,9 @@ impl> ProbabilisticScorer { impl Default for ProbabilisticScoringParameters { fn default() -> Self { - Self + Self { + liquidity_penalty_multiplier_msat: 1000, + } } } @@ -576,21 +582,17 @@ impl ChannelLiquidity { impl> DirectedChannelLiquidity { /// Returns the success probability of routing the given HTLC `amount_msat` through the channel /// in this direction. - fn success_probability(&self, amount_msat: u64) -> Probability { + fn success_probability(&self, amount_msat: u64) -> f64 { 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 { - Probability::Zero - } else if amount_msat < min_liquidity_msat { - Probability::One + 0.0 + } else if amount_msat <= min_liquidity_msat { + 1.0 } else { let numerator = max_liquidity_msat + 1 - amount_msat; let denominator = max_liquidity_msat + 1 - min_liquidity_msat; - if numerator == denominator { - Probability::One - } else { - Probability::Ratio { numerator, denominator } - } + numerator as f64 / denominator as f64 } } @@ -654,18 +656,18 @@ impl> Score for ProbabilisticScorer { return 0; } + let liquidity_penalty_multiplier_msat = self.params.liquidity_penalty_multiplier_msat; let success_probability = self.channel_liquidities .get(&short_channel_id) .unwrap_or(&ChannelLiquidity::new()) .as_directed(source, target, capacity_msat) .success_probability(amount_msat); - match success_probability { - Probability::Zero => u64::max_value(), - Probability::One => 0, - Probability::Ratio { numerator, denominator } => { - let success_probability = numerator as f64 / denominator as f64; - (-(success_probability.log10()) * amount_msat as f64) as u64 - }, + if success_probability == 0.0 { + u64::max_value() + } else if success_probability == 1.0 { + 0 + } else { + (-(success_probability.log10()) * liquidity_penalty_multiplier_msat as f64) as u64 } } @@ -732,21 +734,21 @@ impl> Score for ProbabilisticScorer { impl> Writeable for ProbabilisticScorer { #[inline] fn write(&self, w: &mut W) -> Result<(), io::Error> { - self._params.write(w)?; - self.node_id.write(w)?; + self.params.write(w)?; self.channel_liquidities.write(w)?; write_tlv_fields!(w, {}); Ok(()) } } -impl> ReadableArgs for ProbabilisticScorer { +impl> ReadableArgs<(&PublicKey, G)> for ProbabilisticScorer { #[inline] - fn read(r: &mut R, args: G) -> Result { + fn read(r: &mut R, args: (&PublicKey, G)) -> Result { + let (node_pubkey, network_graph) = args; let res = Ok(Self { - _params: Readable::read(r)?, - node_id: Readable::read(r)?, - network_graph: args, + params: Readable::read(r)?, + node_id: NodeId::from_pubkey(node_pubkey), + network_graph, channel_liquidities: Readable::read(r)?, }); read_tlv_fields!(r, {}); @@ -1287,7 +1289,7 @@ mod tests { network_graph.update_channel(&signed_update, &secp_ctx).unwrap(); } - fn payment_path(amount_msat: u64) -> Vec { + fn payment_path_for_amount(amount_msat: u64) -> Vec { vec![ RouteHop { pubkey: source_pubkey(), @@ -1320,7 +1322,7 @@ mod tests { fn liquidity_bounds_directed_from_lowest_node_id() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters::default(); - let mut scorer = ProbabilisticScorer::new(params, sender_pubkey(), &network_graph) + let mut scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph) .with_channel(42, ChannelLiquidity { min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100 @@ -1360,33 +1362,143 @@ mod tests { assert_eq!(liquidity.as_directed(&recipient, &target, 1_000).max_liquidity_msat(), 1000); } + #[test] + fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() { + let network_graph = network_graph(); + let params = ProbabilisticScoringParameters::default(); + let mut scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph) + .with_channel(42, + ChannelLiquidity { + min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400 + }); + let source = source_node_id(); + let target = target_node_id(); + assert!(source > target); + + // Check initial bounds. + let liquidity = scorer.channel_liquidities.get(&42).unwrap() + .as_directed(&source, &target, 1_000); + assert_eq!(liquidity.min_liquidity_msat(), 400); + assert_eq!(liquidity.max_liquidity_msat(), 800); + + let liquidity = scorer.channel_liquidities.get(&42).unwrap() + .as_directed(&target, &source, 1_000); + assert_eq!(liquidity.min_liquidity_msat(), 200); + assert_eq!(liquidity.max_liquidity_msat(), 600); + + // Reset from source to target. + scorer.channel_liquidities.get_mut(&42).unwrap() + .as_directed_mut(&source, &target, 1_000) + .set_min_liquidity_msat(900); + + let liquidity = scorer.channel_liquidities.get(&42).unwrap() + .as_directed(&source, &target, 1_000); + assert_eq!(liquidity.min_liquidity_msat(), 900); + assert_eq!(liquidity.max_liquidity_msat(), 1_000); + + let liquidity = scorer.channel_liquidities.get(&42).unwrap() + .as_directed(&target, &source, 1_000); + assert_eq!(liquidity.min_liquidity_msat(), 0); + assert_eq!(liquidity.max_liquidity_msat(), 100); + + // Reset from target to source. + scorer.channel_liquidities.get_mut(&42).unwrap() + .as_directed_mut(&target, &source, 1_000) + .set_min_liquidity_msat(400); + + let liquidity = scorer.channel_liquidities.get(&42).unwrap() + .as_directed(&source, &target, 1_000); + assert_eq!(liquidity.min_liquidity_msat(), 0); + assert_eq!(liquidity.max_liquidity_msat(), 600); + + let liquidity = scorer.channel_liquidities.get(&42).unwrap() + .as_directed(&target, &source, 1_000); + assert_eq!(liquidity.min_liquidity_msat(), 400); + assert_eq!(liquidity.max_liquidity_msat(), 1_000); + } + + #[test] + fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() { + let network_graph = network_graph(); + let params = ProbabilisticScoringParameters::default(); + let mut scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph) + .with_channel(42, + ChannelLiquidity { + min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400 + }); + let source = source_node_id(); + let target = target_node_id(); + assert!(source > target); + + // Check initial bounds. + let liquidity = scorer.channel_liquidities.get(&42).unwrap() + .as_directed(&source, &target, 1_000); + assert_eq!(liquidity.min_liquidity_msat(), 400); + assert_eq!(liquidity.max_liquidity_msat(), 800); + + let liquidity = scorer.channel_liquidities.get(&42).unwrap() + .as_directed(&target, &source, 1_000); + assert_eq!(liquidity.min_liquidity_msat(), 200); + assert_eq!(liquidity.max_liquidity_msat(), 600); + + // Reset from source to target. + scorer.channel_liquidities.get_mut(&42).unwrap() + .as_directed_mut(&source, &target, 1_000) + .set_max_liquidity_msat(300); + + let liquidity = scorer.channel_liquidities.get(&42).unwrap() + .as_directed(&source, &target, 1_000); + assert_eq!(liquidity.min_liquidity_msat(), 0); + assert_eq!(liquidity.max_liquidity_msat(), 300); + + let liquidity = scorer.channel_liquidities.get(&42).unwrap() + .as_directed(&target, &source, 1_000); + assert_eq!(liquidity.min_liquidity_msat(), 700); + assert_eq!(liquidity.max_liquidity_msat(), 1_000); + + // Reset from target to source. + scorer.channel_liquidities.get_mut(&42).unwrap() + .as_directed_mut(&target, &source, 1_000) + .set_max_liquidity_msat(600); + + let liquidity = scorer.channel_liquidities.get(&42).unwrap() + .as_directed(&source, &target, 1_000); + assert_eq!(liquidity.min_liquidity_msat(), 400); + assert_eq!(liquidity.max_liquidity_msat(), 1_000); + + let liquidity = scorer.channel_liquidities.get(&42).unwrap() + .as_directed(&target, &source, 1_000); + assert_eq!(liquidity.min_liquidity_msat(), 0); + assert_eq!(liquidity.max_liquidity_msat(), 600); + } + #[test] fn increased_penalty_nearing_liquidity_upper_bound() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters::default(); - let scorer = ProbabilisticScorer::new(params, sender_pubkey(), &network_graph); + let scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph); let source = source_node_id(); let target = target_node_id(); assert_eq!(scorer.channel_penalty_msat(42, 100, 100_000, &source, &target), 0); assert_eq!(scorer.channel_penalty_msat(42, 1_000, 100_000, &source, &target), 4); - assert_eq!(scorer.channel_penalty_msat(42, 10_000, 100_000, &source, &target), 457); - assert_eq!(scorer.channel_penalty_msat(42, 100_000, 100_000, &source, &target), 500_000); + assert_eq!(scorer.channel_penalty_msat(42, 10_000, 100_000, &source, &target), 45); + assert_eq!(scorer.channel_penalty_msat(42, 100_000, 100_000, &source, &target), 5_000); - assert_eq!(scorer.channel_penalty_msat(42, 125, 1_000, &source, &target), 7); - assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 31); - assert_eq!(scorer.channel_penalty_msat(42, 375, 1_000, &source, &target), 76); - assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 150); - assert_eq!(scorer.channel_penalty_msat(42, 625, 1_000, &source, &target), 265); - assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 450); - assert_eq!(scorer.channel_penalty_msat(42, 875, 1_000, &source, &target), 787); + assert_eq!(scorer.channel_penalty_msat(42, 125, 1_000, &source, &target), 57); + assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 124); + assert_eq!(scorer.channel_penalty_msat(42, 375, 1_000, &source, &target), 203); + assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300); + assert_eq!(scorer.channel_penalty_msat(42, 625, 1_000, &source, &target), 425); + assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 600); + assert_eq!(scorer.channel_penalty_msat(42, 875, 1_000, &source, &target), 900); } #[test] fn constant_penalty_outside_liquidity_bounds() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters::default(); - let scorer = ProbabilisticScorer::new(params, sender_pubkey(), &network_graph) + let scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph) .with_channel(42, ChannelLiquidity { min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40 }); let source = source_node_id(); @@ -1399,30 +1511,83 @@ mod tests { } #[test] - fn reduces_liquidity_upper_bound_on_success() { + fn does_not_penalize_own_channel() { let network_graph = network_graph(); let params = ProbabilisticScoringParameters::default(); - let mut scorer = ProbabilisticScorer::new(params, sender_pubkey(), &network_graph) - .with_channel(42, - ChannelLiquidity { min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 0 }) - .with_channel(43, - ChannelLiquidity { min_liquidity_offset_msat: 0, max_liquidity_offset_msat: 400 }); + let mut scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph); + let sender = sender_node_id(); + let source = source_node_id(); + let failed_path = payment_path_for_amount(500); + let successful_path = payment_path_for_amount(200); + + assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 0); + + scorer.payment_path_failed(&failed_path.iter().collect::>(), 41); + assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 0); + + scorer.payment_path_successful(&successful_path.iter().collect::>()); + assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 0); + } + + #[test] + fn sets_liquidity_lower_bound_on_downstream_failure() { + let network_graph = network_graph(); + let params = ProbabilisticScoringParameters::default(); + let mut scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph); + let source = source_node_id(); + let target = target_node_id(); + let path = payment_path_for_amount(500); + + assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 124); + assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300); + assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 600); + + scorer.payment_path_failed(&path.iter().collect::>(), 43); + + assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 0); + assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 0); + assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 300); + } + + #[test] + fn sets_liquidity_upper_bound_on_failure() { + let network_graph = network_graph(); + let params = ProbabilisticScoringParameters::default(); + let mut scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph); + let source = source_node_id(); + let target = target_node_id(); + let path = payment_path_for_amount(500); + + assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 124); + assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300); + assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 600); + + 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), 2699); + 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::default(); + let mut scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph); let sender = sender_node_id(); let source = source_node_id(); let target = target_node_id(); let recipient = recipient_node_id(); - let path = payment_path(200); + let path = payment_path_for_amount(500); - assert_eq!(scorer.channel_penalty_msat(41, 200, 1_000, &sender, &source), 0); - assert_eq!(scorer.channel_penalty_msat(42, 200, 1_000, &source, &target), 94); - assert_eq!(scorer.channel_penalty_msat(43, 200, 1_000, &target, &recipient), 35); + assert_eq!(scorer.channel_penalty_msat(41, 250, 1_000, &sender, &source), 0); + assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 124); + assert_eq!(scorer.channel_penalty_msat(43, 250, 1_000, &target, &recipient), 124); scorer.payment_path_successful(&path.iter().collect::>()); - assert_eq!(scorer.channel_penalty_msat(41, 200, 1_000, &sender, &source), 0); - assert_eq!(scorer.channel_penalty_msat(42, 200, 1_000, &source, &target), u64::max_value()); - assert_eq!(scorer.channel_penalty_msat(43, 200, 1_000, &target, &recipient), 59); + assert_eq!(scorer.channel_penalty_msat(41, 250, 1_000, &sender, &source), 0); + assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 300); + assert_eq!(scorer.channel_penalty_msat(43, 250, 1_000, &target, &recipient), 300); } - - // TODO: Add more test coverage }