]> git.bitcoin.ninja Git - rust-lightning/blob - lightning/src/routing/scoring.rs
Merge pull request #1430 from vincenzopalazzo/macros/channel_reestablish_v2
[rust-lightning] / 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::chain::keysinterface::{KeysManager, KeysInterface};
24 //! # use lightning::util::logger::{Logger, Record};
25 //! # use secp256k1::key::PublicKey;
26 //! #
27 //! # struct FakeLogger {};
28 //! # impl Logger for FakeLogger {
29 //! #     fn log(&self, record: &Record) { unimplemented!() }
30 //! # }
31 //! # fn find_scored_route(payer: PublicKey, route_params: RouteParameters, network_graph: NetworkGraph) {
32 //! # let logger = FakeLogger {};
33 //! #
34 //! // Use the default channel penalties.
35 //! let params = ProbabilisticScoringParameters::default();
36 //! let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
37 //!
38 //! // Or use custom channel penalties.
39 //! let params = ProbabilisticScoringParameters {
40 //!     liquidity_penalty_multiplier_msat: 2 * 1000,
41 //!     ..ProbabilisticScoringParameters::default()
42 //! };
43 //! let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
44 //! # let random_seed_bytes = [42u8; 32];
45 //!
46 //! let route = find_route(&payer, &route_params, &network_graph, None, &logger, &scorer, &random_seed_bytes);
47 //! # }
48 //! ```
49 //!
50 //! # Note
51 //!
52 //! Persisting when built with feature `no-std` and restoring without it, or vice versa, uses
53 //! different types and thus is undefined.
54 //!
55 //! [`find_route`]: crate::routing::router::find_route
56
57 use ln::msgs::DecodeError;
58 use routing::network_graph::{NetworkGraph, NodeId};
59 use routing::router::RouteHop;
60 use util::ser::{Readable, ReadableArgs, Writeable, Writer};
61 use util::logger::Logger;
62
63 use prelude::*;
64 use core::fmt;
65 use core::cell::{RefCell, RefMut};
66 use core::ops::{Deref, DerefMut};
67 use core::time::Duration;
68 use io::{self, Read};
69 use sync::{Mutex, MutexGuard};
70
71 /// We define Score ever-so-slightly differently based on whether we are being built for C bindings
72 /// or not. For users, `LockableScore` must somehow be writeable to disk. For Rust users, this is
73 /// no problem - you move a `Score` that implements `Writeable` into a `Mutex`, lock it, and now
74 /// you have the original, concrete, `Score` type, which presumably implements `Writeable`.
75 ///
76 /// For C users, once you've moved the `Score` into a `LockableScore` all you have after locking it
77 /// is an opaque trait object with an opaque pointer with no type info. Users could take the unsafe
78 /// approach of blindly casting that opaque pointer to a concrete type and calling `Writeable` from
79 /// there, but other languages downstream of the C bindings (e.g. Java) can't even do that.
80 /// Instead, we really want `Score` and `LockableScore` to implement `Writeable` directly, which we
81 /// do here by defining `Score` differently for `cfg(c_bindings)`.
82 macro_rules! define_score { ($($supertrait: path)*) => {
83 /// An interface used to score payment channels for path finding.
84 ///
85 ///     Scoring is in terms of fees willing to be paid in order to avoid routing through a channel.
86 pub trait Score $(: $supertrait)* {
87         /// Returns the fee in msats willing to be paid to avoid routing `send_amt_msat` through the
88         /// given channel in the direction from `source` to `target`.
89         ///
90         /// The channel's capacity (less any other MPP parts that are also being considered for use in
91         /// the same payment) is given by `capacity_msat`. It may be determined from various sources
92         /// such as a chain data, network gossip, or invoice hints. For invoice hints, a capacity near
93         /// [`u64::max_value`] is given to indicate sufficient capacity for the invoice's full amount.
94         /// Thus, implementations should be overflow-safe.
95         fn channel_penalty_msat(&self, short_channel_id: u64, send_amt_msat: u64, capacity_msat: u64, source: &NodeId, target: &NodeId) -> u64;
96
97         /// Handles updating channel penalties after failing to route through a channel.
98         fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64);
99
100         /// Handles updating channel penalties after successfully routing along a path.
101         fn payment_path_successful(&mut self, path: &[&RouteHop]);
102 }
103
104 impl<S: Score, T: DerefMut<Target=S> $(+ $supertrait)*> Score for T {
105         fn channel_penalty_msat(&self, short_channel_id: u64, send_amt_msat: u64, capacity_msat: u64, source: &NodeId, target: &NodeId) -> u64 {
106                 self.deref().channel_penalty_msat(short_channel_id, send_amt_msat, capacity_msat, source, target)
107         }
108
109         fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
110                 self.deref_mut().payment_path_failed(path, short_channel_id)
111         }
112
113         fn payment_path_successful(&mut self, path: &[&RouteHop]) {
114                 self.deref_mut().payment_path_successful(path)
115         }
116 }
117 } }
118
119 #[cfg(c_bindings)]
120 define_score!(Writeable);
121 #[cfg(not(c_bindings))]
122 define_score!();
123
124 /// A scorer that is accessed under a lock.
125 ///
126 /// Needed so that calls to [`Score::channel_penalty_msat`] in [`find_route`] can be made while
127 /// having shared ownership of a scorer but without requiring internal locking in [`Score`]
128 /// implementations. Internal locking would be detrimental to route finding performance and could
129 /// result in [`Score::channel_penalty_msat`] returning a different value for the same channel.
130 ///
131 /// [`find_route`]: crate::routing::router::find_route
132 pub trait LockableScore<'a> {
133         /// The locked [`Score`] type.
134         type Locked: 'a + Score;
135
136         /// Returns the locked scorer.
137         fn lock(&'a self) -> Self::Locked;
138 }
139
140 /// Refers to a scorer that is accessible under lock and also writeable to disk
141 ///
142 /// We need this trait to be able to pass in a scorer to `lightning-background-processor` that will enable us to
143 /// use the Persister to persist it.
144 pub trait WriteableScore<'a>: LockableScore<'a> + Writeable {}
145
146 impl<'a, T> WriteableScore<'a> for T where T: LockableScore<'a> + Writeable {}
147
148 /// (C-not exported)
149 impl<'a, T: 'a + Score> LockableScore<'a> for Mutex<T> {
150         type Locked = MutexGuard<'a, T>;
151
152         fn lock(&'a self) -> MutexGuard<'a, T> {
153                 Mutex::lock(self).unwrap()
154         }
155 }
156
157 impl<'a, T: 'a + Score> LockableScore<'a> for RefCell<T> {
158         type Locked = RefMut<'a, T>;
159
160         fn lock(&'a self) -> RefMut<'a, T> {
161                 self.borrow_mut()
162         }
163 }
164
165 #[cfg(c_bindings)]
166 /// A concrete implementation of [`LockableScore`] which supports multi-threading.
167 pub struct MultiThreadedLockableScore<S: Score> {
168         score: Mutex<S>,
169 }
170 #[cfg(c_bindings)]
171 /// (C-not exported)
172 impl<'a, T: Score + 'a> LockableScore<'a> for MultiThreadedLockableScore<T> {
173         type Locked = MutexGuard<'a, T>;
174
175         fn lock(&'a self) -> MutexGuard<'a, T> {
176                 Mutex::lock(&self.score).unwrap()
177         }
178 }
179
180 #[cfg(c_bindings)]
181 impl<T: Score> MultiThreadedLockableScore<T> {
182         /// Creates a new [`MultiThreadedLockableScore`] given an underlying [`Score`].
183         pub fn new(score: T) -> Self {
184                 MultiThreadedLockableScore { score: Mutex::new(score) }
185         }
186 }
187
188 #[cfg(c_bindings)]
189 /// (C-not exported)
190 impl<'a, T: Writeable> Writeable for RefMut<'a, T> {
191         fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
192                 T::write(&**self, writer)
193         }
194 }
195
196 #[cfg(c_bindings)]
197 /// (C-not exported)
198 impl<'a, S: Writeable> Writeable for MutexGuard<'a, S> {
199         fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
200                 S::write(&**self, writer)
201         }
202 }
203
204 #[derive(Clone)]
205 /// [`Score`] implementation that uses a fixed penalty.
206 pub struct FixedPenaltyScorer {
207         penalty_msat: u64,
208 }
209
210 impl FixedPenaltyScorer {
211         /// Creates a new scorer using `penalty_msat`.
212         pub fn with_penalty(penalty_msat: u64) -> Self {
213                 Self { penalty_msat }
214         }
215 }
216
217 impl Score for FixedPenaltyScorer {
218         fn channel_penalty_msat(&self, _: u64, _: u64, _: u64, _: &NodeId, _: &NodeId) -> u64 {
219                 self.penalty_msat
220         }
221
222         fn payment_path_failed(&mut self, _path: &[&RouteHop], _short_channel_id: u64) {}
223
224         fn payment_path_successful(&mut self, _path: &[&RouteHop]) {}
225 }
226
227 impl Writeable for FixedPenaltyScorer {
228         #[inline]
229         fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
230                 write_tlv_fields!(w, {});
231                 Ok(())
232         }
233 }
234
235 impl ReadableArgs<u64> for FixedPenaltyScorer {
236         #[inline]
237         fn read<R: Read>(r: &mut R, penalty_msat: u64) -> Result<Self, DecodeError> {
238                 read_tlv_fields!(r, {});
239                 Ok(Self { penalty_msat })
240         }
241 }
242
243 /// [`Score`] implementation that provides reasonable default behavior.
244 ///
245 /// Used to apply a fixed penalty to each channel, thus avoiding long paths when shorter paths with
246 /// slightly higher fees are available. Will further penalize channels that fail to relay payments.
247 ///
248 /// See [module-level documentation] for usage and [`ScoringParameters`] for customization.
249 ///
250 /// # Note
251 ///
252 /// Mixing the `no-std` feature between serialization and deserialization results in undefined
253 /// behavior.
254 ///
255 /// [module-level documentation]: crate::routing::scoring
256 #[deprecated(
257         since = "0.0.105",
258         note = "ProbabilisticScorer should be used instead of Scorer.",
259 )]
260 pub type Scorer = ScorerUsingTime::<ConfiguredTime>;
261
262 #[cfg(not(feature = "no-std"))]
263 type ConfiguredTime = std::time::Instant;
264 #[cfg(feature = "no-std")]
265 type ConfiguredTime = time::Eternity;
266
267 // Note that ideally we'd hide ScorerUsingTime from public view by sealing it as well, but rustdoc
268 // doesn't handle this well - instead exposing a `Scorer` which has no trait implementation(s) or
269 // methods at all.
270
271 /// [`Score`] implementation.
272 ///
273 /// (C-not exported) generally all users should use the [`Scorer`] type alias.
274 pub struct ScorerUsingTime<T: Time> {
275         params: ScoringParameters,
276         // TODO: Remove entries of closed channels.
277         channel_failures: HashMap<u64, ChannelFailure<T>>,
278 }
279
280 #[derive(Clone)]
281 /// Parameters for configuring [`Scorer`].
282 pub struct ScoringParameters {
283         /// A fixed penalty in msats to apply to each channel.
284         ///
285         /// Default value: 500 msat
286         pub base_penalty_msat: u64,
287
288         /// A penalty in msats to apply to a channel upon failing to relay a payment.
289         ///
290         /// This accumulates for each failure but may be reduced over time based on
291         /// [`failure_penalty_half_life`] or when successfully routing through a channel.
292         ///
293         /// Default value: 1,024,000 msat
294         ///
295         /// [`failure_penalty_half_life`]: Self::failure_penalty_half_life
296         pub failure_penalty_msat: u64,
297
298         /// When the amount being sent over a channel is this many 1024ths of the total channel
299         /// capacity, we begin applying [`overuse_penalty_msat_per_1024th`].
300         ///
301         /// Default value: 128 1024ths (i.e. begin penalizing when an HTLC uses 1/8th of a channel)
302         ///
303         /// [`overuse_penalty_msat_per_1024th`]: Self::overuse_penalty_msat_per_1024th
304         pub overuse_penalty_start_1024th: u16,
305
306         /// A penalty applied, per whole 1024ths of the channel capacity which the amount being sent
307         /// over the channel exceeds [`overuse_penalty_start_1024th`] by.
308         ///
309         /// Default value: 20 msat (i.e. 2560 msat penalty to use 1/4th of a channel, 7680 msat penalty
310         ///                to use half a channel, and 12,560 msat penalty to use 3/4ths of a channel)
311         ///
312         /// [`overuse_penalty_start_1024th`]: Self::overuse_penalty_start_1024th
313         pub overuse_penalty_msat_per_1024th: u64,
314
315         /// The time required to elapse before any accumulated [`failure_penalty_msat`] penalties are
316         /// cut in half.
317         ///
318         /// Successfully routing through a channel will immediately cut the penalty in half as well.
319         ///
320         /// Default value: 1 hour
321         ///
322         /// # Note
323         ///
324         /// When built with the `no-std` feature, time will never elapse. Therefore, this penalty will
325         /// never decay.
326         ///
327         /// [`failure_penalty_msat`]: Self::failure_penalty_msat
328         pub failure_penalty_half_life: Duration,
329 }
330
331 impl_writeable_tlv_based!(ScoringParameters, {
332         (0, base_penalty_msat, required),
333         (1, overuse_penalty_start_1024th, (default_value, 128)),
334         (2, failure_penalty_msat, required),
335         (3, overuse_penalty_msat_per_1024th, (default_value, 20)),
336         (4, failure_penalty_half_life, required),
337 });
338
339 /// Accounting for penalties against a channel for failing to relay any payments.
340 ///
341 /// Penalties decay over time, though accumulate as more failures occur.
342 struct ChannelFailure<T: Time> {
343         /// Accumulated penalty in msats for the channel as of `last_updated`.
344         undecayed_penalty_msat: u64,
345
346         /// Last time the channel either failed to route or successfully routed a payment. Used to decay
347         /// `undecayed_penalty_msat`.
348         last_updated: T,
349 }
350
351 impl<T: Time> ScorerUsingTime<T> {
352         /// Creates a new scorer using the given scoring parameters.
353         pub fn new(params: ScoringParameters) -> Self {
354                 Self {
355                         params,
356                         channel_failures: HashMap::new(),
357                 }
358         }
359 }
360
361 impl<T: Time> ChannelFailure<T> {
362         fn new(failure_penalty_msat: u64) -> Self {
363                 Self {
364                         undecayed_penalty_msat: failure_penalty_msat,
365                         last_updated: T::now(),
366                 }
367         }
368
369         fn add_penalty(&mut self, failure_penalty_msat: u64, half_life: Duration) {
370                 self.undecayed_penalty_msat = self.decayed_penalty_msat(half_life) + failure_penalty_msat;
371                 self.last_updated = T::now();
372         }
373
374         fn reduce_penalty(&mut self, half_life: Duration) {
375                 self.undecayed_penalty_msat = self.decayed_penalty_msat(half_life) >> 1;
376                 self.last_updated = T::now();
377         }
378
379         fn decayed_penalty_msat(&self, half_life: Duration) -> u64 {
380                 self.last_updated.elapsed().as_secs()
381                         .checked_div(half_life.as_secs())
382                         .and_then(|decays| self.undecayed_penalty_msat.checked_shr(decays as u32))
383                         .unwrap_or(0)
384         }
385 }
386
387 impl<T: Time> Default for ScorerUsingTime<T> {
388         fn default() -> Self {
389                 Self::new(ScoringParameters::default())
390         }
391 }
392
393 impl Default for ScoringParameters {
394         fn default() -> Self {
395                 Self {
396                         base_penalty_msat: 500,
397                         failure_penalty_msat: 1024 * 1000,
398                         failure_penalty_half_life: Duration::from_secs(3600),
399                         overuse_penalty_start_1024th: 1024 / 8,
400                         overuse_penalty_msat_per_1024th: 20,
401                 }
402         }
403 }
404
405 impl<T: Time> Score for ScorerUsingTime<T> {
406         fn channel_penalty_msat(
407                 &self, short_channel_id: u64, send_amt_msat: u64, capacity_msat: u64, _source: &NodeId, _target: &NodeId
408         ) -> u64 {
409                 let failure_penalty_msat = self.channel_failures
410                         .get(&short_channel_id)
411                         .map_or(0, |value| value.decayed_penalty_msat(self.params.failure_penalty_half_life));
412
413                 let mut penalty_msat = self.params.base_penalty_msat + failure_penalty_msat;
414                 let send_1024ths = send_amt_msat.checked_mul(1024).unwrap_or(u64::max_value()) / capacity_msat;
415                 if send_1024ths > self.params.overuse_penalty_start_1024th as u64 {
416                         penalty_msat = penalty_msat.checked_add(
417                                         (send_1024ths - self.params.overuse_penalty_start_1024th as u64)
418                                         .checked_mul(self.params.overuse_penalty_msat_per_1024th).unwrap_or(u64::max_value()))
419                                 .unwrap_or(u64::max_value());
420                 }
421
422                 penalty_msat
423         }
424
425         fn payment_path_failed(&mut self, _path: &[&RouteHop], short_channel_id: u64) {
426                 let failure_penalty_msat = self.params.failure_penalty_msat;
427                 let half_life = self.params.failure_penalty_half_life;
428                 self.channel_failures
429                         .entry(short_channel_id)
430                         .and_modify(|failure| failure.add_penalty(failure_penalty_msat, half_life))
431                         .or_insert_with(|| ChannelFailure::new(failure_penalty_msat));
432         }
433
434         fn payment_path_successful(&mut self, path: &[&RouteHop]) {
435                 let half_life = self.params.failure_penalty_half_life;
436                 for hop in path.iter() {
437                         self.channel_failures
438                                 .entry(hop.short_channel_id)
439                                 .and_modify(|failure| failure.reduce_penalty(half_life));
440                 }
441         }
442 }
443
444 impl<T: Time> Writeable for ScorerUsingTime<T> {
445         #[inline]
446         fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
447                 self.params.write(w)?;
448                 self.channel_failures.write(w)?;
449                 write_tlv_fields!(w, {});
450                 Ok(())
451         }
452 }
453
454 impl<T: Time> Readable for ScorerUsingTime<T> {
455         #[inline]
456         fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
457                 let res = Ok(Self {
458                         params: Readable::read(r)?,
459                         channel_failures: Readable::read(r)?,
460                 });
461                 read_tlv_fields!(r, {});
462                 res
463         }
464 }
465
466 impl<T: Time> Writeable for ChannelFailure<T> {
467         #[inline]
468         fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
469                 let duration_since_epoch = T::duration_since_epoch() - self.last_updated.elapsed();
470                 write_tlv_fields!(w, {
471                         (0, self.undecayed_penalty_msat, required),
472                         (2, duration_since_epoch, required),
473                 });
474                 Ok(())
475         }
476 }
477
478 impl<T: Time> Readable for ChannelFailure<T> {
479         #[inline]
480         fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
481                 let mut undecayed_penalty_msat = 0;
482                 let mut duration_since_epoch = Duration::from_secs(0);
483                 read_tlv_fields!(r, {
484                         (0, undecayed_penalty_msat, required),
485                         (2, duration_since_epoch, required),
486                 });
487                 Ok(Self {
488                         undecayed_penalty_msat,
489                         last_updated: T::now() - (T::duration_since_epoch() - duration_since_epoch),
490                 })
491         }
492 }
493
494 /// [`Score`] implementation using channel success probability distributions.
495 ///
496 /// Based on *Optimally Reliable & Cheap Payment Flows on the Lightning Network* by Rene Pickhardt
497 /// and Stefan Richter [[1]]. Given the uncertainty of channel liquidity balances, probability
498 /// distributions are defined based on knowledge learned from successful and unsuccessful attempts.
499 /// Then the negative `log10` of the success probability is used to determine the cost of routing a
500 /// specific HTLC amount through a channel.
501 ///
502 /// Knowledge about channel liquidity balances takes the form of upper and lower bounds on the
503 /// possible liquidity. Certainty of the bounds is decreased over time using a decay function. See
504 /// [`ProbabilisticScoringParameters`] for details.
505 ///
506 /// Since the scorer aims to learn the current channel liquidity balances, it works best for nodes
507 /// with high payment volume or that actively probe the [`NetworkGraph`]. Nodes with low payment
508 /// volume are more likely to experience failed payment paths, which would need to be retried.
509 ///
510 /// # Note
511 ///
512 /// Mixing the `no-std` feature between serialization and deserialization results in undefined
513 /// behavior.
514 ///
515 /// [1]: https://arxiv.org/abs/2107.05322
516 pub type ProbabilisticScorer<G, L> = ProbabilisticScorerUsingTime::<G, L, ConfiguredTime>;
517
518 /// Probabilistic [`Score`] implementation.
519 ///
520 /// (C-not exported) generally all users should use the [`ProbabilisticScorer`] type alias.
521 pub struct ProbabilisticScorerUsingTime<G: Deref<Target = NetworkGraph>, L: Deref, T: Time> where L::Target: Logger {
522         params: ProbabilisticScoringParameters,
523         network_graph: G,
524         logger: L,
525         // TODO: Remove entries of closed channels.
526         channel_liquidities: HashMap<u64, ChannelLiquidity<T>>,
527 }
528
529 /// Parameters for configuring [`ProbabilisticScorer`].
530 ///
531 /// Used to configure base, liquidity, and amount penalties, the sum of which comprises the channel
532 /// penalty (i.e., the amount in msats willing to be paid to avoid routing through the channel).
533 #[derive(Clone, Copy)]
534 pub struct ProbabilisticScoringParameters {
535         /// A fixed penalty in msats to apply to each channel.
536         ///
537         /// Default value: 500 msat
538         pub base_penalty_msat: u64,
539
540         /// A multiplier used in conjunction with the negative `log10` of the channel's success
541         /// probability for a payment to determine the liquidity penalty.
542         ///
543         /// The penalty is based in part on the knowledge learned from prior successful and unsuccessful
544         /// payments. This knowledge is decayed over time based on [`liquidity_offset_half_life`]. The
545         /// penalty is effectively limited to `2 * liquidity_penalty_multiplier_msat` (corresponding to
546         /// lower bounding the success probability to `0.01`) when the amount falls within the
547         /// uncertainty bounds of the channel liquidity balance. Amounts above the upper bound will
548         /// result in a `u64::max_value` penalty, however.
549         ///
550         /// Default value: 40,000 msat
551         ///
552         /// [`liquidity_offset_half_life`]: Self::liquidity_offset_half_life
553         pub liquidity_penalty_multiplier_msat: u64,
554
555         /// The time required to elapse before any knowledge learned about channel liquidity balances is
556         /// cut in half.
557         ///
558         /// The bounds are defined in terms of offsets and are initially zero. Increasing the offsets
559         /// gives tighter bounds on the channel liquidity balance. Thus, halving the offsets decreases
560         /// the certainty of the channel liquidity balance.
561         ///
562         /// Default value: 1 hour
563         ///
564         /// # Note
565         ///
566         /// When built with the `no-std` feature, time will never elapse. Therefore, the channel
567         /// liquidity knowledge will never decay except when the bounds cross.
568         pub liquidity_offset_half_life: Duration,
569
570         /// A multiplier used in conjunction with a payment amount and the negative `log10` of the
571         /// channel's success probability for the payment to determine the amount penalty.
572         ///
573         /// The purpose of the amount penalty is to avoid having fees dominate the channel cost (i.e.,
574         /// fees plus penalty) for large payments. The penalty is computed as the product of this
575         /// multiplier and `2^20`ths of the payment amount, weighted by the negative `log10` of the
576         /// success probability.
577         ///
578         /// `-log10(success_probability) * amount_penalty_multiplier_msat * amount_msat / 2^20`
579         ///
580         /// In practice, this means for 0.1 success probability (`-log10(0.1) == 1`) each `2^20`th of
581         /// the amount will result in a penalty of the multiplier. And, as the success probability
582         /// decreases, the negative `log10` weighting will increase dramatically. For higher success
583         /// probabilities, the multiplier will have a decreasing effect as the negative `log10` will
584         /// fall below `1`.
585         ///
586         /// Default value: 256 msat
587         pub amount_penalty_multiplier_msat: u64,
588 }
589
590 /// Accounting for channel liquidity balance uncertainty.
591 ///
592 /// Direction is defined in terms of [`NodeId`] partial ordering, where the source node is the
593 /// first node in the ordering of the channel's counterparties. Thus, swapping the two liquidity
594 /// offset fields gives the opposite direction.
595 struct ChannelLiquidity<T: Time> {
596         /// Lower channel liquidity bound in terms of an offset from zero.
597         min_liquidity_offset_msat: u64,
598
599         /// Upper channel liquidity bound in terms of an offset from the effective capacity.
600         max_liquidity_offset_msat: u64,
601
602         /// Time when the liquidity bounds were last modified.
603         last_updated: T,
604 }
605
606 /// A snapshot of [`ChannelLiquidity`] in one direction assuming a certain channel capacity and
607 /// decayed with a given half life.
608 struct DirectedChannelLiquidity<L: Deref<Target = u64>, T: Time, U: Deref<Target = T>> {
609         min_liquidity_offset_msat: L,
610         max_liquidity_offset_msat: L,
611         capacity_msat: u64,
612         last_updated: U,
613         now: T,
614         half_life: Duration,
615 }
616
617 impl<G: Deref<Target = NetworkGraph>, L: Deref, T: Time> ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
618         /// Creates a new scorer using the given scoring parameters for sending payments from a node
619         /// through a network graph.
620         pub fn new(params: ProbabilisticScoringParameters, network_graph: G, logger: L) -> Self {
621                 Self {
622                         params,
623                         network_graph,
624                         logger,
625                         channel_liquidities: HashMap::new(),
626                 }
627         }
628
629         #[cfg(test)]
630         fn with_channel(mut self, short_channel_id: u64, liquidity: ChannelLiquidity<T>) -> Self {
631                 assert!(self.channel_liquidities.insert(short_channel_id, liquidity).is_none());
632                 self
633         }
634
635         /// Dump the contents of this scorer into the configured logger.
636         ///
637         /// Note that this writes roughly one line per channel for which we have a liquidity estimate,
638         /// which may be a substantial amount of log output.
639         pub fn debug_log_liquidity_stats(&self) {
640                 let graph = self.network_graph.read_only();
641                 for (scid, liq) in self.channel_liquidities.iter() {
642                         if let Some(chan_debug) = graph.channels().get(scid) {
643                                 let log_direction = |source, target| {
644                                         if let Some((directed_info, _)) = chan_debug.as_directed_to(target) {
645                                                 let amt = directed_info.effective_capacity().as_msat();
646                                                 let dir_liq = liq.as_directed(source, target, amt, self.params.liquidity_offset_half_life);
647                                                 log_debug!(self.logger, "Liquidity from {:?} to {:?} via {} is in the range ({}, {})",
648                                                         source, target, scid, dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat());
649                                         } else {
650                                                 log_debug!(self.logger, "No amount known for SCID {} from {:?} to {:?}", scid, source, target);
651                                         }
652                                 };
653
654                                 log_direction(&chan_debug.node_one, &chan_debug.node_two);
655                                 log_direction(&chan_debug.node_two, &chan_debug.node_one);
656                         } else {
657                                 log_debug!(self.logger, "No network graph entry for SCID {}", scid);
658                         }
659                 }
660         }
661 }
662
663 impl ProbabilisticScoringParameters {
664         #[cfg(test)]
665         fn zero_penalty() -> Self {
666                 Self {
667                         base_penalty_msat: 0,
668                         liquidity_penalty_multiplier_msat: 0,
669                         liquidity_offset_half_life: Duration::from_secs(3600),
670                         amount_penalty_multiplier_msat: 0,
671                 }
672         }
673 }
674
675 impl Default for ProbabilisticScoringParameters {
676         fn default() -> Self {
677                 Self {
678                         base_penalty_msat: 500,
679                         liquidity_penalty_multiplier_msat: 40_000,
680                         liquidity_offset_half_life: Duration::from_secs(3600),
681                         amount_penalty_multiplier_msat: 256,
682                 }
683         }
684 }
685
686 impl<T: Time> ChannelLiquidity<T> {
687         #[inline]
688         fn new() -> Self {
689                 Self {
690                         min_liquidity_offset_msat: 0,
691                         max_liquidity_offset_msat: 0,
692                         last_updated: T::now(),
693                 }
694         }
695
696         /// Returns a view of the channel liquidity directed from `source` to `target` assuming
697         /// `capacity_msat`.
698         fn as_directed(
699                 &self, source: &NodeId, target: &NodeId, capacity_msat: u64, half_life: Duration
700         ) -> DirectedChannelLiquidity<&u64, T, &T> {
701                 let (min_liquidity_offset_msat, max_liquidity_offset_msat) = if source < target {
702                         (&self.min_liquidity_offset_msat, &self.max_liquidity_offset_msat)
703                 } else {
704                         (&self.max_liquidity_offset_msat, &self.min_liquidity_offset_msat)
705                 };
706
707                 DirectedChannelLiquidity {
708                         min_liquidity_offset_msat,
709                         max_liquidity_offset_msat,
710                         capacity_msat,
711                         last_updated: &self.last_updated,
712                         now: T::now(),
713                         half_life,
714                 }
715         }
716
717         /// Returns a mutable view of the channel liquidity directed from `source` to `target` assuming
718         /// `capacity_msat`.
719         fn as_directed_mut(
720                 &mut self, source: &NodeId, target: &NodeId, capacity_msat: u64, half_life: Duration
721         ) -> DirectedChannelLiquidity<&mut u64, T, &mut T> {
722                 let (min_liquidity_offset_msat, max_liquidity_offset_msat) = if source < target {
723                         (&mut self.min_liquidity_offset_msat, &mut self.max_liquidity_offset_msat)
724                 } else {
725                         (&mut self.max_liquidity_offset_msat, &mut self.min_liquidity_offset_msat)
726                 };
727
728                 DirectedChannelLiquidity {
729                         min_liquidity_offset_msat,
730                         max_liquidity_offset_msat,
731                         capacity_msat,
732                         last_updated: &mut self.last_updated,
733                         now: T::now(),
734                         half_life,
735                 }
736         }
737 }
738
739 /// Bounds `-log10` to avoid excessive liquidity penalties for payments with low success
740 /// probabilities.
741 const NEGATIVE_LOG10_UPPER_BOUND: u64 = 2;
742
743 /// The rough cutoff at which our precision falls off and we should stop bothering to try to log a
744 /// ratio, as X in 1/X.
745 const PRECISION_LOWER_BOUND_DENOMINATOR: u64 = approx::LOWER_BITS_BOUND;
746
747 /// The divisor used when computing the amount penalty.
748 const AMOUNT_PENALTY_DIVISOR: u64 = 1 << 20;
749
750 impl<L: Deref<Target = u64>, T: Time, U: Deref<Target = T>> DirectedChannelLiquidity<L, T, U> {
751         /// Returns a penalty for routing the given HTLC `amount_msat` through the channel in this
752         /// direction.
753         fn penalty_msat(&self, amount_msat: u64, params: ProbabilisticScoringParameters) -> u64 {
754                 let max_liquidity_msat = self.max_liquidity_msat();
755                 let min_liquidity_msat = core::cmp::min(self.min_liquidity_msat(), max_liquidity_msat);
756                 if amount_msat <= min_liquidity_msat {
757                         0
758                 } else if amount_msat >= max_liquidity_msat {
759                         if amount_msat > max_liquidity_msat {
760                                 u64::max_value()
761                         } else if max_liquidity_msat != self.capacity_msat {
762                                 // Avoid using the failed channel on retry.
763                                 u64::max_value()
764                         } else {
765                                 // Equivalent to hitting the else clause below with the amount equal to the
766                                 // effective capacity and without any certainty on the liquidity upper bound.
767                                 let negative_log10_times_2048 = NEGATIVE_LOG10_UPPER_BOUND * 2048;
768                                 self.combined_penalty_msat(amount_msat, negative_log10_times_2048, params)
769                         }
770                 } else {
771                         let numerator = (max_liquidity_msat - amount_msat).saturating_add(1);
772                         let denominator = (max_liquidity_msat - min_liquidity_msat).saturating_add(1);
773                         if amount_msat - min_liquidity_msat < denominator / PRECISION_LOWER_BOUND_DENOMINATOR {
774                                 // If the failure probability is < 1.5625% (as 1 - numerator/denominator < 1/64),
775                                 // don't bother trying to use the log approximation as it gets too noisy to be
776                                 // particularly helpful, instead just round down to 0 and return the base penalty.
777                                 params.base_penalty_msat
778                         } else {
779                                 let negative_log10_times_2048 =
780                                         approx::negative_log10_times_2048(numerator, denominator);
781                                 self.combined_penalty_msat(amount_msat, negative_log10_times_2048, params)
782                         }
783                 }
784         }
785
786         /// Computes the liquidity and amount penalties and adds them to the base penalty.
787         #[inline(always)]
788         fn combined_penalty_msat(
789                 &self, amount_msat: u64, negative_log10_times_2048: u64,
790                 params: ProbabilisticScoringParameters
791         ) -> u64 {
792                 let liquidity_penalty_msat = {
793                         // Upper bound the liquidity penalty to ensure some channel is selected.
794                         let multiplier_msat = params.liquidity_penalty_multiplier_msat;
795                         let max_penalty_msat = multiplier_msat.saturating_mul(NEGATIVE_LOG10_UPPER_BOUND);
796                         (negative_log10_times_2048.saturating_mul(multiplier_msat) / 2048).min(max_penalty_msat)
797                 };
798                 let amount_penalty_msat = negative_log10_times_2048
799                         .saturating_mul(params.amount_penalty_multiplier_msat)
800                         .saturating_mul(amount_msat) / 2048 / AMOUNT_PENALTY_DIVISOR;
801
802                 params.base_penalty_msat
803                         .saturating_add(liquidity_penalty_msat)
804                         .saturating_add(amount_penalty_msat)
805         }
806
807         /// Returns the lower bound of the channel liquidity balance in this direction.
808         fn min_liquidity_msat(&self) -> u64 {
809                 self.decayed_offset_msat(*self.min_liquidity_offset_msat)
810         }
811
812         /// Returns the upper bound of the channel liquidity balance in this direction.
813         fn max_liquidity_msat(&self) -> u64 {
814                 self.capacity_msat
815                         .checked_sub(self.decayed_offset_msat(*self.max_liquidity_offset_msat))
816                         .unwrap_or(0)
817         }
818
819         fn decayed_offset_msat(&self, offset_msat: u64) -> u64 {
820                 self.now.duration_since(*self.last_updated).as_secs()
821                         .checked_div(self.half_life.as_secs())
822                         .and_then(|decays| offset_msat.checked_shr(decays as u32))
823                         .unwrap_or(0)
824         }
825 }
826
827 impl<L: DerefMut<Target = u64>, T: Time, U: DerefMut<Target = T>> DirectedChannelLiquidity<L, T, U> {
828         /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat`.
829         fn failed_at_channel<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
830                 if amount_msat < self.max_liquidity_msat() {
831                         log_debug!(logger, "Setting max liquidity of {} to {}", chan_descr, amount_msat);
832                         self.set_max_liquidity_msat(amount_msat);
833                 } else {
834                         log_trace!(logger, "Max liquidity of {} already more than {}", chan_descr, amount_msat);
835                 }
836         }
837
838         /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat` downstream.
839         fn failed_downstream<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
840                 if amount_msat > self.min_liquidity_msat() {
841                         log_debug!(logger, "Setting min liquidity of {} to {}", chan_descr, amount_msat);
842                         self.set_min_liquidity_msat(amount_msat);
843                 } else {
844                         log_trace!(logger, "Min liquidity of {} already less than {}", chan_descr, amount_msat);
845                 }
846         }
847
848         /// Adjusts the channel liquidity balance bounds when successfully routing `amount_msat`.
849         fn successful<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
850                 let max_liquidity_msat = self.max_liquidity_msat().checked_sub(amount_msat).unwrap_or(0);
851                 log_debug!(logger, "Subtracting {} from max liquidity of {} (setting it to {})", amount_msat, chan_descr, max_liquidity_msat);
852                 self.set_max_liquidity_msat(max_liquidity_msat);
853         }
854
855         /// Adjusts the lower bound of the channel liquidity balance in this direction.
856         fn set_min_liquidity_msat(&mut self, amount_msat: u64) {
857                 *self.min_liquidity_offset_msat = amount_msat;
858                 *self.max_liquidity_offset_msat = if amount_msat > self.max_liquidity_msat() {
859                         0
860                 } else {
861                         self.decayed_offset_msat(*self.max_liquidity_offset_msat)
862                 };
863                 *self.last_updated = self.now;
864         }
865
866         /// Adjusts the upper bound of the channel liquidity balance in this direction.
867         fn set_max_liquidity_msat(&mut self, amount_msat: u64) {
868                 *self.max_liquidity_offset_msat = self.capacity_msat.checked_sub(amount_msat).unwrap_or(0);
869                 *self.min_liquidity_offset_msat = if amount_msat < self.min_liquidity_msat() {
870                         0
871                 } else {
872                         self.decayed_offset_msat(*self.min_liquidity_offset_msat)
873                 };
874                 *self.last_updated = self.now;
875         }
876 }
877
878 impl<G: Deref<Target = NetworkGraph>, L: Deref, T: Time> Score for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
879         fn channel_penalty_msat(
880                 &self, short_channel_id: u64, amount_msat: u64, capacity_msat: u64, source: &NodeId,
881                 target: &NodeId
882         ) -> u64 {
883                 let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
884                 self.channel_liquidities
885                         .get(&short_channel_id)
886                         .unwrap_or(&ChannelLiquidity::new())
887                         .as_directed(source, target, capacity_msat, liquidity_offset_half_life)
888                         .penalty_msat(amount_msat, self.params)
889         }
890
891         fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
892                 let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
893                 let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
894                 log_trace!(self.logger, "Scoring path through to SCID {} as having failed at {} msat", short_channel_id, amount_msat);
895                 let network_graph = self.network_graph.read_only();
896                 for (hop_idx, hop) in path.iter().enumerate() {
897                         let target = NodeId::from_pubkey(&hop.pubkey);
898                         let channel_directed_from_source = network_graph.channels()
899                                 .get(&hop.short_channel_id)
900                                 .and_then(|channel| channel.as_directed_to(&target));
901
902                         if hop.short_channel_id == short_channel_id && hop_idx == 0 {
903                                 log_warn!(self.logger, "Payment failed at the first hop - we do not attempt to learn channel info in such cases as we can directly observe local state.\n\tBecause we know the local state, we should generally not see failures here - this may be an indication that your channel peer on channel {} is broken and you may wish to close the channel.", hop.short_channel_id);
904                         }
905
906                         // Only score announced channels.
907                         if let Some((channel, source)) = channel_directed_from_source {
908                                 let capacity_msat = channel.effective_capacity().as_msat();
909                                 if hop.short_channel_id == short_channel_id {
910                                         self.channel_liquidities
911                                                 .entry(hop.short_channel_id)
912                                                 .or_insert_with(ChannelLiquidity::new)
913                                                 .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life)
914                                                 .failed_at_channel(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
915                                         break;
916                                 }
917
918                                 self.channel_liquidities
919                                         .entry(hop.short_channel_id)
920                                         .or_insert_with(ChannelLiquidity::new)
921                                         .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life)
922                                         .failed_downstream(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
923                         } else {
924                                 log_debug!(self.logger, "Not able to penalize channel with SCID {} as we do not have graph info for it (likely a route-hint last-hop).",
925                                         hop.short_channel_id);
926                         }
927                 }
928         }
929
930         fn payment_path_successful(&mut self, path: &[&RouteHop]) {
931                 let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
932                 let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
933                 log_trace!(self.logger, "Scoring path through SCID {} as having succeeded at {} msat.",
934                         path.split_last().map(|(hop, _)| hop.short_channel_id).unwrap_or(0), amount_msat);
935                 let network_graph = self.network_graph.read_only();
936                 for hop in path {
937                         let target = NodeId::from_pubkey(&hop.pubkey);
938                         let channel_directed_from_source = network_graph.channels()
939                                 .get(&hop.short_channel_id)
940                                 .and_then(|channel| channel.as_directed_to(&target));
941
942                         // Only score announced channels.
943                         if let Some((channel, source)) = channel_directed_from_source {
944                                 let capacity_msat = channel.effective_capacity().as_msat();
945                                 self.channel_liquidities
946                                         .entry(hop.short_channel_id)
947                                         .or_insert_with(ChannelLiquidity::new)
948                                         .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life)
949                                         .successful(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
950                         } else {
951                                 log_debug!(self.logger, "Not able to learn for channel with SCID {} as we do not have graph info for it (likely a route-hint last-hop).",
952                                         hop.short_channel_id);
953                         }
954                 }
955         }
956 }
957
958 mod approx {
959         const BITS: u32 = 64;
960         const HIGHEST_BIT: u32 = BITS - 1;
961         const LOWER_BITS: u32 = 6;
962         pub(super) const LOWER_BITS_BOUND: u64 = 1 << LOWER_BITS;
963         const LOWER_BITMASK: u64 = (1 << LOWER_BITS) - 1;
964
965         /// Look-up table for `log10(x) * 2048` where row `i` is used for each `x` having `i` as the
966         /// most significant bit. The next 4 bits of `x`, if applicable, are used for the second index.
967         const LOG10_TIMES_2048: [[u16; (LOWER_BITS_BOUND) as usize]; BITS as usize] = [
968                 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
969                         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
970                         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
971                         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
972                 [617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
973                         617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
974                         977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977,
975                         977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977],
976                 [1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233,
977                         1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431,
978                         1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594,
979                         1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731],
980                 [1850, 1850, 1850, 1850, 1850, 1850, 1850, 1850, 1954, 1954, 1954, 1954, 1954, 1954, 1954, 1954,
981                         2048, 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2133, 2133, 2133, 2133, 2133, 2133, 2133, 2133,
982                         2210, 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2281, 2281, 2281, 2281, 2281, 2281, 2281, 2281,
983                         2347, 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2409, 2409, 2409, 2409, 2409, 2409, 2409, 2409],
984                 [2466, 2466, 2466, 2466, 2520, 2520, 2520, 2520, 2571, 2571, 2571, 2571, 2619, 2619, 2619, 2619,
985                         2665, 2665, 2665, 2665, 2708, 2708, 2708, 2708, 2749, 2749, 2749, 2749, 2789, 2789, 2789, 2789,
986                         2827, 2827, 2827, 2827, 2863, 2863, 2863, 2863, 2898, 2898, 2898, 2898, 2931, 2931, 2931, 2931,
987                         2964, 2964, 2964, 2964, 2995, 2995, 2995, 2995, 3025, 3025, 3025, 3025, 3054, 3054, 3054, 3054],
988                 [3083, 3083, 3110, 3110, 3136, 3136, 3162, 3162, 3187, 3187, 3212, 3212, 3235, 3235, 3259, 3259,
989                         3281, 3281, 3303, 3303, 3324, 3324, 3345, 3345, 3366, 3366, 3386, 3386, 3405, 3405, 3424, 3424,
990                         3443, 3443, 3462, 3462, 3479, 3479, 3497, 3497, 3514, 3514, 3531, 3531, 3548, 3548, 3564, 3564,
991                         3580, 3580, 3596, 3596, 3612, 3612, 3627, 3627, 3642, 3642, 3656, 3656, 3671, 3671, 3685, 3685],
992                 [3699, 3713, 3726, 3740, 3753, 3766, 3779, 3791, 3804, 3816, 3828, 3840, 3852, 3864, 3875, 3886,
993                         3898, 3909, 3919, 3930, 3941, 3951, 3962, 3972, 3982, 3992, 4002, 4012, 4022, 4031, 4041, 4050,
994                         4060, 4069, 4078, 4087, 4096, 4105, 4114, 4122, 4131, 4139, 4148, 4156, 4164, 4173, 4181, 4189,
995                         4197, 4205, 4213, 4220, 4228, 4236, 4243, 4251, 4258, 4266, 4273, 4280, 4287, 4294, 4302, 4309],
996                 [4316, 4329, 4343, 4356, 4369, 4382, 4395, 4408, 4420, 4433, 4445, 4457, 4468, 4480, 4492, 4503,
997                         4514, 4525, 4536, 4547, 4557, 4568, 4578, 4589, 4599, 4609, 4619, 4629, 4638, 4648, 4657, 4667,
998                         4676, 4685, 4695, 4704, 4713, 4721, 4730, 4739, 4747, 4756, 4764, 4773, 4781, 4789, 4797, 4805,
999                         4813, 4821, 4829, 4837, 4845, 4852, 4860, 4867, 4875, 4882, 4889, 4897, 4904, 4911, 4918, 4925],
1000                 [4932, 4946, 4959, 4973, 4986, 4999, 5012, 5024, 5037, 5049, 5061, 5073, 5085, 5097, 5108, 5119,
1001                         5131, 5142, 5153, 5163, 5174, 5184, 5195, 5205, 5215, 5225, 5235, 5245, 5255, 5264, 5274, 5283,
1002                         5293, 5302, 5311, 5320, 5329, 5338, 5347, 5355, 5364, 5372, 5381, 5389, 5397, 5406, 5414, 5422,
1003                         5430, 5438, 5446, 5453, 5461, 5469, 5476, 5484, 5491, 5499, 5506, 5513, 5520, 5527, 5535, 5542],
1004                 [5549, 5562, 5576, 5589, 5603, 5615, 5628, 5641, 5653, 5666, 5678, 5690, 5701, 5713, 5725, 5736,
1005                         5747, 5758, 5769, 5780, 5790, 5801, 5811, 5822, 5832, 5842, 5852, 5862, 5871, 5881, 5890, 5900,
1006                         5909, 5918, 5928, 5937, 5946, 5954, 5963, 5972, 5980, 5989, 5997, 6006, 6014, 6022, 6030, 6038,
1007                         6046, 6054, 6062, 6070, 6078, 6085, 6093, 6100, 6108, 6115, 6122, 6130, 6137, 6144, 6151, 6158],
1008                 [6165, 6179, 6192, 6206, 6219, 6232, 6245, 6257, 6270, 6282, 6294, 6306, 6318, 6330, 6341, 6352,
1009                         6364, 6375, 6386, 6396, 6407, 6417, 6428, 6438, 6448, 6458, 6468, 6478, 6488, 6497, 6507, 6516,
1010                         6526, 6535, 6544, 6553, 6562, 6571, 6580, 6588, 6597, 6605, 6614, 6622, 6630, 6639, 6647, 6655,
1011                         6663, 6671, 6679, 6686, 6694, 6702, 6709, 6717, 6724, 6732, 6739, 6746, 6753, 6761, 6768, 6775],
1012                 [6782, 6795, 6809, 6822, 6836, 6849, 6861, 6874, 6886, 6899, 6911, 6923, 6934, 6946, 6958, 6969,
1013                         6980, 6991, 7002, 7013, 7023, 7034, 7044, 7055, 7065, 7075, 7085, 7095, 7104, 7114, 7124, 7133,
1014                         7142, 7151, 7161, 7170, 7179, 7187, 7196, 7205, 7213, 7222, 7230, 7239, 7247, 7255, 7263, 7271,
1015                         7279, 7287, 7295, 7303, 7311, 7318, 7326, 7333, 7341, 7348, 7355, 7363, 7370, 7377, 7384, 7391],
1016                 [7398, 7412, 7425, 7439, 7452, 7465, 7478, 7490, 7503, 7515, 7527, 7539, 7551, 7563, 7574, 7585,
1017                         7597, 7608, 7619, 7629, 7640, 7651, 7661, 7671, 7681, 7691, 7701, 7711, 7721, 7731, 7740, 7749,
1018                         7759, 7768, 7777, 7786, 7795, 7804, 7813, 7821, 7830, 7838, 7847, 7855, 7864, 7872, 7880, 7888,
1019                         7896, 7904, 7912, 7919, 7927, 7935, 7942, 7950, 7957, 7965, 7972, 7979, 7986, 7994, 8001, 8008],
1020                 [8015, 8028, 8042, 8055, 8069, 8082, 8094, 8107, 8119, 8132, 8144, 8156, 8167, 8179, 8191, 8202,
1021                         8213, 8224, 8235, 8246, 8256, 8267, 8277, 8288, 8298, 8308, 8318, 8328, 8337, 8347, 8357, 8366,
1022                         8375, 8384, 8394, 8403, 8412, 8420, 8429, 8438, 8446, 8455, 8463, 8472, 8480, 8488, 8496, 8504,
1023                         8512, 8520, 8528, 8536, 8544, 8551, 8559, 8566, 8574, 8581, 8588, 8596, 8603, 8610, 8617, 8624],
1024                 [8631, 8645, 8659, 8672, 8685, 8698, 8711, 8723, 8736, 8748, 8760, 8772, 8784, 8796, 8807, 8818,
1025                         8830, 8841, 8852, 8862, 8873, 8884, 8894, 8904, 8914, 8924, 8934, 8944, 8954, 8964, 8973, 8982,
1026                         8992, 9001, 9010, 9019, 9028, 9037, 9046, 9054, 9063, 9071, 9080, 9088, 9097, 9105, 9113, 9121,
1027                         9129, 9137, 9145, 9152, 9160, 9168, 9175, 9183, 9190, 9198, 9205, 9212, 9219, 9227, 9234, 9241],
1028                 [9248, 9261, 9275, 9288, 9302, 9315, 9327, 9340, 9352, 9365, 9377, 9389, 9400, 9412, 9424, 9435,
1029                         9446, 9457, 9468, 9479, 9490, 9500, 9510, 9521, 9531, 9541, 9551, 9561, 9570, 9580, 9590, 9599,
1030                         9608, 9617, 9627, 9636, 9645, 9653, 9662, 9671, 9679, 9688, 9696, 9705, 9713, 9721, 9729, 9737,
1031                         9745, 9753, 9761, 9769, 9777, 9784, 9792, 9799, 9807, 9814, 9821, 9829, 9836, 9843, 9850, 9857],
1032                 [9864, 9878, 9892, 9905, 9918, 9931, 9944, 9956, 9969, 9981, 9993, 10005, 10017, 10029, 10040, 10051,
1033                         10063, 10074, 10085, 10095, 10106, 10117, 10127, 10137, 10147, 10157, 10167, 10177, 10187, 10197, 10206, 10215,
1034                         10225, 10234, 10243, 10252, 10261, 10270, 10279, 10287, 10296, 10304, 10313, 10321, 10330, 10338, 10346, 10354,
1035                         10362, 10370, 10378, 10385, 10393, 10401, 10408, 10416, 10423, 10431, 10438, 10445, 10452, 10460, 10467, 10474],
1036                 [10481, 10494, 10508, 10521, 10535, 10548, 10560, 10573, 10585, 10598, 10610, 10622, 10634, 10645, 10657, 10668,
1037                         10679, 10690, 10701, 10712, 10723, 10733, 10743, 10754, 10764, 10774, 10784, 10794, 10803, 10813, 10823, 10832,
1038                         10841, 10851, 10860, 10869, 10878, 10886, 10895, 10904, 10912, 10921, 10929, 10938, 10946, 10954, 10962, 10970,
1039                         10978, 10986, 10994, 11002, 11010, 11017, 11025, 11032, 11040, 11047, 11054, 11062, 11069, 11076, 11083, 11090],
1040                 [11097, 11111, 11125, 11138, 11151, 11164, 11177, 11189, 11202, 11214, 11226, 11238, 11250, 11262, 11273, 11284,
1041                         11296, 11307, 11318, 11328, 11339, 11350, 11360, 11370, 11380, 11390, 11400, 11410, 11420, 11430, 11439, 11448,
1042                         11458, 11467, 11476, 11485, 11494, 11503, 11512, 11520, 11529, 11538, 11546, 11554, 11563, 11571, 11579, 11587,
1043                         11595, 11603, 11611, 11618, 11626, 11634, 11641, 11649, 11656, 11664, 11671, 11678, 11685, 11693, 11700, 11707],
1044                 [11714, 11727, 11741, 11754, 11768, 11781, 11793, 11806, 11818, 11831, 11843, 11855, 11867, 11878, 11890, 11901,
1045                         11912, 11923, 11934, 11945, 11956, 11966, 11976, 11987, 11997, 12007, 12017, 12027, 12036, 12046, 12056, 12065,
1046                         12074, 12084, 12093, 12102, 12111, 12119, 12128, 12137, 12146, 12154, 12162, 12171, 12179, 12187, 12195, 12203,
1047                         12211, 12219, 12227, 12235, 12243, 12250, 12258, 12265, 12273, 12280, 12287, 12295, 12302, 12309, 12316, 12323],
1048                 [12330, 12344, 12358, 12371, 12384, 12397, 12410, 12423, 12435, 12447, 12459, 12471, 12483, 12495, 12506, 12517,
1049                         12529, 12540, 12551, 12561, 12572, 12583, 12593, 12603, 12613, 12623, 12633, 12643, 12653, 12663, 12672, 12682,
1050                         12691, 12700, 12709, 12718, 12727, 12736, 12745, 12753, 12762, 12771, 12779, 12787, 12796, 12804, 12812, 12820,
1051                         12828, 12836, 12844, 12851, 12859, 12867, 12874, 12882, 12889, 12897, 12904, 12911, 12918, 12926, 12933, 12940],
1052                 [12947, 12960, 12974, 12987, 13001, 13014, 13026, 13039, 13051, 13064, 13076, 13088, 13100, 13111, 13123, 13134,
1053                         13145, 13156, 13167, 13178, 13189, 13199, 13209, 13220, 13230, 13240, 13250, 13260, 13269, 13279, 13289, 13298,
1054                         13307, 13317, 13326, 13335, 13344, 13352, 13361, 13370, 13379, 13387, 13395, 13404, 13412, 13420, 13428, 13436,
1055                         13444, 13452, 13460, 13468, 13476, 13483, 13491, 13498, 13506, 13513, 13521, 13528, 13535, 13542, 13549, 13556],
1056                 [13563, 13577, 13591, 13604, 13617, 13630, 13643, 13656, 13668, 13680, 13692, 13704, 13716, 13728, 13739, 13750,
1057                         13762, 13773, 13784, 13794, 13805, 13816, 13826, 13836, 13846, 13857, 13866, 13876, 13886, 13896, 13905, 13915,
1058                         13924, 13933, 13942, 13951, 13960, 13969, 13978, 13986, 13995, 14004, 14012, 14020, 14029, 14037, 14045, 14053,
1059                         14061, 14069, 14077, 14084, 14092, 14100, 14107, 14115, 14122, 14130, 14137, 14144, 14151, 14159, 14166, 14173],
1060                 [14180, 14194, 14207, 14220, 14234, 14247, 14259, 14272, 14284, 14297, 14309, 14321, 14333, 14344, 14356, 14367,
1061                         14378, 14389, 14400, 14411, 14422, 14432, 14443, 14453, 14463, 14473, 14483, 14493, 14502, 14512, 14522, 14531,
1062                         14540, 14550, 14559, 14568, 14577, 14586, 14594, 14603, 14612, 14620, 14628, 14637, 14645, 14653, 14661, 14669,
1063                         14677, 14685, 14693, 14701, 14709, 14716, 14724, 14731, 14739, 14746, 14754, 14761, 14768, 14775, 14782, 14789],
1064                 [14796, 14810, 14824, 14837, 14850, 14863, 14876, 14889, 14901, 14913, 14925, 14937, 14949, 14961, 14972, 14984,
1065                         14995, 15006, 15017, 15027, 15038, 15049, 15059, 15069, 15079, 15090, 15099, 15109, 15119, 15129, 15138, 15148,
1066                         15157, 15166, 15175, 15184, 15193, 15202, 15211, 15219, 15228, 15237, 15245, 15253, 15262, 15270, 15278, 15286,
1067                         15294, 15302, 15310, 15317, 15325, 15333, 15340, 15348, 15355, 15363, 15370, 15377, 15384, 15392, 15399, 15406],
1068                 [15413, 15427, 15440, 15453, 15467, 15480, 15492, 15505, 15517, 15530, 15542, 15554, 15566, 15577, 15589, 15600,
1069                         15611, 15622, 15633, 15644, 15655, 15665, 15676, 15686, 15696, 15706, 15716, 15726, 15736, 15745, 15755, 15764,
1070                         15773, 15783, 15792, 15801, 15810, 15819, 15827, 15836, 15845, 15853, 15862, 15870, 15878, 15886, 15894, 15903,
1071                         15910, 15918, 15926, 15934, 15942, 15949, 15957, 15964, 15972, 15979, 15987, 15994, 16001, 16008, 16015, 16022],
1072                 [16029, 16043, 16057, 16070, 16083, 16096, 16109, 16122, 16134, 16146, 16158, 16170, 16182, 16194, 16205, 16217,
1073                         16228, 16239, 16250, 16260, 16271, 16282, 16292, 16302, 16312, 16323, 16332, 16342, 16352, 16362, 16371, 16381,
1074                         16390, 16399, 16408, 16417, 16426, 16435, 16444, 16452, 16461, 16470, 16478, 16486, 16495, 16503, 16511, 16519,
1075                         16527, 16535, 16543, 16550, 16558, 16566, 16573, 16581, 16588, 16596, 16603, 16610, 16618, 16625, 16632, 16639],
1076                 [16646, 16660, 16673, 16686, 16700, 16713, 16725, 16738, 16751, 16763, 16775, 16787, 16799, 16810, 16822, 16833,
1077                         16844, 16855, 16866, 16877, 16888, 16898, 16909, 16919, 16929, 16939, 16949, 16959, 16969, 16978, 16988, 16997,
1078                         17006, 17016, 17025, 17034, 17043, 17052, 17060, 17069, 17078, 17086, 17095, 17103, 17111, 17119, 17127, 17136,
1079                         17143, 17151, 17159, 17167, 17175, 17182, 17190, 17197, 17205, 17212, 17220, 17227, 17234, 17241, 17248, 17255],
1080                 [17262, 17276, 17290, 17303, 17316, 17329, 17342, 17355, 17367, 17379, 17391, 17403, 17415, 17427, 17438, 17450,
1081                         17461, 17472, 17483, 17493, 17504, 17515, 17525, 17535, 17546, 17556, 17565, 17575, 17585, 17595, 17604, 17614,
1082                         17623, 17632, 17641, 17650, 17659, 17668, 17677, 17685, 17694, 17703, 17711, 17719, 17728, 17736, 17744, 17752,
1083                         17760, 17768, 17776, 17784, 17791, 17799, 17806, 17814, 17821, 17829, 17836, 17843, 17851, 17858, 17865, 17872],
1084                 [17879, 17893, 17906, 17920, 17933, 17946, 17958, 17971, 17984, 17996, 18008, 18020, 18032, 18043, 18055, 18066,
1085                         18077, 18088, 18099, 18110, 18121, 18131, 18142, 18152, 18162, 18172, 18182, 18192, 18202, 18211, 18221, 18230,
1086                         18239, 18249, 18258, 18267, 18276, 18285, 18293, 18302, 18311, 18319, 18328, 18336, 18344, 18352, 18360, 18369,
1087                         18377, 18384, 18392, 18400, 18408, 18415, 18423, 18430, 18438, 18445, 18453, 18460, 18467, 18474, 18481, 18488],
1088                 [18495, 18509, 18523, 18536, 18549, 18562, 18575, 18588, 18600, 18612, 18624, 18636, 18648, 18660, 18671, 18683,
1089                         18694, 18705, 18716, 18726, 18737, 18748, 18758, 18768, 18779, 18789, 18799, 18808, 18818, 18828, 18837, 18847,
1090                         18856, 18865, 18874, 18883, 18892, 18901, 18910, 18919, 18927, 18936, 18944, 18952, 18961, 18969, 18977, 18985,
1091                         18993, 19001, 19009, 19017, 19024, 19032, 19039, 19047, 19054, 19062, 19069, 19076, 19084, 19091, 19098, 19105],
1092                 [19112, 19126, 19139, 19153, 19166, 19179, 19191, 19204, 19217, 19229, 19241, 19253, 19265, 19276, 19288, 19299,
1093                         19310, 19321, 19332, 19343, 19354, 19364, 19375, 19385, 19395, 19405, 19415, 19425, 19435, 19444, 19454, 19463,
1094                         19472, 19482, 19491, 19500, 19509, 19518, 19526, 19535, 19544, 19552, 19561, 19569, 19577, 19585, 19594, 19602,
1095                         19610, 19617, 19625, 19633, 19641, 19648, 19656, 19663, 19671, 19678, 19686, 19693, 19700, 19707, 19714, 19721],
1096                 [19728, 19742, 19756, 19769, 19782, 19795, 19808, 19821, 19833, 19845, 19857, 19869, 19881, 19893, 19904, 19916,
1097                         19927, 19938, 19949, 19960, 19970, 19981, 19991, 20001, 20012, 20022, 20032, 20041, 20051, 20061, 20070, 20080,
1098                         20089, 20098, 20107, 20116, 20125, 20134, 20143, 20152, 20160, 20169, 20177, 20185, 20194, 20202, 20210, 20218,
1099                         20226, 20234, 20242, 20250, 20257, 20265, 20272, 20280, 20287, 20295, 20302, 20309, 20317, 20324, 20331, 20338],
1100                 [20345, 20359, 20372, 20386, 20399, 20412, 20425, 20437, 20450, 20462, 20474, 20486, 20498, 20509, 20521, 20532,
1101                         20543, 20554, 20565, 20576, 20587, 20597, 20608, 20618, 20628, 20638, 20648, 20658, 20668, 20677, 20687, 20696,
1102                         20705, 20715, 20724, 20733, 20742, 20751, 20759, 20768, 20777, 20785, 20794, 20802, 20810, 20818, 20827, 20835,
1103                         20843, 20850, 20858, 20866, 20874, 20881, 20889, 20896, 20904, 20911, 20919, 20926, 20933, 20940, 20947, 20954],
1104                 [20961, 20975, 20989, 21002, 21015, 21028, 21041, 21054, 21066, 21078, 21090, 21102, 21114, 21126, 21137, 21149,
1105                         21160, 21171, 21182, 21193, 21203, 21214, 21224, 21234, 21245, 21255, 21265, 21274, 21284, 21294, 21303, 21313,
1106                         21322, 21331, 21340, 21349, 21358, 21367, 21376, 21385, 21393, 21402, 21410, 21418, 21427, 21435, 21443, 21451,
1107                         21459, 21467, 21475, 21483, 21490, 21498, 21505, 21513, 21520, 21528, 21535, 21542, 21550, 21557, 21564, 21571],
1108                 [21578, 21592, 21605, 21619, 21632, 21645, 21658, 21670, 21683, 21695, 21707, 21719, 21731, 21742, 21754, 21765,
1109                         21776, 21787, 21798, 21809, 21820, 21830, 21841, 21851, 21861, 21871, 21881, 21891, 21901, 21910, 21920, 21929,
1110                         21938, 21948, 21957, 21966, 21975, 21984, 21992, 22001, 22010, 22018, 22027, 22035, 22043, 22051, 22060, 22068,
1111                         22076, 22083, 22091, 22099, 22107, 22114, 22122, 22129, 22137, 22144, 22152, 22159, 22166, 22173, 22180, 22187],
1112                 [22194, 22208, 22222, 22235, 22248, 22261, 22274, 22287, 22299, 22311, 22323, 22335, 22347, 22359, 22370, 22382,
1113                         22393, 22404, 22415, 22426, 22436, 22447, 22457, 22467, 22478, 22488, 22498, 22507, 22517, 22527, 22536, 22546,
1114                         22555, 22564, 22573, 22582, 22591, 22600, 22609, 22618, 22626, 22635, 22643, 22651, 22660, 22668, 22676, 22684,
1115                         22692, 22700, 22708, 22716, 22723, 22731, 22738, 22746, 22753, 22761, 22768, 22775, 22783, 22790, 22797, 22804],
1116                 [22811, 22825, 22838, 22852, 22865, 22878, 22891, 22903, 22916, 22928, 22940, 22952, 22964, 22975, 22987, 22998,
1117                         23009, 23020, 23031, 23042, 23053, 23063, 23074, 23084, 23094, 23104, 23114, 23124, 23134, 23143, 23153, 23162,
1118                         23171, 23181, 23190, 23199, 23208, 23217, 23225, 23234, 23243, 23251, 23260, 23268, 23276, 23284, 23293, 23301,
1119                         23309, 23316, 23324, 23332, 23340, 23347, 23355, 23363, 23370, 23377, 23385, 23392, 23399, 23406, 23413, 23420],
1120                 [23427, 23441, 23455, 23468, 23481, 23494, 23507, 23520, 23532, 23544, 23556, 23568, 23580, 23592, 23603, 23615,
1121                         23626, 23637, 23648, 23659, 23669, 23680, 23690, 23700, 23711, 23721, 23731, 23740, 23750, 23760, 23769, 23779,
1122                         23788, 23797, 23806, 23815, 23824, 23833, 23842, 23851, 23859, 23868, 23876, 23884, 23893, 23901, 23909, 23917,
1123                         23925, 23933, 23941, 23949, 23956, 23964, 23972, 23979, 23986, 23994, 24001, 24008, 24016, 24023, 24030, 24037],
1124                 [24044, 24058, 24071, 24085, 24098, 24111, 24124, 24136, 24149, 24161, 24173, 24185, 24197, 24208, 24220, 24231,
1125                         24242, 24253, 24264, 24275, 24286, 24296, 24307, 24317, 24327, 24337, 24347, 24357, 24367, 24376, 24386, 24395,
1126                         24405, 24414, 24423, 24432, 24441, 24450, 24458, 24467, 24476, 24484, 24493, 24501, 24509, 24517, 24526, 24534,
1127                         24542, 24550, 24557, 24565, 24573, 24580, 24588, 24596, 24603, 24610, 24618, 24625, 24632, 24639, 24646, 24653],
1128                 [24660, 24674, 24688, 24701, 24714, 24727, 24740, 24753, 24765, 24777, 24790, 24801, 24813, 24825, 24836, 24848,
1129                         24859, 24870, 24881, 24892, 24902, 24913, 24923, 24933, 24944, 24954, 24964, 24973, 24983, 24993, 25002, 25012,
1130                         25021, 25030, 25039, 25048, 25057, 25066, 25075, 25084, 25092, 25101, 25109, 25117, 25126, 25134, 25142, 25150,
1131                         25158, 25166, 25174, 25182, 25189, 25197, 25205, 25212, 25219, 25227, 25234, 25241, 25249, 25256, 25263, 25270],
1132                 [25277, 25291, 25304, 25318, 25331, 25344, 25357, 25369, 25382, 25394, 25406, 25418, 25430, 25441, 25453, 25464,
1133                         25475, 25486, 25497, 25508, 25519, 25529, 25540, 25550, 25560, 25570, 25580, 25590, 25600, 25609, 25619, 25628,
1134                         25638, 25647, 25656, 25665, 25674, 25683, 25691, 25700, 25709, 25717, 25726, 25734, 25742, 25750, 25759, 25767,
1135                         25775, 25783, 25790, 25798, 25806, 25813, 25821, 25829, 25836, 25843, 25851, 25858, 25865, 25872, 25879, 25886],
1136                 [25893, 25907, 25921, 25934, 25947, 25960, 25973, 25986, 25998, 26010, 26023, 26034, 26046, 26058, 26069, 26081,
1137                         26092, 26103, 26114, 26125, 26135, 26146, 26156, 26166, 26177, 26187, 26197, 26206, 26216, 26226, 26235, 26245,
1138                         26254, 26263, 26272, 26281, 26290, 26299, 26308, 26317, 26325, 26334, 26342, 26351, 26359, 26367, 26375, 26383,
1139                         26391, 26399, 26407, 26415, 26422, 26430, 26438, 26445, 26453, 26460, 26467, 26474, 26482, 26489, 26496, 26503],
1140                 [26510, 26524, 26537, 26551, 26564, 26577, 26590, 26602, 26615, 26627, 26639, 26651, 26663, 26674, 26686, 26697,
1141                         26708, 26719, 26730, 26741, 26752, 26762, 26773, 26783, 26793, 26803, 26813, 26823, 26833, 26842, 26852, 26861,
1142                         26871, 26880, 26889, 26898, 26907, 26916, 26924, 26933, 26942, 26950, 26959, 26967, 26975, 26983, 26992, 27000,
1143                         27008, 27016, 27023, 27031, 27039, 27046, 27054, 27062, 27069, 27076, 27084, 27091, 27098, 27105, 27112, 27119],
1144                 [27126, 27140, 27154, 27167, 27180, 27193, 27206, 27219, 27231, 27243, 27256, 27267, 27279, 27291, 27302, 27314,
1145                         27325, 27336, 27347, 27358, 27368, 27379, 27389, 27399, 27410, 27420, 27430, 27439, 27449, 27459, 27468, 27478,
1146                         27487, 27496, 27505, 27514, 27523, 27532, 27541, 27550, 27558, 27567, 27575, 27584, 27592, 27600, 27608, 27616,
1147                         27624, 27632, 27640, 27648, 27655, 27663, 27671, 27678, 27686, 27693, 27700, 27707, 27715, 27722, 27729, 27736],
1148                 [27743, 27757, 27770, 27784, 27797, 27810, 27823, 27835, 27848, 27860, 27872, 27884, 27896, 27907, 27919, 27930,
1149                         27941, 27952, 27963, 27974, 27985, 27995, 28006, 28016, 28026, 28036, 28046, 28056, 28066, 28075, 28085, 28094,
1150                         28104, 28113, 28122, 28131, 28140, 28149, 28157, 28166, 28175, 28183, 28192, 28200, 28208, 28217, 28225, 28233,
1151                         28241, 28249, 28256, 28264, 28272, 28280, 28287, 28295, 28302, 28309, 28317, 28324, 28331, 28338, 28345, 28352],
1152                 [28359, 28373, 28387, 28400, 28413, 28426, 28439, 28452, 28464, 28476, 28489, 28501, 28512, 28524, 28535, 28547,
1153                         28558, 28569, 28580, 28591, 28601, 28612, 28622, 28633, 28643, 28653, 28663, 28672, 28682, 28692, 28701, 28711,
1154                         28720, 28729, 28738, 28747, 28756, 28765, 28774, 28783, 28791, 28800, 28808, 28817, 28825, 28833, 28841, 28849,
1155                         28857, 28865, 28873, 28881, 28888, 28896, 28904, 28911, 28919, 28926, 28933, 28941, 28948, 28955, 28962, 28969],
1156                 [28976, 28990, 29003, 29017, 29030, 29043, 29056, 29068, 29081, 29093, 29105, 29117, 29129, 29140, 29152, 29163,
1157                         29174, 29185, 29196, 29207, 29218, 29228, 29239, 29249, 29259, 29269, 29279, 29289, 29299, 29308, 29318, 29327,
1158                         29337, 29346, 29355, 29364, 29373, 29382, 29390, 29399, 29408, 29416, 29425, 29433, 29441, 29450, 29458, 29466,
1159                         29474, 29482, 29489, 29497, 29505, 29513, 29520, 29528, 29535, 29542, 29550, 29557, 29564, 29571, 29578, 29585],
1160                 [29592, 29606, 29620, 29633, 29646, 29659, 29672, 29685, 29697, 29709, 29722, 29734, 29745, 29757, 29768, 29780,
1161                         29791, 29802, 29813, 29824, 29834, 29845, 29855, 29866, 29876, 29886, 29896, 29906, 29915, 29925, 29934, 29944,
1162                         29953, 29962, 29971, 29980, 29989, 29998, 30007, 30016, 30024, 30033, 30041, 30050, 30058, 30066, 30074, 30082,
1163                         30090, 30098, 30106, 30114, 30121, 30129, 30137, 30144, 30152, 30159, 30166, 30174, 30181, 30188, 30195, 30202],
1164                 [30209, 30223, 30236, 30250, 30263, 30276, 30289, 30301, 30314, 30326, 30338, 30350, 30362, 30373, 30385, 30396,
1165                         30407, 30418, 30429, 30440, 30451, 30461, 30472, 30482, 30492, 30502, 30512, 30522, 30532, 30541, 30551, 30560,
1166                         30570, 30579, 30588, 30597, 30606, 30615, 30624, 30632, 30641, 30649, 30658, 30666, 30674, 30683, 30691, 30699,
1167                         30707, 30715, 30722, 30730, 30738, 30746, 30753, 30761, 30768, 30775, 30783, 30790, 30797, 30804, 30811, 30818],
1168                 [30825, 30839, 30853, 30866, 30879, 30892, 30905, 30918, 30930, 30943, 30955, 30967, 30978, 30990, 31001, 31013,
1169                         31024, 31035, 31046, 31057, 31067, 31078, 31088, 31099, 31109, 31119, 31129, 31139, 31148, 31158, 31167, 31177,
1170                         31186, 31195, 31204, 31213, 31222, 31231, 31240, 31249, 31257, 31266, 31274, 31283, 31291, 31299, 31307, 31315,
1171                         31323, 31331, 31339, 31347, 31354, 31362, 31370, 31377, 31385, 31392, 31399, 31407, 31414, 31421, 31428, 31435],
1172                 [31442, 31456, 31469, 31483, 31496, 31509, 31522, 31534, 31547, 31559, 31571, 31583, 31595, 31606, 31618, 31629,
1173                         31640, 31652, 31662, 31673, 31684, 31694, 31705, 31715, 31725, 31735, 31745, 31755, 31765, 31774, 31784, 31793,
1174                         31803, 31812, 31821, 31830, 31839, 31848, 31857, 31865, 31874, 31882, 31891, 31899, 31907, 31916, 31924, 31932,
1175                         31940, 31948, 31955, 31963, 31971, 31979, 31986, 31994, 32001, 32008, 32016, 32023, 32030, 32037, 32044, 32052],
1176                 [32058, 32072, 32086, 32099, 32112, 32125, 32138, 32151, 32163, 32176, 32188, 32200, 32211, 32223, 32234, 32246,
1177                         32257, 32268, 32279, 32290, 32300, 32311, 32321, 32332, 32342, 32352, 32362, 32372, 32381, 32391, 32400, 32410,
1178                         32419, 32428, 32437, 32446, 32455, 32464, 32473, 32482, 32490, 32499, 32507, 32516, 32524, 32532, 32540, 32548,
1179                         32556, 32564, 32572, 32580, 32587, 32595, 32603, 32610, 32618, 32625, 32632, 32640, 32647, 32654, 32661, 32668],
1180                 [32675, 32689, 32702, 32716, 32729, 32742, 32755, 32767, 32780, 32792, 32804, 32816, 32828, 32839, 32851, 32862,
1181                         32873, 32885, 32895, 32906, 32917, 32927, 32938, 32948, 32958, 32968, 32978, 32988, 32998, 33007, 33017, 33026,
1182                         33036, 33045, 33054, 33063, 33072, 33081, 33090, 33098, 33107, 33115, 33124, 33132, 33140, 33149, 33157, 33165,
1183                         33173, 33181, 33188, 33196, 33204, 33212, 33219, 33227, 33234, 33241, 33249, 33256, 33263, 33270, 33278, 33285],
1184                 [33292, 33305, 33319, 33332, 33345, 33358, 33371, 33384, 33396, 33409, 33421, 33433, 33444, 33456, 33467, 33479,
1185                         33490, 33501, 33512, 33523, 33533, 33544, 33554, 33565, 33575, 33585, 33595, 33605, 33614, 33624, 33633, 33643,
1186                         33652, 33661, 33670, 33680, 33688, 33697, 33706, 33715, 33723, 33732, 33740, 33749, 33757, 33765, 33773, 33781,
1187                         33789, 33797, 33805, 33813, 33820, 33828, 33836, 33843, 33851, 33858, 33865, 33873, 33880, 33887, 33894, 33901],
1188                 [33908, 33922, 33935, 33949, 33962, 33975, 33988, 34000, 34013, 34025, 34037, 34049, 34061, 34072, 34084, 34095,
1189                         34106, 34118, 34128, 34139, 34150, 34160, 34171, 34181, 34191, 34201, 34211, 34221, 34231, 34240, 34250, 34259,
1190                         34269, 34278, 34287, 34296, 34305, 34314, 34323, 34331, 34340, 34348, 34357, 34365, 34373, 34382, 34390, 34398,
1191                         34406, 34414, 34422, 34429, 34437, 34445, 34452, 34460, 34467, 34475, 34482, 34489, 34496, 34503, 34511, 34518],
1192                 [34525, 34538, 34552, 34565, 34578, 34591, 34604, 34617, 34629, 34642, 34654, 34666, 34677, 34689, 34700, 34712,
1193                         34723, 34734, 34745, 34756, 34766, 34777, 34787, 34798, 34808, 34818, 34828, 34838, 34847, 34857, 34866, 34876,
1194                         34885, 34894, 34904, 34913, 34921, 34930, 34939, 34948, 34956, 34965, 34973, 34982, 34990, 34998, 35006, 35014,
1195                         35022, 35030, 35038, 35046, 35053, 35061, 35069, 35076, 35084, 35091, 35098, 35106, 35113, 35120, 35127, 35134],
1196                 [35141, 35155, 35168, 35182, 35195, 35208, 35221, 35233, 35246, 35258, 35270, 35282, 35294, 35306, 35317, 35328,
1197                         35340, 35351, 35361, 35372, 35383, 35393, 35404, 35414, 35424, 35434, 35444, 35454, 35464, 35473, 35483, 35492,
1198                         35502, 35511, 35520, 35529, 35538, 35547, 35556, 35564, 35573, 35581, 35590, 35598, 35606, 35615, 35623, 35631,
1199                         35639, 35647, 35655, 35662, 35670, 35678, 35685, 35693, 35700, 35708, 35715, 35722, 35729, 35736, 35744, 35751],
1200                 [35758, 35771, 35785, 35798, 35811, 35824, 35837, 35850, 35862, 35875, 35887, 35899, 35910, 35922, 35934, 35945,
1201                         35956, 35967, 35978, 35989, 35999, 36010, 36020, 36031, 36041, 36051, 36061, 36071, 36080, 36090, 36099, 36109,
1202                         36118, 36127, 36137, 36146, 36154, 36163, 36172, 36181, 36189, 36198, 36206, 36215, 36223, 36231, 36239, 36247,
1203                         36255, 36263, 36271, 36279, 36287, 36294, 36302, 36309, 36317, 36324, 36331, 36339, 36346, 36353, 36360, 36367],
1204                 [36374, 36388, 36401, 36415, 36428, 36441, 36454, 36466, 36479, 36491, 36503, 36515, 36527, 36539, 36550, 36561,
1205                         36573, 36584, 36594, 36605, 36616, 36626, 36637, 36647, 36657, 36667, 36677, 36687, 36697, 36706, 36716, 36725,
1206                         36735, 36744, 36753, 36762, 36771, 36780, 36789, 36797, 36806, 36814, 36823, 36831, 36839, 36848, 36856, 36864,
1207                         36872, 36880, 36888, 36895, 36903, 36911, 36918, 36926, 36933, 36941, 36948, 36955, 36962, 36969, 36977, 36984],
1208                 [36991, 37004, 37018, 37031, 37044, 37057, 37070, 37083, 37095, 37108, 37120, 37132, 37143, 37155, 37167, 37178,
1209                         37189, 37200, 37211, 37222, 37232, 37243, 37253, 37264, 37274, 37284, 37294, 37304, 37313, 37323, 37332, 37342,
1210                         37351, 37360, 37370, 37379, 37388, 37396, 37405, 37414, 37422, 37431, 37439, 37448, 37456, 37464, 37472, 37480,
1211                         37488, 37496, 37504, 37512, 37520, 37527, 37535, 37542, 37550, 37557, 37564, 37572, 37579, 37586, 37593, 37600],
1212                 [37607, 37621, 37634, 37648, 37661, 37674, 37687, 37699, 37712, 37724, 37736, 37748, 37760, 37772, 37783, 37794,
1213                         37806, 37817, 37828, 37838, 37849, 37859, 37870, 37880, 37890, 37900, 37910, 37920, 37930, 37939, 37949, 37958,
1214                         37968, 37977, 37986, 37995, 38004, 38013, 38022, 38030, 38039, 38047, 38056, 38064, 38072, 38081, 38089, 38097,
1215                         38105, 38113, 38121, 38128, 38136, 38144, 38151, 38159, 38166, 38174, 38181, 38188, 38195, 38202, 38210, 38217],
1216                 [38224, 38237, 38251, 38264, 38278, 38290, 38303, 38316, 38328, 38341, 38353, 38365, 38376, 38388, 38400, 38411,
1217                         38422, 38433, 38444, 38455, 38465, 38476, 38486, 38497, 38507, 38517, 38527, 38537, 38546, 38556, 38565, 38575,
1218                         38584, 38593, 38603, 38612, 38621, 38629, 38638, 38647, 38655, 38664, 38672, 38681, 38689, 38697, 38705, 38713,
1219                         38721, 38729, 38737, 38745, 38753, 38760, 38768, 38775, 38783, 38790, 38797, 38805, 38812, 38819, 38826, 38833],
1220                 [38840, 38854, 38867, 38881, 38894, 38907, 38920, 38932, 38945, 38957, 38969, 38981, 38993, 39005, 39016, 39027,
1221                         39039, 39050, 39061, 39071, 39082, 39092, 39103, 39113, 39123, 39133, 39143, 39153, 39163, 39172, 39182, 39191,
1222                         39201, 39210, 39219, 39228, 39237, 39246, 39255, 39263, 39272, 39280, 39289, 39297, 39305, 39314, 39322, 39330,
1223                         39338, 39346, 39354, 39361, 39369, 39377, 39384, 39392, 39399, 39407, 39414, 39421, 39428, 39436, 39443, 39450],
1224         ];
1225
1226         /// Approximate `log10(numerator / denominator) * 2048` using a look-up table.
1227         #[inline]
1228         pub fn negative_log10_times_2048(numerator: u64, denominator: u64) -> u64 {
1229                 // Multiply the -1 through to avoid needing to use signed numbers.
1230                 (log10_times_2048(denominator) - log10_times_2048(numerator)) as u64
1231         }
1232
1233         #[inline]
1234         fn log10_times_2048(x: u64) -> u16 {
1235                 debug_assert_ne!(x, 0);
1236                 let most_significant_bit = HIGHEST_BIT - x.leading_zeros();
1237                 let lower_bits = (x >> most_significant_bit.saturating_sub(LOWER_BITS)) & LOWER_BITMASK;
1238                 LOG10_TIMES_2048[most_significant_bit as usize][lower_bits as usize]
1239         }
1240
1241         #[cfg(test)]
1242         mod tests {
1243                 use super::*;
1244
1245                 #[test]
1246                 fn prints_negative_log10_times_2048_lookup_table() {
1247                         for msb in 0..BITS {
1248                                 for i in 0..LOWER_BITS_BOUND {
1249                                         let x = ((LOWER_BITS_BOUND + i) << (HIGHEST_BIT - LOWER_BITS)) >> (HIGHEST_BIT - msb);
1250                                         let log10_times_2048 = ((x as f64).log10() * 2048.0).round() as u16;
1251                                         assert_eq!(log10_times_2048, LOG10_TIMES_2048[msb as usize][i as usize]);
1252
1253                                         if i % LOWER_BITS_BOUND == 0 {
1254                                                 print!("\t\t[{}, ", log10_times_2048);
1255                                         } else if i % LOWER_BITS_BOUND == LOWER_BITS_BOUND - 1 {
1256                                                 println!("{}],", log10_times_2048);
1257                                         } else if i % (LOWER_BITS_BOUND/4) == LOWER_BITS_BOUND/4 - 1 {
1258                                                 print!("{},\n\t\t\t", log10_times_2048);
1259                                         } else {
1260                                                 print!("{}, ", log10_times_2048);
1261                                         }
1262                                 }
1263                         }
1264                 }
1265         }
1266 }
1267
1268 impl<G: Deref<Target = NetworkGraph>, L: Deref, T: Time> Writeable for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1269         #[inline]
1270         fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
1271                 write_tlv_fields!(w, {
1272                         (0, self.channel_liquidities, required)
1273                 });
1274                 Ok(())
1275         }
1276 }
1277
1278 impl<G: Deref<Target = NetworkGraph>, L: Deref, T: Time>
1279 ReadableArgs<(ProbabilisticScoringParameters, G, L)> for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1280         #[inline]
1281         fn read<R: Read>(
1282                 r: &mut R, args: (ProbabilisticScoringParameters, G, L)
1283         ) -> Result<Self, DecodeError> {
1284                 let (params, network_graph, logger) = args;
1285                 let mut channel_liquidities = HashMap::new();
1286                 read_tlv_fields!(r, {
1287                         (0, channel_liquidities, required)
1288                 });
1289                 Ok(Self {
1290                         params,
1291                         network_graph,
1292                         logger,
1293                         channel_liquidities,
1294                 })
1295         }
1296 }
1297
1298 impl<T: Time> Writeable for ChannelLiquidity<T> {
1299         #[inline]
1300         fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
1301                 let duration_since_epoch = T::duration_since_epoch() - self.last_updated.elapsed();
1302                 write_tlv_fields!(w, {
1303                         (0, self.min_liquidity_offset_msat, required),
1304                         (2, self.max_liquidity_offset_msat, required),
1305                         (4, duration_since_epoch, required),
1306                 });
1307                 Ok(())
1308         }
1309 }
1310
1311 impl<T: Time> Readable for ChannelLiquidity<T> {
1312         #[inline]
1313         fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
1314                 let mut min_liquidity_offset_msat = 0;
1315                 let mut max_liquidity_offset_msat = 0;
1316                 let mut duration_since_epoch = Duration::from_secs(0);
1317                 read_tlv_fields!(r, {
1318                         (0, min_liquidity_offset_msat, required),
1319                         (2, max_liquidity_offset_msat, required),
1320                         (4, duration_since_epoch, required),
1321                 });
1322                 Ok(Self {
1323                         min_liquidity_offset_msat,
1324                         max_liquidity_offset_msat,
1325                         last_updated: T::now() - (T::duration_since_epoch() - duration_since_epoch),
1326                 })
1327         }
1328 }
1329
1330 pub(crate) mod time {
1331         use core::ops::Sub;
1332         use core::time::Duration;
1333         /// A measurement of time.
1334         pub trait Time: Copy + Sub<Duration, Output = Self> where Self: Sized {
1335                 /// Returns an instance corresponding to the current moment.
1336                 fn now() -> Self;
1337
1338                 /// Returns the amount of time elapsed since `self` was created.
1339                 fn elapsed(&self) -> Duration;
1340
1341                 /// Returns the amount of time passed between `earlier` and `self`.
1342                 fn duration_since(&self, earlier: Self) -> Duration;
1343
1344                 /// Returns the amount of time passed since the beginning of [`Time`].
1345                 ///
1346                 /// Used during (de-)serialization.
1347                 fn duration_since_epoch() -> Duration;
1348         }
1349
1350         /// A state in which time has no meaning.
1351         #[derive(Clone, Copy, Debug, PartialEq, Eq)]
1352         pub struct Eternity;
1353
1354         #[cfg(not(feature = "no-std"))]
1355         impl Time for std::time::Instant {
1356                 fn now() -> Self {
1357                         std::time::Instant::now()
1358                 }
1359
1360                 fn duration_since(&self, earlier: Self) -> Duration {
1361                         self.duration_since(earlier)
1362                 }
1363
1364                 fn duration_since_epoch() -> Duration {
1365                         use std::time::SystemTime;
1366                         SystemTime::now().duration_since(SystemTime::UNIX_EPOCH).unwrap()
1367                 }
1368
1369                 fn elapsed(&self) -> Duration {
1370                         std::time::Instant::elapsed(self)
1371                 }
1372         }
1373
1374         impl Time for Eternity {
1375                 fn now() -> Self {
1376                         Self
1377                 }
1378
1379                 fn duration_since(&self, _earlier: Self) -> Duration {
1380                         Duration::from_secs(0)
1381                 }
1382
1383                 fn duration_since_epoch() -> Duration {
1384                         Duration::from_secs(0)
1385                 }
1386
1387                 fn elapsed(&self) -> Duration {
1388                         Duration::from_secs(0)
1389                 }
1390         }
1391
1392         impl Sub<Duration> for Eternity {
1393                 type Output = Self;
1394
1395                 fn sub(self, _other: Duration) -> Self {
1396                         self
1397                 }
1398         }
1399 }
1400
1401 pub(crate) use self::time::Time;
1402
1403 #[cfg(test)]
1404 mod tests {
1405         use super::{ChannelLiquidity, ProbabilisticScoringParameters, ProbabilisticScorerUsingTime, ScoringParameters, ScorerUsingTime, Time};
1406         use super::time::Eternity;
1407
1408         use ln::features::{ChannelFeatures, NodeFeatures};
1409         use ln::msgs::{ChannelAnnouncement, ChannelUpdate, OptionalField, UnsignedChannelAnnouncement, UnsignedChannelUpdate};
1410         use routing::scoring::Score;
1411         use routing::network_graph::{NetworkGraph, NodeId};
1412         use routing::router::RouteHop;
1413         use util::ser::{Readable, ReadableArgs, Writeable};
1414         use util::test_utils::TestLogger;
1415
1416         use bitcoin::blockdata::constants::genesis_block;
1417         use bitcoin::hashes::Hash;
1418         use bitcoin::hashes::sha256d::Hash as Sha256dHash;
1419         use bitcoin::network::constants::Network;
1420         use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey};
1421         use core::cell::Cell;
1422         use core::ops::Sub;
1423         use core::time::Duration;
1424         use io;
1425
1426         // `Time` tests
1427
1428         /// Time that can be advanced manually in tests.
1429         #[derive(Clone, Copy, Debug, PartialEq, Eq)]
1430         struct SinceEpoch(Duration);
1431
1432         impl SinceEpoch {
1433                 thread_local! {
1434                         static ELAPSED: Cell<Duration> = core::cell::Cell::new(Duration::from_secs(0));
1435                 }
1436
1437                 fn advance(duration: Duration) {
1438                         Self::ELAPSED.with(|elapsed| elapsed.set(elapsed.get() + duration))
1439                 }
1440         }
1441
1442         impl Time for SinceEpoch {
1443                 fn now() -> Self {
1444                         Self(Self::duration_since_epoch())
1445                 }
1446
1447                 fn duration_since(&self, earlier: Self) -> Duration {
1448                         self.0 - earlier.0
1449                 }
1450
1451                 fn duration_since_epoch() -> Duration {
1452                         Self::ELAPSED.with(|elapsed| elapsed.get())
1453                 }
1454
1455                 fn elapsed(&self) -> Duration {
1456                         Self::duration_since_epoch() - self.0
1457                 }
1458         }
1459
1460         impl Sub<Duration> for SinceEpoch {
1461                 type Output = Self;
1462
1463                 fn sub(self, other: Duration) -> Self {
1464                         Self(self.0 - other)
1465                 }
1466         }
1467
1468         #[test]
1469         fn time_passes_when_advanced() {
1470                 let now = SinceEpoch::now();
1471                 assert_eq!(now.elapsed(), Duration::from_secs(0));
1472
1473                 SinceEpoch::advance(Duration::from_secs(1));
1474                 SinceEpoch::advance(Duration::from_secs(1));
1475
1476                 let elapsed = now.elapsed();
1477                 let later = SinceEpoch::now();
1478
1479                 assert_eq!(elapsed, Duration::from_secs(2));
1480                 assert_eq!(later - elapsed, now);
1481         }
1482
1483         #[test]
1484         fn time_never_passes_in_an_eternity() {
1485                 let now = Eternity::now();
1486                 let elapsed = now.elapsed();
1487                 let later = Eternity::now();
1488
1489                 assert_eq!(now.elapsed(), Duration::from_secs(0));
1490                 assert_eq!(later - elapsed, now);
1491         }
1492
1493         // `Scorer` tests
1494
1495         /// A scorer for testing with time that can be manually advanced.
1496         type Scorer = ScorerUsingTime::<SinceEpoch>;
1497
1498         fn source_privkey() -> SecretKey {
1499                 SecretKey::from_slice(&[42; 32]).unwrap()
1500         }
1501
1502         fn target_privkey() -> SecretKey {
1503                 SecretKey::from_slice(&[43; 32]).unwrap()
1504         }
1505
1506         fn source_pubkey() -> PublicKey {
1507                 let secp_ctx = Secp256k1::new();
1508                 PublicKey::from_secret_key(&secp_ctx, &source_privkey())
1509         }
1510
1511         fn target_pubkey() -> PublicKey {
1512                 let secp_ctx = Secp256k1::new();
1513                 PublicKey::from_secret_key(&secp_ctx, &target_privkey())
1514         }
1515
1516         fn source_node_id() -> NodeId {
1517                 NodeId::from_pubkey(&source_pubkey())
1518         }
1519
1520         fn target_node_id() -> NodeId {
1521                 NodeId::from_pubkey(&target_pubkey())
1522         }
1523
1524         #[test]
1525         fn penalizes_without_channel_failures() {
1526                 let scorer = Scorer::new(ScoringParameters {
1527                         base_penalty_msat: 1_000,
1528                         failure_penalty_msat: 512,
1529                         failure_penalty_half_life: Duration::from_secs(1),
1530                         overuse_penalty_start_1024th: 1024,
1531                         overuse_penalty_msat_per_1024th: 0,
1532                 });
1533                 let source = source_node_id();
1534                 let target = target_node_id();
1535                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1536
1537                 SinceEpoch::advance(Duration::from_secs(1));
1538                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1539         }
1540
1541         #[test]
1542         fn accumulates_channel_failure_penalties() {
1543                 let mut scorer = Scorer::new(ScoringParameters {
1544                         base_penalty_msat: 1_000,
1545                         failure_penalty_msat: 64,
1546                         failure_penalty_half_life: Duration::from_secs(10),
1547                         overuse_penalty_start_1024th: 1024,
1548                         overuse_penalty_msat_per_1024th: 0,
1549                 });
1550                 let source = source_node_id();
1551                 let target = target_node_id();
1552                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1553
1554                 scorer.payment_path_failed(&[], 42);
1555                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_064);
1556
1557                 scorer.payment_path_failed(&[], 42);
1558                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_128);
1559
1560                 scorer.payment_path_failed(&[], 42);
1561                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_192);
1562         }
1563
1564         #[test]
1565         fn decays_channel_failure_penalties_over_time() {
1566                 let mut scorer = Scorer::new(ScoringParameters {
1567                         base_penalty_msat: 1_000,
1568                         failure_penalty_msat: 512,
1569                         failure_penalty_half_life: Duration::from_secs(10),
1570                         overuse_penalty_start_1024th: 1024,
1571                         overuse_penalty_msat_per_1024th: 0,
1572                 });
1573                 let source = source_node_id();
1574                 let target = target_node_id();
1575                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1576
1577                 scorer.payment_path_failed(&[], 42);
1578                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1579
1580                 SinceEpoch::advance(Duration::from_secs(9));
1581                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1582
1583                 SinceEpoch::advance(Duration::from_secs(1));
1584                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1585
1586                 SinceEpoch::advance(Duration::from_secs(10 * 8));
1587                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_001);
1588
1589                 SinceEpoch::advance(Duration::from_secs(10));
1590                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1591
1592                 SinceEpoch::advance(Duration::from_secs(10));
1593                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1594         }
1595
1596         #[test]
1597         fn decays_channel_failure_penalties_without_shift_overflow() {
1598                 let mut scorer = Scorer::new(ScoringParameters {
1599                         base_penalty_msat: 1_000,
1600                         failure_penalty_msat: 512,
1601                         failure_penalty_half_life: Duration::from_secs(10),
1602                         overuse_penalty_start_1024th: 1024,
1603                         overuse_penalty_msat_per_1024th: 0,
1604                 });
1605                 let source = source_node_id();
1606                 let target = target_node_id();
1607                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1608
1609                 scorer.payment_path_failed(&[], 42);
1610                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1611
1612                 // An unchecked right shift 64 bits or more in ChannelFailure::decayed_penalty_msat would
1613                 // cause an overflow.
1614                 SinceEpoch::advance(Duration::from_secs(10 * 64));
1615                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1616
1617                 SinceEpoch::advance(Duration::from_secs(10));
1618                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1619         }
1620
1621         #[test]
1622         fn accumulates_channel_failure_penalties_after_decay() {
1623                 let mut scorer = Scorer::new(ScoringParameters {
1624                         base_penalty_msat: 1_000,
1625                         failure_penalty_msat: 512,
1626                         failure_penalty_half_life: Duration::from_secs(10),
1627                         overuse_penalty_start_1024th: 1024,
1628                         overuse_penalty_msat_per_1024th: 0,
1629                 });
1630                 let source = source_node_id();
1631                 let target = target_node_id();
1632                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1633
1634                 scorer.payment_path_failed(&[], 42);
1635                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1636
1637                 SinceEpoch::advance(Duration::from_secs(10));
1638                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1639
1640                 scorer.payment_path_failed(&[], 42);
1641                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_768);
1642
1643                 SinceEpoch::advance(Duration::from_secs(10));
1644                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_384);
1645         }
1646
1647         #[test]
1648         fn reduces_channel_failure_penalties_after_success() {
1649                 let mut scorer = Scorer::new(ScoringParameters {
1650                         base_penalty_msat: 1_000,
1651                         failure_penalty_msat: 512,
1652                         failure_penalty_half_life: Duration::from_secs(10),
1653                         overuse_penalty_start_1024th: 1024,
1654                         overuse_penalty_msat_per_1024th: 0,
1655                 });
1656                 let source = source_node_id();
1657                 let target = target_node_id();
1658                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1659
1660                 scorer.payment_path_failed(&[], 42);
1661                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1662
1663                 SinceEpoch::advance(Duration::from_secs(10));
1664                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1665
1666                 let hop = RouteHop {
1667                         pubkey: PublicKey::from_slice(target.as_slice()).unwrap(),
1668                         node_features: NodeFeatures::known(),
1669                         short_channel_id: 42,
1670                         channel_features: ChannelFeatures::known(),
1671                         fee_msat: 1,
1672                         cltv_expiry_delta: 18,
1673                 };
1674                 scorer.payment_path_successful(&[&hop]);
1675                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_128);
1676
1677                 SinceEpoch::advance(Duration::from_secs(10));
1678                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_064);
1679         }
1680
1681         #[test]
1682         fn restores_persisted_channel_failure_penalties() {
1683                 let mut scorer = Scorer::new(ScoringParameters {
1684                         base_penalty_msat: 1_000,
1685                         failure_penalty_msat: 512,
1686                         failure_penalty_half_life: Duration::from_secs(10),
1687                         overuse_penalty_start_1024th: 1024,
1688                         overuse_penalty_msat_per_1024th: 0,
1689                 });
1690                 let source = source_node_id();
1691                 let target = target_node_id();
1692
1693                 scorer.payment_path_failed(&[], 42);
1694                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1695
1696                 SinceEpoch::advance(Duration::from_secs(10));
1697                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1698
1699                 scorer.payment_path_failed(&[], 43);
1700                 assert_eq!(scorer.channel_penalty_msat(43, 1, 1, &source, &target), 1_512);
1701
1702                 let mut serialized_scorer = Vec::new();
1703                 scorer.write(&mut serialized_scorer).unwrap();
1704
1705                 let deserialized_scorer = <Scorer>::read(&mut io::Cursor::new(&serialized_scorer)).unwrap();
1706                 assert_eq!(deserialized_scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1707                 assert_eq!(deserialized_scorer.channel_penalty_msat(43, 1, 1, &source, &target), 1_512);
1708         }
1709
1710         #[test]
1711         fn decays_persisted_channel_failure_penalties() {
1712                 let mut scorer = Scorer::new(ScoringParameters {
1713                         base_penalty_msat: 1_000,
1714                         failure_penalty_msat: 512,
1715                         failure_penalty_half_life: Duration::from_secs(10),
1716                         overuse_penalty_start_1024th: 1024,
1717                         overuse_penalty_msat_per_1024th: 0,
1718                 });
1719                 let source = source_node_id();
1720                 let target = target_node_id();
1721
1722                 scorer.payment_path_failed(&[], 42);
1723                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1724
1725                 let mut serialized_scorer = Vec::new();
1726                 scorer.write(&mut serialized_scorer).unwrap();
1727
1728                 SinceEpoch::advance(Duration::from_secs(10));
1729
1730                 let deserialized_scorer = <Scorer>::read(&mut io::Cursor::new(&serialized_scorer)).unwrap();
1731                 assert_eq!(deserialized_scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1732
1733                 SinceEpoch::advance(Duration::from_secs(10));
1734                 assert_eq!(deserialized_scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_128);
1735         }
1736
1737         #[test]
1738         fn charges_per_1024th_penalty() {
1739                 let scorer = Scorer::new(ScoringParameters {
1740                         base_penalty_msat: 0,
1741                         failure_penalty_msat: 0,
1742                         failure_penalty_half_life: Duration::from_secs(0),
1743                         overuse_penalty_start_1024th: 256,
1744                         overuse_penalty_msat_per_1024th: 100,
1745                 });
1746                 let source = source_node_id();
1747                 let target = target_node_id();
1748
1749                 assert_eq!(scorer.channel_penalty_msat(42, 1_000, 1_024_000, &source, &target), 0);
1750                 assert_eq!(scorer.channel_penalty_msat(42, 256_999, 1_024_000, &source, &target), 0);
1751                 assert_eq!(scorer.channel_penalty_msat(42, 257_000, 1_024_000, &source, &target), 100);
1752                 assert_eq!(scorer.channel_penalty_msat(42, 258_000, 1_024_000, &source, &target), 200);
1753                 assert_eq!(scorer.channel_penalty_msat(42, 512_000, 1_024_000, &source, &target), 256 * 100);
1754         }
1755
1756         // `ProbabilisticScorer` tests
1757
1758         /// A probabilistic scorer for testing with time that can be manually advanced.
1759         type ProbabilisticScorer<'a> = ProbabilisticScorerUsingTime::<&'a NetworkGraph, &'a TestLogger, SinceEpoch>;
1760
1761         fn sender_privkey() -> SecretKey {
1762                 SecretKey::from_slice(&[41; 32]).unwrap()
1763         }
1764
1765         fn recipient_privkey() -> SecretKey {
1766                 SecretKey::from_slice(&[45; 32]).unwrap()
1767         }
1768
1769         fn sender_pubkey() -> PublicKey {
1770                 let secp_ctx = Secp256k1::new();
1771                 PublicKey::from_secret_key(&secp_ctx, &sender_privkey())
1772         }
1773
1774         fn recipient_pubkey() -> PublicKey {
1775                 let secp_ctx = Secp256k1::new();
1776                 PublicKey::from_secret_key(&secp_ctx, &recipient_privkey())
1777         }
1778
1779         fn sender_node_id() -> NodeId {
1780                 NodeId::from_pubkey(&sender_pubkey())
1781         }
1782
1783         fn recipient_node_id() -> NodeId {
1784                 NodeId::from_pubkey(&recipient_pubkey())
1785         }
1786
1787         fn network_graph() -> NetworkGraph {
1788                 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1789                 let mut network_graph = NetworkGraph::new(genesis_hash);
1790                 add_channel(&mut network_graph, 42, source_privkey(), target_privkey());
1791                 add_channel(&mut network_graph, 43, target_privkey(), recipient_privkey());
1792
1793                 network_graph
1794         }
1795
1796         fn add_channel(
1797                 network_graph: &mut NetworkGraph, short_channel_id: u64, node_1_key: SecretKey,
1798                 node_2_key: SecretKey
1799         ) {
1800                 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1801                 let node_1_secret = &SecretKey::from_slice(&[39; 32]).unwrap();
1802                 let node_2_secret = &SecretKey::from_slice(&[40; 32]).unwrap();
1803                 let secp_ctx = Secp256k1::new();
1804                 let unsigned_announcement = UnsignedChannelAnnouncement {
1805                         features: ChannelFeatures::known(),
1806                         chain_hash: genesis_hash,
1807                         short_channel_id,
1808                         node_id_1: PublicKey::from_secret_key(&secp_ctx, &node_1_key),
1809                         node_id_2: PublicKey::from_secret_key(&secp_ctx, &node_2_key),
1810                         bitcoin_key_1: PublicKey::from_secret_key(&secp_ctx, &node_1_secret),
1811                         bitcoin_key_2: PublicKey::from_secret_key(&secp_ctx, &node_2_secret),
1812                         excess_data: Vec::new(),
1813                 };
1814                 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
1815                 let signed_announcement = ChannelAnnouncement {
1816                         node_signature_1: secp_ctx.sign(&msghash, &node_1_key),
1817                         node_signature_2: secp_ctx.sign(&msghash, &node_2_key),
1818                         bitcoin_signature_1: secp_ctx.sign(&msghash, &node_1_secret),
1819                         bitcoin_signature_2: secp_ctx.sign(&msghash, &node_2_secret),
1820                         contents: unsigned_announcement,
1821                 };
1822                 let chain_source: Option<&::util::test_utils::TestChainSource> = None;
1823                 network_graph.update_channel_from_announcement(
1824                         &signed_announcement, &chain_source, &secp_ctx).unwrap();
1825                 update_channel(network_graph, short_channel_id, node_1_key, 0);
1826                 update_channel(network_graph, short_channel_id, node_2_key, 1);
1827         }
1828
1829         fn update_channel(
1830                 network_graph: &mut NetworkGraph, short_channel_id: u64, node_key: SecretKey, flags: u8
1831         ) {
1832                 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1833                 let secp_ctx = Secp256k1::new();
1834                 let unsigned_update = UnsignedChannelUpdate {
1835                         chain_hash: genesis_hash,
1836                         short_channel_id,
1837                         timestamp: 100,
1838                         flags,
1839                         cltv_expiry_delta: 18,
1840                         htlc_minimum_msat: 0,
1841                         htlc_maximum_msat: OptionalField::Present(1_000),
1842                         fee_base_msat: 1,
1843                         fee_proportional_millionths: 0,
1844                         excess_data: Vec::new(),
1845                 };
1846                 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_update.encode()[..])[..]);
1847                 let signed_update = ChannelUpdate {
1848                         signature: secp_ctx.sign(&msghash, &node_key),
1849                         contents: unsigned_update,
1850                 };
1851                 network_graph.update_channel(&signed_update, &secp_ctx).unwrap();
1852         }
1853
1854         fn payment_path_for_amount(amount_msat: u64) -> Vec<RouteHop> {
1855                 vec![
1856                         RouteHop {
1857                                 pubkey: source_pubkey(),
1858                                 node_features: NodeFeatures::known(),
1859                                 short_channel_id: 41,
1860                                 channel_features: ChannelFeatures::known(),
1861                                 fee_msat: 1,
1862                                 cltv_expiry_delta: 18,
1863                         },
1864                         RouteHop {
1865                                 pubkey: target_pubkey(),
1866                                 node_features: NodeFeatures::known(),
1867                                 short_channel_id: 42,
1868                                 channel_features: ChannelFeatures::known(),
1869                                 fee_msat: 2,
1870                                 cltv_expiry_delta: 18,
1871                         },
1872                         RouteHop {
1873                                 pubkey: recipient_pubkey(),
1874                                 node_features: NodeFeatures::known(),
1875                                 short_channel_id: 43,
1876                                 channel_features: ChannelFeatures::known(),
1877                                 fee_msat: amount_msat,
1878                                 cltv_expiry_delta: 18,
1879                         },
1880                 ]
1881         }
1882
1883         #[test]
1884         fn liquidity_bounds_directed_from_lowest_node_id() {
1885                 let logger = TestLogger::new();
1886                 let last_updated = SinceEpoch::now();
1887                 let network_graph = network_graph();
1888                 let params = ProbabilisticScoringParameters::default();
1889                 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1890                         .with_channel(42,
1891                                 ChannelLiquidity {
1892                                         min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated
1893                                 })
1894                         .with_channel(43,
1895                                 ChannelLiquidity {
1896                                         min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated
1897                                 });
1898                 let source = source_node_id();
1899                 let target = target_node_id();
1900                 let recipient = recipient_node_id();
1901                 assert!(source > target);
1902                 assert!(target < recipient);
1903
1904                 // Update minimum liquidity.
1905
1906                 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
1907                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1908                         .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1909                 assert_eq!(liquidity.min_liquidity_msat(), 100);
1910                 assert_eq!(liquidity.max_liquidity_msat(), 300);
1911
1912                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1913                         .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1914                 assert_eq!(liquidity.min_liquidity_msat(), 700);
1915                 assert_eq!(liquidity.max_liquidity_msat(), 900);
1916
1917                 scorer.channel_liquidities.get_mut(&42).unwrap()
1918                         .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
1919                         .set_min_liquidity_msat(200);
1920
1921                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1922                         .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1923                 assert_eq!(liquidity.min_liquidity_msat(), 200);
1924                 assert_eq!(liquidity.max_liquidity_msat(), 300);
1925
1926                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1927                         .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1928                 assert_eq!(liquidity.min_liquidity_msat(), 700);
1929                 assert_eq!(liquidity.max_liquidity_msat(), 800);
1930
1931                 // Update maximum liquidity.
1932
1933                 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1934                         .as_directed(&target, &recipient, 1_000, liquidity_offset_half_life);
1935                 assert_eq!(liquidity.min_liquidity_msat(), 700);
1936                 assert_eq!(liquidity.max_liquidity_msat(), 900);
1937
1938                 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1939                         .as_directed(&recipient, &target, 1_000, liquidity_offset_half_life);
1940                 assert_eq!(liquidity.min_liquidity_msat(), 100);
1941                 assert_eq!(liquidity.max_liquidity_msat(), 300);
1942
1943                 scorer.channel_liquidities.get_mut(&43).unwrap()
1944                         .as_directed_mut(&target, &recipient, 1_000, liquidity_offset_half_life)
1945                         .set_max_liquidity_msat(200);
1946
1947                 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1948                         .as_directed(&target, &recipient, 1_000, liquidity_offset_half_life);
1949                 assert_eq!(liquidity.min_liquidity_msat(), 0);
1950                 assert_eq!(liquidity.max_liquidity_msat(), 200);
1951
1952                 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1953                         .as_directed(&recipient, &target, 1_000, liquidity_offset_half_life);
1954                 assert_eq!(liquidity.min_liquidity_msat(), 800);
1955                 assert_eq!(liquidity.max_liquidity_msat(), 1000);
1956         }
1957
1958         #[test]
1959         fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() {
1960                 let logger = TestLogger::new();
1961                 let last_updated = SinceEpoch::now();
1962                 let network_graph = network_graph();
1963                 let params = ProbabilisticScoringParameters::default();
1964                 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1965                         .with_channel(42,
1966                                 ChannelLiquidity {
1967                                         min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated
1968                                 });
1969                 let source = source_node_id();
1970                 let target = target_node_id();
1971                 assert!(source > target);
1972
1973                 // Check initial bounds.
1974                 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
1975                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1976                         .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1977                 assert_eq!(liquidity.min_liquidity_msat(), 400);
1978                 assert_eq!(liquidity.max_liquidity_msat(), 800);
1979
1980                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1981                         .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1982                 assert_eq!(liquidity.min_liquidity_msat(), 200);
1983                 assert_eq!(liquidity.max_liquidity_msat(), 600);
1984
1985                 // Reset from source to target.
1986                 scorer.channel_liquidities.get_mut(&42).unwrap()
1987                         .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
1988                         .set_min_liquidity_msat(900);
1989
1990                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1991                         .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1992                 assert_eq!(liquidity.min_liquidity_msat(), 900);
1993                 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1994
1995                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1996                         .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1997                 assert_eq!(liquidity.min_liquidity_msat(), 0);
1998                 assert_eq!(liquidity.max_liquidity_msat(), 100);
1999
2000                 // Reset from target to source.
2001                 scorer.channel_liquidities.get_mut(&42).unwrap()
2002                         .as_directed_mut(&target, &source, 1_000, liquidity_offset_half_life)
2003                         .set_min_liquidity_msat(400);
2004
2005                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2006                         .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
2007                 assert_eq!(liquidity.min_liquidity_msat(), 0);
2008                 assert_eq!(liquidity.max_liquidity_msat(), 600);
2009
2010                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2011                         .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
2012                 assert_eq!(liquidity.min_liquidity_msat(), 400);
2013                 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2014         }
2015
2016         #[test]
2017         fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() {
2018                 let logger = TestLogger::new();
2019                 let last_updated = SinceEpoch::now();
2020                 let network_graph = network_graph();
2021                 let params = ProbabilisticScoringParameters::default();
2022                 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
2023                         .with_channel(42,
2024                                 ChannelLiquidity {
2025                                         min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated
2026                                 });
2027                 let source = source_node_id();
2028                 let target = target_node_id();
2029                 assert!(source > target);
2030
2031                 // Check initial bounds.
2032                 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
2033                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2034                         .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
2035                 assert_eq!(liquidity.min_liquidity_msat(), 400);
2036                 assert_eq!(liquidity.max_liquidity_msat(), 800);
2037
2038                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2039                         .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
2040                 assert_eq!(liquidity.min_liquidity_msat(), 200);
2041                 assert_eq!(liquidity.max_liquidity_msat(), 600);
2042
2043                 // Reset from source to target.
2044                 scorer.channel_liquidities.get_mut(&42).unwrap()
2045                         .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
2046                         .set_max_liquidity_msat(300);
2047
2048                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2049                         .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
2050                 assert_eq!(liquidity.min_liquidity_msat(), 0);
2051                 assert_eq!(liquidity.max_liquidity_msat(), 300);
2052
2053                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2054                         .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
2055                 assert_eq!(liquidity.min_liquidity_msat(), 700);
2056                 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2057
2058                 // Reset from target to source.
2059                 scorer.channel_liquidities.get_mut(&42).unwrap()
2060                         .as_directed_mut(&target, &source, 1_000, liquidity_offset_half_life)
2061                         .set_max_liquidity_msat(600);
2062
2063                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2064                         .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
2065                 assert_eq!(liquidity.min_liquidity_msat(), 400);
2066                 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2067
2068                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2069                         .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
2070                 assert_eq!(liquidity.min_liquidity_msat(), 0);
2071                 assert_eq!(liquidity.max_liquidity_msat(), 600);
2072         }
2073
2074         #[test]
2075         fn increased_penalty_nearing_liquidity_upper_bound() {
2076                 let logger = TestLogger::new();
2077                 let network_graph = network_graph();
2078                 let params = ProbabilisticScoringParameters {
2079                         liquidity_penalty_multiplier_msat: 1_000,
2080                         ..ProbabilisticScoringParameters::zero_penalty()
2081                 };
2082                 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2083                 let source = source_node_id();
2084                 let target = target_node_id();
2085
2086                 assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024_000, &source, &target), 0);
2087                 assert_eq!(scorer.channel_penalty_msat(42, 10_240, 1_024_000, &source, &target), 0);
2088                 assert_eq!(scorer.channel_penalty_msat(42, 102_400, 1_024_000, &source, &target), 47);
2089                 assert_eq!(scorer.channel_penalty_msat(42, 1_024_000, 1_024_000, &source, &target), 2_000);
2090
2091                 assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 58);
2092                 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 125);
2093                 assert_eq!(scorer.channel_penalty_msat(42, 374, 1_024, &source, &target), 198);
2094                 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 300);
2095                 assert_eq!(scorer.channel_penalty_msat(42, 640, 1_024, &source, &target), 425);
2096                 assert_eq!(scorer.channel_penalty_msat(42, 768, 1_024, &source, &target), 602);
2097                 assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), 902);
2098         }
2099
2100         #[test]
2101         fn constant_penalty_outside_liquidity_bounds() {
2102                 let logger = TestLogger::new();
2103                 let last_updated = SinceEpoch::now();
2104                 let network_graph = network_graph();
2105                 let params = ProbabilisticScoringParameters {
2106                         liquidity_penalty_multiplier_msat: 1_000,
2107                         ..ProbabilisticScoringParameters::zero_penalty()
2108                 };
2109                 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
2110                         .with_channel(42,
2111                                 ChannelLiquidity {
2112                                         min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40, last_updated
2113                                 });
2114                 let source = source_node_id();
2115                 let target = target_node_id();
2116
2117                 assert_eq!(scorer.channel_penalty_msat(42, 39, 100, &source, &target), 0);
2118                 assert_ne!(scorer.channel_penalty_msat(42, 50, 100, &source, &target), 0);
2119                 assert_ne!(scorer.channel_penalty_msat(42, 50, 100, &source, &target), u64::max_value());
2120                 assert_eq!(scorer.channel_penalty_msat(42, 61, 100, &source, &target), u64::max_value());
2121         }
2122
2123         #[test]
2124         fn does_not_further_penalize_own_channel() {
2125                 let logger = TestLogger::new();
2126                 let network_graph = network_graph();
2127                 let params = ProbabilisticScoringParameters {
2128                         liquidity_penalty_multiplier_msat: 1_000,
2129                         ..ProbabilisticScoringParameters::zero_penalty()
2130                 };
2131                 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2132                 let sender = sender_node_id();
2133                 let source = source_node_id();
2134                 let failed_path = payment_path_for_amount(500);
2135                 let successful_path = payment_path_for_amount(200);
2136
2137                 assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 301);
2138
2139                 scorer.payment_path_failed(&failed_path.iter().collect::<Vec<_>>(), 41);
2140                 assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 301);
2141
2142                 scorer.payment_path_successful(&successful_path.iter().collect::<Vec<_>>());
2143                 assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 301);
2144         }
2145
2146         #[test]
2147         fn sets_liquidity_lower_bound_on_downstream_failure() {
2148                 let logger = TestLogger::new();
2149                 let network_graph = network_graph();
2150                 let params = ProbabilisticScoringParameters {
2151                         liquidity_penalty_multiplier_msat: 1_000,
2152                         ..ProbabilisticScoringParameters::zero_penalty()
2153                 };
2154                 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2155                 let source = source_node_id();
2156                 let target = target_node_id();
2157                 let path = payment_path_for_amount(500);
2158
2159                 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 128);
2160                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 301);
2161                 assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 602);
2162
2163                 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 43);
2164
2165                 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 0);
2166                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 0);
2167                 assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 300);
2168         }
2169
2170         #[test]
2171         fn sets_liquidity_upper_bound_on_failure() {
2172                 let logger = TestLogger::new();
2173                 let network_graph = network_graph();
2174                 let params = ProbabilisticScoringParameters {
2175                         liquidity_penalty_multiplier_msat: 1_000,
2176                         ..ProbabilisticScoringParameters::zero_penalty()
2177                 };
2178                 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2179                 let source = source_node_id();
2180                 let target = target_node_id();
2181                 let path = payment_path_for_amount(500);
2182
2183                 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 128);
2184                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 301);
2185                 assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 602);
2186
2187                 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 42);
2188
2189                 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 300);
2190                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), u64::max_value());
2191                 assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), u64::max_value());
2192         }
2193
2194         #[test]
2195         fn reduces_liquidity_upper_bound_along_path_on_success() {
2196                 let logger = TestLogger::new();
2197                 let network_graph = network_graph();
2198                 let params = ProbabilisticScoringParameters {
2199                         liquidity_penalty_multiplier_msat: 1_000,
2200                         ..ProbabilisticScoringParameters::zero_penalty()
2201                 };
2202                 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2203                 let sender = sender_node_id();
2204                 let source = source_node_id();
2205                 let target = target_node_id();
2206                 let recipient = recipient_node_id();
2207                 let path = payment_path_for_amount(500);
2208
2209                 assert_eq!(scorer.channel_penalty_msat(41, 250, 1_000, &sender, &source), 128);
2210                 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 128);
2211                 assert_eq!(scorer.channel_penalty_msat(43, 250, 1_000, &target, &recipient), 128);
2212
2213                 scorer.payment_path_successful(&path.iter().collect::<Vec<_>>());
2214
2215                 assert_eq!(scorer.channel_penalty_msat(41, 250, 1_000, &sender, &source), 128);
2216                 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 300);
2217                 assert_eq!(scorer.channel_penalty_msat(43, 250, 1_000, &target, &recipient), 300);
2218         }
2219
2220         #[test]
2221         fn decays_liquidity_bounds_over_time() {
2222                 let logger = TestLogger::new();
2223                 let network_graph = network_graph();
2224                 let params = ProbabilisticScoringParameters {
2225                         liquidity_penalty_multiplier_msat: 1_000,
2226                         liquidity_offset_half_life: Duration::from_secs(10),
2227                         ..ProbabilisticScoringParameters::zero_penalty()
2228                 };
2229                 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2230                 let source = source_node_id();
2231                 let target = target_node_id();
2232
2233                 assert_eq!(scorer.channel_penalty_msat(42, 0, 1_024, &source, &target), 0);
2234                 assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024, &source, &target), 2_000);
2235
2236                 scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::<Vec<_>>(), 42);
2237                 scorer.payment_path_failed(&payment_path_for_amount(128).iter().collect::<Vec<_>>(), 43);
2238
2239                 assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 0);
2240                 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 93);
2241                 assert_eq!(scorer.channel_penalty_msat(42, 768, 1_024, &source, &target), 1_479);
2242                 assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), u64::max_value());
2243
2244                 SinceEpoch::advance(Duration::from_secs(9));
2245                 assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 0);
2246                 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 93);
2247                 assert_eq!(scorer.channel_penalty_msat(42, 768, 1_024, &source, &target), 1_479);
2248                 assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), u64::max_value());
2249
2250                 SinceEpoch::advance(Duration::from_secs(1));
2251                 assert_eq!(scorer.channel_penalty_msat(42, 64, 1_024, &source, &target), 0);
2252                 assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 34);
2253                 assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), 1_970);
2254                 assert_eq!(scorer.channel_penalty_msat(42, 960, 1_024, &source, &target), u64::max_value());
2255
2256                 // Fully decay liquidity lower bound.
2257                 SinceEpoch::advance(Duration::from_secs(10 * 7));
2258                 assert_eq!(scorer.channel_penalty_msat(42, 0, 1_024, &source, &target), 0);
2259                 assert_eq!(scorer.channel_penalty_msat(42, 1, 1_024, &source, &target), 0);
2260                 assert_eq!(scorer.channel_penalty_msat(42, 1_023, 1_024, &source, &target), 2_000);
2261                 assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024, &source, &target), 2_000);
2262
2263                 // Fully decay liquidity upper bound.
2264                 SinceEpoch::advance(Duration::from_secs(10));
2265                 assert_eq!(scorer.channel_penalty_msat(42, 0, 1_024, &source, &target), 0);
2266                 assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024, &source, &target), 2_000);
2267
2268                 SinceEpoch::advance(Duration::from_secs(10));
2269                 assert_eq!(scorer.channel_penalty_msat(42, 0, 1_024, &source, &target), 0);
2270                 assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024, &source, &target), 2_000);
2271         }
2272
2273         #[test]
2274         fn decays_liquidity_bounds_without_shift_overflow() {
2275                 let logger = TestLogger::new();
2276                 let network_graph = network_graph();
2277                 let params = ProbabilisticScoringParameters {
2278                         liquidity_penalty_multiplier_msat: 1_000,
2279                         liquidity_offset_half_life: Duration::from_secs(10),
2280                         ..ProbabilisticScoringParameters::zero_penalty()
2281                 };
2282                 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2283                 let source = source_node_id();
2284                 let target = target_node_id();
2285                 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 125);
2286
2287                 scorer.payment_path_failed(&payment_path_for_amount(512).iter().collect::<Vec<_>>(), 42);
2288                 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 281);
2289
2290                 // An unchecked right shift 64 bits or more in DirectedChannelLiquidity::decayed_offset_msat
2291                 // would cause an overflow.
2292                 SinceEpoch::advance(Duration::from_secs(10 * 64));
2293                 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 125);
2294
2295                 SinceEpoch::advance(Duration::from_secs(10));
2296                 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 125);
2297         }
2298
2299         #[test]
2300         fn restricts_liquidity_bounds_after_decay() {
2301                 let logger = TestLogger::new();
2302                 let network_graph = network_graph();
2303                 let params = ProbabilisticScoringParameters {
2304                         liquidity_penalty_multiplier_msat: 1_000,
2305                         liquidity_offset_half_life: Duration::from_secs(10),
2306                         ..ProbabilisticScoringParameters::zero_penalty()
2307                 };
2308                 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2309                 let source = source_node_id();
2310                 let target = target_node_id();
2311
2312                 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 300);
2313
2314                 // More knowledge gives higher confidence (256, 768), meaning a lower penalty.
2315                 scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::<Vec<_>>(), 42);
2316                 scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::<Vec<_>>(), 43);
2317                 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 281);
2318
2319                 // Decaying knowledge gives less confidence (128, 896), meaning a higher penalty.
2320                 SinceEpoch::advance(Duration::from_secs(10));
2321                 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 291);
2322
2323                 // Reducing the upper bound gives more confidence (128, 832) that the payment amount (512)
2324                 // is closer to the upper bound, meaning a higher penalty.
2325                 scorer.payment_path_successful(&payment_path_for_amount(64).iter().collect::<Vec<_>>());
2326                 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 331);
2327
2328                 // Increasing the lower bound gives more confidence (256, 832) that the payment amount (512)
2329                 // is closer to the lower bound, meaning a lower penalty.
2330                 scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::<Vec<_>>(), 43);
2331                 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 245);
2332
2333                 // Further decaying affects the lower bound more than the upper bound (128, 928).
2334                 SinceEpoch::advance(Duration::from_secs(10));
2335                 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 280);
2336         }
2337
2338         #[test]
2339         fn restores_persisted_liquidity_bounds() {
2340                 let logger = TestLogger::new();
2341                 let network_graph = network_graph();
2342                 let params = ProbabilisticScoringParameters {
2343                         liquidity_penalty_multiplier_msat: 1_000,
2344                         liquidity_offset_half_life: Duration::from_secs(10),
2345                         ..ProbabilisticScoringParameters::zero_penalty()
2346                 };
2347                 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2348                 let source = source_node_id();
2349                 let target = target_node_id();
2350
2351                 scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
2352                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), u64::max_value());
2353
2354                 SinceEpoch::advance(Duration::from_secs(10));
2355                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 473);
2356
2357                 scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::<Vec<_>>(), 43);
2358                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300);
2359
2360                 let mut serialized_scorer = Vec::new();
2361                 scorer.write(&mut serialized_scorer).unwrap();
2362
2363                 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
2364                 let deserialized_scorer =
2365                         <ProbabilisticScorer>::read(&mut serialized_scorer, (params, &network_graph, &logger)).unwrap();
2366                 assert_eq!(deserialized_scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300);
2367         }
2368
2369         #[test]
2370         fn decays_persisted_liquidity_bounds() {
2371                 let logger = TestLogger::new();
2372                 let network_graph = network_graph();
2373                 let params = ProbabilisticScoringParameters {
2374                         liquidity_penalty_multiplier_msat: 1_000,
2375                         liquidity_offset_half_life: Duration::from_secs(10),
2376                         ..ProbabilisticScoringParameters::zero_penalty()
2377                 };
2378                 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2379                 let source = source_node_id();
2380                 let target = target_node_id();
2381
2382                 scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
2383                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), u64::max_value());
2384
2385                 let mut serialized_scorer = Vec::new();
2386                 scorer.write(&mut serialized_scorer).unwrap();
2387
2388                 SinceEpoch::advance(Duration::from_secs(10));
2389
2390                 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
2391                 let deserialized_scorer =
2392                         <ProbabilisticScorer>::read(&mut serialized_scorer, (params, &network_graph, &logger)).unwrap();
2393                 assert_eq!(deserialized_scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 473);
2394
2395                 scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::<Vec<_>>(), 43);
2396                 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300);
2397
2398                 SinceEpoch::advance(Duration::from_secs(10));
2399                 assert_eq!(deserialized_scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 365);
2400         }
2401
2402         #[test]
2403         fn scores_realistic_payments() {
2404                 // Shows the scores of "realistic" sends of 100k sats over channels of 1-10m sats (with a
2405                 // 50k sat reserve).
2406                 let logger = TestLogger::new();
2407                 let network_graph = network_graph();
2408                 let params = ProbabilisticScoringParameters::default();
2409                 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2410                 let source = source_node_id();
2411                 let target = target_node_id();
2412
2413                 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 950_000_000, &source, &target), 3613);
2414                 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 1_950_000_000, &source, &target), 1977);
2415                 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 2_950_000_000, &source, &target), 1474);
2416                 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 3_950_000_000, &source, &target), 1223);
2417                 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 4_950_000_000, &source, &target), 877);
2418                 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 5_950_000_000, &source, &target), 845);
2419                 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 6_950_000_000, &source, &target), 500);
2420                 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 7_450_000_000, &source, &target), 500);
2421                 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 7_950_000_000, &source, &target), 500);
2422                 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 8_950_000_000, &source, &target), 500);
2423                 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 9_950_000_000, &source, &target), 500);
2424         }
2425
2426         #[test]
2427         fn adds_base_penalty_to_liquidity_penalty() {
2428                 let logger = TestLogger::new();
2429                 let network_graph = network_graph();
2430                 let source = source_node_id();
2431                 let target = target_node_id();
2432
2433                 let params = ProbabilisticScoringParameters {
2434                         liquidity_penalty_multiplier_msat: 1_000,
2435                         ..ProbabilisticScoringParameters::zero_penalty()
2436                 };
2437                 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2438                 assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 58);
2439
2440                 let params = ProbabilisticScoringParameters {
2441                         base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000, ..Default::default()
2442                 };
2443                 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2444                 assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 558);
2445         }
2446
2447         #[test]
2448         fn adds_amount_penalty_to_liquidity_penalty() {
2449                 let logger = TestLogger::new();
2450                 let network_graph = network_graph();
2451                 let source = source_node_id();
2452                 let target = target_node_id();
2453
2454                 let params = ProbabilisticScoringParameters {
2455                         liquidity_penalty_multiplier_msat: 1_000,
2456                         amount_penalty_multiplier_msat: 0,
2457                         ..ProbabilisticScoringParameters::zero_penalty()
2458                 };
2459                 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2460                 assert_eq!(scorer.channel_penalty_msat(42, 512_000, 1_024_000, &source, &target), 300);
2461
2462                 let params = ProbabilisticScoringParameters {
2463                         liquidity_penalty_multiplier_msat: 1_000,
2464                         amount_penalty_multiplier_msat: 256,
2465                         ..ProbabilisticScoringParameters::zero_penalty()
2466                 };
2467                 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2468                 assert_eq!(scorer.channel_penalty_msat(42, 512_000, 1_024_000, &source, &target), 337);
2469         }
2470
2471         #[test]
2472         fn calculates_log10_without_overflowing_u64_max_value() {
2473                 let logger = TestLogger::new();
2474                 let network_graph = network_graph();
2475                 let source = source_node_id();
2476                 let target = target_node_id();
2477
2478                 let params = ProbabilisticScoringParameters {
2479                         liquidity_penalty_multiplier_msat: 40_000,
2480                         ..ProbabilisticScoringParameters::zero_penalty()
2481                 };
2482                 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2483                 assert_eq!(
2484                         scorer.channel_penalty_msat(42, u64::max_value(), u64::max_value(), &source, &target),
2485                         80_000,
2486                 );
2487         }
2488 }