From 3986f98ec1fb9b8abc54675d1305e94ecd429a0a Mon Sep 17 00:00:00 2001 From: Jeffrey Czyz Date: Tue, 4 Jan 2022 18:15:59 -0600 Subject: [PATCH] Decay channel liquidity balance offsets ProbabilisticScorer uses successful and unsuccessful payments to gain more certainty of a channel's liquidity balance. Decay this knowledge over time to indicate decreasing certainty about the liquidity balance. --- lightning/src/routing/scoring.rs | 490 ++++++++++++++++++++++++------- 1 file changed, 392 insertions(+), 98 deletions(-) diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index 47c5dc966..bf6c11089 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -189,16 +189,6 @@ impl<'a, S: Writeable> Writeable for MutexGuard<'a, S> { } } -/// [`Score`] implementation that provides reasonable default behavior. -/// -/// Used to apply a fixed penalty to each channel, thus avoiding long paths when shorter paths with -/// slightly higher fees are available. Will further penalize channels that fail to relay payments. -/// -/// See [module-level documentation] for usage. -/// -/// [module-level documentation]: crate::routing::scoring -#[cfg(not(feature = "no-std"))] -pub type Scorer = ScorerUsingTime::; /// [`Score`] implementation that provides reasonable default behavior. /// /// Used to apply a fixed penalty to each channel, thus avoiding long paths when shorter paths with @@ -207,8 +197,12 @@ pub type Scorer = ScorerUsingTime::; /// See [module-level documentation] for usage and [`ScoringParameters`] for customization. /// /// [module-level documentation]: crate::routing::scoring +pub type Scorer = ScorerUsingTime::; + +#[cfg(not(feature = "no-std"))] +type ConfiguredTime = std::time::Instant; #[cfg(feature = "no-std")] -pub type Scorer = ScorerUsingTime::; +type ConfiguredTime = time::Eternity; // Note that ideally we'd hide ScorerUsingTime from public view by sealing it as well, but rustdoc // doesn't handle this well - instead exposing a `Scorer` which has no trait implementation(s) or @@ -216,14 +210,13 @@ pub type Scorer = ScorerUsingTime::; /// [`Score`] implementation. /// -/// See [`Scorer`] for details. -/// /// # Note /// /// Mixing the `no-std` feature between serialization and deserialization results in undefined /// behavior. /// /// (C-not exported) generally all users should use the [`Scorer`] type alias. +#[doc(hidden)] pub struct ScorerUsingTime { params: ScoringParameters, // TODO: Remove entries of closed channels. @@ -269,6 +262,8 @@ pub struct ScoringParameters { /// /// Successfully routing through a channel will immediately cut the penalty in half as well. /// + /// Default value: 1 hour + /// /// # Note /// /// When built with the `no-std` feature, time will never elapse. Therefore, this penalty will @@ -461,15 +456,31 @@ impl Readable for ChannelFailure { /// Then the negative log of the success probability is used to determine the cost of routing a /// specific HTLC amount through a channel. /// +/// Knowledge about channel liquidity balances takes the form of upper and lower bounds on the +/// possible liquidity. Certainty of the bounds is decreased over time using a decay function. See +/// [`ProbabilisticScoringParameters`] for details. +/// /// [1]: https://arxiv.org/abs/2107.05322 -pub struct ProbabilisticScorer> { +pub type ProbabilisticScorer = ProbabilisticScorerUsingTime::; + +/// Probabilistic [`Score`] implementation. +/// +/// # Note +/// +/// Mixing the `no-std` feature between serialization and deserialization results in undefined +/// behavior. +/// +/// (C-not exported) generally all users should use the [`ProbabilisticScorer`] type alias. +#[doc(hidden)] +pub struct ProbabilisticScorerUsingTime, T: Time> { params: ProbabilisticScoringParameters, network_graph: G, // TODO: Remove entries of closed channels. - channel_liquidities: HashMap, + channel_liquidities: HashMap>, } /// Parameters for configuring [`ProbabilisticScorer`]. +#[derive(Clone, Copy)] pub struct ProbabilisticScoringParameters { /// A penalty applied after multiplying by the negative log of the channel's success probability /// for a payment. @@ -477,14 +488,33 @@ pub struct ProbabilisticScoringParameters { /// The success probability is determined by the effective channel capacity, the payment amount, /// and knowledge learned from prior successful and unsuccessful payments. The lower bound of /// the success probability is 0.01, effectively limiting the penalty to the range - /// `0..=2*liquidity_penalty_multiplier_msat`. + /// `0..=2*liquidity_penalty_multiplier_msat`. The knowledge learned is reduced over time based + /// on [`liquidity_offset_half_life`]. /// /// Default value: 10,000 msat + /// + /// [`liquidity_offset_half_life`]: Self::liquidity_offset_half_life pub liquidity_penalty_multiplier_msat: u64, + + /// The time required to elapse before any knowledge learned about channel liquidity balances is + /// cut in half. + /// + /// The bounds are defined in terms offsets and are initially zero. Increasing the offsets gives + /// tighter bounds on the channel liquidity balance. Thus, halving the offsets decreases the + /// certainty of the channel liquidity balance. + /// + /// Default value: 1 hour + /// + /// # Note + /// + /// When built with the `no-std` feature, time will never elapse. Therefore, the channel + /// liquidity knowledge will never decay except when the bounds cross. + pub liquidity_offset_half_life: Duration, } impl_writeable_tlv_based!(ProbabilisticScoringParameters, { (0, liquidity_penalty_multiplier_msat, required), + (2, liquidity_offset_half_life, required), }); /// Accounting for channel liquidity balance uncertainty. @@ -492,22 +522,27 @@ impl_writeable_tlv_based!(ProbabilisticScoringParameters, { /// 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, + last_updated: T, } -/// A view of [`ChannelLiquidity`] in one direction assuming a certain channel capacity. -struct DirectedChannelLiquidity> { +/// A view of [`ChannelLiquidity`] in one direction assuming a certain channel capacity and decayed +/// with a given half life. +struct DirectedChannelLiquidity, T: Time, U: Deref> { min_liquidity_offset_msat: L, max_liquidity_offset_msat: L, capacity_msat: u64, + last_updated: U, + now: T, + half_life: Duration, } -impl> ProbabilisticScorer { +impl, T: Time> ProbabilisticScorerUsingTime { /// Creates a new scorer using the given scoring parameters for sending payments from a node /// through a network graph. pub fn new(params: ProbabilisticScoringParameters, network_graph: G) -> Self { @@ -519,7 +554,7 @@ impl> ProbabilisticScorer { } #[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 } @@ -529,24 +564,26 @@ impl Default for ProbabilisticScoringParameters { fn default() -> Self { Self { liquidity_penalty_multiplier_msat: 10_000, + liquidity_offset_half_life: Duration::from_secs(3600), } } } -impl ChannelLiquidity { +impl ChannelLiquidity { #[inline] fn new() -> Self { Self { min_liquidity_offset_msat: 0, max_liquidity_offset_msat: 0, + last_updated: T::now(), } } /// 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 - ) -> DirectedChannelLiquidity<&u64> { + &self, source: &NodeId, target: &NodeId, capacity_msat: u64, half_life: Duration + ) -> DirectedChannelLiquidity<&u64, T, &T> { let (min_liquidity_offset_msat, max_liquidity_offset_msat) = if source < target { (&self.min_liquidity_offset_msat, &self.max_liquidity_offset_msat) } else { @@ -557,14 +594,17 @@ impl ChannelLiquidity { min_liquidity_offset_msat, max_liquidity_offset_msat, capacity_msat, + last_updated: &self.last_updated, + now: T::now(), + half_life, } } /// 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 - ) -> DirectedChannelLiquidity<&mut u64> { + &mut self, source: &NodeId, target: &NodeId, capacity_msat: u64, half_life: Duration + ) -> DirectedChannelLiquidity<&mut u64, T, &mut T> { let (min_liquidity_offset_msat, max_liquidity_offset_msat) = if source < target { (&mut self.min_liquidity_offset_msat, &mut self.max_liquidity_offset_msat) } else { @@ -575,11 +615,14 @@ impl ChannelLiquidity { min_liquidity_offset_msat, max_liquidity_offset_msat, capacity_msat, + last_updated: &mut self.last_updated, + now: T::now(), + half_life, } } } -impl> DirectedChannelLiquidity { +impl, T: Time, U: Deref> DirectedChannelLiquidity { /// Returns the success probability of routing the given HTLC `amount_msat` through the channel /// in this direction. fn success_probability(&self, amount_msat: u64) -> f64 { @@ -598,16 +641,25 @@ impl> DirectedChannelLiquidity { /// Returns the lower bound of the channel liquidity balance in this direction. fn min_liquidity_msat(&self) -> u64 { - *self.min_liquidity_offset_msat + self.decayed_offset_msat(*self.min_liquidity_offset_msat) } /// Returns the upper bound of the channel liquidity balance in this direction. fn max_liquidity_msat(&self) -> u64 { - self.capacity_msat.checked_sub(*self.max_liquidity_offset_msat).unwrap_or(0) + self.capacity_msat + .checked_sub(self.decayed_offset_msat(*self.max_liquidity_offset_msat)) + .unwrap_or(0) + } + + fn decayed_offset_msat(&self, offset_msat: u64) -> u64 { + self.now.duration_since(*self.last_updated).as_secs() + .checked_div(self.half_life.as_secs()) + .and_then(|decays| offset_msat.checked_shr(decays as u32)) + .unwrap_or(0) } } -impl> DirectedChannelLiquidity { +impl, T: Time, U: DerefMut> DirectedChannelLiquidity { /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat`. fn failed_at_channel(&mut self, amount_msat: u64) { if amount_msat < self.max_liquidity_msat() { @@ -631,32 +683,37 @@ impl> DirectedChannelLiquidity { /// Adjusts the lower bound of the channel liquidity balance in this direction. fn set_min_liquidity_msat(&mut self, amount_msat: u64) { *self.min_liquidity_offset_msat = amount_msat; - - if amount_msat > self.max_liquidity_msat() { - *self.max_liquidity_offset_msat = 0; - } + *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; } /// Adjusts the upper bound of the channel liquidity balance in this direction. fn set_max_liquidity_msat(&mut self, amount_msat: u64) { *self.max_liquidity_offset_msat = self.capacity_msat.checked_sub(amount_msat).unwrap_or(0); - - if amount_msat < self.min_liquidity_msat() { - *self.min_liquidity_offset_msat = 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; } } -impl> Score for ProbabilisticScorer { +impl, T: Time> Score for ProbabilisticScorerUsingTime { fn channel_penalty_msat( &self, short_channel_id: u64, amount_msat: u64, capacity_msat: u64, source: &NodeId, target: &NodeId ) -> u64 { let liquidity_penalty_multiplier_msat = self.params.liquidity_penalty_multiplier_msat; + let liquidity_offset_half_life = self.params.liquidity_offset_half_life; let success_probability = self.channel_liquidities .get(&short_channel_id) .unwrap_or(&ChannelLiquidity::new()) - .as_directed(source, target, capacity_msat) + .as_directed(source, target, capacity_msat, liquidity_offset_half_life) .success_probability(amount_msat); // NOTE: If success_probability is ever changed to return 0.0, log10 is undefined so return // u64::max_value instead. @@ -666,6 +723,7 @@ impl> Score for ProbabilisticScorer { fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) { let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0); + let liquidity_offset_half_life = self.params.liquidity_offset_half_life; let network_graph = self.network_graph.read_only(); for hop in path { let target = NodeId::from_pubkey(&hop.pubkey); @@ -680,7 +738,7 @@ impl> Score for ProbabilisticScorer { self.channel_liquidities .entry(hop.short_channel_id) .or_insert_with(ChannelLiquidity::new) - .as_directed_mut(source, &target, capacity_msat) + .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life) .failed_at_channel(amount_msat); break; } @@ -688,7 +746,7 @@ impl> Score for ProbabilisticScorer { self.channel_liquidities .entry(hop.short_channel_id) .or_insert_with(ChannelLiquidity::new) - .as_directed_mut(source, &target, capacity_msat) + .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life) .failed_downstream(amount_msat); } } @@ -696,6 +754,7 @@ impl> Score for ProbabilisticScorer { fn payment_path_successful(&mut self, path: &[&RouteHop]) { let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0); + let liquidity_offset_half_life = self.params.liquidity_offset_half_life; let network_graph = self.network_graph.read_only(); for hop in path { let target = NodeId::from_pubkey(&hop.pubkey); @@ -709,14 +768,14 @@ impl> Score for ProbabilisticScorer { self.channel_liquidities .entry(hop.short_channel_id) .or_insert_with(ChannelLiquidity::new) - .as_directed_mut(source, &target, capacity_msat) + .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life) .successful(amount_msat); } } } } -impl> Writeable for ProbabilisticScorer { +impl, T: Time> Writeable for ProbabilisticScorerUsingTime { #[inline] fn write(&self, w: &mut W) -> Result<(), io::Error> { write_tlv_fields!(w, { @@ -726,8 +785,11 @@ impl> Writeable for ProbabilisticScorer { } } -impl> ReadableArgs<(ProbabilisticScoringParameters, G)> -for ProbabilisticScorer { +impl ReadableArgs<(ProbabilisticScoringParameters, G)> for ProbabilisticScorerUsingTime +where + G: Deref, + T: Time, +{ #[inline] fn read( r: &mut R, args: (ProbabilisticScoringParameters, G) @@ -745,29 +807,34 @@ for ProbabilisticScorer { } } -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), (2, self.max_liquidity_offset_msat, required), + (4, duration_since_epoch, required), }); Ok(()) } } -impl Readable for ChannelLiquidity { +impl Readable for ChannelLiquidity { #[inline] fn read(r: &mut R) -> Result { let mut min_liquidity_offset_msat = 0; let mut max_liquidity_offset_msat = 0; + let mut duration_since_epoch = Duration::from_secs(0); read_tlv_fields!(r, { (0, min_liquidity_offset_msat, required), (2, max_liquidity_offset_msat, required), + (4, duration_since_epoch, required), }); Ok(Self { min_liquidity_offset_msat, - max_liquidity_offset_msat + max_liquidity_offset_msat, + last_updated: T::now() - (T::duration_since_epoch() - duration_since_epoch), }) } } @@ -776,13 +843,16 @@ pub(crate) mod time { use core::ops::Sub; use core::time::Duration; /// A measurement of time. - pub trait Time: Sub where Self: Sized { + pub trait Time: Copy + Sub where Self: Sized { /// Returns an instance corresponding to the current moment. fn now() -> Self; /// Returns the amount of time elapsed since `self` was created. fn elapsed(&self) -> Duration; + /// Returns the amount of time passed between `earlier` and `self`. + fn duration_since(&self, earlier: Self) -> Duration; + /// Returns the amount of time passed since the beginning of [`Time`]. /// /// Used during (de-)serialization. @@ -790,7 +860,7 @@ pub(crate) mod time { } /// A state in which time has no meaning. - #[derive(Debug, PartialEq, Eq)] + #[derive(Clone, Copy, Debug, PartialEq, Eq)] pub struct Eternity; #[cfg(not(feature = "no-std"))] @@ -799,6 +869,10 @@ pub(crate) mod time { std::time::Instant::now() } + fn duration_since(&self, earlier: Self) -> Duration { + self.duration_since(earlier) + } + fn duration_since_epoch() -> Duration { use std::time::SystemTime; SystemTime::now().duration_since(SystemTime::UNIX_EPOCH).unwrap() @@ -814,6 +888,10 @@ pub(crate) mod time { Self } + fn duration_since(&self, _earlier: Self) -> Duration { + Duration::from_secs(0) + } + fn duration_since_epoch() -> Duration { Duration::from_secs(0) } @@ -836,7 +914,7 @@ pub(crate) use self::time::Time; #[cfg(test)] mod tests { - use super::{ChannelLiquidity, ProbabilisticScoringParameters, ProbabilisticScorer, ScoringParameters, ScorerUsingTime, Time}; + use super::{ChannelLiquidity, ProbabilisticScoringParameters, ProbabilisticScorerUsingTime, ScoringParameters, ScorerUsingTime, Time}; use super::time::Eternity; use ln::features::{ChannelFeatures, NodeFeatures}; @@ -844,7 +922,7 @@ mod tests { use routing::scoring::Score; use routing::network_graph::{NetworkGraph, NodeId}; use routing::router::RouteHop; - use util::ser::{Readable, Writeable}; + use util::ser::{Readable, ReadableArgs, Writeable}; use bitcoin::blockdata::constants::genesis_block; use bitcoin::hashes::Hash; @@ -859,7 +937,7 @@ mod tests { // `Time` tests /// Time that can be advanced manually in tests. - #[derive(Debug, PartialEq, Eq)] + #[derive(Clone, Copy, Debug, PartialEq, Eq)] struct SinceEpoch(Duration); impl SinceEpoch { @@ -877,6 +955,10 @@ mod tests { Self(Self::duration_since_epoch()) } + fn duration_since(&self, earlier: Self) -> Duration { + self.0 - earlier.0 + } + fn duration_since_epoch() -> Duration { Self::ELAPSED.with(|elapsed| elapsed.get()) } @@ -1184,6 +1266,9 @@ mod tests { // `ProbabilisticScorer` tests + /// A probabilistic scorer for testing with time that can be manually advanced. + type ProbabilisticScorer<'a> = ProbabilisticScorerUsingTime::<&'a NetworkGraph, SinceEpoch>; + fn sender_privkey() -> SecretKey { SecretKey::from_slice(&[41; 32]).unwrap() } @@ -1308,154 +1393,188 @@ mod tests { #[test] fn liquidity_bounds_directed_from_lowest_node_id() { + let last_updated = SinceEpoch::now(); let network_graph = network_graph(); let params = ProbabilisticScoringParameters::default(); let mut scorer = ProbabilisticScorer::new(params, &network_graph) .with_channel(42, ChannelLiquidity { - min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100 + min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated }) .with_channel(43, ChannelLiquidity { - min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100 + min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated }); let source = source_node_id(); let target = target_node_id(); let recipient = recipient_node_id(); - - let liquidity = scorer.channel_liquidities.get_mut(&42).unwrap(); assert!(source > target); - assert_eq!(liquidity.as_directed(&source, &target, 1_000).min_liquidity_msat(), 100); - assert_eq!(liquidity.as_directed(&source, &target, 1_000).max_liquidity_msat(), 300); - assert_eq!(liquidity.as_directed(&target, &source, 1_000).min_liquidity_msat(), 700); - assert_eq!(liquidity.as_directed(&target, &source, 1_000).max_liquidity_msat(), 900); - - liquidity.as_directed_mut(&source, &target, 1_000).set_min_liquidity_msat(200); - assert_eq!(liquidity.as_directed(&source, &target, 1_000).min_liquidity_msat(), 200); - assert_eq!(liquidity.as_directed(&source, &target, 1_000).max_liquidity_msat(), 300); - assert_eq!(liquidity.as_directed(&target, &source, 1_000).min_liquidity_msat(), 700); - assert_eq!(liquidity.as_directed(&target, &source, 1_000).max_liquidity_msat(), 800); - - let liquidity = scorer.channel_liquidities.get_mut(&43).unwrap(); assert!(target < recipient); - assert_eq!(liquidity.as_directed(&target, &recipient, 1_000).min_liquidity_msat(), 700); - assert_eq!(liquidity.as_directed(&target, &recipient, 1_000).max_liquidity_msat(), 900); - assert_eq!(liquidity.as_directed(&recipient, &target, 1_000).min_liquidity_msat(), 100); - assert_eq!(liquidity.as_directed(&recipient, &target, 1_000).max_liquidity_msat(), 300); - liquidity.as_directed_mut(&target, &recipient, 1_000).set_max_liquidity_msat(200); - assert_eq!(liquidity.as_directed(&target, &recipient, 1_000).min_liquidity_msat(), 0); - assert_eq!(liquidity.as_directed(&target, &recipient, 1_000).max_liquidity_msat(), 200); - assert_eq!(liquidity.as_directed(&recipient, &target, 1_000).min_liquidity_msat(), 800); - assert_eq!(liquidity.as_directed(&recipient, &target, 1_000).max_liquidity_msat(), 1000); + // Update minimum liquidity. + + let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life; + let liquidity = scorer.channel_liquidities.get(&42).unwrap() + .as_directed(&source, &target, 1_000, liquidity_offset_half_life); + 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, liquidity_offset_half_life); + 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, liquidity_offset_half_life) + .set_min_liquidity_msat(200); + + let liquidity = scorer.channel_liquidities.get(&42).unwrap() + .as_directed(&source, &target, 1_000, liquidity_offset_half_life); + 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, liquidity_offset_half_life); + 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, liquidity_offset_half_life); + 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, liquidity_offset_half_life); + 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, liquidity_offset_half_life) + .set_max_liquidity_msat(200); + + let liquidity = scorer.channel_liquidities.get(&43).unwrap() + .as_directed(&target, &recipient, 1_000, liquidity_offset_half_life); + 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, liquidity_offset_half_life); + assert_eq!(liquidity.min_liquidity_msat(), 800); + assert_eq!(liquidity.max_liquidity_msat(), 1000); } #[test] fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() { + let last_updated = SinceEpoch::now(); let network_graph = network_graph(); let params = ProbabilisticScoringParameters::default(); let mut scorer = ProbabilisticScorer::new(params, &network_graph) .with_channel(42, ChannelLiquidity { - min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400 + min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated }); let source = source_node_id(); let target = target_node_id(); assert!(source > target); // Check initial bounds. + let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life; let liquidity = scorer.channel_liquidities.get(&42).unwrap() - .as_directed(&source, &target, 1_000); + .as_directed(&source, &target, 1_000, liquidity_offset_half_life); 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); + .as_directed(&target, &source, 1_000, liquidity_offset_half_life); 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) + .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life) .set_min_liquidity_msat(900); let liquidity = scorer.channel_liquidities.get(&42).unwrap() - .as_directed(&source, &target, 1_000); + .as_directed(&source, &target, 1_000, liquidity_offset_half_life); 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); + .as_directed(&target, &source, 1_000, liquidity_offset_half_life); 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) + .as_directed_mut(&target, &source, 1_000, liquidity_offset_half_life) .set_min_liquidity_msat(400); let liquidity = scorer.channel_liquidities.get(&42).unwrap() - .as_directed(&source, &target, 1_000); + .as_directed(&source, &target, 1_000, liquidity_offset_half_life); 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); + .as_directed(&target, &source, 1_000, liquidity_offset_half_life); assert_eq!(liquidity.min_liquidity_msat(), 400); assert_eq!(liquidity.max_liquidity_msat(), 1_000); } #[test] fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() { + let last_updated = SinceEpoch::now(); let network_graph = network_graph(); let params = ProbabilisticScoringParameters::default(); let mut scorer = ProbabilisticScorer::new(params, &network_graph) .with_channel(42, ChannelLiquidity { - min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400 + min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated }); let source = source_node_id(); let target = target_node_id(); assert!(source > target); // Check initial bounds. + let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life; let liquidity = scorer.channel_liquidities.get(&42).unwrap() - .as_directed(&source, &target, 1_000); + .as_directed(&source, &target, 1_000, liquidity_offset_half_life); 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); + .as_directed(&target, &source, 1_000, liquidity_offset_half_life); 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) + .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life) .set_max_liquidity_msat(300); let liquidity = scorer.channel_liquidities.get(&42).unwrap() - .as_directed(&source, &target, 1_000); + .as_directed(&source, &target, 1_000, liquidity_offset_half_life); 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); + .as_directed(&target, &source, 1_000, liquidity_offset_half_life); 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) + .as_directed_mut(&target, &source, 1_000, liquidity_offset_half_life) .set_max_liquidity_msat(600); let liquidity = scorer.channel_liquidities.get(&42).unwrap() - .as_directed(&source, &target, 1_000); + .as_directed(&source, &target, 1_000, liquidity_offset_half_life); 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); + .as_directed(&target, &source, 1_000, liquidity_offset_half_life); assert_eq!(liquidity.min_liquidity_msat(), 0); assert_eq!(liquidity.max_liquidity_msat(), 600); } @@ -1486,13 +1605,16 @@ mod tests { #[test] fn constant_penalty_outside_liquidity_bounds() { + let last_updated = SinceEpoch::now(); let network_graph = network_graph(); let params = ProbabilisticScoringParameters { liquidity_penalty_multiplier_msat: 1_000, ..Default::default() }; let scorer = ProbabilisticScorer::new(params, &network_graph) .with_channel(42, - ChannelLiquidity { min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40 }); + ChannelLiquidity { + min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40, last_updated + }); let source = source_node_id(); let target = target_node_id(); @@ -1590,4 +1712,176 @@ mod tests { assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 300); assert_eq!(scorer.channel_penalty_msat(43, 250, 1_000, &target, &recipient), 300); } + + #[test] + fn decays_liquidity_bounds_over_time() { + let network_graph = network_graph(); + let params = ProbabilisticScoringParameters { + liquidity_penalty_multiplier_msat: 1_000, + liquidity_offset_half_life: Duration::from_secs(10), + }; + let mut scorer = ProbabilisticScorer::new(params, &network_graph); + let source = source_node_id(); + let target = target_node_id(); + + assert_eq!(scorer.channel_penalty_msat(42, 0, 1_024, &source, &target), 0); + assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024, &source, &target), 2_000); + + scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::>(), 42); + scorer.payment_path_failed(&payment_path_for_amount(128).iter().collect::>(), 43); + + assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 0); + assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 92); + assert_eq!(scorer.channel_penalty_msat(42, 768, 1_024, &source, &target), 1_424); + assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), 2_000); + + SinceEpoch::advance(Duration::from_secs(9)); + assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 0); + assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 92); + assert_eq!(scorer.channel_penalty_msat(42, 768, 1_024, &source, &target), 1_424); + assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), 2_000); + + SinceEpoch::advance(Duration::from_secs(1)); + assert_eq!(scorer.channel_penalty_msat(42, 64, 1_024, &source, &target), 0); + assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 34); + assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), 1_812); + assert_eq!(scorer.channel_penalty_msat(42, 960, 1_024, &source, &target), 2_000); + + // Fully decay liquidity lower bound. + SinceEpoch::advance(Duration::from_secs(10 * 7)); + assert_eq!(scorer.channel_penalty_msat(42, 0, 1_024, &source, &target), 0); + assert_eq!(scorer.channel_penalty_msat(42, 1, 1_024, &source, &target), 0); + assert_eq!(scorer.channel_penalty_msat(42, 1_023, 1_024, &source, &target), 2_000); + assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024, &source, &target), 2_000); + + // Fully decay liquidity upper bound. + SinceEpoch::advance(Duration::from_secs(10)); + assert_eq!(scorer.channel_penalty_msat(42, 0, 1_024, &source, &target), 0); + assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024, &source, &target), 2_000); + + SinceEpoch::advance(Duration::from_secs(10)); + assert_eq!(scorer.channel_penalty_msat(42, 0, 1_024, &source, &target), 0); + assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024, &source, &target), 2_000); + } + + #[test] + fn decays_liquidity_bounds_without_shift_overflow() { + let network_graph = network_graph(); + let params = ProbabilisticScoringParameters { + liquidity_penalty_multiplier_msat: 1_000, + liquidity_offset_half_life: Duration::from_secs(10), + }; + let mut scorer = ProbabilisticScorer::new(params, &network_graph); + let source = source_node_id(); + let target = target_node_id(); + assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 124); + + scorer.payment_path_failed(&payment_path_for_amount(512).iter().collect::>(), 42); + assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 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, 256, 1_024, &source, &target), 124); + + SinceEpoch::advance(Duration::from_secs(10)); + assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 124); + } + + #[test] + fn restricts_liquidity_bounds_after_decay() { + let network_graph = network_graph(); + let params = ProbabilisticScoringParameters { + liquidity_penalty_multiplier_msat: 1_000, + liquidity_offset_half_life: Duration::from_secs(10), + }; + let mut scorer = ProbabilisticScorer::new(params, &network_graph); + let source = source_node_id(); + let target = target_node_id(); + + assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 300); + + // More knowledge gives higher confidence (256, 768), meaning a lower penalty. + scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::>(), 42); + scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::>(), 43); + assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 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, 512, 1_024, &source, &target), 293); + + // 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).iter().collect::>()); + assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 333); + + // 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).iter().collect::>(), 43); + assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 247); + + // 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, 512, 1_024, &source, &target), 280); + } + + #[test] + fn restores_persisted_liquidity_bounds() { + let network_graph = network_graph(); + let params = ProbabilisticScoringParameters { + liquidity_penalty_multiplier_msat: 1_000, + liquidity_offset_half_life: Duration::from_secs(10), + }; + let mut scorer = ProbabilisticScorer::new(params, &network_graph); + let source = source_node_id(); + let target = target_node_id(); + + scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::>(), 42); + assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 2_000); + + SinceEpoch::advance(Duration::from_secs(10)); + assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 475); + + scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::>(), 43); + assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 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, (params, &network_graph)).unwrap(); + assert_eq!(deserialized_scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300); + } + + #[test] + fn decays_persisted_liquidity_bounds() { + let network_graph = network_graph(); + let params = ProbabilisticScoringParameters { + liquidity_penalty_multiplier_msat: 1_000, + liquidity_offset_half_life: Duration::from_secs(10), + }; + let mut scorer = ProbabilisticScorer::new(params, &network_graph); + let source = source_node_id(); + let target = target_node_id(); + + scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::>(), 42); + assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 2_000); + + 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, (params, &network_graph)).unwrap(); + assert_eq!(deserialized_scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 475); + + scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::>(), 43); + assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300); + + SinceEpoch::advance(Duration::from_secs(10)); + assert_eq!(deserialized_scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 367); + } } -- 2.39.5