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