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