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