Decay channel liquidity balance offsets
authorJeffrey Czyz <jkczyz@gmail.com>
Wed, 5 Jan 2022 00:15:59 +0000 (18:15 -0600)
committerJeffrey Czyz <jkczyz@gmail.com>
Thu, 3 Feb 2022 02:22:27 +0000 (20:22 -0600)
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

index 643425bb214a05347a307144ae965b934fe52780..9f3b7806a991681259deb4ae8655cc060a730382 100644 (file)
@@ -194,21 +194,20 @@ impl<'a, S: Writeable> Writeable for MutexGuard<'a, S> {
 /// 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::<std::time::Instant>;
-/// [`Score`] implementation that provides reasonable default behavior.
+/// See [module-level documentation] for usage and [`ScoringParameters`] for customization.
 ///
-/// 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.
+/// # Note
 ///
-/// See [module-level documentation] for usage and [`ScoringParameters`] for customization.
+/// Mixing the `no-std` feature between serialization and deserialization results in undefined
+/// behavior.
 ///
 /// [module-level documentation]: crate::routing::scoring
+pub type Scorer = ScorerUsingTime::<ConfiguredTime>;
+
+#[cfg(not(feature = "no-std"))]
+type ConfiguredTime = std::time::Instant;
 #[cfg(feature = "no-std")]
-pub type Scorer = ScorerUsingTime::<time::Eternity>;
+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 +215,8 @@ pub type Scorer = ScorerUsingTime::<time::Eternity>;
 
 /// [`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<T: Time> {
        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,30 +456,70 @@ impl<T: Time> Readable for ChannelFailure<T> {
 /// Then the negative `log10` 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.
+///
+/// Since the scorer aims to learn the current channel liquidity balances, it works best for nodes
+/// with high payment volume or that actively probe the [`NetworkGraph`]. Nodes with low payment
+/// volume are more likely to experience failed payment paths, which would need to be retried.
+///
+/// # Note
+///
+/// Mixing the `no-std` feature between serialization and deserialization results in undefined
+/// behavior.
+///
 /// [1]: https://arxiv.org/abs/2107.05322
-pub struct ProbabilisticScorer<G: Deref<Target = NetworkGraph>> {
+pub type ProbabilisticScorer<G> = ProbabilisticScorerUsingTime::<G, ConfiguredTime>;
+
+/// Probabilistic [`Score`] implementation.
+///
+/// (C-not exported) generally all users should use the [`ProbabilisticScorer`] type alias.
+#[doc(hidden)]
+pub struct ProbabilisticScorerUsingTime<G: Deref<Target = NetworkGraph>, T: Time> {
        params: ProbabilisticScoringParameters,
        network_graph: G,
        // TODO: Remove entries of closed channels.
-       channel_liquidities: HashMap<u64, ChannelLiquidity>,
+       channel_liquidities: HashMap<u64, ChannelLiquidity<T>>,
 }
 
 /// Parameters for configuring [`ProbabilisticScorer`].
+#[derive(Clone, Copy)]
 pub struct ProbabilisticScoringParameters {
-       /// A penalty applied after multiplying by the negative `log10` of the channel's success
+       /// A multiplier used to determine the amount in msats willing to be paid to avoid routing
+       /// through a channel, as per multiplying by the negative `log10` of the channel's success
        /// probability for a payment.
        ///
        /// The success probability is determined by the effective channel capacity, the payment amount,
        /// and knowledge learned from prior successful and unsuccessful payments. 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 decayed 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 of 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 +527,29 @@ 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<T: Time> {
        /// 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,
 }
 
-/// A view of [`ChannelLiquidity`] in one direction assuming a certain channel capacity.
-struct DirectedChannelLiquidity<L: Deref<Target = u64>> {
+/// A snapshot of [`ChannelLiquidity`] in one direction assuming a certain channel capacity and
+/// decayed with a given half life.
+struct DirectedChannelLiquidity<L: Deref<Target = u64>, T: Time, U: Deref<Target = T>> {
        min_liquidity_offset_msat: L,
        max_liquidity_offset_msat: L,
        capacity_msat: u64,
+       last_updated: U,
+       now: T,
+       half_life: Duration,
 }
 
-impl<G: Deref<Target = NetworkGraph>> ProbabilisticScorer<G> {
+impl<G: Deref<Target = NetworkGraph>, T: Time> ProbabilisticScorerUsingTime<G, T> {
        /// 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 +561,7 @@ impl<G: Deref<Target = NetworkGraph>> ProbabilisticScorer<G> {
        }
 
        #[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<T>) -> Self {
                assert!(self.channel_liquidities.insert(short_channel_id, liquidity).is_none());
                self
        }
@@ -529,24 +571,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<T: Time> ChannelLiquidity<T> {
        #[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 +601,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 +622,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<L: Deref<Target = u64>> DirectedChannelLiquidity<L> {
+impl<L: Deref<Target = u64>, T: Time, U: Deref<Target = T>> DirectedChannelLiquidity<L, T, U> {
        /// 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 +648,25 @@ impl<L: Deref<Target = u64>> DirectedChannelLiquidity<L> {
 
        /// 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<L: DerefMut<Target = u64>> DirectedChannelLiquidity<L> {
+impl<L: DerefMut<Target = u64>, T: Time, U: DerefMut<Target = T>> DirectedChannelLiquidity<L, T, U> {
        /// 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 +690,37 @@ impl<L: DerefMut<Target = u64>> DirectedChannelLiquidity<L> {
        /// 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<G: Deref<Target = NetworkGraph>> Score for ProbabilisticScorer<G> {
+impl<G: Deref<Target = NetworkGraph>, T: Time> Score for ProbabilisticScorerUsingTime<G, T> {
        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 +730,7 @@ impl<G: Deref<Target = NetworkGraph>> Score for ProbabilisticScorer<G> {
 
        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 +745,7 @@ impl<G: Deref<Target = NetworkGraph>> Score for ProbabilisticScorer<G> {
                                        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 +753,7 @@ impl<G: Deref<Target = NetworkGraph>> Score for ProbabilisticScorer<G> {
                                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 +761,7 @@ impl<G: Deref<Target = NetworkGraph>> Score for ProbabilisticScorer<G> {
 
        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 +775,14 @@ impl<G: Deref<Target = NetworkGraph>> Score for ProbabilisticScorer<G> {
                                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<G: Deref<Target = NetworkGraph>> Writeable for ProbabilisticScorer<G> {
+impl<G: Deref<Target = NetworkGraph>, T: Time> Writeable for ProbabilisticScorerUsingTime<G, T> {
        #[inline]
        fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
                write_tlv_fields!(w, {
@@ -726,8 +792,11 @@ impl<G: Deref<Target = NetworkGraph>> Writeable for ProbabilisticScorer<G> {
        }
 }
 
-impl<G: Deref<Target = NetworkGraph>> ReadableArgs<(ProbabilisticScoringParameters, G)>
-for ProbabilisticScorer<G> {
+impl<G, T> ReadableArgs<(ProbabilisticScoringParameters, G)> for ProbabilisticScorerUsingTime<G, T>
+where
+       G: Deref<Target = NetworkGraph>,
+       T: Time,
+{
        #[inline]
        fn read<R: Read>(
                r: &mut R, args: (ProbabilisticScoringParameters, G)
@@ -745,29 +814,34 @@ for ProbabilisticScorer<G> {
        }
 }
 
-impl Writeable for ChannelLiquidity {
+impl<T: Time> Writeable for ChannelLiquidity<T> {
        #[inline]
        fn write<W: Writer>(&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<T: Time> Readable for ChannelLiquidity<T> {
        #[inline]
        fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
                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 +850,16 @@ pub(crate) mod time {
        use core::ops::Sub;
        use core::time::Duration;
        /// A measurement of time.
-       pub trait Time: Sub<Duration, Output = Self> where Self: Sized {
+       pub trait Time: Copy + Sub<Duration, Output = Self> 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 +867,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 +876,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 +895,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 +921,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 +929,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 +944,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 +962,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 +1273,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 +1400,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 +1612,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 +1719,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::<Vec<_>>(), 42);
+               scorer.payment_path_failed(&payment_path_for_amount(128).iter().collect::<Vec<_>>(), 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::<Vec<_>>(), 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::<Vec<_>>(), 42);
+               scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::<Vec<_>>(), 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::<Vec<_>>());
+               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::<Vec<_>>(), 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::<Vec<_>>(), 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::<Vec<_>>(), 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 =
+                       <ProbabilisticScorer>::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::<Vec<_>>(), 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 =
+                       <ProbabilisticScorer>::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::<Vec<_>>(), 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);
+       }
 }