_ Git - rust-lightning/blob - lightning/src/routing/scoring.rs

   1 // This file is Copyright its original authors, visible in version control
   2 // history.
   3 //
   4 // This file is licensed under the Apache License, Version 2.0 <LICENSE-APACHE
   5 // or http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   6 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your option.
   7 // You may not use this file except in accordance with one or both of these
   8 // licenses.
   9
  10 //! Utilities for scoring payment channels.
  11 //!
  12 //! [`ProbabilisticScorer`] may be given to [`find_route`] to score payment channels during path
  13 //! finding when a custom [`Score`] implementation is not needed.
  14 //!
  15 //! # Example
  16 //!
  17 //! ```
  18 //! # extern crate secp256k1;
  19 //! #
  20 //! # use lightning::routing::network_graph::NetworkGraph;
  21 //! # use lightning::routing::router::{RouteParameters, find_route};
  22 //! # use lightning::routing::scoring::{ProbabilisticScorer, ProbabilisticScoringParameters, Scorer, ScoringParameters};
  23 //! # use lightning::util::logger::{Logger, Record};
  24 //! # use secp256k1::key::PublicKey;
  25 //! #
  26 //! # struct FakeLogger {};
  27 //! # impl Logger for FakeLogger {
  28 //! #     fn log(&self, record: &Record) { unimplemented!() }
  29 //! # }
  30 //! # fn find_scored_route(payer: PublicKey, route_params: RouteParameters, network_graph: NetworkGraph) {
  31 //! # let logger = FakeLogger {};
  32 //! #
  33 //! // Use the default channel penalties.
  34 //! let params = ProbabilisticScoringParameters::default();
  35 //! let scorer = ProbabilisticScorer::new(params, &network_graph);
  36 //!
  37 //! // Or use custom channel penalties.
  38 //! let params = ProbabilisticScoringParameters {
  39 //!     liquidity_penalty_multiplier_msat: 2 * 1000,
  40 //!     ..ProbabilisticScoringParameters::default()
  41 //! };
  42 //! let scorer = ProbabilisticScorer::new(params, &network_graph);
  43 //!
  44 //! let route = find_route(&payer, &route_params, &network_graph, None, &logger, &scorer);
  45 //! # }
  46 //! ```
  47 //!
  48 //! # Note
  49 //!
  50 //! Persisting when built with feature `no-std` and restoring without it, or vice versa, uses
  51 //! different types and thus is undefined.
  52 //!
  53 //! [`find_route`]: crate::routing::router::find_route
  54
  55 use ln::msgs::DecodeError;
  56 use routing::network_graph::{NetworkGraph, NodeId};
  57 use routing::router::RouteHop;
  58 use util::ser::{Readable, ReadableArgs, Writeable, Writer};
  59
  60 use prelude::*;
  61 use core::cell::{RefCell, RefMut};
  62 use core::ops::{Deref, DerefMut};
  63 use core::time::Duration;
  64 use io::{self, Read};
  65 use sync::{Mutex, MutexGuard};
  66
  67 /// We define Score ever-so-slightly differently based on whether we are being built for C bindings
  68 /// or not. For users, `LockableScore` must somehow be writeable to disk. For Rust users, this is
  69 /// no problem - you move a `Score` that implements `Writeable` into a `Mutex`, lock it, and now
  70 /// you have the original, concrete, `Score` type, which presumably implements `Writeable`.
  71 ///
  72 /// For C users, once you've moved the `Score` into a `LockableScore` all you have after locking it
  73 /// is an opaque trait object with an opaque pointer with no type info. Users could take the unsafe
  74 /// approach of blindly casting that opaque pointer to a concrete type and calling `Writeable` from
  75 /// there, but other languages downstream of the C bindings (e.g. Java) can't even do that.
  76 /// Instead, we really want `Score` and `LockableScore` to implement `Writeable` directly, which we
  77 /// do here by defining `Score` differently for `cfg(c_bindings)`.
  78 macro_rules! define_score { ($($supertrait: path)*) => {
  79 /// An interface used to score payment channels for path finding.
  80 ///
  81 ///     Scoring is in terms of fees willing to be paid in order to avoid routing through a channel.
  82 pub trait Score $(: $supertrait)* {
  83         /// Returns the fee in msats willing to be paid to avoid routing `send_amt_msat` through the
  84         /// given channel in the direction from `source` to `target`.
  85         ///
  86         /// The channel's capacity (less any other MPP parts that are also being considered for use in
  87         /// the same payment) is given by `capacity_msat`. It may be determined from various sources
  88         /// such as a chain data, network gossip, or invoice hints. For invoice hints, a capacity near
  89         /// [`u64::max_value`] is given to indicate sufficient capacity for the invoice's full amount.
  90         /// Thus, implementations should be overflow-safe.
  91         fn channel_penalty_msat(&self, short_channel_id: u64, send_amt_msat: u64, capacity_msat: u64, source: &NodeId, target: &NodeId) -> u64;
  92
  93         /// Handles updating channel penalties after failing to route through a channel.
  94         fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64);
  95
  96         /// Handles updating channel penalties after successfully routing along a path.
  97         fn payment_path_successful(&mut self, path: &[&RouteHop]);
  98 }
  99
 100 impl<S: Score, T: DerefMut<Target=S> $(+ $supertrait)*> Score for T {
 101         fn channel_penalty_msat(&self, short_channel_id: u64, send_amt_msat: u64, capacity_msat: u64, source: &NodeId, target: &NodeId) -> u64 {
 102                 self.deref().channel_penalty_msat(short_channel_id, send_amt_msat, capacity_msat, source, target)
 103         }
 104
 105         fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
 106                 self.deref_mut().payment_path_failed(path, short_channel_id)
 107         }
 108
 109         fn payment_path_successful(&mut self, path: &[&RouteHop]) {
 110                 self.deref_mut().payment_path_successful(path)
 111         }
 112 }
 113 } }
 114
 115 #[cfg(c_bindings)]
 116 define_score!(Writeable);
 117 #[cfg(not(c_bindings))]
 118 define_score!();
 119
 120 /// A scorer that is accessed under a lock.
 121 ///
 122 /// Needed so that calls to [`Score::channel_penalty_msat`] in [`find_route`] can be made while
 123 /// having shared ownership of a scorer but without requiring internal locking in [`Score`]
 124 /// implementations. Internal locking would be detrimental to route finding performance and could
 125 /// result in [`Score::channel_penalty_msat`] returning a different value for the same channel.
 126 ///
 127 /// [`find_route`]: crate::routing::router::find_route
 128 pub trait LockableScore<'a> {
 129         /// The locked [`Score`] type.
 130         type Locked: 'a + Score;
 131
 132         /// Returns the locked scorer.
 133         fn lock(&'a self) -> Self::Locked;
 134 }
 135
 136 /// (C-not exported)
 137 impl<'a, T: 'a + Score> LockableScore<'a> for Mutex<T> {
 138         type Locked = MutexGuard<'a, T>;
 139
 140         fn lock(&'a self) -> MutexGuard<'a, T> {
 141                 Mutex::lock(self).unwrap()
 142         }
 143 }
 144
 145 impl<'a, T: 'a + Score> LockableScore<'a> for RefCell<T> {
 146         type Locked = RefMut<'a, T>;
 147
 148         fn lock(&'a self) -> RefMut<'a, T> {
 149                 self.borrow_mut()
 150         }
 151 }
 152
 153 #[cfg(c_bindings)]
 154 /// A concrete implementation of [`LockableScore`] which supports multi-threading.
 155 pub struct MultiThreadedLockableScore<S: Score> {
 156         score: Mutex<S>,
 157 }
 158 #[cfg(c_bindings)]
 159 /// (C-not exported)
 160 impl<'a, T: Score + 'a> LockableScore<'a> for MultiThreadedLockableScore<T> {
 161         type Locked = MutexGuard<'a, T>;
 162
 163         fn lock(&'a self) -> MutexGuard<'a, T> {
 164                 Mutex::lock(&self.score).unwrap()
 165         }
 166 }
 167
 168 #[cfg(c_bindings)]
 169 impl<T: Score> MultiThreadedLockableScore<T> {
 170         /// Creates a new [`MultiThreadedLockableScore`] given an underlying [`Score`].
 171         pub fn new(score: T) -> Self {
 172                 MultiThreadedLockableScore { score: Mutex::new(score) }
 173         }
 174 }
 175
 176 #[cfg(c_bindings)]
 177 /// (C-not exported)
 178 impl<'a, T: Writeable> Writeable for RefMut<'a, T> {
 179         fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
 180                 T::write(&**self, writer)
 181         }
 182 }
 183
 184 #[cfg(c_bindings)]
 185 /// (C-not exported)
 186 impl<'a, S: Writeable> Writeable for MutexGuard<'a, S> {
 187         fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
 188                 S::write(&**self, writer)
 189         }
 190 }
 191
 192 /// [`Score`] implementation that uses a fixed penalty.
 193 pub struct FixedPenaltyScorer {
 194         penalty_msat: u64,
 195 }
 196
 197 impl_writeable_tlv_based!(FixedPenaltyScorer, {
 198         (0, penalty_msat, required),
 199 });
 200
 201 impl FixedPenaltyScorer {
 202         /// Creates a new scorer using `penalty_msat`.
 203         pub fn with_penalty(penalty_msat: u64) -> Self {
 204                 Self { penalty_msat }
 205         }
 206 }
 207
 208 impl Score for FixedPenaltyScorer {
 209         fn channel_penalty_msat(&self, _: u64, _: u64, _: u64, _: &NodeId, _: &NodeId) -> u64 {
 210                 self.penalty_msat
 211         }
 212
 213         fn payment_path_failed(&mut self, _path: &[&RouteHop], _short_channel_id: u64) {}
 214
 215         fn payment_path_successful(&mut self, _path: &[&RouteHop]) {}
 216 }
 217
 218 /// [`Score`] implementation that provides reasonable default behavior.
 219 ///
 220 /// Used to apply a fixed penalty to each channel, thus avoiding long paths when shorter paths with
 221 /// slightly higher fees are available. Will further penalize channels that fail to relay payments.
 222 ///
 223 /// See [module-level documentation] for usage and [`ScoringParameters`] for customization.
 224 ///
 225 /// # Note
 226 ///
 227 /// Mixing the `no-std` feature between serialization and deserialization results in undefined
 228 /// behavior.
 229 ///
 230 /// [module-level documentation]: crate::routing::scoring
 231 #[deprecated(
 232         since = "0.0.105",
 233         note = "ProbabilisticScorer should be used instead of Scorer.",
 234 )]
 235 #[cfg(not(feature = "no-std"))]
 236 pub type Scorer = ScorerUsingTime::<std::time::Instant>;
 237 #[cfg(feature = "no-std")]
 238 pub type Scorer = ScorerUsingTime::<time::Eternity>;
 239
 240 // Note that ideally we'd hide ScorerUsingTime from public view by sealing it as well, but rustdoc
 241 // doesn't handle this well - instead exposing a `Scorer` which has no trait implementation(s) or
 242 // methods at all.
 243
 244 /// [`Score`] implementation.
 245 ///
 246 /// (C-not exported) generally all users should use the [`Scorer`] type alias.
 247 pub struct ScorerUsingTime<T: Time> {
 248         params: ScoringParameters,
 249         // TODO: Remove entries of closed channels.
 250         channel_failures: HashMap<u64, ChannelFailure<T>>,
 251 }
 252
 253 /// Parameters for configuring [`Scorer`].
 254 pub struct ScoringParameters {
 255         /// A fixed penalty in msats to apply to each channel.
 256         ///
 257         /// Default value: 500 msat
 258         pub base_penalty_msat: u64,
 259
 260         /// A penalty in msats to apply to a channel upon failing to relay a payment.
 261         ///
 262         /// This accumulates for each failure but may be reduced over time based on
 263         /// [`failure_penalty_half_life`] or when successfully routing through a channel.
 264         ///
 265         /// Default value: 1,024,000 msat
 266         ///
 267         /// [`failure_penalty_half_life`]: Self::failure_penalty_half_life
 268         pub failure_penalty_msat: u64,
 269
 270         /// When the amount being sent over a channel is this many 1024ths of the total channel
 271         /// capacity, we begin applying [`overuse_penalty_msat_per_1024th`].
 272         ///
 273         /// Default value: 128 1024ths (i.e. begin penalizing when an HTLC uses 1/8th of a channel)
 274         ///
 275         /// [`overuse_penalty_msat_per_1024th`]: Self::overuse_penalty_msat_per_1024th
 276         pub overuse_penalty_start_1024th: u16,
 277
 278         /// A penalty applied, per whole 1024ths of the channel capacity which the amount being sent
 279         /// over the channel exceeds [`overuse_penalty_start_1024th`] by.
 280         ///
 281         /// Default value: 20 msat (i.e. 2560 msat penalty to use 1/4th of a channel, 7680 msat penalty
 282         ///                to use half a channel, and 12,560 msat penalty to use 3/4ths of a channel)
 283         ///
 284         /// [`overuse_penalty_start_1024th`]: Self::overuse_penalty_start_1024th
 285         pub overuse_penalty_msat_per_1024th: u64,
 286
 287         /// The time required to elapse before any accumulated [`failure_penalty_msat`] penalties are
 288         /// cut in half.
 289         ///
 290         /// Successfully routing through a channel will immediately cut the penalty in half as well.
 291         ///
 292         /// Default value: 1 hour
 293         ///
 294         /// # Note
 295         ///
 296         /// When built with the `no-std` feature, time will never elapse. Therefore, this penalty will
 297         /// never decay.
 298         ///
 299         /// [`failure_penalty_msat`]: Self::failure_penalty_msat
 300         pub failure_penalty_half_life: Duration,
 301 }
 302
 303 impl_writeable_tlv_based!(ScoringParameters, {
 304         (0, base_penalty_msat, required),
 305         (1, overuse_penalty_start_1024th, (default_value, 128)),
 306         (2, failure_penalty_msat, required),
 307         (3, overuse_penalty_msat_per_1024th, (default_value, 20)),
 308         (4, failure_penalty_half_life, required),
 309 });
 310
 311 /// Accounting for penalties against a channel for failing to relay any payments.
 312 ///
 313 /// Penalties decay over time, though accumulate as more failures occur.
 314 struct ChannelFailure<T: Time> {
 315         /// Accumulated penalty in msats for the channel as of `last_updated`.
 316         undecayed_penalty_msat: u64,
 317
 318         /// Last time the channel either failed to route or successfully routed a payment. Used to decay
 319         /// `undecayed_penalty_msat`.
 320         last_updated: T,
 321 }
 322
 323 impl<T: Time> ScorerUsingTime<T> {
 324         /// Creates a new scorer using the given scoring parameters.
 325         pub fn new(params: ScoringParameters) -> Self {
 326                 Self {
 327                         params,
 328                         channel_failures: HashMap::new(),
 329                 }
 330         }
 331 }
 332
 333 impl<T: Time> ChannelFailure<T> {
 334         fn new(failure_penalty_msat: u64) -> Self {
 335                 Self {
 336                         undecayed_penalty_msat: failure_penalty_msat,
 337                         last_updated: T::now(),
 338                 }
 339         }
 340
 341         fn add_penalty(&mut self, failure_penalty_msat: u64, half_life: Duration) {
 342                 self.undecayed_penalty_msat = self.decayed_penalty_msat(half_life) + failure_penalty_msat;
 343                 self.last_updated = T::now();
 344         }
 345
 346         fn reduce_penalty(&mut self, half_life: Duration) {
 347                 self.undecayed_penalty_msat = self.decayed_penalty_msat(half_life) >> 1;
 348                 self.last_updated = T::now();
 349         }
 350
 351         fn decayed_penalty_msat(&self, half_life: Duration) -> u64 {
 352                 self.last_updated.elapsed().as_secs()
 353                         .checked_div(half_life.as_secs())
 354                         .and_then(|decays| self.undecayed_penalty_msat.checked_shr(decays as u32))
 355                         .unwrap_or(0)
 356         }
 357 }
 358
 359 impl<T: Time> Default for ScorerUsingTime<T> {
 360         fn default() -> Self {
 361                 Self::new(ScoringParameters::default())
 362         }
 363 }
 364
 365 impl Default for ScoringParameters {
 366         fn default() -> Self {
 367                 Self {
 368                         base_penalty_msat: 500,
 369                         failure_penalty_msat: 1024 * 1000,
 370                         failure_penalty_half_life: Duration::from_secs(3600),
 371                         overuse_penalty_start_1024th: 1024 / 8,
 372                         overuse_penalty_msat_per_1024th: 20,
 373                 }
 374         }
 375 }
 376
 377 impl<T: Time> Score for ScorerUsingTime<T> {
 378         fn channel_penalty_msat(
 379                 &self, short_channel_id: u64, send_amt_msat: u64, capacity_msat: u64, _source: &NodeId, _target: &NodeId
 380         ) -> u64 {
 381                 let failure_penalty_msat = self.channel_failures
 382                         .get(&short_channel_id)
 383                         .map_or(0, |value| value.decayed_penalty_msat(self.params.failure_penalty_half_life));
 384
 385                 let mut penalty_msat = self.params.base_penalty_msat + failure_penalty_msat;
 386                 let send_1024ths = send_amt_msat.checked_mul(1024).unwrap_or(u64::max_value()) / capacity_msat;
 387                 if send_1024ths > self.params.overuse_penalty_start_1024th as u64 {
 388                         penalty_msat = penalty_msat.checked_add(
 389                                         (send_1024ths - self.params.overuse_penalty_start_1024th as u64)
 390                                         .checked_mul(self.params.overuse_penalty_msat_per_1024th).unwrap_or(u64::max_value()))
 391                                 .unwrap_or(u64::max_value());
 392                 }
 393
 394                 penalty_msat
 395         }
 396
 397         fn payment_path_failed(&mut self, _path: &[&RouteHop], short_channel_id: u64) {
 398                 let failure_penalty_msat = self.params.failure_penalty_msat;
 399                 let half_life = self.params.failure_penalty_half_life;
 400                 self.channel_failures
 401                         .entry(short_channel_id)
 402                         .and_modify(|failure| failure.add_penalty(failure_penalty_msat, half_life))
 403                         .or_insert_with(|| ChannelFailure::new(failure_penalty_msat));
 404         }
 405
 406         fn payment_path_successful(&mut self, path: &[&RouteHop]) {
 407                 let half_life = self.params.failure_penalty_half_life;
 408                 for hop in path.iter() {
 409                         self.channel_failures
 410                                 .entry(hop.short_channel_id)
 411                                 .and_modify(|failure| failure.reduce_penalty(half_life));
 412                 }
 413         }
 414 }
 415
 416 impl<T: Time> Writeable for ScorerUsingTime<T> {
 417         #[inline]
 418         fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
 419                 self.params.write(w)?;
 420                 self.channel_failures.write(w)?;
 421                 write_tlv_fields!(w, {});
 422                 Ok(())
 423         }
 424 }
 425
 426 impl<T: Time> Readable for ScorerUsingTime<T> {
 427         #[inline]
 428         fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
 429                 let res = Ok(Self {
 430                         params: Readable::read(r)?,
 431                         channel_failures: Readable::read(r)?,
 432                 });
 433                 read_tlv_fields!(r, {});
 434                 res
 435         }
 436 }
 437
 438 impl<T: Time> Writeable for ChannelFailure<T> {
 439         #[inline]
 440         fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
 441                 let duration_since_epoch = T::duration_since_epoch() - self.last_updated.elapsed();
 442                 write_tlv_fields!(w, {
 443                         (0, self.undecayed_penalty_msat, required),
 444                         (2, duration_since_epoch, required),
 445                 });
 446                 Ok(())
 447         }
 448 }
 449
 450 impl<T: Time> Readable for ChannelFailure<T> {
 451         #[inline]
 452         fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
 453                 let mut undecayed_penalty_msat = 0;
 454                 let mut duration_since_epoch = Duration::from_secs(0);
 455                 read_tlv_fields!(r, {
 456                         (0, undecayed_penalty_msat, required),
 457                         (2, duration_since_epoch, required),
 458                 });
 459                 Ok(Self {
 460                         undecayed_penalty_msat,
 461                         last_updated: T::now() - (T::duration_since_epoch() - duration_since_epoch),
 462                 })
 463         }
 464 }
 465
 466 /// [`Score`] implementation using channel success probability distributions.
 467 ///
 468 /// Based on *Optimally Reliable & Cheap Payment Flows on the Lightning Network* by Rene Pickhardt
 469 /// and Stefan Richter [[1]]. Given the uncertainty of channel liquidity balances, probability
 470 /// distributions are defined based on knowledge learned from successful and unsuccessful attempts.
 471 /// Then the negative `log10` of the success probability is used to determine the cost of routing a
 472 /// specific HTLC amount through a channel.
 473 ///
 474 /// Knowledge about channel liquidity balances takes the form of upper and lower bounds on the
 475 /// possible liquidity. Certainty of the bounds is decreased over time using a decay function. See
 476 /// [`ProbabilisticScoringParameters`] for details.
 477 ///
 478 /// Since the scorer aims to learn the current channel liquidity balances, it works best for nodes
 479 /// with high payment volume or that actively probe the [`NetworkGraph`]. Nodes with low payment
 480 /// volume are more likely to experience failed payment paths, which would need to be retried.
 481 ///
 482 /// # Note
 483 ///
 484 /// Mixing the `no-std` feature between serialization and deserialization results in undefined
 485 /// behavior.
 486 ///
 487 /// [1]: https://arxiv.org/abs/2107.05322
 488 #[cfg(not(feature = "no-std"))]
 489 pub type ProbabilisticScorer<G> = ProbabilisticScorerUsingTime::<G, std::time::Instant>;
 490 #[cfg(feature = "no-std")]
 491 pub type ProbabilisticScorer<G> = ProbabilisticScorerUsingTime::<G, time::Eternity>;
 492
 493 /// Probabilistic [`Score`] implementation.
 494 ///
 495 /// (C-not exported) generally all users should use the [`ProbabilisticScorer`] type alias.
 496 pub struct ProbabilisticScorerUsingTime<G: Deref<Target = NetworkGraph>, T: Time> {
 497         params: ProbabilisticScoringParameters,
 498         network_graph: G,
 499         // TODO: Remove entries of closed channels.
 500         channel_liquidities: HashMap<u64, ChannelLiquidity<T>>,
 501 }
 502
 503 /// Parameters for configuring [`ProbabilisticScorer`].
 504 #[derive(Clone, Copy)]
 505 pub struct ProbabilisticScoringParameters {
 506         /// A multiplier used to determine the amount in msats willing to be paid to avoid routing
 507         /// through a channel, as per multiplying by the negative `log10` of the channel's success
 508         /// probability for a payment.
 509         ///
 510         /// The success probability is determined by the effective channel capacity, the payment amount,
 511         /// and knowledge learned from prior successful and unsuccessful payments. The lower bound of
 512         /// the success probability is 0.01, effectively limiting the penalty to the range
 513         /// `0..=2*liquidity_penalty_multiplier_msat`. The knowledge learned is decayed over time based
 514         /// on [`liquidity_offset_half_life`].
 515         ///
 516         /// Default value: 10,000 msat
 517         ///
 518         /// [`liquidity_offset_half_life`]: Self::liquidity_offset_half_life
 519         pub liquidity_penalty_multiplier_msat: u64,
 520
 521         /// The time required to elapse before any knowledge learned about channel liquidity balances is
 522         /// cut in half.
 523         ///
 524         /// The bounds are defined in terms of offsets and are initially zero. Increasing the offsets
 525         /// gives tighter bounds on the channel liquidity balance. Thus, halving the offsets decreases
 526         /// the certainty of the channel liquidity balance.
 527         ///
 528         /// Default value: 1 hour
 529         ///
 530         /// # Note
 531         ///
 532         /// When built with the `no-std` feature, time will never elapse. Therefore, the channel
 533         /// liquidity knowledge will never decay except when the bounds cross.
 534         pub liquidity_offset_half_life: Duration,
 535 }
 536
 537 impl_writeable_tlv_based!(ProbabilisticScoringParameters, {
 538         (0, liquidity_penalty_multiplier_msat, required),
 539         (2, liquidity_offset_half_life, required),
 540 });
 541
 542 /// Accounting for channel liquidity balance uncertainty.
 543 ///
 544 /// Direction is defined in terms of [`NodeId`] partial ordering, where the source node is the
 545 /// first node in the ordering of the channel's counterparties. Thus, swapping the two liquidity
 546 /// offset fields gives the opposite direction.
 547 struct ChannelLiquidity<T: Time> {
 548         /// Lower channel liquidity bound in terms of an offset from zero.
 549         min_liquidity_offset_msat: u64,
 550
 551         /// Upper channel liquidity bound in terms of an offset from the effective capacity.
 552         max_liquidity_offset_msat: u64,
 553
 554         /// Time when the liquidity bounds were last modified.
 555         last_updated: T,
 556 }
 557
 558 /// A snapshot of [`ChannelLiquidity`] in one direction assuming a certain channel capacity and
 559 /// decayed with a given half life.
 560 struct DirectedChannelLiquidity<L: Deref<Target = u64>, T: Time, U: Deref<Target = T>> {
 561         min_liquidity_offset_msat: L,
 562         max_liquidity_offset_msat: L,
 563         capacity_msat: u64,
 564         last_updated: U,
 565         now: T,
 566         half_life: Duration,
 567 }
 568
 569 impl<G: Deref<Target = NetworkGraph>, T: Time> ProbabilisticScorerUsingTime<G, T> {
 570         /// Creates a new scorer using the given scoring parameters for sending payments from a node
 571         /// through a network graph.
 572         pub fn new(params: ProbabilisticScoringParameters, network_graph: G) -> Self {
 573                 Self {
 574                         params,
 575                         network_graph,
 576                         channel_liquidities: HashMap::new(),
 577                 }
 578         }
 579
 580         #[cfg(test)]
 581         fn with_channel(mut self, short_channel_id: u64, liquidity: ChannelLiquidity<T>) -> Self {
 582                 assert!(self.channel_liquidities.insert(short_channel_id, liquidity).is_none());
 583                 self
 584         }
 585 }
 586
 587 impl Default for ProbabilisticScoringParameters {
 588         fn default() -> Self {
 589                 Self {
 590                         liquidity_penalty_multiplier_msat: 10_000,
 591                         liquidity_offset_half_life: Duration::from_secs(3600),
 592                 }
 593         }
 594 }
 595
 596 impl<T: Time> ChannelLiquidity<T> {
 597         #[inline]
 598         fn new() -> Self {
 599                 Self {
 600                         min_liquidity_offset_msat: 0,
 601                         max_liquidity_offset_msat: 0,
 602                         last_updated: T::now(),
 603                 }
 604         }
 605
 606         /// Returns a view of the channel liquidity directed from `source` to `target` assuming
 607         /// `capacity_msat`.
 608         fn as_directed(
 609                 &self, source: &NodeId, target: &NodeId, capacity_msat: u64, half_life: Duration
 610         ) -> DirectedChannelLiquidity<&u64, T, &T> {
 611                 let (min_liquidity_offset_msat, max_liquidity_offset_msat) = if source < target {
 612                         (&self.min_liquidity_offset_msat, &self.max_liquidity_offset_msat)
 613                 } else {
 614                         (&self.max_liquidity_offset_msat, &self.min_liquidity_offset_msat)
 615                 };
 616
 617                 DirectedChannelLiquidity {
 618                         min_liquidity_offset_msat,
 619                         max_liquidity_offset_msat,
 620                         capacity_msat,
 621                         last_updated: &self.last_updated,
 622                         now: T::now(),
 623                         half_life,
 624                 }
 625         }
 626
 627         /// Returns a mutable view of the channel liquidity directed from `source` to `target` assuming
 628         /// `capacity_msat`.
 629         fn as_directed_mut(
 630                 &mut self, source: &NodeId, target: &NodeId, capacity_msat: u64, half_life: Duration
 631         ) -> DirectedChannelLiquidity<&mut u64, T, &mut T> {
 632                 let (min_liquidity_offset_msat, max_liquidity_offset_msat) = if source < target {
 633                         (&mut self.min_liquidity_offset_msat, &mut self.max_liquidity_offset_msat)
 634                 } else {
 635                         (&mut self.max_liquidity_offset_msat, &mut self.min_liquidity_offset_msat)
 636                 };
 637
 638                 DirectedChannelLiquidity {
 639                         min_liquidity_offset_msat,
 640                         max_liquidity_offset_msat,
 641                         capacity_msat,
 642                         last_updated: &mut self.last_updated,
 643                         now: T::now(),
 644                         half_life,
 645                 }
 646         }
 647 }
 648
 649 impl<L: Deref<Target = u64>, T: Time, U: Deref<Target = T>> DirectedChannelLiquidity<L, T, U> {
 650         /// Returns the success probability of routing the given HTLC `amount_msat` through the channel
 651         /// in this direction.
 652         fn success_probability(&self, amount_msat: u64) -> f64 {
 653                 let max_liquidity_msat = self.max_liquidity_msat();
 654                 let min_liquidity_msat = core::cmp::min(self.min_liquidity_msat(), max_liquidity_msat);
 655                 if amount_msat > max_liquidity_msat {
 656                         0.0
 657                 } else if amount_msat <= min_liquidity_msat {
 658                         1.0
 659                 } else {
 660                         let numerator = max_liquidity_msat + 1 - amount_msat;
 661                         let denominator = max_liquidity_msat + 1 - min_liquidity_msat;
 662                         numerator as f64 / denominator as f64
 663                 }.max(0.01) // Lower bound the success probability to ensure some channel is selected.
 664         }
 665
 666         /// Returns the lower bound of the channel liquidity balance in this direction.
 667         fn min_liquidity_msat(&self) -> u64 {
 668                 self.decayed_offset_msat(*self.min_liquidity_offset_msat)
 669         }
 670
 671         /// Returns the upper bound of the channel liquidity balance in this direction.
 672         fn max_liquidity_msat(&self) -> u64 {
 673                 self.capacity_msat
 674                         .checked_sub(self.decayed_offset_msat(*self.max_liquidity_offset_msat))
 675                         .unwrap_or(0)
 676         }
 677
 678         fn decayed_offset_msat(&self, offset_msat: u64) -> u64 {
 679                 self.now.duration_since(*self.last_updated).as_secs()
 680                         .checked_div(self.half_life.as_secs())
 681                         .and_then(|decays| offset_msat.checked_shr(decays as u32))
 682                         .unwrap_or(0)
 683         }
 684 }
 685
 686 impl<L: DerefMut<Target = u64>, T: Time, U: DerefMut<Target = T>> DirectedChannelLiquidity<L, T, U> {
 687         /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat`.
 688         fn failed_at_channel(&mut self, amount_msat: u64) {
 689                 if amount_msat < self.max_liquidity_msat() {
 690                         self.set_max_liquidity_msat(amount_msat);
 691                 }
 692         }
 693
 694         /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat` downstream.
 695         fn failed_downstream(&mut self, amount_msat: u64) {
 696                 if amount_msat > self.min_liquidity_msat() {
 697                         self.set_min_liquidity_msat(amount_msat);
 698                 }
 699         }
 700
 701         /// Adjusts the channel liquidity balance bounds when successfully routing `amount_msat`.
 702         fn successful(&mut self, amount_msat: u64) {
 703                 let max_liquidity_msat = self.max_liquidity_msat().checked_sub(amount_msat).unwrap_or(0);
 704                 self.set_max_liquidity_msat(max_liquidity_msat);
 705         }
 706
 707         /// Adjusts the lower bound of the channel liquidity balance in this direction.
 708         fn set_min_liquidity_msat(&mut self, amount_msat: u64) {
 709                 *self.min_liquidity_offset_msat = amount_msat;
 710                 *self.max_liquidity_offset_msat = if amount_msat > self.max_liquidity_msat() {
 711                         0
 712                 } else {
 713                         self.decayed_offset_msat(*self.max_liquidity_offset_msat)
 714                 };
 715                 *self.last_updated = self.now;
 716         }
 717
 718         /// Adjusts the upper bound of the channel liquidity balance in this direction.
 719         fn set_max_liquidity_msat(&mut self, amount_msat: u64) {
 720                 *self.max_liquidity_offset_msat = self.capacity_msat.checked_sub(amount_msat).unwrap_or(0);
 721                 *self.min_liquidity_offset_msat = if amount_msat < self.min_liquidity_msat() {
 722                         0
 723                 } else {
 724                         self.decayed_offset_msat(*self.min_liquidity_offset_msat)
 725                 };
 726                 *self.last_updated = self.now;
 727         }
 728 }
 729
 730 impl<G: Deref<Target = NetworkGraph>, T: Time> Score for ProbabilisticScorerUsingTime<G, T> {
 731         fn channel_penalty_msat(
 732                 &self, short_channel_id: u64, amount_msat: u64, capacity_msat: u64, source: &NodeId,
 733                 target: &NodeId
 734         ) -> u64 {
 735                 let liquidity_penalty_multiplier_msat = self.params.liquidity_penalty_multiplier_msat;
 736                 let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
 737                 let success_probability = self.channel_liquidities
 738                         .get(&short_channel_id)
 739                         .unwrap_or(&ChannelLiquidity::new())
 740                         .as_directed(source, target, capacity_msat, liquidity_offset_half_life)
 741                         .success_probability(amount_msat);
 742                 // NOTE: If success_probability is ever changed to return 0.0, log10 is undefined so return
 743                 // u64::max_value instead.
 744                 debug_assert!(success_probability > core::f64::EPSILON);
 745                 (-(success_probability.log10()) * liquidity_penalty_multiplier_msat as f64) as u64
 746         }
 747
 748         fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
 749                 let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
 750                 let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
 751                 let network_graph = self.network_graph.read_only();
 752                 for hop in path {
 753                         let target = NodeId::from_pubkey(&hop.pubkey);
 754                         let channel_directed_from_source = network_graph.channels()
 755                                 .get(&hop.short_channel_id)
 756                                 .and_then(|channel| channel.as_directed_to(&target));
 757
 758                         // Only score announced channels.
 759                         if let Some((channel, source)) = channel_directed_from_source {
 760                                 let capacity_msat = channel.effective_capacity().as_msat();
 761                                 if hop.short_channel_id == short_channel_id {
 762                                         self.channel_liquidities
 763                                                 .entry(hop.short_channel_id)
 764                                                 .or_insert_with(ChannelLiquidity::new)
 765                                                 .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life)
 766                                                 .failed_at_channel(amount_msat);
 767                                         break;
 768                                 }
 769
 770                                 self.channel_liquidities
 771                                         .entry(hop.short_channel_id)
 772                                         .or_insert_with(ChannelLiquidity::new)
 773                                         .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life)
 774                                         .failed_downstream(amount_msat);
 775                         }
 776                 }
 777         }
 778
 779         fn payment_path_successful(&mut self, path: &[&RouteHop]) {
 780                 let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
 781                 let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
 782                 let network_graph = self.network_graph.read_only();
 783                 for hop in path {
 784                         let target = NodeId::from_pubkey(&hop.pubkey);
 785                         let channel_directed_from_source = network_graph.channels()
 786                                 .get(&hop.short_channel_id)
 787                                 .and_then(|channel| channel.as_directed_to(&target));
 788
 789                         // Only score announced channels.
 790                         if let Some((channel, source)) = channel_directed_from_source {
 791                                 let capacity_msat = channel.effective_capacity().as_msat();
 792                                 self.channel_liquidities
 793                                         .entry(hop.short_channel_id)
 794                                         .or_insert_with(ChannelLiquidity::new)
 795                                         .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life)
 796                                         .successful(amount_msat);
 797                         }
 798                 }
 799         }
 800 }
 801
 802 impl<G: Deref<Target = NetworkGraph>, T: Time> Writeable for ProbabilisticScorerUsingTime<G, T> {
 803         #[inline]
 804         fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
 805                 write_tlv_fields!(w, {
 806                         (0, self.channel_liquidities, required)
 807                 });
 808                 Ok(())
 809         }
 810 }
 811
 812 impl<G, T> ReadableArgs<(ProbabilisticScoringParameters, G)> for ProbabilisticScorerUsingTime<G, T>
 813 where
 814         G: Deref<Target = NetworkGraph>,
 815         T: Time,
 816 {
 817         #[inline]
 818         fn read<R: Read>(
 819                 r: &mut R, args: (ProbabilisticScoringParameters, G)
 820         ) -> Result<Self, DecodeError> {
 821                 let (params, network_graph) = args;
 822                 let mut channel_liquidities = HashMap::new();
 823                 read_tlv_fields!(r, {
 824                         (0, channel_liquidities, required)
 825                 });
 826                 Ok(Self {
 827                         params,
 828                         network_graph,
 829                         channel_liquidities,
 830                 })
 831         }
 832 }
 833
 834 impl<T: Time> Writeable for ChannelLiquidity<T> {
 835         #[inline]
 836         fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
 837                 let duration_since_epoch = T::duration_since_epoch() - self.last_updated.elapsed();
 838                 write_tlv_fields!(w, {
 839                         (0, self.min_liquidity_offset_msat, required),
 840                         (2, self.max_liquidity_offset_msat, required),
 841                         (4, duration_since_epoch, required),
 842                 });
 843                 Ok(())
 844         }
 845 }
 846
 847 impl<T: Time> Readable for ChannelLiquidity<T> {
 848         #[inline]
 849         fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
 850                 let mut min_liquidity_offset_msat = 0;
 851                 let mut max_liquidity_offset_msat = 0;
 852                 let mut duration_since_epoch = Duration::from_secs(0);
 853                 read_tlv_fields!(r, {
 854                         (0, min_liquidity_offset_msat, required),
 855                         (2, max_liquidity_offset_msat, required),
 856                         (4, duration_since_epoch, required),
 857                 });
 858                 Ok(Self {
 859                         min_liquidity_offset_msat,
 860                         max_liquidity_offset_msat,
 861                         last_updated: T::now() - (T::duration_since_epoch() - duration_since_epoch),
 862                 })
 863         }
 864 }
 865
 866 pub(crate) mod time {
 867         use core::ops::Sub;
 868         use core::time::Duration;
 869         /// A measurement of time.
 870         pub trait Time: Copy + Sub<Duration, Output = Self> where Self: Sized {
 871                 /// Returns an instance corresponding to the current moment.
 872                 fn now() -> Self;
 873
 874                 /// Returns the amount of time elapsed since `self` was created.
 875                 fn elapsed(&self) -> Duration;
 876
 877                 /// Returns the amount of time passed between `earlier` and `self`.
 878                 fn duration_since(&self, earlier: Self) -> Duration;
 879
 880                 /// Returns the amount of time passed since the beginning of [`Time`].
 881                 ///
 882                 /// Used during (de-)serialization.
 883                 fn duration_since_epoch() -> Duration;
 884         }
 885
 886         /// A state in which time has no meaning.
 887         #[derive(Clone, Copy, Debug, PartialEq, Eq)]
 888         pub struct Eternity;
 889
 890         #[cfg(not(feature = "no-std"))]
 891         impl Time for std::time::Instant {
 892                 fn now() -> Self {
 893                         std::time::Instant::now()
 894                 }
 895
 896                 fn duration_since(&self, earlier: Self) -> Duration {
 897                         self.duration_since(earlier)
 898                 }
 899
 900                 fn duration_since_epoch() -> Duration {
 901                         use std::time::SystemTime;
 902                         SystemTime::now().duration_since(SystemTime::UNIX_EPOCH).unwrap()
 903                 }
 904
 905                 fn elapsed(&self) -> Duration {
 906                         std::time::Instant::elapsed(self)
 907                 }
 908         }
 909
 910         impl Time for Eternity {
 911                 fn now() -> Self {
 912                         Self
 913                 }
 914
 915                 fn duration_since(&self, _earlier: Self) -> Duration {
 916                         Duration::from_secs(0)
 917                 }
 918
 919                 fn duration_since_epoch() -> Duration {
 920                         Duration::from_secs(0)
 921                 }
 922
 923                 fn elapsed(&self) -> Duration {
 924                         Duration::from_secs(0)
 925                 }
 926         }
 927
 928         impl Sub<Duration> for Eternity {
 929                 type Output = Self;
 930
 931                 fn sub(self, _other: Duration) -> Self {
 932                         self
 933                 }
 934         }
 935 }
 936
 937 pub(crate) use self::time::Time;
 938
 939 #[cfg(test)]
 940 mod tests {
 941         use super::{ChannelLiquidity, ProbabilisticScoringParameters, ProbabilisticScorerUsingTime, ScoringParameters, ScorerUsingTime, Time};
 942         use super::time::Eternity;
 943
 944         use ln::features::{ChannelFeatures, NodeFeatures};
 945         use ln::msgs::{ChannelAnnouncement, ChannelUpdate, OptionalField, UnsignedChannelAnnouncement, UnsignedChannelUpdate};
 946         use routing::scoring::Score;
 947         use routing::network_graph::{NetworkGraph, NodeId};
 948         use routing::router::RouteHop;
 949         use util::ser::{Readable, ReadableArgs, Writeable};
 950
 951         use bitcoin::blockdata::constants::genesis_block;
 952         use bitcoin::hashes::Hash;
 953         use bitcoin::hashes::sha256d::Hash as Sha256dHash;
 954         use bitcoin::network::constants::Network;
 955         use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey};
 956         use core::cell::Cell;
 957         use core::ops::Sub;
 958         use core::time::Duration;
 959         use io;
 960
 961         // `Time` tests
 962
 963         /// Time that can be advanced manually in tests.
 964         #[derive(Clone, Copy, Debug, PartialEq, Eq)]
 965         struct SinceEpoch(Duration);
 966
 967         impl SinceEpoch {
 968                 thread_local! {
 969                         static ELAPSED: Cell<Duration> = core::cell::Cell::new(Duration::from_secs(0));
 970                 }
 971
 972                 fn advance(duration: Duration) {
 973                         Self::ELAPSED.with(|elapsed| elapsed.set(elapsed.get() + duration))
 974                 }
 975         }
 976
 977         impl Time for SinceEpoch {
 978                 fn now() -> Self {
 979                         Self(Self::duration_since_epoch())
 980                 }
 981
 982                 fn duration_since(&self, earlier: Self) -> Duration {
 983                         self.0 - earlier.0
 984                 }
 985
 986                 fn duration_since_epoch() -> Duration {
 987                         Self::ELAPSED.with(|elapsed| elapsed.get())
 988                 }
 989
 990                 fn elapsed(&self) -> Duration {
 991                         Self::duration_since_epoch() - self.0
 992                 }
 993         }
 994
 995         impl Sub<Duration> for SinceEpoch {
 996                 type Output = Self;
 997
 998                 fn sub(self, other: Duration) -> Self {
 999                         Self(self.0 - other)
1000                 }
1001         }
1002
1003         #[test]
1004         fn time_passes_when_advanced() {
1005                 let now = SinceEpoch::now();
1006                 assert_eq!(now.elapsed(), Duration::from_secs(0));
1007
1008                 SinceEpoch::advance(Duration::from_secs(1));
1009                 SinceEpoch::advance(Duration::from_secs(1));
1010
1011                 let elapsed = now.elapsed();
1012                 let later = SinceEpoch::now();
1013
1014                 assert_eq!(elapsed, Duration::from_secs(2));
1015                 assert_eq!(later - elapsed, now);
1016         }
1017
1018         #[test]
1019         fn time_never_passes_in_an_eternity() {
1020                 let now = Eternity::now();
1021                 let elapsed = now.elapsed();
1022                 let later = Eternity::now();
1023
1024                 assert_eq!(now.elapsed(), Duration::from_secs(0));
1025                 assert_eq!(later - elapsed, now);
1026         }
1027
1028         // `Scorer` tests
1029
1030         /// A scorer for testing with time that can be manually advanced.
1031         type Scorer = ScorerUsingTime::<SinceEpoch>;
1032
1033         fn source_privkey() -> SecretKey {
1034                 SecretKey::from_slice(&[42; 32]).unwrap()
1035         }
1036
1037         fn target_privkey() -> SecretKey {
1038                 SecretKey::from_slice(&[43; 32]).unwrap()
1039         }
1040
1041         fn source_pubkey() -> PublicKey {
1042                 let secp_ctx = Secp256k1::new();
1043                 PublicKey::from_secret_key(&secp_ctx, &source_privkey())
1044         }
1045
1046         fn target_pubkey() -> PublicKey {
1047                 let secp_ctx = Secp256k1::new();
1048                 PublicKey::from_secret_key(&secp_ctx, &target_privkey())
1049         }
1050
1051         fn source_node_id() -> NodeId {
1052                 NodeId::from_pubkey(&source_pubkey())
1053         }
1054
1055         fn target_node_id() -> NodeId {
1056                 NodeId::from_pubkey(&target_pubkey())
1057         }
1058
1059         #[test]
1060         fn penalizes_without_channel_failures() {
1061                 let scorer = Scorer::new(ScoringParameters {
1062                         base_penalty_msat: 1_000,
1063                         failure_penalty_msat: 512,
1064                         failure_penalty_half_life: Duration::from_secs(1),
1065                         overuse_penalty_start_1024th: 1024,
1066                         overuse_penalty_msat_per_1024th: 0,
1067                 });
1068                 let source = source_node_id();
1069                 let target = target_node_id();
1070                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1071
1072                 SinceEpoch::advance(Duration::from_secs(1));
1073                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1074         }
1075
1076         #[test]
1077         fn accumulates_channel_failure_penalties() {
1078                 let mut scorer = Scorer::new(ScoringParameters {
1079                         base_penalty_msat: 1_000,
1080                         failure_penalty_msat: 64,
1081                         failure_penalty_half_life: Duration::from_secs(10),
1082                         overuse_penalty_start_1024th: 1024,
1083                         overuse_penalty_msat_per_1024th: 0,
1084                 });
1085                 let source = source_node_id();
1086                 let target = target_node_id();
1087                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1088
1089                 scorer.payment_path_failed(&[], 42);
1090                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_064);
1091
1092                 scorer.payment_path_failed(&[], 42);
1093                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_128);
1094
1095                 scorer.payment_path_failed(&[], 42);
1096                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_192);
1097         }
1098
1099         #[test]
1100         fn decays_channel_failure_penalties_over_time() {
1101                 let mut scorer = Scorer::new(ScoringParameters {
1102                         base_penalty_msat: 1_000,
1103                         failure_penalty_msat: 512,
1104                         failure_penalty_half_life: Duration::from_secs(10),
1105                         overuse_penalty_start_1024th: 1024,
1106                         overuse_penalty_msat_per_1024th: 0,
1107                 });
1108                 let source = source_node_id();
1109                 let target = target_node_id();
1110                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1111
1112                 scorer.payment_path_failed(&[], 42);
1113                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1114
1115                 SinceEpoch::advance(Duration::from_secs(9));
1116                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1117
1118                 SinceEpoch::advance(Duration::from_secs(1));
1119                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1120
1121                 SinceEpoch::advance(Duration::from_secs(10 * 8));
1122                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_001);
1123
1124                 SinceEpoch::advance(Duration::from_secs(10));
1125                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1126
1127                 SinceEpoch::advance(Duration::from_secs(10));
1128                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1129         }
1130
1131         #[test]
1132         fn decays_channel_failure_penalties_without_shift_overflow() {
1133                 let mut scorer = Scorer::new(ScoringParameters {
1134                         base_penalty_msat: 1_000,
1135                         failure_penalty_msat: 512,
1136                         failure_penalty_half_life: Duration::from_secs(10),
1137                         overuse_penalty_start_1024th: 1024,
1138                         overuse_penalty_msat_per_1024th: 0,
1139                 });
1140                 let source = source_node_id();
1141                 let target = target_node_id();
1142                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1143
1144                 scorer.payment_path_failed(&[], 42);
1145                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1146
1147                 // An unchecked right shift 64 bits or more in ChannelFailure::decayed_penalty_msat would
1148                 // cause an overflow.
1149                 SinceEpoch::advance(Duration::from_secs(10 * 64));
1150                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1151
1152                 SinceEpoch::advance(Duration::from_secs(10));
1153                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1154         }
1155
1156         #[test]
1157         fn accumulates_channel_failure_penalties_after_decay() {
1158                 let mut scorer = Scorer::new(ScoringParameters {
1159                         base_penalty_msat: 1_000,
1160                         failure_penalty_msat: 512,
1161                         failure_penalty_half_life: Duration::from_secs(10),
1162                         overuse_penalty_start_1024th: 1024,
1163                         overuse_penalty_msat_per_1024th: 0,
1164                 });
1165                 let source = source_node_id();
1166                 let target = target_node_id();
1167                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1168
1169                 scorer.payment_path_failed(&[], 42);
1170                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1171
1172                 SinceEpoch::advance(Duration::from_secs(10));
1173                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1174
1175                 scorer.payment_path_failed(&[], 42);
1176                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_768);
1177
1178                 SinceEpoch::advance(Duration::from_secs(10));
1179                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_384);
1180         }
1181
1182         #[test]
1183         fn reduces_channel_failure_penalties_after_success() {
1184                 let mut scorer = Scorer::new(ScoringParameters {
1185                         base_penalty_msat: 1_000,
1186                         failure_penalty_msat: 512,
1187                         failure_penalty_half_life: Duration::from_secs(10),
1188                         overuse_penalty_start_1024th: 1024,
1189                         overuse_penalty_msat_per_1024th: 0,
1190                 });
1191                 let source = source_node_id();
1192                 let target = target_node_id();
1193                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1194
1195                 scorer.payment_path_failed(&[], 42);
1196                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1197
1198                 SinceEpoch::advance(Duration::from_secs(10));
1199                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1200
1201                 let hop = RouteHop {
1202                         pubkey: PublicKey::from_slice(target.as_slice()).unwrap(),
1203                         node_features: NodeFeatures::known(),
1204                         short_channel_id: 42,
1205                         channel_features: ChannelFeatures::known(),
1206                         fee_msat: 1,
1207                         cltv_expiry_delta: 18,
1208                 };
1209                 scorer.payment_path_successful(&[&hop]);
1210                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_128);
1211
1212                 SinceEpoch::advance(Duration::from_secs(10));
1213                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_064);
1214         }
1215
1216         #[test]
1217         fn restores_persisted_channel_failure_penalties() {
1218                 let mut scorer = Scorer::new(ScoringParameters {
1219                         base_penalty_msat: 1_000,
1220                         failure_penalty_msat: 512,
1221                         failure_penalty_half_life: Duration::from_secs(10),
1222                         overuse_penalty_start_1024th: 1024,
1223                         overuse_penalty_msat_per_1024th: 0,
1224                 });
1225                 let source = source_node_id();
1226                 let target = target_node_id();
1227
1228                 scorer.payment_path_failed(&[], 42);
1229                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1230
1231                 SinceEpoch::advance(Duration::from_secs(10));
1232                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1233
1234                 scorer.payment_path_failed(&[], 43);
1235                 assert_eq!(scorer.channel_penalty_msat(43, 1, 1, &source, &target), 1_512);
1236
1237                 let mut serialized_scorer = Vec::new();
1238                 scorer.write(&mut serialized_scorer).unwrap();
1239
1240                 let deserialized_scorer = <Scorer>::read(&mut io::Cursor::new(&serialized_scorer)).unwrap();
1241                 assert_eq!(deserialized_scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1242                 assert_eq!(deserialized_scorer.channel_penalty_msat(43, 1, 1, &source, &target), 1_512);
1243         }
1244
1245         #[test]
1246         fn decays_persisted_channel_failure_penalties() {
1247                 let mut scorer = Scorer::new(ScoringParameters {
1248                         base_penalty_msat: 1_000,
1249                         failure_penalty_msat: 512,
1250                         failure_penalty_half_life: Duration::from_secs(10),
1251                         overuse_penalty_start_1024th: 1024,
1252                         overuse_penalty_msat_per_1024th: 0,
1253                 });
1254                 let source = source_node_id();
1255                 let target = target_node_id();
1256
1257                 scorer.payment_path_failed(&[], 42);
1258                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1259
1260                 let mut serialized_scorer = Vec::new();
1261                 scorer.write(&mut serialized_scorer).unwrap();
1262
1263                 SinceEpoch::advance(Duration::from_secs(10));
1264
1265                 let deserialized_scorer = <Scorer>::read(&mut io::Cursor::new(&serialized_scorer)).unwrap();
1266                 assert_eq!(deserialized_scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1267
1268                 SinceEpoch::advance(Duration::from_secs(10));
1269                 assert_eq!(deserialized_scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_128);
1270         }
1271
1272         #[test]
1273         fn charges_per_1024th_penalty() {
1274                 let scorer = Scorer::new(ScoringParameters {
1275                         base_penalty_msat: 0,
1276                         failure_penalty_msat: 0,
1277                         failure_penalty_half_life: Duration::from_secs(0),
1278                         overuse_penalty_start_1024th: 256,
1279                         overuse_penalty_msat_per_1024th: 100,
1280                 });
1281                 let source = source_node_id();
1282                 let target = target_node_id();
1283
1284                 assert_eq!(scorer.channel_penalty_msat(42, 1_000, 1_024_000, &source, &target), 0);
1285                 assert_eq!(scorer.channel_penalty_msat(42, 256_999, 1_024_000, &source, &target), 0);
1286                 assert_eq!(scorer.channel_penalty_msat(42, 257_000, 1_024_000, &source, &target), 100);
1287                 assert_eq!(scorer.channel_penalty_msat(42, 258_000, 1_024_000, &source, &target), 200);
1288                 assert_eq!(scorer.channel_penalty_msat(42, 512_000, 1_024_000, &source, &target), 256 * 100);
1289         }
1290
1291         // `ProbabilisticScorer` tests
1292
1293         /// A probabilistic scorer for testing with time that can be manually advanced.
1294         type ProbabilisticScorer<'a> = ProbabilisticScorerUsingTime::<&'a NetworkGraph, SinceEpoch>;
1295
1296         fn sender_privkey() -> SecretKey {
1297                 SecretKey::from_slice(&[41; 32]).unwrap()
1298         }
1299
1300         fn recipient_privkey() -> SecretKey {
1301                 SecretKey::from_slice(&[45; 32]).unwrap()
1302         }
1303
1304         fn sender_pubkey() -> PublicKey {
1305                 let secp_ctx = Secp256k1::new();
1306                 PublicKey::from_secret_key(&secp_ctx, &sender_privkey())
1307         }
1308
1309         fn recipient_pubkey() -> PublicKey {
1310                 let secp_ctx = Secp256k1::new();
1311                 PublicKey::from_secret_key(&secp_ctx, &recipient_privkey())
1312         }
1313
1314         fn sender_node_id() -> NodeId {
1315                 NodeId::from_pubkey(&sender_pubkey())
1316         }
1317
1318         fn recipient_node_id() -> NodeId {
1319                 NodeId::from_pubkey(&recipient_pubkey())
1320         }
1321
1322         fn network_graph() -> NetworkGraph {
1323                 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1324                 let mut network_graph = NetworkGraph::new(genesis_hash);
1325                 add_channel(&mut network_graph, 42, source_privkey(), target_privkey());
1326                 add_channel(&mut network_graph, 43, target_privkey(), recipient_privkey());
1327
1328                 network_graph
1329         }
1330
1331         fn add_channel(
1332                 network_graph: &mut NetworkGraph, short_channel_id: u64, node_1_key: SecretKey,
1333                 node_2_key: SecretKey
1334         ) {
1335                 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1336                 let node_1_secret = &SecretKey::from_slice(&[39; 32]).unwrap();
1337                 let node_2_secret = &SecretKey::from_slice(&[40; 32]).unwrap();
1338                 let secp_ctx = Secp256k1::new();
1339                 let unsigned_announcement = UnsignedChannelAnnouncement {
1340                         features: ChannelFeatures::known(),
1341                         chain_hash: genesis_hash,
1342                         short_channel_id,
1343                         node_id_1: PublicKey::from_secret_key(&secp_ctx, &node_1_key),
1344                         node_id_2: PublicKey::from_secret_key(&secp_ctx, &node_2_key),
1345                         bitcoin_key_1: PublicKey::from_secret_key(&secp_ctx, &node_1_secret),
1346                         bitcoin_key_2: PublicKey::from_secret_key(&secp_ctx, &node_2_secret),
1347                         excess_data: Vec::new(),
1348                 };
1349                 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
1350                 let signed_announcement = ChannelAnnouncement {
1351                         node_signature_1: secp_ctx.sign(&msghash, &node_1_key),
1352                         node_signature_2: secp_ctx.sign(&msghash, &node_2_key),
1353                         bitcoin_signature_1: secp_ctx.sign(&msghash, &node_1_secret),
1354                         bitcoin_signature_2: secp_ctx.sign(&msghash, &node_2_secret),
1355                         contents: unsigned_announcement,
1356                 };
1357                 let chain_source: Option<&::util::test_utils::TestChainSource> = None;
1358                 network_graph.update_channel_from_announcement(
1359                         &signed_announcement, &chain_source, &secp_ctx).unwrap();
1360                 update_channel(network_graph, short_channel_id, node_1_key, 0);
1361                 update_channel(network_graph, short_channel_id, node_2_key, 1);
1362         }
1363
1364         fn update_channel(
1365                 network_graph: &mut NetworkGraph, short_channel_id: u64, node_key: SecretKey, flags: u8
1366         ) {
1367                 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1368                 let secp_ctx = Secp256k1::new();
1369                 let unsigned_update = UnsignedChannelUpdate {
1370                         chain_hash: genesis_hash,
1371                         short_channel_id,
1372                         timestamp: 100,
1373                         flags,
1374                         cltv_expiry_delta: 18,
1375                         htlc_minimum_msat: 0,
1376                         htlc_maximum_msat: OptionalField::Present(1_000),
1377                         fee_base_msat: 1,
1378                         fee_proportional_millionths: 0,
1379                         excess_data: Vec::new(),
1380                 };
1381                 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_update.encode()[..])[..]);
1382                 let signed_update = ChannelUpdate {
1383                         signature: secp_ctx.sign(&msghash, &node_key),
1384                         contents: unsigned_update,
1385                 };
1386                 network_graph.update_channel(&signed_update, &secp_ctx).unwrap();
1387         }
1388
1389         fn payment_path_for_amount(amount_msat: u64) -> Vec<RouteHop> {
1390                 vec![
1391                         RouteHop {
1392                                 pubkey: source_pubkey(),
1393                                 node_features: NodeFeatures::known(),
1394                                 short_channel_id: 41,
1395                                 channel_features: ChannelFeatures::known(),
1396                                 fee_msat: 1,
1397                                 cltv_expiry_delta: 18,
1398                         },
1399                         RouteHop {
1400                                 pubkey: target_pubkey(),
1401                                 node_features: NodeFeatures::known(),
1402                                 short_channel_id: 42,
1403                                 channel_features: ChannelFeatures::known(),
1404                                 fee_msat: 2,
1405                                 cltv_expiry_delta: 18,
1406                         },
1407                         RouteHop {
1408                                 pubkey: recipient_pubkey(),
1409                                 node_features: NodeFeatures::known(),
1410                                 short_channel_id: 43,
1411                                 channel_features: ChannelFeatures::known(),
1412                                 fee_msat: amount_msat,
1413                                 cltv_expiry_delta: 18,
1414                         },
1415                 ]
1416         }
1417
1418         #[test]
1419         fn liquidity_bounds_directed_from_lowest_node_id() {
1420                 let last_updated = SinceEpoch::now();
1421                 let network_graph = network_graph();
1422                 let params = ProbabilisticScoringParameters::default();
1423                 let mut scorer = ProbabilisticScorer::new(params, &network_graph)
1424                         .with_channel(42,
1425                                 ChannelLiquidity {
1426                                         min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated
1427                                 })
1428                         .with_channel(43,
1429                                 ChannelLiquidity {
1430                                         min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated
1431                                 });
1432                 let source = source_node_id();
1433                 let target = target_node_id();
1434                 let recipient = recipient_node_id();
1435                 assert!(source > target);
1436                 assert!(target < recipient);
1437
1438                 // Update minimum liquidity.
1439
1440                 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
1441                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1442                         .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1443                 assert_eq!(liquidity.min_liquidity_msat(), 100);
1444                 assert_eq!(liquidity.max_liquidity_msat(), 300);
1445
1446                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1447                         .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1448                 assert_eq!(liquidity.min_liquidity_msat(), 700);
1449                 assert_eq!(liquidity.max_liquidity_msat(), 900);
1450
1451                 scorer.channel_liquidities.get_mut(&42).unwrap()
1452                         .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
1453                         .set_min_liquidity_msat(200);
1454
1455                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1456                         .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1457                 assert_eq!(liquidity.min_liquidity_msat(), 200);
1458                 assert_eq!(liquidity.max_liquidity_msat(), 300);
1459
1460                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1461                         .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1462                 assert_eq!(liquidity.min_liquidity_msat(), 700);
1463                 assert_eq!(liquidity.max_liquidity_msat(), 800);
1464
1465                 // Update maximum liquidity.
1466
1467                 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1468                         .as_directed(&target, &recipient, 1_000, liquidity_offset_half_life);
1469                 assert_eq!(liquidity.min_liquidity_msat(), 700);
1470                 assert_eq!(liquidity.max_liquidity_msat(), 900);
1471
1472                 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1473                         .as_directed(&recipient, &target, 1_000, liquidity_offset_half_life);
1474                 assert_eq!(liquidity.min_liquidity_msat(), 100);
1475                 assert_eq!(liquidity.max_liquidity_msat(), 300);
1476
1477                 scorer.channel_liquidities.get_mut(&43).unwrap()
1478                         .as_directed_mut(&target, &recipient, 1_000, liquidity_offset_half_life)
1479                         .set_max_liquidity_msat(200);
1480
1481                 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1482                         .as_directed(&target, &recipient, 1_000, liquidity_offset_half_life);
1483                 assert_eq!(liquidity.min_liquidity_msat(), 0);
1484                 assert_eq!(liquidity.max_liquidity_msat(), 200);
1485
1486                 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1487                         .as_directed(&recipient, &target, 1_000, liquidity_offset_half_life);
1488                 assert_eq!(liquidity.min_liquidity_msat(), 800);
1489                 assert_eq!(liquidity.max_liquidity_msat(), 1000);
1490         }
1491
1492         #[test]
1493         fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() {
1494                 let last_updated = SinceEpoch::now();
1495                 let network_graph = network_graph();
1496                 let params = ProbabilisticScoringParameters::default();
1497                 let mut scorer = ProbabilisticScorer::new(params, &network_graph)
1498                         .with_channel(42,
1499                                 ChannelLiquidity {
1500                                         min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated
1501                                 });
1502                 let source = source_node_id();
1503                 let target = target_node_id();
1504                 assert!(source > target);
1505
1506                 // Check initial bounds.
1507                 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
1508                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1509                         .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1510                 assert_eq!(liquidity.min_liquidity_msat(), 400);
1511                 assert_eq!(liquidity.max_liquidity_msat(), 800);
1512
1513                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1514                         .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1515                 assert_eq!(liquidity.min_liquidity_msat(), 200);
1516                 assert_eq!(liquidity.max_liquidity_msat(), 600);
1517
1518                 // Reset from source to target.
1519                 scorer.channel_liquidities.get_mut(&42).unwrap()
1520                         .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
1521                         .set_min_liquidity_msat(900);
1522
1523                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1524                         .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1525                 assert_eq!(liquidity.min_liquidity_msat(), 900);
1526                 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1527
1528                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1529                         .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1530                 assert_eq!(liquidity.min_liquidity_msat(), 0);
1531                 assert_eq!(liquidity.max_liquidity_msat(), 100);
1532
1533                 // Reset from target to source.
1534                 scorer.channel_liquidities.get_mut(&42).unwrap()
1535                         .as_directed_mut(&target, &source, 1_000, liquidity_offset_half_life)
1536                         .set_min_liquidity_msat(400);
1537
1538                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1539                         .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1540                 assert_eq!(liquidity.min_liquidity_msat(), 0);
1541                 assert_eq!(liquidity.max_liquidity_msat(), 600);
1542
1543                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1544                         .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1545                 assert_eq!(liquidity.min_liquidity_msat(), 400);
1546                 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1547         }
1548
1549         #[test]
1550         fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() {
1551                 let last_updated = SinceEpoch::now();
1552                 let network_graph = network_graph();
1553                 let params = ProbabilisticScoringParameters::default();
1554                 let mut scorer = ProbabilisticScorer::new(params, &network_graph)
1555                         .with_channel(42,
1556                                 ChannelLiquidity {
1557                                         min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated
1558                                 });
1559                 let source = source_node_id();
1560                 let target = target_node_id();
1561                 assert!(source > target);
1562
1563                 // Check initial bounds.
1564                 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
1565                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1566                         .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1567                 assert_eq!(liquidity.min_liquidity_msat(), 400);
1568                 assert_eq!(liquidity.max_liquidity_msat(), 800);
1569
1570                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1571                         .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1572                 assert_eq!(liquidity.min_liquidity_msat(), 200);
1573                 assert_eq!(liquidity.max_liquidity_msat(), 600);
1574
1575                 // Reset from source to target.
1576                 scorer.channel_liquidities.get_mut(&42).unwrap()
1577                         .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
1578                         .set_max_liquidity_msat(300);
1579
1580                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1581                         .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1582                 assert_eq!(liquidity.min_liquidity_msat(), 0);
1583                 assert_eq!(liquidity.max_liquidity_msat(), 300);
1584
1585                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1586                         .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1587                 assert_eq!(liquidity.min_liquidity_msat(), 700);
1588                 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1589
1590                 // Reset from target to source.
1591                 scorer.channel_liquidities.get_mut(&42).unwrap()
1592                         .as_directed_mut(&target, &source, 1_000, liquidity_offset_half_life)
1593                         .set_max_liquidity_msat(600);
1594
1595                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1596                         .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1597                 assert_eq!(liquidity.min_liquidity_msat(), 400);
1598                 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1599
1600                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1601                         .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1602                 assert_eq!(liquidity.min_liquidity_msat(), 0);
1603                 assert_eq!(liquidity.max_liquidity_msat(), 600);
1604         }
1605
1606         #[test]
1607         fn increased_penalty_nearing_liquidity_upper_bound() {
1608                 let network_graph = network_graph();
1609                 let params = ProbabilisticScoringParameters {
1610                         liquidity_penalty_multiplier_msat: 1_000, ..Default::default()
1611                 };
1612                 let scorer = ProbabilisticScorer::new(params, &network_graph);
1613                 let source = source_node_id();
1614                 let target = target_node_id();
1615
1616                 assert_eq!(scorer.channel_penalty_msat(42, 100, 100_000, &source, &target), 0);
1617                 assert_eq!(scorer.channel_penalty_msat(42, 1_000, 100_000, &source, &target), 4);
1618                 assert_eq!(scorer.channel_penalty_msat(42, 10_000, 100_000, &source, &target), 45);
1619                 assert_eq!(scorer.channel_penalty_msat(42, 100_000, 100_000, &source, &target), 2_000);
1620
1621                 assert_eq!(scorer.channel_penalty_msat(42, 125, 1_000, &source, &target), 57);
1622                 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 124);
1623                 assert_eq!(scorer.channel_penalty_msat(42, 375, 1_000, &source, &target), 203);
1624                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300);
1625                 assert_eq!(scorer.channel_penalty_msat(42, 625, 1_000, &source, &target), 425);
1626                 assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 600);
1627                 assert_eq!(scorer.channel_penalty_msat(42, 875, 1_000, &source, &target), 900);
1628         }
1629
1630         #[test]
1631         fn constant_penalty_outside_liquidity_bounds() {
1632                 let last_updated = SinceEpoch::now();
1633                 let network_graph = network_graph();
1634                 let params = ProbabilisticScoringParameters {
1635                         liquidity_penalty_multiplier_msat: 1_000, ..Default::default()
1636                 };
1637                 let scorer = ProbabilisticScorer::new(params, &network_graph)
1638                         .with_channel(42,
1639                                 ChannelLiquidity {
1640                                         min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40, last_updated
1641                                 });
1642                 let source = source_node_id();
1643                 let target = target_node_id();
1644
1645                 assert_eq!(scorer.channel_penalty_msat(42, 39, 100, &source, &target), 0);
1646                 assert_ne!(scorer.channel_penalty_msat(42, 50, 100, &source, &target), 0);
1647                 assert_ne!(scorer.channel_penalty_msat(42, 50, 100, &source, &target), 2_000);
1648                 assert_eq!(scorer.channel_penalty_msat(42, 61, 100, &source, &target), 2_000);
1649         }
1650
1651         #[test]
1652         fn does_not_further_penalize_own_channel() {
1653                 let network_graph = network_graph();
1654                 let params = ProbabilisticScoringParameters {
1655                         liquidity_penalty_multiplier_msat: 1_000, ..Default::default()
1656                 };
1657                 let mut scorer = ProbabilisticScorer::new(params, &network_graph);
1658                 let sender = sender_node_id();
1659                 let source = source_node_id();
1660                 let failed_path = payment_path_for_amount(500);
1661                 let successful_path = payment_path_for_amount(200);
1662
1663                 assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 300);
1664
1665                 scorer.payment_path_failed(&failed_path.iter().collect::<Vec<_>>(), 41);
1666                 assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 300);
1667
1668                 scorer.payment_path_successful(&successful_path.iter().collect::<Vec<_>>());
1669                 assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 300);
1670         }
1671
1672         #[test]
1673         fn sets_liquidity_lower_bound_on_downstream_failure() {
1674                 let network_graph = network_graph();
1675                 let params = ProbabilisticScoringParameters {
1676                         liquidity_penalty_multiplier_msat: 1_000, ..Default::default()
1677                 };
1678                 let mut scorer = ProbabilisticScorer::new(params, &network_graph);
1679                 let source = source_node_id();
1680                 let target = target_node_id();
1681                 let path = payment_path_for_amount(500);
1682
1683                 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 124);
1684                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300);
1685                 assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 600);
1686
1687                 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 43);
1688
1689                 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 0);
1690                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 0);
1691                 assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 300);
1692         }
1693
1694         #[test]
1695         fn sets_liquidity_upper_bound_on_failure() {
1696                 let network_graph = network_graph();
1697                 let params = ProbabilisticScoringParameters {
1698                         liquidity_penalty_multiplier_msat: 1_000, ..Default::default()
1699                 };
1700                 let mut scorer = ProbabilisticScorer::new(params, &network_graph);
1701                 let source = source_node_id();
1702                 let target = target_node_id();
1703                 let path = payment_path_for_amount(500);
1704
1705                 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 124);
1706                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300);
1707                 assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 600);
1708
1709                 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 42);
1710
1711                 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 300);
1712                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 2_000);
1713                 assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 2_000);
1714         }
1715
1716         #[test]
1717         fn reduces_liquidity_upper_bound_along_path_on_success() {
1718                 let network_graph = network_graph();
1719                 let params = ProbabilisticScoringParameters {
1720                         liquidity_penalty_multiplier_msat: 1_000, ..Default::default()
1721                 };
1722                 let mut scorer = ProbabilisticScorer::new(params, &network_graph);
1723                 let sender = sender_node_id();
1724                 let source = source_node_id();
1725                 let target = target_node_id();
1726                 let recipient = recipient_node_id();
1727                 let path = payment_path_for_amount(500);
1728
1729                 assert_eq!(scorer.channel_penalty_msat(41, 250, 1_000, &sender, &source), 124);
1730                 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 124);
1731                 assert_eq!(scorer.channel_penalty_msat(43, 250, 1_000, &target, &recipient), 124);
1732
1733                 scorer.payment_path_successful(&path.iter().collect::<Vec<_>>());
1734
1735                 assert_eq!(scorer.channel_penalty_msat(41, 250, 1_000, &sender, &source), 124);
1736                 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 300);
1737                 assert_eq!(scorer.channel_penalty_msat(43, 250, 1_000, &target, &recipient), 300);
1738         }
1739
1740         #[test]
1741         fn decays_liquidity_bounds_over_time() {
1742                 let network_graph = network_graph();
1743                 let params = ProbabilisticScoringParameters {
1744                         liquidity_penalty_multiplier_msat: 1_000,
1745                         liquidity_offset_half_life: Duration::from_secs(10),
1746                 };
1747                 let mut scorer = ProbabilisticScorer::new(params, &network_graph);
1748                 let source = source_node_id();
1749                 let target = target_node_id();
1750
1751                 assert_eq!(scorer.channel_penalty_msat(42, 0, 1_024, &source, &target), 0);
1752                 assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024, &source, &target), 2_000);
1753
1754                 scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::<Vec<_>>(), 42);
1755                 scorer.payment_path_failed(&payment_path_for_amount(128).iter().collect::<Vec<_>>(), 43);
1756
1757                 assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 0);
1758                 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 92);
1759                 assert_eq!(scorer.channel_penalty_msat(42, 768, 1_024, &source, &target), 1_424);
1760                 assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), 2_000);
1761
1762                 SinceEpoch::advance(Duration::from_secs(9));
1763                 assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 0);
1764                 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 92);
1765                 assert_eq!(scorer.channel_penalty_msat(42, 768, 1_024, &source, &target), 1_424);
1766                 assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), 2_000);
1767
1768                 SinceEpoch::advance(Duration::from_secs(1));
1769                 assert_eq!(scorer.channel_penalty_msat(42, 64, 1_024, &source, &target), 0);
1770                 assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 34);
1771                 assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), 1_812);
1772                 assert_eq!(scorer.channel_penalty_msat(42, 960, 1_024, &source, &target), 2_000);
1773
1774                 // Fully decay liquidity lower bound.
1775                 SinceEpoch::advance(Duration::from_secs(10 * 7));
1776                 assert_eq!(scorer.channel_penalty_msat(42, 0, 1_024, &source, &target), 0);
1777                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1_024, &source, &target), 0);
1778                 assert_eq!(scorer.channel_penalty_msat(42, 1_023, 1_024, &source, &target), 2_000);
1779                 assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024, &source, &target), 2_000);
1780
1781                 // Fully decay liquidity upper bound.
1782                 SinceEpoch::advance(Duration::from_secs(10));
1783                 assert_eq!(scorer.channel_penalty_msat(42, 0, 1_024, &source, &target), 0);
1784                 assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024, &source, &target), 2_000);
1785
1786                 SinceEpoch::advance(Duration::from_secs(10));
1787                 assert_eq!(scorer.channel_penalty_msat(42, 0, 1_024, &source, &target), 0);
1788                 assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024, &source, &target), 2_000);
1789         }
1790
1791         #[test]
1792         fn decays_liquidity_bounds_without_shift_overflow() {
1793                 let network_graph = network_graph();
1794                 let params = ProbabilisticScoringParameters {
1795                         liquidity_penalty_multiplier_msat: 1_000,
1796                         liquidity_offset_half_life: Duration::from_secs(10),
1797                 };
1798                 let mut scorer = ProbabilisticScorer::new(params, &network_graph);
1799                 let source = source_node_id();
1800                 let target = target_node_id();
1801                 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 124);
1802
1803                 scorer.payment_path_failed(&payment_path_for_amount(512).iter().collect::<Vec<_>>(), 42);
1804                 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 281);
1805
1806                 // An unchecked right shift 64 bits or more in DirectedChannelLiquidity::decayed_offset_msat
1807                 // would cause an overflow.
1808                 SinceEpoch::advance(Duration::from_secs(10 * 64));
1809                 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 124);
1810
1811                 SinceEpoch::advance(Duration::from_secs(10));
1812                 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 124);
1813         }
1814
1815         #[test]
1816         fn restricts_liquidity_bounds_after_decay() {
1817                 let network_graph = network_graph();
1818                 let params = ProbabilisticScoringParameters {
1819                         liquidity_penalty_multiplier_msat: 1_000,
1820                         liquidity_offset_half_life: Duration::from_secs(10),
1821                 };
1822                 let mut scorer = ProbabilisticScorer::new(params, &network_graph);
1823                 let source = source_node_id();
1824                 let target = target_node_id();
1825
1826                 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 300);
1827
1828                 // More knowledge gives higher confidence (256, 768), meaning a lower penalty.
1829                 scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::<Vec<_>>(), 42);
1830                 scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::<Vec<_>>(), 43);
1831                 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 281);
1832
1833                 // Decaying knowledge gives less confidence (128, 896), meaning a higher penalty.
1834                 SinceEpoch::advance(Duration::from_secs(10));
1835                 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 293);
1836
1837                 // Reducing the upper bound gives more confidence (128, 832) that the payment amount (512)
1838                 // is closer to the upper bound, meaning a higher penalty.
1839                 scorer.payment_path_successful(&payment_path_for_amount(64).iter().collect::<Vec<_>>());
1840                 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 333);
1841
1842                 // Increasing the lower bound gives more confidence (256, 832) that the payment amount (512)
1843                 // is closer to the lower bound, meaning a lower penalty.
1844                 scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::<Vec<_>>(), 43);
1845                 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 247);
1846
1847                 // Further decaying affects the lower bound more than the upper bound (128, 928).
1848                 SinceEpoch::advance(Duration::from_secs(10));
1849                 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 280);
1850         }
1851
1852         #[test]
1853         fn restores_persisted_liquidity_bounds() {
1854                 let network_graph = network_graph();
1855                 let params = ProbabilisticScoringParameters {
1856                         liquidity_penalty_multiplier_msat: 1_000,
1857                         liquidity_offset_half_life: Duration::from_secs(10),
1858                 };
1859                 let mut scorer = ProbabilisticScorer::new(params, &network_graph);
1860                 let source = source_node_id();
1861                 let target = target_node_id();
1862
1863                 scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
1864                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 2_000);
1865
1866                 SinceEpoch::advance(Duration::from_secs(10));
1867                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 475);
1868
1869                 scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::<Vec<_>>(), 43);
1870                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300);
1871
1872                 let mut serialized_scorer = Vec::new();
1873                 scorer.write(&mut serialized_scorer).unwrap();
1874
1875                 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
1876                 let deserialized_scorer =
1877                         <ProbabilisticScorer>::read(&mut serialized_scorer, (params, &network_graph)).unwrap();
1878                 assert_eq!(deserialized_scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300);
1879         }
1880
1881         #[test]
1882         fn decays_persisted_liquidity_bounds() {
1883                 let network_graph = network_graph();
1884                 let params = ProbabilisticScoringParameters {
1885                         liquidity_penalty_multiplier_msat: 1_000,
1886                         liquidity_offset_half_life: Duration::from_secs(10),
1887                 };
1888                 let mut scorer = ProbabilisticScorer::new(params, &network_graph);
1889                 let source = source_node_id();
1890                 let target = target_node_id();
1891
1892                 scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
1893                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 2_000);
1894
1895                 let mut serialized_scorer = Vec::new();
1896                 scorer.write(&mut serialized_scorer).unwrap();
1897
1898                 SinceEpoch::advance(Duration::from_secs(10));
1899
1900                 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
1901                 let deserialized_scorer =
1902                         <ProbabilisticScorer>::read(&mut serialized_scorer, (params, &network_graph)).unwrap();
1903                 assert_eq!(deserialized_scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 475);
1904
1905                 scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::<Vec<_>>(), 43);
1906                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300);
1907
1908                 SinceEpoch::advance(Duration::from_secs(10));
1909                 assert_eq!(deserialized_scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 367);
1910         }
1911 }