X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Fscoring.rs;h=42a565aee95b908b4a60ddf6c99b10ba98899987;hb=d8748b05c5ae3917656a5debc77e14a7767225c6;hp=04c405b036dd7c63f5a891815af108bcd885398c;hpb=df52da7b31494c7ec77a705cca4c44bc840f8a95;p=rust-lightning diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index 04c405b0..42a565ae 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -26,7 +26,7 @@ //! # //! # struct FakeLogger {}; //! # impl Logger for FakeLogger { -//! # fn log(&self, record: &Record) { unimplemented!() } +//! # fn log(&self, record: Record) { unimplemented!() } //! # } //! # fn find_scored_route(payer: PublicKey, route_params: RouteParameters, network_graph: NetworkGraph<&FakeLogger>) { //! # let logger = FakeLogger {}; @@ -58,10 +58,10 @@ use crate::ln::msgs::DecodeError; use crate::routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId}; -use crate::routing::router::Path; +use crate::routing::router::{Path, CandidateRouteHop}; +use crate::routing::log_approx; 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}; @@ -89,7 +89,7 @@ macro_rules! define_score { ($($supertrait: path)*) => { /// `ScoreLookUp` is used to determine the penalty for a given channel. /// /// Scoring is in terms of fees willing to be paid in order to avoid routing through a channel. -pub trait ScoreLookUp $(: $supertrait)* { +pub trait ScoreLookUp { /// A configurable type which should contain various passed-in parameters for configuring the scorer, /// on a per-routefinding-call basis through to the scorer methods, /// which are used to determine the parameters for the suitability of channels for use. @@ -103,49 +103,72 @@ pub trait ScoreLookUp $(: $supertrait)* { /// [`u64::max_value`] is given to indicate sufficient capacity for the invoice's full amount. /// Thus, implementations should be overflow-safe. fn channel_penalty_msat( - &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage, score_params: &Self::ScoreParams + &self, candidate: &CandidateRouteHop, usage: ChannelUsage, score_params: &Self::ScoreParams ) -> u64; } /// `ScoreUpdate` is used to update the scorer's internal state after a payment attempt. -pub trait ScoreUpdate $(: $supertrait)* { +pub trait ScoreUpdate { /// Handles updating channel penalties after failing to route through a channel. - fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64); + fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration); /// Handles updating channel penalties after successfully routing along a path. - fn payment_path_successful(&mut self, path: &Path); + fn payment_path_successful(&mut self, path: &Path, duration_since_epoch: Duration); /// Handles updating channel penalties after a probe over the given path failed. - fn probe_failed(&mut self, path: &Path, short_channel_id: u64); + fn probe_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration); /// Handles updating channel penalties after a probe over the given path succeeded. - fn probe_successful(&mut self, path: &Path); + fn probe_successful(&mut self, path: &Path, duration_since_epoch: Duration); + + /// Scorers may wish to reduce their certainty of channel liquidity information over time. + /// Thus, this method is provided to allow scorers to observe the passage of time - the holder + /// of this object should call this method regularly (generally via the + /// `lightning-background-processor` crate). + fn decay_liquidity_certainty(&mut self, duration_since_epoch: Duration); } -impl, T: Deref $(+ $supertrait)*> ScoreLookUp for T { - type ScoreParams = SP; +/// A trait which can both lookup and update routing channel penalty scores. +/// +/// This is used in places where both bounds are required and implemented for all types which +/// implement [`ScoreLookUp`] and [`ScoreUpdate`]. +/// +/// Bindings users may need to manually implement this for their custom scoring implementations. +pub trait Score : ScoreLookUp + ScoreUpdate $(+ $supertrait)* {} + +#[cfg(not(c_bindings))] +impl Score for T {} + +#[cfg(not(c_bindings))] +impl> ScoreLookUp for T { + type ScoreParams = S::ScoreParams; fn channel_penalty_msat( - &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage, score_params: &Self::ScoreParams + &self, candidate: &CandidateRouteHop, usage: ChannelUsage, score_params: &Self::ScoreParams ) -> u64 { - self.deref().channel_penalty_msat(short_channel_id, source, target, usage, score_params) + self.deref().channel_penalty_msat(candidate, usage, score_params) } } -impl $(+ $supertrait)*> ScoreUpdate for T { - fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64) { - self.deref_mut().payment_path_failed(path, short_channel_id) +#[cfg(not(c_bindings))] +impl> ScoreUpdate for T { + fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) { + self.deref_mut().payment_path_failed(path, short_channel_id, duration_since_epoch) + } + + fn payment_path_successful(&mut self, path: &Path, duration_since_epoch: Duration) { + self.deref_mut().payment_path_successful(path, duration_since_epoch) } - fn payment_path_successful(&mut self, path: &Path) { - self.deref_mut().payment_path_successful(path) + fn probe_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) { + self.deref_mut().probe_failed(path, short_channel_id, duration_since_epoch) } - fn probe_failed(&mut self, path: &Path, short_channel_id: u64) { - self.deref_mut().probe_failed(path, short_channel_id) + fn probe_successful(&mut self, path: &Path, duration_since_epoch: Duration) { + self.deref_mut().probe_successful(path, duration_since_epoch) } - fn probe_successful(&mut self, path: &Path) { - self.deref_mut().probe_successful(path) + fn decay_liquidity_certainty(&mut self, duration_since_epoch: Duration) { + self.deref_mut().decay_liquidity_certainty(duration_since_epoch) } } } } @@ -192,7 +215,7 @@ pub trait WriteableScore<'a>: LockableScore<'a> + Writeable {} #[cfg(not(c_bindings))] impl<'a, T> WriteableScore<'a> for T where T: LockableScore<'a> + Writeable {} #[cfg(not(c_bindings))] -impl<'a, T: 'a + ScoreLookUp + ScoreUpdate> LockableScore<'a> for Mutex { +impl<'a, T: Score + 'a> LockableScore<'a> for Mutex { type ScoreUpdate = T; type ScoreLookUp = T; @@ -209,7 +232,7 @@ impl<'a, T: 'a + ScoreLookUp + ScoreUpdate> LockableScore<'a> for Mutex { } #[cfg(not(c_bindings))] -impl<'a, T: 'a + ScoreUpdate + ScoreLookUp> LockableScore<'a> for RefCell { +impl<'a, T: Score + 'a> LockableScore<'a> for RefCell { type ScoreUpdate = T; type ScoreLookUp = T; @@ -226,7 +249,7 @@ impl<'a, T: 'a + ScoreUpdate + ScoreLookUp> LockableScore<'a> for RefCell { } #[cfg(not(c_bindings))] -impl<'a, SP:Sized, T: 'a + ScoreUpdate + ScoreLookUp> LockableScore<'a> for RwLock { +impl<'a, T: Score + 'a> LockableScore<'a> for RwLock { type ScoreUpdate = T; type ScoreLookUp = T; @@ -244,12 +267,12 @@ impl<'a, SP:Sized, T: 'a + ScoreUpdate + ScoreLookUp> Lockabl #[cfg(c_bindings)] /// A concrete implementation of [`LockableScore`] which supports multi-threading. -pub struct MultiThreadedLockableScore { +pub struct MultiThreadedLockableScore { score: RwLock, } #[cfg(c_bindings)] -impl<'a, SP:Sized, T: 'a + ScoreLookUp + ScoreUpdate> LockableScore<'a> for MultiThreadedLockableScore { +impl<'a, T: Score + 'a> LockableScore<'a> for MultiThreadedLockableScore { type ScoreUpdate = T; type ScoreLookUp = T; type WriteLocked = MultiThreadedScoreLockWrite<'a, Self::ScoreUpdate>; @@ -265,17 +288,17 @@ impl<'a, SP:Sized, T: 'a + ScoreLookUp + ScoreUpdate> Lockable } #[cfg(c_bindings)] -impl Writeable for MultiThreadedLockableScore { +impl Writeable for MultiThreadedLockableScore { fn write(&self, writer: &mut W) -> Result<(), io::Error> { self.score.read().unwrap().write(writer) } } #[cfg(c_bindings)] -impl<'a, T: 'a + ScoreUpdate + ScoreLookUp> WriteableScore<'a> for MultiThreadedLockableScore {} +impl<'a, T: Score + 'a> WriteableScore<'a> for MultiThreadedLockableScore {} #[cfg(c_bindings)] -impl MultiThreadedLockableScore { +impl MultiThreadedLockableScore { /// Creates a new [`MultiThreadedLockableScore`] given an underlying [`Score`]. pub fn new(score: T) -> Self { MultiThreadedLockableScore { score: RwLock::new(score) } @@ -284,14 +307,14 @@ impl MultiThreadedLockableScore { #[cfg(c_bindings)] /// A locked `MultiThreadedLockableScore`. -pub struct MultiThreadedScoreLockRead<'a, T: ScoreLookUp>(RwLockReadGuard<'a, T>); +pub struct MultiThreadedScoreLockRead<'a, T: Score>(RwLockReadGuard<'a, T>); #[cfg(c_bindings)] /// A locked `MultiThreadedLockableScore`. -pub struct MultiThreadedScoreLockWrite<'a, T: ScoreUpdate>(RwLockWriteGuard<'a, T>); +pub struct MultiThreadedScoreLockWrite<'a, T: Score>(RwLockWriteGuard<'a, T>); #[cfg(c_bindings)] -impl<'a, T: 'a + ScoreLookUp> Deref for MultiThreadedScoreLockRead<'a, T> { +impl<'a, T: 'a + Score> Deref for MultiThreadedScoreLockRead<'a, T> { type Target = T; fn deref(&self) -> &Self::Target { @@ -300,14 +323,23 @@ impl<'a, T: 'a + ScoreLookUp> Deref for MultiThreadedScoreLockRead<'a, T> { } #[cfg(c_bindings)] -impl<'a, T: 'a + ScoreUpdate> Writeable for MultiThreadedScoreLockWrite<'a, T> { +impl<'a, T: Score> ScoreLookUp for MultiThreadedScoreLockRead<'a, T> { + type ScoreParams = T::ScoreParams; + fn channel_penalty_msat(&self, candidate:&CandidateRouteHop, usage: ChannelUsage, score_params: &Self::ScoreParams + ) -> u64 { + self.0.channel_penalty_msat(candidate, usage, score_params) + } +} + +#[cfg(c_bindings)] +impl<'a, T: Score> Writeable for MultiThreadedScoreLockWrite<'a, T> { fn write(&self, writer: &mut W) -> Result<(), io::Error> { self.0.write(writer) } } #[cfg(c_bindings)] -impl<'a, T: 'a + ScoreUpdate> Deref for MultiThreadedScoreLockWrite<'a, T> { +impl<'a, T: 'a + Score> Deref for MultiThreadedScoreLockWrite<'a, T> { type Target = T; fn deref(&self) -> &Self::Target { @@ -316,12 +348,35 @@ impl<'a, T: 'a + ScoreUpdate> Deref for MultiThreadedScoreLockWrite<'a, T> { } #[cfg(c_bindings)] -impl<'a, T: 'a + ScoreUpdate> DerefMut for MultiThreadedScoreLockWrite<'a, T> { +impl<'a, T: 'a + Score> DerefMut for MultiThreadedScoreLockWrite<'a, T> { fn deref_mut(&mut self) -> &mut Self::Target { self.0.deref_mut() } } +#[cfg(c_bindings)] +impl<'a, T: Score> ScoreUpdate for MultiThreadedScoreLockWrite<'a, T> { + fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) { + self.0.payment_path_failed(path, short_channel_id, duration_since_epoch) + } + + fn payment_path_successful(&mut self, path: &Path, duration_since_epoch: Duration) { + self.0.payment_path_successful(path, duration_since_epoch) + } + + fn probe_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) { + self.0.probe_failed(path, short_channel_id, duration_since_epoch) + } + + fn probe_successful(&mut self, path: &Path, duration_since_epoch: Duration) { + self.0.probe_successful(path, duration_since_epoch) + } + + fn decay_liquidity_certainty(&mut self, duration_since_epoch: Duration) { + self.0.decay_liquidity_certainty(duration_since_epoch) + } +} + /// Proposed use of a channel passed as a parameter to [`ScoreLookUp::channel_penalty_msat`]. #[derive(Clone, Copy, Debug, PartialEq)] @@ -352,19 +407,21 @@ impl FixedPenaltyScorer { impl ScoreLookUp for FixedPenaltyScorer { type ScoreParams = (); - fn channel_penalty_msat(&self, _: u64, _: &NodeId, _: &NodeId, _: ChannelUsage, _score_params: &Self::ScoreParams) -> u64 { + fn channel_penalty_msat(&self, _: &CandidateRouteHop, _: ChannelUsage, _score_params: &Self::ScoreParams) -> u64 { self.penalty_msat } } impl ScoreUpdate for FixedPenaltyScorer { - fn payment_path_failed(&mut self, _path: &Path, _short_channel_id: u64) {} + fn payment_path_failed(&mut self, _path: &Path, _short_channel_id: u64, _duration_since_epoch: Duration) {} - fn payment_path_successful(&mut self, _path: &Path) {} + fn payment_path_successful(&mut self, _path: &Path, _duration_since_epoch: Duration) {} - fn probe_failed(&mut self, _path: &Path, _short_channel_id: u64) {} + fn probe_failed(&mut self, _path: &Path, _short_channel_id: u64, _duration_since_epoch: Duration) {} - fn probe_successful(&mut self, _path: &Path) {} + fn probe_successful(&mut self, _path: &Path, _duration_since_epoch: Duration) {} + + fn decay_liquidity_certainty(&mut self, _duration_since_epoch: Duration) {} } impl Writeable for FixedPenaltyScorer { @@ -383,13 +440,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, @@ -415,29 +465,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, - // TODO: Remove entries of closed channels. - channel_liquidities: HashMap>, + channel_liquidities: HashMap, } /// Parameters for configuring [`ProbabilisticScorer`]. @@ -580,6 +619,28 @@ pub struct ProbabilisticScoringFeeParameters { /// [`base_penalty_msat`]: Self::base_penalty_msat /// [`anti_probing_penalty_msat`]: Self::anti_probing_penalty_msat pub considered_impossible_penalty_msat: u64, + + /// In order to calculate most of the scores above, we must first convert a lower and upper + /// bound on the available liquidity in a channel into the probability that we think a payment + /// will succeed. That probability is derived from a Probability Density Function for where we + /// think the liquidity in a channel likely lies, given such bounds. + /// + /// If this flag is set, that PDF is simply a constant - we assume that the actual available + /// liquidity in a channel is just as likely to be at any point between our lower and upper + /// bounds. + /// + /// If this flag is *not* set, that PDF is `(x - 0.5*capacity) ^ 2`. That is, we use an + /// exponential curve which expects the liquidity of a channel to lie "at the edges". This + /// matches experimental results - most routing nodes do not aggressively rebalance their + /// channels and flows in the network are often unbalanced, leaving liquidity usually + /// unavailable. + /// + /// Thus, for the "best" routes, leave this flag `false`. However, the flag does imply a number + /// of floating-point multiplications in the hottest routing code, which may lead to routing + /// performance degradation on some machines. + /// + /// Default value: false + pub linear_success_probability: bool, } impl Default for ProbabilisticScoringFeeParameters { @@ -594,6 +655,7 @@ impl Default for ProbabilisticScoringFeeParameters { considered_impossible_penalty_msat: 1_0000_0000_000, historical_liquidity_penalty_multiplier_msat: 10_000, historical_liquidity_penalty_amount_multiplier_msat: 64, + linear_success_probability: false, } } } @@ -647,6 +709,7 @@ impl ProbabilisticScoringFeeParameters { manual_node_penalties: HashMap::new(), anti_probing_penalty_msat: 0, considered_impossible_penalty_msat: 0, + linear_success_probability: true, } } } @@ -668,7 +731,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, @@ -717,33 +780,35 @@ impl ProbabilisticScoringDecayParameters { /// Direction is defined in terms of [`NodeId`] partial ordering, where the source node is the /// first node in the ordering of the channel's counterparties. Thus, swapping the two liquidity /// offset fields gives the opposite direction. -struct ChannelLiquidity { +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, - /// Time when the liquidity bounds were last modified. - last_updated: T, + liquidity_history: HistoricalLiquidityTracker, - 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. + last_updated: Duration, + + /// Time when the historical liquidity bounds were last modified as an offset against the unix + /// epoch. + offset_history_last_updated: Duration, } /// A snapshot of [`ChannelLiquidity`] in one direction assuming a certain channel capacity and /// decayed with a given half life. -struct DirectedChannelLiquidity, BRT: Deref, T: Time, U: Deref> { +struct DirectedChannelLiquidity, HT: Deref, T: Deref> { min_liquidity_offset_msat: L, max_liquidity_offset_msat: L, - liquidity_history: HistoricalMinMaxBuckets, + liquidity_history: DirectedHistoricalLiquidityTracker, capacity_msat: u64, - last_updated: U, - now: T, - decay_params: ProbabilisticScoringDecayParameters, + last_updated: T, + offset_history_last_updated: T, } -impl>, 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 { @@ -756,7 +821,7 @@ impl>, L: Deref, T: Time> ProbabilisticScorerU } #[cfg(test)] - fn with_channel(mut self, short_channel_id: u64, liquidity: ChannelLiquidity) -> Self { + fn with_channel(mut self, short_channel_id: u64, liquidity: ChannelLiquidity) -> Self { assert!(self.channel_liquidities.insert(short_channel_id, liquidity).is_none()); self } @@ -766,20 +831,16 @@ impl>, L: Deref, T: Time> ProbabilisticScorerU /// Note that this writes roughly one line per channel for which we have a liquidity estimate, /// which may be a substantial amount of log output. pub fn debug_log_liquidity_stats(&self) { - let now = T::now(); - let graph = self.network_graph.read_only(); for (scid, liq) in self.channel_liquidities.iter() { if let Some(chan_debug) = graph.channels().get(scid) { 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, max_buckets) = dir_liq.liquidity_history - .get_decayed_buckets(now, *dir_liq.last_updated, - self.decay_params.historical_no_updates_half_life) - .unwrap_or(([0; 32], [0; 32])); + let min_buckets = &dir_liq.liquidity_history.min_liquidity_offset_history_buckets(); + let max_buckets = &dir_liq.liquidity_history.max_liquidity_offset_history_buckets(); log_debug!(self.logger, core::concat!( "Liquidity from {} to {} via {} is in the range ({}, {}).\n", @@ -828,7 +889,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())); } } @@ -858,7 +919,7 @@ impl>, L: Deref, T: Time> ProbabilisticScorerU /// in the top and bottom bucket, and roughly with similar (recent) frequency. /// /// Because the datapoints are decayed slowly over time, values will eventually return to - /// `Some(([1; 32], [1; 32]))` and then to `None` once no datapoints remain. + /// `Some(([0; 32], [0; 32]))` or `None` if no data remains for a channel. /// /// In order to fetch a single success probability from the buckets provided here, as used in /// the scoring model, see [`Self::historical_estimated_payment_success_probability`]. @@ -870,13 +931,10 @@ 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, mut max_buckets) = - dir_liq.liquidity_history.get_decayed_buckets( - dir_liq.now, *dir_liq.last_updated, - self.decay_params.historical_no_updates_half_life - )?; + 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(); // Note that the liquidity buckets are an offset from the edge, so we inverse // the max order to get the probabilities from zero. @@ -904,12 +962,10 @@ 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( - dir_liq.now, *dir_liq.last_updated, - self.decay_params.historical_no_updates_half_life, ¶ms, amount_msat, - capacity_msat + ¶ms, amount_msat, capacity_msat ).map(|p| p as f64 / (1024 * 1024 * 1024) as f64); } } @@ -918,71 +974,72 @@ impl>, L: Deref, T: Time> ProbabilisticScorerU } } -impl ChannelLiquidity { - #[inline] - fn new() -> Self { +impl ChannelLiquidity { + fn new(last_updated: Duration) -> Self { Self { min_liquidity_offset_msat: 0, max_liquidity_offset_msat: 0, - min_liquidity_offset_history: HistoricalBucketRangeTracker::new(), - max_liquidity_offset_history: HistoricalBucketRangeTracker::new(), - last_updated: T::now(), + liquidity_history: HistoricalLiquidityTracker::new(), + last_updated, + offset_history_last_updated: last_updated, } } /// 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 - ) -> DirectedChannelLiquidity<&u64, &HistoricalBucketRangeTracker, T, &T> { - let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) = - if source < target { - (&self.min_liquidity_offset_msat, &self.max_liquidity_offset_msat, - &self.min_liquidity_offset_history, &self.max_liquidity_offset_history) + &self, source: &NodeId, target: &NodeId, capacity_msat: u64, + ) -> DirectedChannelLiquidity<&u64, &HistoricalLiquidityTracker, &Duration> { + let source_less_than_target = source < target; + let (min_liquidity_offset_msat, max_liquidity_offset_msat) = + if source_less_than_target { + (&self.min_liquidity_offset_msat, &self.max_liquidity_offset_msat) } else { - (&self.max_liquidity_offset_msat, &self.min_liquidity_offset_msat, - &self.max_liquidity_offset_history, &self.min_liquidity_offset_history) + (&self.max_liquidity_offset_msat, &self.min_liquidity_offset_msat) }; DirectedChannelLiquidity { min_liquidity_offset_msat, max_liquidity_offset_msat, - liquidity_history: HistoricalMinMaxBuckets { - min_liquidity_offset_history, - max_liquidity_offset_history, - }, + liquidity_history: self.liquidity_history.as_directed(source_less_than_target), capacity_msat, last_updated: &self.last_updated, - now: T::now(), - decay_params: decay_params, + offset_history_last_updated: &self.offset_history_last_updated, } } /// 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 - ) -> DirectedChannelLiquidity<&mut u64, &mut HistoricalBucketRangeTracker, T, &mut T> { - let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) = - if source < target { - (&mut self.min_liquidity_offset_msat, &mut self.max_liquidity_offset_msat, - &mut self.min_liquidity_offset_history, &mut self.max_liquidity_offset_history) + &mut self, source: &NodeId, target: &NodeId, capacity_msat: u64, + ) -> DirectedChannelLiquidity<&mut u64, &mut HistoricalLiquidityTracker, &mut Duration> { + let source_less_than_target = source < target; + let (min_liquidity_offset_msat, max_liquidity_offset_msat) = + if source_less_than_target { + (&mut self.min_liquidity_offset_msat, &mut self.max_liquidity_offset_msat) } else { - (&mut self.max_liquidity_offset_msat, &mut self.min_liquidity_offset_msat, - &mut self.max_liquidity_offset_history, &mut self.min_liquidity_offset_history) + (&mut self.max_liquidity_offset_msat, &mut self.min_liquidity_offset_msat) }; DirectedChannelLiquidity { min_liquidity_offset_msat, max_liquidity_offset_msat, - liquidity_history: HistoricalMinMaxBuckets { - min_liquidity_offset_history, - max_liquidity_offset_history, - }, + liquidity_history: self.liquidity_history.as_directed_mut(source_less_than_target), capacity_msat, last_updated: &mut self.last_updated, - now: T::now(), - decay_params: decay_params, + offset_history_last_updated: &mut self.offset_history_last_updated, + } + } + + fn decayed_offset(&self, offset: u64, duration_since_epoch: Duration, + decay_params: ProbabilisticScoringDecayParameters + ) -> u64 { + let half_life = decay_params.liquidity_offset_half_life.as_secs_f64(); + if half_life != 0.0 { + let elapsed_time = duration_since_epoch.saturating_sub(self.last_updated).as_secs_f64(); + ((offset as f64) * powf64(0.5, elapsed_time / half_life)) as u64 + } else { + 0 } } } @@ -993,12 +1050,18 @@ const NEGATIVE_LOG10_UPPER_BOUND: u64 = 2; /// The rough cutoff at which our precision falls off and we should stop bothering to try to log a /// ratio, as X in 1/X. -const PRECISION_LOWER_BOUND_DENOMINATOR: u64 = approx::LOWER_BITS_BOUND; +const PRECISION_LOWER_BOUND_DENOMINATOR: u64 = log_approx::LOWER_BITS_BOUND; /// The divisor used when computing the amount penalty. const AMOUNT_PENALTY_DIVISOR: u64 = 1 << 20; const BASE_AMOUNT_PENALTY_DIVISOR: u64 = 1 << 30; +/// Raises three `f64`s to the 3rd power, without `powi` because it requires `std` (dunno why). +#[inline(always)] +fn three_f64_pow_3(a: f64, b: f64, c: f64) -> (f64, f64, f64) { + (a * a * a, b * b * b, c * c * c) +} + /// Given liquidity bounds, calculates the success probability (in the form of a numerator and /// denominator) of an HTLC. This is a key assumption in our scoring models. /// @@ -1009,14 +1072,46 @@ const BASE_AMOUNT_PENALTY_DIVISOR: u64 = 1 << 30; #[inline(always)] fn success_probability( amount_msat: u64, min_liquidity_msat: u64, max_liquidity_msat: u64, capacity_msat: u64, - _params: &ProbabilisticScoringFeeParameters, min_zero_implies_no_successes: bool, + params: &ProbabilisticScoringFeeParameters, min_zero_implies_no_successes: bool, ) -> (u64, u64) { debug_assert!(min_liquidity_msat <= amount_msat); debug_assert!(amount_msat < max_liquidity_msat); debug_assert!(max_liquidity_msat <= capacity_msat); - let numerator = max_liquidity_msat - amount_msat; - let mut denominator = (max_liquidity_msat - min_liquidity_msat).saturating_add(1); + let (numerator, mut denominator) = + if params.linear_success_probability { + (max_liquidity_msat - amount_msat, + (max_liquidity_msat - min_liquidity_msat).saturating_add(1)) + } else { + let capacity = capacity_msat as f64; + let min = (min_liquidity_msat as f64) / capacity; + let max = (max_liquidity_msat as f64) / capacity; + let amount = (amount_msat as f64) / capacity; + + // Assume the channel has a probability density function of (x - 0.5)^2 for values from + // 0 to 1 (where 1 is the channel's full capacity). The success probability given some + // liquidity bounds is thus the integral under the curve from the amount to maximum + // estimated liquidity, divided by the same integral from the minimum to the maximum + // estimated liquidity bounds. + // + // Because the integral from x to y is simply (y - 0.5)^3 - (x - 0.5)^3, we can + // calculate the cumulative density function between the min/max bounds trivially. Note + // that we don't bother to normalize the CDF to total to 1, as it will come out in the + // division of num / den. + let (max_pow, amt_pow, min_pow) = three_f64_pow_3(max - 0.5, amount - 0.5, min - 0.5); + let num = max_pow - amt_pow; + let den = max_pow - min_pow; + + // Because our numerator and denominator max out at 0.5^3 we need to multiply them by + // quite a large factor to get something useful (ideally in the 2^30 range). + const BILLIONISH: f64 = 1024.0 * 1024.0 * 1024.0; + let numerator = (num * BILLIONISH) as u64 + 1; + let denominator = (den * BILLIONISH) as u64 + 1; + debug_assert!(numerator <= 1 << 30, "Got large numerator ({}) from float {}.", numerator, num); + debug_assert!(denominator <= 1 << 30, "Got large denominator ({}) from float {}.", denominator, den); + (numerator, denominator) + }; + if min_zero_implies_no_successes && min_liquidity_msat == 0 && denominator < u64::max_value() / 21 { @@ -1030,7 +1125,8 @@ fn success_probability( (numerator, denominator) } -impl, BRT: Deref, T: Time, U: Deref> DirectedChannelLiquidity< L, BRT, T, U> { +impl, HT: Deref, T: Deref> +DirectedChannelLiquidity< L, HT, T> { /// Returns a liquidity penalty for routing the given HTLC `amount_msat` through the channel in /// this direction. fn penalty_msat(&self, amount_msat: u64, score_params: &ProbabilisticScoringFeeParameters) -> u64 { @@ -1059,7 +1155,7 @@ impl, BRT: Deref, 0 } else { let negative_log10_times_2048 = - approx::negative_log10_times_2048(numerator, denominator); + log_approx::negative_log10_times_2048(numerator, denominator); Self::combined_penalty_msat(amount_msat, negative_log10_times_2048, score_params.liquidity_penalty_multiplier_msat, score_params.liquidity_penalty_amount_multiplier_msat) @@ -1078,11 +1174,11 @@ impl, BRT: Deref, if score_params.historical_liquidity_penalty_multiplier_msat != 0 || score_params.historical_liquidity_penalty_amount_multiplier_msat != 0 { if let Some(cumulative_success_prob_times_billion) = self.liquidity_history - .calculate_success_probability_times_billion(self.now, *self.last_updated, - self.decay_params.historical_no_updates_half_life, score_params, amount_msat, - self.capacity_msat) + .calculate_success_probability_times_billion( + score_params, amount_msat, self.capacity_msat) { - let historical_negative_log10_times_2048 = approx::negative_log10_times_2048(cumulative_success_prob_times_billion + 1, 1024 * 1024 * 1024); + let historical_negative_log10_times_2048 = + log_approx::negative_log10_times_2048(cumulative_success_prob_times_billion + 1, 1024 * 1024 * 1024); res = res.saturating_add(Self::combined_penalty_msat(amount_msat, historical_negative_log10_times_2048, score_params.historical_liquidity_penalty_multiplier_msat, score_params.historical_liquidity_penalty_amount_multiplier_msat)); @@ -1093,7 +1189,7 @@ impl, BRT: Deref, let (numerator, denominator) = success_probability(amount_msat, 0, available_capacity, available_capacity, score_params, true); let negative_log10_times_2048 = - approx::negative_log10_times_2048(numerator, denominator); + log_approx::negative_log10_times_2048(numerator, denominator); res = res.saturating_add(Self::combined_penalty_msat(amount_msat, negative_log10_times_2048, score_params.historical_liquidity_penalty_multiplier_msat, score_params.historical_liquidity_penalty_amount_multiplier_msat)); @@ -1124,124 +1220,104 @@ impl, BRT: Deref, /// 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 { - let half_life = self.decay_params.liquidity_offset_half_life.as_secs(); - if half_life != 0 { - // Decay the offset by the appropriate number of half lives. If half of the next half - // life has passed, approximate an additional three-quarter life to help smooth out the - // decay. - let elapsed_time = self.now.duration_since(*self.last_updated).as_secs(); - let half_decays = elapsed_time / (half_life / 2); - let decays = half_decays / 2; - let decayed_offset_msat = offset_msat.checked_shr(decays as u32).unwrap_or(0); - if half_decays % 2 == 0 { - decayed_offset_msat - } else { - // 11_585 / 16_384 ~= core::f64::consts::FRAC_1_SQRT_2 - // 16_384 == 2^14 - (decayed_offset_msat as u128 * 11_585 / 16_384) as u64 - } - } else { - 0 - } + .saturating_sub(*self.max_liquidity_offset_msat) } } -impl, BRT: DerefMut, T: Time, U: DerefMut> DirectedChannelLiquidity { +impl, HT: DerefMut, T: DerefMut> +DirectedChannelLiquidity { /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat`. - fn failed_at_channel(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger { + fn failed_at_channel( + &mut self, amount_msat: u64, duration_since_epoch: Duration, chan_descr: fmt::Arguments, logger: &Log + ) where Log::Target: Logger { let existing_max_msat = self.max_liquidity_msat(); if amount_msat < existing_max_msat { log_debug!(logger, "Setting max liquidity of {} from {} to {}", chan_descr, existing_max_msat, amount_msat); - self.set_max_liquidity_msat(amount_msat); + self.set_max_liquidity_msat(amount_msat, duration_since_epoch); } else { log_trace!(logger, "Max liquidity of {} is {} (already less than or equal to {})", chan_descr, existing_max_msat, amount_msat); } - self.update_history_buckets(0); + self.update_history_buckets(0, duration_since_epoch); } /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat` downstream. - fn failed_downstream(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger { + fn failed_downstream( + &mut self, amount_msat: u64, duration_since_epoch: Duration, chan_descr: fmt::Arguments, logger: &Log + ) where Log::Target: Logger { let existing_min_msat = self.min_liquidity_msat(); if amount_msat > existing_min_msat { log_debug!(logger, "Setting min liquidity of {} from {} to {}", existing_min_msat, chan_descr, amount_msat); - self.set_min_liquidity_msat(amount_msat); + self.set_min_liquidity_msat(amount_msat, duration_since_epoch); } else { log_trace!(logger, "Min liquidity of {} is {} (already greater than or equal to {})", chan_descr, existing_min_msat, amount_msat); } - self.update_history_buckets(0); + self.update_history_buckets(0, duration_since_epoch); } /// Adjusts the channel liquidity balance bounds when successfully routing `amount_msat`. - fn successful(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger { + fn successful(&mut self, + amount_msat: u64, duration_since_epoch: Duration, chan_descr: fmt::Arguments, logger: &Log + ) where Log::Target: Logger { let max_liquidity_msat = self.max_liquidity_msat().checked_sub(amount_msat).unwrap_or(0); log_debug!(logger, "Subtracting {} from max liquidity of {} (setting it to {})", amount_msat, chan_descr, max_liquidity_msat); - self.set_max_liquidity_msat(max_liquidity_msat); - self.update_history_buckets(amount_msat); + self.set_max_liquidity_msat(max_liquidity_msat, duration_since_epoch); + self.update_history_buckets(amount_msat, duration_since_epoch); } /// Updates the history buckets for this channel. Because the history buckets track what we now /// know about the channel's state *prior to our payment* (i.e. what we assume is "steady /// 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) { - let half_lives = self.now.duration_since(*self.last_updated).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 - ); - 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 + fn update_history_buckets(&mut self, bucket_offset_msat: u64, duration_since_epoch: Duration) { + self.liquidity_history.track_datapoint( + *self.min_liquidity_offset_msat + bucket_offset_msat, + self.max_liquidity_offset_msat.saturating_sub(bucket_offset_msat), + self.capacity_msat, ); + *self.offset_history_last_updated = duration_since_epoch; } /// Adjusts the lower bound of the channel liquidity balance in this direction. - fn set_min_liquidity_msat(&mut self, amount_msat: u64) { + fn set_min_liquidity_msat(&mut self, amount_msat: u64, duration_since_epoch: Duration) { *self.min_liquidity_offset_msat = amount_msat; - *self.max_liquidity_offset_msat = if amount_msat > self.max_liquidity_msat() { - 0 - } else { - self.decayed_offset_msat(*self.max_liquidity_offset_msat) - }; - *self.last_updated = self.now; + if amount_msat > self.max_liquidity_msat() { + *self.max_liquidity_offset_msat = 0; + } + *self.last_updated = duration_since_epoch; } /// Adjusts the upper bound of the channel liquidity balance in this direction. - fn set_max_liquidity_msat(&mut self, amount_msat: u64) { + fn set_max_liquidity_msat(&mut self, amount_msat: u64, duration_since_epoch: Duration) { *self.max_liquidity_offset_msat = self.capacity_msat.checked_sub(amount_msat).unwrap_or(0); - *self.min_liquidity_offset_msat = if amount_msat < self.min_liquidity_msat() { - 0 - } else { - self.decayed_offset_msat(*self.min_liquidity_offset_msat) - }; - *self.last_updated = self.now; + if amount_msat < *self.min_liquidity_offset_msat { + *self.min_liquidity_offset_msat = 0; + } + *self.last_updated = duration_since_epoch; } } -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, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage, score_params: &ProbabilisticScoringFeeParameters + &self, candidate: &CandidateRouteHop, usage: ChannelUsage, score_params: &ProbabilisticScoringFeeParameters ) -> u64 { - if let Some(penalty) = score_params.manual_node_penalties.get(target) { + let (scid, target) = match candidate { + CandidateRouteHop::PublicHop { info, short_channel_id } => { + (short_channel_id, info.target()) + }, + _ => return 0, + }; + let source = candidate.source(); + if let Some(penalty) = score_params.manual_node_penalties.get(&target) { return *penalty; } @@ -1271,17 +1347,17 @@ impl>, L: Deref, T: Time> ScoreLookUp for Prob let amount_msat = usage.amount_msat.saturating_add(usage.inflight_htlc_msat); let capacity_msat = usage.effective_capacity.as_msat(); self.channel_liquidities - .get(&short_channel_id) - .unwrap_or(&ChannelLiquidity::new()) - .as_directed(source, target, capacity_msat, self.decay_params) + .get(&scid) + .unwrap_or(&ChannelLiquidity::new(Duration::ZERO)) + .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 { - fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64) { +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); let network_graph = self.network_graph.read_only(); @@ -1302,15 +1378,17 @@ impl>, L: Deref, T: Time> ScoreUpdate for Prob if at_failed_channel { self.channel_liquidities .entry(hop.short_channel_id) - .or_insert_with(ChannelLiquidity::new) - .as_directed_mut(source, &target, capacity_msat, self.decay_params) - .failed_at_channel(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger); + .or_insert_with(|| ChannelLiquidity::new(duration_since_epoch)) + .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) - .as_directed_mut(source, &target, capacity_msat, self.decay_params) - .failed_downstream(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger); + .or_insert_with(|| ChannelLiquidity::new(duration_since_epoch)) + .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); } } else { log_debug!(self.logger, "Not able to penalize channel with SCID {} as we do not have graph info for it (likely a route-hint last-hop).", @@ -1320,7 +1398,7 @@ impl>, L: Deref, T: Time> ScoreUpdate for Prob } } - fn payment_path_successful(&mut self, path: &Path) { + fn payment_path_successful(&mut self, path: &Path, duration_since_epoch: Duration) { let amount_msat = path.final_value_msat(); log_trace!(self.logger, "Scoring path through SCID {} as having succeeded at {} msat.", path.hops.split_last().map(|(hop, _)| hop.short_channel_id).unwrap_or(0), amount_msat); @@ -1336,9 +1414,10 @@ impl>, L: Deref, T: Time> ScoreUpdate for Prob 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, self.decay_params) - .successful(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger); + .or_insert_with(|| ChannelLiquidity::new(duration_since_epoch)) + .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 { log_debug!(self.logger, "Not able to learn for channel with SCID {} as we do not have graph info for it (likely a route-hint last-hop).", hop.short_channel_id); @@ -1346,325 +1425,52 @@ impl>, L: Deref, T: Time> ScoreUpdate for Prob } } - fn probe_failed(&mut self, path: &Path, short_channel_id: u64) { - self.payment_path_failed(path, short_channel_id) + fn probe_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) { + self.payment_path_failed(path, short_channel_id, duration_since_epoch) } - fn probe_successful(&mut self, path: &Path) { - self.payment_path_failed(path, u64::max_value()) + fn probe_successful(&mut self, path: &Path, duration_since_epoch: Duration) { + self.payment_path_failed(path, u64::max_value(), duration_since_epoch) } -} -mod approx { - const BITS: u32 = 64; - const HIGHEST_BIT: u32 = BITS - 1; - const LOWER_BITS: u32 = 6; - pub(super) const LOWER_BITS_BOUND: u64 = 1 << LOWER_BITS; - const LOWER_BITMASK: u64 = (1 << LOWER_BITS) - 1; - - /// Look-up table for `log10(x) * 2048` where row `i` is used for each `x` having `i` as the - /// most significant bit. The next 4 bits of `x`, if applicable, are used for the second index. - const LOG10_TIMES_2048: [[u16; (LOWER_BITS_BOUND) as usize]; BITS as usize] = [ - [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], - [617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, - 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, - 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, - 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977], - [1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, - 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, - 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, - 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731], - [1850, 1850, 1850, 1850, 1850, 1850, 1850, 1850, 1954, 1954, 1954, 1954, 1954, 1954, 1954, 1954, - 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2133, 2133, 2133, 2133, 2133, 2133, 2133, 2133, - 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2281, 2281, 2281, 2281, 2281, 2281, 2281, 2281, - 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2409, 2409, 2409, 2409, 2409, 2409, 2409, 2409], - [2466, 2466, 2466, 2466, 2520, 2520, 2520, 2520, 2571, 2571, 2571, 2571, 2619, 2619, 2619, 2619, - 2665, 2665, 2665, 2665, 2708, 2708, 2708, 2708, 2749, 2749, 2749, 2749, 2789, 2789, 2789, 2789, - 2827, 2827, 2827, 2827, 2863, 2863, 2863, 2863, 2898, 2898, 2898, 2898, 2931, 2931, 2931, 2931, - 2964, 2964, 2964, 2964, 2995, 2995, 2995, 2995, 3025, 3025, 3025, 3025, 3054, 3054, 3054, 3054], - [3083, 3083, 3110, 3110, 3136, 3136, 3162, 3162, 3187, 3187, 3212, 3212, 3235, 3235, 3259, 3259, - 3281, 3281, 3303, 3303, 3324, 3324, 3345, 3345, 3366, 3366, 3386, 3386, 3405, 3405, 3424, 3424, - 3443, 3443, 3462, 3462, 3479, 3479, 3497, 3497, 3514, 3514, 3531, 3531, 3548, 3548, 3564, 3564, - 3580, 3580, 3596, 3596, 3612, 3612, 3627, 3627, 3642, 3642, 3656, 3656, 3671, 3671, 3685, 3685], - [3699, 3713, 3726, 3740, 3753, 3766, 3779, 3791, 3804, 3816, 3828, 3840, 3852, 3864, 3875, 3886, - 3898, 3909, 3919, 3930, 3941, 3951, 3962, 3972, 3982, 3992, 4002, 4012, 4022, 4031, 4041, 4050, - 4060, 4069, 4078, 4087, 4096, 4105, 4114, 4122, 4131, 4139, 4148, 4156, 4164, 4173, 4181, 4189, - 4197, 4205, 4213, 4220, 4228, 4236, 4243, 4251, 4258, 4266, 4273, 4280, 4287, 4294, 4302, 4309], - [4316, 4329, 4343, 4356, 4369, 4382, 4395, 4408, 4420, 4433, 4445, 4457, 4468, 4480, 4492, 4503, - 4514, 4525, 4536, 4547, 4557, 4568, 4578, 4589, 4599, 4609, 4619, 4629, 4638, 4648, 4657, 4667, - 4676, 4685, 4695, 4704, 4713, 4721, 4730, 4739, 4747, 4756, 4764, 4773, 4781, 4789, 4797, 4805, - 4813, 4821, 4829, 4837, 4845, 4852, 4860, 4867, 4875, 4882, 4889, 4897, 4904, 4911, 4918, 4925], - [4932, 4946, 4959, 4973, 4986, 4999, 5012, 5024, 5037, 5049, 5061, 5073, 5085, 5097, 5108, 5119, - 5131, 5142, 5153, 5163, 5174, 5184, 5195, 5205, 5215, 5225, 5235, 5245, 5255, 5264, 5274, 5283, - 5293, 5302, 5311, 5320, 5329, 5338, 5347, 5355, 5364, 5372, 5381, 5389, 5397, 5406, 5414, 5422, - 5430, 5438, 5446, 5453, 5461, 5469, 5476, 5484, 5491, 5499, 5506, 5513, 5520, 5527, 5535, 5542], - [5549, 5562, 5576, 5589, 5603, 5615, 5628, 5641, 5653, 5666, 5678, 5690, 5701, 5713, 5725, 5736, - 5747, 5758, 5769, 5780, 5790, 5801, 5811, 5822, 5832, 5842, 5852, 5862, 5871, 5881, 5890, 5900, - 5909, 5918, 5928, 5937, 5946, 5954, 5963, 5972, 5980, 5989, 5997, 6006, 6014, 6022, 6030, 6038, - 6046, 6054, 6062, 6070, 6078, 6085, 6093, 6100, 6108, 6115, 6122, 6130, 6137, 6144, 6151, 6158], - [6165, 6179, 6192, 6206, 6219, 6232, 6245, 6257, 6270, 6282, 6294, 6306, 6318, 6330, 6341, 6352, - 6364, 6375, 6386, 6396, 6407, 6417, 6428, 6438, 6448, 6458, 6468, 6478, 6488, 6497, 6507, 6516, - 6526, 6535, 6544, 6553, 6562, 6571, 6580, 6588, 6597, 6605, 6614, 6622, 6630, 6639, 6647, 6655, - 6663, 6671, 6679, 6686, 6694, 6702, 6709, 6717, 6724, 6732, 6739, 6746, 6753, 6761, 6768, 6775], - [6782, 6795, 6809, 6822, 6836, 6849, 6861, 6874, 6886, 6899, 6911, 6923, 6934, 6946, 6958, 6969, - 6980, 6991, 7002, 7013, 7023, 7034, 7044, 7055, 7065, 7075, 7085, 7095, 7104, 7114, 7124, 7133, - 7142, 7151, 7161, 7170, 7179, 7187, 7196, 7205, 7213, 7222, 7230, 7239, 7247, 7255, 7263, 7271, - 7279, 7287, 7295, 7303, 7311, 7318, 7326, 7333, 7341, 7348, 7355, 7363, 7370, 7377, 7384, 7391], - [7398, 7412, 7425, 7439, 7452, 7465, 7478, 7490, 7503, 7515, 7527, 7539, 7551, 7563, 7574, 7585, - 7597, 7608, 7619, 7629, 7640, 7651, 7661, 7671, 7681, 7691, 7701, 7711, 7721, 7731, 7740, 7749, - 7759, 7768, 7777, 7786, 7795, 7804, 7813, 7821, 7830, 7838, 7847, 7855, 7864, 7872, 7880, 7888, - 7896, 7904, 7912, 7919, 7927, 7935, 7942, 7950, 7957, 7965, 7972, 7979, 7986, 7994, 8001, 8008], - [8015, 8028, 8042, 8055, 8069, 8082, 8094, 8107, 8119, 8132, 8144, 8156, 8167, 8179, 8191, 8202, - 8213, 8224, 8235, 8246, 8256, 8267, 8277, 8288, 8298, 8308, 8318, 8328, 8337, 8347, 8357, 8366, - 8375, 8384, 8394, 8403, 8412, 8420, 8429, 8438, 8446, 8455, 8463, 8472, 8480, 8488, 8496, 8504, - 8512, 8520, 8528, 8536, 8544, 8551, 8559, 8566, 8574, 8581, 8588, 8596, 8603, 8610, 8617, 8624], - [8631, 8645, 8659, 8672, 8685, 8698, 8711, 8723, 8736, 8748, 8760, 8772, 8784, 8796, 8807, 8818, - 8830, 8841, 8852, 8862, 8873, 8884, 8894, 8904, 8914, 8924, 8934, 8944, 8954, 8964, 8973, 8982, - 8992, 9001, 9010, 9019, 9028, 9037, 9046, 9054, 9063, 9071, 9080, 9088, 9097, 9105, 9113, 9121, - 9129, 9137, 9145, 9152, 9160, 9168, 9175, 9183, 9190, 9198, 9205, 9212, 9219, 9227, 9234, 9241], - [9248, 9261, 9275, 9288, 9302, 9315, 9327, 9340, 9352, 9365, 9377, 9389, 9400, 9412, 9424, 9435, - 9446, 9457, 9468, 9479, 9490, 9500, 9510, 9521, 9531, 9541, 9551, 9561, 9570, 9580, 9590, 9599, - 9608, 9617, 9627, 9636, 9645, 9653, 9662, 9671, 9679, 9688, 9696, 9705, 9713, 9721, 9729, 9737, - 9745, 9753, 9761, 9769, 9777, 9784, 9792, 9799, 9807, 9814, 9821, 9829, 9836, 9843, 9850, 9857], - [9864, 9878, 9892, 9905, 9918, 9931, 9944, 9956, 9969, 9981, 9993, 10005, 10017, 10029, 10040, 10051, - 10063, 10074, 10085, 10095, 10106, 10117, 10127, 10137, 10147, 10157, 10167, 10177, 10187, 10197, 10206, 10215, - 10225, 10234, 10243, 10252, 10261, 10270, 10279, 10287, 10296, 10304, 10313, 10321, 10330, 10338, 10346, 10354, - 10362, 10370, 10378, 10385, 10393, 10401, 10408, 10416, 10423, 10431, 10438, 10445, 10452, 10460, 10467, 10474], - [10481, 10494, 10508, 10521, 10535, 10548, 10560, 10573, 10585, 10598, 10610, 10622, 10634, 10645, 10657, 10668, - 10679, 10690, 10701, 10712, 10723, 10733, 10743, 10754, 10764, 10774, 10784, 10794, 10803, 10813, 10823, 10832, - 10841, 10851, 10860, 10869, 10878, 10886, 10895, 10904, 10912, 10921, 10929, 10938, 10946, 10954, 10962, 10970, - 10978, 10986, 10994, 11002, 11010, 11017, 11025, 11032, 11040, 11047, 11054, 11062, 11069, 11076, 11083, 11090], - [11097, 11111, 11125, 11138, 11151, 11164, 11177, 11189, 11202, 11214, 11226, 11238, 11250, 11262, 11273, 11284, - 11296, 11307, 11318, 11328, 11339, 11350, 11360, 11370, 11380, 11390, 11400, 11410, 11420, 11430, 11439, 11448, - 11458, 11467, 11476, 11485, 11494, 11503, 11512, 11520, 11529, 11538, 11546, 11554, 11563, 11571, 11579, 11587, - 11595, 11603, 11611, 11618, 11626, 11634, 11641, 11649, 11656, 11664, 11671, 11678, 11685, 11693, 11700, 11707], - [11714, 11727, 11741, 11754, 11768, 11781, 11793, 11806, 11818, 11831, 11843, 11855, 11867, 11878, 11890, 11901, - 11912, 11923, 11934, 11945, 11956, 11966, 11976, 11987, 11997, 12007, 12017, 12027, 12036, 12046, 12056, 12065, - 12074, 12084, 12093, 12102, 12111, 12119, 12128, 12137, 12146, 12154, 12162, 12171, 12179, 12187, 12195, 12203, - 12211, 12219, 12227, 12235, 12243, 12250, 12258, 12265, 12273, 12280, 12287, 12295, 12302, 12309, 12316, 12323], - [12330, 12344, 12358, 12371, 12384, 12397, 12410, 12423, 12435, 12447, 12459, 12471, 12483, 12495, 12506, 12517, - 12529, 12540, 12551, 12561, 12572, 12583, 12593, 12603, 12613, 12623, 12633, 12643, 12653, 12663, 12672, 12682, - 12691, 12700, 12709, 12718, 12727, 12736, 12745, 12753, 12762, 12771, 12779, 12787, 12796, 12804, 12812, 12820, - 12828, 12836, 12844, 12851, 12859, 12867, 12874, 12882, 12889, 12897, 12904, 12911, 12918, 12926, 12933, 12940], - [12947, 12960, 12974, 12987, 13001, 13014, 13026, 13039, 13051, 13064, 13076, 13088, 13100, 13111, 13123, 13134, - 13145, 13156, 13167, 13178, 13189, 13199, 13209, 13220, 13230, 13240, 13250, 13260, 13269, 13279, 13289, 13298, - 13307, 13317, 13326, 13335, 13344, 13352, 13361, 13370, 13379, 13387, 13395, 13404, 13412, 13420, 13428, 13436, - 13444, 13452, 13460, 13468, 13476, 13483, 13491, 13498, 13506, 13513, 13521, 13528, 13535, 13542, 13549, 13556], - [13563, 13577, 13591, 13604, 13617, 13630, 13643, 13656, 13668, 13680, 13692, 13704, 13716, 13728, 13739, 13750, - 13762, 13773, 13784, 13794, 13805, 13816, 13826, 13836, 13846, 13857, 13866, 13876, 13886, 13896, 13905, 13915, - 13924, 13933, 13942, 13951, 13960, 13969, 13978, 13986, 13995, 14004, 14012, 14020, 14029, 14037, 14045, 14053, - 14061, 14069, 14077, 14084, 14092, 14100, 14107, 14115, 14122, 14130, 14137, 14144, 14151, 14159, 14166, 14173], - [14180, 14194, 14207, 14220, 14234, 14247, 14259, 14272, 14284, 14297, 14309, 14321, 14333, 14344, 14356, 14367, - 14378, 14389, 14400, 14411, 14422, 14432, 14443, 14453, 14463, 14473, 14483, 14493, 14502, 14512, 14522, 14531, - 14540, 14550, 14559, 14568, 14577, 14586, 14594, 14603, 14612, 14620, 14628, 14637, 14645, 14653, 14661, 14669, - 14677, 14685, 14693, 14701, 14709, 14716, 14724, 14731, 14739, 14746, 14754, 14761, 14768, 14775, 14782, 14789], - [14796, 14810, 14824, 14837, 14850, 14863, 14876, 14889, 14901, 14913, 14925, 14937, 14949, 14961, 14972, 14984, - 14995, 15006, 15017, 15027, 15038, 15049, 15059, 15069, 15079, 15090, 15099, 15109, 15119, 15129, 15138, 15148, - 15157, 15166, 15175, 15184, 15193, 15202, 15211, 15219, 15228, 15237, 15245, 15253, 15262, 15270, 15278, 15286, - 15294, 15302, 15310, 15317, 15325, 15333, 15340, 15348, 15355, 15363, 15370, 15377, 15384, 15392, 15399, 15406], - [15413, 15427, 15440, 15453, 15467, 15480, 15492, 15505, 15517, 15530, 15542, 15554, 15566, 15577, 15589, 15600, - 15611, 15622, 15633, 15644, 15655, 15665, 15676, 15686, 15696, 15706, 15716, 15726, 15736, 15745, 15755, 15764, - 15773, 15783, 15792, 15801, 15810, 15819, 15827, 15836, 15845, 15853, 15862, 15870, 15878, 15886, 15894, 15903, - 15910, 15918, 15926, 15934, 15942, 15949, 15957, 15964, 15972, 15979, 15987, 15994, 16001, 16008, 16015, 16022], - [16029, 16043, 16057, 16070, 16083, 16096, 16109, 16122, 16134, 16146, 16158, 16170, 16182, 16194, 16205, 16217, - 16228, 16239, 16250, 16260, 16271, 16282, 16292, 16302, 16312, 16323, 16332, 16342, 16352, 16362, 16371, 16381, - 16390, 16399, 16408, 16417, 16426, 16435, 16444, 16452, 16461, 16470, 16478, 16486, 16495, 16503, 16511, 16519, - 16527, 16535, 16543, 16550, 16558, 16566, 16573, 16581, 16588, 16596, 16603, 16610, 16618, 16625, 16632, 16639], - [16646, 16660, 16673, 16686, 16700, 16713, 16725, 16738, 16751, 16763, 16775, 16787, 16799, 16810, 16822, 16833, - 16844, 16855, 16866, 16877, 16888, 16898, 16909, 16919, 16929, 16939, 16949, 16959, 16969, 16978, 16988, 16997, - 17006, 17016, 17025, 17034, 17043, 17052, 17060, 17069, 17078, 17086, 17095, 17103, 17111, 17119, 17127, 17136, - 17143, 17151, 17159, 17167, 17175, 17182, 17190, 17197, 17205, 17212, 17220, 17227, 17234, 17241, 17248, 17255], - [17262, 17276, 17290, 17303, 17316, 17329, 17342, 17355, 17367, 17379, 17391, 17403, 17415, 17427, 17438, 17450, - 17461, 17472, 17483, 17493, 17504, 17515, 17525, 17535, 17546, 17556, 17565, 17575, 17585, 17595, 17604, 17614, - 17623, 17632, 17641, 17650, 17659, 17668, 17677, 17685, 17694, 17703, 17711, 17719, 17728, 17736, 17744, 17752, - 17760, 17768, 17776, 17784, 17791, 17799, 17806, 17814, 17821, 17829, 17836, 17843, 17851, 17858, 17865, 17872], - [17879, 17893, 17906, 17920, 17933, 17946, 17958, 17971, 17984, 17996, 18008, 18020, 18032, 18043, 18055, 18066, - 18077, 18088, 18099, 18110, 18121, 18131, 18142, 18152, 18162, 18172, 18182, 18192, 18202, 18211, 18221, 18230, - 18239, 18249, 18258, 18267, 18276, 18285, 18293, 18302, 18311, 18319, 18328, 18336, 18344, 18352, 18360, 18369, - 18377, 18384, 18392, 18400, 18408, 18415, 18423, 18430, 18438, 18445, 18453, 18460, 18467, 18474, 18481, 18488], - [18495, 18509, 18523, 18536, 18549, 18562, 18575, 18588, 18600, 18612, 18624, 18636, 18648, 18660, 18671, 18683, - 18694, 18705, 18716, 18726, 18737, 18748, 18758, 18768, 18779, 18789, 18799, 18808, 18818, 18828, 18837, 18847, - 18856, 18865, 18874, 18883, 18892, 18901, 18910, 18919, 18927, 18936, 18944, 18952, 18961, 18969, 18977, 18985, - 18993, 19001, 19009, 19017, 19024, 19032, 19039, 19047, 19054, 19062, 19069, 19076, 19084, 19091, 19098, 19105], - [19112, 19126, 19139, 19153, 19166, 19179, 19191, 19204, 19217, 19229, 19241, 19253, 19265, 19276, 19288, 19299, - 19310, 19321, 19332, 19343, 19354, 19364, 19375, 19385, 19395, 19405, 19415, 19425, 19435, 19444, 19454, 19463, - 19472, 19482, 19491, 19500, 19509, 19518, 19526, 19535, 19544, 19552, 19561, 19569, 19577, 19585, 19594, 19602, - 19610, 19617, 19625, 19633, 19641, 19648, 19656, 19663, 19671, 19678, 19686, 19693, 19700, 19707, 19714, 19721], - [19728, 19742, 19756, 19769, 19782, 19795, 19808, 19821, 19833, 19845, 19857, 19869, 19881, 19893, 19904, 19916, - 19927, 19938, 19949, 19960, 19970, 19981, 19991, 20001, 20012, 20022, 20032, 20041, 20051, 20061, 20070, 20080, - 20089, 20098, 20107, 20116, 20125, 20134, 20143, 20152, 20160, 20169, 20177, 20185, 20194, 20202, 20210, 20218, - 20226, 20234, 20242, 20250, 20257, 20265, 20272, 20280, 20287, 20295, 20302, 20309, 20317, 20324, 20331, 20338], - [20345, 20359, 20372, 20386, 20399, 20412, 20425, 20437, 20450, 20462, 20474, 20486, 20498, 20509, 20521, 20532, - 20543, 20554, 20565, 20576, 20587, 20597, 20608, 20618, 20628, 20638, 20648, 20658, 20668, 20677, 20687, 20696, - 20705, 20715, 20724, 20733, 20742, 20751, 20759, 20768, 20777, 20785, 20794, 20802, 20810, 20818, 20827, 20835, - 20843, 20850, 20858, 20866, 20874, 20881, 20889, 20896, 20904, 20911, 20919, 20926, 20933, 20940, 20947, 20954], - [20961, 20975, 20989, 21002, 21015, 21028, 21041, 21054, 21066, 21078, 21090, 21102, 21114, 21126, 21137, 21149, - 21160, 21171, 21182, 21193, 21203, 21214, 21224, 21234, 21245, 21255, 21265, 21274, 21284, 21294, 21303, 21313, - 21322, 21331, 21340, 21349, 21358, 21367, 21376, 21385, 21393, 21402, 21410, 21418, 21427, 21435, 21443, 21451, - 21459, 21467, 21475, 21483, 21490, 21498, 21505, 21513, 21520, 21528, 21535, 21542, 21550, 21557, 21564, 21571], - [21578, 21592, 21605, 21619, 21632, 21645, 21658, 21670, 21683, 21695, 21707, 21719, 21731, 21742, 21754, 21765, - 21776, 21787, 21798, 21809, 21820, 21830, 21841, 21851, 21861, 21871, 21881, 21891, 21901, 21910, 21920, 21929, - 21938, 21948, 21957, 21966, 21975, 21984, 21992, 22001, 22010, 22018, 22027, 22035, 22043, 22051, 22060, 22068, - 22076, 22083, 22091, 22099, 22107, 22114, 22122, 22129, 22137, 22144, 22152, 22159, 22166, 22173, 22180, 22187], - [22194, 22208, 22222, 22235, 22248, 22261, 22274, 22287, 22299, 22311, 22323, 22335, 22347, 22359, 22370, 22382, - 22393, 22404, 22415, 22426, 22436, 22447, 22457, 22467, 22478, 22488, 22498, 22507, 22517, 22527, 22536, 22546, - 22555, 22564, 22573, 22582, 22591, 22600, 22609, 22618, 22626, 22635, 22643, 22651, 22660, 22668, 22676, 22684, - 22692, 22700, 22708, 22716, 22723, 22731, 22738, 22746, 22753, 22761, 22768, 22775, 22783, 22790, 22797, 22804], - [22811, 22825, 22838, 22852, 22865, 22878, 22891, 22903, 22916, 22928, 22940, 22952, 22964, 22975, 22987, 22998, - 23009, 23020, 23031, 23042, 23053, 23063, 23074, 23084, 23094, 23104, 23114, 23124, 23134, 23143, 23153, 23162, - 23171, 23181, 23190, 23199, 23208, 23217, 23225, 23234, 23243, 23251, 23260, 23268, 23276, 23284, 23293, 23301, - 23309, 23316, 23324, 23332, 23340, 23347, 23355, 23363, 23370, 23377, 23385, 23392, 23399, 23406, 23413, 23420], - [23427, 23441, 23455, 23468, 23481, 23494, 23507, 23520, 23532, 23544, 23556, 23568, 23580, 23592, 23603, 23615, - 23626, 23637, 23648, 23659, 23669, 23680, 23690, 23700, 23711, 23721, 23731, 23740, 23750, 23760, 23769, 23779, - 23788, 23797, 23806, 23815, 23824, 23833, 23842, 23851, 23859, 23868, 23876, 23884, 23893, 23901, 23909, 23917, - 23925, 23933, 23941, 23949, 23956, 23964, 23972, 23979, 23986, 23994, 24001, 24008, 24016, 24023, 24030, 24037], - [24044, 24058, 24071, 24085, 24098, 24111, 24124, 24136, 24149, 24161, 24173, 24185, 24197, 24208, 24220, 24231, - 24242, 24253, 24264, 24275, 24286, 24296, 24307, 24317, 24327, 24337, 24347, 24357, 24367, 24376, 24386, 24395, - 24405, 24414, 24423, 24432, 24441, 24450, 24458, 24467, 24476, 24484, 24493, 24501, 24509, 24517, 24526, 24534, - 24542, 24550, 24557, 24565, 24573, 24580, 24588, 24596, 24603, 24610, 24618, 24625, 24632, 24639, 24646, 24653], - [24660, 24674, 24688, 24701, 24714, 24727, 24740, 24753, 24765, 24777, 24790, 24801, 24813, 24825, 24836, 24848, - 24859, 24870, 24881, 24892, 24902, 24913, 24923, 24933, 24944, 24954, 24964, 24973, 24983, 24993, 25002, 25012, - 25021, 25030, 25039, 25048, 25057, 25066, 25075, 25084, 25092, 25101, 25109, 25117, 25126, 25134, 25142, 25150, - 25158, 25166, 25174, 25182, 25189, 25197, 25205, 25212, 25219, 25227, 25234, 25241, 25249, 25256, 25263, 25270], - [25277, 25291, 25304, 25318, 25331, 25344, 25357, 25369, 25382, 25394, 25406, 25418, 25430, 25441, 25453, 25464, - 25475, 25486, 25497, 25508, 25519, 25529, 25540, 25550, 25560, 25570, 25580, 25590, 25600, 25609, 25619, 25628, - 25638, 25647, 25656, 25665, 25674, 25683, 25691, 25700, 25709, 25717, 25726, 25734, 25742, 25750, 25759, 25767, - 25775, 25783, 25790, 25798, 25806, 25813, 25821, 25829, 25836, 25843, 25851, 25858, 25865, 25872, 25879, 25886], - [25893, 25907, 25921, 25934, 25947, 25960, 25973, 25986, 25998, 26010, 26023, 26034, 26046, 26058, 26069, 26081, - 26092, 26103, 26114, 26125, 26135, 26146, 26156, 26166, 26177, 26187, 26197, 26206, 26216, 26226, 26235, 26245, - 26254, 26263, 26272, 26281, 26290, 26299, 26308, 26317, 26325, 26334, 26342, 26351, 26359, 26367, 26375, 26383, - 26391, 26399, 26407, 26415, 26422, 26430, 26438, 26445, 26453, 26460, 26467, 26474, 26482, 26489, 26496, 26503], - [26510, 26524, 26537, 26551, 26564, 26577, 26590, 26602, 26615, 26627, 26639, 26651, 26663, 26674, 26686, 26697, - 26708, 26719, 26730, 26741, 26752, 26762, 26773, 26783, 26793, 26803, 26813, 26823, 26833, 26842, 26852, 26861, - 26871, 26880, 26889, 26898, 26907, 26916, 26924, 26933, 26942, 26950, 26959, 26967, 26975, 26983, 26992, 27000, - 27008, 27016, 27023, 27031, 27039, 27046, 27054, 27062, 27069, 27076, 27084, 27091, 27098, 27105, 27112, 27119], - [27126, 27140, 27154, 27167, 27180, 27193, 27206, 27219, 27231, 27243, 27256, 27267, 27279, 27291, 27302, 27314, - 27325, 27336, 27347, 27358, 27368, 27379, 27389, 27399, 27410, 27420, 27430, 27439, 27449, 27459, 27468, 27478, - 27487, 27496, 27505, 27514, 27523, 27532, 27541, 27550, 27558, 27567, 27575, 27584, 27592, 27600, 27608, 27616, - 27624, 27632, 27640, 27648, 27655, 27663, 27671, 27678, 27686, 27693, 27700, 27707, 27715, 27722, 27729, 27736], - [27743, 27757, 27770, 27784, 27797, 27810, 27823, 27835, 27848, 27860, 27872, 27884, 27896, 27907, 27919, 27930, - 27941, 27952, 27963, 27974, 27985, 27995, 28006, 28016, 28026, 28036, 28046, 28056, 28066, 28075, 28085, 28094, - 28104, 28113, 28122, 28131, 28140, 28149, 28157, 28166, 28175, 28183, 28192, 28200, 28208, 28217, 28225, 28233, - 28241, 28249, 28256, 28264, 28272, 28280, 28287, 28295, 28302, 28309, 28317, 28324, 28331, 28338, 28345, 28352], - [28359, 28373, 28387, 28400, 28413, 28426, 28439, 28452, 28464, 28476, 28489, 28501, 28512, 28524, 28535, 28547, - 28558, 28569, 28580, 28591, 28601, 28612, 28622, 28633, 28643, 28653, 28663, 28672, 28682, 28692, 28701, 28711, - 28720, 28729, 28738, 28747, 28756, 28765, 28774, 28783, 28791, 28800, 28808, 28817, 28825, 28833, 28841, 28849, - 28857, 28865, 28873, 28881, 28888, 28896, 28904, 28911, 28919, 28926, 28933, 28941, 28948, 28955, 28962, 28969], - [28976, 28990, 29003, 29017, 29030, 29043, 29056, 29068, 29081, 29093, 29105, 29117, 29129, 29140, 29152, 29163, - 29174, 29185, 29196, 29207, 29218, 29228, 29239, 29249, 29259, 29269, 29279, 29289, 29299, 29308, 29318, 29327, - 29337, 29346, 29355, 29364, 29373, 29382, 29390, 29399, 29408, 29416, 29425, 29433, 29441, 29450, 29458, 29466, - 29474, 29482, 29489, 29497, 29505, 29513, 29520, 29528, 29535, 29542, 29550, 29557, 29564, 29571, 29578, 29585], - [29592, 29606, 29620, 29633, 29646, 29659, 29672, 29685, 29697, 29709, 29722, 29734, 29745, 29757, 29768, 29780, - 29791, 29802, 29813, 29824, 29834, 29845, 29855, 29866, 29876, 29886, 29896, 29906, 29915, 29925, 29934, 29944, - 29953, 29962, 29971, 29980, 29989, 29998, 30007, 30016, 30024, 30033, 30041, 30050, 30058, 30066, 30074, 30082, - 30090, 30098, 30106, 30114, 30121, 30129, 30137, 30144, 30152, 30159, 30166, 30174, 30181, 30188, 30195, 30202], - [30209, 30223, 30236, 30250, 30263, 30276, 30289, 30301, 30314, 30326, 30338, 30350, 30362, 30373, 30385, 30396, - 30407, 30418, 30429, 30440, 30451, 30461, 30472, 30482, 30492, 30502, 30512, 30522, 30532, 30541, 30551, 30560, - 30570, 30579, 30588, 30597, 30606, 30615, 30624, 30632, 30641, 30649, 30658, 30666, 30674, 30683, 30691, 30699, - 30707, 30715, 30722, 30730, 30738, 30746, 30753, 30761, 30768, 30775, 30783, 30790, 30797, 30804, 30811, 30818], - [30825, 30839, 30853, 30866, 30879, 30892, 30905, 30918, 30930, 30943, 30955, 30967, 30978, 30990, 31001, 31013, - 31024, 31035, 31046, 31057, 31067, 31078, 31088, 31099, 31109, 31119, 31129, 31139, 31148, 31158, 31167, 31177, - 31186, 31195, 31204, 31213, 31222, 31231, 31240, 31249, 31257, 31266, 31274, 31283, 31291, 31299, 31307, 31315, - 31323, 31331, 31339, 31347, 31354, 31362, 31370, 31377, 31385, 31392, 31399, 31407, 31414, 31421, 31428, 31435], - [31442, 31456, 31469, 31483, 31496, 31509, 31522, 31534, 31547, 31559, 31571, 31583, 31595, 31606, 31618, 31629, - 31640, 31652, 31662, 31673, 31684, 31694, 31705, 31715, 31725, 31735, 31745, 31755, 31765, 31774, 31784, 31793, - 31803, 31812, 31821, 31830, 31839, 31848, 31857, 31865, 31874, 31882, 31891, 31899, 31907, 31916, 31924, 31932, - 31940, 31948, 31955, 31963, 31971, 31979, 31986, 31994, 32001, 32008, 32016, 32023, 32030, 32037, 32044, 32052], - [32058, 32072, 32086, 32099, 32112, 32125, 32138, 32151, 32163, 32176, 32188, 32200, 32211, 32223, 32234, 32246, - 32257, 32268, 32279, 32290, 32300, 32311, 32321, 32332, 32342, 32352, 32362, 32372, 32381, 32391, 32400, 32410, - 32419, 32428, 32437, 32446, 32455, 32464, 32473, 32482, 32490, 32499, 32507, 32516, 32524, 32532, 32540, 32548, - 32556, 32564, 32572, 32580, 32587, 32595, 32603, 32610, 32618, 32625, 32632, 32640, 32647, 32654, 32661, 32668], - [32675, 32689, 32702, 32716, 32729, 32742, 32755, 32767, 32780, 32792, 32804, 32816, 32828, 32839, 32851, 32862, - 32873, 32885, 32895, 32906, 32917, 32927, 32938, 32948, 32958, 32968, 32978, 32988, 32998, 33007, 33017, 33026, - 33036, 33045, 33054, 33063, 33072, 33081, 33090, 33098, 33107, 33115, 33124, 33132, 33140, 33149, 33157, 33165, - 33173, 33181, 33188, 33196, 33204, 33212, 33219, 33227, 33234, 33241, 33249, 33256, 33263, 33270, 33278, 33285], - [33292, 33305, 33319, 33332, 33345, 33358, 33371, 33384, 33396, 33409, 33421, 33433, 33444, 33456, 33467, 33479, - 33490, 33501, 33512, 33523, 33533, 33544, 33554, 33565, 33575, 33585, 33595, 33605, 33614, 33624, 33633, 33643, - 33652, 33661, 33670, 33680, 33688, 33697, 33706, 33715, 33723, 33732, 33740, 33749, 33757, 33765, 33773, 33781, - 33789, 33797, 33805, 33813, 33820, 33828, 33836, 33843, 33851, 33858, 33865, 33873, 33880, 33887, 33894, 33901], - [33908, 33922, 33935, 33949, 33962, 33975, 33988, 34000, 34013, 34025, 34037, 34049, 34061, 34072, 34084, 34095, - 34106, 34118, 34128, 34139, 34150, 34160, 34171, 34181, 34191, 34201, 34211, 34221, 34231, 34240, 34250, 34259, - 34269, 34278, 34287, 34296, 34305, 34314, 34323, 34331, 34340, 34348, 34357, 34365, 34373, 34382, 34390, 34398, - 34406, 34414, 34422, 34429, 34437, 34445, 34452, 34460, 34467, 34475, 34482, 34489, 34496, 34503, 34511, 34518], - [34525, 34538, 34552, 34565, 34578, 34591, 34604, 34617, 34629, 34642, 34654, 34666, 34677, 34689, 34700, 34712, - 34723, 34734, 34745, 34756, 34766, 34777, 34787, 34798, 34808, 34818, 34828, 34838, 34847, 34857, 34866, 34876, - 34885, 34894, 34904, 34913, 34921, 34930, 34939, 34948, 34956, 34965, 34973, 34982, 34990, 34998, 35006, 35014, - 35022, 35030, 35038, 35046, 35053, 35061, 35069, 35076, 35084, 35091, 35098, 35106, 35113, 35120, 35127, 35134], - [35141, 35155, 35168, 35182, 35195, 35208, 35221, 35233, 35246, 35258, 35270, 35282, 35294, 35306, 35317, 35328, - 35340, 35351, 35361, 35372, 35383, 35393, 35404, 35414, 35424, 35434, 35444, 35454, 35464, 35473, 35483, 35492, - 35502, 35511, 35520, 35529, 35538, 35547, 35556, 35564, 35573, 35581, 35590, 35598, 35606, 35615, 35623, 35631, - 35639, 35647, 35655, 35662, 35670, 35678, 35685, 35693, 35700, 35708, 35715, 35722, 35729, 35736, 35744, 35751], - [35758, 35771, 35785, 35798, 35811, 35824, 35837, 35850, 35862, 35875, 35887, 35899, 35910, 35922, 35934, 35945, - 35956, 35967, 35978, 35989, 35999, 36010, 36020, 36031, 36041, 36051, 36061, 36071, 36080, 36090, 36099, 36109, - 36118, 36127, 36137, 36146, 36154, 36163, 36172, 36181, 36189, 36198, 36206, 36215, 36223, 36231, 36239, 36247, - 36255, 36263, 36271, 36279, 36287, 36294, 36302, 36309, 36317, 36324, 36331, 36339, 36346, 36353, 36360, 36367], - [36374, 36388, 36401, 36415, 36428, 36441, 36454, 36466, 36479, 36491, 36503, 36515, 36527, 36539, 36550, 36561, - 36573, 36584, 36594, 36605, 36616, 36626, 36637, 36647, 36657, 36667, 36677, 36687, 36697, 36706, 36716, 36725, - 36735, 36744, 36753, 36762, 36771, 36780, 36789, 36797, 36806, 36814, 36823, 36831, 36839, 36848, 36856, 36864, - 36872, 36880, 36888, 36895, 36903, 36911, 36918, 36926, 36933, 36941, 36948, 36955, 36962, 36969, 36977, 36984], - [36991, 37004, 37018, 37031, 37044, 37057, 37070, 37083, 37095, 37108, 37120, 37132, 37143, 37155, 37167, 37178, - 37189, 37200, 37211, 37222, 37232, 37243, 37253, 37264, 37274, 37284, 37294, 37304, 37313, 37323, 37332, 37342, - 37351, 37360, 37370, 37379, 37388, 37396, 37405, 37414, 37422, 37431, 37439, 37448, 37456, 37464, 37472, 37480, - 37488, 37496, 37504, 37512, 37520, 37527, 37535, 37542, 37550, 37557, 37564, 37572, 37579, 37586, 37593, 37600], - [37607, 37621, 37634, 37648, 37661, 37674, 37687, 37699, 37712, 37724, 37736, 37748, 37760, 37772, 37783, 37794, - 37806, 37817, 37828, 37838, 37849, 37859, 37870, 37880, 37890, 37900, 37910, 37920, 37930, 37939, 37949, 37958, - 37968, 37977, 37986, 37995, 38004, 38013, 38022, 38030, 38039, 38047, 38056, 38064, 38072, 38081, 38089, 38097, - 38105, 38113, 38121, 38128, 38136, 38144, 38151, 38159, 38166, 38174, 38181, 38188, 38195, 38202, 38210, 38217], - [38224, 38237, 38251, 38264, 38278, 38290, 38303, 38316, 38328, 38341, 38353, 38365, 38376, 38388, 38400, 38411, - 38422, 38433, 38444, 38455, 38465, 38476, 38486, 38497, 38507, 38517, 38527, 38537, 38546, 38556, 38565, 38575, - 38584, 38593, 38603, 38612, 38621, 38629, 38638, 38647, 38655, 38664, 38672, 38681, 38689, 38697, 38705, 38713, - 38721, 38729, 38737, 38745, 38753, 38760, 38768, 38775, 38783, 38790, 38797, 38805, 38812, 38819, 38826, 38833], - [38840, 38854, 38867, 38881, 38894, 38907, 38920, 38932, 38945, 38957, 38969, 38981, 38993, 39005, 39016, 39027, - 39039, 39050, 39061, 39071, 39082, 39092, 39103, 39113, 39123, 39133, 39143, 39153, 39163, 39172, 39182, 39191, - 39201, 39210, 39219, 39228, 39237, 39246, 39255, 39263, 39272, 39280, 39289, 39297, 39305, 39314, 39322, 39330, - 39338, 39346, 39354, 39361, 39369, 39377, 39384, 39392, 39399, 39407, 39414, 39421, 39428, 39436, 39443, 39450], - ]; + fn decay_liquidity_certainty(&mut self, duration_since_epoch: Duration) { + let decay_params = self.decay_params; + self.channel_liquidities.retain(|_scid, liquidity| { + liquidity.min_liquidity_offset_msat = + liquidity.decayed_offset(liquidity.min_liquidity_offset_msat, duration_since_epoch, decay_params); + liquidity.max_liquidity_offset_msat = + liquidity.decayed_offset(liquidity.max_liquidity_offset_msat, duration_since_epoch, decay_params); + liquidity.last_updated = duration_since_epoch; - /// Approximate `log10(numerator / denominator) * 2048` using a look-up table. - #[inline] - pub fn negative_log10_times_2048(numerator: u64, denominator: u64) -> u64 { - // Multiply the -1 through to avoid needing to use signed numbers. - (log10_times_2048(denominator) - log10_times_2048(numerator)) as u64 - } - - #[inline] - fn log10_times_2048(x: u64) -> u16 { - debug_assert_ne!(x, 0); - let most_significant_bit = HIGHEST_BIT - x.leading_zeros(); - let lower_bits = (x >> most_significant_bit.saturating_sub(LOWER_BITS)) & LOWER_BITMASK; - LOG10_TIMES_2048[most_significant_bit as usize][lower_bits as usize] - } - - #[cfg(test)] - mod tests { - use super::*; - - #[test] - fn prints_negative_log10_times_2048_lookup_table() { - for msb in 0..BITS { - for i in 0..LOWER_BITS_BOUND { - let x = ((LOWER_BITS_BOUND + i) << (HIGHEST_BIT - LOWER_BITS)) >> (HIGHEST_BIT - msb); - let log10_times_2048 = ((x as f64).log10() * 2048.0).round() as u16; - assert_eq!(log10_times_2048, LOG10_TIMES_2048[msb as usize][i as usize]); - - if i % LOWER_BITS_BOUND == 0 { - print!("\t\t[{}, ", log10_times_2048); - } else if i % LOWER_BITS_BOUND == LOWER_BITS_BOUND - 1 { - println!("{}],", log10_times_2048); - } else if i % (LOWER_BITS_BOUND/4) == LOWER_BITS_BOUND/4 - 1 { - print!("{},\n\t\t\t", log10_times_2048); - } else { - print!("{}, ", log10_times_2048); - } + let elapsed_time = + duration_since_epoch.saturating_sub(liquidity.offset_history_last_updated); + if elapsed_time > decay_params.historical_no_updates_half_life { + let half_life = decay_params.historical_no_updates_half_life.as_secs_f64(); + if half_life != 0.0 { + liquidity.liquidity_history.decay_buckets(elapsed_time.as_secs_f64() / half_life); + liquidity.offset_history_last_updated = duration_since_epoch; } } - } + liquidity.min_liquidity_offset_msat != 0 || liquidity.max_liquidity_offset_msat != 0 || + liquidity.liquidity_history.has_datapoints() + }); } } +#[cfg(c_bindings)] +impl>, L: Deref> Score for ProbabilisticScorer +where L::Target: Logger {} + +#[cfg(feature = "std")] +#[inline] +fn powf64(n: f64, exp: f64) -> f64 { + n.powf(exp) +} +#[cfg(not(feature = "std"))] +fn powf64(n: f64, exp: f64) -> f64 { + libm::powf(n as f32, exp as f32) as f64 +} + mod bucketed_history { use super::*; @@ -1785,7 +1591,7 @@ mod bucketed_history { impl HistoricalBucketRangeTracker { pub(super) fn new() -> Self { Self { buckets: [0; 32] } } - pub(super) fn track_datapoint(&mut self, liquidity_offset_msat: u64, capacity_msat: u64) { + fn track_datapoint(&mut self, liquidity_offset_msat: u64, capacity_msat: u64) { // We have 32 leaky buckets for min and max liquidity. Each bucket tracks the amount of time // we spend in each bucket as a 16-bit fixed-point number with a 5 bit fractional part. // @@ -1816,69 +1622,127 @@ 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) }); impl_writeable_tlv_based!(LegacyHistoricalBucketRangeTracker, { (0, buckets, required) }); - /// A set of buckets representing the history of where we've seen the minimum- and maximum- - /// liquidity bounds for a given channel. - pub(super) struct HistoricalMinMaxBuckets> { - /// Buckets tracking where and how often we've seen the minimum liquidity bound for a - /// channel. - pub(super) min_liquidity_offset_history: D, - /// Buckets tracking where and how often we've seen the maximum liquidity bound for a - /// channel. - pub(super) max_liquidity_offset_history: D, - } - - impl> HistoricalMinMaxBuckets { - pub(super) fn get_decayed_buckets(&self, now: T, last_updated: T, half_life: Duration) - -> Option<([u16; 32], [u16; 32])> { - let (_, required_decays) = self.get_total_valid_points(now, last_updated, half_life)?; - - let mut min_buckets = *self.min_liquidity_offset_history; - min_buckets.time_decay_data(required_decays); - let mut max_buckets = *self.max_liquidity_offset_history; - max_buckets.time_decay_data(required_decays); - Some((min_buckets.buckets, max_buckets.buckets)) + #[derive(Clone, Copy)] + pub(super) struct HistoricalLiquidityTracker { + min_liquidity_offset_history: HistoricalBucketRangeTracker, + max_liquidity_offset_history: HistoricalBucketRangeTracker, + total_valid_points_tracked: u64, + } + + impl HistoricalLiquidityTracker { + pub(super) fn new() -> HistoricalLiquidityTracker { + HistoricalLiquidityTracker { + min_liquidity_offset_history: HistoricalBucketRangeTracker::new(), + max_liquidity_offset_history: HistoricalBucketRangeTracker::new(), + total_valid_points_tracked: 0, + } + } + + pub(super) fn from_min_max( + min_liquidity_offset_history: HistoricalBucketRangeTracker, + max_liquidity_offset_history: HistoricalBucketRangeTracker, + ) -> HistoricalLiquidityTracker { + let mut res = HistoricalLiquidityTracker { + min_liquidity_offset_history, + max_liquidity_offset_history, + total_valid_points_tracked: 0, + }; + res.recalculate_valid_points(); + res + } + + pub(super) fn has_datapoints(&self) -> bool { + self.min_liquidity_offset_history.buckets != [0; 32] || + self.max_liquidity_offset_history.buckets != [0; 32] } - #[inline] - pub(super) fn get_total_valid_points(&self, now: T, last_updated: T, half_life: Duration) - -> Option<(u64, u32)> { - let required_decays = now.duration_since(last_updated).as_secs() - .checked_div(half_life.as_secs()) - .map_or(u32::max_value(), |decays| cmp::min(decays, u32::max_value() as u64) as u32); - let mut total_valid_points_tracked = 0; + pub(super) fn decay_buckets(&mut self, half_lives: f64) { + let divisor = powf64(2048.0, half_lives) as u64; + for bucket in self.min_liquidity_offset_history.buckets.iter_mut() { + *bucket = ((*bucket as u64) * 1024 / divisor) as u16; + } + for bucket in self.max_liquidity_offset_history.buckets.iter_mut() { + *bucket = ((*bucket as u64) * 1024 / divisor) as u16; + } + self.recalculate_valid_points(); + } + + fn recalculate_valid_points(&mut self) { + self.total_valid_points_tracked = 0; for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate() { for max_bucket in self.max_liquidity_offset_history.buckets.iter().take(32 - min_idx) { - total_valid_points_tracked += (*min_bucket as u64) * (*max_bucket as u64); + self.total_valid_points_tracked += (*min_bucket as u64) * (*max_bucket as u64); } } + } - // If the total valid points is smaller than 1.0 (i.e. 32 in our fixed-point scheme), - // treat it as if we were fully decayed. - const FULLY_DECAYED: u16 = BUCKET_FIXED_POINT_ONE * BUCKET_FIXED_POINT_ONE; - if total_valid_points_tracked.checked_shr(required_decays).unwrap_or(0) < FULLY_DECAYED.into() { - return None; + pub(super) fn writeable_min_offset_history(&self) -> &HistoricalBucketRangeTracker { + &self.min_liquidity_offset_history + } + + pub(super) fn writeable_max_offset_history(&self) -> &HistoricalBucketRangeTracker { + &self.max_liquidity_offset_history + } + + pub(super) fn as_directed<'a>(&'a self, source_less_than_target: bool) + -> DirectedHistoricalLiquidityTracker<&'a HistoricalLiquidityTracker> { + DirectedHistoricalLiquidityTracker { source_less_than_target, tracker: self } + } + + pub(super) fn as_directed_mut<'a>(&'a mut self, source_less_than_target: bool) + -> DirectedHistoricalLiquidityTracker<&'a mut HistoricalLiquidityTracker> { + DirectedHistoricalLiquidityTracker { source_less_than_target, tracker: self } + } + } + + /// A set of buckets representing the history of where we've seen the minimum- and maximum- + /// liquidity bounds for a given channel. + pub(super) struct DirectedHistoricalLiquidityTracker> { + source_less_than_target: bool, + tracker: D, + } + + impl> DirectedHistoricalLiquidityTracker { + pub(super) fn track_datapoint( + &mut self, min_offset_msat: u64, max_offset_msat: u64, capacity_msat: u64, + ) { + if self.source_less_than_target { + self.tracker.min_liquidity_offset_history.track_datapoint(min_offset_msat, capacity_msat); + self.tracker.max_liquidity_offset_history.track_datapoint(max_offset_msat, capacity_msat); + } else { + self.tracker.max_liquidity_offset_history.track_datapoint(min_offset_msat, capacity_msat); + self.tracker.min_liquidity_offset_history.track_datapoint(max_offset_msat, capacity_msat); + } + self.tracker.recalculate_valid_points(); + } + } + + impl> DirectedHistoricalLiquidityTracker { + pub(super) fn min_liquidity_offset_history_buckets(&self) -> &[u16; 32] { + if self.source_less_than_target { + &self.tracker.min_liquidity_offset_history.buckets + } else { + &self.tracker.max_liquidity_offset_history.buckets } + } - Some((total_valid_points_tracked, required_decays)) + pub(super) fn max_liquidity_offset_history_buckets(&self) -> &[u16; 32] { + if self.source_less_than_target { + &self.tracker.max_liquidity_offset_history.buckets + } else { + &self.tracker.min_liquidity_offset_history.buckets + } } #[inline] - pub(super) fn calculate_success_probability_times_billion( - &self, now: T, last_updated: T, half_life: Duration, - params: &ProbabilisticScoringFeeParameters, amount_msat: u64, capacity_msat: u64 + pub(super) fn calculate_success_probability_times_billion( + &self, params: &ProbabilisticScoringFeeParameters, amount_msat: u64, + capacity_msat: u64 ) -> Option { // If historical penalties are enabled, we try to calculate a probability of success // given our historical distribution of min- and max-liquidity bounds in a channel. @@ -1890,10 +1754,28 @@ mod bucketed_history { let payment_pos = amount_to_pos(amount_msat, capacity_msat); if payment_pos >= POSITION_TICKS { return None; } - // Check if all our buckets are zero, once decayed and treat it as if we had no data. We - // don't actually use the decayed buckets, though, as that would lose precision. - let (total_valid_points_tracked, _) - = self.get_total_valid_points(now, last_updated, half_life)?; + let min_liquidity_offset_history_buckets = + self.min_liquidity_offset_history_buckets(); + let max_liquidity_offset_history_buckets = + self.max_liquidity_offset_history_buckets(); + + let total_valid_points_tracked = self.tracker.total_valid_points_tracked; + #[cfg(debug_assertions)] { + let mut actual_valid_points_tracked = 0; + for (min_idx, min_bucket) in min_liquidity_offset_history_buckets.iter().enumerate() { + for max_bucket in max_liquidity_offset_history_buckets.iter().take(32 - min_idx) { + actual_valid_points_tracked += (*min_bucket as u64) * (*max_bucket as u64); + } + } + assert_eq!(total_valid_points_tracked, actual_valid_points_tracked); + } + + // If the total valid points is smaller than 1.0 (i.e. 32 in our fixed-point scheme), + // treat it as if we were fully decayed. + const FULLY_DECAYED: u16 = BUCKET_FIXED_POINT_ONE * BUCKET_FIXED_POINT_ONE; + if total_valid_points_tracked < FULLY_DECAYED.into() { + return None; + } let mut cumulative_success_prob_times_billion = 0; // Special-case the 0th min bucket - it generally means we failed a payment, so only @@ -1903,10 +1785,10 @@ mod bucketed_history { // datapoint, many of which may have relatively high maximum-available-liquidity // values, which will result in us thinking we have some nontrivial probability of // routing up to that amount. - if self.min_liquidity_offset_history.buckets[0] != 0 { + if min_liquidity_offset_history_buckets[0] != 0 { let mut highest_max_bucket_with_points = 0; // The highest max-bucket with any data let mut total_max_points = 0; // Total points in max-buckets to consider - for (max_idx, max_bucket) in self.max_liquidity_offset_history.buckets.iter().enumerate() { + for (max_idx, max_bucket) in max_liquidity_offset_history_buckets.iter().enumerate() { if *max_bucket >= BUCKET_FIXED_POINT_ONE { highest_max_bucket_with_points = cmp::max(highest_max_bucket_with_points, max_idx); } @@ -1917,16 +1799,16 @@ mod bucketed_history { let (numerator, denominator) = success_probability(payment_pos as u64, 0, max_bucket_end_pos as u64, POSITION_TICKS as u64 - 1, params, true); let bucket_prob_times_billion = - (self.min_liquidity_offset_history.buckets[0] as u64) * total_max_points + (min_liquidity_offset_history_buckets[0] as u64) * total_max_points * 1024 * 1024 * 1024 / total_valid_points_tracked; cumulative_success_prob_times_billion += bucket_prob_times_billion * numerator / denominator; } } - for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate().skip(1) { + for (min_idx, min_bucket) in min_liquidity_offset_history_buckets.iter().enumerate().skip(1) { let min_bucket_start_pos = BUCKET_START_POS[min_idx]; - for (max_idx, max_bucket) in self.max_liquidity_offset_history.buckets.iter().enumerate().take(32 - min_idx) { + for (max_idx, max_bucket) in max_liquidity_offset_history_buckets.iter().enumerate().take(32 - min_idx) { let max_bucket_end_pos = BUCKET_START_POS[32 - max_idx] - 1; // Note that this multiply can only barely not overflow - two 16 bit ints plus // 30 bits is 62 bits. @@ -1951,9 +1833,9 @@ mod bucketed_history { } } } -use bucketed_history::{LegacyHistoricalBucketRangeTracker, HistoricalBucketRangeTracker, HistoricalMinMaxBuckets}; +use bucketed_history::{LegacyHistoricalBucketRangeTracker, HistoricalBucketRangeTracker, DirectedHistoricalLiquidityTracker, HistoricalLiquidityTracker}; -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, { @@ -1963,8 +1845,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) @@ -1983,24 +1865,24 @@ ReadableArgs<(ProbabilisticScoringDecayParameters, G, L)> for ProbabilisticScore } } -impl Writeable for ChannelLiquidity { +impl Writeable for ChannelLiquidity { #[inline] fn write(&self, w: &mut W) -> Result<(), io::Error> { - let duration_since_epoch = T::duration_since_epoch() - self.last_updated.elapsed(); write_tlv_fields!(w, { (0, self.min_liquidity_offset_msat, required), // 1 was the min_liquidity_offset_history in octile form (2, self.max_liquidity_offset_msat, required), // 3 was the max_liquidity_offset_history in octile form - (4, duration_since_epoch, required), - (5, Some(self.min_liquidity_offset_history), option), - (7, Some(self.max_liquidity_offset_history), option), + (4, self.last_updated, required), + (5, self.liquidity_history.writeable_min_offset_history(), required), + (7, self.liquidity_history.writeable_max_offset_history(), required), + (9, self.offset_history_last_updated, required), }); Ok(()) } } -impl Readable for ChannelLiquidity { +impl Readable for ChannelLiquidity { #[inline] fn read(r: &mut R) -> Result { let mut min_liquidity_offset_msat = 0; @@ -2009,28 +1891,19 @@ impl Readable for ChannelLiquidity { let mut legacy_max_liq_offset_history: Option = None; let mut min_liquidity_offset_history: Option = None; let mut max_liquidity_offset_history: Option = None; - let mut duration_since_epoch = Duration::from_secs(0); + let mut last_updated = Duration::from_secs(0); + let mut offset_history_last_updated = None; read_tlv_fields!(r, { (0, min_liquidity_offset_msat, required), (1, legacy_min_liq_offset_history, option), (2, max_liquidity_offset_msat, required), (3, legacy_max_liq_offset_history, option), - (4, duration_since_epoch, required), + (4, last_updated, required), (5, min_liquidity_offset_history, option), (7, max_liquidity_offset_history, option), + (9, offset_history_last_updated, option), }); - // 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 }; + if min_liquidity_offset_history.is_none() { if let Some(legacy_buckets) = legacy_min_liq_offset_history { min_liquidity_offset_history = Some(legacy_buckets.into_current()); @@ -2048,30 +1921,30 @@ impl Readable for ChannelLiquidity { Ok(Self { min_liquidity_offset_msat, max_liquidity_offset_msat, - min_liquidity_offset_history: min_liquidity_offset_history.unwrap(), - max_liquidity_offset_history: max_liquidity_offset_history.unwrap(), + liquidity_history: HistoricalLiquidityTracker::from_min_max( + min_liquidity_offset_history.unwrap(), max_liquidity_offset_history.unwrap() + ), last_updated, + offset_history_last_updated: offset_history_last_updated.unwrap_or(last_updated), }) } } #[cfg(test)] mod tests { - use super::{ChannelLiquidity, HistoricalBucketRangeTracker, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters, ProbabilisticScorerUsingTime}; + use super::{ChannelLiquidity, HistoricalLiquidityTracker, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters, ProbabilisticScorer}; use crate::blinded_path::{BlindedHop, BlindedPath}; use crate::util::config::UserConfig; - use crate::util::time::Time; - use crate::util::time::tests::SinceEpoch; use crate::ln::channelmanager; use crate::ln::msgs::{ChannelAnnouncement, ChannelUpdate, UnsignedChannelAnnouncement, UnsignedChannelUpdate}; use crate::routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId}; - use crate::routing::router::{BlindedTail, Path, RouteHop}; + use crate::routing::router::{BlindedTail, Path, RouteHop, CandidateRouteHop}; use crate::routing::scoring::{ChannelUsage, ScoreLookUp, ScoreUpdate}; use crate::util::ser::{ReadableArgs, Writeable}; use crate::util::test_utils::{self, TestLogger}; - use bitcoin::blockdata::constants::genesis_block; + use bitcoin::blockdata::constants::ChainHash; use bitcoin::hashes::Hash; use bitcoin::hashes::sha256d::Hash as Sha256dHash; use bitcoin::network::constants::Network; @@ -2107,9 +1980,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() } @@ -2128,10 +1998,6 @@ mod tests { PublicKey::from_secret_key(&secp_ctx, &recipient_privkey()) } - fn sender_node_id() -> NodeId { - NodeId::from_pubkey(&sender_pubkey()) - } - fn recipient_node_id() -> NodeId { NodeId::from_pubkey(&recipient_pubkey()) } @@ -2148,7 +2014,7 @@ mod tests { network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_1_key: SecretKey, node_2_key: SecretKey ) { - let genesis_hash = genesis_block(Network::Testnet).header.block_hash(); + let genesis_hash = ChainHash::using_genesis_block(Network::Testnet); let node_1_secret = &SecretKey::from_slice(&[39; 32]).unwrap(); let node_2_secret = &SecretKey::from_slice(&[40; 32]).unwrap(); let secp_ctx = Secp256k1::new(); @@ -2181,7 +2047,7 @@ mod tests { network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_key: SecretKey, flags: u8, htlc_maximum_msat: u64, timestamp: u32, ) { - let genesis_hash = genesis_block(Network::Testnet).header.block_hash(); + let genesis_hash = ChainHash::using_genesis_block(Network::Testnet); let secp_ctx = Secp256k1::new(); let unsigned_update = UnsignedChannelUpdate { chain_hash: genesis_hash, @@ -2212,6 +2078,7 @@ mod tests { channel_features: channelmanager::provided_channel_features(&config), fee_msat, cltv_expiry_delta: 18, + maybe_announced_channel: true, } } @@ -2228,21 +2095,22 @@ mod tests { #[test] fn liquidity_bounds_directed_from_lowest_node_id() { let logger = TestLogger::new(); - let last_updated = SinceEpoch::now(); + let last_updated = Duration::ZERO; + let offset_history_last_updated = Duration::ZERO; let network_graph = network_graph(&logger); let decay_params = ProbabilisticScoringDecayParameters::default(); let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger) .with_channel(42, ChannelLiquidity { - min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated, - min_liquidity_offset_history: HistoricalBucketRangeTracker::new(), - max_liquidity_offset_history: HistoricalBucketRangeTracker::new(), + min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, + last_updated, offset_history_last_updated, + liquidity_history: HistoricalLiquidityTracker::new(), }) .with_channel(43, ChannelLiquidity { - min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated, - min_liquidity_offset_history: HistoricalBucketRangeTracker::new(), - max_liquidity_offset_history: HistoricalBucketRangeTracker::new(), + min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, + last_updated, offset_history_last_updated, + liquidity_history: HistoricalLiquidityTracker::new(), }); let source = source_node_id(); let target = target_node_id(); @@ -2253,52 +2121,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) - .set_min_liquidity_msat(200); + .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) - .set_max_liquidity_msat(200); + .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); } @@ -2306,15 +2174,16 @@ mod tests { #[test] fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() { let logger = TestLogger::new(); - let last_updated = SinceEpoch::now(); + let last_updated = Duration::ZERO; + let offset_history_last_updated = Duration::ZERO; let network_graph = network_graph(&logger); let decay_params = ProbabilisticScoringDecayParameters::default(); let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger) .with_channel(42, ChannelLiquidity { - min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated, - min_liquidity_offset_history: HistoricalBucketRangeTracker::new(), - max_liquidity_offset_history: HistoricalBucketRangeTracker::new(), + min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, + last_updated, offset_history_last_updated, + liquidity_history: HistoricalLiquidityTracker::new(), }); let source = source_node_id(); let target = target_node_id(); @@ -2322,42 +2191,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) - .set_min_liquidity_msat(900); + .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) - .set_min_liquidity_msat(400); + .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); } @@ -2365,15 +2234,16 @@ mod tests { #[test] fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() { let logger = TestLogger::new(); - let last_updated = SinceEpoch::now(); + let last_updated = Duration::ZERO; + let offset_history_last_updated = Duration::ZERO; let network_graph = network_graph(&logger); let decay_params = ProbabilisticScoringDecayParameters::default(); let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger) .with_channel(42, ChannelLiquidity { - min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated, - min_liquidity_offset_history: HistoricalBucketRangeTracker::new(), - max_liquidity_offset_history: HistoricalBucketRangeTracker::new(), + min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, + last_updated, offset_history_last_updated, + liquidity_history: HistoricalLiquidityTracker::new(), }); let source = source_node_id(); let target = target_node_id(); @@ -2381,42 +2251,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) - .set_max_liquidity_msat(300); + .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) - .set_max_liquidity_msat(600); + .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); } @@ -2432,45 +2302,52 @@ mod tests { let decay_params = ProbabilisticScoringDecayParameters::default(); let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger); let source = source_node_id(); - let target = target_node_id(); let usage = ChannelUsage { amount_msat: 1_024, inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 }, }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); + let network_graph = network_graph.read_only(); + let channel = network_graph.channel(42).unwrap(); + 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), 0); let usage = ChannelUsage { amount_msat: 10_240, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0); let usage = ChannelUsage { amount_msat: 102_400, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 47); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 47); let usage = ChannelUsage { amount_msat: 1_023_999, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2_000); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 2_000); let usage = ChannelUsage { amount_msat: 128, inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 }, }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 58); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 58); let usage = ChannelUsage { amount_msat: 256, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 125); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 125); let usage = ChannelUsage { amount_msat: 374, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 198); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 198); let usage = ChannelUsage { amount_msat: 512, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300); let usage = ChannelUsage { amount_msat: 640, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 425); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 425); let usage = ChannelUsage { amount_msat: 768, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 602); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 602); let usage = ChannelUsage { amount_msat: 896, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 902); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 902); } #[test] fn constant_penalty_outside_liquidity_bounds() { let logger = TestLogger::new(); - let last_updated = SinceEpoch::now(); + let last_updated = Duration::ZERO; + let offset_history_last_updated = Duration::ZERO; let network_graph = network_graph(&logger); let params = ProbabilisticScoringFeeParameters { liquidity_penalty_multiplier_msat: 1_000, @@ -2483,24 +2360,29 @@ mod tests { let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger) .with_channel(42, ChannelLiquidity { - min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40, last_updated, - min_liquidity_offset_history: HistoricalBucketRangeTracker::new(), - max_liquidity_offset_history: HistoricalBucketRangeTracker::new(), + min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40, + last_updated, offset_history_last_updated, + liquidity_history: HistoricalLiquidityTracker::new(), }); let source = source_node_id(); - let target = target_node_id(); let usage = ChannelUsage { amount_msat: 39, inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat: 100, htlc_maximum_msat: 1_000 }, }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); + 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), 0); let usage = ChannelUsage { amount_msat: 50, ..usage }; - assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); - assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); + assert_ne!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0); + assert_ne!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); let usage = ChannelUsage { amount_msat: 61, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); } #[test] @@ -2512,7 +2394,6 @@ mod tests { ..ProbabilisticScoringFeeParameters::zero_penalty() }; let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); - let sender = sender_node_id(); let source = source_node_id(); let usage = ChannelUsage { amount_msat: 500, @@ -2521,14 +2402,20 @@ mod tests { }; let failed_path = payment_path_for_amount(500); let successful_path = payment_path_for_amount(200); + 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: 41, + }; - assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 301); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 301); - scorer.payment_path_failed(&failed_path, 41); - assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 301); + scorer.payment_path_failed(&failed_path, 41, Duration::ZERO); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 301); - scorer.payment_path_successful(&successful_path); - assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 301); + scorer.payment_path_successful(&successful_path, Duration::ZERO); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 301); } #[test] @@ -2541,7 +2428,6 @@ mod tests { }; let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); let source = source_node_id(); - let target = target_node_id(); let path = payment_path_for_amount(500); let usage = ChannelUsage { @@ -2549,20 +2435,26 @@ mod tests { inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 }, }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 128); + 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), 128); let usage = ChannelUsage { amount_msat: 500, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 301); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 301); let usage = ChannelUsage { amount_msat: 750, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 602); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 602); - scorer.payment_path_failed(&path, 43); + scorer.payment_path_failed(&path, 43, Duration::ZERO); let usage = ChannelUsage { amount_msat: 250, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0); let usage = ChannelUsage { amount_msat: 500, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0); let usage = ChannelUsage { amount_msat: 750, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300); } #[test] @@ -2576,7 +2468,6 @@ mod tests { }; let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); let source = source_node_id(); - let target = target_node_id(); let path = payment_path_for_amount(500); let usage = ChannelUsage { @@ -2584,20 +2475,26 @@ mod tests { inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 }, }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 128); + 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), 128); let usage = ChannelUsage { amount_msat: 500, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 301); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 301); let usage = ChannelUsage { amount_msat: 750, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 602); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 602); - scorer.payment_path_failed(&path, 42); + scorer.payment_path_failed(&path, 42, Duration::ZERO); let usage = ChannelUsage { amount_msat: 250, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300); let usage = ChannelUsage { amount_msat: 500, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); let usage = ChannelUsage { amount_msat: 750, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); } #[test] @@ -2632,7 +2529,6 @@ mod tests { let node_a = NodeId::from_pubkey(&pub_a); let node_b = NodeId::from_pubkey(&pub_b); let node_c = NodeId::from_pubkey(&pub_c); - let node_d = NodeId::from_pubkey(&pub_d); let params = ProbabilisticScoringFeeParameters { liquidity_penalty_multiplier_msat: 1_000, @@ -2645,17 +2541,53 @@ mod tests { inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 }, }; - assert_eq!(scorer.channel_penalty_msat(42, &node_a, &node_b, usage, ¶ms), 128); + let channel = network_graph.read_only().channel(42).unwrap().to_owned(); + let (info, _) = channel.as_directed_from(&node_a).unwrap(); + let candidate = CandidateRouteHop::PublicHop { + info, + short_channel_id: 42, + }; + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 128); // Note that a default liquidity bound is used for B -> C as no channel exists - assert_eq!(scorer.channel_penalty_msat(43, &node_b, &node_c, usage, ¶ms), 128); - assert_eq!(scorer.channel_penalty_msat(44, &node_c, &node_d, usage, ¶ms), 128); - - scorer.payment_path_failed(&Path { hops: path, blinded_tail: None }, 43); - - assert_eq!(scorer.channel_penalty_msat(42, &node_a, &node_b, usage, ¶ms), 80); + let channel = network_graph.read_only().channel(42).unwrap().to_owned(); + let (info, _) = channel.as_directed_from(&node_b).unwrap(); + let candidate = CandidateRouteHop::PublicHop { + info, + short_channel_id: 43, + }; + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 128); + let channel = network_graph.read_only().channel(44).unwrap().to_owned(); + let (info, _) = channel.as_directed_from(&node_c).unwrap(); + let candidate = CandidateRouteHop::PublicHop { + info, + short_channel_id: 44, + }; + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 128); + + scorer.payment_path_failed(&Path { hops: path, blinded_tail: None }, 43, Duration::ZERO); + + let channel = network_graph.read_only().channel(42).unwrap().to_owned(); + let (info, _) = channel.as_directed_from(&node_a).unwrap(); + let candidate = CandidateRouteHop::PublicHop { + info, + short_channel_id: 42, + }; + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 80); // Note that a default liquidity bound is used for B -> C as no channel exists - assert_eq!(scorer.channel_penalty_msat(43, &node_b, &node_c, usage, ¶ms), 128); - assert_eq!(scorer.channel_penalty_msat(44, &node_c, &node_d, usage, ¶ms), 128); + let channel = network_graph.read_only().channel(42).unwrap().to_owned(); + let (info, _) = channel.as_directed_from(&node_b).unwrap(); + let candidate = CandidateRouteHop::PublicHop { + info, + short_channel_id: 43, + }; + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 128); + let channel = network_graph.read_only().channel(44).unwrap().to_owned(); + let (info, _) = channel.as_directed_from(&node_c).unwrap(); + let candidate = CandidateRouteHop::PublicHop { + info, + short_channel_id: 44, + }; + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 128); } #[test] @@ -2667,25 +2599,39 @@ mod tests { ..ProbabilisticScoringFeeParameters::zero_penalty() }; let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); - let sender = sender_node_id(); let source = source_node_id(); - let target = target_node_id(); - let recipient = recipient_node_id(); let usage = ChannelUsage { amount_msat: 250, inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 }, }; + let network_graph = network_graph.read_only().channels().clone(); + let channel_42 = network_graph.get(&42).unwrap(); + let channel_43 = network_graph.get(&43).unwrap(); + let (info, _) = channel_42.as_directed_from(&source).unwrap(); + let candidate_41 = CandidateRouteHop::PublicHop { + info, + short_channel_id: 41, + }; + let (info, target) = channel_42.as_directed_from(&source).unwrap(); + let candidate_42 = CandidateRouteHop::PublicHop { + info, + short_channel_id: 42, + }; + let (info, _) = channel_43.as_directed_from(&target).unwrap(); + let candidate_43 = CandidateRouteHop::PublicHop { + info, + short_channel_id: 43, + }; + assert_eq!(scorer.channel_penalty_msat(&candidate_41, usage, ¶ms), 128); + assert_eq!(scorer.channel_penalty_msat(&candidate_42, usage, ¶ms), 128); + assert_eq!(scorer.channel_penalty_msat(&candidate_43, usage, ¶ms), 128); - assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 128); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 128); - assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage, ¶ms), 128); - - scorer.payment_path_successful(&payment_path_for_amount(500)); + scorer.payment_path_successful(&payment_path_for_amount(500), Duration::ZERO); - assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 128); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300); - assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage, ¶ms), 300); + assert_eq!(scorer.channel_penalty_msat(&candidate_41, usage, ¶ms), 128); + assert_eq!(scorer.channel_penalty_msat(&candidate_42, usage, ¶ms), 300); + assert_eq!(scorer.channel_penalty_msat(&candidate_43, usage, ¶ms), 300); } #[test] @@ -2703,120 +2649,80 @@ mod tests { }; let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger); let source = source_node_id(); - let target = target_node_id(); let usage = ChannelUsage { amount_msat: 0, inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 }, }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); + 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), 0); let usage = ChannelUsage { amount_msat: 1_023, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2_000); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 2_000); - scorer.payment_path_failed(&payment_path_for_amount(768), 42); - scorer.payment_path_failed(&payment_path_for_amount(128), 43); + scorer.payment_path_failed(&payment_path_for_amount(768), 42, Duration::ZERO); + scorer.payment_path_failed(&payment_path_for_amount(128), 43, Duration::ZERO); // Initial penalties let usage = ChannelUsage { amount_msat: 128, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); - let usage = ChannelUsage { amount_msat: 256, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 93); - let usage = ChannelUsage { amount_msat: 768, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1_479); - let usage = ChannelUsage { amount_msat: 896, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); - - // No decay - SinceEpoch::advance(Duration::from_secs(4)); - let usage = ChannelUsage { amount_msat: 128, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0); let usage = ChannelUsage { amount_msat: 256, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 93); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 93); let usage = ChannelUsage { amount_msat: 768, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1_479); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 1_479); let usage = ChannelUsage { amount_msat: 896, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); // Half decay (i.e., three-quarter life) - SinceEpoch::advance(Duration::from_secs(1)); + scorer.decay_liquidity_certainty(Duration::from_secs(5)); let usage = ChannelUsage { amount_msat: 128, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 22); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 22); let usage = ChannelUsage { amount_msat: 256, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 106); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 106); let usage = ChannelUsage { amount_msat: 768, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 921); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 921); let usage = ChannelUsage { amount_msat: 896, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); + 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.decay_liquidity_certainty(Duration::from_secs(10)); let usage = ChannelUsage { amount_msat: 64, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0); let usage = ChannelUsage { amount_msat: 128, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 34); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 34); let usage = ChannelUsage { amount_msat: 896, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1_970); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 1_970); let usage = ChannelUsage { amount_msat: 960, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); + 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.decay_liquidity_certainty(Duration::from_secs(10 * 8)); let usage = ChannelUsage { amount_msat: 0, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0); let usage = ChannelUsage { amount_msat: 1, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0); let usage = ChannelUsage { amount_msat: 1_023, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2_000); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 2_000); let usage = ChannelUsage { amount_msat: 1_024, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); // Fully decay liquidity upper bound. - SinceEpoch::advance(Duration::from_secs(10)); + scorer.decay_liquidity_certainty(Duration::from_secs(10 * 9)); let usage = ChannelUsage { amount_msat: 0, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0); let usage = ChannelUsage { amount_msat: 1_024, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); - SinceEpoch::advance(Duration::from_secs(10)); + scorer.decay_liquidity_certainty(Duration::from_secs(10 * 10)); let usage = ChannelUsage { amount_msat: 0, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0); let usage = ChannelUsage { amount_msat: 1_024, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, 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 target = target_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 }, - }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 125); - - scorer.payment_path_failed(&payment_path_for_amount(512), 42); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, 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)); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 125); - - SinceEpoch::advance(Duration::from_secs(10)); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 125); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); } #[test] @@ -2833,37 +2739,42 @@ mod tests { }; let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger); let source = source_node_id(); - let target = target_node_id(); let usage = ChannelUsage { amount_msat: 512, 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(42, &source, &target, usage, ¶ms), 300); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300); // More knowledge gives higher confidence (256, 768), meaning a lower penalty. - scorer.payment_path_failed(&payment_path_for_amount(768), 42); - scorer.payment_path_failed(&payment_path_for_amount(256), 43); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 281); + scorer.payment_path_failed(&payment_path_for_amount(768), 42, Duration::ZERO); + scorer.payment_path_failed(&payment_path_for_amount(256), 43, Duration::ZERO); + 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)); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 291); + scorer.decay_liquidity_certainty(Duration::from_secs(10)); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 291); // Reducing the upper bound gives more confidence (128, 832) that the payment amount (512) // is closer to the upper bound, meaning a higher penalty. - scorer.payment_path_successful(&payment_path_for_amount(64)); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 331); + scorer.payment_path_successful(&payment_path_for_amount(64), Duration::from_secs(10)); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 331); // Increasing the lower bound gives more confidence (256, 832) that the payment amount (512) // is closer to the lower bound, meaning a lower penalty. - scorer.payment_path_failed(&payment_path_for_amount(256), 43); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 245); + scorer.payment_path_failed(&payment_path_for_amount(256), 43, Duration::from_secs(10)); + 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)); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 280); + scorer.decay_liquidity_certainty(Duration::from_secs(20)); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 280); } #[test] @@ -2881,33 +2792,37 @@ mod tests { }; let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger); let source = source_node_id(); - let target = target_node_id(); let usage = ChannelUsage { amount_msat: 500, inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 }, }; - scorer.payment_path_failed(&payment_path_for_amount(500), 42); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); + scorer.payment_path_failed(&payment_path_for_amount(500), 42, Duration::ZERO); + 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), u64::max_value()); - SinceEpoch::advance(Duration::from_secs(10)); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 473); + scorer.decay_liquidity_certainty(Duration::from_secs(10)); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 473); - scorer.payment_path_failed(&payment_path_for_amount(250), 43); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300); + scorer.payment_path_failed(&payment_path_for_amount(250), 43, Duration::from_secs(10)); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300); let mut serialized_scorer = Vec::new(); scorer.write(&mut serialized_scorer).unwrap(); let mut serialized_scorer = io::Cursor::new(&serialized_scorer); let deserialized_scorer = - ::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap(); - assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300); + >::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap(); + assert_eq!(deserialized_scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300); } - #[test] - fn decays_persisted_liquidity_bounds() { + fn do_decays_persisted_liquidity_bounds(decay_before_reload: bool) { let logger = TestLogger::new(); let network_graph = network_graph(&logger); let params = ProbabilisticScoringFeeParameters { @@ -2921,31 +2836,48 @@ mod tests { }; let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger); let source = source_node_id(); - let target = target_node_id(); let usage = ChannelUsage { amount_msat: 500, inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 }, }; - scorer.payment_path_failed(&payment_path_for_amount(500), 42); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); + scorer.payment_path_failed(&payment_path_for_amount(500), 42, Duration::ZERO); + 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), u64::max_value()); + + if decay_before_reload { + scorer.decay_liquidity_certainty(Duration::from_secs(10)); + } let mut serialized_scorer = Vec::new(); scorer.write(&mut serialized_scorer).unwrap(); - SinceEpoch::advance(Duration::from_secs(10)); - let mut serialized_scorer = io::Cursor::new(&serialized_scorer); - let deserialized_scorer = - ::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap(); - assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 473); + let mut deserialized_scorer = + >::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap(); + if !decay_before_reload { + scorer.decay_liquidity_certainty(Duration::from_secs(10)); + deserialized_scorer.decay_liquidity_certainty(Duration::from_secs(10)); + } + assert_eq!(deserialized_scorer.channel_penalty_msat(&candidate, usage, ¶ms), 473); + + scorer.payment_path_failed(&payment_path_for_amount(250), 43, Duration::from_secs(10)); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300); - scorer.payment_path_failed(&payment_path_for_amount(250), 43); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300); + deserialized_scorer.decay_liquidity_certainty(Duration::from_secs(20)); + assert_eq!(deserialized_scorer.channel_penalty_msat(&candidate, usage, ¶ms), 370); + } - SinceEpoch::advance(Duration::from_secs(10)); - assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 370); + #[test] + fn decays_persisted_liquidity_bounds() { + do_decays_persisted_liquidity_bounds(false); + do_decays_persisted_liquidity_bounds(true); } #[test] @@ -2957,54 +2889,59 @@ mod tests { let params = ProbabilisticScoringFeeParameters::default(); let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); let source = source_node_id(); - let target = target_node_id(); let usage = ChannelUsage { amount_msat: 100_000_000, inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat: 950_000_000, htlc_maximum_msat: 1_000 }, }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 6262); + 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), 11497); let usage = ChannelUsage { effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_950_000_000, htlc_maximum_msat: 1_000 }, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 4634); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 7408); let usage = ChannelUsage { effective_capacity: EffectiveCapacity::Total { capacity_msat: 2_950_000_000, htlc_maximum_msat: 1_000 }, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 4186); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 6151); let usage = ChannelUsage { effective_capacity: EffectiveCapacity::Total { capacity_msat: 3_950_000_000, htlc_maximum_msat: 1_000 }, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 3909); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 5427); let usage = ChannelUsage { effective_capacity: EffectiveCapacity::Total { capacity_msat: 4_950_000_000, htlc_maximum_msat: 1_000 }, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 3556); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 4955); let usage = ChannelUsage { effective_capacity: EffectiveCapacity::Total { capacity_msat: 5_950_000_000, htlc_maximum_msat: 1_000 }, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 3533); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 4736); let usage = ChannelUsage { effective_capacity: EffectiveCapacity::Total { capacity_msat: 6_950_000_000, htlc_maximum_msat: 1_000 }, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 3172); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 4484); let usage = ChannelUsage { effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_450_000_000, htlc_maximum_msat: 1_000 }, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 3211); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 4484); let usage = ChannelUsage { effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_950_000_000, htlc_maximum_msat: 1_000 }, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 3243); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 4263); let usage = ChannelUsage { effective_capacity: EffectiveCapacity::Total { capacity_msat: 8_950_000_000, htlc_maximum_msat: 1_000 }, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 3297); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 4263); let usage = ChannelUsage { effective_capacity: EffectiveCapacity::Total { capacity_msat: 9_950_000_000, htlc_maximum_msat: 1_000 }, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 3250); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 4044); } #[test] @@ -3012,7 +2949,6 @@ mod tests { let logger = TestLogger::new(); let network_graph = network_graph(&logger); let source = source_node_id(); - let target = target_node_id(); let usage = ChannelUsage { amount_msat: 128, inflight_htlc_msat: 0, @@ -3024,14 +2960,20 @@ mod tests { ..ProbabilisticScoringFeeParameters::zero_penalty() }; let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 58); + 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), 58); let params = ProbabilisticScoringFeeParameters { base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000, anti_probing_penalty_msat: 0, ..ProbabilisticScoringFeeParameters::zero_penalty() }; let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 558); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 558); let params = ProbabilisticScoringFeeParameters { base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000, @@ -3040,7 +2982,7 @@ mod tests { }; let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 558 + 128); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 558 + 128); } #[test] @@ -3048,7 +2990,6 @@ mod tests { let logger = TestLogger::new(); let network_graph = network_graph(&logger); let source = source_node_id(); - let target = target_node_id(); let usage = ChannelUsage { amount_msat: 512_000, inflight_htlc_msat: 0, @@ -3061,7 +3002,13 @@ mod tests { ..ProbabilisticScoringFeeParameters::zero_penalty() }; let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300); + 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), 300); let params = ProbabilisticScoringFeeParameters { liquidity_penalty_multiplier_msat: 1_000, @@ -3069,7 +3016,7 @@ mod tests { ..ProbabilisticScoringFeeParameters::zero_penalty() }; let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 337); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 337); } #[test] @@ -3077,20 +3024,24 @@ mod tests { let logger = TestLogger::new(); let network_graph = network_graph(&logger); let source = source_node_id(); - let target = target_node_id(); let usage = ChannelUsage { amount_msat: u64::max_value(), inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Infinite, }; - let params = ProbabilisticScoringFeeParameters { liquidity_penalty_multiplier_msat: 40_000, ..ProbabilisticScoringFeeParameters::zero_penalty() }; let decay_params = ProbabilisticScoringDecayParameters::zero_penalty(); + 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, + }; let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 80_000); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 80_000); } #[test] @@ -3103,17 +3054,23 @@ mod tests { }; let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); let source = source_node_id(); - let target = target_node_id(); let usage = ChannelUsage { amount_msat: 750, inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 }, }; - assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); + let network_graph = network_graph.read_only(); + let channel = network_graph.channel(42).unwrap(); + let (info, _) = channel.as_directed_from(&source).unwrap(); + let candidate = CandidateRouteHop::PublicHop { + info, + short_channel_id: 42, + }; + assert_ne!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); let usage = ChannelUsage { inflight_htlc_msat: 251, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); } #[test] @@ -3123,7 +3080,6 @@ mod tests { let params = ProbabilisticScoringFeeParameters::default(); let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); let source = source_node_id(); - let target = target_node_id(); let base_penalty_msat = params.base_penalty_msat; let usage = ChannelUsage { @@ -3131,13 +3087,20 @@ mod tests { inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::ExactLiquidity { liquidity_msat: 1_000 }, }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), base_penalty_msat); + let network_graph = network_graph.read_only(); + let channel = network_graph.channel(42).unwrap(); + 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), base_penalty_msat); let usage = ChannelUsage { amount_msat: 1_000, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), base_penalty_msat); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), base_penalty_msat); let usage = ChannelUsage { amount_msat: 1_001, ..usage }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value()); } #[test] @@ -3168,16 +3131,36 @@ mod tests { effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 }, }; - // With no historical data the normal liquidity penalty calculation is used. - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 168); + { + let network_graph = network_graph.read_only(); + let channel = network_graph.channel(42).unwrap(); + let (info, _) = channel.as_directed_from(&source).unwrap(); + let candidate = CandidateRouteHop::PublicHop { + info, + short_channel_id: 42, + }; + + // With no historical data the normal liquidity penalty calculation is used. + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 168); + } assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target), - None); + None); assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 42, ¶ms), - None); + None); + + scorer.payment_path_failed(&payment_path_for_amount(1), 42, Duration::ZERO); + { + let network_graph = network_graph.read_only(); + let channel = network_graph.channel(42).unwrap(); + let (info, _) = channel.as_directed_from(&source).unwrap(); + let candidate = CandidateRouteHop::PublicHop { + info, + short_channel_id: 42, + }; - scorer.payment_path_failed(&payment_path_for_amount(1), 42); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2048); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage_1, ¶ms), 249); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 2048); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage_1, ¶ms), 249); + } // The "it failed" increment is 32, where the probability should lie several buckets into // the first octile. assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target), @@ -3190,8 +3173,18 @@ mod tests { // Even after we tell the scorer we definitely have enough available liquidity, it will // still remember that there was some failure in the past, and assign a non-0 penalty. - scorer.payment_path_failed(&payment_path_for_amount(1000), 43); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 105); + scorer.payment_path_failed(&payment_path_for_amount(1000), 43, Duration::ZERO); + { + let network_graph = network_graph.read_only(); + let channel = network_graph.channel(42).unwrap(); + 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), 105); + } // The first points should be decayed just slightly and the last bucket has a new point. assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target), Some(([31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0], @@ -3210,12 +3203,22 @@ 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)); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 168); + scorer.decay_liquidity_certainty(Duration::from_secs(10 * 16)); + { + let network_graph = network_graph.read_only(); + let channel = network_graph.channel(42).unwrap(); + 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), 168); + } // Once fully decayed we still have data, but its all-0s. In the future we may remove the // data entirely instead. assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target), - None); + Some(([0; 32], [0; 32]))); assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 1, ¶ms), None); let mut usage = ChannelUsage { @@ -3223,20 +3226,33 @@ mod tests { inflight_htlc_msat: 1024, effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 }, }; - scorer.payment_path_failed(&payment_path_for_amount(1), 42); - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2050); - usage.inflight_htlc_msat = 0; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 866); + scorer.payment_path_failed(&payment_path_for_amount(1), 42, Duration::from_secs(10 * 16)); + { + let network_graph = network_graph.read_only(); + let channel = network_graph.channel(42).unwrap(); + let (info, _) = channel.as_directed_from(&source).unwrap(); + let candidate = CandidateRouteHop::PublicHop { + info, + short_channel_id: 42, + }; - let usage = ChannelUsage { - amount_msat: 1, - inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::AdvertisedMaxHTLC { amount_msat: 0 }, - }; - assert_eq!(scorer.channel_penalty_msat(42, &target, &source, usage, ¶ms), 2048); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 2050); + + let usage = ChannelUsage { + amount_msat: 1, + inflight_htlc_msat: 0, + effective_capacity: EffectiveCapacity::AdvertisedMaxHTLC { amount_msat: 0 }, + }; + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 2048); + } // Advance to decay all liquidity offsets to zero. - SinceEpoch::advance(Duration::from_secs(60 * 60 * 10)); + scorer.decay_liquidity_certainty(Duration::from_secs(10 * (16 + 60 * 60))); + + // Once even the bounds have decayed information about the channel should be removed + // entirely. + assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target), + None); // Use a path in the opposite direction, which have zero for htlc_maximum_msat. This will // ensure that the effective capacity is zero to test division-by-zero edge cases. @@ -3245,7 +3261,7 @@ mod tests { path_hop(source_pubkey(), 42, 1), path_hop(sender_pubkey(), 41, 0), ]; - scorer.payment_path_failed(&Path { hops: path, blinded_tail: None }, 42); + scorer.payment_path_failed(&Path { hops: path, blinded_tail: None }, 42, Duration::from_secs(10 * (16 + 60 * 60))); } #[test] @@ -3253,7 +3269,6 @@ mod tests { let logger = TestLogger::new(); let network_graph = network_graph(&logger); let source = source_node_id(); - let target = target_node_id(); let params = ProbabilisticScoringFeeParameters { anti_probing_penalty_msat: 500, ..ProbabilisticScoringFeeParameters::zero_penalty() @@ -3266,7 +3281,14 @@ mod tests { inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 }, }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); + let network_graph = network_graph.read_only(); + let channel = network_graph.channel(42).unwrap(); + 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), 0); // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity. let usage = ChannelUsage { @@ -3274,7 +3296,7 @@ mod tests { inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_024_000 }, }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 500); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 500); // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity/2. let usage = ChannelUsage { @@ -3282,7 +3304,7 @@ mod tests { inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 512_000 }, }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 500); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 500); // Check we receive no anti-probing penalty for htlc_maximum_msat == channel_capacity/2 - 1. let usage = ChannelUsage { @@ -3290,7 +3312,7 @@ mod tests { inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 511_999 }, }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0); } #[test] @@ -3305,13 +3327,18 @@ mod tests { let decay_params = ProbabilisticScoringDecayParameters::default(); let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger); let source = source_node_id(); - let target = target_node_id(); let usage = ChannelUsage { amount_msat: 512, inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 }, }; - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300); + let channel = network_graph.read_only().channel(42).unwrap().to_owned(); + let (info, target) = channel.as_directed_from(&source).unwrap(); + let candidate = CandidateRouteHop::PublicHop { + info, + short_channel_id: 42, + }; + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300); let mut path = payment_path_for_amount(768); let recipient_hop = path.hops.pop().unwrap(); @@ -3333,12 +3360,12 @@ mod tests { // final value is taken into account. assert!(scorer.channel_liquidities.get(&42).is_none()); - scorer.payment_path_failed(&path, 42); + scorer.payment_path_failed(&path, 42, Duration::ZERO); path.blinded_tail.as_mut().unwrap().final_value_msat = 256; - scorer.payment_path_failed(&path, 43); + 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); } @@ -3367,7 +3394,6 @@ mod tests { let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger); let source = source_node_id(); - let target = target_node_id(); let mut amount_msat = 10_000_000; let usage = ChannelUsage { @@ -3375,19 +3401,25 @@ mod tests { inflight_htlc_msat: 0, effective_capacity: EffectiveCapacity::Total { capacity_msat, htlc_maximum_msat: capacity_msat }, }; + let channel = network_graph.read_only().channel(42).unwrap().to_owned(); + let (info, target) = channel.as_directed_from(&source).unwrap(); + let candidate = CandidateRouteHop::PublicHop { + info, + short_channel_id: 42, + }; // With no historical data the normal liquidity penalty calculation is used, which results // in a success probability of ~75%. - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1269); + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 1269); assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target), None); assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 42, ¶ms), None); // Fail to pay once, and then check the buckets and penalty. - scorer.payment_path_failed(&payment_path_for_amount(amount_msat), 42); + scorer.payment_path_failed(&payment_path_for_amount(amount_msat), 42, Duration::ZERO); // The penalty should be the maximum penalty, as the payment we're scoring is now in the // same bucket which is the only maximum datapoint. - assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), + assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 2048 + 2048 * amount_msat / super::AMOUNT_PENALTY_DIVISOR); // The "it failed" increment is 32, which we should apply to the first upper-bound (between // 6k sats and 12k sats). @@ -3408,7 +3440,7 @@ mod tests { // ...but once we see a failure, we consider the payment to be substantially less likely, // even though not a probability of zero as we still look at the second max bucket which // now shows 31. - scorer.payment_path_failed(&payment_path_for_amount(amount_msat), 42); + scorer.payment_path_failed(&payment_path_for_amount(amount_msat), 42, Duration::ZERO); assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target), Some(([63, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [32, 31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]))); @@ -3416,3 +3448,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.decay_liquidity_certainty(cur_time); + bench.bench_function("decay_100k_channel_bounds", |b| b.iter(|| { + cur_time += Duration::from_millis(1); + scorer.decay_liquidity_certainty(cur_time); + })); + } +}