X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Fscoring.rs;h=6ace8681ac025a08423bff54c4dae67b829fab5f;hb=bfe911dadcd31ec0e3a2e866d3e154e9781498a4;hp=2c29fd3f1c02cc588530ed4c307cb7360574bce6;hpb=22888425f7bfb5a9ac9ffd32906f1a01a035021b;p=rust-lightning diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index 2c29fd3f..6ace8681 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -61,7 +61,6 @@ use crate::routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId}; use crate::routing::router::{Path, CandidateRouteHop}; use crate::util::ser::{Readable, ReadableArgs, Writeable, Writer}; use crate::util::logger::Logger; -use crate::util::time::Time; use crate::prelude::*; use core::{cmp, fmt}; @@ -440,13 +439,6 @@ impl ReadableArgs for FixedPenaltyScorer { } } -#[cfg(not(feature = "no-std"))] -type ConfiguredTime = crate::util::time::MonotonicTime; -#[cfg(feature = "no-std")] -use crate::util::time::Eternity; -#[cfg(feature = "no-std")] -type ConfiguredTime = Eternity; - /// [`ScoreLookUp`] implementation using channel success probability distributions. /// /// Channels are tracked with upper and lower liquidity bounds - when an HTLC fails at a channel, @@ -472,29 +464,18 @@ type ConfiguredTime = Eternity; /// formula, but using the history of a channel rather than our latest estimates for the liquidity /// bounds. /// -/// # Note -/// -/// Mixing the `no-std` feature between serialization and deserialization results in undefined -/// behavior. -/// /// [1]: https://arxiv.org/abs/2107.05322 /// [`liquidity_penalty_multiplier_msat`]: ProbabilisticScoringFeeParameters::liquidity_penalty_multiplier_msat /// [`liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringFeeParameters::liquidity_penalty_amount_multiplier_msat /// [`liquidity_offset_half_life`]: ProbabilisticScoringDecayParameters::liquidity_offset_half_life /// [`historical_liquidity_penalty_multiplier_msat`]: ProbabilisticScoringFeeParameters::historical_liquidity_penalty_multiplier_msat /// [`historical_liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringFeeParameters::historical_liquidity_penalty_amount_multiplier_msat -pub type ProbabilisticScorer = ProbabilisticScorerUsingTime::; - -/// Probabilistic [`ScoreLookUp`] implementation. -/// -/// This is not exported to bindings users generally all users should use the [`ProbabilisticScorer`] type alias. -pub struct ProbabilisticScorerUsingTime>, L: Deref, T: Time> +pub struct ProbabilisticScorer>, L: Deref> where L::Target: Logger { decay_params: ProbabilisticScoringDecayParameters, network_graph: G, logger: L, channel_liquidities: HashMap, - _unused_time: core::marker::PhantomData, } /// Parameters for configuring [`ProbabilisticScorer`]. @@ -749,7 +730,7 @@ pub struct ProbabilisticScoringDecayParameters { /// /// Default value: 14 days /// - /// [`historical_estimated_channel_liquidity_probabilities`]: ProbabilisticScorerUsingTime::historical_estimated_channel_liquidity_probabilities + /// [`historical_estimated_channel_liquidity_probabilities`]: ProbabilisticScorer::historical_estimated_channel_liquidity_probabilities pub historical_no_updates_half_life: Duration, /// Whenever this amount of time elapses since the last update to a channel's liquidity bounds, @@ -808,7 +789,7 @@ struct ChannelLiquidity { min_liquidity_offset_history: HistoricalBucketRangeTracker, max_liquidity_offset_history: HistoricalBucketRangeTracker, - /// Time when the liquidity bounds were last modified as an offset since the unix epoch. + /// Time when either liquidity bound was last modified as an offset since the unix epoch. last_updated: Duration, /// Time when the historical liquidity bounds were last modified as an offset against the unix @@ -824,10 +805,9 @@ struct DirectedChannelLiquidity, BRT: Deref>, L: Deref, T: Time> ProbabilisticScorerUsingTime where L::Target: Logger { +impl>, L: Deref> ProbabilisticScorer 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(decay_params: ProbabilisticScoringDecayParameters, network_graph: G, logger: L) -> Self { @@ -836,7 +816,6 @@ impl>, L: Deref, T: Time> ProbabilisticScorerU network_graph, logger, channel_liquidities: HashMap::new(), - _unused_time: core::marker::PhantomData, } } @@ -857,7 +836,7 @@ impl>, L: Deref, T: Time> ProbabilisticScorerU let log_direction = |source, target| { if let Some((directed_info, _)) = chan_debug.as_directed_to(target) { let amt = directed_info.effective_capacity().as_msat(); - let dir_liq = liq.as_directed(source, target, amt, self.decay_params); + let dir_liq = liq.as_directed(source, target, amt); let min_buckets = &dir_liq.liquidity_history.min_liquidity_offset_history.buckets; let max_buckets = &dir_liq.liquidity_history.max_liquidity_offset_history.buckets; @@ -909,7 +888,7 @@ impl>, L: Deref, T: Time> ProbabilisticScorerU 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.decay_params); + let dir_liq = liq.as_directed(source, target, amt); return Some((dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat())); } } @@ -951,7 +930,7 @@ impl>, L: Deref, T: Time> ProbabilisticScorerU 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.decay_params); + let dir_liq = liq.as_directed(source, target, amt); let min_buckets = dir_liq.liquidity_history.min_liquidity_offset_history.buckets; let mut max_buckets = dir_liq.liquidity_history.max_liquidity_offset_history.buckets; @@ -982,7 +961,7 @@ impl>, L: Deref, T: Time> ProbabilisticScorerU if let Some(liq) = self.channel_liquidities.get(&scid) { if let Some((directed_info, source)) = chan.as_directed_to(target) { let capacity_msat = directed_info.effective_capacity().as_msat(); - let dir_liq = liq.as_directed(source, target, capacity_msat, self.decay_params); + let dir_liq = liq.as_directed(source, target, capacity_msat); return dir_liq.liquidity_history.calculate_success_probability_times_billion( ¶ms, amount_msat, capacity_msat @@ -1009,7 +988,7 @@ impl ChannelLiquidity { /// Returns a view of the channel liquidity directed from `source` to `target` assuming /// `capacity_msat`. fn as_directed( - &self, source: &NodeId, target: &NodeId, capacity_msat: u64, decay_params: ProbabilisticScoringDecayParameters + &self, source: &NodeId, target: &NodeId, capacity_msat: u64, ) -> DirectedChannelLiquidity<&u64, &HistoricalBucketRangeTracker, &Duration> { let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) = if source < target { @@ -1030,14 +1009,13 @@ impl ChannelLiquidity { capacity_msat, last_updated: &self.last_updated, offset_history_last_updated: &self.offset_history_last_updated, - decay_params: decay_params, } } /// Returns a mutable view of the channel liquidity directed from `source` to `target` assuming /// `capacity_msat`. fn as_directed_mut( - &mut self, source: &NodeId, target: &NodeId, capacity_msat: u64, decay_params: ProbabilisticScoringDecayParameters + &mut self, source: &NodeId, target: &NodeId, capacity_msat: u64, ) -> DirectedChannelLiquidity<&mut u64, &mut HistoricalBucketRangeTracker, &mut Duration> { let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) = if source < target { @@ -1058,7 +1036,6 @@ impl ChannelLiquidity { capacity_msat, last_updated: &mut self.last_updated, offset_history_last_updated: &mut self.offset_history_last_updated, - decay_params: decay_params, } } @@ -1251,18 +1228,14 @@ DirectedChannelLiquidity< L, BRT, T> { /// Returns the lower bound of the channel liquidity balance in this direction. #[inline(always)] fn min_liquidity_msat(&self) -> u64 { - self.decayed_offset_msat(*self.min_liquidity_offset_msat) + *self.min_liquidity_offset_msat } /// Returns the upper bound of the channel liquidity balance in this direction. #[inline(always)] fn max_liquidity_msat(&self) -> u64 { self.capacity_msat - .saturating_sub(self.decayed_offset_msat(*self.max_liquidity_offset_msat)) - } - - fn decayed_offset_msat(&self, offset_msat: u64) -> u64 { - offset_msat + .saturating_sub(*self.max_liquidity_offset_msat) } } @@ -1313,21 +1286,11 @@ DirectedChannelLiquidity { /// state"), we allow the caller to set an offset applied to our liquidity bounds which /// represents the amount of the successful payment we just made. fn update_history_buckets(&mut self, bucket_offset_msat: u64, duration_since_epoch: Duration) { - let half_lives = - duration_since_epoch.checked_sub(*self.offset_history_last_updated) - .unwrap_or(Duration::ZERO).as_secs() - .checked_div(self.decay_params.historical_no_updates_half_life.as_secs()) - .map(|v| v.try_into().unwrap_or(u32::max_value())).unwrap_or(u32::max_value()); - self.liquidity_history.min_liquidity_offset_history.time_decay_data(half_lives); - self.liquidity_history.max_liquidity_offset_history.time_decay_data(half_lives); - - let min_liquidity_offset_msat = self.decayed_offset_msat(*self.min_liquidity_offset_msat); self.liquidity_history.min_liquidity_offset_history.track_datapoint( - min_liquidity_offset_msat + bucket_offset_msat, self.capacity_msat + *self.min_liquidity_offset_msat + bucket_offset_msat, self.capacity_msat ); - let max_liquidity_offset_msat = self.decayed_offset_msat(*self.max_liquidity_offset_msat); self.liquidity_history.max_liquidity_offset_history.track_datapoint( - max_liquidity_offset_msat.saturating_sub(bucket_offset_msat), self.capacity_msat + self.max_liquidity_offset_msat.saturating_sub(bucket_offset_msat), self.capacity_msat ); *self.offset_history_last_updated = duration_since_epoch; } @@ -1351,7 +1314,7 @@ DirectedChannelLiquidity { } } -impl>, L: Deref, T: Time> ScoreLookUp for ProbabilisticScorerUsingTime where L::Target: Logger { +impl>, L: Deref> ScoreLookUp for ProbabilisticScorer where L::Target: Logger { type ScoreParams = ProbabilisticScoringFeeParameters; fn channel_penalty_msat( &self, candidate: &CandidateRouteHop, usage: ChannelUsage, score_params: &ProbabilisticScoringFeeParameters @@ -1395,14 +1358,14 @@ impl>, L: Deref, T: Time> ScoreLookUp for Prob self.channel_liquidities .get(&scid) .unwrap_or(&ChannelLiquidity::new(Duration::ZERO)) - .as_directed(&source, &target, capacity_msat, self.decay_params) + .as_directed(&source, &target, capacity_msat) .penalty_msat(amount_msat, score_params) .saturating_add(anti_probing_penalty_msat) .saturating_add(base_penalty_msat) } } -impl>, L: Deref, T: Time> ScoreUpdate for ProbabilisticScorerUsingTime where L::Target: Logger { +impl>, L: Deref> ScoreUpdate for ProbabilisticScorer where L::Target: Logger { fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) { let amount_msat = path.final_value_msat(); log_trace!(self.logger, "Scoring path through to SCID {} as having failed at {} msat", short_channel_id, amount_msat); @@ -1425,14 +1388,14 @@ impl>, L: Deref, T: Time> ScoreUpdate for Prob self.channel_liquidities .entry(hop.short_channel_id) .or_insert_with(|| ChannelLiquidity::new(duration_since_epoch)) - .as_directed_mut(source, &target, capacity_msat, self.decay_params) + .as_directed_mut(source, &target, capacity_msat) .failed_at_channel(amount_msat, duration_since_epoch, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger); } else { self.channel_liquidities .entry(hop.short_channel_id) .or_insert_with(|| ChannelLiquidity::new(duration_since_epoch)) - .as_directed_mut(source, &target, capacity_msat, self.decay_params) + .as_directed_mut(source, &target, capacity_msat) .failed_downstream(amount_msat, duration_since_epoch, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger); } @@ -1461,7 +1424,7 @@ impl>, L: Deref, T: Time> ScoreUpdate for Prob self.channel_liquidities .entry(hop.short_channel_id) .or_insert_with(|| ChannelLiquidity::new(duration_since_epoch)) - .as_directed_mut(source, &target, capacity_msat, self.decay_params) + .as_directed_mut(source, &target, capacity_msat) .successful(amount_msat, duration_since_epoch, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger); } else { @@ -1511,7 +1474,7 @@ impl>, L: Deref, T: Time> ScoreUpdate for Prob } #[cfg(c_bindings)] -impl>, L: Deref, T: Time> Score for ProbabilisticScorerUsingTime +impl>, L: Deref> Score for ProbabilisticScorer where L::Target: Logger {} #[cfg(feature = "std")] @@ -1985,14 +1948,6 @@ mod bucketed_history { self.buckets[bucket] = self.buckets[bucket].saturating_add(BUCKET_FIXED_POINT_ONE); } } - /// Decay all buckets by the given number of half-lives. Used to more aggressively remove old - /// datapoints as we receive newer information. - #[inline] - pub(super) fn time_decay_data(&mut self, half_lives: u32) { - for e in self.buckets.iter_mut() { - *e = e.checked_shr(half_lives).unwrap_or(0); - } - } } impl_writeable_tlv_based!(HistoricalBucketRangeTracker, { (0, buckets, required) }); @@ -2097,7 +2052,7 @@ mod bucketed_history { } use bucketed_history::{LegacyHistoricalBucketRangeTracker, HistoricalBucketRangeTracker, HistoricalMinMaxBuckets}; -impl>, L: Deref, T: Time> Writeable for ProbabilisticScorerUsingTime where L::Target: Logger { +impl>, L: Deref> Writeable for ProbabilisticScorer where L::Target: Logger { #[inline] fn write(&self, w: &mut W) -> Result<(), io::Error> { write_tlv_fields!(w, { @@ -2107,8 +2062,8 @@ impl>, L: Deref, T: Time> Writeable for Probab } } -impl>, L: Deref, T: Time> -ReadableArgs<(ProbabilisticScoringDecayParameters, G, L)> for ProbabilisticScorerUsingTime where L::Target: Logger { +impl>, L: Deref> +ReadableArgs<(ProbabilisticScoringDecayParameters, G, L)> for ProbabilisticScorer where L::Target: Logger { #[inline] fn read( r: &mut R, args: (ProbabilisticScoringDecayParameters, G, L) @@ -2123,7 +2078,6 @@ ReadableArgs<(ProbabilisticScoringDecayParameters, G, L)> for ProbabilisticScore network_graph, logger, channel_liquidities, - _unused_time: core::marker::PhantomData, }) } } @@ -2194,10 +2148,9 @@ impl Readable for ChannelLiquidity { #[cfg(test)] mod tests { - use super::{ChannelLiquidity, HistoricalBucketRangeTracker, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters, ProbabilisticScorerUsingTime}; + use super::{ChannelLiquidity, HistoricalBucketRangeTracker, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters, ProbabilisticScorer}; use crate::blinded_path::{BlindedHop, BlindedPath}; use crate::util::config::UserConfig; - use crate::util::time::tests::SinceEpoch; use crate::ln::channelmanager; use crate::ln::msgs::{ChannelAnnouncement, ChannelUpdate, UnsignedChannelAnnouncement, UnsignedChannelUpdate}; @@ -2243,9 +2196,6 @@ mod tests { // `ProbabilisticScorer` tests - /// A probabilistic scorer for testing with time that can be manually advanced. - type ProbabilisticScorer<'a> = ProbabilisticScorerUsingTime::<&'a NetworkGraph<&'a TestLogger>, &'a TestLogger, SinceEpoch>; - fn sender_privkey() -> SecretKey { SecretKey::from_slice(&[41; 32]).unwrap() } @@ -2389,52 +2339,52 @@ mod tests { // Update minimum liquidity. let liquidity = scorer.channel_liquidities.get(&42).unwrap() - .as_directed(&source, &target, 1_000, decay_params); + .as_directed(&source, &target, 1_000); assert_eq!(liquidity.min_liquidity_msat(), 100); assert_eq!(liquidity.max_liquidity_msat(), 300); let liquidity = scorer.channel_liquidities.get(&42).unwrap() - .as_directed(&target, &source, 1_000, decay_params); + .as_directed(&target, &source, 1_000); assert_eq!(liquidity.min_liquidity_msat(), 700); assert_eq!(liquidity.max_liquidity_msat(), 900); scorer.channel_liquidities.get_mut(&42).unwrap() - .as_directed_mut(&source, &target, 1_000, decay_params) + .as_directed_mut(&source, &target, 1_000) .set_min_liquidity_msat(200, Duration::ZERO); let liquidity = scorer.channel_liquidities.get(&42).unwrap() - .as_directed(&source, &target, 1_000, decay_params); + .as_directed(&source, &target, 1_000); assert_eq!(liquidity.min_liquidity_msat(), 200); assert_eq!(liquidity.max_liquidity_msat(), 300); let liquidity = scorer.channel_liquidities.get(&42).unwrap() - .as_directed(&target, &source, 1_000, decay_params); + .as_directed(&target, &source, 1_000); assert_eq!(liquidity.min_liquidity_msat(), 700); assert_eq!(liquidity.max_liquidity_msat(), 800); // Update maximum liquidity. let liquidity = scorer.channel_liquidities.get(&43).unwrap() - .as_directed(&target, &recipient, 1_000, decay_params); + .as_directed(&target, &recipient, 1_000); assert_eq!(liquidity.min_liquidity_msat(), 700); assert_eq!(liquidity.max_liquidity_msat(), 900); let liquidity = scorer.channel_liquidities.get(&43).unwrap() - .as_directed(&recipient, &target, 1_000, decay_params); + .as_directed(&recipient, &target, 1_000); assert_eq!(liquidity.min_liquidity_msat(), 100); assert_eq!(liquidity.max_liquidity_msat(), 300); scorer.channel_liquidities.get_mut(&43).unwrap() - .as_directed_mut(&target, &recipient, 1_000, decay_params) + .as_directed_mut(&target, &recipient, 1_000) .set_max_liquidity_msat(200, Duration::ZERO); let liquidity = scorer.channel_liquidities.get(&43).unwrap() - .as_directed(&target, &recipient, 1_000, decay_params); + .as_directed(&target, &recipient, 1_000); assert_eq!(liquidity.min_liquidity_msat(), 0); assert_eq!(liquidity.max_liquidity_msat(), 200); let liquidity = scorer.channel_liquidities.get(&43).unwrap() - .as_directed(&recipient, &target, 1_000, decay_params); + .as_directed(&recipient, &target, 1_000); assert_eq!(liquidity.min_liquidity_msat(), 800); assert_eq!(liquidity.max_liquidity_msat(), 1000); } @@ -2460,42 +2410,42 @@ mod tests { // Check initial bounds. let liquidity = scorer.channel_liquidities.get(&42).unwrap() - .as_directed(&source, &target, 1_000, decay_params); + .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, decay_params); + .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, decay_params) + .as_directed_mut(&source, &target, 1_000) .set_min_liquidity_msat(900, Duration::ZERO); let liquidity = scorer.channel_liquidities.get(&42).unwrap() - .as_directed(&source, &target, 1_000, decay_params); + .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, decay_params); + .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, decay_params) + .as_directed_mut(&target, &source, 1_000) .set_min_liquidity_msat(400, Duration::ZERO); let liquidity = scorer.channel_liquidities.get(&42).unwrap() - .as_directed(&source, &target, 1_000, decay_params); + .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, decay_params); + .as_directed(&target, &source, 1_000); assert_eq!(liquidity.min_liquidity_msat(), 400); assert_eq!(liquidity.max_liquidity_msat(), 1_000); } @@ -2521,42 +2471,42 @@ mod tests { // Check initial bounds. let liquidity = scorer.channel_liquidities.get(&42).unwrap() - .as_directed(&source, &target, 1_000, decay_params); + .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, decay_params); + .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, decay_params) + .as_directed_mut(&source, &target, 1_000) .set_max_liquidity_msat(300, Duration::ZERO); let liquidity = scorer.channel_liquidities.get(&42).unwrap() - .as_directed(&source, &target, 1_000, decay_params); + .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, decay_params); + .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, decay_params) + .as_directed_mut(&target, &source, 1_000) .set_max_liquidity_msat(600, Duration::ZERO); let liquidity = scorer.channel_liquidities.get(&42).unwrap() - .as_directed(&source, &target, 1_000, decay_params); + .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, decay_params); + .as_directed(&target, &source, 1_000); assert_eq!(liquidity.min_liquidity_msat(), 0); assert_eq!(liquidity.max_liquidity_msat(), 600); } @@ -2950,7 +2900,6 @@ mod tests { assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); // Half decay (i.e., three-quarter life) - SinceEpoch::advance(Duration::from_secs(5)); scorer.time_passed(Duration::from_secs(5)); let usage = ChannelUsage { amount_msat: 128, ..usage }; assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 22); @@ -2962,7 +2911,6 @@ mod tests { assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); // One decay (i.e., half life) - SinceEpoch::advance(Duration::from_secs(5)); scorer.time_passed(Duration::from_secs(10)); let usage = ChannelUsage { amount_msat: 64, ..usage }; assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0); @@ -2974,7 +2922,6 @@ mod tests { assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); // Fully decay liquidity lower bound. - SinceEpoch::advance(Duration::from_secs(10 * 7)); scorer.time_passed(Duration::from_secs(10 * 8)); let usage = ChannelUsage { amount_msat: 0, ..usage }; assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0); @@ -2986,14 +2933,12 @@ mod tests { assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); // Fully decay liquidity upper bound. - SinceEpoch::advance(Duration::from_secs(10)); scorer.time_passed(Duration::from_secs(10 * 9)); let usage = ChannelUsage { amount_msat: 0, ..usage }; assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0); let usage = ChannelUsage { amount_msat: 1_024, ..usage }; assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); - SinceEpoch::advance(Duration::from_secs(10)); scorer.time_passed(Duration::from_secs(10 * 10)); let usage = ChannelUsage { amount_msat: 0, ..usage }; assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0); @@ -3001,47 +2946,6 @@ mod tests { assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); } - #[test] - fn decays_liquidity_bounds_without_shift_overflow() { - let logger = TestLogger::new(); - let network_graph = network_graph(&logger); - let params = ProbabilisticScoringFeeParameters { - liquidity_penalty_multiplier_msat: 1_000, - ..ProbabilisticScoringFeeParameters::zero_penalty() - }; - let decay_params = ProbabilisticScoringDecayParameters { - liquidity_offset_half_life: Duration::from_secs(10), - ..ProbabilisticScoringDecayParameters::default() - }; - let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger); - let source = source_node_id(); - let usage = ChannelUsage { - amount_msat: 256, - inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 }, - }; - let channel = network_graph.read_only().channel(42).unwrap().to_owned(); - let (info, _) = channel.as_directed_from(&source).unwrap(); - let candidate = CandidateRouteHop::PublicHop { - info, - short_channel_id: 42, - }; - assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 125); - - scorer.payment_path_failed(&payment_path_for_amount(512), 42, Duration::ZERO); - assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 281); - - // An unchecked right shift 64 bits or more in DirectedChannelLiquidity::decayed_offset_msat - // would cause an overflow. - SinceEpoch::advance(Duration::from_secs(10 * 64)); - scorer.time_passed(Duration::from_secs(10 * 64)); - assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 125); - - SinceEpoch::advance(Duration::from_secs(10)); - scorer.time_passed(Duration::from_secs(10 * 65)); - assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 125); - } - #[test] fn restricts_liquidity_bounds_after_decay() { let logger = TestLogger::new(); @@ -3076,7 +2980,6 @@ mod tests { assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 281); // Decaying knowledge gives less confidence (128, 896), meaning a higher penalty. - SinceEpoch::advance(Duration::from_secs(10)); scorer.time_passed(Duration::from_secs(10)); assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 291); @@ -3091,7 +2994,6 @@ mod tests { assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 245); // Further decaying affects the lower bound more than the upper bound (128, 928). - SinceEpoch::advance(Duration::from_secs(10)); scorer.time_passed(Duration::from_secs(20)); assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 280); } @@ -3126,7 +3028,6 @@ mod tests { }; assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); - SinceEpoch::advance(Duration::from_secs(10)); scorer.time_passed(Duration::from_secs(10)); assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 473); @@ -3138,7 +3039,7 @@ mod tests { let mut serialized_scorer = io::Cursor::new(&serialized_scorer); let deserialized_scorer = - ::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap(); + >::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap(); assert_eq!(deserialized_scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300); } @@ -3172,7 +3073,6 @@ mod tests { assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); if decay_before_reload { - SinceEpoch::advance(Duration::from_secs(10)); scorer.time_passed(Duration::from_secs(10)); } @@ -3181,9 +3081,8 @@ mod tests { let mut serialized_scorer = io::Cursor::new(&serialized_scorer); let mut deserialized_scorer = - ::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap(); + >::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap(); if !decay_before_reload { - SinceEpoch::advance(Duration::from_secs(10)); scorer.time_passed(Duration::from_secs(10)); deserialized_scorer.time_passed(Duration::from_secs(10)); } @@ -3192,7 +3091,6 @@ mod tests { scorer.payment_path_failed(&payment_path_for_amount(250), 43, Duration::from_secs(10)); assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300); - SinceEpoch::advance(Duration::from_secs(10)); deserialized_scorer.time_passed(Duration::from_secs(20)); assert_eq!(deserialized_scorer.channel_penalty_msat(&candidate, usage, ¶ms), 370); } @@ -3526,7 +3424,6 @@ mod tests { // Advance the time forward 16 half-lives (which the docs claim will ensure all data is // gone), and check that we're back to where we started. - SinceEpoch::advance(Duration::from_secs(10 * 16)); scorer.time_passed(Duration::from_secs(10 * 16)); { let network_graph = network_graph.read_only(); @@ -3545,7 +3442,7 @@ mod tests { Some(([0; 32], [0; 32]))); assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 1, ¶ms), None); - let mut usage = ChannelUsage { + let usage = ChannelUsage { amount_msat: 100, inflight_htlc_msat: 1024, effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 }, @@ -3571,7 +3468,6 @@ mod tests { } // Advance to decay all liquidity offsets to zero. - SinceEpoch::advance(Duration::from_secs(60 * 60 * 10)); scorer.time_passed(Duration::from_secs(10 * (16 + 60 * 60))); // Once even the bounds have decayed information about the channel should be removed @@ -3690,7 +3586,7 @@ mod tests { scorer.payment_path_failed(&path, 43, Duration::ZERO); let liquidity = scorer.channel_liquidities.get(&42).unwrap() - .as_directed(&source, &target, 1_000, decay_params); + .as_directed(&source, &target, 1_000); assert_eq!(liquidity.min_liquidity_msat(), 256); assert_eq!(liquidity.max_liquidity_msat(), 768); } @@ -3773,3 +3669,61 @@ mod tests { Some(0.0)); } } + +#[cfg(ldk_bench)] +pub mod benches { + use super::*; + use criterion::Criterion; + use crate::routing::router::{bench_utils, RouteHop}; + use crate::util::test_utils::TestLogger; + use crate::ln::features::{ChannelFeatures, NodeFeatures}; + + pub fn decay_100k_channel_bounds(bench: &mut Criterion) { + let logger = TestLogger::new(); + let network_graph = bench_utils::read_network_graph(&logger).unwrap(); + let mut scorer = ProbabilisticScorer::new(Default::default(), &network_graph, &logger); + // Score a number of random channels + let mut seed: u64 = 0xdeadbeef; + for _ in 0..100_000 { + seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0; + let (victim, victim_dst, amt) = { + let rong = network_graph.read_only(); + let channels = rong.channels(); + let chan = channels.unordered_iter() + .skip((seed as usize) % channels.len()) + .next().unwrap(); + seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0; + let amt = seed % chan.1.capacity_sats.map(|c| c * 1000) + .or(chan.1.one_to_two.as_ref().map(|info| info.htlc_maximum_msat)) + .or(chan.1.two_to_one.as_ref().map(|info| info.htlc_maximum_msat)) + .unwrap_or(1_000_000_000).saturating_add(1); + (*chan.0, chan.1.node_two, amt) + }; + let path = Path { + hops: vec![RouteHop { + pubkey: victim_dst.as_pubkey().unwrap(), + node_features: NodeFeatures::empty(), + short_channel_id: victim, + channel_features: ChannelFeatures::empty(), + fee_msat: amt, + cltv_expiry_delta: 42, + maybe_announced_channel: true, + }], + blinded_tail: None + }; + seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0; + if seed % 1 == 0 { + scorer.probe_failed(&path, victim, Duration::ZERO); + } else { + scorer.probe_successful(&path, Duration::ZERO); + } + } + let mut cur_time = Duration::ZERO; + cur_time += Duration::from_millis(1); + scorer.time_passed(cur_time); + bench.bench_function("decay_100k_channel_bounds", |b| b.iter(|| { + cur_time += Duration::from_millis(1); + scorer.time_passed(cur_time); + })); + } +}