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