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