33c868a07c3a5845764ced38cf058f2c26eb98bc
[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 [`ScoreLookUp`] implementation is not needed.
14 //!
15 //! # Example
16 //!
17 //! ```
18 //! # extern crate bitcoin;
19 //! #
20 //! # use lightning::routing::gossip::NetworkGraph;
21 //! # use lightning::routing::router::{RouteParameters, find_route};
22 //! # use lightning::routing::scoring::{ProbabilisticScorer, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters};
23 //! # use lightning::sign::KeysManager;
24 //! # use lightning::util::logger::{Logger, Record};
25 //! # use bitcoin::secp256k1::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<&FakeLogger>) {
32 //! # let logger = FakeLogger {};
33 //! #
34 //! // Use the default channel penalties.
35 //! let params = ProbabilisticScoringFeeParameters::default();
36 //! let decay_params = ProbabilisticScoringDecayParameters::default();
37 //! let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
38 //!
39 //! // Or use custom channel penalties.
40 //! let params = ProbabilisticScoringFeeParameters {
41 //!     liquidity_penalty_multiplier_msat: 2 * 1000,
42 //!     ..ProbabilisticScoringFeeParameters::default()
43 //! };
44 //! let decay_params = ProbabilisticScoringDecayParameters::default();
45 //! let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
46 //! # let random_seed_bytes = [42u8; 32];
47 //!
48 //! let route = find_route(&payer, &route_params, &network_graph, None, &logger, &scorer, &params, &random_seed_bytes);
49 //! # }
50 //! ```
51 //!
52 //! # Note
53 //!
54 //! Persisting when built with feature `no-std` and restoring without it, or vice versa, uses
55 //! different types and thus is undefined.
56 //!
57 //! [`find_route`]: crate::routing::router::find_route
58
59 use crate::ln::msgs::DecodeError;
60 use crate::routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId};
61 use crate::routing::router::{Path, CandidateRouteHop};
62 use crate::util::ser::{Readable, ReadableArgs, Writeable, Writer};
63 use crate::util::logger::Logger;
64 use crate::util::time::Time;
65
66 use crate::prelude::*;
67 use core::{cmp, fmt};
68 use core::cell::{RefCell, RefMut, Ref};
69 use core::convert::TryInto;
70 use core::ops::{Deref, DerefMut};
71 use core::time::Duration;
72 use crate::io::{self, Read};
73 use crate::sync::{Mutex, MutexGuard, RwLock, RwLockReadGuard, RwLockWriteGuard};
74
75 /// We define Score ever-so-slightly differently based on whether we are being built for C bindings
76 /// or not. For users, `LockableScore` must somehow be writeable to disk. For Rust users, this is
77 /// no problem - you move a `Score` that implements `Writeable` into a `Mutex`, lock it, and now
78 /// you have the original, concrete, `Score` type, which presumably implements `Writeable`.
79 ///
80 /// For C users, once you've moved the `Score` into a `LockableScore` all you have after locking it
81 /// is an opaque trait object with an opaque pointer with no type info. Users could take the unsafe
82 /// approach of blindly casting that opaque pointer to a concrete type and calling `Writeable` from
83 /// there, but other languages downstream of the C bindings (e.g. Java) can't even do that.
84 /// Instead, we really want `Score` and `LockableScore` to implement `Writeable` directly, which we
85 /// do here by defining `Score` differently for `cfg(c_bindings)`.
86 macro_rules! define_score { ($($supertrait: path)*) => {
87 /// An interface used to score payment channels for path finding.
88 ///
89 /// `ScoreLookUp` is used to determine the penalty for a given channel.
90 ///
91 /// Scoring is in terms of fees willing to be paid in order to avoid routing through a channel.
92 pub trait ScoreLookUp {
93         /// A configurable type which should contain various passed-in parameters for configuring the scorer,
94         /// on a per-routefinding-call basis through to the scorer methods,
95         /// which are used to determine the parameters for the suitability of channels for use.
96         type ScoreParams;
97         /// Returns the fee in msats willing to be paid to avoid routing `send_amt_msat` through the
98         /// given channel in the direction from `source` to `target`.
99         ///
100         /// The channel's capacity (less any other MPP parts that are also being considered for use in
101         /// the same payment) is given by `capacity_msat`. It may be determined from various sources
102         /// such as a chain data, network gossip, or invoice hints. For invoice hints, a capacity near
103         /// [`u64::max_value`] is given to indicate sufficient capacity for the invoice's full amount.
104         /// Thus, implementations should be overflow-safe.
105         fn channel_penalty_msat(
106                 &self, candidate: &CandidateRouteHop, usage: ChannelUsage, score_params: &Self::ScoreParams
107         ) -> u64;
108 }
109
110 /// `ScoreUpdate` is used to update the scorer's internal state after a payment attempt.
111 pub trait ScoreUpdate {
112         /// Handles updating channel penalties after failing to route through a channel.
113         fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration);
114
115         /// Handles updating channel penalties after successfully routing along a path.
116         fn payment_path_successful(&mut self, path: &Path, duration_since_epoch: Duration);
117
118         /// Handles updating channel penalties after a probe over the given path failed.
119         fn probe_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration);
120
121         /// Handles updating channel penalties after a probe over the given path succeeded.
122         fn probe_successful(&mut self, path: &Path, duration_since_epoch: Duration);
123
124         /// Scorers may wish to reduce their certainty of channel liquidity information over time.
125         /// Thus, this method is provided to allow scorers to observe the passage of time - the holder
126         /// of this object should call this method regularly (generally via the
127         /// `lightning-background-processor` crate).
128         fn decay_liquidity_certainty(&mut self, duration_since_epoch: Duration);
129 }
130
131 /// A trait which can both lookup and update routing channel penalty scores.
132 ///
133 /// This is used in places where both bounds are required and implemented for all types which
134 /// implement [`ScoreLookUp`] and [`ScoreUpdate`].
135 ///
136 /// Bindings users may need to manually implement this for their custom scoring implementations.
137 pub trait Score : ScoreLookUp + ScoreUpdate $(+ $supertrait)* {}
138
139 #[cfg(not(c_bindings))]
140 impl<T: ScoreLookUp + ScoreUpdate $(+ $supertrait)*> Score for T {}
141
142 #[cfg(not(c_bindings))]
143 impl<S: ScoreLookUp, T: Deref<Target=S>> ScoreLookUp for T {
144         type ScoreParams = S::ScoreParams;
145         fn channel_penalty_msat(
146                 &self, candidate: &CandidateRouteHop, usage: ChannelUsage, score_params: &Self::ScoreParams
147         ) -> u64 {
148                 self.deref().channel_penalty_msat(candidate, usage, score_params)
149         }
150 }
151
152 #[cfg(not(c_bindings))]
153 impl<S: ScoreUpdate, T: DerefMut<Target=S>> ScoreUpdate for T {
154         fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) {
155                 self.deref_mut().payment_path_failed(path, short_channel_id, duration_since_epoch)
156         }
157
158         fn payment_path_successful(&mut self, path: &Path, duration_since_epoch: Duration) {
159                 self.deref_mut().payment_path_successful(path, duration_since_epoch)
160         }
161
162         fn probe_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) {
163                 self.deref_mut().probe_failed(path, short_channel_id, duration_since_epoch)
164         }
165
166         fn probe_successful(&mut self, path: &Path, duration_since_epoch: Duration) {
167                 self.deref_mut().probe_successful(path, duration_since_epoch)
168         }
169
170         fn decay_liquidity_certainty(&mut self, duration_since_epoch: Duration) {
171                 self.deref_mut().decay_liquidity_certainty(duration_since_epoch)
172         }
173 }
174 } }
175
176 #[cfg(c_bindings)]
177 define_score!(Writeable);
178
179 #[cfg(not(c_bindings))]
180 define_score!();
181
182 /// A scorer that is accessed under a lock.
183 ///
184 /// Needed so that calls to [`ScoreLookUp::channel_penalty_msat`] in [`find_route`] can be made while
185 /// having shared ownership of a scorer but without requiring internal locking in [`ScoreUpdate`]
186 /// implementations. Internal locking would be detrimental to route finding performance and could
187 /// result in [`ScoreLookUp::channel_penalty_msat`] returning a different value for the same channel.
188 ///
189 /// [`find_route`]: crate::routing::router::find_route
190 pub trait LockableScore<'a> {
191         /// The [`ScoreUpdate`] type.
192         type ScoreUpdate: 'a + ScoreUpdate;
193         /// The [`ScoreLookUp`] type.
194         type ScoreLookUp: 'a + ScoreLookUp;
195
196         /// The write locked [`ScoreUpdate`] type.
197         type WriteLocked: DerefMut<Target = Self::ScoreUpdate> + Sized;
198
199         /// The read locked [`ScoreLookUp`] type.
200         type ReadLocked: Deref<Target = Self::ScoreLookUp> + Sized;
201
202         /// Returns read locked scorer.
203         fn read_lock(&'a self) -> Self::ReadLocked;
204
205         /// Returns write locked scorer.
206         fn write_lock(&'a self) -> Self::WriteLocked;
207 }
208
209 /// Refers to a scorer that is accessible under lock and also writeable to disk
210 ///
211 /// We need this trait to be able to pass in a scorer to `lightning-background-processor` that will enable us to
212 /// use the Persister to persist it.
213 pub trait WriteableScore<'a>: LockableScore<'a> + Writeable {}
214
215 #[cfg(not(c_bindings))]
216 impl<'a, T> WriteableScore<'a> for T where T: LockableScore<'a> + Writeable {}
217 #[cfg(not(c_bindings))]
218 impl<'a, T: Score + 'a> LockableScore<'a> for Mutex<T> {
219         type ScoreUpdate = T;
220         type ScoreLookUp = T;
221
222         type WriteLocked = MutexGuard<'a, Self::ScoreUpdate>;
223         type ReadLocked = MutexGuard<'a, Self::ScoreLookUp>;
224
225         fn read_lock(&'a self) -> Self::ReadLocked {
226                 Mutex::lock(self).unwrap()
227         }
228
229         fn write_lock(&'a self) -> Self::WriteLocked {
230                 Mutex::lock(self).unwrap()
231         }
232 }
233
234 #[cfg(not(c_bindings))]
235 impl<'a, T: Score + 'a> LockableScore<'a> for RefCell<T> {
236         type ScoreUpdate = T;
237         type ScoreLookUp = T;
238
239         type WriteLocked = RefMut<'a, Self::ScoreUpdate>;
240         type ReadLocked = Ref<'a, Self::ScoreLookUp>;
241
242         fn write_lock(&'a self) -> Self::WriteLocked {
243                 self.borrow_mut()
244         }
245
246         fn read_lock(&'a self) -> Self::ReadLocked {
247                 self.borrow()
248         }
249 }
250
251 #[cfg(not(c_bindings))]
252 impl<'a, T: Score + 'a> LockableScore<'a> for RwLock<T> {
253         type ScoreUpdate = T;
254         type ScoreLookUp = T;
255
256         type WriteLocked = RwLockWriteGuard<'a, Self::ScoreLookUp>;
257         type ReadLocked = RwLockReadGuard<'a, Self::ScoreUpdate>;
258
259         fn read_lock(&'a self) -> Self::ReadLocked {
260                 RwLock::read(self).unwrap()
261         }
262
263         fn write_lock(&'a self) -> Self::WriteLocked {
264                 RwLock::write(self).unwrap()
265         }
266 }
267
268 #[cfg(c_bindings)]
269 /// A concrete implementation of [`LockableScore`] which supports multi-threading.
270 pub struct MultiThreadedLockableScore<T: Score> {
271         score: RwLock<T>,
272 }
273
274 #[cfg(c_bindings)]
275 impl<'a, T: Score + 'a> LockableScore<'a> for MultiThreadedLockableScore<T> {
276         type ScoreUpdate = T;
277         type ScoreLookUp = T;
278         type WriteLocked = MultiThreadedScoreLockWrite<'a, Self::ScoreUpdate>;
279         type ReadLocked = MultiThreadedScoreLockRead<'a, Self::ScoreLookUp>;
280
281         fn read_lock(&'a self) -> Self::ReadLocked {
282                 MultiThreadedScoreLockRead(self.score.read().unwrap())
283         }
284
285         fn write_lock(&'a self) -> Self::WriteLocked {
286                 MultiThreadedScoreLockWrite(self.score.write().unwrap())
287         }
288 }
289
290 #[cfg(c_bindings)]
291 impl<T: Score> Writeable for MultiThreadedLockableScore<T> {
292         fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
293                 self.score.read().unwrap().write(writer)
294         }
295 }
296
297 #[cfg(c_bindings)]
298 impl<'a, T: Score + 'a> WriteableScore<'a> for MultiThreadedLockableScore<T> {}
299
300 #[cfg(c_bindings)]
301 impl<T: Score> MultiThreadedLockableScore<T> {
302         /// Creates a new [`MultiThreadedLockableScore`] given an underlying [`Score`].
303         pub fn new(score: T) -> Self {
304                 MultiThreadedLockableScore { score: RwLock::new(score) }
305         }
306 }
307
308 #[cfg(c_bindings)]
309 /// A locked `MultiThreadedLockableScore`.
310 pub struct MultiThreadedScoreLockRead<'a, T: Score>(RwLockReadGuard<'a, T>);
311
312 #[cfg(c_bindings)]
313 /// A locked `MultiThreadedLockableScore`.
314 pub struct MultiThreadedScoreLockWrite<'a, T: Score>(RwLockWriteGuard<'a, T>);
315
316 #[cfg(c_bindings)]
317 impl<'a, T: 'a + Score> Deref for MultiThreadedScoreLockRead<'a, T> {
318         type Target = T;
319
320         fn deref(&self) -> &Self::Target {
321                 self.0.deref()
322         }
323 }
324
325 #[cfg(c_bindings)]
326 impl<'a, T: Score> ScoreLookUp for MultiThreadedScoreLockRead<'a, T> {
327         type ScoreParams = T::ScoreParams;
328         fn channel_penalty_msat(&self, candidate:&CandidateRouteHop, usage: ChannelUsage, score_params: &Self::ScoreParams
329         ) -> u64 {
330                 self.0.channel_penalty_msat(candidate, usage, score_params)
331         }
332 }
333
334 #[cfg(c_bindings)]
335 impl<'a, T: Score> Writeable for MultiThreadedScoreLockWrite<'a, T> {
336         fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
337                 self.0.write(writer)
338         }
339 }
340
341 #[cfg(c_bindings)]
342 impl<'a, T: 'a + Score> Deref for MultiThreadedScoreLockWrite<'a, T> {
343         type Target = T;
344
345         fn deref(&self) -> &Self::Target {
346                 self.0.deref()
347         }
348 }
349
350 #[cfg(c_bindings)]
351 impl<'a, T: 'a + Score> DerefMut for MultiThreadedScoreLockWrite<'a, T> {
352         fn deref_mut(&mut self) -> &mut Self::Target {
353                 self.0.deref_mut()
354         }
355 }
356
357 #[cfg(c_bindings)]
358 impl<'a, T: Score> ScoreUpdate for MultiThreadedScoreLockWrite<'a, T> {
359         fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) {
360                 self.0.payment_path_failed(path, short_channel_id, duration_since_epoch)
361         }
362
363         fn payment_path_successful(&mut self, path: &Path, duration_since_epoch: Duration) {
364                 self.0.payment_path_successful(path, duration_since_epoch)
365         }
366
367         fn probe_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) {
368                 self.0.probe_failed(path, short_channel_id, duration_since_epoch)
369         }
370
371         fn probe_successful(&mut self, path: &Path, duration_since_epoch: Duration) {
372                 self.0.probe_successful(path, duration_since_epoch)
373         }
374
375         fn decay_liquidity_certainty(&mut self, duration_since_epoch: Duration) {
376                 self.0.decay_liquidity_certainty(duration_since_epoch)
377         }
378 }
379
380
381 /// Proposed use of a channel passed as a parameter to [`ScoreLookUp::channel_penalty_msat`].
382 #[derive(Clone, Copy, Debug, PartialEq)]
383 pub struct ChannelUsage {
384         /// The amount to send through the channel, denominated in millisatoshis.
385         pub amount_msat: u64,
386
387         /// Total amount, denominated in millisatoshis, already allocated to send through the channel
388         /// as part of a multi-path payment.
389         pub inflight_htlc_msat: u64,
390
391         /// The effective capacity of the channel.
392         pub effective_capacity: EffectiveCapacity,
393 }
394
395 #[derive(Clone)]
396 /// [`ScoreLookUp`] implementation that uses a fixed penalty.
397 pub struct FixedPenaltyScorer {
398         penalty_msat: u64,
399 }
400
401 impl FixedPenaltyScorer {
402         /// Creates a new scorer using `penalty_msat`.
403         pub fn with_penalty(penalty_msat: u64) -> Self {
404                 Self { penalty_msat }
405         }
406 }
407
408 impl ScoreLookUp for FixedPenaltyScorer {
409         type ScoreParams = ();
410         fn channel_penalty_msat(&self, _: &CandidateRouteHop, _: ChannelUsage, _score_params: &Self::ScoreParams) -> u64 {
411                 self.penalty_msat
412         }
413 }
414
415 impl ScoreUpdate for FixedPenaltyScorer {
416         fn payment_path_failed(&mut self, _path: &Path, _short_channel_id: u64, _duration_since_epoch: Duration) {}
417
418         fn payment_path_successful(&mut self, _path: &Path, _duration_since_epoch: Duration) {}
419
420         fn probe_failed(&mut self, _path: &Path, _short_channel_id: u64, _duration_since_epoch: Duration) {}
421
422         fn probe_successful(&mut self, _path: &Path, _duration_since_epoch: Duration) {}
423
424         fn decay_liquidity_certainty(&mut self, _duration_since_epoch: Duration) {}
425 }
426
427 impl Writeable for FixedPenaltyScorer {
428         #[inline]
429         fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
430                 write_tlv_fields!(w, {});
431                 Ok(())
432         }
433 }
434
435 impl ReadableArgs<u64> for FixedPenaltyScorer {
436         #[inline]
437         fn read<R: Read>(r: &mut R, penalty_msat: u64) -> Result<Self, DecodeError> {
438                 read_tlv_fields!(r, {});
439                 Ok(Self { penalty_msat })
440         }
441 }
442
443 #[cfg(not(feature = "no-std"))]
444 type ConfiguredTime = crate::util::time::MonotonicTime;
445 #[cfg(feature = "no-std")]
446 use crate::util::time::Eternity;
447 #[cfg(feature = "no-std")]
448 type ConfiguredTime = Eternity;
449
450 /// [`ScoreLookUp`] implementation using channel success probability distributions.
451 ///
452 /// Channels are tracked with upper and lower liquidity bounds - when an HTLC fails at a channel,
453 /// we learn that the upper-bound on the available liquidity is lower than the amount of the HTLC.
454 /// When a payment is forwarded through a channel (but fails later in the route), we learn the
455 /// lower-bound on the channel's available liquidity must be at least the value of the HTLC.
456 ///
457 /// These bounds are then used to determine a success probability using the formula from
458 /// *Optimally Reliable & Cheap Payment Flows on the Lightning Network* by Rene Pickhardt
459 /// and Stefan Richter [[1]] (i.e. `(upper_bound - payment_amount) / (upper_bound - lower_bound)`).
460 ///
461 /// This probability is combined with the [`liquidity_penalty_multiplier_msat`] and
462 /// [`liquidity_penalty_amount_multiplier_msat`] parameters to calculate a concrete penalty in
463 /// milli-satoshis. The penalties, when added across all hops, have the property of being linear in
464 /// terms of the entire path's success probability. This allows the router to directly compare
465 /// penalties for different paths. See the documentation of those parameters for the exact formulas.
466 ///
467 /// The liquidity bounds are decayed by halving them every [`liquidity_offset_half_life`].
468 ///
469 /// Further, we track the history of our upper and lower liquidity bounds for each channel,
470 /// allowing us to assign a second penalty (using [`historical_liquidity_penalty_multiplier_msat`]
471 /// and [`historical_liquidity_penalty_amount_multiplier_msat`]) based on the same probability
472 /// formula, but using the history of a channel rather than our latest estimates for the liquidity
473 /// bounds.
474 ///
475 /// # Note
476 ///
477 /// Mixing the `no-std` feature between serialization and deserialization results in undefined
478 /// behavior.
479 ///
480 /// [1]: https://arxiv.org/abs/2107.05322
481 /// [`liquidity_penalty_multiplier_msat`]: ProbabilisticScoringFeeParameters::liquidity_penalty_multiplier_msat
482 /// [`liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringFeeParameters::liquidity_penalty_amount_multiplier_msat
483 /// [`liquidity_offset_half_life`]: ProbabilisticScoringDecayParameters::liquidity_offset_half_life
484 /// [`historical_liquidity_penalty_multiplier_msat`]: ProbabilisticScoringFeeParameters::historical_liquidity_penalty_multiplier_msat
485 /// [`historical_liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringFeeParameters::historical_liquidity_penalty_amount_multiplier_msat
486 pub type ProbabilisticScorer<G, L> = ProbabilisticScorerUsingTime::<G, L, ConfiguredTime>;
487
488 /// Probabilistic [`ScoreLookUp`] implementation.
489 ///
490 /// This is not exported to bindings users generally all users should use the [`ProbabilisticScorer`] type alias.
491 pub struct ProbabilisticScorerUsingTime<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time>
492 where L::Target: Logger {
493         decay_params: ProbabilisticScoringDecayParameters,
494         network_graph: G,
495         logger: L,
496         channel_liquidities: HashMap<u64, ChannelLiquidity<T>>,
497 }
498
499 /// Parameters for configuring [`ProbabilisticScorer`].
500 ///
501 /// Used to configure base, liquidity, and amount penalties, the sum of which comprises the channel
502 /// penalty (i.e., the amount in msats willing to be paid to avoid routing through the channel).
503 ///
504 /// The penalty applied to any channel by the [`ProbabilisticScorer`] is the sum of each of the
505 /// parameters here.
506 #[derive(Clone)]
507 pub struct ProbabilisticScoringFeeParameters {
508         /// A fixed penalty in msats to apply to each channel.
509         ///
510         /// Default value: 500 msat
511         pub base_penalty_msat: u64,
512
513         /// A multiplier used with the total amount flowing over a channel to calculate a fixed penalty
514         /// applied to each channel, in excess of the [`base_penalty_msat`].
515         ///
516         /// The purpose of the amount penalty is to avoid having fees dominate the channel cost (i.e.,
517         /// fees plus penalty) for large payments. The penalty is computed as the product of this
518         /// multiplier and `2^30`ths of the total amount flowing over a channel (i.e. the payment
519         /// amount plus the amount of any other HTLCs flowing we sent over the same channel).
520         ///
521         /// ie `base_penalty_amount_multiplier_msat * amount_msat / 2^30`
522         ///
523         /// Default value: 8,192 msat
524         ///
525         /// [`base_penalty_msat`]: Self::base_penalty_msat
526         pub base_penalty_amount_multiplier_msat: u64,
527
528         /// A multiplier used in conjunction with the negative `log10` of the channel's success
529         /// probability for a payment, as determined by our latest estimates of the channel's
530         /// liquidity, to determine the liquidity penalty.
531         ///
532         /// The penalty is based in part on the knowledge learned from prior successful and unsuccessful
533         /// payments. This knowledge is decayed over time based on [`liquidity_offset_half_life`]. The
534         /// penalty is effectively limited to `2 * liquidity_penalty_multiplier_msat` (corresponding to
535         /// lower bounding the success probability to `0.01`) when the amount falls within the
536         /// uncertainty bounds of the channel liquidity balance. Amounts above the upper bound will
537         /// result in a `u64::max_value` penalty, however.
538         ///
539         /// `-log10(success_probability) * liquidity_penalty_multiplier_msat`
540         ///
541         /// Default value: 30,000 msat
542         ///
543         /// [`liquidity_offset_half_life`]: ProbabilisticScoringDecayParameters::liquidity_offset_half_life
544         pub liquidity_penalty_multiplier_msat: u64,
545
546         /// A multiplier used in conjunction with the total amount flowing over a channel and the
547         /// negative `log10` of the channel's success probability for the payment, as determined by our
548         /// latest estimates of the channel's liquidity, to determine the amount penalty.
549         ///
550         /// The purpose of the amount penalty is to avoid having fees dominate the channel cost (i.e.,
551         /// fees plus penalty) for large payments. The penalty is computed as the product of this
552         /// multiplier and `2^20`ths of the amount flowing over this channel, weighted by the negative
553         /// `log10` of the success probability.
554         ///
555         /// `-log10(success_probability) * liquidity_penalty_amount_multiplier_msat * amount_msat / 2^20`
556         ///
557         /// In practice, this means for 0.1 success probability (`-log10(0.1) == 1`) each `2^20`th of
558         /// the amount will result in a penalty of the multiplier. And, as the success probability
559         /// decreases, the negative `log10` weighting will increase dramatically. For higher success
560         /// probabilities, the multiplier will have a decreasing effect as the negative `log10` will
561         /// fall below `1`.
562         ///
563         /// Default value: 192 msat
564         pub liquidity_penalty_amount_multiplier_msat: u64,
565
566         /// A multiplier used in conjunction with the negative `log10` of the channel's success
567         /// probability for the payment, as determined based on the history of our estimates of the
568         /// channel's available liquidity, to determine a penalty.
569         ///
570         /// This penalty is similar to [`liquidity_penalty_multiplier_msat`], however, instead of using
571         /// only our latest estimate for the current liquidity available in the channel, it estimates
572         /// success probability based on the estimated liquidity available in the channel through
573         /// history. Specifically, every time we update our liquidity bounds on a given channel, we
574         /// track which of several buckets those bounds fall into, exponentially decaying the
575         /// probability of each bucket as new samples are added.
576         ///
577         /// Default value: 10,000 msat
578         ///
579         /// [`liquidity_penalty_multiplier_msat`]: Self::liquidity_penalty_multiplier_msat
580         pub historical_liquidity_penalty_multiplier_msat: u64,
581
582         /// A multiplier used in conjunction with the total amount flowing over a channel and the
583         /// negative `log10` of the channel's success probability for the payment, as determined based
584         /// on the history of our estimates of the channel's available liquidity, to determine a
585         /// penalty.
586         ///
587         /// The purpose of the amount penalty is to avoid having fees dominate the channel cost for
588         /// large payments. The penalty is computed as the product of this multiplier and `2^20`ths
589         /// of the amount flowing over this channel, weighted by the negative `log10` of the success
590         /// probability.
591         ///
592         /// This penalty is similar to [`liquidity_penalty_amount_multiplier_msat`], however, instead
593         /// of using only our latest estimate for the current liquidity available in the channel, it
594         /// estimates success probability based on the estimated liquidity available in the channel
595         /// through history. Specifically, every time we update our liquidity bounds on a given
596         /// channel, we track which of several buckets those bounds fall into, exponentially decaying
597         /// the probability of each bucket as new samples are added.
598         ///
599         /// Default value: 64 msat
600         ///
601         /// [`liquidity_penalty_amount_multiplier_msat`]: Self::liquidity_penalty_amount_multiplier_msat
602         pub historical_liquidity_penalty_amount_multiplier_msat: u64,
603
604         /// Manual penalties used for the given nodes. Allows to set a particular penalty for a given
605         /// node. Note that a manual penalty of `u64::max_value()` means the node would not ever be
606         /// considered during path finding.
607         ///
608         /// This is not exported to bindings users
609         pub manual_node_penalties: HashMap<NodeId, u64>,
610
611         /// This penalty is applied when `htlc_maximum_msat` is equal to or larger than half of the
612         /// channel's capacity, (ie. htlc_maximum_msat >= 0.5 * channel_capacity) which makes us
613         /// prefer nodes with a smaller `htlc_maximum_msat`. We treat such nodes preferentially
614         /// as this makes balance discovery attacks harder to execute, thereby creating an incentive
615         /// to restrict `htlc_maximum_msat` and improve privacy.
616         ///
617         /// Default value: 250 msat
618         pub anti_probing_penalty_msat: u64,
619
620         /// This penalty is applied when the total amount flowing over a channel exceeds our current
621         /// estimate of the channel's available liquidity. The total amount is the amount of the
622         /// current HTLC plus any HTLCs which we've sent over the same channel.
623         ///
624         /// Note that in this case all other penalties, including the
625         /// [`liquidity_penalty_multiplier_msat`] and [`liquidity_penalty_amount_multiplier_msat`]-based
626         /// penalties, as well as the [`base_penalty_msat`] and the [`anti_probing_penalty_msat`], if
627         /// applicable, are still included in the overall penalty.
628         ///
629         /// If you wish to avoid creating paths with such channels entirely, setting this to a value of
630         /// `u64::max_value()` will guarantee that.
631         ///
632         /// Default value: 1_0000_0000_000 msat (1 Bitcoin)
633         ///
634         /// [`liquidity_penalty_multiplier_msat`]: Self::liquidity_penalty_multiplier_msat
635         /// [`liquidity_penalty_amount_multiplier_msat`]: Self::liquidity_penalty_amount_multiplier_msat
636         /// [`base_penalty_msat`]: Self::base_penalty_msat
637         /// [`anti_probing_penalty_msat`]: Self::anti_probing_penalty_msat
638         pub considered_impossible_penalty_msat: u64,
639
640         /// In order to calculate most of the scores above, we must first convert a lower and upper
641         /// bound on the available liquidity in a channel into the probability that we think a payment
642         /// will succeed. That probability is derived from a Probability Density Function for where we
643         /// think the liquidity in a channel likely lies, given such bounds.
644         ///
645         /// If this flag is set, that PDF is simply a constant - we assume that the actual available
646         /// liquidity in a channel is just as likely to be at any point between our lower and upper
647         /// bounds.
648         ///
649         /// If this flag is *not* set, that PDF is `(x - 0.5*capacity) ^ 2`. That is, we use an
650         /// exponential curve which expects the liquidity of a channel to lie "at the edges". This
651         /// matches experimental results - most routing nodes do not aggressively rebalance their
652         /// channels and flows in the network are often unbalanced, leaving liquidity usually
653         /// unavailable.
654         ///
655         /// Thus, for the "best" routes, leave this flag `false`. However, the flag does imply a number
656         /// of floating-point multiplications in the hottest routing code, which may lead to routing
657         /// performance degradation on some machines.
658         ///
659         /// Default value: false
660         pub linear_success_probability: bool,
661 }
662
663 impl Default for ProbabilisticScoringFeeParameters {
664         fn default() -> Self {
665                 Self {
666                         base_penalty_msat: 500,
667                         base_penalty_amount_multiplier_msat: 8192,
668                         liquidity_penalty_multiplier_msat: 30_000,
669                         liquidity_penalty_amount_multiplier_msat: 192,
670                         manual_node_penalties: HashMap::new(),
671                         anti_probing_penalty_msat: 250,
672                         considered_impossible_penalty_msat: 1_0000_0000_000,
673                         historical_liquidity_penalty_multiplier_msat: 10_000,
674                         historical_liquidity_penalty_amount_multiplier_msat: 64,
675                         linear_success_probability: false,
676                 }
677         }
678 }
679
680 impl ProbabilisticScoringFeeParameters {
681         /// Marks the node with the given `node_id` as banned,
682         /// i.e it will be avoided during path finding.
683         pub fn add_banned(&mut self, node_id: &NodeId) {
684                 self.manual_node_penalties.insert(*node_id, u64::max_value());
685         }
686
687         /// Marks all nodes in the given list as banned, i.e.,
688         /// they will be avoided during path finding.
689         pub fn add_banned_from_list(&mut self, node_ids: Vec<NodeId>) {
690                 for id in node_ids {
691                         self.manual_node_penalties.insert(id, u64::max_value());
692                 }
693         }
694
695         /// Removes the node with the given `node_id` from the list of nodes to avoid.
696         pub fn remove_banned(&mut self, node_id: &NodeId) {
697                 self.manual_node_penalties.remove(node_id);
698         }
699
700         /// Sets a manual penalty for the given node.
701         pub fn set_manual_penalty(&mut self, node_id: &NodeId, penalty: u64) {
702                 self.manual_node_penalties.insert(*node_id, penalty);
703         }
704
705         /// Removes the node with the given `node_id` from the list of manual penalties.
706         pub fn remove_manual_penalty(&mut self, node_id: &NodeId) {
707                 self.manual_node_penalties.remove(node_id);
708         }
709
710         /// Clears the list of manual penalties that are applied during path finding.
711         pub fn clear_manual_penalties(&mut self) {
712                 self.manual_node_penalties = HashMap::new();
713         }
714 }
715
716 #[cfg(test)]
717 impl ProbabilisticScoringFeeParameters {
718         fn zero_penalty() -> Self {
719                 Self {
720                         base_penalty_msat: 0,
721                         base_penalty_amount_multiplier_msat: 0,
722                         liquidity_penalty_multiplier_msat: 0,
723                         liquidity_penalty_amount_multiplier_msat: 0,
724                         historical_liquidity_penalty_multiplier_msat: 0,
725                         historical_liquidity_penalty_amount_multiplier_msat: 0,
726                         manual_node_penalties: HashMap::new(),
727                         anti_probing_penalty_msat: 0,
728                         considered_impossible_penalty_msat: 0,
729                         linear_success_probability: true,
730                 }
731         }
732 }
733
734 /// Parameters for configuring [`ProbabilisticScorer`].
735 ///
736 /// Used to configure decay parameters that are static throughout the lifetime of the scorer.
737 /// these decay parameters affect the score of the channel penalty and are not changed on a
738 /// per-route penalty cost call.
739 #[derive(Copy, Clone)]
740 pub struct ProbabilisticScoringDecayParameters {
741         /// If we aren't learning any new datapoints for a channel, the historical liquidity bounds
742         /// tracking can simply live on with increasingly stale data. Instead, when a channel has not
743         /// seen a liquidity estimate update for this amount of time, the historical datapoints are
744         /// decayed by half.
745         /// For an example of historical_no_updates_half_life being used see [`historical_estimated_channel_liquidity_probabilities`]
746         ///
747         /// Note that after 16 or more half lives all historical data will be completely gone.
748         ///
749         /// Default value: 14 days
750         ///
751         /// [`historical_estimated_channel_liquidity_probabilities`]: ProbabilisticScorerUsingTime::historical_estimated_channel_liquidity_probabilities
752         pub historical_no_updates_half_life: Duration,
753
754         /// Whenever this amount of time elapses since the last update to a channel's liquidity bounds,
755         /// the distance from the bounds to "zero" is cut in half. In other words, the lower-bound on
756         /// the available liquidity is halved and the upper-bound moves half-way to the channel's total
757         /// capacity.
758         ///
759         /// Because halving the liquidity bounds grows the uncertainty on the channel's liquidity,
760         /// the penalty for an amount within the new bounds may change. See the [`ProbabilisticScorer`]
761         /// struct documentation for more info on the way the liquidity bounds are used.
762         ///
763         /// For example, if the channel's capacity is 1 million sats, and the current upper and lower
764         /// liquidity bounds are 200,000 sats and 600,000 sats, after this amount of time the upper
765         /// and lower liquidity bounds will be decayed to 100,000 and 800,000 sats.
766         ///
767         /// Default value: 6 hours
768         ///
769         /// # Note
770         ///
771         /// When built with the `no-std` feature, time will never elapse. Therefore, the channel
772         /// liquidity knowledge will never decay except when the bounds cross.
773         pub liquidity_offset_half_life: Duration,
774 }
775
776 impl Default for ProbabilisticScoringDecayParameters {
777         fn default() -> Self {
778                 Self {
779                         liquidity_offset_half_life: Duration::from_secs(6 * 60 * 60),
780                         historical_no_updates_half_life: Duration::from_secs(60 * 60 * 24 * 14),
781                 }
782         }
783 }
784
785 #[cfg(test)]
786 impl ProbabilisticScoringDecayParameters {
787         fn zero_penalty() -> Self {
788                 Self {
789                         liquidity_offset_half_life: Duration::from_secs(6 * 60 * 60),
790                         historical_no_updates_half_life: Duration::from_secs(60 * 60 * 24 * 14),
791                 }
792         }
793 }
794
795 /// Accounting for channel liquidity balance uncertainty.
796 ///
797 /// Direction is defined in terms of [`NodeId`] partial ordering, where the source node is the
798 /// first node in the ordering of the channel's counterparties. Thus, swapping the two liquidity
799 /// offset fields gives the opposite direction.
800 struct ChannelLiquidity<T: Time> {
801         /// Lower channel liquidity bound in terms of an offset from zero.
802         min_liquidity_offset_msat: u64,
803
804         /// Upper channel liquidity bound in terms of an offset from the effective capacity.
805         max_liquidity_offset_msat: u64,
806
807         min_liquidity_offset_history: HistoricalBucketRangeTracker,
808         max_liquidity_offset_history: HistoricalBucketRangeTracker,
809
810         /// Time when the liquidity bounds were last modified.
811         last_updated: T,
812
813         /// Time when the historical liquidity bounds were last modified.
814         offset_history_last_updated: T,
815 }
816
817 /// A snapshot of [`ChannelLiquidity`] in one direction assuming a certain channel capacity and
818 /// decayed with a given half life.
819 struct DirectedChannelLiquidity<L: Deref<Target = u64>, BRT: Deref<Target = HistoricalBucketRangeTracker>, T: Time, U: Deref<Target = T>> {
820         min_liquidity_offset_msat: L,
821         max_liquidity_offset_msat: L,
822         liquidity_history: HistoricalMinMaxBuckets<BRT>,
823         capacity_msat: u64,
824         last_updated: U,
825         offset_history_last_updated: U,
826         now: T,
827         decay_params: ProbabilisticScoringDecayParameters,
828 }
829
830 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
831         /// Creates a new scorer using the given scoring parameters for sending payments from a node
832         /// through a network graph.
833         pub fn new(decay_params: ProbabilisticScoringDecayParameters, network_graph: G, logger: L) -> Self {
834                 Self {
835                         decay_params,
836                         network_graph,
837                         logger,
838                         channel_liquidities: HashMap::new(),
839                 }
840         }
841
842         #[cfg(test)]
843         fn with_channel(mut self, short_channel_id: u64, liquidity: ChannelLiquidity<T>) -> Self {
844                 assert!(self.channel_liquidities.insert(short_channel_id, liquidity).is_none());
845                 self
846         }
847
848         /// Dump the contents of this scorer into the configured logger.
849         ///
850         /// Note that this writes roughly one line per channel for which we have a liquidity estimate,
851         /// which may be a substantial amount of log output.
852         pub fn debug_log_liquidity_stats(&self) {
853                 let graph = self.network_graph.read_only();
854                 for (scid, liq) in self.channel_liquidities.iter() {
855                         if let Some(chan_debug) = graph.channels().get(scid) {
856                                 let log_direction = |source, target| {
857                                         if let Some((directed_info, _)) = chan_debug.as_directed_to(target) {
858                                                 let amt = directed_info.effective_capacity().as_msat();
859                                                 let dir_liq = liq.as_directed(source, target, amt, self.decay_params);
860
861                                                 let min_buckets = &dir_liq.liquidity_history.min_liquidity_offset_history.buckets;
862                                                 let max_buckets = &dir_liq.liquidity_history.max_liquidity_offset_history.buckets;
863
864                                                 log_debug!(self.logger, core::concat!(
865                                                         "Liquidity from {} to {} via {} is in the range ({}, {}).\n",
866                                                         "\tHistorical min liquidity bucket relative probabilities:\n",
867                                                         "\t\t{} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {}\n",
868                                                         "\tHistorical max liquidity bucket relative probabilities:\n",
869                                                         "\t\t{} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {}"),
870                                                         source, target, scid, dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat(),
871                                                         min_buckets[ 0], min_buckets[ 1], min_buckets[ 2], min_buckets[ 3],
872                                                         min_buckets[ 4], min_buckets[ 5], min_buckets[ 6], min_buckets[ 7],
873                                                         min_buckets[ 8], min_buckets[ 9], min_buckets[10], min_buckets[11],
874                                                         min_buckets[12], min_buckets[13], min_buckets[14], min_buckets[15],
875                                                         min_buckets[16], min_buckets[17], min_buckets[18], min_buckets[19],
876                                                         min_buckets[20], min_buckets[21], min_buckets[22], min_buckets[23],
877                                                         min_buckets[24], min_buckets[25], min_buckets[26], min_buckets[27],
878                                                         min_buckets[28], min_buckets[29], min_buckets[30], min_buckets[31],
879                                                         // Note that the liquidity buckets are an offset from the edge, so we
880                                                         // inverse the max order to get the probabilities from zero.
881                                                         max_buckets[31], max_buckets[30], max_buckets[29], max_buckets[28],
882                                                         max_buckets[27], max_buckets[26], max_buckets[25], max_buckets[24],
883                                                         max_buckets[23], max_buckets[22], max_buckets[21], max_buckets[20],
884                                                         max_buckets[19], max_buckets[18], max_buckets[17], max_buckets[16],
885                                                         max_buckets[15], max_buckets[14], max_buckets[13], max_buckets[12],
886                                                         max_buckets[11], max_buckets[10], max_buckets[ 9], max_buckets[ 8],
887                                                         max_buckets[ 7], max_buckets[ 6], max_buckets[ 5], max_buckets[ 4],
888                                                         max_buckets[ 3], max_buckets[ 2], max_buckets[ 1], max_buckets[ 0]);
889                                         } else {
890                                                 log_debug!(self.logger, "No amount known for SCID {} from {:?} to {:?}", scid, source, target);
891                                         }
892                                 };
893
894                                 log_direction(&chan_debug.node_one, &chan_debug.node_two);
895                                 log_direction(&chan_debug.node_two, &chan_debug.node_one);
896                         } else {
897                                 log_debug!(self.logger, "No network graph entry for SCID {}", scid);
898                         }
899                 }
900         }
901
902         /// Query the estimated minimum and maximum liquidity available for sending a payment over the
903         /// channel with `scid` towards the given `target` node.
904         pub fn estimated_channel_liquidity_range(&self, scid: u64, target: &NodeId) -> Option<(u64, u64)> {
905                 let graph = self.network_graph.read_only();
906
907                 if let Some(chan) = graph.channels().get(&scid) {
908                         if let Some(liq) = self.channel_liquidities.get(&scid) {
909                                 if let Some((directed_info, source)) = chan.as_directed_to(target) {
910                                         let amt = directed_info.effective_capacity().as_msat();
911                                         let dir_liq = liq.as_directed(source, target, amt, self.decay_params);
912                                         return Some((dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat()));
913                                 }
914                         }
915                 }
916                 None
917         }
918
919         /// Query the historical estimated minimum and maximum liquidity available for sending a
920         /// payment over the channel with `scid` towards the given `target` node.
921         ///
922         /// Returns two sets of 32 buckets. The first set describes the lower-bound liquidity history,
923         /// the second set describes the upper-bound liquidity history. Each bucket describes the
924         /// relative frequency at which we've seen a liquidity bound in the bucket's range relative to
925         /// the channel's total capacity, on an arbitrary scale. Because the values are slowly decayed,
926         /// more recent data points are weighted more heavily than older datapoints.
927         ///
928         /// Note that the range of each bucket varies by its location to provide more granular results
929         /// at the edges of a channel's capacity, where it is more likely to sit.
930         ///
931         /// When scoring, the estimated probability that an upper-/lower-bound lies in a given bucket
932         /// is calculated by dividing that bucket's value with the total value of all buckets.
933         ///
934         /// For example, using a lower bucket count for illustrative purposes, a value of
935         /// `[0, 0, 0, ..., 0, 32]` indicates that we believe the probability of a bound being very
936         /// close to the channel's capacity to be 100%, and have never (recently) seen it in any other
937         /// bucket. A value of `[31, 0, 0, ..., 0, 0, 32]` indicates we've seen the bound being both
938         /// in the top and bottom bucket, and roughly with similar (recent) frequency.
939         ///
940         /// Because the datapoints are decayed slowly over time, values will eventually return to
941         /// `Some(([0; 32], [0; 32]))` or `None` if no data remains for a channel.
942         ///
943         /// In order to fetch a single success probability from the buckets provided here, as used in
944         /// the scoring model, see [`Self::historical_estimated_payment_success_probability`].
945         pub fn historical_estimated_channel_liquidity_probabilities(&self, scid: u64, target: &NodeId)
946         -> Option<([u16; 32], [u16; 32])> {
947                 let graph = self.network_graph.read_only();
948
949                 if let Some(chan) = graph.channels().get(&scid) {
950                         if let Some(liq) = self.channel_liquidities.get(&scid) {
951                                 if let Some((directed_info, source)) = chan.as_directed_to(target) {
952                                         let amt = directed_info.effective_capacity().as_msat();
953                                         let dir_liq = liq.as_directed(source, target, amt, self.decay_params);
954
955                                         let min_buckets = dir_liq.liquidity_history.min_liquidity_offset_history.buckets;
956                                         let mut max_buckets = dir_liq.liquidity_history.max_liquidity_offset_history.buckets;
957
958                                         // Note that the liquidity buckets are an offset from the edge, so we inverse
959                                         // the max order to get the probabilities from zero.
960                                         max_buckets.reverse();
961                                         return Some((min_buckets, max_buckets));
962                                 }
963                         }
964                 }
965                 None
966         }
967
968         /// Query the probability of payment success sending the given `amount_msat` over the channel
969         /// with `scid` towards the given `target` node, based on the historical estimated liquidity
970         /// bounds.
971         ///
972         /// These are the same bounds as returned by
973         /// [`Self::historical_estimated_channel_liquidity_probabilities`] (but not those returned by
974         /// [`Self::estimated_channel_liquidity_range`]).
975         pub fn historical_estimated_payment_success_probability(
976                 &self, scid: u64, target: &NodeId, amount_msat: u64, params: &ProbabilisticScoringFeeParameters)
977         -> Option<f64> {
978                 let graph = self.network_graph.read_only();
979
980                 if let Some(chan) = graph.channels().get(&scid) {
981                         if let Some(liq) = self.channel_liquidities.get(&scid) {
982                                 if let Some((directed_info, source)) = chan.as_directed_to(target) {
983                                         let capacity_msat = directed_info.effective_capacity().as_msat();
984                                         let dir_liq = liq.as_directed(source, target, capacity_msat, self.decay_params);
985
986                                         return dir_liq.liquidity_history.calculate_success_probability_times_billion(
987                                                 &params, amount_msat, capacity_msat
988                                         ).map(|p| p as f64 / (1024 * 1024 * 1024) as f64);
989                                 }
990                         }
991                 }
992                 None
993         }
994 }
995
996 impl<T: Time> ChannelLiquidity<T> {
997         #[inline]
998         fn new() -> Self {
999                 Self {
1000                         min_liquidity_offset_msat: 0,
1001                         max_liquidity_offset_msat: 0,
1002                         min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1003                         max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1004                         last_updated: T::now(),
1005                         offset_history_last_updated: T::now(),
1006                 }
1007         }
1008
1009         /// Returns a view of the channel liquidity directed from `source` to `target` assuming
1010         /// `capacity_msat`.
1011         fn as_directed(
1012                 &self, source: &NodeId, target: &NodeId, capacity_msat: u64, decay_params: ProbabilisticScoringDecayParameters
1013         ) -> DirectedChannelLiquidity<&u64, &HistoricalBucketRangeTracker, T, &T> {
1014                 let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) =
1015                         if source < target {
1016                                 (&self.min_liquidity_offset_msat, &self.max_liquidity_offset_msat,
1017                                         &self.min_liquidity_offset_history, &self.max_liquidity_offset_history)
1018                         } else {
1019                                 (&self.max_liquidity_offset_msat, &self.min_liquidity_offset_msat,
1020                                         &self.max_liquidity_offset_history, &self.min_liquidity_offset_history)
1021                         };
1022
1023                 DirectedChannelLiquidity {
1024                         min_liquidity_offset_msat,
1025                         max_liquidity_offset_msat,
1026                         liquidity_history: HistoricalMinMaxBuckets {
1027                                 min_liquidity_offset_history,
1028                                 max_liquidity_offset_history,
1029                         },
1030                         capacity_msat,
1031                         last_updated: &self.last_updated,
1032                         offset_history_last_updated: &self.offset_history_last_updated,
1033                         now: T::now(),
1034                         decay_params: decay_params,
1035                 }
1036         }
1037
1038         /// Returns a mutable view of the channel liquidity directed from `source` to `target` assuming
1039         /// `capacity_msat`.
1040         fn as_directed_mut(
1041                 &mut self, source: &NodeId, target: &NodeId, capacity_msat: u64, decay_params: ProbabilisticScoringDecayParameters
1042         ) -> DirectedChannelLiquidity<&mut u64, &mut HistoricalBucketRangeTracker, T, &mut T> {
1043                 let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) =
1044                         if source < target {
1045                                 (&mut self.min_liquidity_offset_msat, &mut self.max_liquidity_offset_msat,
1046                                         &mut self.min_liquidity_offset_history, &mut self.max_liquidity_offset_history)
1047                         } else {
1048                                 (&mut self.max_liquidity_offset_msat, &mut self.min_liquidity_offset_msat,
1049                                         &mut self.max_liquidity_offset_history, &mut self.min_liquidity_offset_history)
1050                         };
1051
1052                 DirectedChannelLiquidity {
1053                         min_liquidity_offset_msat,
1054                         max_liquidity_offset_msat,
1055                         liquidity_history: HistoricalMinMaxBuckets {
1056                                 min_liquidity_offset_history,
1057                                 max_liquidity_offset_history,
1058                         },
1059                         capacity_msat,
1060                         last_updated: &mut self.last_updated,
1061                         offset_history_last_updated: &mut self.offset_history_last_updated,
1062                         now: T::now(),
1063                         decay_params: decay_params,
1064                 }
1065         }
1066
1067         fn decayed_offset(&self, offset: u64, duration_since_epoch: Duration,
1068                 decay_params: ProbabilisticScoringDecayParameters
1069         ) -> u64 {
1070                 let half_life = decay_params.liquidity_offset_half_life.as_secs_f64();
1071                 if half_life != 0.0 {
1072                         let elapsed_time = T::now().duration_since(self.last_updated).as_secs_f64();
1073                         ((offset as f64) * powf64(0.5, elapsed_time / half_life)) as u64
1074                 } else {
1075                         0
1076                 }
1077         }
1078 }
1079
1080 /// Bounds `-log10` to avoid excessive liquidity penalties for payments with low success
1081 /// probabilities.
1082 const NEGATIVE_LOG10_UPPER_BOUND: u64 = 2;
1083
1084 /// The rough cutoff at which our precision falls off and we should stop bothering to try to log a
1085 /// ratio, as X in 1/X.
1086 const PRECISION_LOWER_BOUND_DENOMINATOR: u64 = approx::LOWER_BITS_BOUND;
1087
1088 /// The divisor used when computing the amount penalty.
1089 const AMOUNT_PENALTY_DIVISOR: u64 = 1 << 20;
1090 const BASE_AMOUNT_PENALTY_DIVISOR: u64 = 1 << 30;
1091
1092 /// Raises three `f64`s to the 3rd power, without `powi` because it requires `std` (dunno why).
1093 #[inline(always)]
1094 fn three_f64_pow_3(a: f64, b: f64, c: f64) -> (f64, f64, f64) {
1095         (a * a * a, b * b * b, c * c * c)
1096 }
1097
1098 /// Given liquidity bounds, calculates the success probability (in the form of a numerator and
1099 /// denominator) of an HTLC. This is a key assumption in our scoring models.
1100 ///
1101 /// Must not return a numerator or denominator greater than 2^31 for arguments less than 2^31.
1102 ///
1103 /// min_zero_implies_no_successes signals that a `min_liquidity_msat` of 0 means we've not
1104 /// (recently) seen an HTLC successfully complete over this channel.
1105 #[inline(always)]
1106 fn success_probability(
1107         amount_msat: u64, min_liquidity_msat: u64, max_liquidity_msat: u64, capacity_msat: u64,
1108         params: &ProbabilisticScoringFeeParameters, min_zero_implies_no_successes: bool,
1109 ) -> (u64, u64) {
1110         debug_assert!(min_liquidity_msat <= amount_msat);
1111         debug_assert!(amount_msat < max_liquidity_msat);
1112         debug_assert!(max_liquidity_msat <= capacity_msat);
1113
1114         let (numerator, mut denominator) =
1115                 if params.linear_success_probability {
1116                         (max_liquidity_msat - amount_msat,
1117                                 (max_liquidity_msat - min_liquidity_msat).saturating_add(1))
1118                 } else {
1119                         let capacity = capacity_msat as f64;
1120                         let min = (min_liquidity_msat as f64) / capacity;
1121                         let max = (max_liquidity_msat as f64) / capacity;
1122                         let amount = (amount_msat as f64) / capacity;
1123
1124                         // Assume the channel has a probability density function of (x - 0.5)^2 for values from
1125                         // 0 to 1 (where 1 is the channel's full capacity). The success probability given some
1126                         // liquidity bounds is thus the integral under the curve from the amount to maximum
1127                         // estimated liquidity, divided by the same integral from the minimum to the maximum
1128                         // estimated liquidity bounds.
1129                         //
1130                         // Because the integral from x to y is simply (y - 0.5)^3 - (x - 0.5)^3, we can
1131                         // calculate the cumulative density function between the min/max bounds trivially. Note
1132                         // that we don't bother to normalize the CDF to total to 1, as it will come out in the
1133                         // division of num / den.
1134                         let (max_pow, amt_pow, min_pow) = three_f64_pow_3(max - 0.5, amount - 0.5, min - 0.5);
1135                         let num = max_pow - amt_pow;
1136                         let den = max_pow - min_pow;
1137
1138                         // Because our numerator and denominator max out at 0.5^3 we need to multiply them by
1139                         // quite a large factor to get something useful (ideally in the 2^30 range).
1140                         const BILLIONISH: f64 = 1024.0 * 1024.0 * 1024.0;
1141                         let numerator = (num * BILLIONISH) as u64 + 1;
1142                         let denominator = (den * BILLIONISH) as u64 + 1;
1143                         debug_assert!(numerator <= 1 << 30, "Got large numerator ({}) from float {}.", numerator, num);
1144                         debug_assert!(denominator <= 1 << 30, "Got large denominator ({}) from float {}.", denominator, den);
1145                         (numerator, denominator)
1146                 };
1147
1148         if min_zero_implies_no_successes && min_liquidity_msat == 0 &&
1149                 denominator < u64::max_value() / 21
1150         {
1151                 // If we have no knowledge of the channel, scale probability down by ~75%
1152                 // Note that we prefer to increase the denominator rather than decrease the numerator as
1153                 // the denominator is more likely to be larger and thus provide greater precision. This is
1154                 // mostly an overoptimization but makes a large difference in tests.
1155                 denominator = denominator * 21 / 16
1156         }
1157
1158         (numerator, denominator)
1159 }
1160
1161 impl<L: Deref<Target = u64>, BRT: Deref<Target = HistoricalBucketRangeTracker>, T: Time, U: Deref<Target = T>> DirectedChannelLiquidity< L, BRT, T, U> {
1162         /// Returns a liquidity penalty for routing the given HTLC `amount_msat` through the channel in
1163         /// this direction.
1164         fn penalty_msat(&self, amount_msat: u64, score_params: &ProbabilisticScoringFeeParameters) -> u64 {
1165                 let available_capacity = self.capacity_msat;
1166                 let max_liquidity_msat = self.max_liquidity_msat();
1167                 let min_liquidity_msat = core::cmp::min(self.min_liquidity_msat(), max_liquidity_msat);
1168
1169                 let mut res = if amount_msat <= min_liquidity_msat {
1170                         0
1171                 } else if amount_msat >= max_liquidity_msat {
1172                         // Equivalent to hitting the else clause below with the amount equal to the effective
1173                         // capacity and without any certainty on the liquidity upper bound, plus the
1174                         // impossibility penalty.
1175                         let negative_log10_times_2048 = NEGATIVE_LOG10_UPPER_BOUND * 2048;
1176                         Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
1177                                         score_params.liquidity_penalty_multiplier_msat,
1178                                         score_params.liquidity_penalty_amount_multiplier_msat)
1179                                 .saturating_add(score_params.considered_impossible_penalty_msat)
1180                 } else {
1181                         let (numerator, denominator) = success_probability(amount_msat,
1182                                 min_liquidity_msat, max_liquidity_msat, available_capacity, score_params, false);
1183                         if denominator - numerator < denominator / PRECISION_LOWER_BOUND_DENOMINATOR {
1184                                 // If the failure probability is < 1.5625% (as 1 - numerator/denominator < 1/64),
1185                                 // don't bother trying to use the log approximation as it gets too noisy to be
1186                                 // particularly helpful, instead just round down to 0.
1187                                 0
1188                         } else {
1189                                 let negative_log10_times_2048 =
1190                                         approx::negative_log10_times_2048(numerator, denominator);
1191                                 Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
1192                                         score_params.liquidity_penalty_multiplier_msat,
1193                                         score_params.liquidity_penalty_amount_multiplier_msat)
1194                         }
1195                 };
1196
1197                 if amount_msat >= available_capacity {
1198                         // We're trying to send more than the capacity, use a max penalty.
1199                         res = res.saturating_add(Self::combined_penalty_msat(amount_msat,
1200                                 NEGATIVE_LOG10_UPPER_BOUND * 2048,
1201                                 score_params.historical_liquidity_penalty_multiplier_msat,
1202                                 score_params.historical_liquidity_penalty_amount_multiplier_msat));
1203                         return res;
1204                 }
1205
1206                 if score_params.historical_liquidity_penalty_multiplier_msat != 0 ||
1207                    score_params.historical_liquidity_penalty_amount_multiplier_msat != 0 {
1208                         if let Some(cumulative_success_prob_times_billion) = self.liquidity_history
1209                                 .calculate_success_probability_times_billion(
1210                                         score_params, amount_msat, self.capacity_msat)
1211                         {
1212                                 let historical_negative_log10_times_2048 = approx::negative_log10_times_2048(cumulative_success_prob_times_billion + 1, 1024 * 1024 * 1024);
1213                                 res = res.saturating_add(Self::combined_penalty_msat(amount_msat,
1214                                         historical_negative_log10_times_2048, score_params.historical_liquidity_penalty_multiplier_msat,
1215                                         score_params.historical_liquidity_penalty_amount_multiplier_msat));
1216                         } else {
1217                                 // If we don't have any valid points (or, once decayed, we have less than a full
1218                                 // point), redo the non-historical calculation with no liquidity bounds tracked and
1219                                 // the historical penalty multipliers.
1220                                 let (numerator, denominator) = success_probability(amount_msat, 0,
1221                                         available_capacity, available_capacity, score_params, true);
1222                                 let negative_log10_times_2048 =
1223                                         approx::negative_log10_times_2048(numerator, denominator);
1224                                 res = res.saturating_add(Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
1225                                         score_params.historical_liquidity_penalty_multiplier_msat,
1226                                         score_params.historical_liquidity_penalty_amount_multiplier_msat));
1227                         }
1228                 }
1229
1230                 res
1231         }
1232
1233         /// Computes the liquidity penalty from the penalty multipliers.
1234         #[inline(always)]
1235         fn combined_penalty_msat(amount_msat: u64, mut negative_log10_times_2048: u64,
1236                 liquidity_penalty_multiplier_msat: u64, liquidity_penalty_amount_multiplier_msat: u64,
1237         ) -> u64 {
1238                 negative_log10_times_2048 =
1239                         negative_log10_times_2048.min(NEGATIVE_LOG10_UPPER_BOUND * 2048);
1240
1241                 // Upper bound the liquidity penalty to ensure some channel is selected.
1242                 let liquidity_penalty_msat = negative_log10_times_2048
1243                         .saturating_mul(liquidity_penalty_multiplier_msat) / 2048;
1244                 let amount_penalty_msat = negative_log10_times_2048
1245                         .saturating_mul(liquidity_penalty_amount_multiplier_msat)
1246                         .saturating_mul(amount_msat) / 2048 / AMOUNT_PENALTY_DIVISOR;
1247
1248                 liquidity_penalty_msat.saturating_add(amount_penalty_msat)
1249         }
1250
1251         /// Returns the lower bound of the channel liquidity balance in this direction.
1252         #[inline(always)]
1253         fn min_liquidity_msat(&self) -> u64 {
1254                 self.decayed_offset_msat(*self.min_liquidity_offset_msat)
1255         }
1256
1257         /// Returns the upper bound of the channel liquidity balance in this direction.
1258         #[inline(always)]
1259         fn max_liquidity_msat(&self) -> u64 {
1260                 self.capacity_msat
1261                         .saturating_sub(self.decayed_offset_msat(*self.max_liquidity_offset_msat))
1262         }
1263
1264         fn decayed_offset_msat(&self, offset_msat: u64) -> u64 {
1265                 offset_msat
1266         }
1267 }
1268
1269 impl<L: DerefMut<Target = u64>, BRT: DerefMut<Target = HistoricalBucketRangeTracker>, T: Time, U: DerefMut<Target = T>> DirectedChannelLiquidity<L, BRT, T, U> {
1270         /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat`.
1271         fn failed_at_channel<Log: Deref>(
1272                 &mut self, amount_msat: u64, duration_since_epoch: Duration, chan_descr: fmt::Arguments, logger: &Log
1273         ) where Log::Target: Logger {
1274                 let existing_max_msat = self.max_liquidity_msat();
1275                 if amount_msat < existing_max_msat {
1276                         log_debug!(logger, "Setting max liquidity of {} from {} to {}", chan_descr, existing_max_msat, amount_msat);
1277                         self.set_max_liquidity_msat(amount_msat, duration_since_epoch);
1278                 } else {
1279                         log_trace!(logger, "Max liquidity of {} is {} (already less than or equal to {})",
1280                                 chan_descr, existing_max_msat, amount_msat);
1281                 }
1282                 self.update_history_buckets(0, duration_since_epoch);
1283         }
1284
1285         /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat` downstream.
1286         fn failed_downstream<Log: Deref>(
1287                 &mut self, amount_msat: u64, duration_since_epoch: Duration, chan_descr: fmt::Arguments, logger: &Log
1288         ) where Log::Target: Logger {
1289                 let existing_min_msat = self.min_liquidity_msat();
1290                 if amount_msat > existing_min_msat {
1291                         log_debug!(logger, "Setting min liquidity of {} from {} to {}", existing_min_msat, chan_descr, amount_msat);
1292                         self.set_min_liquidity_msat(amount_msat, duration_since_epoch);
1293                 } else {
1294                         log_trace!(logger, "Min liquidity of {} is {} (already greater than or equal to {})",
1295                                 chan_descr, existing_min_msat, amount_msat);
1296                 }
1297                 self.update_history_buckets(0, duration_since_epoch);
1298         }
1299
1300         /// Adjusts the channel liquidity balance bounds when successfully routing `amount_msat`.
1301         fn successful<Log: Deref>(&mut self,
1302                 amount_msat: u64, duration_since_epoch: Duration, chan_descr: fmt::Arguments, logger: &Log
1303         ) where Log::Target: Logger {
1304                 let max_liquidity_msat = self.max_liquidity_msat().checked_sub(amount_msat).unwrap_or(0);
1305                 log_debug!(logger, "Subtracting {} from max liquidity of {} (setting it to {})", amount_msat, chan_descr, max_liquidity_msat);
1306                 self.set_max_liquidity_msat(max_liquidity_msat, duration_since_epoch);
1307                 self.update_history_buckets(amount_msat, duration_since_epoch);
1308         }
1309
1310         /// Updates the history buckets for this channel. Because the history buckets track what we now
1311         /// know about the channel's state *prior to our payment* (i.e. what we assume is "steady
1312         /// state"), we allow the caller to set an offset applied to our liquidity bounds which
1313         /// represents the amount of the successful payment we just made.
1314         fn update_history_buckets(&mut self, bucket_offset_msat: u64, duration_since_epoch: Duration) {
1315                 let half_lives = self.now.duration_since(*self.offset_history_last_updated).as_secs()
1316                         .checked_div(self.decay_params.historical_no_updates_half_life.as_secs())
1317                         .map(|v| v.try_into().unwrap_or(u32::max_value())).unwrap_or(u32::max_value());
1318                 self.liquidity_history.min_liquidity_offset_history.time_decay_data(half_lives);
1319                 self.liquidity_history.max_liquidity_offset_history.time_decay_data(half_lives);
1320
1321                 let min_liquidity_offset_msat = self.decayed_offset_msat(*self.min_liquidity_offset_msat);
1322                 self.liquidity_history.min_liquidity_offset_history.track_datapoint(
1323                         min_liquidity_offset_msat + bucket_offset_msat, self.capacity_msat
1324                 );
1325                 let max_liquidity_offset_msat = self.decayed_offset_msat(*self.max_liquidity_offset_msat);
1326                 self.liquidity_history.max_liquidity_offset_history.track_datapoint(
1327                         max_liquidity_offset_msat.saturating_sub(bucket_offset_msat), self.capacity_msat
1328                 );
1329                 *self.offset_history_last_updated = self.now;
1330         }
1331
1332         /// Adjusts the lower bound of the channel liquidity balance in this direction.
1333         fn set_min_liquidity_msat(&mut self, amount_msat: u64, duration_since_epoch: Duration) {
1334                 *self.min_liquidity_offset_msat = amount_msat;
1335                 *self.max_liquidity_offset_msat = if amount_msat > self.max_liquidity_msat() {
1336                         0
1337                 } else {
1338                         self.decayed_offset_msat(*self.max_liquidity_offset_msat)
1339                 };
1340                 *self.last_updated = self.now;
1341         }
1342
1343         /// Adjusts the upper bound of the channel liquidity balance in this direction.
1344         fn set_max_liquidity_msat(&mut self, amount_msat: u64, duration_since_epoch: Duration) {
1345                 *self.max_liquidity_offset_msat = self.capacity_msat.checked_sub(amount_msat).unwrap_or(0);
1346                 *self.min_liquidity_offset_msat = if amount_msat < self.min_liquidity_msat() {
1347                         0
1348                 } else {
1349                         self.decayed_offset_msat(*self.min_liquidity_offset_msat)
1350                 };
1351                 *self.last_updated = self.now;
1352         }
1353 }
1354
1355 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> ScoreLookUp for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1356         type ScoreParams = ProbabilisticScoringFeeParameters;
1357         fn channel_penalty_msat(
1358                 &self, candidate: &CandidateRouteHop, usage: ChannelUsage, score_params: &ProbabilisticScoringFeeParameters
1359         ) -> u64 {
1360                 let (scid, target) = match candidate {
1361                         CandidateRouteHop::PublicHop { info, short_channel_id } => {
1362                                 (short_channel_id, info.target())
1363                         },
1364                         _ => return 0,
1365                 };
1366                 let source = candidate.source();
1367                 if let Some(penalty) = score_params.manual_node_penalties.get(&target) {
1368                         return *penalty;
1369                 }
1370
1371                 let base_penalty_msat = score_params.base_penalty_msat.saturating_add(
1372                         score_params.base_penalty_amount_multiplier_msat
1373                                 .saturating_mul(usage.amount_msat) / BASE_AMOUNT_PENALTY_DIVISOR);
1374
1375                 let mut anti_probing_penalty_msat = 0;
1376                 match usage.effective_capacity {
1377                         EffectiveCapacity::ExactLiquidity { liquidity_msat: amount_msat } |
1378                                 EffectiveCapacity::HintMaxHTLC { amount_msat } =>
1379                         {
1380                                 if usage.amount_msat > amount_msat {
1381                                         return u64::max_value();
1382                                 } else {
1383                                         return base_penalty_msat;
1384                                 }
1385                         },
1386                         EffectiveCapacity::Total { capacity_msat, htlc_maximum_msat } => {
1387                                 if htlc_maximum_msat >= capacity_msat/2 {
1388                                         anti_probing_penalty_msat = score_params.anti_probing_penalty_msat;
1389                                 }
1390                         },
1391                         _ => {},
1392                 }
1393
1394                 let amount_msat = usage.amount_msat.saturating_add(usage.inflight_htlc_msat);
1395                 let capacity_msat = usage.effective_capacity.as_msat();
1396                 self.channel_liquidities
1397                         .get(&scid)
1398                         .unwrap_or(&ChannelLiquidity::new())
1399                         .as_directed(&source, &target, capacity_msat, self.decay_params)
1400                         .penalty_msat(amount_msat, score_params)
1401                         .saturating_add(anti_probing_penalty_msat)
1402                         .saturating_add(base_penalty_msat)
1403         }
1404 }
1405
1406 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> ScoreUpdate for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1407         fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) {
1408                 let amount_msat = path.final_value_msat();
1409                 log_trace!(self.logger, "Scoring path through to SCID {} as having failed at {} msat", short_channel_id, amount_msat);
1410                 let network_graph = self.network_graph.read_only();
1411                 for (hop_idx, hop) in path.hops.iter().enumerate() {
1412                         let target = NodeId::from_pubkey(&hop.pubkey);
1413                         let channel_directed_from_source = network_graph.channels()
1414                                 .get(&hop.short_channel_id)
1415                                 .and_then(|channel| channel.as_directed_to(&target));
1416
1417                         let at_failed_channel = hop.short_channel_id == short_channel_id;
1418                         if at_failed_channel && hop_idx == 0 {
1419                                 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);
1420                         }
1421
1422                         // Only score announced channels.
1423                         if let Some((channel, source)) = channel_directed_from_source {
1424                                 let capacity_msat = channel.effective_capacity().as_msat();
1425                                 if at_failed_channel {
1426                                         self.channel_liquidities
1427                                                 .entry(hop.short_channel_id)
1428                                                 .or_insert_with(ChannelLiquidity::new)
1429                                                 .as_directed_mut(source, &target, capacity_msat, self.decay_params)
1430                                                 .failed_at_channel(amount_msat, duration_since_epoch,
1431                                                         format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1432                                 } else {
1433                                         self.channel_liquidities
1434                                                 .entry(hop.short_channel_id)
1435                                                 .or_insert_with(ChannelLiquidity::new)
1436                                                 .as_directed_mut(source, &target, capacity_msat, self.decay_params)
1437                                                 .failed_downstream(amount_msat, duration_since_epoch,
1438                                                         format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1439                                 }
1440                         } else {
1441                                 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).",
1442                                         hop.short_channel_id);
1443                         }
1444                         if at_failed_channel { break; }
1445                 }
1446         }
1447
1448         fn payment_path_successful(&mut self, path: &Path, duration_since_epoch: Duration) {
1449                 let amount_msat = path.final_value_msat();
1450                 log_trace!(self.logger, "Scoring path through SCID {} as having succeeded at {} msat.",
1451                         path.hops.split_last().map(|(hop, _)| hop.short_channel_id).unwrap_or(0), amount_msat);
1452                 let network_graph = self.network_graph.read_only();
1453                 for hop in &path.hops {
1454                         let target = NodeId::from_pubkey(&hop.pubkey);
1455                         let channel_directed_from_source = network_graph.channels()
1456                                 .get(&hop.short_channel_id)
1457                                 .and_then(|channel| channel.as_directed_to(&target));
1458
1459                         // Only score announced channels.
1460                         if let Some((channel, source)) = channel_directed_from_source {
1461                                 let capacity_msat = channel.effective_capacity().as_msat();
1462                                 self.channel_liquidities
1463                                         .entry(hop.short_channel_id)
1464                                         .or_insert_with(ChannelLiquidity::new)
1465                                         .as_directed_mut(source, &target, capacity_msat, self.decay_params)
1466                                         .successful(amount_msat, duration_since_epoch,
1467                                                 format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1468                         } else {
1469                                 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).",
1470                                         hop.short_channel_id);
1471                         }
1472                 }
1473         }
1474
1475         fn probe_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) {
1476                 self.payment_path_failed(path, short_channel_id, duration_since_epoch)
1477         }
1478
1479         fn probe_successful(&mut self, path: &Path, duration_since_epoch: Duration) {
1480                 self.payment_path_failed(path, u64::max_value(), duration_since_epoch)
1481         }
1482
1483         fn decay_liquidity_certainty(&mut self, duration_since_epoch: Duration) {
1484                 let decay_params = self.decay_params;
1485                 self.channel_liquidities.retain(|_scid, liquidity| {
1486                         liquidity.min_liquidity_offset_msat =
1487                                 liquidity.decayed_offset(liquidity.min_liquidity_offset_msat, duration_since_epoch, decay_params);
1488                         liquidity.max_liquidity_offset_msat =
1489                                 liquidity.decayed_offset(liquidity.max_liquidity_offset_msat, duration_since_epoch, decay_params);
1490                         liquidity.last_updated = T::now();
1491
1492                         let elapsed_time =
1493                                 T::now().duration_since(liquidity.offset_history_last_updated);
1494                         if elapsed_time > decay_params.historical_no_updates_half_life {
1495                                 let half_life = decay_params.historical_no_updates_half_life.as_secs_f64();
1496                                 if half_life != 0.0 {
1497                                         let divisor = powf64(2048.0, elapsed_time.as_secs_f64() / half_life) as u64;
1498                                         for bucket in liquidity.min_liquidity_offset_history.buckets.iter_mut() {
1499                                                 *bucket = ((*bucket as u64) * 1024 / divisor) as u16;
1500                                         }
1501                                         for bucket in liquidity.max_liquidity_offset_history.buckets.iter_mut() {
1502                                                 *bucket = ((*bucket as u64) * 1024 / divisor) as u16;
1503                                         }
1504                                         liquidity.offset_history_last_updated = T::now();
1505                                 }
1506                         }
1507                         liquidity.min_liquidity_offset_msat != 0 || liquidity.max_liquidity_offset_msat != 0 ||
1508                                 liquidity.min_liquidity_offset_history.buckets != [0; 32] ||
1509                                 liquidity.max_liquidity_offset_history.buckets != [0; 32]
1510                 });
1511         }
1512 }
1513
1514 #[cfg(c_bindings)]
1515 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Score for ProbabilisticScorerUsingTime<G, L, T>
1516 where L::Target: Logger {}
1517
1518 #[cfg(feature = "std")]
1519 #[inline]
1520 fn powf64(n: f64, exp: f64) -> f64 {
1521         n.powf(exp)
1522 }
1523 #[cfg(not(feature = "std"))]
1524 fn powf64(n: f64, exp: f64) -> f64 {
1525         libm::powf(n as f32, exp as f32) as f64
1526 }
1527
1528 mod approx {
1529         const BITS: u32 = 64;
1530         const HIGHEST_BIT: u32 = BITS - 1;
1531         const LOWER_BITS: u32 = 6;
1532         pub(super) const LOWER_BITS_BOUND: u64 = 1 << LOWER_BITS;
1533         const LOWER_BITMASK: u64 = (1 << LOWER_BITS) - 1;
1534
1535         /// Look-up table for `log10(x) * 2048` where row `i` is used for each `x` having `i` as the
1536         /// most significant bit. The next 4 bits of `x`, if applicable, are used for the second index.
1537         const LOG10_TIMES_2048: [[u16; (LOWER_BITS_BOUND) as usize]; BITS as usize] = [
1538                 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1539                         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1540                         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1541                         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
1542                 [617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
1543                         617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
1544                         977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977,
1545                         977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977],
1546                 [1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233,
1547                         1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431,
1548                         1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594,
1549                         1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731],
1550                 [1850, 1850, 1850, 1850, 1850, 1850, 1850, 1850, 1954, 1954, 1954, 1954, 1954, 1954, 1954, 1954,
1551                         2048, 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2133, 2133, 2133, 2133, 2133, 2133, 2133, 2133,
1552                         2210, 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2281, 2281, 2281, 2281, 2281, 2281, 2281, 2281,
1553                         2347, 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2409, 2409, 2409, 2409, 2409, 2409, 2409, 2409],
1554                 [2466, 2466, 2466, 2466, 2520, 2520, 2520, 2520, 2571, 2571, 2571, 2571, 2619, 2619, 2619, 2619,
1555                         2665, 2665, 2665, 2665, 2708, 2708, 2708, 2708, 2749, 2749, 2749, 2749, 2789, 2789, 2789, 2789,
1556                         2827, 2827, 2827, 2827, 2863, 2863, 2863, 2863, 2898, 2898, 2898, 2898, 2931, 2931, 2931, 2931,
1557                         2964, 2964, 2964, 2964, 2995, 2995, 2995, 2995, 3025, 3025, 3025, 3025, 3054, 3054, 3054, 3054],
1558                 [3083, 3083, 3110, 3110, 3136, 3136, 3162, 3162, 3187, 3187, 3212, 3212, 3235, 3235, 3259, 3259,
1559                         3281, 3281, 3303, 3303, 3324, 3324, 3345, 3345, 3366, 3366, 3386, 3386, 3405, 3405, 3424, 3424,
1560                         3443, 3443, 3462, 3462, 3479, 3479, 3497, 3497, 3514, 3514, 3531, 3531, 3548, 3548, 3564, 3564,
1561                         3580, 3580, 3596, 3596, 3612, 3612, 3627, 3627, 3642, 3642, 3656, 3656, 3671, 3671, 3685, 3685],
1562                 [3699, 3713, 3726, 3740, 3753, 3766, 3779, 3791, 3804, 3816, 3828, 3840, 3852, 3864, 3875, 3886,
1563                         3898, 3909, 3919, 3930, 3941, 3951, 3962, 3972, 3982, 3992, 4002, 4012, 4022, 4031, 4041, 4050,
1564                         4060, 4069, 4078, 4087, 4096, 4105, 4114, 4122, 4131, 4139, 4148, 4156, 4164, 4173, 4181, 4189,
1565                         4197, 4205, 4213, 4220, 4228, 4236, 4243, 4251, 4258, 4266, 4273, 4280, 4287, 4294, 4302, 4309],
1566                 [4316, 4329, 4343, 4356, 4369, 4382, 4395, 4408, 4420, 4433, 4445, 4457, 4468, 4480, 4492, 4503,
1567                         4514, 4525, 4536, 4547, 4557, 4568, 4578, 4589, 4599, 4609, 4619, 4629, 4638, 4648, 4657, 4667,
1568                         4676, 4685, 4695, 4704, 4713, 4721, 4730, 4739, 4747, 4756, 4764, 4773, 4781, 4789, 4797, 4805,
1569                         4813, 4821, 4829, 4837, 4845, 4852, 4860, 4867, 4875, 4882, 4889, 4897, 4904, 4911, 4918, 4925],
1570                 [4932, 4946, 4959, 4973, 4986, 4999, 5012, 5024, 5037, 5049, 5061, 5073, 5085, 5097, 5108, 5119,
1571                         5131, 5142, 5153, 5163, 5174, 5184, 5195, 5205, 5215, 5225, 5235, 5245, 5255, 5264, 5274, 5283,
1572                         5293, 5302, 5311, 5320, 5329, 5338, 5347, 5355, 5364, 5372, 5381, 5389, 5397, 5406, 5414, 5422,
1573                         5430, 5438, 5446, 5453, 5461, 5469, 5476, 5484, 5491, 5499, 5506, 5513, 5520, 5527, 5535, 5542],
1574                 [5549, 5562, 5576, 5589, 5603, 5615, 5628, 5641, 5653, 5666, 5678, 5690, 5701, 5713, 5725, 5736,
1575                         5747, 5758, 5769, 5780, 5790, 5801, 5811, 5822, 5832, 5842, 5852, 5862, 5871, 5881, 5890, 5900,
1576                         5909, 5918, 5928, 5937, 5946, 5954, 5963, 5972, 5980, 5989, 5997, 6006, 6014, 6022, 6030, 6038,
1577                         6046, 6054, 6062, 6070, 6078, 6085, 6093, 6100, 6108, 6115, 6122, 6130, 6137, 6144, 6151, 6158],
1578                 [6165, 6179, 6192, 6206, 6219, 6232, 6245, 6257, 6270, 6282, 6294, 6306, 6318, 6330, 6341, 6352,
1579                         6364, 6375, 6386, 6396, 6407, 6417, 6428, 6438, 6448, 6458, 6468, 6478, 6488, 6497, 6507, 6516,
1580                         6526, 6535, 6544, 6553, 6562, 6571, 6580, 6588, 6597, 6605, 6614, 6622, 6630, 6639, 6647, 6655,
1581                         6663, 6671, 6679, 6686, 6694, 6702, 6709, 6717, 6724, 6732, 6739, 6746, 6753, 6761, 6768, 6775],
1582                 [6782, 6795, 6809, 6822, 6836, 6849, 6861, 6874, 6886, 6899, 6911, 6923, 6934, 6946, 6958, 6969,
1583                         6980, 6991, 7002, 7013, 7023, 7034, 7044, 7055, 7065, 7075, 7085, 7095, 7104, 7114, 7124, 7133,
1584                         7142, 7151, 7161, 7170, 7179, 7187, 7196, 7205, 7213, 7222, 7230, 7239, 7247, 7255, 7263, 7271,
1585                         7279, 7287, 7295, 7303, 7311, 7318, 7326, 7333, 7341, 7348, 7355, 7363, 7370, 7377, 7384, 7391],
1586                 [7398, 7412, 7425, 7439, 7452, 7465, 7478, 7490, 7503, 7515, 7527, 7539, 7551, 7563, 7574, 7585,
1587                         7597, 7608, 7619, 7629, 7640, 7651, 7661, 7671, 7681, 7691, 7701, 7711, 7721, 7731, 7740, 7749,
1588                         7759, 7768, 7777, 7786, 7795, 7804, 7813, 7821, 7830, 7838, 7847, 7855, 7864, 7872, 7880, 7888,
1589                         7896, 7904, 7912, 7919, 7927, 7935, 7942, 7950, 7957, 7965, 7972, 7979, 7986, 7994, 8001, 8008],
1590                 [8015, 8028, 8042, 8055, 8069, 8082, 8094, 8107, 8119, 8132, 8144, 8156, 8167, 8179, 8191, 8202,
1591                         8213, 8224, 8235, 8246, 8256, 8267, 8277, 8288, 8298, 8308, 8318, 8328, 8337, 8347, 8357, 8366,
1592                         8375, 8384, 8394, 8403, 8412, 8420, 8429, 8438, 8446, 8455, 8463, 8472, 8480, 8488, 8496, 8504,
1593                         8512, 8520, 8528, 8536, 8544, 8551, 8559, 8566, 8574, 8581, 8588, 8596, 8603, 8610, 8617, 8624],
1594                 [8631, 8645, 8659, 8672, 8685, 8698, 8711, 8723, 8736, 8748, 8760, 8772, 8784, 8796, 8807, 8818,
1595                         8830, 8841, 8852, 8862, 8873, 8884, 8894, 8904, 8914, 8924, 8934, 8944, 8954, 8964, 8973, 8982,
1596                         8992, 9001, 9010, 9019, 9028, 9037, 9046, 9054, 9063, 9071, 9080, 9088, 9097, 9105, 9113, 9121,
1597                         9129, 9137, 9145, 9152, 9160, 9168, 9175, 9183, 9190, 9198, 9205, 9212, 9219, 9227, 9234, 9241],
1598                 [9248, 9261, 9275, 9288, 9302, 9315, 9327, 9340, 9352, 9365, 9377, 9389, 9400, 9412, 9424, 9435,
1599                         9446, 9457, 9468, 9479, 9490, 9500, 9510, 9521, 9531, 9541, 9551, 9561, 9570, 9580, 9590, 9599,
1600                         9608, 9617, 9627, 9636, 9645, 9653, 9662, 9671, 9679, 9688, 9696, 9705, 9713, 9721, 9729, 9737,
1601                         9745, 9753, 9761, 9769, 9777, 9784, 9792, 9799, 9807, 9814, 9821, 9829, 9836, 9843, 9850, 9857],
1602                 [9864, 9878, 9892, 9905, 9918, 9931, 9944, 9956, 9969, 9981, 9993, 10005, 10017, 10029, 10040, 10051,
1603                         10063, 10074, 10085, 10095, 10106, 10117, 10127, 10137, 10147, 10157, 10167, 10177, 10187, 10197, 10206, 10215,
1604                         10225, 10234, 10243, 10252, 10261, 10270, 10279, 10287, 10296, 10304, 10313, 10321, 10330, 10338, 10346, 10354,
1605                         10362, 10370, 10378, 10385, 10393, 10401, 10408, 10416, 10423, 10431, 10438, 10445, 10452, 10460, 10467, 10474],
1606                 [10481, 10494, 10508, 10521, 10535, 10548, 10560, 10573, 10585, 10598, 10610, 10622, 10634, 10645, 10657, 10668,
1607                         10679, 10690, 10701, 10712, 10723, 10733, 10743, 10754, 10764, 10774, 10784, 10794, 10803, 10813, 10823, 10832,
1608                         10841, 10851, 10860, 10869, 10878, 10886, 10895, 10904, 10912, 10921, 10929, 10938, 10946, 10954, 10962, 10970,
1609                         10978, 10986, 10994, 11002, 11010, 11017, 11025, 11032, 11040, 11047, 11054, 11062, 11069, 11076, 11083, 11090],
1610                 [11097, 11111, 11125, 11138, 11151, 11164, 11177, 11189, 11202, 11214, 11226, 11238, 11250, 11262, 11273, 11284,
1611                         11296, 11307, 11318, 11328, 11339, 11350, 11360, 11370, 11380, 11390, 11400, 11410, 11420, 11430, 11439, 11448,
1612                         11458, 11467, 11476, 11485, 11494, 11503, 11512, 11520, 11529, 11538, 11546, 11554, 11563, 11571, 11579, 11587,
1613                         11595, 11603, 11611, 11618, 11626, 11634, 11641, 11649, 11656, 11664, 11671, 11678, 11685, 11693, 11700, 11707],
1614                 [11714, 11727, 11741, 11754, 11768, 11781, 11793, 11806, 11818, 11831, 11843, 11855, 11867, 11878, 11890, 11901,
1615                         11912, 11923, 11934, 11945, 11956, 11966, 11976, 11987, 11997, 12007, 12017, 12027, 12036, 12046, 12056, 12065,
1616                         12074, 12084, 12093, 12102, 12111, 12119, 12128, 12137, 12146, 12154, 12162, 12171, 12179, 12187, 12195, 12203,
1617                         12211, 12219, 12227, 12235, 12243, 12250, 12258, 12265, 12273, 12280, 12287, 12295, 12302, 12309, 12316, 12323],
1618                 [12330, 12344, 12358, 12371, 12384, 12397, 12410, 12423, 12435, 12447, 12459, 12471, 12483, 12495, 12506, 12517,
1619                         12529, 12540, 12551, 12561, 12572, 12583, 12593, 12603, 12613, 12623, 12633, 12643, 12653, 12663, 12672, 12682,
1620                         12691, 12700, 12709, 12718, 12727, 12736, 12745, 12753, 12762, 12771, 12779, 12787, 12796, 12804, 12812, 12820,
1621                         12828, 12836, 12844, 12851, 12859, 12867, 12874, 12882, 12889, 12897, 12904, 12911, 12918, 12926, 12933, 12940],
1622                 [12947, 12960, 12974, 12987, 13001, 13014, 13026, 13039, 13051, 13064, 13076, 13088, 13100, 13111, 13123, 13134,
1623                         13145, 13156, 13167, 13178, 13189, 13199, 13209, 13220, 13230, 13240, 13250, 13260, 13269, 13279, 13289, 13298,
1624                         13307, 13317, 13326, 13335, 13344, 13352, 13361, 13370, 13379, 13387, 13395, 13404, 13412, 13420, 13428, 13436,
1625                         13444, 13452, 13460, 13468, 13476, 13483, 13491, 13498, 13506, 13513, 13521, 13528, 13535, 13542, 13549, 13556],
1626                 [13563, 13577, 13591, 13604, 13617, 13630, 13643, 13656, 13668, 13680, 13692, 13704, 13716, 13728, 13739, 13750,
1627                         13762, 13773, 13784, 13794, 13805, 13816, 13826, 13836, 13846, 13857, 13866, 13876, 13886, 13896, 13905, 13915,
1628                         13924, 13933, 13942, 13951, 13960, 13969, 13978, 13986, 13995, 14004, 14012, 14020, 14029, 14037, 14045, 14053,
1629                         14061, 14069, 14077, 14084, 14092, 14100, 14107, 14115, 14122, 14130, 14137, 14144, 14151, 14159, 14166, 14173],
1630                 [14180, 14194, 14207, 14220, 14234, 14247, 14259, 14272, 14284, 14297, 14309, 14321, 14333, 14344, 14356, 14367,
1631                         14378, 14389, 14400, 14411, 14422, 14432, 14443, 14453, 14463, 14473, 14483, 14493, 14502, 14512, 14522, 14531,
1632                         14540, 14550, 14559, 14568, 14577, 14586, 14594, 14603, 14612, 14620, 14628, 14637, 14645, 14653, 14661, 14669,
1633                         14677, 14685, 14693, 14701, 14709, 14716, 14724, 14731, 14739, 14746, 14754, 14761, 14768, 14775, 14782, 14789],
1634                 [14796, 14810, 14824, 14837, 14850, 14863, 14876, 14889, 14901, 14913, 14925, 14937, 14949, 14961, 14972, 14984,
1635                         14995, 15006, 15017, 15027, 15038, 15049, 15059, 15069, 15079, 15090, 15099, 15109, 15119, 15129, 15138, 15148,
1636                         15157, 15166, 15175, 15184, 15193, 15202, 15211, 15219, 15228, 15237, 15245, 15253, 15262, 15270, 15278, 15286,
1637                         15294, 15302, 15310, 15317, 15325, 15333, 15340, 15348, 15355, 15363, 15370, 15377, 15384, 15392, 15399, 15406],
1638                 [15413, 15427, 15440, 15453, 15467, 15480, 15492, 15505, 15517, 15530, 15542, 15554, 15566, 15577, 15589, 15600,
1639                         15611, 15622, 15633, 15644, 15655, 15665, 15676, 15686, 15696, 15706, 15716, 15726, 15736, 15745, 15755, 15764,
1640                         15773, 15783, 15792, 15801, 15810, 15819, 15827, 15836, 15845, 15853, 15862, 15870, 15878, 15886, 15894, 15903,
1641                         15910, 15918, 15926, 15934, 15942, 15949, 15957, 15964, 15972, 15979, 15987, 15994, 16001, 16008, 16015, 16022],
1642                 [16029, 16043, 16057, 16070, 16083, 16096, 16109, 16122, 16134, 16146, 16158, 16170, 16182, 16194, 16205, 16217,
1643                         16228, 16239, 16250, 16260, 16271, 16282, 16292, 16302, 16312, 16323, 16332, 16342, 16352, 16362, 16371, 16381,
1644                         16390, 16399, 16408, 16417, 16426, 16435, 16444, 16452, 16461, 16470, 16478, 16486, 16495, 16503, 16511, 16519,
1645                         16527, 16535, 16543, 16550, 16558, 16566, 16573, 16581, 16588, 16596, 16603, 16610, 16618, 16625, 16632, 16639],
1646                 [16646, 16660, 16673, 16686, 16700, 16713, 16725, 16738, 16751, 16763, 16775, 16787, 16799, 16810, 16822, 16833,
1647                         16844, 16855, 16866, 16877, 16888, 16898, 16909, 16919, 16929, 16939, 16949, 16959, 16969, 16978, 16988, 16997,
1648                         17006, 17016, 17025, 17034, 17043, 17052, 17060, 17069, 17078, 17086, 17095, 17103, 17111, 17119, 17127, 17136,
1649                         17143, 17151, 17159, 17167, 17175, 17182, 17190, 17197, 17205, 17212, 17220, 17227, 17234, 17241, 17248, 17255],
1650                 [17262, 17276, 17290, 17303, 17316, 17329, 17342, 17355, 17367, 17379, 17391, 17403, 17415, 17427, 17438, 17450,
1651                         17461, 17472, 17483, 17493, 17504, 17515, 17525, 17535, 17546, 17556, 17565, 17575, 17585, 17595, 17604, 17614,
1652                         17623, 17632, 17641, 17650, 17659, 17668, 17677, 17685, 17694, 17703, 17711, 17719, 17728, 17736, 17744, 17752,
1653                         17760, 17768, 17776, 17784, 17791, 17799, 17806, 17814, 17821, 17829, 17836, 17843, 17851, 17858, 17865, 17872],
1654                 [17879, 17893, 17906, 17920, 17933, 17946, 17958, 17971, 17984, 17996, 18008, 18020, 18032, 18043, 18055, 18066,
1655                         18077, 18088, 18099, 18110, 18121, 18131, 18142, 18152, 18162, 18172, 18182, 18192, 18202, 18211, 18221, 18230,
1656                         18239, 18249, 18258, 18267, 18276, 18285, 18293, 18302, 18311, 18319, 18328, 18336, 18344, 18352, 18360, 18369,
1657                         18377, 18384, 18392, 18400, 18408, 18415, 18423, 18430, 18438, 18445, 18453, 18460, 18467, 18474, 18481, 18488],
1658                 [18495, 18509, 18523, 18536, 18549, 18562, 18575, 18588, 18600, 18612, 18624, 18636, 18648, 18660, 18671, 18683,
1659                         18694, 18705, 18716, 18726, 18737, 18748, 18758, 18768, 18779, 18789, 18799, 18808, 18818, 18828, 18837, 18847,
1660                         18856, 18865, 18874, 18883, 18892, 18901, 18910, 18919, 18927, 18936, 18944, 18952, 18961, 18969, 18977, 18985,
1661                         18993, 19001, 19009, 19017, 19024, 19032, 19039, 19047, 19054, 19062, 19069, 19076, 19084, 19091, 19098, 19105],
1662                 [19112, 19126, 19139, 19153, 19166, 19179, 19191, 19204, 19217, 19229, 19241, 19253, 19265, 19276, 19288, 19299,
1663                         19310, 19321, 19332, 19343, 19354, 19364, 19375, 19385, 19395, 19405, 19415, 19425, 19435, 19444, 19454, 19463,
1664                         19472, 19482, 19491, 19500, 19509, 19518, 19526, 19535, 19544, 19552, 19561, 19569, 19577, 19585, 19594, 19602,
1665                         19610, 19617, 19625, 19633, 19641, 19648, 19656, 19663, 19671, 19678, 19686, 19693, 19700, 19707, 19714, 19721],
1666                 [19728, 19742, 19756, 19769, 19782, 19795, 19808, 19821, 19833, 19845, 19857, 19869, 19881, 19893, 19904, 19916,
1667                         19927, 19938, 19949, 19960, 19970, 19981, 19991, 20001, 20012, 20022, 20032, 20041, 20051, 20061, 20070, 20080,
1668                         20089, 20098, 20107, 20116, 20125, 20134, 20143, 20152, 20160, 20169, 20177, 20185, 20194, 20202, 20210, 20218,
1669                         20226, 20234, 20242, 20250, 20257, 20265, 20272, 20280, 20287, 20295, 20302, 20309, 20317, 20324, 20331, 20338],
1670                 [20345, 20359, 20372, 20386, 20399, 20412, 20425, 20437, 20450, 20462, 20474, 20486, 20498, 20509, 20521, 20532,
1671                         20543, 20554, 20565, 20576, 20587, 20597, 20608, 20618, 20628, 20638, 20648, 20658, 20668, 20677, 20687, 20696,
1672                         20705, 20715, 20724, 20733, 20742, 20751, 20759, 20768, 20777, 20785, 20794, 20802, 20810, 20818, 20827, 20835,
1673                         20843, 20850, 20858, 20866, 20874, 20881, 20889, 20896, 20904, 20911, 20919, 20926, 20933, 20940, 20947, 20954],
1674                 [20961, 20975, 20989, 21002, 21015, 21028, 21041, 21054, 21066, 21078, 21090, 21102, 21114, 21126, 21137, 21149,
1675                         21160, 21171, 21182, 21193, 21203, 21214, 21224, 21234, 21245, 21255, 21265, 21274, 21284, 21294, 21303, 21313,
1676                         21322, 21331, 21340, 21349, 21358, 21367, 21376, 21385, 21393, 21402, 21410, 21418, 21427, 21435, 21443, 21451,
1677                         21459, 21467, 21475, 21483, 21490, 21498, 21505, 21513, 21520, 21528, 21535, 21542, 21550, 21557, 21564, 21571],
1678                 [21578, 21592, 21605, 21619, 21632, 21645, 21658, 21670, 21683, 21695, 21707, 21719, 21731, 21742, 21754, 21765,
1679                         21776, 21787, 21798, 21809, 21820, 21830, 21841, 21851, 21861, 21871, 21881, 21891, 21901, 21910, 21920, 21929,
1680                         21938, 21948, 21957, 21966, 21975, 21984, 21992, 22001, 22010, 22018, 22027, 22035, 22043, 22051, 22060, 22068,
1681                         22076, 22083, 22091, 22099, 22107, 22114, 22122, 22129, 22137, 22144, 22152, 22159, 22166, 22173, 22180, 22187],
1682                 [22194, 22208, 22222, 22235, 22248, 22261, 22274, 22287, 22299, 22311, 22323, 22335, 22347, 22359, 22370, 22382,
1683                         22393, 22404, 22415, 22426, 22436, 22447, 22457, 22467, 22478, 22488, 22498, 22507, 22517, 22527, 22536, 22546,
1684                         22555, 22564, 22573, 22582, 22591, 22600, 22609, 22618, 22626, 22635, 22643, 22651, 22660, 22668, 22676, 22684,
1685                         22692, 22700, 22708, 22716, 22723, 22731, 22738, 22746, 22753, 22761, 22768, 22775, 22783, 22790, 22797, 22804],
1686                 [22811, 22825, 22838, 22852, 22865, 22878, 22891, 22903, 22916, 22928, 22940, 22952, 22964, 22975, 22987, 22998,
1687                         23009, 23020, 23031, 23042, 23053, 23063, 23074, 23084, 23094, 23104, 23114, 23124, 23134, 23143, 23153, 23162,
1688                         23171, 23181, 23190, 23199, 23208, 23217, 23225, 23234, 23243, 23251, 23260, 23268, 23276, 23284, 23293, 23301,
1689                         23309, 23316, 23324, 23332, 23340, 23347, 23355, 23363, 23370, 23377, 23385, 23392, 23399, 23406, 23413, 23420],
1690                 [23427, 23441, 23455, 23468, 23481, 23494, 23507, 23520, 23532, 23544, 23556, 23568, 23580, 23592, 23603, 23615,
1691                         23626, 23637, 23648, 23659, 23669, 23680, 23690, 23700, 23711, 23721, 23731, 23740, 23750, 23760, 23769, 23779,
1692                         23788, 23797, 23806, 23815, 23824, 23833, 23842, 23851, 23859, 23868, 23876, 23884, 23893, 23901, 23909, 23917,
1693                         23925, 23933, 23941, 23949, 23956, 23964, 23972, 23979, 23986, 23994, 24001, 24008, 24016, 24023, 24030, 24037],
1694                 [24044, 24058, 24071, 24085, 24098, 24111, 24124, 24136, 24149, 24161, 24173, 24185, 24197, 24208, 24220, 24231,
1695                         24242, 24253, 24264, 24275, 24286, 24296, 24307, 24317, 24327, 24337, 24347, 24357, 24367, 24376, 24386, 24395,
1696                         24405, 24414, 24423, 24432, 24441, 24450, 24458, 24467, 24476, 24484, 24493, 24501, 24509, 24517, 24526, 24534,
1697                         24542, 24550, 24557, 24565, 24573, 24580, 24588, 24596, 24603, 24610, 24618, 24625, 24632, 24639, 24646, 24653],
1698                 [24660, 24674, 24688, 24701, 24714, 24727, 24740, 24753, 24765, 24777, 24790, 24801, 24813, 24825, 24836, 24848,
1699                         24859, 24870, 24881, 24892, 24902, 24913, 24923, 24933, 24944, 24954, 24964, 24973, 24983, 24993, 25002, 25012,
1700                         25021, 25030, 25039, 25048, 25057, 25066, 25075, 25084, 25092, 25101, 25109, 25117, 25126, 25134, 25142, 25150,
1701                         25158, 25166, 25174, 25182, 25189, 25197, 25205, 25212, 25219, 25227, 25234, 25241, 25249, 25256, 25263, 25270],
1702                 [25277, 25291, 25304, 25318, 25331, 25344, 25357, 25369, 25382, 25394, 25406, 25418, 25430, 25441, 25453, 25464,
1703                         25475, 25486, 25497, 25508, 25519, 25529, 25540, 25550, 25560, 25570, 25580, 25590, 25600, 25609, 25619, 25628,
1704                         25638, 25647, 25656, 25665, 25674, 25683, 25691, 25700, 25709, 25717, 25726, 25734, 25742, 25750, 25759, 25767,
1705                         25775, 25783, 25790, 25798, 25806, 25813, 25821, 25829, 25836, 25843, 25851, 25858, 25865, 25872, 25879, 25886],
1706                 [25893, 25907, 25921, 25934, 25947, 25960, 25973, 25986, 25998, 26010, 26023, 26034, 26046, 26058, 26069, 26081,
1707                         26092, 26103, 26114, 26125, 26135, 26146, 26156, 26166, 26177, 26187, 26197, 26206, 26216, 26226, 26235, 26245,
1708                         26254, 26263, 26272, 26281, 26290, 26299, 26308, 26317, 26325, 26334, 26342, 26351, 26359, 26367, 26375, 26383,
1709                         26391, 26399, 26407, 26415, 26422, 26430, 26438, 26445, 26453, 26460, 26467, 26474, 26482, 26489, 26496, 26503],
1710                 [26510, 26524, 26537, 26551, 26564, 26577, 26590, 26602, 26615, 26627, 26639, 26651, 26663, 26674, 26686, 26697,
1711                         26708, 26719, 26730, 26741, 26752, 26762, 26773, 26783, 26793, 26803, 26813, 26823, 26833, 26842, 26852, 26861,
1712                         26871, 26880, 26889, 26898, 26907, 26916, 26924, 26933, 26942, 26950, 26959, 26967, 26975, 26983, 26992, 27000,
1713                         27008, 27016, 27023, 27031, 27039, 27046, 27054, 27062, 27069, 27076, 27084, 27091, 27098, 27105, 27112, 27119],
1714                 [27126, 27140, 27154, 27167, 27180, 27193, 27206, 27219, 27231, 27243, 27256, 27267, 27279, 27291, 27302, 27314,
1715                         27325, 27336, 27347, 27358, 27368, 27379, 27389, 27399, 27410, 27420, 27430, 27439, 27449, 27459, 27468, 27478,
1716                         27487, 27496, 27505, 27514, 27523, 27532, 27541, 27550, 27558, 27567, 27575, 27584, 27592, 27600, 27608, 27616,
1717                         27624, 27632, 27640, 27648, 27655, 27663, 27671, 27678, 27686, 27693, 27700, 27707, 27715, 27722, 27729, 27736],
1718                 [27743, 27757, 27770, 27784, 27797, 27810, 27823, 27835, 27848, 27860, 27872, 27884, 27896, 27907, 27919, 27930,
1719                         27941, 27952, 27963, 27974, 27985, 27995, 28006, 28016, 28026, 28036, 28046, 28056, 28066, 28075, 28085, 28094,
1720                         28104, 28113, 28122, 28131, 28140, 28149, 28157, 28166, 28175, 28183, 28192, 28200, 28208, 28217, 28225, 28233,
1721                         28241, 28249, 28256, 28264, 28272, 28280, 28287, 28295, 28302, 28309, 28317, 28324, 28331, 28338, 28345, 28352],
1722                 [28359, 28373, 28387, 28400, 28413, 28426, 28439, 28452, 28464, 28476, 28489, 28501, 28512, 28524, 28535, 28547,
1723                         28558, 28569, 28580, 28591, 28601, 28612, 28622, 28633, 28643, 28653, 28663, 28672, 28682, 28692, 28701, 28711,
1724                         28720, 28729, 28738, 28747, 28756, 28765, 28774, 28783, 28791, 28800, 28808, 28817, 28825, 28833, 28841, 28849,
1725                         28857, 28865, 28873, 28881, 28888, 28896, 28904, 28911, 28919, 28926, 28933, 28941, 28948, 28955, 28962, 28969],
1726                 [28976, 28990, 29003, 29017, 29030, 29043, 29056, 29068, 29081, 29093, 29105, 29117, 29129, 29140, 29152, 29163,
1727                         29174, 29185, 29196, 29207, 29218, 29228, 29239, 29249, 29259, 29269, 29279, 29289, 29299, 29308, 29318, 29327,
1728                         29337, 29346, 29355, 29364, 29373, 29382, 29390, 29399, 29408, 29416, 29425, 29433, 29441, 29450, 29458, 29466,
1729                         29474, 29482, 29489, 29497, 29505, 29513, 29520, 29528, 29535, 29542, 29550, 29557, 29564, 29571, 29578, 29585],
1730                 [29592, 29606, 29620, 29633, 29646, 29659, 29672, 29685, 29697, 29709, 29722, 29734, 29745, 29757, 29768, 29780,
1731                         29791, 29802, 29813, 29824, 29834, 29845, 29855, 29866, 29876, 29886, 29896, 29906, 29915, 29925, 29934, 29944,
1732                         29953, 29962, 29971, 29980, 29989, 29998, 30007, 30016, 30024, 30033, 30041, 30050, 30058, 30066, 30074, 30082,
1733                         30090, 30098, 30106, 30114, 30121, 30129, 30137, 30144, 30152, 30159, 30166, 30174, 30181, 30188, 30195, 30202],
1734                 [30209, 30223, 30236, 30250, 30263, 30276, 30289, 30301, 30314, 30326, 30338, 30350, 30362, 30373, 30385, 30396,
1735                         30407, 30418, 30429, 30440, 30451, 30461, 30472, 30482, 30492, 30502, 30512, 30522, 30532, 30541, 30551, 30560,
1736                         30570, 30579, 30588, 30597, 30606, 30615, 30624, 30632, 30641, 30649, 30658, 30666, 30674, 30683, 30691, 30699,
1737                         30707, 30715, 30722, 30730, 30738, 30746, 30753, 30761, 30768, 30775, 30783, 30790, 30797, 30804, 30811, 30818],
1738                 [30825, 30839, 30853, 30866, 30879, 30892, 30905, 30918, 30930, 30943, 30955, 30967, 30978, 30990, 31001, 31013,
1739                         31024, 31035, 31046, 31057, 31067, 31078, 31088, 31099, 31109, 31119, 31129, 31139, 31148, 31158, 31167, 31177,
1740                         31186, 31195, 31204, 31213, 31222, 31231, 31240, 31249, 31257, 31266, 31274, 31283, 31291, 31299, 31307, 31315,
1741                         31323, 31331, 31339, 31347, 31354, 31362, 31370, 31377, 31385, 31392, 31399, 31407, 31414, 31421, 31428, 31435],
1742                 [31442, 31456, 31469, 31483, 31496, 31509, 31522, 31534, 31547, 31559, 31571, 31583, 31595, 31606, 31618, 31629,
1743                         31640, 31652, 31662, 31673, 31684, 31694, 31705, 31715, 31725, 31735, 31745, 31755, 31765, 31774, 31784, 31793,
1744                         31803, 31812, 31821, 31830, 31839, 31848, 31857, 31865, 31874, 31882, 31891, 31899, 31907, 31916, 31924, 31932,
1745                         31940, 31948, 31955, 31963, 31971, 31979, 31986, 31994, 32001, 32008, 32016, 32023, 32030, 32037, 32044, 32052],
1746                 [32058, 32072, 32086, 32099, 32112, 32125, 32138, 32151, 32163, 32176, 32188, 32200, 32211, 32223, 32234, 32246,
1747                         32257, 32268, 32279, 32290, 32300, 32311, 32321, 32332, 32342, 32352, 32362, 32372, 32381, 32391, 32400, 32410,
1748                         32419, 32428, 32437, 32446, 32455, 32464, 32473, 32482, 32490, 32499, 32507, 32516, 32524, 32532, 32540, 32548,
1749                         32556, 32564, 32572, 32580, 32587, 32595, 32603, 32610, 32618, 32625, 32632, 32640, 32647, 32654, 32661, 32668],
1750                 [32675, 32689, 32702, 32716, 32729, 32742, 32755, 32767, 32780, 32792, 32804, 32816, 32828, 32839, 32851, 32862,
1751                         32873, 32885, 32895, 32906, 32917, 32927, 32938, 32948, 32958, 32968, 32978, 32988, 32998, 33007, 33017, 33026,
1752                         33036, 33045, 33054, 33063, 33072, 33081, 33090, 33098, 33107, 33115, 33124, 33132, 33140, 33149, 33157, 33165,
1753                         33173, 33181, 33188, 33196, 33204, 33212, 33219, 33227, 33234, 33241, 33249, 33256, 33263, 33270, 33278, 33285],
1754                 [33292, 33305, 33319, 33332, 33345, 33358, 33371, 33384, 33396, 33409, 33421, 33433, 33444, 33456, 33467, 33479,
1755                         33490, 33501, 33512, 33523, 33533, 33544, 33554, 33565, 33575, 33585, 33595, 33605, 33614, 33624, 33633, 33643,
1756                         33652, 33661, 33670, 33680, 33688, 33697, 33706, 33715, 33723, 33732, 33740, 33749, 33757, 33765, 33773, 33781,
1757                         33789, 33797, 33805, 33813, 33820, 33828, 33836, 33843, 33851, 33858, 33865, 33873, 33880, 33887, 33894, 33901],
1758                 [33908, 33922, 33935, 33949, 33962, 33975, 33988, 34000, 34013, 34025, 34037, 34049, 34061, 34072, 34084, 34095,
1759                         34106, 34118, 34128, 34139, 34150, 34160, 34171, 34181, 34191, 34201, 34211, 34221, 34231, 34240, 34250, 34259,
1760                         34269, 34278, 34287, 34296, 34305, 34314, 34323, 34331, 34340, 34348, 34357, 34365, 34373, 34382, 34390, 34398,
1761                         34406, 34414, 34422, 34429, 34437, 34445, 34452, 34460, 34467, 34475, 34482, 34489, 34496, 34503, 34511, 34518],
1762                 [34525, 34538, 34552, 34565, 34578, 34591, 34604, 34617, 34629, 34642, 34654, 34666, 34677, 34689, 34700, 34712,
1763                         34723, 34734, 34745, 34756, 34766, 34777, 34787, 34798, 34808, 34818, 34828, 34838, 34847, 34857, 34866, 34876,
1764                         34885, 34894, 34904, 34913, 34921, 34930, 34939, 34948, 34956, 34965, 34973, 34982, 34990, 34998, 35006, 35014,
1765                         35022, 35030, 35038, 35046, 35053, 35061, 35069, 35076, 35084, 35091, 35098, 35106, 35113, 35120, 35127, 35134],
1766                 [35141, 35155, 35168, 35182, 35195, 35208, 35221, 35233, 35246, 35258, 35270, 35282, 35294, 35306, 35317, 35328,
1767                         35340, 35351, 35361, 35372, 35383, 35393, 35404, 35414, 35424, 35434, 35444, 35454, 35464, 35473, 35483, 35492,
1768                         35502, 35511, 35520, 35529, 35538, 35547, 35556, 35564, 35573, 35581, 35590, 35598, 35606, 35615, 35623, 35631,
1769                         35639, 35647, 35655, 35662, 35670, 35678, 35685, 35693, 35700, 35708, 35715, 35722, 35729, 35736, 35744, 35751],
1770                 [35758, 35771, 35785, 35798, 35811, 35824, 35837, 35850, 35862, 35875, 35887, 35899, 35910, 35922, 35934, 35945,
1771                         35956, 35967, 35978, 35989, 35999, 36010, 36020, 36031, 36041, 36051, 36061, 36071, 36080, 36090, 36099, 36109,
1772                         36118, 36127, 36137, 36146, 36154, 36163, 36172, 36181, 36189, 36198, 36206, 36215, 36223, 36231, 36239, 36247,
1773                         36255, 36263, 36271, 36279, 36287, 36294, 36302, 36309, 36317, 36324, 36331, 36339, 36346, 36353, 36360, 36367],
1774                 [36374, 36388, 36401, 36415, 36428, 36441, 36454, 36466, 36479, 36491, 36503, 36515, 36527, 36539, 36550, 36561,
1775                         36573, 36584, 36594, 36605, 36616, 36626, 36637, 36647, 36657, 36667, 36677, 36687, 36697, 36706, 36716, 36725,
1776                         36735, 36744, 36753, 36762, 36771, 36780, 36789, 36797, 36806, 36814, 36823, 36831, 36839, 36848, 36856, 36864,
1777                         36872, 36880, 36888, 36895, 36903, 36911, 36918, 36926, 36933, 36941, 36948, 36955, 36962, 36969, 36977, 36984],
1778                 [36991, 37004, 37018, 37031, 37044, 37057, 37070, 37083, 37095, 37108, 37120, 37132, 37143, 37155, 37167, 37178,
1779                         37189, 37200, 37211, 37222, 37232, 37243, 37253, 37264, 37274, 37284, 37294, 37304, 37313, 37323, 37332, 37342,
1780                         37351, 37360, 37370, 37379, 37388, 37396, 37405, 37414, 37422, 37431, 37439, 37448, 37456, 37464, 37472, 37480,
1781                         37488, 37496, 37504, 37512, 37520, 37527, 37535, 37542, 37550, 37557, 37564, 37572, 37579, 37586, 37593, 37600],
1782                 [37607, 37621, 37634, 37648, 37661, 37674, 37687, 37699, 37712, 37724, 37736, 37748, 37760, 37772, 37783, 37794,
1783                         37806, 37817, 37828, 37838, 37849, 37859, 37870, 37880, 37890, 37900, 37910, 37920, 37930, 37939, 37949, 37958,
1784                         37968, 37977, 37986, 37995, 38004, 38013, 38022, 38030, 38039, 38047, 38056, 38064, 38072, 38081, 38089, 38097,
1785                         38105, 38113, 38121, 38128, 38136, 38144, 38151, 38159, 38166, 38174, 38181, 38188, 38195, 38202, 38210, 38217],
1786                 [38224, 38237, 38251, 38264, 38278, 38290, 38303, 38316, 38328, 38341, 38353, 38365, 38376, 38388, 38400, 38411,
1787                         38422, 38433, 38444, 38455, 38465, 38476, 38486, 38497, 38507, 38517, 38527, 38537, 38546, 38556, 38565, 38575,
1788                         38584, 38593, 38603, 38612, 38621, 38629, 38638, 38647, 38655, 38664, 38672, 38681, 38689, 38697, 38705, 38713,
1789                         38721, 38729, 38737, 38745, 38753, 38760, 38768, 38775, 38783, 38790, 38797, 38805, 38812, 38819, 38826, 38833],
1790                 [38840, 38854, 38867, 38881, 38894, 38907, 38920, 38932, 38945, 38957, 38969, 38981, 38993, 39005, 39016, 39027,
1791                         39039, 39050, 39061, 39071, 39082, 39092, 39103, 39113, 39123, 39133, 39143, 39153, 39163, 39172, 39182, 39191,
1792                         39201, 39210, 39219, 39228, 39237, 39246, 39255, 39263, 39272, 39280, 39289, 39297, 39305, 39314, 39322, 39330,
1793                         39338, 39346, 39354, 39361, 39369, 39377, 39384, 39392, 39399, 39407, 39414, 39421, 39428, 39436, 39443, 39450],
1794         ];
1795
1796         /// Approximate `log10(numerator / denominator) * 2048` using a look-up table.
1797         #[inline]
1798         pub fn negative_log10_times_2048(numerator: u64, denominator: u64) -> u64 {
1799                 // Multiply the -1 through to avoid needing to use signed numbers.
1800                 (log10_times_2048(denominator) - log10_times_2048(numerator)) as u64
1801         }
1802
1803         #[inline]
1804         fn log10_times_2048(x: u64) -> u16 {
1805                 debug_assert_ne!(x, 0);
1806                 let most_significant_bit = HIGHEST_BIT - x.leading_zeros();
1807                 let lower_bits = (x >> most_significant_bit.saturating_sub(LOWER_BITS)) & LOWER_BITMASK;
1808                 LOG10_TIMES_2048[most_significant_bit as usize][lower_bits as usize]
1809         }
1810
1811         #[cfg(test)]
1812         mod tests {
1813                 use super::*;
1814
1815                 #[test]
1816                 fn prints_negative_log10_times_2048_lookup_table() {
1817                         for msb in 0..BITS {
1818                                 for i in 0..LOWER_BITS_BOUND {
1819                                         let x = ((LOWER_BITS_BOUND + i) << (HIGHEST_BIT - LOWER_BITS)) >> (HIGHEST_BIT - msb);
1820                                         let log10_times_2048 = ((x as f64).log10() * 2048.0).round() as u16;
1821                                         assert_eq!(log10_times_2048, LOG10_TIMES_2048[msb as usize][i as usize]);
1822
1823                                         if i % LOWER_BITS_BOUND == 0 {
1824                                                 print!("\t\t[{}, ", log10_times_2048);
1825                                         } else if i % LOWER_BITS_BOUND == LOWER_BITS_BOUND - 1 {
1826                                                 println!("{}],", log10_times_2048);
1827                                         } else if i % (LOWER_BITS_BOUND/4) == LOWER_BITS_BOUND/4 - 1 {
1828                                                 print!("{},\n\t\t\t", log10_times_2048);
1829                                         } else {
1830                                                 print!("{}, ", log10_times_2048);
1831                                         }
1832                                 }
1833                         }
1834                 }
1835         }
1836 }
1837
1838 mod bucketed_history {
1839         use super::*;
1840
1841         // Because liquidity is often skewed heavily in one direction, we store historical state
1842         // distribution in buckets of different size. For backwards compatibility, buckets of size 1/8th
1843         // must fit evenly into the buckets here.
1844         //
1845         // The smallest bucket is 2^-14th of the channel, for each of our 32 buckets here we define the
1846         // width of the bucket in 2^14'ths of the channel. This increases exponentially until we reach
1847         // a full 16th of the channel's capacity, which is reapeated a few times for backwards
1848         // compatibility. The four middle buckets represent full octiles of the channel's capacity.
1849         //
1850         // For a 1 BTC channel, this let's us differentiate between failures in the bottom 6k sats, or
1851         // between the 12,000th sat and 24,000th sat, while only needing to store and operate on 32
1852         // buckets in total.
1853
1854         const BUCKET_START_POS: [u16; 33] = [
1855                 0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 3072, 4096, 6144, 8192, 10240, 12288,
1856                 13312, 14336, 15360, 15872, 16128, 16256, 16320, 16352, 16368, 16376, 16380, 16382, 16383, 16384,
1857         ];
1858
1859         const LEGACY_TO_BUCKET_RANGE: [(u8, u8); 8] = [
1860                 (0, 12), (12, 14), (14, 15), (15, 16), (16, 17), (17, 18), (18, 20), (20, 32)
1861         ];
1862
1863         const POSITION_TICKS: u16 = 1 << 14;
1864
1865         fn pos_to_bucket(pos: u16) -> usize {
1866                 for bucket in 0..32 {
1867                         if pos < BUCKET_START_POS[bucket + 1] {
1868                                 return bucket;
1869                         }
1870                 }
1871                 debug_assert!(false);
1872                 return 32;
1873         }
1874
1875         #[cfg(test)]
1876         #[test]
1877         fn check_bucket_maps() {
1878                 const BUCKET_WIDTH_IN_16384S: [u16; 32] = [
1879                         1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 1024, 1024, 2048, 2048,
1880                         2048, 2048, 1024, 1024, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 1];
1881
1882                 let mut min_size_iter = 0;
1883                 let mut legacy_bucket_iter = 0;
1884                 for (bucket, width) in BUCKET_WIDTH_IN_16384S.iter().enumerate() {
1885                         assert_eq!(BUCKET_START_POS[bucket], min_size_iter);
1886                         for i in 0..*width {
1887                                 assert_eq!(pos_to_bucket(min_size_iter + i) as usize, bucket);
1888                         }
1889                         min_size_iter += *width;
1890                         if min_size_iter % (POSITION_TICKS / 8) == 0 {
1891                                 assert_eq!(LEGACY_TO_BUCKET_RANGE[legacy_bucket_iter].1 as usize, bucket + 1);
1892                                 if legacy_bucket_iter + 1 < 8 {
1893                                         assert_eq!(LEGACY_TO_BUCKET_RANGE[legacy_bucket_iter + 1].0 as usize, bucket + 1);
1894                                 }
1895                                 legacy_bucket_iter += 1;
1896                         }
1897                 }
1898                 assert_eq!(BUCKET_START_POS[32], POSITION_TICKS);
1899                 assert_eq!(min_size_iter, POSITION_TICKS);
1900         }
1901
1902         #[inline]
1903         fn amount_to_pos(amount_msat: u64, capacity_msat: u64) -> u16 {
1904                 let pos = if amount_msat < u64::max_value() / (POSITION_TICKS as u64) {
1905                         (amount_msat * (POSITION_TICKS as u64) / capacity_msat.saturating_add(1))
1906                                 .try_into().unwrap_or(POSITION_TICKS)
1907                 } else {
1908                         // Only use 128-bit arithmetic when multiplication will overflow to avoid 128-bit
1909                         // division. This branch should only be hit in fuzz testing since the amount would
1910                         // need to be over 2.88 million BTC in practice.
1911                         ((amount_msat as u128) * (POSITION_TICKS as u128)
1912                                         / (capacity_msat as u128).saturating_add(1))
1913                                 .try_into().unwrap_or(POSITION_TICKS)
1914                 };
1915                 // If we are running in a client that doesn't validate gossip, its possible for a channel's
1916                 // capacity to change due to a `channel_update` message which, if received while a payment
1917                 // is in-flight, could cause this to fail. Thus, we only assert in test.
1918                 #[cfg(test)]
1919                 debug_assert!(pos < POSITION_TICKS);
1920                 pos
1921         }
1922
1923         /// Prior to LDK 0.0.117 we used eight buckets which were split evenly across the either
1924         /// octiles. This was changed to use 32 buckets for accuracy reasons in 0.0.117, however we
1925         /// support reading the legacy values here for backwards compatibility.
1926         pub(super) struct LegacyHistoricalBucketRangeTracker {
1927                 buckets: [u16; 8],
1928         }
1929
1930         impl LegacyHistoricalBucketRangeTracker {
1931                 pub(crate) fn into_current(&self) -> HistoricalBucketRangeTracker {
1932                         let mut buckets = [0; 32];
1933                         for (idx, legacy_bucket) in self.buckets.iter().enumerate() {
1934                                 let mut new_val = *legacy_bucket;
1935                                 let (start, end) = LEGACY_TO_BUCKET_RANGE[idx];
1936                                 new_val /= (end - start) as u16;
1937                                 for i in start..end {
1938                                         buckets[i as usize] = new_val;
1939                                 }
1940                         }
1941                         HistoricalBucketRangeTracker { buckets }
1942                 }
1943         }
1944
1945         /// Tracks the historical state of a distribution as a weighted average of how much time was spent
1946         /// in each of 32 buckets.
1947         #[derive(Clone, Copy)]
1948         pub(super) struct HistoricalBucketRangeTracker {
1949                 pub(super) buckets: [u16; 32],
1950         }
1951
1952         /// Buckets are stored in fixed point numbers with a 5 bit fractional part. Thus, the value
1953         /// "one" is 32, or this constant.
1954         pub const BUCKET_FIXED_POINT_ONE: u16 = 32;
1955
1956         impl HistoricalBucketRangeTracker {
1957                 pub(super) fn new() -> Self { Self { buckets: [0; 32] } }
1958                 pub(super) fn track_datapoint(&mut self, liquidity_offset_msat: u64, capacity_msat: u64) {
1959                         // We have 32 leaky buckets for min and max liquidity. Each bucket tracks the amount of time
1960                         // we spend in each bucket as a 16-bit fixed-point number with a 5 bit fractional part.
1961                         //
1962                         // Each time we update our liquidity estimate, we add 32 (1.0 in our fixed-point system) to
1963                         // the buckets for the current min and max liquidity offset positions.
1964                         //
1965                         // We then decay each bucket by multiplying by 2047/2048 (avoiding dividing by a
1966                         // non-power-of-two). This ensures we can't actually overflow the u16 - when we get to
1967                         // 63,457 adding 32 and decaying by 2047/2048 leaves us back at 63,457.
1968                         //
1969                         // In total, this allows us to track data for the last 8,000 or so payments across a given
1970                         // channel.
1971                         //
1972                         // These constants are a balance - we try to fit in 2 bytes per bucket to reduce overhead,
1973                         // and need to balance having more bits in the decimal part (to ensure decay isn't too
1974                         // non-linear) with having too few bits in the mantissa, causing us to not store very many
1975                         // datapoints.
1976                         //
1977                         // The constants were picked experimentally, selecting a decay amount that restricts us
1978                         // from overflowing buckets without having to cap them manually.
1979
1980                         let pos: u16 = amount_to_pos(liquidity_offset_msat, capacity_msat);
1981                         if pos < POSITION_TICKS {
1982                                 for e in self.buckets.iter_mut() {
1983                                         *e = ((*e as u32) * 2047 / 2048) as u16;
1984                                 }
1985                                 let bucket = pos_to_bucket(pos);
1986                                 self.buckets[bucket] = self.buckets[bucket].saturating_add(BUCKET_FIXED_POINT_ONE);
1987                         }
1988                 }
1989                 /// Decay all buckets by the given number of half-lives. Used to more aggressively remove old
1990                 /// datapoints as we receive newer information.
1991                 #[inline]
1992                 pub(super) fn time_decay_data(&mut self, half_lives: u32) {
1993                         for e in self.buckets.iter_mut() {
1994                                 *e = e.checked_shr(half_lives).unwrap_or(0);
1995                         }
1996                 }
1997         }
1998
1999         impl_writeable_tlv_based!(HistoricalBucketRangeTracker, { (0, buckets, required) });
2000         impl_writeable_tlv_based!(LegacyHistoricalBucketRangeTracker, { (0, buckets, required) });
2001
2002         /// A set of buckets representing the history of where we've seen the minimum- and maximum-
2003         /// liquidity bounds for a given channel.
2004         pub(super) struct HistoricalMinMaxBuckets<D: Deref<Target = HistoricalBucketRangeTracker>> {
2005                 /// Buckets tracking where and how often we've seen the minimum liquidity bound for a
2006                 /// channel.
2007                 pub(super) min_liquidity_offset_history: D,
2008                 /// Buckets tracking where and how often we've seen the maximum liquidity bound for a
2009                 /// channel.
2010                 pub(super) max_liquidity_offset_history: D,
2011         }
2012
2013         impl<D: Deref<Target = HistoricalBucketRangeTracker>> HistoricalMinMaxBuckets<D> {
2014                 #[inline]
2015                 pub(super) fn calculate_success_probability_times_billion(
2016                         &self, params: &ProbabilisticScoringFeeParameters, amount_msat: u64,
2017                         capacity_msat: u64
2018                 ) -> Option<u64> {
2019                         // If historical penalties are enabled, we try to calculate a probability of success
2020                         // given our historical distribution of min- and max-liquidity bounds in a channel.
2021                         // To do so, we walk the set of historical liquidity bucket (min, max) combinations
2022                         // (where min_idx < max_idx, as having a minimum above our maximum is an invalid
2023                         // state). For each pair, we calculate the probability as if the bucket's corresponding
2024                         // min- and max- liquidity bounds were our current liquidity bounds and then multiply
2025                         // that probability by the weight of the selected buckets.
2026                         let payment_pos = amount_to_pos(amount_msat, capacity_msat);
2027                         if payment_pos >= POSITION_TICKS { return None; }
2028
2029                         let mut total_valid_points_tracked = 0;
2030                         for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate() {
2031                                 for max_bucket in self.max_liquidity_offset_history.buckets.iter().take(32 - min_idx) {
2032                                         total_valid_points_tracked += (*min_bucket as u64) * (*max_bucket as u64);
2033                                 }
2034                         }
2035
2036                         // If the total valid points is smaller than 1.0 (i.e. 32 in our fixed-point scheme),
2037                         // treat it as if we were fully decayed.
2038                         const FULLY_DECAYED: u16 = BUCKET_FIXED_POINT_ONE * BUCKET_FIXED_POINT_ONE;
2039                         if total_valid_points_tracked < FULLY_DECAYED.into() {
2040                                 return None;
2041                         }
2042
2043                         let mut cumulative_success_prob_times_billion = 0;
2044                         // Special-case the 0th min bucket - it generally means we failed a payment, so only
2045                         // consider the highest (i.e. largest-offset-from-max-capacity) max bucket for all
2046                         // points against the 0th min bucket. This avoids the case where we fail to route
2047                         // increasingly lower values over a channel, but treat each failure as a separate
2048                         // datapoint, many of which may have relatively high maximum-available-liquidity
2049                         // values, which will result in us thinking we have some nontrivial probability of
2050                         // routing up to that amount.
2051                         if self.min_liquidity_offset_history.buckets[0] != 0 {
2052                                 let mut highest_max_bucket_with_points = 0; // The highest max-bucket with any data
2053                                 let mut total_max_points = 0; // Total points in max-buckets to consider
2054                                 for (max_idx, max_bucket) in self.max_liquidity_offset_history.buckets.iter().enumerate() {
2055                                         if *max_bucket >= BUCKET_FIXED_POINT_ONE {
2056                                                 highest_max_bucket_with_points = cmp::max(highest_max_bucket_with_points, max_idx);
2057                                         }
2058                                         total_max_points += *max_bucket as u64;
2059                                 }
2060                                 let max_bucket_end_pos = BUCKET_START_POS[32 - highest_max_bucket_with_points] - 1;
2061                                 if payment_pos < max_bucket_end_pos {
2062                                         let (numerator, denominator) = success_probability(payment_pos as u64, 0,
2063                                                 max_bucket_end_pos as u64, POSITION_TICKS as u64 - 1, params, true);
2064                                         let bucket_prob_times_billion =
2065                                                 (self.min_liquidity_offset_history.buckets[0] as u64) * total_max_points
2066                                                         * 1024 * 1024 * 1024 / total_valid_points_tracked;
2067                                         cumulative_success_prob_times_billion += bucket_prob_times_billion *
2068                                                 numerator / denominator;
2069                                 }
2070                         }
2071
2072                         for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate().skip(1) {
2073                                 let min_bucket_start_pos = BUCKET_START_POS[min_idx];
2074                                 for (max_idx, max_bucket) in self.max_liquidity_offset_history.buckets.iter().enumerate().take(32 - min_idx) {
2075                                         let max_bucket_end_pos = BUCKET_START_POS[32 - max_idx] - 1;
2076                                         // Note that this multiply can only barely not overflow - two 16 bit ints plus
2077                                         // 30 bits is 62 bits.
2078                                         let bucket_prob_times_billion = (*min_bucket as u64) * (*max_bucket as u64)
2079                                                 * 1024 * 1024 * 1024 / total_valid_points_tracked;
2080                                         if payment_pos >= max_bucket_end_pos {
2081                                                 // Success probability 0, the payment amount may be above the max liquidity
2082                                                 break;
2083                                         } else if payment_pos < min_bucket_start_pos {
2084                                                 cumulative_success_prob_times_billion += bucket_prob_times_billion;
2085                                         } else {
2086                                                 let (numerator, denominator) = success_probability(payment_pos as u64,
2087                                                         min_bucket_start_pos as u64, max_bucket_end_pos as u64,
2088                                                         POSITION_TICKS as u64 - 1, params, true);
2089                                                 cumulative_success_prob_times_billion += bucket_prob_times_billion *
2090                                                         numerator / denominator;
2091                                         }
2092                                 }
2093                         }
2094
2095                         Some(cumulative_success_prob_times_billion)
2096                 }
2097         }
2098 }
2099 use bucketed_history::{LegacyHistoricalBucketRangeTracker, HistoricalBucketRangeTracker, HistoricalMinMaxBuckets};
2100
2101 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Writeable for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
2102         #[inline]
2103         fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
2104                 write_tlv_fields!(w, {
2105                         (0, self.channel_liquidities, required),
2106                 });
2107                 Ok(())
2108         }
2109 }
2110
2111 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time>
2112 ReadableArgs<(ProbabilisticScoringDecayParameters, G, L)> for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
2113         #[inline]
2114         fn read<R: Read>(
2115                 r: &mut R, args: (ProbabilisticScoringDecayParameters, G, L)
2116         ) -> Result<Self, DecodeError> {
2117                 let (decay_params, network_graph, logger) = args;
2118                 let mut channel_liquidities = HashMap::new();
2119                 read_tlv_fields!(r, {
2120                         (0, channel_liquidities, required),
2121                 });
2122                 Ok(Self {
2123                         decay_params,
2124                         network_graph,
2125                         logger,
2126                         channel_liquidities,
2127                 })
2128         }
2129 }
2130
2131 impl<T: Time> Writeable for ChannelLiquidity<T> {
2132         #[inline]
2133         fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
2134                 let offset_history_duration_since_epoch =
2135                         T::duration_since_epoch() - self.offset_history_last_updated.elapsed();
2136                 let duration_since_epoch = T::duration_since_epoch() - self.last_updated.elapsed();
2137                 write_tlv_fields!(w, {
2138                         (0, self.min_liquidity_offset_msat, required),
2139                         // 1 was the min_liquidity_offset_history in octile form
2140                         (2, self.max_liquidity_offset_msat, required),
2141                         // 3 was the max_liquidity_offset_history in octile form
2142                         (4, duration_since_epoch, required),
2143                         (5, Some(self.min_liquidity_offset_history), option),
2144                         (7, Some(self.max_liquidity_offset_history), option),
2145                         (9, offset_history_duration_since_epoch, required),
2146                 });
2147                 Ok(())
2148         }
2149 }
2150
2151 impl<T: Time> Readable for ChannelLiquidity<T> {
2152         #[inline]
2153         fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
2154                 let mut min_liquidity_offset_msat = 0;
2155                 let mut max_liquidity_offset_msat = 0;
2156                 let mut legacy_min_liq_offset_history: Option<LegacyHistoricalBucketRangeTracker> = None;
2157                 let mut legacy_max_liq_offset_history: Option<LegacyHistoricalBucketRangeTracker> = None;
2158                 let mut min_liquidity_offset_history: Option<HistoricalBucketRangeTracker> = None;
2159                 let mut max_liquidity_offset_history: Option<HistoricalBucketRangeTracker> = None;
2160                 let mut duration_since_epoch = Duration::from_secs(0);
2161                 let mut offset_history_duration_since_epoch = None;
2162                 read_tlv_fields!(r, {
2163                         (0, min_liquidity_offset_msat, required),
2164                         (1, legacy_min_liq_offset_history, option),
2165                         (2, max_liquidity_offset_msat, required),
2166                         (3, legacy_max_liq_offset_history, option),
2167                         (4, duration_since_epoch, required),
2168                         (5, min_liquidity_offset_history, option),
2169                         (7, max_liquidity_offset_history, option),
2170                         (9, offset_history_duration_since_epoch, option),
2171                 });
2172                 // On rust prior to 1.60 `Instant::duration_since` will panic if time goes backwards.
2173                 // We write `last_updated` as wallclock time even though its ultimately an `Instant` (which
2174                 // is a time from a monotonic clock usually represented as an offset against boot time).
2175                 // Thus, we have to construct an `Instant` by subtracting the difference in wallclock time
2176                 // from the one that was written. However, because `Instant` can panic if we construct one
2177                 // in the future, we must handle wallclock time jumping backwards, which we do by simply
2178                 // using `Instant::now()` in that case.
2179                 let wall_clock_now = T::duration_since_epoch();
2180                 let now = T::now();
2181                 let last_updated = if wall_clock_now > duration_since_epoch {
2182                         now - (wall_clock_now - duration_since_epoch)
2183                 } else { now };
2184
2185                 let offset_history_duration_since_epoch =
2186                         offset_history_duration_since_epoch.unwrap_or(duration_since_epoch);
2187                 let offset_history_last_updated = if wall_clock_now > offset_history_duration_since_epoch {
2188                         now - (wall_clock_now - offset_history_duration_since_epoch)
2189                 } else { now };
2190
2191                 if min_liquidity_offset_history.is_none() {
2192                         if let Some(legacy_buckets) = legacy_min_liq_offset_history {
2193                                 min_liquidity_offset_history = Some(legacy_buckets.into_current());
2194                         } else {
2195                                 min_liquidity_offset_history = Some(HistoricalBucketRangeTracker::new());
2196                         }
2197                 }
2198                 if max_liquidity_offset_history.is_none() {
2199                         if let Some(legacy_buckets) = legacy_max_liq_offset_history {
2200                                 max_liquidity_offset_history = Some(legacy_buckets.into_current());
2201                         } else {
2202                                 max_liquidity_offset_history = Some(HistoricalBucketRangeTracker::new());
2203                         }
2204                 }
2205                 Ok(Self {
2206                         min_liquidity_offset_msat,
2207                         max_liquidity_offset_msat,
2208                         min_liquidity_offset_history: min_liquidity_offset_history.unwrap(),
2209                         max_liquidity_offset_history: max_liquidity_offset_history.unwrap(),
2210                         last_updated,
2211                         offset_history_last_updated,
2212                 })
2213         }
2214 }
2215
2216 #[cfg(test)]
2217 mod tests {
2218         use super::{ChannelLiquidity, HistoricalBucketRangeTracker, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters, ProbabilisticScorerUsingTime};
2219         use crate::blinded_path::{BlindedHop, BlindedPath};
2220         use crate::util::config::UserConfig;
2221         use crate::util::time::Time;
2222         use crate::util::time::tests::SinceEpoch;
2223
2224         use crate::ln::channelmanager;
2225         use crate::ln::msgs::{ChannelAnnouncement, ChannelUpdate, UnsignedChannelAnnouncement, UnsignedChannelUpdate};
2226         use crate::routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId};
2227         use crate::routing::router::{BlindedTail, Path, RouteHop, CandidateRouteHop};
2228         use crate::routing::scoring::{ChannelUsage, ScoreLookUp, ScoreUpdate};
2229         use crate::util::ser::{ReadableArgs, Writeable};
2230         use crate::util::test_utils::{self, TestLogger};
2231
2232         use bitcoin::blockdata::constants::ChainHash;
2233         use bitcoin::hashes::Hash;
2234         use bitcoin::hashes::sha256d::Hash as Sha256dHash;
2235         use bitcoin::network::constants::Network;
2236         use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey};
2237         use core::time::Duration;
2238         use crate::io;
2239
2240         fn source_privkey() -> SecretKey {
2241                 SecretKey::from_slice(&[42; 32]).unwrap()
2242         }
2243
2244         fn target_privkey() -> SecretKey {
2245                 SecretKey::from_slice(&[43; 32]).unwrap()
2246         }
2247
2248         fn source_pubkey() -> PublicKey {
2249                 let secp_ctx = Secp256k1::new();
2250                 PublicKey::from_secret_key(&secp_ctx, &source_privkey())
2251         }
2252
2253         fn target_pubkey() -> PublicKey {
2254                 let secp_ctx = Secp256k1::new();
2255                 PublicKey::from_secret_key(&secp_ctx, &target_privkey())
2256         }
2257
2258         fn source_node_id() -> NodeId {
2259                 NodeId::from_pubkey(&source_pubkey())
2260         }
2261
2262         fn target_node_id() -> NodeId {
2263                 NodeId::from_pubkey(&target_pubkey())
2264         }
2265
2266         // `ProbabilisticScorer` tests
2267
2268         /// A probabilistic scorer for testing with time that can be manually advanced.
2269         type ProbabilisticScorer<'a> = ProbabilisticScorerUsingTime::<&'a NetworkGraph<&'a TestLogger>, &'a TestLogger, SinceEpoch>;
2270
2271         fn sender_privkey() -> SecretKey {
2272                 SecretKey::from_slice(&[41; 32]).unwrap()
2273         }
2274
2275         fn recipient_privkey() -> SecretKey {
2276                 SecretKey::from_slice(&[45; 32]).unwrap()
2277         }
2278
2279         fn sender_pubkey() -> PublicKey {
2280                 let secp_ctx = Secp256k1::new();
2281                 PublicKey::from_secret_key(&secp_ctx, &sender_privkey())
2282         }
2283
2284         fn recipient_pubkey() -> PublicKey {
2285                 let secp_ctx = Secp256k1::new();
2286                 PublicKey::from_secret_key(&secp_ctx, &recipient_privkey())
2287         }
2288
2289         fn recipient_node_id() -> NodeId {
2290                 NodeId::from_pubkey(&recipient_pubkey())
2291         }
2292
2293         fn network_graph(logger: &TestLogger) -> NetworkGraph<&TestLogger> {
2294                 let mut network_graph = NetworkGraph::new(Network::Testnet, logger);
2295                 add_channel(&mut network_graph, 42, source_privkey(), target_privkey());
2296                 add_channel(&mut network_graph, 43, target_privkey(), recipient_privkey());
2297
2298                 network_graph
2299         }
2300
2301         fn add_channel(
2302                 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_1_key: SecretKey,
2303                 node_2_key: SecretKey
2304         ) {
2305                 let genesis_hash = ChainHash::using_genesis_block(Network::Testnet);
2306                 let node_1_secret = &SecretKey::from_slice(&[39; 32]).unwrap();
2307                 let node_2_secret = &SecretKey::from_slice(&[40; 32]).unwrap();
2308                 let secp_ctx = Secp256k1::new();
2309                 let unsigned_announcement = UnsignedChannelAnnouncement {
2310                         features: channelmanager::provided_channel_features(&UserConfig::default()),
2311                         chain_hash: genesis_hash,
2312                         short_channel_id,
2313                         node_id_1: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_1_key)),
2314                         node_id_2: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_2_key)),
2315                         bitcoin_key_1: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_1_secret)),
2316                         bitcoin_key_2: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_2_secret)),
2317                         excess_data: Vec::new(),
2318                 };
2319                 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
2320                 let signed_announcement = ChannelAnnouncement {
2321                         node_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_key),
2322                         node_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_key),
2323                         bitcoin_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_secret),
2324                         bitcoin_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_secret),
2325                         contents: unsigned_announcement,
2326                 };
2327                 let chain_source: Option<&crate::util::test_utils::TestChainSource> = None;
2328                 network_graph.update_channel_from_announcement(
2329                         &signed_announcement, &chain_source).unwrap();
2330                 update_channel(network_graph, short_channel_id, node_1_key, 0, 1_000, 100);
2331                 update_channel(network_graph, short_channel_id, node_2_key, 1, 0, 100);
2332         }
2333
2334         fn update_channel(
2335                 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_key: SecretKey,
2336                 flags: u8, htlc_maximum_msat: u64, timestamp: u32,
2337         ) {
2338                 let genesis_hash = ChainHash::using_genesis_block(Network::Testnet);
2339                 let secp_ctx = Secp256k1::new();
2340                 let unsigned_update = UnsignedChannelUpdate {
2341                         chain_hash: genesis_hash,
2342                         short_channel_id,
2343                         timestamp,
2344                         flags,
2345                         cltv_expiry_delta: 18,
2346                         htlc_minimum_msat: 0,
2347                         htlc_maximum_msat,
2348                         fee_base_msat: 1,
2349                         fee_proportional_millionths: 0,
2350                         excess_data: Vec::new(),
2351                 };
2352                 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_update.encode()[..])[..]);
2353                 let signed_update = ChannelUpdate {
2354                         signature: secp_ctx.sign_ecdsa(&msghash, &node_key),
2355                         contents: unsigned_update,
2356                 };
2357                 network_graph.update_channel(&signed_update).unwrap();
2358         }
2359
2360         fn path_hop(pubkey: PublicKey, short_channel_id: u64, fee_msat: u64) -> RouteHop {
2361                 let config = UserConfig::default();
2362                 RouteHop {
2363                         pubkey,
2364                         node_features: channelmanager::provided_node_features(&config),
2365                         short_channel_id,
2366                         channel_features: channelmanager::provided_channel_features(&config),
2367                         fee_msat,
2368                         cltv_expiry_delta: 18,
2369                         maybe_announced_channel: true,
2370                 }
2371         }
2372
2373         fn payment_path_for_amount(amount_msat: u64) -> Path {
2374                 Path {
2375                         hops: vec![
2376                                 path_hop(source_pubkey(), 41, 1),
2377                                 path_hop(target_pubkey(), 42, 2),
2378                                 path_hop(recipient_pubkey(), 43, amount_msat),
2379                         ], blinded_tail: None,
2380                 }
2381         }
2382
2383         #[test]
2384         fn liquidity_bounds_directed_from_lowest_node_id() {
2385                 let logger = TestLogger::new();
2386                 let last_updated = SinceEpoch::now();
2387                 let offset_history_last_updated = SinceEpoch::now();
2388                 let network_graph = network_graph(&logger);
2389                 let decay_params = ProbabilisticScoringDecayParameters::default();
2390                 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2391                         .with_channel(42,
2392                                 ChannelLiquidity {
2393                                         min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100,
2394                                         last_updated, offset_history_last_updated,
2395                                         min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2396                                         max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2397                                 })
2398                         .with_channel(43,
2399                                 ChannelLiquidity {
2400                                         min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100,
2401                                         last_updated, offset_history_last_updated,
2402                                         min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2403                                         max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2404                                 });
2405                 let source = source_node_id();
2406                 let target = target_node_id();
2407                 let recipient = recipient_node_id();
2408                 assert!(source > target);
2409                 assert!(target < recipient);
2410
2411                 // Update minimum liquidity.
2412
2413                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2414                         .as_directed(&source, &target, 1_000, decay_params);
2415                 assert_eq!(liquidity.min_liquidity_msat(), 100);
2416                 assert_eq!(liquidity.max_liquidity_msat(), 300);
2417
2418                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2419                         .as_directed(&target, &source, 1_000, decay_params);
2420                 assert_eq!(liquidity.min_liquidity_msat(), 700);
2421                 assert_eq!(liquidity.max_liquidity_msat(), 900);
2422
2423                 scorer.channel_liquidities.get_mut(&42).unwrap()
2424                         .as_directed_mut(&source, &target, 1_000, decay_params)
2425                         .set_min_liquidity_msat(200, Duration::ZERO);
2426
2427                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2428                         .as_directed(&source, &target, 1_000, decay_params);
2429                 assert_eq!(liquidity.min_liquidity_msat(), 200);
2430                 assert_eq!(liquidity.max_liquidity_msat(), 300);
2431
2432                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2433                         .as_directed(&target, &source, 1_000, decay_params);
2434                 assert_eq!(liquidity.min_liquidity_msat(), 700);
2435                 assert_eq!(liquidity.max_liquidity_msat(), 800);
2436
2437                 // Update maximum liquidity.
2438
2439                 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2440                         .as_directed(&target, &recipient, 1_000, decay_params);
2441                 assert_eq!(liquidity.min_liquidity_msat(), 700);
2442                 assert_eq!(liquidity.max_liquidity_msat(), 900);
2443
2444                 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2445                         .as_directed(&recipient, &target, 1_000, decay_params);
2446                 assert_eq!(liquidity.min_liquidity_msat(), 100);
2447                 assert_eq!(liquidity.max_liquidity_msat(), 300);
2448
2449                 scorer.channel_liquidities.get_mut(&43).unwrap()
2450                         .as_directed_mut(&target, &recipient, 1_000, decay_params)
2451                         .set_max_liquidity_msat(200, Duration::ZERO);
2452
2453                 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2454                         .as_directed(&target, &recipient, 1_000, decay_params);
2455                 assert_eq!(liquidity.min_liquidity_msat(), 0);
2456                 assert_eq!(liquidity.max_liquidity_msat(), 200);
2457
2458                 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2459                         .as_directed(&recipient, &target, 1_000, decay_params);
2460                 assert_eq!(liquidity.min_liquidity_msat(), 800);
2461                 assert_eq!(liquidity.max_liquidity_msat(), 1000);
2462         }
2463
2464         #[test]
2465         fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() {
2466                 let logger = TestLogger::new();
2467                 let last_updated = SinceEpoch::now();
2468                 let offset_history_last_updated = SinceEpoch::now();
2469                 let network_graph = network_graph(&logger);
2470                 let decay_params = ProbabilisticScoringDecayParameters::default();
2471                 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2472                         .with_channel(42,
2473                                 ChannelLiquidity {
2474                                         min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400,
2475                                         last_updated, offset_history_last_updated,
2476                                         min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2477                                         max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2478                                 });
2479                 let source = source_node_id();
2480                 let target = target_node_id();
2481                 assert!(source > target);
2482
2483                 // Check initial bounds.
2484                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2485                         .as_directed(&source, &target, 1_000, decay_params);
2486                 assert_eq!(liquidity.min_liquidity_msat(), 400);
2487                 assert_eq!(liquidity.max_liquidity_msat(), 800);
2488
2489                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2490                         .as_directed(&target, &source, 1_000, decay_params);
2491                 assert_eq!(liquidity.min_liquidity_msat(), 200);
2492                 assert_eq!(liquidity.max_liquidity_msat(), 600);
2493
2494                 // Reset from source to target.
2495                 scorer.channel_liquidities.get_mut(&42).unwrap()
2496                         .as_directed_mut(&source, &target, 1_000, decay_params)
2497                         .set_min_liquidity_msat(900, Duration::ZERO);
2498
2499                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2500                         .as_directed(&source, &target, 1_000, decay_params);
2501                 assert_eq!(liquidity.min_liquidity_msat(), 900);
2502                 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2503
2504                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2505                         .as_directed(&target, &source, 1_000, decay_params);
2506                 assert_eq!(liquidity.min_liquidity_msat(), 0);
2507                 assert_eq!(liquidity.max_liquidity_msat(), 100);
2508
2509                 // Reset from target to source.
2510                 scorer.channel_liquidities.get_mut(&42).unwrap()
2511                         .as_directed_mut(&target, &source, 1_000, decay_params)
2512                         .set_min_liquidity_msat(400, Duration::ZERO);
2513
2514                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2515                         .as_directed(&source, &target, 1_000, decay_params);
2516                 assert_eq!(liquidity.min_liquidity_msat(), 0);
2517                 assert_eq!(liquidity.max_liquidity_msat(), 600);
2518
2519                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2520                         .as_directed(&target, &source, 1_000, decay_params);
2521                 assert_eq!(liquidity.min_liquidity_msat(), 400);
2522                 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2523         }
2524
2525         #[test]
2526         fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() {
2527                 let logger = TestLogger::new();
2528                 let last_updated = SinceEpoch::now();
2529                 let offset_history_last_updated = SinceEpoch::now();
2530                 let network_graph = network_graph(&logger);
2531                 let decay_params = ProbabilisticScoringDecayParameters::default();
2532                 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2533                         .with_channel(42,
2534                                 ChannelLiquidity {
2535                                         min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400,
2536                                         last_updated, offset_history_last_updated,
2537                                         min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2538                                         max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2539                                 });
2540                 let source = source_node_id();
2541                 let target = target_node_id();
2542                 assert!(source > target);
2543
2544                 // Check initial bounds.
2545                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2546                         .as_directed(&source, &target, 1_000, decay_params);
2547                 assert_eq!(liquidity.min_liquidity_msat(), 400);
2548                 assert_eq!(liquidity.max_liquidity_msat(), 800);
2549
2550                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2551                         .as_directed(&target, &source, 1_000, decay_params);
2552                 assert_eq!(liquidity.min_liquidity_msat(), 200);
2553                 assert_eq!(liquidity.max_liquidity_msat(), 600);
2554
2555                 // Reset from source to target.
2556                 scorer.channel_liquidities.get_mut(&42).unwrap()
2557                         .as_directed_mut(&source, &target, 1_000, decay_params)
2558                         .set_max_liquidity_msat(300, Duration::ZERO);
2559
2560                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2561                         .as_directed(&source, &target, 1_000, decay_params);
2562                 assert_eq!(liquidity.min_liquidity_msat(), 0);
2563                 assert_eq!(liquidity.max_liquidity_msat(), 300);
2564
2565                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2566                         .as_directed(&target, &source, 1_000, decay_params);
2567                 assert_eq!(liquidity.min_liquidity_msat(), 700);
2568                 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2569
2570                 // Reset from target to source.
2571                 scorer.channel_liquidities.get_mut(&42).unwrap()
2572                         .as_directed_mut(&target, &source, 1_000, decay_params)
2573                         .set_max_liquidity_msat(600, Duration::ZERO);
2574
2575                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2576                         .as_directed(&source, &target, 1_000, decay_params);
2577                 assert_eq!(liquidity.min_liquidity_msat(), 400);
2578                 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2579
2580                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2581                         .as_directed(&target, &source, 1_000, decay_params);
2582                 assert_eq!(liquidity.min_liquidity_msat(), 0);
2583                 assert_eq!(liquidity.max_liquidity_msat(), 600);
2584         }
2585
2586         #[test]
2587         fn increased_penalty_nearing_liquidity_upper_bound() {
2588                 let logger = TestLogger::new();
2589                 let network_graph = network_graph(&logger);
2590                 let params = ProbabilisticScoringFeeParameters {
2591                         liquidity_penalty_multiplier_msat: 1_000,
2592                         ..ProbabilisticScoringFeeParameters::zero_penalty()
2593                 };
2594                 let decay_params = ProbabilisticScoringDecayParameters::default();
2595                 let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2596                 let source = source_node_id();
2597
2598                 let usage = ChannelUsage {
2599                         amount_msat: 1_024,
2600                         inflight_htlc_msat: 0,
2601                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
2602                 };
2603                 let network_graph = network_graph.read_only();
2604                 let channel = network_graph.channel(42).unwrap();
2605                 let (info, _) = channel.as_directed_from(&source).unwrap();
2606                 let candidate = CandidateRouteHop::PublicHop {
2607                         info,
2608                         short_channel_id: 42,
2609                 };
2610                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 0);
2611                 let usage = ChannelUsage { amount_msat: 10_240, ..usage };
2612                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 0);
2613                 let usage = ChannelUsage { amount_msat: 102_400, ..usage };
2614                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 47);
2615                 let usage = ChannelUsage { amount_msat: 1_023_999, ..usage };
2616                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 2_000);
2617
2618                 let usage = ChannelUsage {
2619                         amount_msat: 128,
2620                         inflight_htlc_msat: 0,
2621                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2622                 };
2623                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 58);
2624                 let usage = ChannelUsage { amount_msat: 256, ..usage };
2625                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 125);
2626                 let usage = ChannelUsage { amount_msat: 374, ..usage };
2627                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 198);
2628                 let usage = ChannelUsage { amount_msat: 512, ..usage };
2629                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 300);
2630                 let usage = ChannelUsage { amount_msat: 640, ..usage };
2631                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 425);
2632                 let usage = ChannelUsage { amount_msat: 768, ..usage };
2633                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 602);
2634                 let usage = ChannelUsage { amount_msat: 896, ..usage };
2635                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 902);
2636         }
2637
2638         #[test]
2639         fn constant_penalty_outside_liquidity_bounds() {
2640                 let logger = TestLogger::new();
2641                 let last_updated = SinceEpoch::now();
2642                 let offset_history_last_updated = SinceEpoch::now();
2643                 let network_graph = network_graph(&logger);
2644                 let params = ProbabilisticScoringFeeParameters {
2645                         liquidity_penalty_multiplier_msat: 1_000,
2646                         considered_impossible_penalty_msat: u64::max_value(),
2647                         ..ProbabilisticScoringFeeParameters::zero_penalty()
2648                 };
2649                 let decay_params = ProbabilisticScoringDecayParameters {
2650                         ..ProbabilisticScoringDecayParameters::zero_penalty()
2651                 };
2652                 let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2653                         .with_channel(42,
2654                                 ChannelLiquidity {
2655                                         min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40,
2656                                         last_updated, offset_history_last_updated,
2657                                         min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2658                                         max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2659                                 });
2660                 let source = source_node_id();
2661
2662                 let usage = ChannelUsage {
2663                         amount_msat: 39,
2664                         inflight_htlc_msat: 0,
2665                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 100, htlc_maximum_msat: 1_000 },
2666                 };
2667                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2668                 let (info, _) = channel.as_directed_from(&source).unwrap();
2669                 let candidate = CandidateRouteHop::PublicHop {
2670                         info,
2671                         short_channel_id: 42,
2672                 };
2673                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 0);
2674                 let usage = ChannelUsage { amount_msat: 50, ..usage };
2675                 assert_ne!(scorer.channel_penalty_msat(&candidate, usage, &params), 0);
2676                 assert_ne!(scorer.channel_penalty_msat(&candidate, usage, &params), u64::max_value());
2677                 let usage = ChannelUsage { amount_msat: 61, ..usage };
2678                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), u64::max_value());
2679         }
2680
2681         #[test]
2682         fn does_not_further_penalize_own_channel() {
2683                 let logger = TestLogger::new();
2684                 let network_graph = network_graph(&logger);
2685                 let params = ProbabilisticScoringFeeParameters {
2686                         liquidity_penalty_multiplier_msat: 1_000,
2687                         ..ProbabilisticScoringFeeParameters::zero_penalty()
2688                 };
2689                 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2690                 let source = source_node_id();
2691                 let usage = ChannelUsage {
2692                         amount_msat: 500,
2693                         inflight_htlc_msat: 0,
2694                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2695                 };
2696                 let failed_path = payment_path_for_amount(500);
2697                 let successful_path = payment_path_for_amount(200);
2698                 let channel = &network_graph.read_only().channel(42).unwrap().to_owned();
2699                 let (info, _) = channel.as_directed_from(&source).unwrap();
2700                 let candidate = CandidateRouteHop::PublicHop {
2701                         info,
2702                         short_channel_id: 41,
2703                 };
2704
2705                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 301);
2706
2707                 scorer.payment_path_failed(&failed_path, 41, Duration::ZERO);
2708                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 301);
2709
2710                 scorer.payment_path_successful(&successful_path, Duration::ZERO);
2711                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 301);
2712         }
2713
2714         #[test]
2715         fn sets_liquidity_lower_bound_on_downstream_failure() {
2716                 let logger = TestLogger::new();
2717                 let network_graph = network_graph(&logger);
2718                 let params = ProbabilisticScoringFeeParameters {
2719                         liquidity_penalty_multiplier_msat: 1_000,
2720                         ..ProbabilisticScoringFeeParameters::zero_penalty()
2721                 };
2722                 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2723                 let source = source_node_id();
2724                 let path = payment_path_for_amount(500);
2725
2726                 let usage = ChannelUsage {
2727                         amount_msat: 250,
2728                         inflight_htlc_msat: 0,
2729                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2730                 };
2731                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2732                 let (info, _) = channel.as_directed_from(&source).unwrap();
2733                 let candidate = CandidateRouteHop::PublicHop {
2734                         info,
2735                         short_channel_id: 42,
2736                 };
2737                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 128);
2738                 let usage = ChannelUsage { amount_msat: 500, ..usage };
2739                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 301);
2740                 let usage = ChannelUsage { amount_msat: 750, ..usage };
2741                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 602);
2742
2743                 scorer.payment_path_failed(&path, 43, Duration::ZERO);
2744
2745                 let usage = ChannelUsage { amount_msat: 250, ..usage };
2746                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 0);
2747                 let usage = ChannelUsage { amount_msat: 500, ..usage };
2748                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 0);
2749                 let usage = ChannelUsage { amount_msat: 750, ..usage };
2750                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 300);
2751         }
2752
2753         #[test]
2754         fn sets_liquidity_upper_bound_on_failure() {
2755                 let logger = TestLogger::new();
2756                 let network_graph = network_graph(&logger);
2757                 let params = ProbabilisticScoringFeeParameters {
2758                         liquidity_penalty_multiplier_msat: 1_000,
2759                         considered_impossible_penalty_msat: u64::max_value(),
2760                         ..ProbabilisticScoringFeeParameters::zero_penalty()
2761                 };
2762                 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2763                 let source = source_node_id();
2764                 let path = payment_path_for_amount(500);
2765
2766                 let usage = ChannelUsage {
2767                         amount_msat: 250,
2768                         inflight_htlc_msat: 0,
2769                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2770                 };
2771                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2772                 let (info, _) = channel.as_directed_from(&source).unwrap();
2773                 let candidate = CandidateRouteHop::PublicHop {
2774                         info,
2775                         short_channel_id: 42,
2776                 };
2777                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 128);
2778                 let usage = ChannelUsage { amount_msat: 500, ..usage };
2779                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 301);
2780                 let usage = ChannelUsage { amount_msat: 750, ..usage };
2781                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 602);
2782
2783                 scorer.payment_path_failed(&path, 42, Duration::ZERO);
2784
2785                 let usage = ChannelUsage { amount_msat: 250, ..usage };
2786                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 300);
2787                 let usage = ChannelUsage { amount_msat: 500, ..usage };
2788                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), u64::max_value());
2789                 let usage = ChannelUsage { amount_msat: 750, ..usage };
2790                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), u64::max_value());
2791         }
2792
2793         #[test]
2794         fn ignores_channels_after_removed_failed_channel() {
2795                 // Previously, if we'd tried to send over a channel which was removed from the network
2796                 // graph before we call `payment_path_failed` (which is the default if the we get a "no
2797                 // such channel" error in the `InvoicePayer`), we would call `failed_downstream` on all
2798                 // channels in the route, even ones which they payment never reached. This tests to ensure
2799                 // we do not score such channels.
2800                 let secp_ctx = Secp256k1::new();
2801                 let logger = TestLogger::new();
2802                 let mut network_graph = NetworkGraph::new(Network::Testnet, &logger);
2803                 let secret_a = SecretKey::from_slice(&[42; 32]).unwrap();
2804                 let secret_b = SecretKey::from_slice(&[43; 32]).unwrap();
2805                 let secret_c = SecretKey::from_slice(&[44; 32]).unwrap();
2806                 let secret_d = SecretKey::from_slice(&[45; 32]).unwrap();
2807                 add_channel(&mut network_graph, 42, secret_a, secret_b);
2808                 // Don't add the channel from B -> C.
2809                 add_channel(&mut network_graph, 44, secret_c, secret_d);
2810
2811                 let pub_a = PublicKey::from_secret_key(&secp_ctx, &secret_a);
2812                 let pub_b = PublicKey::from_secret_key(&secp_ctx, &secret_b);
2813                 let pub_c = PublicKey::from_secret_key(&secp_ctx, &secret_c);
2814                 let pub_d = PublicKey::from_secret_key(&secp_ctx, &secret_d);
2815
2816                 let path = vec![
2817                         path_hop(pub_b, 42, 1),
2818                         path_hop(pub_c, 43, 2),
2819                         path_hop(pub_d, 44, 100),
2820                 ];
2821
2822                 let node_a = NodeId::from_pubkey(&pub_a);
2823                 let node_b = NodeId::from_pubkey(&pub_b);
2824                 let node_c = NodeId::from_pubkey(&pub_c);
2825
2826                 let params = ProbabilisticScoringFeeParameters {
2827                         liquidity_penalty_multiplier_msat: 1_000,
2828                         ..ProbabilisticScoringFeeParameters::zero_penalty()
2829                 };
2830                 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2831
2832                 let usage = ChannelUsage {
2833                         amount_msat: 250,
2834                         inflight_htlc_msat: 0,
2835                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2836                 };
2837                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2838                 let (info, _) = channel.as_directed_from(&node_a).unwrap();
2839                 let candidate = CandidateRouteHop::PublicHop {
2840                         info,
2841                         short_channel_id: 42,
2842                 };
2843                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 128);
2844                 // Note that a default liquidity bound is used for B -> C as no channel exists
2845                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2846                 let (info, _) = channel.as_directed_from(&node_b).unwrap();
2847                 let candidate = CandidateRouteHop::PublicHop {
2848                         info,
2849                         short_channel_id: 43,
2850                 };
2851                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 128);
2852                 let channel = network_graph.read_only().channel(44).unwrap().to_owned();
2853                 let (info, _) = channel.as_directed_from(&node_c).unwrap();
2854                 let candidate = CandidateRouteHop::PublicHop {
2855                         info,
2856                         short_channel_id: 44,
2857                 };
2858                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 128);
2859
2860                 scorer.payment_path_failed(&Path { hops: path, blinded_tail: None }, 43, Duration::ZERO);
2861
2862                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2863                 let (info, _) = channel.as_directed_from(&node_a).unwrap();
2864                 let candidate = CandidateRouteHop::PublicHop {
2865                         info,
2866                         short_channel_id: 42,
2867                 };
2868                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 80);
2869                 // Note that a default liquidity bound is used for B -> C as no channel exists
2870                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2871                 let (info, _) = channel.as_directed_from(&node_b).unwrap();
2872                 let candidate = CandidateRouteHop::PublicHop {
2873                         info,
2874                         short_channel_id: 43,
2875                 };
2876                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 128);
2877                 let channel = network_graph.read_only().channel(44).unwrap().to_owned();
2878                 let (info, _) = channel.as_directed_from(&node_c).unwrap();
2879                 let candidate = CandidateRouteHop::PublicHop {
2880                         info,
2881                         short_channel_id: 44,
2882                 };
2883                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 128);
2884         }
2885
2886         #[test]
2887         fn reduces_liquidity_upper_bound_along_path_on_success() {
2888                 let logger = TestLogger::new();
2889                 let network_graph = network_graph(&logger);
2890                 let params = ProbabilisticScoringFeeParameters {
2891                         liquidity_penalty_multiplier_msat: 1_000,
2892                         ..ProbabilisticScoringFeeParameters::zero_penalty()
2893                 };
2894                 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2895                 let source = source_node_id();
2896                 let usage = ChannelUsage {
2897                         amount_msat: 250,
2898                         inflight_htlc_msat: 0,
2899                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2900                 };
2901                 let network_graph = network_graph.read_only().channels().clone();
2902                 let channel_42 = network_graph.get(&42).unwrap();
2903                 let channel_43 = network_graph.get(&43).unwrap();
2904                 let (info, _) = channel_42.as_directed_from(&source).unwrap();
2905                 let candidate_41 = CandidateRouteHop::PublicHop {
2906                         info,
2907                         short_channel_id: 41,
2908                 };
2909                 let (info, target) = channel_42.as_directed_from(&source).unwrap();
2910                 let candidate_42 = CandidateRouteHop::PublicHop {
2911                         info,
2912                         short_channel_id: 42,
2913                 };
2914                 let (info, _) = channel_43.as_directed_from(&target).unwrap();
2915                 let candidate_43 = CandidateRouteHop::PublicHop {
2916                         info,
2917                         short_channel_id: 43,
2918                 };
2919                 assert_eq!(scorer.channel_penalty_msat(&candidate_41, usage, &params), 128);
2920                 assert_eq!(scorer.channel_penalty_msat(&candidate_42, usage, &params), 128);
2921                 assert_eq!(scorer.channel_penalty_msat(&candidate_43, usage, &params), 128);
2922
2923                 scorer.payment_path_successful(&payment_path_for_amount(500), Duration::ZERO);
2924
2925                 assert_eq!(scorer.channel_penalty_msat(&candidate_41, usage, &params), 128);
2926                 assert_eq!(scorer.channel_penalty_msat(&candidate_42, usage, &params), 300);
2927                 assert_eq!(scorer.channel_penalty_msat(&candidate_43, usage, &params), 300);
2928         }
2929
2930         #[test]
2931         fn decays_liquidity_bounds_over_time() {
2932                 let logger = TestLogger::new();
2933                 let network_graph = network_graph(&logger);
2934                 let params = ProbabilisticScoringFeeParameters {
2935                         liquidity_penalty_multiplier_msat: 1_000,
2936                         considered_impossible_penalty_msat: u64::max_value(),
2937                         ..ProbabilisticScoringFeeParameters::zero_penalty()
2938                 };
2939                 let decay_params = ProbabilisticScoringDecayParameters {
2940                         liquidity_offset_half_life: Duration::from_secs(10),
2941                         ..ProbabilisticScoringDecayParameters::zero_penalty()
2942                 };
2943                 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2944                 let source = source_node_id();
2945
2946                 let usage = ChannelUsage {
2947                         amount_msat: 0,
2948                         inflight_htlc_msat: 0,
2949                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
2950                 };
2951                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2952                 let (info, _) = channel.as_directed_from(&source).unwrap();
2953                 let candidate = CandidateRouteHop::PublicHop {
2954                         info,
2955                         short_channel_id: 42,
2956                 };
2957                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 0);
2958                 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
2959                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 2_000);
2960
2961                 scorer.payment_path_failed(&payment_path_for_amount(768), 42, Duration::ZERO);
2962                 scorer.payment_path_failed(&payment_path_for_amount(128), 43, Duration::ZERO);
2963
2964                 // Initial penalties
2965                 let usage = ChannelUsage { amount_msat: 128, ..usage };
2966                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 0);
2967                 let usage = ChannelUsage { amount_msat: 256, ..usage };
2968                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 93);
2969                 let usage = ChannelUsage { amount_msat: 768, ..usage };
2970                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 1_479);
2971                 let usage = ChannelUsage { amount_msat: 896, ..usage };
2972                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), u64::max_value());
2973
2974                 // Half decay (i.e., three-quarter life)
2975                 SinceEpoch::advance(Duration::from_secs(5));
2976                 scorer.decay_liquidity_certainty(Duration::from_secs(5));
2977                 let usage = ChannelUsage { amount_msat: 128, ..usage };
2978                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 22);
2979                 let usage = ChannelUsage { amount_msat: 256, ..usage };
2980                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 106);
2981                 let usage = ChannelUsage { amount_msat: 768, ..usage };
2982                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 921);
2983                 let usage = ChannelUsage { amount_msat: 896, ..usage };
2984                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), u64::max_value());
2985
2986                 // One decay (i.e., half life)
2987                 SinceEpoch::advance(Duration::from_secs(5));
2988                 scorer.decay_liquidity_certainty(Duration::from_secs(10));
2989                 let usage = ChannelUsage { amount_msat: 64, ..usage };
2990                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 0);
2991                 let usage = ChannelUsage { amount_msat: 128, ..usage };
2992                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 34);
2993                 let usage = ChannelUsage { amount_msat: 896, ..usage };
2994                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 1_970);
2995                 let usage = ChannelUsage { amount_msat: 960, ..usage };
2996                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), u64::max_value());
2997
2998                 // Fully decay liquidity lower bound.
2999                 SinceEpoch::advance(Duration::from_secs(10 * 7));
3000                 scorer.decay_liquidity_certainty(Duration::from_secs(10 * 8));
3001                 let usage = ChannelUsage { amount_msat: 0, ..usage };
3002                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 0);
3003                 let usage = ChannelUsage { amount_msat: 1, ..usage };
3004                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 0);
3005                 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
3006                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 2_000);
3007                 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
3008                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), u64::max_value());
3009
3010                 // Fully decay liquidity upper bound.
3011                 SinceEpoch::advance(Duration::from_secs(10));
3012                 scorer.decay_liquidity_certainty(Duration::from_secs(10 * 9));
3013                 let usage = ChannelUsage { amount_msat: 0, ..usage };
3014                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 0);
3015                 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
3016                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), u64::max_value());
3017
3018                 SinceEpoch::advance(Duration::from_secs(10));
3019                 scorer.decay_liquidity_certainty(Duration::from_secs(10 * 10));
3020                 let usage = ChannelUsage { amount_msat: 0, ..usage };
3021                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 0);
3022                 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
3023                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), u64::max_value());
3024         }
3025
3026         #[test]
3027         fn decays_liquidity_bounds_without_shift_overflow() {
3028                 let logger = TestLogger::new();
3029                 let network_graph = network_graph(&logger);
3030                 let params = ProbabilisticScoringFeeParameters {
3031                         liquidity_penalty_multiplier_msat: 1_000,
3032                         ..ProbabilisticScoringFeeParameters::zero_penalty()
3033                 };
3034                 let decay_params = ProbabilisticScoringDecayParameters {
3035                         liquidity_offset_half_life: Duration::from_secs(10),
3036                         ..ProbabilisticScoringDecayParameters::default()
3037                 };
3038                 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3039                 let source = source_node_id();
3040                 let usage = ChannelUsage {
3041                         amount_msat: 256,
3042                         inflight_htlc_msat: 0,
3043                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
3044                 };
3045                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
3046                 let (info, _) = channel.as_directed_from(&source).unwrap();
3047                 let candidate = CandidateRouteHop::PublicHop {
3048                         info,
3049                         short_channel_id: 42,
3050                 };
3051                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 125);
3052
3053                 scorer.payment_path_failed(&payment_path_for_amount(512), 42, Duration::ZERO);
3054                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 281);
3055
3056                 // An unchecked right shift 64 bits or more in DirectedChannelLiquidity::decayed_offset_msat
3057                 // would cause an overflow.
3058                 SinceEpoch::advance(Duration::from_secs(10 * 64));
3059                 scorer.decay_liquidity_certainty(Duration::from_secs(10 * 64));
3060                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 125);
3061
3062                 SinceEpoch::advance(Duration::from_secs(10));
3063                 scorer.decay_liquidity_certainty(Duration::from_secs(10 * 65));
3064                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 125);
3065         }
3066
3067         #[test]
3068         fn restricts_liquidity_bounds_after_decay() {
3069                 let logger = TestLogger::new();
3070                 let network_graph = network_graph(&logger);
3071                 let params = ProbabilisticScoringFeeParameters {
3072                         liquidity_penalty_multiplier_msat: 1_000,
3073                         ..ProbabilisticScoringFeeParameters::zero_penalty()
3074                 };
3075                 let decay_params = ProbabilisticScoringDecayParameters {
3076                         liquidity_offset_half_life: Duration::from_secs(10),
3077                         ..ProbabilisticScoringDecayParameters::default()
3078                 };
3079                 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3080                 let source = source_node_id();
3081                 let usage = ChannelUsage {
3082                         amount_msat: 512,
3083                         inflight_htlc_msat: 0,
3084                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
3085                 };
3086                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
3087                 let (info, _) = channel.as_directed_from(&source).unwrap();
3088                 let candidate = CandidateRouteHop::PublicHop {
3089                         info,
3090                         short_channel_id: 42,
3091                 };
3092
3093                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 300);
3094
3095                 // More knowledge gives higher confidence (256, 768), meaning a lower penalty.
3096                 scorer.payment_path_failed(&payment_path_for_amount(768), 42, Duration::ZERO);
3097                 scorer.payment_path_failed(&payment_path_for_amount(256), 43, Duration::ZERO);
3098                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 281);
3099
3100                 // Decaying knowledge gives less confidence (128, 896), meaning a higher penalty.
3101                 SinceEpoch::advance(Duration::from_secs(10));
3102                 scorer.decay_liquidity_certainty(Duration::from_secs(10));
3103                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 291);
3104
3105                 // Reducing the upper bound gives more confidence (128, 832) that the payment amount (512)
3106                 // is closer to the upper bound, meaning a higher penalty.
3107                 scorer.payment_path_successful(&payment_path_for_amount(64), Duration::from_secs(10));
3108                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 331);
3109
3110                 // Increasing the lower bound gives more confidence (256, 832) that the payment amount (512)
3111                 // is closer to the lower bound, meaning a lower penalty.
3112                 scorer.payment_path_failed(&payment_path_for_amount(256), 43, Duration::from_secs(10));
3113                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 245);
3114
3115                 // Further decaying affects the lower bound more than the upper bound (128, 928).
3116                 SinceEpoch::advance(Duration::from_secs(10));
3117                 scorer.decay_liquidity_certainty(Duration::from_secs(20));
3118                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 280);
3119         }
3120
3121         #[test]
3122         fn restores_persisted_liquidity_bounds() {
3123                 let logger = TestLogger::new();
3124                 let network_graph = network_graph(&logger);
3125                 let params = ProbabilisticScoringFeeParameters {
3126                         liquidity_penalty_multiplier_msat: 1_000,
3127                         considered_impossible_penalty_msat: u64::max_value(),
3128                         ..ProbabilisticScoringFeeParameters::zero_penalty()
3129                 };
3130                 let decay_params = ProbabilisticScoringDecayParameters {
3131                         liquidity_offset_half_life: Duration::from_secs(10),
3132                         ..ProbabilisticScoringDecayParameters::default()
3133                 };
3134                 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3135                 let source = source_node_id();
3136                 let usage = ChannelUsage {
3137                         amount_msat: 500,
3138                         inflight_htlc_msat: 0,
3139                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
3140                 };
3141
3142                 scorer.payment_path_failed(&payment_path_for_amount(500), 42, Duration::ZERO);
3143                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
3144                 let (info, _) = channel.as_directed_from(&source).unwrap();
3145                 let candidate = CandidateRouteHop::PublicHop {
3146                         info,
3147                         short_channel_id: 42,
3148                 };
3149                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), u64::max_value());
3150
3151                 SinceEpoch::advance(Duration::from_secs(10));
3152                 scorer.decay_liquidity_certainty(Duration::from_secs(10));
3153                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 473);
3154
3155                 scorer.payment_path_failed(&payment_path_for_amount(250), 43, Duration::from_secs(10));
3156                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 300);
3157
3158                 let mut serialized_scorer = Vec::new();
3159                 scorer.write(&mut serialized_scorer).unwrap();
3160
3161                 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
3162                 let deserialized_scorer =
3163                         <ProbabilisticScorer>::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap();
3164                 assert_eq!(deserialized_scorer.channel_penalty_msat(&candidate, usage, &params), 300);
3165         }
3166
3167         fn do_decays_persisted_liquidity_bounds(decay_before_reload: bool) {
3168                 let logger = TestLogger::new();
3169                 let network_graph = network_graph(&logger);
3170                 let params = ProbabilisticScoringFeeParameters {
3171                         liquidity_penalty_multiplier_msat: 1_000,
3172                         considered_impossible_penalty_msat: u64::max_value(),
3173                         ..ProbabilisticScoringFeeParameters::zero_penalty()
3174                 };
3175                 let decay_params = ProbabilisticScoringDecayParameters {
3176                         liquidity_offset_half_life: Duration::from_secs(10),
3177                         ..ProbabilisticScoringDecayParameters::zero_penalty()
3178                 };
3179                 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3180                 let source = source_node_id();
3181                 let usage = ChannelUsage {
3182                         amount_msat: 500,
3183                         inflight_htlc_msat: 0,
3184                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
3185                 };
3186
3187                 scorer.payment_path_failed(&payment_path_for_amount(500), 42, Duration::ZERO);
3188                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
3189                 let (info, _) = channel.as_directed_from(&source).unwrap();
3190                 let candidate = CandidateRouteHop::PublicHop {
3191                         info,
3192                         short_channel_id: 42,
3193                 };
3194                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), u64::max_value());
3195
3196                 if decay_before_reload {
3197                         SinceEpoch::advance(Duration::from_secs(10));
3198                         scorer.decay_liquidity_certainty(Duration::from_secs(10));
3199                 }
3200
3201                 let mut serialized_scorer = Vec::new();
3202                 scorer.write(&mut serialized_scorer).unwrap();
3203
3204                 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
3205                 let mut deserialized_scorer =
3206                         <ProbabilisticScorer>::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap();
3207                 if !decay_before_reload {
3208                         SinceEpoch::advance(Duration::from_secs(10));
3209                         scorer.decay_liquidity_certainty(Duration::from_secs(10));
3210                         deserialized_scorer.decay_liquidity_certainty(Duration::from_secs(10));
3211                 }
3212                 assert_eq!(deserialized_scorer.channel_penalty_msat(&candidate, usage, &params), 473);
3213
3214                 scorer.payment_path_failed(&payment_path_for_amount(250), 43, Duration::from_secs(10));
3215                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 300);
3216
3217                 SinceEpoch::advance(Duration::from_secs(10));
3218                 deserialized_scorer.decay_liquidity_certainty(Duration::from_secs(20));
3219                 assert_eq!(deserialized_scorer.channel_penalty_msat(&candidate, usage, &params), 370);
3220         }
3221
3222         #[test]
3223         fn decays_persisted_liquidity_bounds() {
3224                 do_decays_persisted_liquidity_bounds(false);
3225                 do_decays_persisted_liquidity_bounds(true);
3226         }
3227
3228         #[test]
3229         fn scores_realistic_payments() {
3230                 // Shows the scores of "realistic" sends of 100k sats over channels of 1-10m sats (with a
3231                 // 50k sat reserve).
3232                 let logger = TestLogger::new();
3233                 let network_graph = network_graph(&logger);
3234                 let params = ProbabilisticScoringFeeParameters::default();
3235                 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3236                 let source = source_node_id();
3237
3238                 let usage = ChannelUsage {
3239                         amount_msat: 100_000_000,
3240                         inflight_htlc_msat: 0,
3241                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 950_000_000, htlc_maximum_msat: 1_000 },
3242                 };
3243                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
3244                 let (info, _) = channel.as_directed_from(&source).unwrap();
3245                 let candidate = CandidateRouteHop::PublicHop {
3246                         info,
3247                         short_channel_id: 42,
3248                 };
3249                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 11497);
3250                 let usage = ChannelUsage {
3251                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3252                 };
3253                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 7408);
3254                 let usage = ChannelUsage {
3255                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 2_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3256                 };
3257                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 6151);
3258                 let usage = ChannelUsage {
3259                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 3_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3260                 };
3261                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 5427);
3262                 let usage = ChannelUsage {
3263                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 4_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3264                 };
3265                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 4955);
3266                 let usage = ChannelUsage {
3267                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 5_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3268                 };
3269                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 4736);
3270                 let usage = ChannelUsage {
3271                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 6_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3272                 };
3273                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 4484);
3274                 let usage = ChannelUsage {
3275                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_450_000_000, htlc_maximum_msat: 1_000 }, ..usage
3276                 };
3277                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 4484);
3278                 let usage = ChannelUsage {
3279                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3280                 };
3281                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 4263);
3282                 let usage = ChannelUsage {
3283                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 8_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3284                 };
3285                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 4263);
3286                 let usage = ChannelUsage {
3287                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 9_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3288                 };
3289                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 4044);
3290         }
3291
3292         #[test]
3293         fn adds_base_penalty_to_liquidity_penalty() {
3294                 let logger = TestLogger::new();
3295                 let network_graph = network_graph(&logger);
3296                 let source = source_node_id();
3297                 let usage = ChannelUsage {
3298                         amount_msat: 128,
3299                         inflight_htlc_msat: 0,
3300                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
3301                 };
3302
3303                 let params = ProbabilisticScoringFeeParameters {
3304                         liquidity_penalty_multiplier_msat: 1_000,
3305                         ..ProbabilisticScoringFeeParameters::zero_penalty()
3306                 };
3307                 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3308                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
3309                 let (info, _) = channel.as_directed_from(&source).unwrap();
3310                 let candidate = CandidateRouteHop::PublicHop {
3311                         info,
3312                         short_channel_id: 42,
3313                 };
3314                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 58);
3315
3316                 let params = ProbabilisticScoringFeeParameters {
3317                         base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000,
3318                         anti_probing_penalty_msat: 0, ..ProbabilisticScoringFeeParameters::zero_penalty()
3319                 };
3320                 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3321                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 558);
3322
3323                 let params = ProbabilisticScoringFeeParameters {
3324                         base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000,
3325                         base_penalty_amount_multiplier_msat: (1 << 30),
3326                         anti_probing_penalty_msat: 0, ..ProbabilisticScoringFeeParameters::zero_penalty()
3327                 };
3328
3329                 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3330                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 558 + 128);
3331         }
3332
3333         #[test]
3334         fn adds_amount_penalty_to_liquidity_penalty() {
3335                 let logger = TestLogger::new();
3336                 let network_graph = network_graph(&logger);
3337                 let source = source_node_id();
3338                 let usage = ChannelUsage {
3339                         amount_msat: 512_000,
3340                         inflight_htlc_msat: 0,
3341                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
3342                 };
3343
3344                 let params = ProbabilisticScoringFeeParameters {
3345                         liquidity_penalty_multiplier_msat: 1_000,
3346                         liquidity_penalty_amount_multiplier_msat: 0,
3347                         ..ProbabilisticScoringFeeParameters::zero_penalty()
3348                 };
3349                 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3350                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
3351                 let (info, _) = channel.as_directed_from(&source).unwrap();
3352                 let candidate = CandidateRouteHop::PublicHop {
3353                         info,
3354                         short_channel_id: 42,
3355                 };
3356                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 300);
3357
3358                 let params = ProbabilisticScoringFeeParameters {
3359                         liquidity_penalty_multiplier_msat: 1_000,
3360                         liquidity_penalty_amount_multiplier_msat: 256,
3361                         ..ProbabilisticScoringFeeParameters::zero_penalty()
3362                 };
3363                 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3364                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 337);
3365         }
3366
3367         #[test]
3368         fn calculates_log10_without_overflowing_u64_max_value() {
3369                 let logger = TestLogger::new();
3370                 let network_graph = network_graph(&logger);
3371                 let source = source_node_id();
3372                 let usage = ChannelUsage {
3373                         amount_msat: u64::max_value(),
3374                         inflight_htlc_msat: 0,
3375                         effective_capacity: EffectiveCapacity::Infinite,
3376                 };
3377                 let params = ProbabilisticScoringFeeParameters {
3378                         liquidity_penalty_multiplier_msat: 40_000,
3379                         ..ProbabilisticScoringFeeParameters::zero_penalty()
3380                 };
3381                 let decay_params = ProbabilisticScoringDecayParameters::zero_penalty();
3382                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
3383                 let (info, _) = channel.as_directed_from(&source).unwrap();
3384                 let candidate = CandidateRouteHop::PublicHop {
3385                         info,
3386                         short_channel_id: 42,
3387                 };
3388                 let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3389                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 80_000);
3390         }
3391
3392         #[test]
3393         fn accounts_for_inflight_htlc_usage() {
3394                 let logger = TestLogger::new();
3395                 let network_graph = network_graph(&logger);
3396                 let params = ProbabilisticScoringFeeParameters {
3397                         considered_impossible_penalty_msat: u64::max_value(),
3398                         ..ProbabilisticScoringFeeParameters::zero_penalty()
3399                 };
3400                 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3401                 let source = source_node_id();
3402
3403                 let usage = ChannelUsage {
3404                         amount_msat: 750,
3405                         inflight_htlc_msat: 0,
3406                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
3407                 };
3408                 let network_graph = network_graph.read_only();
3409                 let channel = network_graph.channel(42).unwrap();
3410                 let (info, _) = channel.as_directed_from(&source).unwrap();
3411                 let candidate = CandidateRouteHop::PublicHop {
3412                         info,
3413                         short_channel_id: 42,
3414                 };
3415                 assert_ne!(scorer.channel_penalty_msat(&candidate, usage, &params), u64::max_value());
3416
3417                 let usage = ChannelUsage { inflight_htlc_msat: 251, ..usage };
3418                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), u64::max_value());
3419         }
3420
3421         #[test]
3422         fn removes_uncertainity_when_exact_liquidity_known() {
3423                 let logger = TestLogger::new();
3424                 let network_graph = network_graph(&logger);
3425                 let params = ProbabilisticScoringFeeParameters::default();
3426                 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3427                 let source = source_node_id();
3428
3429                 let base_penalty_msat = params.base_penalty_msat;
3430                 let usage = ChannelUsage {
3431                         amount_msat: 750,
3432                         inflight_htlc_msat: 0,
3433                         effective_capacity: EffectiveCapacity::ExactLiquidity { liquidity_msat: 1_000 },
3434                 };
3435                 let network_graph = network_graph.read_only();
3436                 let channel = network_graph.channel(42).unwrap();
3437                 let (info, _) = channel.as_directed_from(&source).unwrap();
3438                 let candidate = CandidateRouteHop::PublicHop {
3439                         info,
3440                         short_channel_id: 42,
3441                 };
3442                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), base_penalty_msat);
3443
3444                 let usage = ChannelUsage { amount_msat: 1_000, ..usage };
3445                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), base_penalty_msat);
3446
3447                 let usage = ChannelUsage { amount_msat: 1_001, ..usage };
3448                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), u64::max_value());
3449         }
3450
3451         #[test]
3452         fn remembers_historical_failures() {
3453                 let logger = TestLogger::new();
3454                 let network_graph = network_graph(&logger);
3455                 let params = ProbabilisticScoringFeeParameters {
3456                         historical_liquidity_penalty_multiplier_msat: 1024,
3457                         historical_liquidity_penalty_amount_multiplier_msat: 1024,
3458                         ..ProbabilisticScoringFeeParameters::zero_penalty()
3459                 };
3460                 let decay_params = ProbabilisticScoringDecayParameters {
3461                         liquidity_offset_half_life: Duration::from_secs(60 * 60),
3462                         historical_no_updates_half_life: Duration::from_secs(10),
3463                 };
3464                 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3465                 let source = source_node_id();
3466                 let target = target_node_id();
3467
3468                 let usage = ChannelUsage {
3469                         amount_msat: 100,
3470                         inflight_htlc_msat: 0,
3471                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
3472                 };
3473                 let usage_1 = ChannelUsage {
3474                         amount_msat: 1,
3475                         inflight_htlc_msat: 0,
3476                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
3477                 };
3478
3479                 {
3480                         let network_graph = network_graph.read_only();
3481                         let channel = network_graph.channel(42).unwrap();
3482                         let (info, _) = channel.as_directed_from(&source).unwrap();
3483                         let candidate = CandidateRouteHop::PublicHop {
3484                                 info,
3485                                 short_channel_id: 42,
3486                         };
3487
3488                         // With no historical data the normal liquidity penalty calculation is used.
3489                         assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 168);
3490                 }
3491                 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3492                 None);
3493                 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 42, &params),
3494                 None);
3495
3496                 scorer.payment_path_failed(&payment_path_for_amount(1), 42, Duration::ZERO);
3497                 {
3498                         let network_graph = network_graph.read_only();
3499                         let channel = network_graph.channel(42).unwrap();
3500                         let (info, _) = channel.as_directed_from(&source).unwrap();
3501                         let candidate = CandidateRouteHop::PublicHop {
3502                                 info,
3503                                 short_channel_id: 42,
3504                         };
3505
3506                         assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 2048);
3507                         assert_eq!(scorer.channel_penalty_msat(&candidate, usage_1, &params), 249);
3508                 }
3509                 // The "it failed" increment is 32, where the probability should lie several buckets into
3510                 // the first octile.
3511                 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3512                         Some(([32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
3513                                 [0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])));
3514                 assert!(scorer.historical_estimated_payment_success_probability(42, &target, 1, &params)
3515                         .unwrap() > 0.35);
3516                 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 500, &params),
3517                         Some(0.0));
3518
3519                 // Even after we tell the scorer we definitely have enough available liquidity, it will
3520                 // still remember that there was some failure in the past, and assign a non-0 penalty.
3521                 scorer.payment_path_failed(&payment_path_for_amount(1000), 43, Duration::ZERO);
3522                 {
3523                         let network_graph = network_graph.read_only();
3524                         let channel = network_graph.channel(42).unwrap();
3525                         let (info, _) = channel.as_directed_from(&source).unwrap();
3526                         let candidate = CandidateRouteHop::PublicHop {
3527                                 info,
3528                                 short_channel_id: 42,
3529                         };
3530
3531                         assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 105);
3532                 }
3533                 // The first points should be decayed just slightly and the last bucket has a new point.
3534                 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3535                         Some(([31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0],
3536                                 [0, 0, 0, 0, 0, 0, 31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32])));
3537
3538                 // The exact success probability is a bit complicated and involves integer rounding, so we
3539                 // simply check bounds here.
3540                 let five_hundred_prob =
3541                         scorer.historical_estimated_payment_success_probability(42, &target, 500, &params).unwrap();
3542                 assert!(five_hundred_prob > 0.59);
3543                 assert!(five_hundred_prob < 0.60);
3544                 let one_prob =
3545                         scorer.historical_estimated_payment_success_probability(42, &target, 1, &params).unwrap();
3546                 assert!(one_prob < 0.85);
3547                 assert!(one_prob > 0.84);
3548
3549                 // Advance the time forward 16 half-lives (which the docs claim will ensure all data is
3550                 // gone), and check that we're back to where we started.
3551                 SinceEpoch::advance(Duration::from_secs(10 * 16));
3552                 scorer.decay_liquidity_certainty(Duration::from_secs(10 * 16));
3553                 {
3554                         let network_graph = network_graph.read_only();
3555                         let channel = network_graph.channel(42).unwrap();
3556                         let (info, _) = channel.as_directed_from(&source).unwrap();
3557                         let candidate = CandidateRouteHop::PublicHop {
3558                                 info,
3559                                 short_channel_id: 42,
3560                         };
3561
3562                         assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 168);
3563                 }
3564                 // Once fully decayed we still have data, but its all-0s. In the future we may remove the
3565                 // data entirely instead.
3566                 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3567                         Some(([0; 32], [0; 32])));
3568                 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 1, &params), None);
3569
3570                 let mut usage = ChannelUsage {
3571                         amount_msat: 100,
3572                         inflight_htlc_msat: 1024,
3573                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
3574                 };
3575                 scorer.payment_path_failed(&payment_path_for_amount(1), 42, Duration::from_secs(10 * 16));
3576                 {
3577                         let network_graph = network_graph.read_only();
3578                         let channel = network_graph.channel(42).unwrap();
3579                         let (info, _) = channel.as_directed_from(&source).unwrap();
3580                         let candidate = CandidateRouteHop::PublicHop {
3581                                 info,
3582                                 short_channel_id: 42,
3583                         };
3584
3585                         assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 2050);
3586
3587                         let usage = ChannelUsage {
3588                                 amount_msat: 1,
3589                                 inflight_htlc_msat: 0,
3590                                 effective_capacity: EffectiveCapacity::AdvertisedMaxHTLC { amount_msat: 0 },
3591                         };
3592                         assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 2048);
3593                 }
3594
3595                 // Advance to decay all liquidity offsets to zero.
3596                 SinceEpoch::advance(Duration::from_secs(60 * 60 * 10));
3597                 scorer.decay_liquidity_certainty(Duration::from_secs(10 * (16 + 60 * 60)));
3598
3599                 // Once even the bounds have decayed information about the channel should be removed
3600                 // entirely.
3601                 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3602                         None);
3603
3604                 // Use a path in the opposite direction, which have zero for htlc_maximum_msat. This will
3605                 // ensure that the effective capacity is zero to test division-by-zero edge cases.
3606                 let path = vec![
3607                         path_hop(target_pubkey(), 43, 2),
3608                         path_hop(source_pubkey(), 42, 1),
3609                         path_hop(sender_pubkey(), 41, 0),
3610                 ];
3611                 scorer.payment_path_failed(&Path { hops: path, blinded_tail: None }, 42, Duration::from_secs(10 * (16 + 60 * 60)));
3612         }
3613
3614         #[test]
3615         fn adds_anti_probing_penalty() {
3616                 let logger = TestLogger::new();
3617                 let network_graph = network_graph(&logger);
3618                 let source = source_node_id();
3619                 let params = ProbabilisticScoringFeeParameters {
3620                         anti_probing_penalty_msat: 500,
3621                         ..ProbabilisticScoringFeeParameters::zero_penalty()
3622                 };
3623                 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3624
3625                 // Check we receive no penalty for a low htlc_maximum_msat.
3626                 let usage = ChannelUsage {
3627                         amount_msat: 512_000,
3628                         inflight_htlc_msat: 0,
3629                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
3630                 };
3631                 let network_graph = network_graph.read_only();
3632                 let channel = network_graph.channel(42).unwrap();
3633                 let (info, _) = channel.as_directed_from(&source).unwrap();
3634                 let candidate = CandidateRouteHop::PublicHop {
3635                         info,
3636                         short_channel_id: 42,
3637                 };
3638                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 0);
3639
3640                 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity.
3641                 let usage = ChannelUsage {
3642                         amount_msat: 512_000,
3643                         inflight_htlc_msat: 0,
3644                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_024_000 },
3645                 };
3646                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 500);
3647
3648                 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity/2.
3649                 let usage = ChannelUsage {
3650                         amount_msat: 512_000,
3651                         inflight_htlc_msat: 0,
3652                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 512_000 },
3653                 };
3654                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 500);
3655
3656                 // Check we receive no anti-probing penalty for htlc_maximum_msat == channel_capacity/2 - 1.
3657                 let usage = ChannelUsage {
3658                         amount_msat: 512_000,
3659                         inflight_htlc_msat: 0,
3660                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 511_999 },
3661                 };
3662                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 0);
3663         }
3664
3665         #[test]
3666         fn scores_with_blinded_path() {
3667                 // Make sure we'll account for a blinded path's final_value_msat in scoring
3668                 let logger = TestLogger::new();
3669                 let network_graph = network_graph(&logger);
3670                 let params = ProbabilisticScoringFeeParameters {
3671                         liquidity_penalty_multiplier_msat: 1_000,
3672                         ..ProbabilisticScoringFeeParameters::zero_penalty()
3673                 };
3674                 let decay_params = ProbabilisticScoringDecayParameters::default();
3675                 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3676                 let source = source_node_id();
3677                 let usage = ChannelUsage {
3678                         amount_msat: 512,
3679                         inflight_htlc_msat: 0,
3680                         effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
3681                 };
3682                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
3683                 let (info, target) = channel.as_directed_from(&source).unwrap();
3684                 let candidate = CandidateRouteHop::PublicHop {
3685                         info,
3686                         short_channel_id: 42,
3687                 };
3688                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 300);
3689
3690                 let mut path = payment_path_for_amount(768);
3691                 let recipient_hop = path.hops.pop().unwrap();
3692                 let blinded_path = BlindedPath {
3693                         introduction_node_id: path.hops.last().as_ref().unwrap().pubkey,
3694                         blinding_point: test_utils::pubkey(42),
3695                         blinded_hops: vec![
3696                                 BlindedHop { blinded_node_id: test_utils::pubkey(44), encrypted_payload: Vec::new() }
3697                         ],
3698                 };
3699                 path.blinded_tail = Some(BlindedTail {
3700                         hops: blinded_path.blinded_hops,
3701                         blinding_point: blinded_path.blinding_point,
3702                         excess_final_cltv_expiry_delta: recipient_hop.cltv_expiry_delta,
3703                         final_value_msat: recipient_hop.fee_msat,
3704                 });
3705
3706                 // Check the liquidity before and after scoring payment failures to ensure the blinded path's
3707                 // final value is taken into account.
3708                 assert!(scorer.channel_liquidities.get(&42).is_none());
3709
3710                 scorer.payment_path_failed(&path, 42, Duration::ZERO);
3711                 path.blinded_tail.as_mut().unwrap().final_value_msat = 256;
3712                 scorer.payment_path_failed(&path, 43, Duration::ZERO);
3713
3714                 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
3715                         .as_directed(&source, &target, 1_000, decay_params);
3716                 assert_eq!(liquidity.min_liquidity_msat(), 256);
3717                 assert_eq!(liquidity.max_liquidity_msat(), 768);
3718         }
3719
3720         #[test]
3721         fn realistic_historical_failures() {
3722                 // The motivation for the unequal sized buckets came largely from attempting to pay 10k
3723                 // sats over a one bitcoin channel. This tests that case explicitly, ensuring that we score
3724                 // properly.
3725                 let logger = TestLogger::new();
3726                 let mut network_graph = network_graph(&logger);
3727                 let params = ProbabilisticScoringFeeParameters {
3728                         historical_liquidity_penalty_multiplier_msat: 1024,
3729                         historical_liquidity_penalty_amount_multiplier_msat: 1024,
3730                         ..ProbabilisticScoringFeeParameters::zero_penalty()
3731                 };
3732                 let decay_params = ProbabilisticScoringDecayParameters {
3733                         liquidity_offset_half_life: Duration::from_secs(60 * 60),
3734                         historical_no_updates_half_life: Duration::from_secs(10),
3735                         ..ProbabilisticScoringDecayParameters::default()
3736                 };
3737
3738                 let capacity_msat = 100_000_000_000;
3739                 update_channel(&mut network_graph, 42, source_privkey(), 0, capacity_msat, 200);
3740                 update_channel(&mut network_graph, 42, target_privkey(), 1, capacity_msat, 200);
3741
3742                 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3743                 let source = source_node_id();
3744
3745                 let mut amount_msat = 10_000_000;
3746                 let usage = ChannelUsage {
3747                         amount_msat,
3748                         inflight_htlc_msat: 0,
3749                         effective_capacity: EffectiveCapacity::Total { capacity_msat, htlc_maximum_msat: capacity_msat },
3750                 };
3751                 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
3752                 let (info, target) = channel.as_directed_from(&source).unwrap();
3753                 let candidate = CandidateRouteHop::PublicHop {
3754                         info,
3755                         short_channel_id: 42,
3756                 };
3757                 // With no historical data the normal liquidity penalty calculation is used, which results
3758                 // in a success probability of ~75%.
3759                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params), 1269);
3760                 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3761                         None);
3762                 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 42, &params),
3763                         None);
3764
3765                 // Fail to pay once, and then check the buckets and penalty.
3766                 scorer.payment_path_failed(&payment_path_for_amount(amount_msat), 42, Duration::ZERO);
3767                 // The penalty should be the maximum penalty, as the payment we're scoring is now in the
3768                 // same bucket which is the only maximum datapoint.
3769                 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, &params),
3770                         2048 + 2048 * amount_msat / super::AMOUNT_PENALTY_DIVISOR);
3771                 // The "it failed" increment is 32, which we should apply to the first upper-bound (between
3772                 // 6k sats and 12k sats).
3773                 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3774                         Some(([32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
3775                                 [0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])));
3776                 // The success probability estimate itself should be zero.
3777                 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, amount_msat, &params),
3778                         Some(0.0));
3779
3780                 // Now test again with the amount in the bottom bucket.
3781                 amount_msat /= 2;
3782                 // The new amount is entirely within the only minimum bucket with score, so the probability
3783                 // we assign is 1/2.
3784                 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, amount_msat, &params),
3785                         Some(0.5));
3786
3787                 // ...but once we see a failure, we consider the payment to be substantially less likely,
3788                 // even though not a probability of zero as we still look at the second max bucket which
3789                 // now shows 31.
3790                 scorer.payment_path_failed(&payment_path_for_amount(amount_msat), 42, Duration::ZERO);
3791                 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3792                         Some(([63, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
3793                                 [32, 31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])));
3794                 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, amount_msat, &params),
3795                         Some(0.0));
3796         }
3797 }