X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Fscoring.rs;h=4fef17f9b99b55ae156f8a69fea60dcafdf95ceb;hb=4b36119d87b255c30536d9322407e2478b7b6869;hp=82e52755c8f9ad0fa3f92addbe8741852973ef65;hpb=0a8cb900d8ce5f9be063256becaea897bb37fee5;p=rust-lightning diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index 82e52755..4fef17f9 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -32,14 +32,14 @@ //! # //! // Use the default channel penalties. //! let params = ProbabilisticScoringParameters::default(); -//! let scorer = ProbabilisticScorer::new(params, &payer, &network_graph); +//! let scorer = ProbabilisticScorer::new(params, &network_graph); //! //! // Or use custom channel penalties. //! let params = ProbabilisticScoringParameters { //! liquidity_penalty_multiplier_msat: 2 * 1000, //! ..ProbabilisticScoringParameters::default() //! }; -//! let scorer = ProbabilisticScorer::new(params, &payer, &network_graph); +//! let scorer = ProbabilisticScorer::new(params, &network_graph); //! //! let route = find_route(&payer, &route_params, &network_graph, None, &logger, &scorer); //! # } @@ -52,10 +52,8 @@ //! //! [`find_route`]: crate::routing::router::find_route -use bitcoin::secp256k1::key::PublicKey; - use ln::msgs::DecodeError; -use routing::network_graph::{EffectiveCapacity, NetworkGraph, NodeId}; +use routing::network_graph::{NetworkGraph, NodeId}; use routing::router::RouteHop; use util::ser::{Readable, ReadableArgs, Writeable, Writer}; @@ -466,7 +464,6 @@ impl Readable for ChannelFailure { /// [1]: https://arxiv.org/abs/2107.05322 pub struct ProbabilisticScorer> { params: ProbabilisticScoringParameters, - node_id: NodeId, network_graph: G, // TODO: Remove entries of closed channels. channel_liquidities: HashMap, @@ -496,7 +493,10 @@ impl_writeable_tlv_based!(ProbabilisticScoringParameters, { /// first node in the ordering of the channel's counterparties. Thus, swapping the two liquidity /// offset fields gives the opposite direction. struct ChannelLiquidity { + /// Lower channel liquidity bound in terms of an offset from zero. min_liquidity_offset_msat: u64, + + /// Upper channel liquidity bound in terms of an offset from the effective capacity. max_liquidity_offset_msat: u64, } @@ -510,12 +510,9 @@ struct DirectedChannelLiquidity> { 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 - ) -> Self { + pub fn new(params: ProbabilisticScoringParameters, network_graph: G) -> Self { Self { params, - node_id: NodeId::from_pubkey(node_pubkey), network_graph, channel_liquidities: HashMap::new(), } @@ -651,86 +648,70 @@ impl> DirectedChannelLiquidity { } impl> Score for ProbabilisticScorer { - #[allow(clippy::float_cmp)] fn channel_penalty_msat( &self, short_channel_id: u64, amount_msat: u64, capacity_msat: u64, source: &NodeId, target: &NodeId ) -> u64 { - if *source == self.node_id || *target == self.node_id { - 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); - 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 - } + // NOTE: If success_probability is ever changed to return 0.0, log10 is undefined so return + // u64::max_value instead. + debug_assert!(success_probability > core::f64::EPSILON); + (-(success_probability.log10()) * liquidity_penalty_multiplier_msat as f64) as u64 } fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) { let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0); let network_graph = self.network_graph.read_only(); - let hop_sources = core::iter::once(self.node_id) - .chain(path.iter().map(|hop| NodeId::from_pubkey(&hop.pubkey))); - for (source, hop) in hop_sources.zip(path.iter()) { + for hop in path { let target = NodeId::from_pubkey(&hop.pubkey); - if source == self.node_id || target == self.node_id { - continue; - } - - let capacity_msat = network_graph.channels() + let channel_directed_from_source = network_graph.channels() .get(&hop.short_channel_id) - .and_then(|channel| channel.as_directed_to(&target).map(|(d, _)| d.effective_capacity())) - .unwrap_or(EffectiveCapacity::Unknown) - .as_msat(); + .and_then(|channel| channel.as_directed_to(&target)); + + // Only score announced channels. + if let Some((channel, source)) = channel_directed_from_source { + let capacity_msat = channel.effective_capacity().as_msat(); + if hop.short_channel_id == short_channel_id { + self.channel_liquidities + .entry(hop.short_channel_id) + .or_insert_with(ChannelLiquidity::new) + .as_directed_mut(source, &target, capacity_msat) + .failed_at_channel(amount_msat); + break; + } - if hop.short_channel_id == short_channel_id { self.channel_liquidities .entry(hop.short_channel_id) - .or_insert_with(|| ChannelLiquidity::new()) - .as_directed_mut(&source, &target, capacity_msat) - .failed_at_channel(amount_msat); - break; + .or_insert_with(ChannelLiquidity::new) + .as_directed_mut(source, &target, capacity_msat) + .failed_downstream(amount_msat); } - - self.channel_liquidities - .entry(hop.short_channel_id) - .or_insert_with(|| ChannelLiquidity::new()) - .as_directed_mut(&source, &target, capacity_msat) - .failed_downstream(amount_msat); } } fn payment_path_successful(&mut self, path: &[&RouteHop]) { let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0); let network_graph = self.network_graph.read_only(); - let hop_sources = core::iter::once(self.node_id) - .chain(path.iter().map(|hop| NodeId::from_pubkey(&hop.pubkey))); - for (source, hop) in hop_sources.zip(path.iter()) { + for hop in path { let target = NodeId::from_pubkey(&hop.pubkey); - if source == self.node_id || target == self.node_id { - continue; - } - - let capacity_msat = network_graph.channels() + let channel_directed_from_source = network_graph.channels() .get(&hop.short_channel_id) - .and_then(|channel| channel.as_directed_to(&target).map(|(d, _)| d.effective_capacity())) - .unwrap_or(EffectiveCapacity::Unknown) - .as_msat(); + .and_then(|channel| channel.as_directed_to(&target)); - self.channel_liquidities - .entry(hop.short_channel_id) - .or_insert_with(|| ChannelLiquidity::new()) - .as_directed_mut(&source, &target, capacity_msat) - .successful(amount_msat); + // Only score announced channels. + if let Some((channel, source)) = channel_directed_from_source { + let capacity_msat = channel.effective_capacity().as_msat(); + self.channel_liquidities + .entry(hop.short_channel_id) + .or_insert_with(ChannelLiquidity::new) + .as_directed_mut(source, &target, capacity_msat) + .successful(amount_msat); + } } } } @@ -738,25 +719,29 @@ impl> Score for ProbabilisticScorer { impl> Writeable for ProbabilisticScorer { #[inline] fn write(&self, w: &mut W) -> Result<(), io::Error> { - self.params.write(w)?; - self.channel_liquidities.write(w)?; - write_tlv_fields!(w, {}); + write_tlv_fields!(w, { + (0, self.channel_liquidities, required) + }); Ok(()) } } -impl> ReadableArgs<(&PublicKey, G)> for ProbabilisticScorer { +impl> ReadableArgs<(ProbabilisticScoringParameters, G)> +for ProbabilisticScorer { #[inline] - 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: NodeId::from_pubkey(node_pubkey), - network_graph, - channel_liquidities: Readable::read(r)?, + fn read( + r: &mut R, args: (ProbabilisticScoringParameters, G) + ) -> Result { + let (params, network_graph) = args; + let mut channel_liquidities = HashMap::new(); + read_tlv_fields!(r, { + (0, channel_liquidities, required) }); - read_tlv_fields!(r, {}); - res + Ok(Self { + params, + network_graph, + channel_liquidities, + }) } } @@ -1228,7 +1213,6 @@ mod tests { fn network_graph() -> NetworkGraph { let genesis_hash = genesis_block(Network::Testnet).header.block_hash(); let mut network_graph = NetworkGraph::new(genesis_hash); - add_channel(&mut network_graph, 41, sender_privkey(), source_privkey()); add_channel(&mut network_graph, 42, source_privkey(), target_privkey()); add_channel(&mut network_graph, 43, target_privkey(), recipient_privkey()); @@ -1326,7 +1310,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, &network_graph) .with_channel(42, ChannelLiquidity { min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100 @@ -1370,7 +1354,7 @@ mod tests { 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) + let mut scorer = ProbabilisticScorer::new(params, &network_graph) .with_channel(42, ChannelLiquidity { min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400 @@ -1425,7 +1409,7 @@ mod tests { 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) + let mut scorer = ProbabilisticScorer::new(params, &network_graph) .with_channel(42, ChannelLiquidity { min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400 @@ -1480,7 +1464,7 @@ mod tests { 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, &network_graph); let source = source_node_id(); let target = target_node_id(); @@ -1502,7 +1486,7 @@ mod tests { 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, &network_graph) .with_channel(42, ChannelLiquidity { min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40 }); let source = source_node_id(); @@ -1515,29 +1499,29 @@ mod tests { } #[test] - fn does_not_penalize_own_channel() { + fn does_not_further_penalize_own_channel() { 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, &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); + assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 300); scorer.payment_path_failed(&failed_path.iter().collect::>(), 41); - assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 0); + assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 300); scorer.payment_path_successful(&successful_path.iter().collect::>()); - assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 0); + assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 300); } #[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 mut scorer = ProbabilisticScorer::new(params, &network_graph); let source = source_node_id(); let target = target_node_id(); let path = payment_path_for_amount(500); @@ -1557,7 +1541,7 @@ mod tests { 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 mut scorer = ProbabilisticScorer::new(params, &network_graph); let source = source_node_id(); let target = target_node_id(); let path = payment_path_for_amount(500); @@ -1577,20 +1561,20 @@ mod tests { 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 mut scorer = ProbabilisticScorer::new(params, &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_for_amount(500); - assert_eq!(scorer.channel_penalty_msat(41, 250, 1_000, &sender, &source), 0); + assert_eq!(scorer.channel_penalty_msat(41, 250, 1_000, &sender, &source), 124); 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, 250, 1_000, &sender, &source), 0); + assert_eq!(scorer.channel_penalty_msat(41, 250, 1_000, &sender, &source), 124); 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); }