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