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 liquidity_history: HistoricalMinMaxBuckets<BRT>,
677 inflight_htlc_msat: u64,
681 decay_params: ProbabilisticScoringDecayParameters,
684 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
685 /// Creates a new scorer using the given scoring parameters for sending payments from a node
686 /// through a network graph.
687 pub fn new(decay_params: ProbabilisticScoringDecayParameters, network_graph: G, logger: L) -> Self {
692 channel_liquidities: HashMap::new(),
697 fn with_channel(mut self, short_channel_id: u64, liquidity: ChannelLiquidity<T>) -> Self {
698 assert!(self.channel_liquidities.insert(short_channel_id, liquidity).is_none());
702 /// Dump the contents of this scorer into the configured logger.
704 /// Note that this writes roughly one line per channel for which we have a liquidity estimate,
705 /// which may be a substantial amount of log output.
706 pub fn debug_log_liquidity_stats(&self) {
709 let graph = self.network_graph.read_only();
710 for (scid, liq) in self.channel_liquidities.iter() {
711 if let Some(chan_debug) = graph.channels().get(scid) {
712 let log_direction = |source, target| {
713 if let Some((directed_info, _)) = chan_debug.as_directed_to(target) {
714 let amt = directed_info.effective_capacity().as_msat();
715 let dir_liq = liq.as_directed(source, target, 0, amt, self.decay_params);
717 let (min_buckets, max_buckets, _) = dir_liq.liquidity_history
718 .get_decayed_buckets(now, *dir_liq.last_updated,
719 self.decay_params.historical_no_updates_half_life);
721 log_debug!(self.logger, core::concat!(
722 "Liquidity from {} to {} via {} is in the range ({}, {}).\n",
723 "\tHistorical min liquidity octile relative probabilities: {} {} {} {} {} {} {} {}\n",
724 "\tHistorical max liquidity octile relative probabilities: {} {} {} {} {} {} {} {}"),
725 source, target, scid, dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat(),
726 min_buckets[0], min_buckets[1], min_buckets[2], min_buckets[3],
727 min_buckets[4], min_buckets[5], min_buckets[6], min_buckets[7],
728 // Note that the liquidity buckets are an offset from the edge, so we
729 // inverse the max order to get the probabilities from zero.
730 max_buckets[7], max_buckets[6], max_buckets[5], max_buckets[4],
731 max_buckets[3], max_buckets[2], max_buckets[1], max_buckets[0]);
733 log_debug!(self.logger, "No amount known for SCID {} from {:?} to {:?}", scid, source, target);
737 log_direction(&chan_debug.node_one, &chan_debug.node_two);
738 log_direction(&chan_debug.node_two, &chan_debug.node_one);
740 log_debug!(self.logger, "No network graph entry for SCID {}", scid);
745 /// Query the estimated minimum and maximum liquidity available for sending a payment over the
746 /// channel with `scid` towards the given `target` node.
747 pub fn estimated_channel_liquidity_range(&self, scid: u64, target: &NodeId) -> Option<(u64, u64)> {
748 let graph = self.network_graph.read_only();
750 if let Some(chan) = graph.channels().get(&scid) {
751 if let Some(liq) = self.channel_liquidities.get(&scid) {
752 if let Some((directed_info, source)) = chan.as_directed_to(target) {
753 let amt = directed_info.effective_capacity().as_msat();
754 let dir_liq = liq.as_directed(source, target, 0, amt, self.decay_params);
755 return Some((dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat()));
762 /// Query the historical estimated minimum and maximum liquidity available for sending a
763 /// payment over the channel with `scid` towards the given `target` node.
765 /// Returns two sets of 8 buckets. The first set describes the octiles for lower-bound
766 /// liquidity estimates, the second set describes the octiles for upper-bound liquidity
767 /// estimates. Each bucket describes the relative frequency at which we've seen a liquidity
768 /// bound in the octile relative to the channel's total capacity, on an arbitrary scale.
769 /// Because the values are slowly decayed, more recent data points are weighted more heavily
770 /// than older datapoints.
772 /// When scoring, the estimated probability that an upper-/lower-bound lies in a given octile
773 /// relative to the channel's total capacity is calculated by dividing that bucket's value with
774 /// the total of all buckets for the given bound.
776 /// For example, a value of `[0, 0, 0, 0, 0, 0, 32]` indicates that we believe the probability
777 /// of a bound being in the top octile to be 100%, and have never (recently) seen it in any
778 /// other octiles. A value of `[31, 0, 0, 0, 0, 0, 0, 32]` indicates we've seen the bound being
779 /// both in the top and bottom octile, and roughly with similar (recent) frequency.
781 /// Because the datapoints are decayed slowly over time, values will eventually return to
782 /// `Some(([0; 8], [0; 8]))`.
784 /// In order to fetch a single success probability from the buckets provided here, as used in
785 /// the scoring model, see [`Self::historical_estimated_payment_success_probability`].
786 pub fn historical_estimated_channel_liquidity_probabilities(&self, scid: u64, target: &NodeId)
787 -> Option<([u16; 8], [u16; 8])> {
788 let graph = self.network_graph.read_only();
790 if let Some(chan) = graph.channels().get(&scid) {
791 if let Some(liq) = self.channel_liquidities.get(&scid) {
792 if let Some((directed_info, source)) = chan.as_directed_to(target) {
793 let amt = directed_info.effective_capacity().as_msat();
794 let dir_liq = liq.as_directed(source, target, 0, amt, self.decay_params);
796 let (min_buckets, mut max_buckets, _) = dir_liq.liquidity_history
797 .get_decayed_buckets(dir_liq.now, *dir_liq.last_updated,
798 self.decay_params.historical_no_updates_half_life);
799 // Note that the liquidity buckets are an offset from the edge, so we inverse
800 // the max order to get the probabilities from zero.
801 max_buckets.reverse();
802 return Some((min_buckets, max_buckets));
809 /// Query the probability of payment success sending the given `amount_msat` over the channel
810 /// with `scid` towards the given `target` node, based on the historical estimated liquidity
813 /// These are the same bounds as returned by
814 /// [`Self::historical_estimated_channel_liquidity_probabilities`] (but not those returned by
815 /// [`Self::estimated_channel_liquidity_range`]).
816 pub fn historical_estimated_payment_success_probability(
817 &self, scid: u64, target: &NodeId, amount_msat: u64)
819 let graph = self.network_graph.read_only();
821 if let Some(chan) = graph.channels().get(&scid) {
822 if let Some(liq) = self.channel_liquidities.get(&scid) {
823 if let Some((directed_info, source)) = chan.as_directed_to(target) {
824 let capacity_msat = directed_info.effective_capacity().as_msat();
825 let dir_liq = liq.as_directed(source, target, 0, capacity_msat, self.decay_params);
827 return dir_liq.liquidity_history.calculate_success_probability_times_billion(
828 dir_liq.now, *dir_liq.last_updated,
829 self.decay_params.historical_no_updates_half_life, amount_msat, capacity_msat
830 ).map(|p| p as f64 / (1024 * 1024 * 1024) as f64);
838 impl<T: Time> ChannelLiquidity<T> {
842 min_liquidity_offset_msat: 0,
843 max_liquidity_offset_msat: 0,
844 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
845 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
846 last_updated: T::now(),
850 /// Returns a view of the channel liquidity directed from `source` to `target` assuming
853 &self, source: &NodeId, target: &NodeId, inflight_htlc_msat: u64, capacity_msat: u64, decay_params: ProbabilisticScoringDecayParameters
854 ) -> DirectedChannelLiquidity<&u64, &HistoricalBucketRangeTracker, T, &T> {
855 let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) =
857 (&self.min_liquidity_offset_msat, &self.max_liquidity_offset_msat,
858 &self.min_liquidity_offset_history, &self.max_liquidity_offset_history)
860 (&self.max_liquidity_offset_msat, &self.min_liquidity_offset_msat,
861 &self.max_liquidity_offset_history, &self.min_liquidity_offset_history)
864 DirectedChannelLiquidity {
865 min_liquidity_offset_msat,
866 max_liquidity_offset_msat,
867 liquidity_history: HistoricalMinMaxBuckets {
868 min_liquidity_offset_history,
869 max_liquidity_offset_history,
873 last_updated: &self.last_updated,
875 decay_params: decay_params,
879 /// Returns a mutable view of the channel liquidity directed from `source` to `target` assuming
882 &mut self, source: &NodeId, target: &NodeId, inflight_htlc_msat: u64, capacity_msat: u64, decay_params: ProbabilisticScoringDecayParameters
883 ) -> DirectedChannelLiquidity<&mut u64, &mut HistoricalBucketRangeTracker, T, &mut T> {
884 let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) =
886 (&mut self.min_liquidity_offset_msat, &mut self.max_liquidity_offset_msat,
887 &mut self.min_liquidity_offset_history, &mut self.max_liquidity_offset_history)
889 (&mut self.max_liquidity_offset_msat, &mut self.min_liquidity_offset_msat,
890 &mut self.max_liquidity_offset_history, &mut self.min_liquidity_offset_history)
893 DirectedChannelLiquidity {
894 min_liquidity_offset_msat,
895 max_liquidity_offset_msat,
896 liquidity_history: HistoricalMinMaxBuckets {
897 min_liquidity_offset_history,
898 max_liquidity_offset_history,
902 last_updated: &mut self.last_updated,
904 decay_params: decay_params,
909 /// Bounds `-log10` to avoid excessive liquidity penalties for payments with low success
911 const NEGATIVE_LOG10_UPPER_BOUND: u64 = 2;
913 /// The rough cutoff at which our precision falls off and we should stop bothering to try to log a
914 /// ratio, as X in 1/X.
915 const PRECISION_LOWER_BOUND_DENOMINATOR: u64 = approx::LOWER_BITS_BOUND;
917 /// The divisor used when computing the amount penalty.
918 const AMOUNT_PENALTY_DIVISOR: u64 = 1 << 20;
919 const BASE_AMOUNT_PENALTY_DIVISOR: u64 = 1 << 30;
921 impl<L: Deref<Target = u64>, BRT: Deref<Target = HistoricalBucketRangeTracker>, T: Time, U: Deref<Target = T>> DirectedChannelLiquidity< L, BRT, T, U> {
922 /// Returns a liquidity penalty for routing the given HTLC `amount_msat` through the channel in
924 fn penalty_msat(&self, amount_msat: u64, score_params: &ProbabilisticScoringFeeParameters) -> u64 {
925 let available_capacity = self.available_capacity();
926 let max_liquidity_msat = self.max_liquidity_msat();
927 let min_liquidity_msat = core::cmp::min(self.min_liquidity_msat(), max_liquidity_msat);
929 let mut res = if amount_msat <= min_liquidity_msat {
931 } else if amount_msat >= max_liquidity_msat {
932 // Equivalent to hitting the else clause below with the amount equal to the effective
933 // capacity and without any certainty on the liquidity upper bound, plus the
934 // impossibility penalty.
935 let negative_log10_times_2048 = NEGATIVE_LOG10_UPPER_BOUND * 2048;
936 Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
937 score_params.liquidity_penalty_multiplier_msat,
938 score_params.liquidity_penalty_amount_multiplier_msat)
939 .saturating_add(score_params.considered_impossible_penalty_msat)
941 let numerator = (max_liquidity_msat - amount_msat).saturating_add(1);
942 let denominator = (max_liquidity_msat - min_liquidity_msat).saturating_add(1);
943 if amount_msat - min_liquidity_msat < denominator / PRECISION_LOWER_BOUND_DENOMINATOR {
944 // If the failure probability is < 1.5625% (as 1 - numerator/denominator < 1/64),
945 // don't bother trying to use the log approximation as it gets too noisy to be
946 // particularly helpful, instead just round down to 0.
949 let negative_log10_times_2048 =
950 approx::negative_log10_times_2048(numerator, denominator);
951 Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
952 score_params.liquidity_penalty_multiplier_msat,
953 score_params.liquidity_penalty_amount_multiplier_msat)
957 if amount_msat >= available_capacity {
958 // We're trying to send more than the capacity, use a max penalty.
959 res = res.saturating_add(Self::combined_penalty_msat(amount_msat,
960 NEGATIVE_LOG10_UPPER_BOUND * 2048,
961 score_params.historical_liquidity_penalty_multiplier_msat,
962 score_params.historical_liquidity_penalty_amount_multiplier_msat));
966 if score_params.historical_liquidity_penalty_multiplier_msat != 0 ||
967 score_params.historical_liquidity_penalty_amount_multiplier_msat != 0 {
968 if let Some(cumulative_success_prob_times_billion) = self.liquidity_history
969 .calculate_success_probability_times_billion(self.now, *self.last_updated,
970 self.decay_params.historical_no_updates_half_life, amount_msat, self.capacity_msat)
972 let historical_negative_log10_times_2048 = approx::negative_log10_times_2048(cumulative_success_prob_times_billion + 1, 1024 * 1024 * 1024);
973 res = res.saturating_add(Self::combined_penalty_msat(amount_msat,
974 historical_negative_log10_times_2048, score_params.historical_liquidity_penalty_multiplier_msat,
975 score_params.historical_liquidity_penalty_amount_multiplier_msat));
977 // If we don't have any valid points (or, once decayed, we have less than a full
978 // point), redo the non-historical calculation with no liquidity bounds tracked and
979 // the historical penalty multipliers.
980 let available_capacity = self.available_capacity();
981 let numerator = available_capacity.saturating_sub(amount_msat).saturating_add(1);
982 let denominator = available_capacity.saturating_add(1);
983 let negative_log10_times_2048 =
984 approx::negative_log10_times_2048(numerator, denominator);
985 res = res.saturating_add(Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
986 score_params.historical_liquidity_penalty_multiplier_msat,
987 score_params.historical_liquidity_penalty_amount_multiplier_msat));
994 /// Computes the liquidity penalty from the penalty multipliers.
996 fn combined_penalty_msat(amount_msat: u64, mut negative_log10_times_2048: u64,
997 liquidity_penalty_multiplier_msat: u64, liquidity_penalty_amount_multiplier_msat: u64,
999 negative_log10_times_2048 =
1000 negative_log10_times_2048.min(NEGATIVE_LOG10_UPPER_BOUND * 2048);
1002 // Upper bound the liquidity penalty to ensure some channel is selected.
1003 let liquidity_penalty_msat = negative_log10_times_2048
1004 .saturating_mul(liquidity_penalty_multiplier_msat) / 2048;
1005 let amount_penalty_msat = negative_log10_times_2048
1006 .saturating_mul(liquidity_penalty_amount_multiplier_msat)
1007 .saturating_mul(amount_msat) / 2048 / AMOUNT_PENALTY_DIVISOR;
1009 liquidity_penalty_msat.saturating_add(amount_penalty_msat)
1012 /// Returns the lower bound of the channel liquidity balance in this direction.
1014 fn min_liquidity_msat(&self) -> u64 {
1015 self.decayed_offset_msat(*self.min_liquidity_offset_msat)
1018 /// Returns the upper bound of the channel liquidity balance in this direction.
1020 fn max_liquidity_msat(&self) -> u64 {
1021 self.available_capacity()
1022 .saturating_sub(self.decayed_offset_msat(*self.max_liquidity_offset_msat))
1025 /// Returns the capacity minus the in-flight HTLCs in this direction.
1027 fn available_capacity(&self) -> u64 {
1028 self.capacity_msat.saturating_sub(self.inflight_htlc_msat)
1031 fn decayed_offset_msat(&self, offset_msat: u64) -> u64 {
1032 self.now.duration_since(*self.last_updated).as_secs()
1033 .checked_div(self.decay_params.liquidity_offset_half_life.as_secs())
1034 .and_then(|decays| offset_msat.checked_shr(decays as u32))
1039 impl<L: DerefMut<Target = u64>, BRT: DerefMut<Target = HistoricalBucketRangeTracker>, T: Time, U: DerefMut<Target = T>> DirectedChannelLiquidity<L, BRT, T, U> {
1040 /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat`.
1041 fn failed_at_channel<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
1042 let existing_max_msat = self.max_liquidity_msat();
1043 if amount_msat < existing_max_msat {
1044 log_debug!(logger, "Setting max liquidity of {} from {} to {}", chan_descr, existing_max_msat, amount_msat);
1045 self.set_max_liquidity_msat(amount_msat);
1047 log_trace!(logger, "Max liquidity of {} is {} (already less than or equal to {})",
1048 chan_descr, existing_max_msat, amount_msat);
1050 self.update_history_buckets();
1053 /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat` downstream.
1054 fn failed_downstream<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
1055 let existing_min_msat = self.min_liquidity_msat();
1056 if amount_msat > existing_min_msat {
1057 log_debug!(logger, "Setting min liquidity of {} from {} to {}", existing_min_msat, chan_descr, amount_msat);
1058 self.set_min_liquidity_msat(amount_msat);
1060 log_trace!(logger, "Min liquidity of {} is {} (already greater than or equal to {})",
1061 chan_descr, existing_min_msat, amount_msat);
1063 self.update_history_buckets();
1066 /// Adjusts the channel liquidity balance bounds when successfully routing `amount_msat`.
1067 fn successful<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
1068 let max_liquidity_msat = self.max_liquidity_msat().checked_sub(amount_msat).unwrap_or(0);
1069 log_debug!(logger, "Subtracting {} from max liquidity of {} (setting it to {})", amount_msat, chan_descr, max_liquidity_msat);
1070 self.set_max_liquidity_msat(max_liquidity_msat);
1071 self.update_history_buckets();
1074 fn update_history_buckets(&mut self) {
1075 let half_lives = self.now.duration_since(*self.last_updated).as_secs()
1076 .checked_div(self.decay_params.historical_no_updates_half_life.as_secs())
1077 .map(|v| v.try_into().unwrap_or(u32::max_value())).unwrap_or(u32::max_value());
1078 self.liquidity_history.min_liquidity_offset_history.time_decay_data(half_lives);
1079 self.liquidity_history.max_liquidity_offset_history.time_decay_data(half_lives);
1081 let min_liquidity_offset_msat = self.decayed_offset_msat(*self.min_liquidity_offset_msat);
1082 self.liquidity_history.min_liquidity_offset_history.track_datapoint(
1083 min_liquidity_offset_msat, self.capacity_msat
1085 let max_liquidity_offset_msat = self.decayed_offset_msat(*self.max_liquidity_offset_msat);
1086 self.liquidity_history.max_liquidity_offset_history.track_datapoint(
1087 max_liquidity_offset_msat, self.capacity_msat
1091 /// Adjusts the lower bound of the channel liquidity balance in this direction.
1092 fn set_min_liquidity_msat(&mut self, amount_msat: u64) {
1093 *self.min_liquidity_offset_msat = amount_msat;
1094 *self.max_liquidity_offset_msat = if amount_msat > self.max_liquidity_msat() {
1097 self.decayed_offset_msat(*self.max_liquidity_offset_msat)
1099 *self.last_updated = self.now;
1102 /// Adjusts the upper bound of the channel liquidity balance in this direction.
1103 fn set_max_liquidity_msat(&mut self, amount_msat: u64) {
1104 *self.max_liquidity_offset_msat = self.capacity_msat.checked_sub(amount_msat).unwrap_or(0);
1105 *self.min_liquidity_offset_msat = if amount_msat < self.min_liquidity_msat() {
1108 self.decayed_offset_msat(*self.min_liquidity_offset_msat)
1110 *self.last_updated = self.now;
1114 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Score for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1115 type ScoreParams = ProbabilisticScoringFeeParameters;
1116 fn channel_penalty_msat(
1117 &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage, score_params: &ProbabilisticScoringFeeParameters
1119 if let Some(penalty) = score_params.manual_node_penalties.get(target) {
1123 let base_penalty_msat = score_params.base_penalty_msat.saturating_add(
1124 score_params.base_penalty_amount_multiplier_msat
1125 .saturating_mul(usage.amount_msat) / BASE_AMOUNT_PENALTY_DIVISOR);
1127 let mut anti_probing_penalty_msat = 0;
1128 match usage.effective_capacity {
1129 EffectiveCapacity::ExactLiquidity { liquidity_msat } => {
1130 if usage.amount_msat > liquidity_msat {
1131 return u64::max_value();
1133 return base_penalty_msat;
1136 EffectiveCapacity::Total { capacity_msat, htlc_maximum_msat } => {
1137 if htlc_maximum_msat >= capacity_msat/2 {
1138 anti_probing_penalty_msat = score_params.anti_probing_penalty_msat;
1144 let amount_msat = usage.amount_msat;
1145 let capacity_msat = usage.effective_capacity.as_msat();
1146 let inflight_htlc_msat = usage.inflight_htlc_msat;
1147 self.channel_liquidities
1148 .get(&short_channel_id)
1149 .unwrap_or(&ChannelLiquidity::new())
1150 .as_directed(source, target, inflight_htlc_msat, capacity_msat, self.decay_params)
1151 .penalty_msat(amount_msat, score_params)
1152 .saturating_add(anti_probing_penalty_msat)
1153 .saturating_add(base_penalty_msat)
1156 fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64) {
1157 let amount_msat = path.final_value_msat();
1158 log_trace!(self.logger, "Scoring path through to SCID {} as having failed at {} msat", short_channel_id, amount_msat);
1159 let network_graph = self.network_graph.read_only();
1160 for (hop_idx, hop) in path.hops.iter().enumerate() {
1161 let target = NodeId::from_pubkey(&hop.pubkey);
1162 let channel_directed_from_source = network_graph.channels()
1163 .get(&hop.short_channel_id)
1164 .and_then(|channel| channel.as_directed_to(&target));
1166 let at_failed_channel = hop.short_channel_id == short_channel_id;
1167 if at_failed_channel && hop_idx == 0 {
1168 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);
1171 // Only score announced channels.
1172 if let Some((channel, source)) = channel_directed_from_source {
1173 let capacity_msat = channel.effective_capacity().as_msat();
1174 if at_failed_channel {
1175 self.channel_liquidities
1176 .entry(hop.short_channel_id)
1177 .or_insert_with(ChannelLiquidity::new)
1178 .as_directed_mut(source, &target, 0, capacity_msat, self.decay_params)
1179 .failed_at_channel(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1181 self.channel_liquidities
1182 .entry(hop.short_channel_id)
1183 .or_insert_with(ChannelLiquidity::new)
1184 .as_directed_mut(source, &target, 0, capacity_msat, self.decay_params)
1185 .failed_downstream(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1188 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).",
1189 hop.short_channel_id);
1191 if at_failed_channel { break; }
1195 fn payment_path_successful(&mut self, path: &Path) {
1196 let amount_msat = path.final_value_msat();
1197 log_trace!(self.logger, "Scoring path through SCID {} as having succeeded at {} msat.",
1198 path.hops.split_last().map(|(hop, _)| hop.short_channel_id).unwrap_or(0), amount_msat);
1199 let network_graph = self.network_graph.read_only();
1200 for hop in &path.hops {
1201 let target = NodeId::from_pubkey(&hop.pubkey);
1202 let channel_directed_from_source = network_graph.channels()
1203 .get(&hop.short_channel_id)
1204 .and_then(|channel| channel.as_directed_to(&target));
1206 // Only score announced channels.
1207 if let Some((channel, source)) = channel_directed_from_source {
1208 let capacity_msat = channel.effective_capacity().as_msat();
1209 self.channel_liquidities
1210 .entry(hop.short_channel_id)
1211 .or_insert_with(ChannelLiquidity::new)
1212 .as_directed_mut(source, &target, 0, capacity_msat, self.decay_params)
1213 .successful(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1215 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).",
1216 hop.short_channel_id);
1221 fn probe_failed(&mut self, path: &Path, short_channel_id: u64) {
1222 self.payment_path_failed(path, short_channel_id)
1225 fn probe_successful(&mut self, path: &Path) {
1226 self.payment_path_failed(path, u64::max_value())
1231 const BITS: u32 = 64;
1232 const HIGHEST_BIT: u32 = BITS - 1;
1233 const LOWER_BITS: u32 = 6;
1234 pub(super) const LOWER_BITS_BOUND: u64 = 1 << LOWER_BITS;
1235 const LOWER_BITMASK: u64 = (1 << LOWER_BITS) - 1;
1237 /// Look-up table for `log10(x) * 2048` where row `i` is used for each `x` having `i` as the
1238 /// most significant bit. The next 4 bits of `x`, if applicable, are used for the second index.
1239 const LOG10_TIMES_2048: [[u16; (LOWER_BITS_BOUND) as usize]; BITS as usize] = [
1240 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1241 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1242 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1243 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
1244 [617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
1245 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
1246 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977,
1247 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977],
1248 [1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233,
1249 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431,
1250 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594,
1251 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731],
1252 [1850, 1850, 1850, 1850, 1850, 1850, 1850, 1850, 1954, 1954, 1954, 1954, 1954, 1954, 1954, 1954,
1253 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2133, 2133, 2133, 2133, 2133, 2133, 2133, 2133,
1254 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2281, 2281, 2281, 2281, 2281, 2281, 2281, 2281,
1255 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2409, 2409, 2409, 2409, 2409, 2409, 2409, 2409],
1256 [2466, 2466, 2466, 2466, 2520, 2520, 2520, 2520, 2571, 2571, 2571, 2571, 2619, 2619, 2619, 2619,
1257 2665, 2665, 2665, 2665, 2708, 2708, 2708, 2708, 2749, 2749, 2749, 2749, 2789, 2789, 2789, 2789,
1258 2827, 2827, 2827, 2827, 2863, 2863, 2863, 2863, 2898, 2898, 2898, 2898, 2931, 2931, 2931, 2931,
1259 2964, 2964, 2964, 2964, 2995, 2995, 2995, 2995, 3025, 3025, 3025, 3025, 3054, 3054, 3054, 3054],
1260 [3083, 3083, 3110, 3110, 3136, 3136, 3162, 3162, 3187, 3187, 3212, 3212, 3235, 3235, 3259, 3259,
1261 3281, 3281, 3303, 3303, 3324, 3324, 3345, 3345, 3366, 3366, 3386, 3386, 3405, 3405, 3424, 3424,
1262 3443, 3443, 3462, 3462, 3479, 3479, 3497, 3497, 3514, 3514, 3531, 3531, 3548, 3548, 3564, 3564,
1263 3580, 3580, 3596, 3596, 3612, 3612, 3627, 3627, 3642, 3642, 3656, 3656, 3671, 3671, 3685, 3685],
1264 [3699, 3713, 3726, 3740, 3753, 3766, 3779, 3791, 3804, 3816, 3828, 3840, 3852, 3864, 3875, 3886,
1265 3898, 3909, 3919, 3930, 3941, 3951, 3962, 3972, 3982, 3992, 4002, 4012, 4022, 4031, 4041, 4050,
1266 4060, 4069, 4078, 4087, 4096, 4105, 4114, 4122, 4131, 4139, 4148, 4156, 4164, 4173, 4181, 4189,
1267 4197, 4205, 4213, 4220, 4228, 4236, 4243, 4251, 4258, 4266, 4273, 4280, 4287, 4294, 4302, 4309],
1268 [4316, 4329, 4343, 4356, 4369, 4382, 4395, 4408, 4420, 4433, 4445, 4457, 4468, 4480, 4492, 4503,
1269 4514, 4525, 4536, 4547, 4557, 4568, 4578, 4589, 4599, 4609, 4619, 4629, 4638, 4648, 4657, 4667,
1270 4676, 4685, 4695, 4704, 4713, 4721, 4730, 4739, 4747, 4756, 4764, 4773, 4781, 4789, 4797, 4805,
1271 4813, 4821, 4829, 4837, 4845, 4852, 4860, 4867, 4875, 4882, 4889, 4897, 4904, 4911, 4918, 4925],
1272 [4932, 4946, 4959, 4973, 4986, 4999, 5012, 5024, 5037, 5049, 5061, 5073, 5085, 5097, 5108, 5119,
1273 5131, 5142, 5153, 5163, 5174, 5184, 5195, 5205, 5215, 5225, 5235, 5245, 5255, 5264, 5274, 5283,
1274 5293, 5302, 5311, 5320, 5329, 5338, 5347, 5355, 5364, 5372, 5381, 5389, 5397, 5406, 5414, 5422,
1275 5430, 5438, 5446, 5453, 5461, 5469, 5476, 5484, 5491, 5499, 5506, 5513, 5520, 5527, 5535, 5542],
1276 [5549, 5562, 5576, 5589, 5603, 5615, 5628, 5641, 5653, 5666, 5678, 5690, 5701, 5713, 5725, 5736,
1277 5747, 5758, 5769, 5780, 5790, 5801, 5811, 5822, 5832, 5842, 5852, 5862, 5871, 5881, 5890, 5900,
1278 5909, 5918, 5928, 5937, 5946, 5954, 5963, 5972, 5980, 5989, 5997, 6006, 6014, 6022, 6030, 6038,
1279 6046, 6054, 6062, 6070, 6078, 6085, 6093, 6100, 6108, 6115, 6122, 6130, 6137, 6144, 6151, 6158],
1280 [6165, 6179, 6192, 6206, 6219, 6232, 6245, 6257, 6270, 6282, 6294, 6306, 6318, 6330, 6341, 6352,
1281 6364, 6375, 6386, 6396, 6407, 6417, 6428, 6438, 6448, 6458, 6468, 6478, 6488, 6497, 6507, 6516,
1282 6526, 6535, 6544, 6553, 6562, 6571, 6580, 6588, 6597, 6605, 6614, 6622, 6630, 6639, 6647, 6655,
1283 6663, 6671, 6679, 6686, 6694, 6702, 6709, 6717, 6724, 6732, 6739, 6746, 6753, 6761, 6768, 6775],
1284 [6782, 6795, 6809, 6822, 6836, 6849, 6861, 6874, 6886, 6899, 6911, 6923, 6934, 6946, 6958, 6969,
1285 6980, 6991, 7002, 7013, 7023, 7034, 7044, 7055, 7065, 7075, 7085, 7095, 7104, 7114, 7124, 7133,
1286 7142, 7151, 7161, 7170, 7179, 7187, 7196, 7205, 7213, 7222, 7230, 7239, 7247, 7255, 7263, 7271,
1287 7279, 7287, 7295, 7303, 7311, 7318, 7326, 7333, 7341, 7348, 7355, 7363, 7370, 7377, 7384, 7391],
1288 [7398, 7412, 7425, 7439, 7452, 7465, 7478, 7490, 7503, 7515, 7527, 7539, 7551, 7563, 7574, 7585,
1289 7597, 7608, 7619, 7629, 7640, 7651, 7661, 7671, 7681, 7691, 7701, 7711, 7721, 7731, 7740, 7749,
1290 7759, 7768, 7777, 7786, 7795, 7804, 7813, 7821, 7830, 7838, 7847, 7855, 7864, 7872, 7880, 7888,
1291 7896, 7904, 7912, 7919, 7927, 7935, 7942, 7950, 7957, 7965, 7972, 7979, 7986, 7994, 8001, 8008],
1292 [8015, 8028, 8042, 8055, 8069, 8082, 8094, 8107, 8119, 8132, 8144, 8156, 8167, 8179, 8191, 8202,
1293 8213, 8224, 8235, 8246, 8256, 8267, 8277, 8288, 8298, 8308, 8318, 8328, 8337, 8347, 8357, 8366,
1294 8375, 8384, 8394, 8403, 8412, 8420, 8429, 8438, 8446, 8455, 8463, 8472, 8480, 8488, 8496, 8504,
1295 8512, 8520, 8528, 8536, 8544, 8551, 8559, 8566, 8574, 8581, 8588, 8596, 8603, 8610, 8617, 8624],
1296 [8631, 8645, 8659, 8672, 8685, 8698, 8711, 8723, 8736, 8748, 8760, 8772, 8784, 8796, 8807, 8818,
1297 8830, 8841, 8852, 8862, 8873, 8884, 8894, 8904, 8914, 8924, 8934, 8944, 8954, 8964, 8973, 8982,
1298 8992, 9001, 9010, 9019, 9028, 9037, 9046, 9054, 9063, 9071, 9080, 9088, 9097, 9105, 9113, 9121,
1299 9129, 9137, 9145, 9152, 9160, 9168, 9175, 9183, 9190, 9198, 9205, 9212, 9219, 9227, 9234, 9241],
1300 [9248, 9261, 9275, 9288, 9302, 9315, 9327, 9340, 9352, 9365, 9377, 9389, 9400, 9412, 9424, 9435,
1301 9446, 9457, 9468, 9479, 9490, 9500, 9510, 9521, 9531, 9541, 9551, 9561, 9570, 9580, 9590, 9599,
1302 9608, 9617, 9627, 9636, 9645, 9653, 9662, 9671, 9679, 9688, 9696, 9705, 9713, 9721, 9729, 9737,
1303 9745, 9753, 9761, 9769, 9777, 9784, 9792, 9799, 9807, 9814, 9821, 9829, 9836, 9843, 9850, 9857],
1304 [9864, 9878, 9892, 9905, 9918, 9931, 9944, 9956, 9969, 9981, 9993, 10005, 10017, 10029, 10040, 10051,
1305 10063, 10074, 10085, 10095, 10106, 10117, 10127, 10137, 10147, 10157, 10167, 10177, 10187, 10197, 10206, 10215,
1306 10225, 10234, 10243, 10252, 10261, 10270, 10279, 10287, 10296, 10304, 10313, 10321, 10330, 10338, 10346, 10354,
1307 10362, 10370, 10378, 10385, 10393, 10401, 10408, 10416, 10423, 10431, 10438, 10445, 10452, 10460, 10467, 10474],
1308 [10481, 10494, 10508, 10521, 10535, 10548, 10560, 10573, 10585, 10598, 10610, 10622, 10634, 10645, 10657, 10668,
1309 10679, 10690, 10701, 10712, 10723, 10733, 10743, 10754, 10764, 10774, 10784, 10794, 10803, 10813, 10823, 10832,
1310 10841, 10851, 10860, 10869, 10878, 10886, 10895, 10904, 10912, 10921, 10929, 10938, 10946, 10954, 10962, 10970,
1311 10978, 10986, 10994, 11002, 11010, 11017, 11025, 11032, 11040, 11047, 11054, 11062, 11069, 11076, 11083, 11090],
1312 [11097, 11111, 11125, 11138, 11151, 11164, 11177, 11189, 11202, 11214, 11226, 11238, 11250, 11262, 11273, 11284,
1313 11296, 11307, 11318, 11328, 11339, 11350, 11360, 11370, 11380, 11390, 11400, 11410, 11420, 11430, 11439, 11448,
1314 11458, 11467, 11476, 11485, 11494, 11503, 11512, 11520, 11529, 11538, 11546, 11554, 11563, 11571, 11579, 11587,
1315 11595, 11603, 11611, 11618, 11626, 11634, 11641, 11649, 11656, 11664, 11671, 11678, 11685, 11693, 11700, 11707],
1316 [11714, 11727, 11741, 11754, 11768, 11781, 11793, 11806, 11818, 11831, 11843, 11855, 11867, 11878, 11890, 11901,
1317 11912, 11923, 11934, 11945, 11956, 11966, 11976, 11987, 11997, 12007, 12017, 12027, 12036, 12046, 12056, 12065,
1318 12074, 12084, 12093, 12102, 12111, 12119, 12128, 12137, 12146, 12154, 12162, 12171, 12179, 12187, 12195, 12203,
1319 12211, 12219, 12227, 12235, 12243, 12250, 12258, 12265, 12273, 12280, 12287, 12295, 12302, 12309, 12316, 12323],
1320 [12330, 12344, 12358, 12371, 12384, 12397, 12410, 12423, 12435, 12447, 12459, 12471, 12483, 12495, 12506, 12517,
1321 12529, 12540, 12551, 12561, 12572, 12583, 12593, 12603, 12613, 12623, 12633, 12643, 12653, 12663, 12672, 12682,
1322 12691, 12700, 12709, 12718, 12727, 12736, 12745, 12753, 12762, 12771, 12779, 12787, 12796, 12804, 12812, 12820,
1323 12828, 12836, 12844, 12851, 12859, 12867, 12874, 12882, 12889, 12897, 12904, 12911, 12918, 12926, 12933, 12940],
1324 [12947, 12960, 12974, 12987, 13001, 13014, 13026, 13039, 13051, 13064, 13076, 13088, 13100, 13111, 13123, 13134,
1325 13145, 13156, 13167, 13178, 13189, 13199, 13209, 13220, 13230, 13240, 13250, 13260, 13269, 13279, 13289, 13298,
1326 13307, 13317, 13326, 13335, 13344, 13352, 13361, 13370, 13379, 13387, 13395, 13404, 13412, 13420, 13428, 13436,
1327 13444, 13452, 13460, 13468, 13476, 13483, 13491, 13498, 13506, 13513, 13521, 13528, 13535, 13542, 13549, 13556],
1328 [13563, 13577, 13591, 13604, 13617, 13630, 13643, 13656, 13668, 13680, 13692, 13704, 13716, 13728, 13739, 13750,
1329 13762, 13773, 13784, 13794, 13805, 13816, 13826, 13836, 13846, 13857, 13866, 13876, 13886, 13896, 13905, 13915,
1330 13924, 13933, 13942, 13951, 13960, 13969, 13978, 13986, 13995, 14004, 14012, 14020, 14029, 14037, 14045, 14053,
1331 14061, 14069, 14077, 14084, 14092, 14100, 14107, 14115, 14122, 14130, 14137, 14144, 14151, 14159, 14166, 14173],
1332 [14180, 14194, 14207, 14220, 14234, 14247, 14259, 14272, 14284, 14297, 14309, 14321, 14333, 14344, 14356, 14367,
1333 14378, 14389, 14400, 14411, 14422, 14432, 14443, 14453, 14463, 14473, 14483, 14493, 14502, 14512, 14522, 14531,
1334 14540, 14550, 14559, 14568, 14577, 14586, 14594, 14603, 14612, 14620, 14628, 14637, 14645, 14653, 14661, 14669,
1335 14677, 14685, 14693, 14701, 14709, 14716, 14724, 14731, 14739, 14746, 14754, 14761, 14768, 14775, 14782, 14789],
1336 [14796, 14810, 14824, 14837, 14850, 14863, 14876, 14889, 14901, 14913, 14925, 14937, 14949, 14961, 14972, 14984,
1337 14995, 15006, 15017, 15027, 15038, 15049, 15059, 15069, 15079, 15090, 15099, 15109, 15119, 15129, 15138, 15148,
1338 15157, 15166, 15175, 15184, 15193, 15202, 15211, 15219, 15228, 15237, 15245, 15253, 15262, 15270, 15278, 15286,
1339 15294, 15302, 15310, 15317, 15325, 15333, 15340, 15348, 15355, 15363, 15370, 15377, 15384, 15392, 15399, 15406],
1340 [15413, 15427, 15440, 15453, 15467, 15480, 15492, 15505, 15517, 15530, 15542, 15554, 15566, 15577, 15589, 15600,
1341 15611, 15622, 15633, 15644, 15655, 15665, 15676, 15686, 15696, 15706, 15716, 15726, 15736, 15745, 15755, 15764,
1342 15773, 15783, 15792, 15801, 15810, 15819, 15827, 15836, 15845, 15853, 15862, 15870, 15878, 15886, 15894, 15903,
1343 15910, 15918, 15926, 15934, 15942, 15949, 15957, 15964, 15972, 15979, 15987, 15994, 16001, 16008, 16015, 16022],
1344 [16029, 16043, 16057, 16070, 16083, 16096, 16109, 16122, 16134, 16146, 16158, 16170, 16182, 16194, 16205, 16217,
1345 16228, 16239, 16250, 16260, 16271, 16282, 16292, 16302, 16312, 16323, 16332, 16342, 16352, 16362, 16371, 16381,
1346 16390, 16399, 16408, 16417, 16426, 16435, 16444, 16452, 16461, 16470, 16478, 16486, 16495, 16503, 16511, 16519,
1347 16527, 16535, 16543, 16550, 16558, 16566, 16573, 16581, 16588, 16596, 16603, 16610, 16618, 16625, 16632, 16639],
1348 [16646, 16660, 16673, 16686, 16700, 16713, 16725, 16738, 16751, 16763, 16775, 16787, 16799, 16810, 16822, 16833,
1349 16844, 16855, 16866, 16877, 16888, 16898, 16909, 16919, 16929, 16939, 16949, 16959, 16969, 16978, 16988, 16997,
1350 17006, 17016, 17025, 17034, 17043, 17052, 17060, 17069, 17078, 17086, 17095, 17103, 17111, 17119, 17127, 17136,
1351 17143, 17151, 17159, 17167, 17175, 17182, 17190, 17197, 17205, 17212, 17220, 17227, 17234, 17241, 17248, 17255],
1352 [17262, 17276, 17290, 17303, 17316, 17329, 17342, 17355, 17367, 17379, 17391, 17403, 17415, 17427, 17438, 17450,
1353 17461, 17472, 17483, 17493, 17504, 17515, 17525, 17535, 17546, 17556, 17565, 17575, 17585, 17595, 17604, 17614,
1354 17623, 17632, 17641, 17650, 17659, 17668, 17677, 17685, 17694, 17703, 17711, 17719, 17728, 17736, 17744, 17752,
1355 17760, 17768, 17776, 17784, 17791, 17799, 17806, 17814, 17821, 17829, 17836, 17843, 17851, 17858, 17865, 17872],
1356 [17879, 17893, 17906, 17920, 17933, 17946, 17958, 17971, 17984, 17996, 18008, 18020, 18032, 18043, 18055, 18066,
1357 18077, 18088, 18099, 18110, 18121, 18131, 18142, 18152, 18162, 18172, 18182, 18192, 18202, 18211, 18221, 18230,
1358 18239, 18249, 18258, 18267, 18276, 18285, 18293, 18302, 18311, 18319, 18328, 18336, 18344, 18352, 18360, 18369,
1359 18377, 18384, 18392, 18400, 18408, 18415, 18423, 18430, 18438, 18445, 18453, 18460, 18467, 18474, 18481, 18488],
1360 [18495, 18509, 18523, 18536, 18549, 18562, 18575, 18588, 18600, 18612, 18624, 18636, 18648, 18660, 18671, 18683,
1361 18694, 18705, 18716, 18726, 18737, 18748, 18758, 18768, 18779, 18789, 18799, 18808, 18818, 18828, 18837, 18847,
1362 18856, 18865, 18874, 18883, 18892, 18901, 18910, 18919, 18927, 18936, 18944, 18952, 18961, 18969, 18977, 18985,
1363 18993, 19001, 19009, 19017, 19024, 19032, 19039, 19047, 19054, 19062, 19069, 19076, 19084, 19091, 19098, 19105],
1364 [19112, 19126, 19139, 19153, 19166, 19179, 19191, 19204, 19217, 19229, 19241, 19253, 19265, 19276, 19288, 19299,
1365 19310, 19321, 19332, 19343, 19354, 19364, 19375, 19385, 19395, 19405, 19415, 19425, 19435, 19444, 19454, 19463,
1366 19472, 19482, 19491, 19500, 19509, 19518, 19526, 19535, 19544, 19552, 19561, 19569, 19577, 19585, 19594, 19602,
1367 19610, 19617, 19625, 19633, 19641, 19648, 19656, 19663, 19671, 19678, 19686, 19693, 19700, 19707, 19714, 19721],
1368 [19728, 19742, 19756, 19769, 19782, 19795, 19808, 19821, 19833, 19845, 19857, 19869, 19881, 19893, 19904, 19916,
1369 19927, 19938, 19949, 19960, 19970, 19981, 19991, 20001, 20012, 20022, 20032, 20041, 20051, 20061, 20070, 20080,
1370 20089, 20098, 20107, 20116, 20125, 20134, 20143, 20152, 20160, 20169, 20177, 20185, 20194, 20202, 20210, 20218,
1371 20226, 20234, 20242, 20250, 20257, 20265, 20272, 20280, 20287, 20295, 20302, 20309, 20317, 20324, 20331, 20338],
1372 [20345, 20359, 20372, 20386, 20399, 20412, 20425, 20437, 20450, 20462, 20474, 20486, 20498, 20509, 20521, 20532,
1373 20543, 20554, 20565, 20576, 20587, 20597, 20608, 20618, 20628, 20638, 20648, 20658, 20668, 20677, 20687, 20696,
1374 20705, 20715, 20724, 20733, 20742, 20751, 20759, 20768, 20777, 20785, 20794, 20802, 20810, 20818, 20827, 20835,
1375 20843, 20850, 20858, 20866, 20874, 20881, 20889, 20896, 20904, 20911, 20919, 20926, 20933, 20940, 20947, 20954],
1376 [20961, 20975, 20989, 21002, 21015, 21028, 21041, 21054, 21066, 21078, 21090, 21102, 21114, 21126, 21137, 21149,
1377 21160, 21171, 21182, 21193, 21203, 21214, 21224, 21234, 21245, 21255, 21265, 21274, 21284, 21294, 21303, 21313,
1378 21322, 21331, 21340, 21349, 21358, 21367, 21376, 21385, 21393, 21402, 21410, 21418, 21427, 21435, 21443, 21451,
1379 21459, 21467, 21475, 21483, 21490, 21498, 21505, 21513, 21520, 21528, 21535, 21542, 21550, 21557, 21564, 21571],
1380 [21578, 21592, 21605, 21619, 21632, 21645, 21658, 21670, 21683, 21695, 21707, 21719, 21731, 21742, 21754, 21765,
1381 21776, 21787, 21798, 21809, 21820, 21830, 21841, 21851, 21861, 21871, 21881, 21891, 21901, 21910, 21920, 21929,
1382 21938, 21948, 21957, 21966, 21975, 21984, 21992, 22001, 22010, 22018, 22027, 22035, 22043, 22051, 22060, 22068,
1383 22076, 22083, 22091, 22099, 22107, 22114, 22122, 22129, 22137, 22144, 22152, 22159, 22166, 22173, 22180, 22187],
1384 [22194, 22208, 22222, 22235, 22248, 22261, 22274, 22287, 22299, 22311, 22323, 22335, 22347, 22359, 22370, 22382,
1385 22393, 22404, 22415, 22426, 22436, 22447, 22457, 22467, 22478, 22488, 22498, 22507, 22517, 22527, 22536, 22546,
1386 22555, 22564, 22573, 22582, 22591, 22600, 22609, 22618, 22626, 22635, 22643, 22651, 22660, 22668, 22676, 22684,
1387 22692, 22700, 22708, 22716, 22723, 22731, 22738, 22746, 22753, 22761, 22768, 22775, 22783, 22790, 22797, 22804],
1388 [22811, 22825, 22838, 22852, 22865, 22878, 22891, 22903, 22916, 22928, 22940, 22952, 22964, 22975, 22987, 22998,
1389 23009, 23020, 23031, 23042, 23053, 23063, 23074, 23084, 23094, 23104, 23114, 23124, 23134, 23143, 23153, 23162,
1390 23171, 23181, 23190, 23199, 23208, 23217, 23225, 23234, 23243, 23251, 23260, 23268, 23276, 23284, 23293, 23301,
1391 23309, 23316, 23324, 23332, 23340, 23347, 23355, 23363, 23370, 23377, 23385, 23392, 23399, 23406, 23413, 23420],
1392 [23427, 23441, 23455, 23468, 23481, 23494, 23507, 23520, 23532, 23544, 23556, 23568, 23580, 23592, 23603, 23615,
1393 23626, 23637, 23648, 23659, 23669, 23680, 23690, 23700, 23711, 23721, 23731, 23740, 23750, 23760, 23769, 23779,
1394 23788, 23797, 23806, 23815, 23824, 23833, 23842, 23851, 23859, 23868, 23876, 23884, 23893, 23901, 23909, 23917,
1395 23925, 23933, 23941, 23949, 23956, 23964, 23972, 23979, 23986, 23994, 24001, 24008, 24016, 24023, 24030, 24037],
1396 [24044, 24058, 24071, 24085, 24098, 24111, 24124, 24136, 24149, 24161, 24173, 24185, 24197, 24208, 24220, 24231,
1397 24242, 24253, 24264, 24275, 24286, 24296, 24307, 24317, 24327, 24337, 24347, 24357, 24367, 24376, 24386, 24395,
1398 24405, 24414, 24423, 24432, 24441, 24450, 24458, 24467, 24476, 24484, 24493, 24501, 24509, 24517, 24526, 24534,
1399 24542, 24550, 24557, 24565, 24573, 24580, 24588, 24596, 24603, 24610, 24618, 24625, 24632, 24639, 24646, 24653],
1400 [24660, 24674, 24688, 24701, 24714, 24727, 24740, 24753, 24765, 24777, 24790, 24801, 24813, 24825, 24836, 24848,
1401 24859, 24870, 24881, 24892, 24902, 24913, 24923, 24933, 24944, 24954, 24964, 24973, 24983, 24993, 25002, 25012,
1402 25021, 25030, 25039, 25048, 25057, 25066, 25075, 25084, 25092, 25101, 25109, 25117, 25126, 25134, 25142, 25150,
1403 25158, 25166, 25174, 25182, 25189, 25197, 25205, 25212, 25219, 25227, 25234, 25241, 25249, 25256, 25263, 25270],
1404 [25277, 25291, 25304, 25318, 25331, 25344, 25357, 25369, 25382, 25394, 25406, 25418, 25430, 25441, 25453, 25464,
1405 25475, 25486, 25497, 25508, 25519, 25529, 25540, 25550, 25560, 25570, 25580, 25590, 25600, 25609, 25619, 25628,
1406 25638, 25647, 25656, 25665, 25674, 25683, 25691, 25700, 25709, 25717, 25726, 25734, 25742, 25750, 25759, 25767,
1407 25775, 25783, 25790, 25798, 25806, 25813, 25821, 25829, 25836, 25843, 25851, 25858, 25865, 25872, 25879, 25886],
1408 [25893, 25907, 25921, 25934, 25947, 25960, 25973, 25986, 25998, 26010, 26023, 26034, 26046, 26058, 26069, 26081,
1409 26092, 26103, 26114, 26125, 26135, 26146, 26156, 26166, 26177, 26187, 26197, 26206, 26216, 26226, 26235, 26245,
1410 26254, 26263, 26272, 26281, 26290, 26299, 26308, 26317, 26325, 26334, 26342, 26351, 26359, 26367, 26375, 26383,
1411 26391, 26399, 26407, 26415, 26422, 26430, 26438, 26445, 26453, 26460, 26467, 26474, 26482, 26489, 26496, 26503],
1412 [26510, 26524, 26537, 26551, 26564, 26577, 26590, 26602, 26615, 26627, 26639, 26651, 26663, 26674, 26686, 26697,
1413 26708, 26719, 26730, 26741, 26752, 26762, 26773, 26783, 26793, 26803, 26813, 26823, 26833, 26842, 26852, 26861,
1414 26871, 26880, 26889, 26898, 26907, 26916, 26924, 26933, 26942, 26950, 26959, 26967, 26975, 26983, 26992, 27000,
1415 27008, 27016, 27023, 27031, 27039, 27046, 27054, 27062, 27069, 27076, 27084, 27091, 27098, 27105, 27112, 27119],
1416 [27126, 27140, 27154, 27167, 27180, 27193, 27206, 27219, 27231, 27243, 27256, 27267, 27279, 27291, 27302, 27314,
1417 27325, 27336, 27347, 27358, 27368, 27379, 27389, 27399, 27410, 27420, 27430, 27439, 27449, 27459, 27468, 27478,
1418 27487, 27496, 27505, 27514, 27523, 27532, 27541, 27550, 27558, 27567, 27575, 27584, 27592, 27600, 27608, 27616,
1419 27624, 27632, 27640, 27648, 27655, 27663, 27671, 27678, 27686, 27693, 27700, 27707, 27715, 27722, 27729, 27736],
1420 [27743, 27757, 27770, 27784, 27797, 27810, 27823, 27835, 27848, 27860, 27872, 27884, 27896, 27907, 27919, 27930,
1421 27941, 27952, 27963, 27974, 27985, 27995, 28006, 28016, 28026, 28036, 28046, 28056, 28066, 28075, 28085, 28094,
1422 28104, 28113, 28122, 28131, 28140, 28149, 28157, 28166, 28175, 28183, 28192, 28200, 28208, 28217, 28225, 28233,
1423 28241, 28249, 28256, 28264, 28272, 28280, 28287, 28295, 28302, 28309, 28317, 28324, 28331, 28338, 28345, 28352],
1424 [28359, 28373, 28387, 28400, 28413, 28426, 28439, 28452, 28464, 28476, 28489, 28501, 28512, 28524, 28535, 28547,
1425 28558, 28569, 28580, 28591, 28601, 28612, 28622, 28633, 28643, 28653, 28663, 28672, 28682, 28692, 28701, 28711,
1426 28720, 28729, 28738, 28747, 28756, 28765, 28774, 28783, 28791, 28800, 28808, 28817, 28825, 28833, 28841, 28849,
1427 28857, 28865, 28873, 28881, 28888, 28896, 28904, 28911, 28919, 28926, 28933, 28941, 28948, 28955, 28962, 28969],
1428 [28976, 28990, 29003, 29017, 29030, 29043, 29056, 29068, 29081, 29093, 29105, 29117, 29129, 29140, 29152, 29163,
1429 29174, 29185, 29196, 29207, 29218, 29228, 29239, 29249, 29259, 29269, 29279, 29289, 29299, 29308, 29318, 29327,
1430 29337, 29346, 29355, 29364, 29373, 29382, 29390, 29399, 29408, 29416, 29425, 29433, 29441, 29450, 29458, 29466,
1431 29474, 29482, 29489, 29497, 29505, 29513, 29520, 29528, 29535, 29542, 29550, 29557, 29564, 29571, 29578, 29585],
1432 [29592, 29606, 29620, 29633, 29646, 29659, 29672, 29685, 29697, 29709, 29722, 29734, 29745, 29757, 29768, 29780,
1433 29791, 29802, 29813, 29824, 29834, 29845, 29855, 29866, 29876, 29886, 29896, 29906, 29915, 29925, 29934, 29944,
1434 29953, 29962, 29971, 29980, 29989, 29998, 30007, 30016, 30024, 30033, 30041, 30050, 30058, 30066, 30074, 30082,
1435 30090, 30098, 30106, 30114, 30121, 30129, 30137, 30144, 30152, 30159, 30166, 30174, 30181, 30188, 30195, 30202],
1436 [30209, 30223, 30236, 30250, 30263, 30276, 30289, 30301, 30314, 30326, 30338, 30350, 30362, 30373, 30385, 30396,
1437 30407, 30418, 30429, 30440, 30451, 30461, 30472, 30482, 30492, 30502, 30512, 30522, 30532, 30541, 30551, 30560,
1438 30570, 30579, 30588, 30597, 30606, 30615, 30624, 30632, 30641, 30649, 30658, 30666, 30674, 30683, 30691, 30699,
1439 30707, 30715, 30722, 30730, 30738, 30746, 30753, 30761, 30768, 30775, 30783, 30790, 30797, 30804, 30811, 30818],
1440 [30825, 30839, 30853, 30866, 30879, 30892, 30905, 30918, 30930, 30943, 30955, 30967, 30978, 30990, 31001, 31013,
1441 31024, 31035, 31046, 31057, 31067, 31078, 31088, 31099, 31109, 31119, 31129, 31139, 31148, 31158, 31167, 31177,
1442 31186, 31195, 31204, 31213, 31222, 31231, 31240, 31249, 31257, 31266, 31274, 31283, 31291, 31299, 31307, 31315,
1443 31323, 31331, 31339, 31347, 31354, 31362, 31370, 31377, 31385, 31392, 31399, 31407, 31414, 31421, 31428, 31435],
1444 [31442, 31456, 31469, 31483, 31496, 31509, 31522, 31534, 31547, 31559, 31571, 31583, 31595, 31606, 31618, 31629,
1445 31640, 31652, 31662, 31673, 31684, 31694, 31705, 31715, 31725, 31735, 31745, 31755, 31765, 31774, 31784, 31793,
1446 31803, 31812, 31821, 31830, 31839, 31848, 31857, 31865, 31874, 31882, 31891, 31899, 31907, 31916, 31924, 31932,
1447 31940, 31948, 31955, 31963, 31971, 31979, 31986, 31994, 32001, 32008, 32016, 32023, 32030, 32037, 32044, 32052],
1448 [32058, 32072, 32086, 32099, 32112, 32125, 32138, 32151, 32163, 32176, 32188, 32200, 32211, 32223, 32234, 32246,
1449 32257, 32268, 32279, 32290, 32300, 32311, 32321, 32332, 32342, 32352, 32362, 32372, 32381, 32391, 32400, 32410,
1450 32419, 32428, 32437, 32446, 32455, 32464, 32473, 32482, 32490, 32499, 32507, 32516, 32524, 32532, 32540, 32548,
1451 32556, 32564, 32572, 32580, 32587, 32595, 32603, 32610, 32618, 32625, 32632, 32640, 32647, 32654, 32661, 32668],
1452 [32675, 32689, 32702, 32716, 32729, 32742, 32755, 32767, 32780, 32792, 32804, 32816, 32828, 32839, 32851, 32862,
1453 32873, 32885, 32895, 32906, 32917, 32927, 32938, 32948, 32958, 32968, 32978, 32988, 32998, 33007, 33017, 33026,
1454 33036, 33045, 33054, 33063, 33072, 33081, 33090, 33098, 33107, 33115, 33124, 33132, 33140, 33149, 33157, 33165,
1455 33173, 33181, 33188, 33196, 33204, 33212, 33219, 33227, 33234, 33241, 33249, 33256, 33263, 33270, 33278, 33285],
1456 [33292, 33305, 33319, 33332, 33345, 33358, 33371, 33384, 33396, 33409, 33421, 33433, 33444, 33456, 33467, 33479,
1457 33490, 33501, 33512, 33523, 33533, 33544, 33554, 33565, 33575, 33585, 33595, 33605, 33614, 33624, 33633, 33643,
1458 33652, 33661, 33670, 33680, 33688, 33697, 33706, 33715, 33723, 33732, 33740, 33749, 33757, 33765, 33773, 33781,
1459 33789, 33797, 33805, 33813, 33820, 33828, 33836, 33843, 33851, 33858, 33865, 33873, 33880, 33887, 33894, 33901],
1460 [33908, 33922, 33935, 33949, 33962, 33975, 33988, 34000, 34013, 34025, 34037, 34049, 34061, 34072, 34084, 34095,
1461 34106, 34118, 34128, 34139, 34150, 34160, 34171, 34181, 34191, 34201, 34211, 34221, 34231, 34240, 34250, 34259,
1462 34269, 34278, 34287, 34296, 34305, 34314, 34323, 34331, 34340, 34348, 34357, 34365, 34373, 34382, 34390, 34398,
1463 34406, 34414, 34422, 34429, 34437, 34445, 34452, 34460, 34467, 34475, 34482, 34489, 34496, 34503, 34511, 34518],
1464 [34525, 34538, 34552, 34565, 34578, 34591, 34604, 34617, 34629, 34642, 34654, 34666, 34677, 34689, 34700, 34712,
1465 34723, 34734, 34745, 34756, 34766, 34777, 34787, 34798, 34808, 34818, 34828, 34838, 34847, 34857, 34866, 34876,
1466 34885, 34894, 34904, 34913, 34921, 34930, 34939, 34948, 34956, 34965, 34973, 34982, 34990, 34998, 35006, 35014,
1467 35022, 35030, 35038, 35046, 35053, 35061, 35069, 35076, 35084, 35091, 35098, 35106, 35113, 35120, 35127, 35134],
1468 [35141, 35155, 35168, 35182, 35195, 35208, 35221, 35233, 35246, 35258, 35270, 35282, 35294, 35306, 35317, 35328,
1469 35340, 35351, 35361, 35372, 35383, 35393, 35404, 35414, 35424, 35434, 35444, 35454, 35464, 35473, 35483, 35492,
1470 35502, 35511, 35520, 35529, 35538, 35547, 35556, 35564, 35573, 35581, 35590, 35598, 35606, 35615, 35623, 35631,
1471 35639, 35647, 35655, 35662, 35670, 35678, 35685, 35693, 35700, 35708, 35715, 35722, 35729, 35736, 35744, 35751],
1472 [35758, 35771, 35785, 35798, 35811, 35824, 35837, 35850, 35862, 35875, 35887, 35899, 35910, 35922, 35934, 35945,
1473 35956, 35967, 35978, 35989, 35999, 36010, 36020, 36031, 36041, 36051, 36061, 36071, 36080, 36090, 36099, 36109,
1474 36118, 36127, 36137, 36146, 36154, 36163, 36172, 36181, 36189, 36198, 36206, 36215, 36223, 36231, 36239, 36247,
1475 36255, 36263, 36271, 36279, 36287, 36294, 36302, 36309, 36317, 36324, 36331, 36339, 36346, 36353, 36360, 36367],
1476 [36374, 36388, 36401, 36415, 36428, 36441, 36454, 36466, 36479, 36491, 36503, 36515, 36527, 36539, 36550, 36561,
1477 36573, 36584, 36594, 36605, 36616, 36626, 36637, 36647, 36657, 36667, 36677, 36687, 36697, 36706, 36716, 36725,
1478 36735, 36744, 36753, 36762, 36771, 36780, 36789, 36797, 36806, 36814, 36823, 36831, 36839, 36848, 36856, 36864,
1479 36872, 36880, 36888, 36895, 36903, 36911, 36918, 36926, 36933, 36941, 36948, 36955, 36962, 36969, 36977, 36984],
1480 [36991, 37004, 37018, 37031, 37044, 37057, 37070, 37083, 37095, 37108, 37120, 37132, 37143, 37155, 37167, 37178,
1481 37189, 37200, 37211, 37222, 37232, 37243, 37253, 37264, 37274, 37284, 37294, 37304, 37313, 37323, 37332, 37342,
1482 37351, 37360, 37370, 37379, 37388, 37396, 37405, 37414, 37422, 37431, 37439, 37448, 37456, 37464, 37472, 37480,
1483 37488, 37496, 37504, 37512, 37520, 37527, 37535, 37542, 37550, 37557, 37564, 37572, 37579, 37586, 37593, 37600],
1484 [37607, 37621, 37634, 37648, 37661, 37674, 37687, 37699, 37712, 37724, 37736, 37748, 37760, 37772, 37783, 37794,
1485 37806, 37817, 37828, 37838, 37849, 37859, 37870, 37880, 37890, 37900, 37910, 37920, 37930, 37939, 37949, 37958,
1486 37968, 37977, 37986, 37995, 38004, 38013, 38022, 38030, 38039, 38047, 38056, 38064, 38072, 38081, 38089, 38097,
1487 38105, 38113, 38121, 38128, 38136, 38144, 38151, 38159, 38166, 38174, 38181, 38188, 38195, 38202, 38210, 38217],
1488 [38224, 38237, 38251, 38264, 38278, 38290, 38303, 38316, 38328, 38341, 38353, 38365, 38376, 38388, 38400, 38411,
1489 38422, 38433, 38444, 38455, 38465, 38476, 38486, 38497, 38507, 38517, 38527, 38537, 38546, 38556, 38565, 38575,
1490 38584, 38593, 38603, 38612, 38621, 38629, 38638, 38647, 38655, 38664, 38672, 38681, 38689, 38697, 38705, 38713,
1491 38721, 38729, 38737, 38745, 38753, 38760, 38768, 38775, 38783, 38790, 38797, 38805, 38812, 38819, 38826, 38833],
1492 [38840, 38854, 38867, 38881, 38894, 38907, 38920, 38932, 38945, 38957, 38969, 38981, 38993, 39005, 39016, 39027,
1493 39039, 39050, 39061, 39071, 39082, 39092, 39103, 39113, 39123, 39133, 39143, 39153, 39163, 39172, 39182, 39191,
1494 39201, 39210, 39219, 39228, 39237, 39246, 39255, 39263, 39272, 39280, 39289, 39297, 39305, 39314, 39322, 39330,
1495 39338, 39346, 39354, 39361, 39369, 39377, 39384, 39392, 39399, 39407, 39414, 39421, 39428, 39436, 39443, 39450],
1498 /// Approximate `log10(numerator / denominator) * 2048` using a look-up table.
1500 pub fn negative_log10_times_2048(numerator: u64, denominator: u64) -> u64 {
1501 // Multiply the -1 through to avoid needing to use signed numbers.
1502 (log10_times_2048(denominator) - log10_times_2048(numerator)) as u64
1506 fn log10_times_2048(x: u64) -> u16 {
1507 debug_assert_ne!(x, 0);
1508 let most_significant_bit = HIGHEST_BIT - x.leading_zeros();
1509 let lower_bits = (x >> most_significant_bit.saturating_sub(LOWER_BITS)) & LOWER_BITMASK;
1510 LOG10_TIMES_2048[most_significant_bit as usize][lower_bits as usize]
1518 fn prints_negative_log10_times_2048_lookup_table() {
1519 for msb in 0..BITS {
1520 for i in 0..LOWER_BITS_BOUND {
1521 let x = ((LOWER_BITS_BOUND + i) << (HIGHEST_BIT - LOWER_BITS)) >> (HIGHEST_BIT - msb);
1522 let log10_times_2048 = ((x as f64).log10() * 2048.0).round() as u16;
1523 assert_eq!(log10_times_2048, LOG10_TIMES_2048[msb as usize][i as usize]);
1525 if i % LOWER_BITS_BOUND == 0 {
1526 print!("\t\t[{}, ", log10_times_2048);
1527 } else if i % LOWER_BITS_BOUND == LOWER_BITS_BOUND - 1 {
1528 println!("{}],", log10_times_2048);
1529 } else if i % (LOWER_BITS_BOUND/4) == LOWER_BITS_BOUND/4 - 1 {
1530 print!("{},\n\t\t\t", log10_times_2048);
1532 print!("{}, ", log10_times_2048);
1540 mod bucketed_history {
1543 /// Tracks the historical state of a distribution as a weighted average of how much time was spent
1544 /// in each of 8 buckets.
1545 #[derive(Clone, Copy)]
1546 pub(super) struct HistoricalBucketRangeTracker {
1550 impl HistoricalBucketRangeTracker {
1551 pub(super) fn new() -> Self { Self { buckets: [0; 8] } }
1552 pub(super) fn track_datapoint(&mut self, liquidity_offset_msat: u64, capacity_msat: u64) {
1553 // We have 8 leaky buckets for min and max liquidity. Each bucket tracks the amount of time
1554 // we spend in each bucket as a 16-bit fixed-point number with a 5 bit fractional part.
1556 // Each time we update our liquidity estimate, we add 32 (1.0 in our fixed-point system) to
1557 // the buckets for the current min and max liquidity offset positions.
1559 // We then decay each bucket by multiplying by 2047/2048 (avoiding dividing by a
1560 // non-power-of-two). This ensures we can't actually overflow the u16 - when we get to
1561 // 63,457 adding 32 and decaying by 2047/2048 leaves us back at 63,457.
1563 // In total, this allows us to track data for the last 8,000 or so payments across a given
1566 // These constants are a balance - we try to fit in 2 bytes per bucket to reduce overhead,
1567 // and need to balance having more bits in the decimal part (to ensure decay isn't too
1568 // non-linear) with having too few bits in the mantissa, causing us to not store very many
1571 // The constants were picked experimentally, selecting a decay amount that restricts us
1572 // from overflowing buckets without having to cap them manually.
1574 // Ensure the bucket index is in the range [0, 7], even if the liquidity offset is zero or
1575 // the channel's capacity, though the second should generally never happen.
1576 debug_assert!(liquidity_offset_msat <= capacity_msat);
1577 let bucket_idx: u8 = (liquidity_offset_msat * 8 / capacity_msat.saturating_add(1))
1578 .try_into().unwrap_or(32); // 32 is bogus for 8 buckets, and will be ignored
1579 debug_assert!(bucket_idx < 8);
1581 for e in self.buckets.iter_mut() {
1582 *e = ((*e as u32) * 2047 / 2048) as u16;
1584 self.buckets[bucket_idx as usize] = self.buckets[bucket_idx as usize].saturating_add(32);
1587 /// Decay all buckets by the given number of half-lives. Used to more aggressively remove old
1588 /// datapoints as we receive newer information.
1589 pub(super) fn time_decay_data(&mut self, half_lives: u32) {
1590 for e in self.buckets.iter_mut() {
1591 *e = e.checked_shr(half_lives).unwrap_or(0);
1596 impl_writeable_tlv_based!(HistoricalBucketRangeTracker, { (0, buckets, required) });
1598 pub(super) struct HistoricalMinMaxBuckets<D: Deref<Target = HistoricalBucketRangeTracker>> {
1599 pub(super) min_liquidity_offset_history: D,
1600 pub(super) max_liquidity_offset_history: D,
1603 impl<D: Deref<Target = HistoricalBucketRangeTracker>> HistoricalMinMaxBuckets<D> {
1605 pub(super) fn get_decayed_buckets<T: Time>(&self, now: T, last_updated: T, half_life: Duration)
1606 -> ([u16; 8], [u16; 8], u32) {
1607 let required_decays = now.duration_since(last_updated).as_secs()
1608 .checked_div(half_life.as_secs())
1609 .map_or(u32::max_value(), |decays| cmp::min(decays, u32::max_value() as u64) as u32);
1610 let mut min_buckets = *self.min_liquidity_offset_history;
1611 min_buckets.time_decay_data(required_decays);
1612 let mut max_buckets = *self.max_liquidity_offset_history;
1613 max_buckets.time_decay_data(required_decays);
1614 (min_buckets.buckets, max_buckets.buckets, required_decays)
1618 pub(super) fn calculate_success_probability_times_billion<T: Time>(
1619 &self, now: T, last_updated: T, half_life: Duration, amount_msat: u64, capacity_msat: u64)
1621 // If historical penalties are enabled, calculate the penalty by walking the set of
1622 // historical liquidity bucket (min, max) combinations (where min_idx < max_idx) and, for
1623 // each, calculate the probability of success given our payment amount, then total the
1624 // weighted average probability of success.
1626 // We use a sliding scale to decide which point within a given bucket will be compared to
1627 // the amount being sent - for lower-bounds, the amount being sent is compared to the lower
1628 // edge of the first bucket (i.e. zero), but compared to the upper 7/8ths of the last
1629 // bucket (i.e. 9 times the index, or 63), with each bucket in between increasing the
1630 // comparison point by 1/64th. For upper-bounds, the same applies, however with an offset
1631 // of 1/64th (i.e. starting at one and ending at 64). This avoids failing to assign
1632 // penalties to channels at the edges.
1634 // If we used the bottom edge of buckets, we'd end up never assigning any penalty at all to
1635 // such a channel when sending less than ~0.19% of the channel's capacity (e.g. ~200k sats
1636 // for a 1 BTC channel!).
1638 // If we used the middle of each bucket we'd never assign any penalty at all when sending
1639 // less than 1/16th of a channel's capacity, or 1/8th if we used the top of the bucket.
1640 let mut total_valid_points_tracked = 0;
1642 let payment_amt_64th_bucket: u8 = if amount_msat < u64::max_value() / 64 {
1643 (amount_msat * 64 / capacity_msat.saturating_add(1))
1644 .try_into().unwrap_or(65)
1646 // Only use 128-bit arithmetic when multiplication will overflow to avoid 128-bit
1647 // division. This branch should only be hit in fuzz testing since the amount would
1648 // need to be over 2.88 million BTC in practice.
1649 ((amount_msat as u128) * 64 / (capacity_msat as u128).saturating_add(1))
1650 .try_into().unwrap_or(65)
1652 #[cfg(not(fuzzing))]
1653 debug_assert!(payment_amt_64th_bucket <= 64);
1654 if payment_amt_64th_bucket >= 64 { return None; }
1656 // Check if all our buckets are zero, once decayed and treat it as if we had no data. We
1657 // don't actually use the decayed buckets, though, as that would lose precision.
1658 let (decayed_min_buckets, decayed_max_buckets, required_decays) =
1659 self.get_decayed_buckets(now, last_updated, half_life);
1660 if decayed_min_buckets.iter().all(|v| *v == 0) || decayed_max_buckets.iter().all(|v| *v == 0) {
1664 for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate() {
1665 for max_bucket in self.max_liquidity_offset_history.buckets.iter().take(8 - min_idx) {
1666 total_valid_points_tracked += (*min_bucket as u64) * (*max_bucket as u64);
1669 // If the total valid points is smaller than 1.0 (i.e. 32 in our fixed-point scheme), treat
1670 // it as if we were fully decayed.
1671 if total_valid_points_tracked.checked_shr(required_decays).unwrap_or(0) < 32*32 {
1675 let mut cumulative_success_prob_times_billion = 0;
1676 for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate() {
1677 for (max_idx, max_bucket) in self.max_liquidity_offset_history.buckets.iter().enumerate().take(8 - min_idx) {
1678 let bucket_prob_times_million = (*min_bucket as u64) * (*max_bucket as u64)
1679 * 1024 * 1024 / total_valid_points_tracked;
1680 let min_64th_bucket = min_idx as u8 * 9;
1681 let max_64th_bucket = (7 - max_idx as u8) * 9 + 1;
1682 if payment_amt_64th_bucket > max_64th_bucket {
1683 // Success probability 0, the payment amount is above the max liquidity
1684 } else if payment_amt_64th_bucket <= min_64th_bucket {
1685 cumulative_success_prob_times_billion += bucket_prob_times_million * 1024;
1687 cumulative_success_prob_times_billion += bucket_prob_times_million *
1688 ((max_64th_bucket - payment_amt_64th_bucket) as u64) * 1024 /
1689 ((max_64th_bucket - min_64th_bucket) as u64);
1694 Some(cumulative_success_prob_times_billion)
1698 use bucketed_history::{HistoricalBucketRangeTracker, HistoricalMinMaxBuckets};
1700 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Writeable for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1702 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
1703 write_tlv_fields!(w, {
1704 (0, self.channel_liquidities, required),
1710 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time>
1711 ReadableArgs<(ProbabilisticScoringDecayParameters, G, L)> for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1714 r: &mut R, args: (ProbabilisticScoringDecayParameters, G, L)
1715 ) -> Result<Self, DecodeError> {
1716 let (decay_params, network_graph, logger) = args;
1717 let mut channel_liquidities = HashMap::new();
1718 read_tlv_fields!(r, {
1719 (0, channel_liquidities, required),
1725 channel_liquidities,
1730 impl<T: Time> Writeable for ChannelLiquidity<T> {
1732 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
1733 let duration_since_epoch = T::duration_since_epoch() - self.last_updated.elapsed();
1734 write_tlv_fields!(w, {
1735 (0, self.min_liquidity_offset_msat, required),
1736 (1, Some(self.min_liquidity_offset_history), option),
1737 (2, self.max_liquidity_offset_msat, required),
1738 (3, Some(self.max_liquidity_offset_history), option),
1739 (4, duration_since_epoch, required),
1745 impl<T: Time> Readable for ChannelLiquidity<T> {
1747 fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
1748 let mut min_liquidity_offset_msat = 0;
1749 let mut max_liquidity_offset_msat = 0;
1750 let mut min_liquidity_offset_history = Some(HistoricalBucketRangeTracker::new());
1751 let mut max_liquidity_offset_history = Some(HistoricalBucketRangeTracker::new());
1752 let mut duration_since_epoch = Duration::from_secs(0);
1753 read_tlv_fields!(r, {
1754 (0, min_liquidity_offset_msat, required),
1755 (1, min_liquidity_offset_history, option),
1756 (2, max_liquidity_offset_msat, required),
1757 (3, max_liquidity_offset_history, option),
1758 (4, duration_since_epoch, required),
1760 // On rust prior to 1.60 `Instant::duration_since` will panic if time goes backwards.
1761 // We write `last_updated` as wallclock time even though its ultimately an `Instant` (which
1762 // is a time from a monotonic clock usually represented as an offset against boot time).
1763 // Thus, we have to construct an `Instant` by subtracting the difference in wallclock time
1764 // from the one that was written. However, because `Instant` can panic if we construct one
1765 // in the future, we must handle wallclock time jumping backwards, which we do by simply
1766 // using `Instant::now()` in that case.
1767 let wall_clock_now = T::duration_since_epoch();
1769 let last_updated = if wall_clock_now > duration_since_epoch {
1770 now - (wall_clock_now - duration_since_epoch)
1773 min_liquidity_offset_msat,
1774 max_liquidity_offset_msat,
1775 min_liquidity_offset_history: min_liquidity_offset_history.unwrap(),
1776 max_liquidity_offset_history: max_liquidity_offset_history.unwrap(),
1784 use super::{ChannelLiquidity, HistoricalBucketRangeTracker, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters, ProbabilisticScorerUsingTime};
1785 use crate::blinded_path::{BlindedHop, BlindedPath};
1786 use crate::util::config::UserConfig;
1787 use crate::util::time::Time;
1788 use crate::util::time::tests::SinceEpoch;
1790 use crate::ln::channelmanager;
1791 use crate::ln::msgs::{ChannelAnnouncement, ChannelUpdate, UnsignedChannelAnnouncement, UnsignedChannelUpdate};
1792 use crate::routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId};
1793 use crate::routing::router::{BlindedTail, Path, RouteHop};
1794 use crate::routing::scoring::{ChannelUsage, Score};
1795 use crate::util::ser::{ReadableArgs, Writeable};
1796 use crate::util::test_utils::{self, TestLogger};
1798 use bitcoin::blockdata::constants::genesis_block;
1799 use bitcoin::hashes::Hash;
1800 use bitcoin::hashes::sha256d::Hash as Sha256dHash;
1801 use bitcoin::network::constants::Network;
1802 use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey};
1803 use core::time::Duration;
1806 fn source_privkey() -> SecretKey {
1807 SecretKey::from_slice(&[42; 32]).unwrap()
1810 fn target_privkey() -> SecretKey {
1811 SecretKey::from_slice(&[43; 32]).unwrap()
1814 fn source_pubkey() -> PublicKey {
1815 let secp_ctx = Secp256k1::new();
1816 PublicKey::from_secret_key(&secp_ctx, &source_privkey())
1819 fn target_pubkey() -> PublicKey {
1820 let secp_ctx = Secp256k1::new();
1821 PublicKey::from_secret_key(&secp_ctx, &target_privkey())
1824 fn source_node_id() -> NodeId {
1825 NodeId::from_pubkey(&source_pubkey())
1828 fn target_node_id() -> NodeId {
1829 NodeId::from_pubkey(&target_pubkey())
1832 // `ProbabilisticScorer` tests
1834 /// A probabilistic scorer for testing with time that can be manually advanced.
1835 type ProbabilisticScorer<'a> = ProbabilisticScorerUsingTime::<&'a NetworkGraph<&'a TestLogger>, &'a TestLogger, SinceEpoch>;
1837 fn sender_privkey() -> SecretKey {
1838 SecretKey::from_slice(&[41; 32]).unwrap()
1841 fn recipient_privkey() -> SecretKey {
1842 SecretKey::from_slice(&[45; 32]).unwrap()
1845 fn sender_pubkey() -> PublicKey {
1846 let secp_ctx = Secp256k1::new();
1847 PublicKey::from_secret_key(&secp_ctx, &sender_privkey())
1850 fn recipient_pubkey() -> PublicKey {
1851 let secp_ctx = Secp256k1::new();
1852 PublicKey::from_secret_key(&secp_ctx, &recipient_privkey())
1855 fn sender_node_id() -> NodeId {
1856 NodeId::from_pubkey(&sender_pubkey())
1859 fn recipient_node_id() -> NodeId {
1860 NodeId::from_pubkey(&recipient_pubkey())
1863 fn network_graph(logger: &TestLogger) -> NetworkGraph<&TestLogger> {
1864 let mut network_graph = NetworkGraph::new(Network::Testnet, logger);
1865 add_channel(&mut network_graph, 42, source_privkey(), target_privkey());
1866 add_channel(&mut network_graph, 43, target_privkey(), recipient_privkey());
1872 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_1_key: SecretKey,
1873 node_2_key: SecretKey
1875 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1876 let node_1_secret = &SecretKey::from_slice(&[39; 32]).unwrap();
1877 let node_2_secret = &SecretKey::from_slice(&[40; 32]).unwrap();
1878 let secp_ctx = Secp256k1::new();
1879 let unsigned_announcement = UnsignedChannelAnnouncement {
1880 features: channelmanager::provided_channel_features(&UserConfig::default()),
1881 chain_hash: genesis_hash,
1883 node_id_1: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_1_key)),
1884 node_id_2: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_2_key)),
1885 bitcoin_key_1: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_1_secret)),
1886 bitcoin_key_2: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_2_secret)),
1887 excess_data: Vec::new(),
1889 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
1890 let signed_announcement = ChannelAnnouncement {
1891 node_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_key),
1892 node_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_key),
1893 bitcoin_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_secret),
1894 bitcoin_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_secret),
1895 contents: unsigned_announcement,
1897 let chain_source: Option<&crate::util::test_utils::TestChainSource> = None;
1898 network_graph.update_channel_from_announcement(
1899 &signed_announcement, &chain_source).unwrap();
1900 update_channel(network_graph, short_channel_id, node_1_key, 0, 1_000);
1901 update_channel(network_graph, short_channel_id, node_2_key, 1, 0);
1905 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_key: SecretKey,
1906 flags: u8, htlc_maximum_msat: u64
1908 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1909 let secp_ctx = Secp256k1::new();
1910 let unsigned_update = UnsignedChannelUpdate {
1911 chain_hash: genesis_hash,
1915 cltv_expiry_delta: 18,
1916 htlc_minimum_msat: 0,
1919 fee_proportional_millionths: 0,
1920 excess_data: Vec::new(),
1922 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_update.encode()[..])[..]);
1923 let signed_update = ChannelUpdate {
1924 signature: secp_ctx.sign_ecdsa(&msghash, &node_key),
1925 contents: unsigned_update,
1927 network_graph.update_channel(&signed_update).unwrap();
1930 fn path_hop(pubkey: PublicKey, short_channel_id: u64, fee_msat: u64) -> RouteHop {
1931 let config = UserConfig::default();
1934 node_features: channelmanager::provided_node_features(&config),
1936 channel_features: channelmanager::provided_channel_features(&config),
1938 cltv_expiry_delta: 18,
1942 fn payment_path_for_amount(amount_msat: u64) -> Path {
1945 path_hop(source_pubkey(), 41, 1),
1946 path_hop(target_pubkey(), 42, 2),
1947 path_hop(recipient_pubkey(), 43, amount_msat),
1948 ], blinded_tail: None,
1953 fn liquidity_bounds_directed_from_lowest_node_id() {
1954 let logger = TestLogger::new();
1955 let last_updated = SinceEpoch::now();
1956 let network_graph = network_graph(&logger);
1957 let decay_params = ProbabilisticScoringDecayParameters::default();
1958 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
1961 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated,
1962 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1963 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1967 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated,
1968 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1969 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1971 let source = source_node_id();
1972 let target = target_node_id();
1973 let recipient = recipient_node_id();
1974 assert!(source > target);
1975 assert!(target < recipient);
1977 // Update minimum liquidity.
1979 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1980 .as_directed(&source, &target, 0, 1_000, decay_params);
1981 assert_eq!(liquidity.min_liquidity_msat(), 100);
1982 assert_eq!(liquidity.max_liquidity_msat(), 300);
1984 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1985 .as_directed(&target, &source, 0, 1_000, decay_params);
1986 assert_eq!(liquidity.min_liquidity_msat(), 700);
1987 assert_eq!(liquidity.max_liquidity_msat(), 900);
1989 scorer.channel_liquidities.get_mut(&42).unwrap()
1990 .as_directed_mut(&source, &target, 0, 1_000, decay_params)
1991 .set_min_liquidity_msat(200);
1993 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1994 .as_directed(&source, &target, 0, 1_000, decay_params);
1995 assert_eq!(liquidity.min_liquidity_msat(), 200);
1996 assert_eq!(liquidity.max_liquidity_msat(), 300);
1998 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1999 .as_directed(&target, &source, 0, 1_000, decay_params);
2000 assert_eq!(liquidity.min_liquidity_msat(), 700);
2001 assert_eq!(liquidity.max_liquidity_msat(), 800);
2003 // Update maximum liquidity.
2005 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2006 .as_directed(&target, &recipient, 0, 1_000, decay_params);
2007 assert_eq!(liquidity.min_liquidity_msat(), 700);
2008 assert_eq!(liquidity.max_liquidity_msat(), 900);
2010 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2011 .as_directed(&recipient, &target, 0, 1_000, decay_params);
2012 assert_eq!(liquidity.min_liquidity_msat(), 100);
2013 assert_eq!(liquidity.max_liquidity_msat(), 300);
2015 scorer.channel_liquidities.get_mut(&43).unwrap()
2016 .as_directed_mut(&target, &recipient, 0, 1_000, decay_params)
2017 .set_max_liquidity_msat(200);
2019 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2020 .as_directed(&target, &recipient, 0, 1_000, decay_params);
2021 assert_eq!(liquidity.min_liquidity_msat(), 0);
2022 assert_eq!(liquidity.max_liquidity_msat(), 200);
2024 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2025 .as_directed(&recipient, &target, 0, 1_000, decay_params);
2026 assert_eq!(liquidity.min_liquidity_msat(), 800);
2027 assert_eq!(liquidity.max_liquidity_msat(), 1000);
2031 fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() {
2032 let logger = TestLogger::new();
2033 let last_updated = SinceEpoch::now();
2034 let network_graph = network_graph(&logger);
2035 let decay_params = ProbabilisticScoringDecayParameters::default();
2036 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2039 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated,
2040 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2041 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2043 let source = source_node_id();
2044 let target = target_node_id();
2045 assert!(source > target);
2047 // Check initial bounds.
2048 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2049 .as_directed(&source, &target, 0, 1_000, decay_params);
2050 assert_eq!(liquidity.min_liquidity_msat(), 400);
2051 assert_eq!(liquidity.max_liquidity_msat(), 800);
2053 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2054 .as_directed(&target, &source, 0, 1_000, decay_params);
2055 assert_eq!(liquidity.min_liquidity_msat(), 200);
2056 assert_eq!(liquidity.max_liquidity_msat(), 600);
2058 // Reset from source to target.
2059 scorer.channel_liquidities.get_mut(&42).unwrap()
2060 .as_directed_mut(&source, &target, 0, 1_000, decay_params)
2061 .set_min_liquidity_msat(900);
2063 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2064 .as_directed(&source, &target, 0, 1_000, decay_params);
2065 assert_eq!(liquidity.min_liquidity_msat(), 900);
2066 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2068 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2069 .as_directed(&target, &source, 0, 1_000, decay_params);
2070 assert_eq!(liquidity.min_liquidity_msat(), 0);
2071 assert_eq!(liquidity.max_liquidity_msat(), 100);
2073 // Reset from target to source.
2074 scorer.channel_liquidities.get_mut(&42).unwrap()
2075 .as_directed_mut(&target, &source, 0, 1_000, decay_params)
2076 .set_min_liquidity_msat(400);
2078 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2079 .as_directed(&source, &target, 0, 1_000, decay_params);
2080 assert_eq!(liquidity.min_liquidity_msat(), 0);
2081 assert_eq!(liquidity.max_liquidity_msat(), 600);
2083 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2084 .as_directed(&target, &source, 0, 1_000, decay_params);
2085 assert_eq!(liquidity.min_liquidity_msat(), 400);
2086 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2090 fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() {
2091 let logger = TestLogger::new();
2092 let last_updated = SinceEpoch::now();
2093 let network_graph = network_graph(&logger);
2094 let decay_params = ProbabilisticScoringDecayParameters::default();
2095 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2098 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated,
2099 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2100 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2102 let source = source_node_id();
2103 let target = target_node_id();
2104 assert!(source > target);
2106 // Check initial bounds.
2107 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2108 .as_directed(&source, &target, 0, 1_000, decay_params);
2109 assert_eq!(liquidity.min_liquidity_msat(), 400);
2110 assert_eq!(liquidity.max_liquidity_msat(), 800);
2112 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2113 .as_directed(&target, &source, 0, 1_000, decay_params);
2114 assert_eq!(liquidity.min_liquidity_msat(), 200);
2115 assert_eq!(liquidity.max_liquidity_msat(), 600);
2117 // Reset from source to target.
2118 scorer.channel_liquidities.get_mut(&42).unwrap()
2119 .as_directed_mut(&source, &target, 0, 1_000, decay_params)
2120 .set_max_liquidity_msat(300);
2122 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2123 .as_directed(&source, &target, 0, 1_000, decay_params);
2124 assert_eq!(liquidity.min_liquidity_msat(), 0);
2125 assert_eq!(liquidity.max_liquidity_msat(), 300);
2127 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2128 .as_directed(&target, &source, 0, 1_000, decay_params);
2129 assert_eq!(liquidity.min_liquidity_msat(), 700);
2130 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2132 // Reset from target to source.
2133 scorer.channel_liquidities.get_mut(&42).unwrap()
2134 .as_directed_mut(&target, &source, 0, 1_000, decay_params)
2135 .set_max_liquidity_msat(600);
2137 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2138 .as_directed(&source, &target, 0, 1_000, decay_params);
2139 assert_eq!(liquidity.min_liquidity_msat(), 400);
2140 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2142 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2143 .as_directed(&target, &source, 0, 1_000, decay_params);
2144 assert_eq!(liquidity.min_liquidity_msat(), 0);
2145 assert_eq!(liquidity.max_liquidity_msat(), 600);
2149 fn increased_penalty_nearing_liquidity_upper_bound() {
2150 let logger = TestLogger::new();
2151 let network_graph = network_graph(&logger);
2152 let params = ProbabilisticScoringFeeParameters {
2153 liquidity_penalty_multiplier_msat: 1_000,
2154 ..ProbabilisticScoringFeeParameters::zero_penalty()
2156 let decay_params = ProbabilisticScoringDecayParameters::default();
2157 let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2158 let source = source_node_id();
2159 let target = target_node_id();
2161 let usage = ChannelUsage {
2163 inflight_htlc_msat: 0,
2164 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
2166 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2167 let usage = ChannelUsage { amount_msat: 10_240, ..usage };
2168 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2169 let usage = ChannelUsage { amount_msat: 102_400, ..usage };
2170 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 47);
2171 let usage = ChannelUsage { amount_msat: 1_023_999, ..usage };
2172 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2_000);
2174 let usage = ChannelUsage {
2176 inflight_htlc_msat: 0,
2177 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2179 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 58);
2180 let usage = ChannelUsage { amount_msat: 256, ..usage };
2181 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 125);
2182 let usage = ChannelUsage { amount_msat: 374, ..usage };
2183 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 198);
2184 let usage = ChannelUsage { amount_msat: 512, ..usage };
2185 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2186 let usage = ChannelUsage { amount_msat: 640, ..usage };
2187 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 425);
2188 let usage = ChannelUsage { amount_msat: 768, ..usage };
2189 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 602);
2190 let usage = ChannelUsage { amount_msat: 896, ..usage };
2191 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 902);
2195 fn constant_penalty_outside_liquidity_bounds() {
2196 let logger = TestLogger::new();
2197 let last_updated = SinceEpoch::now();
2198 let network_graph = network_graph(&logger);
2199 let params = ProbabilisticScoringFeeParameters {
2200 liquidity_penalty_multiplier_msat: 1_000,
2201 considered_impossible_penalty_msat: u64::max_value(),
2202 ..ProbabilisticScoringFeeParameters::zero_penalty()
2204 let decay_params = ProbabilisticScoringDecayParameters {
2205 ..ProbabilisticScoringDecayParameters::zero_penalty()
2207 let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2210 min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40, last_updated,
2211 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2212 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2214 let source = source_node_id();
2215 let target = target_node_id();
2217 let usage = ChannelUsage {
2219 inflight_htlc_msat: 0,
2220 effective_capacity: EffectiveCapacity::Total { capacity_msat: 100, htlc_maximum_msat: 1_000 },
2222 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2223 let usage = ChannelUsage { amount_msat: 50, ..usage };
2224 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2225 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2226 let usage = ChannelUsage { amount_msat: 61, ..usage };
2227 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2231 fn does_not_further_penalize_own_channel() {
2232 let logger = TestLogger::new();
2233 let network_graph = network_graph(&logger);
2234 let params = ProbabilisticScoringFeeParameters {
2235 liquidity_penalty_multiplier_msat: 1_000,
2236 ..ProbabilisticScoringFeeParameters::zero_penalty()
2238 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2239 let sender = sender_node_id();
2240 let source = source_node_id();
2241 let usage = ChannelUsage {
2243 inflight_htlc_msat: 0,
2244 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2246 let failed_path = payment_path_for_amount(500);
2247 let successful_path = payment_path_for_amount(200);
2249 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 301);
2251 scorer.payment_path_failed(&failed_path, 41);
2252 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 301);
2254 scorer.payment_path_successful(&successful_path);
2255 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 301);
2259 fn sets_liquidity_lower_bound_on_downstream_failure() {
2260 let logger = TestLogger::new();
2261 let network_graph = network_graph(&logger);
2262 let params = ProbabilisticScoringFeeParameters {
2263 liquidity_penalty_multiplier_msat: 1_000,
2264 ..ProbabilisticScoringFeeParameters::zero_penalty()
2266 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2267 let source = source_node_id();
2268 let target = target_node_id();
2269 let path = payment_path_for_amount(500);
2271 let usage = ChannelUsage {
2273 inflight_htlc_msat: 0,
2274 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2276 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 128);
2277 let usage = ChannelUsage { amount_msat: 500, ..usage };
2278 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 301);
2279 let usage = ChannelUsage { amount_msat: 750, ..usage };
2280 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 602);
2282 scorer.payment_path_failed(&path, 43);
2284 let usage = ChannelUsage { amount_msat: 250, ..usage };
2285 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2286 let usage = ChannelUsage { amount_msat: 500, ..usage };
2287 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2288 let usage = ChannelUsage { amount_msat: 750, ..usage };
2289 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2293 fn sets_liquidity_upper_bound_on_failure() {
2294 let logger = TestLogger::new();
2295 let network_graph = network_graph(&logger);
2296 let params = ProbabilisticScoringFeeParameters {
2297 liquidity_penalty_multiplier_msat: 1_000,
2298 considered_impossible_penalty_msat: u64::max_value(),
2299 ..ProbabilisticScoringFeeParameters::zero_penalty()
2301 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2302 let source = source_node_id();
2303 let target = target_node_id();
2304 let path = payment_path_for_amount(500);
2306 let usage = ChannelUsage {
2308 inflight_htlc_msat: 0,
2309 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2311 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 128);
2312 let usage = ChannelUsage { amount_msat: 500, ..usage };
2313 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 301);
2314 let usage = ChannelUsage { amount_msat: 750, ..usage };
2315 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 602);
2317 scorer.payment_path_failed(&path, 42);
2319 let usage = ChannelUsage { amount_msat: 250, ..usage };
2320 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2321 let usage = ChannelUsage { amount_msat: 500, ..usage };
2322 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2323 let usage = ChannelUsage { amount_msat: 750, ..usage };
2324 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2328 fn ignores_channels_after_removed_failed_channel() {
2329 // Previously, if we'd tried to send over a channel which was removed from the network
2330 // graph before we call `payment_path_failed` (which is the default if the we get a "no
2331 // such channel" error in the `InvoicePayer`), we would call `failed_downstream` on all
2332 // channels in the route, even ones which they payment never reached. This tests to ensure
2333 // we do not score such channels.
2334 let secp_ctx = Secp256k1::new();
2335 let logger = TestLogger::new();
2336 let mut network_graph = NetworkGraph::new(Network::Testnet, &logger);
2337 let secret_a = SecretKey::from_slice(&[42; 32]).unwrap();
2338 let secret_b = SecretKey::from_slice(&[43; 32]).unwrap();
2339 let secret_c = SecretKey::from_slice(&[44; 32]).unwrap();
2340 let secret_d = SecretKey::from_slice(&[45; 32]).unwrap();
2341 add_channel(&mut network_graph, 42, secret_a, secret_b);
2342 // Don't add the channel from B -> C.
2343 add_channel(&mut network_graph, 44, secret_c, secret_d);
2345 let pub_a = PublicKey::from_secret_key(&secp_ctx, &secret_a);
2346 let pub_b = PublicKey::from_secret_key(&secp_ctx, &secret_b);
2347 let pub_c = PublicKey::from_secret_key(&secp_ctx, &secret_c);
2348 let pub_d = PublicKey::from_secret_key(&secp_ctx, &secret_d);
2351 path_hop(pub_b, 42, 1),
2352 path_hop(pub_c, 43, 2),
2353 path_hop(pub_d, 44, 100),
2356 let node_a = NodeId::from_pubkey(&pub_a);
2357 let node_b = NodeId::from_pubkey(&pub_b);
2358 let node_c = NodeId::from_pubkey(&pub_c);
2359 let node_d = NodeId::from_pubkey(&pub_d);
2361 let params = ProbabilisticScoringFeeParameters {
2362 liquidity_penalty_multiplier_msat: 1_000,
2363 ..ProbabilisticScoringFeeParameters::zero_penalty()
2365 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2367 let usage = ChannelUsage {
2369 inflight_htlc_msat: 0,
2370 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2372 assert_eq!(scorer.channel_penalty_msat(42, &node_a, &node_b, usage, ¶ms), 128);
2373 // Note that a default liquidity bound is used for B -> C as no channel exists
2374 assert_eq!(scorer.channel_penalty_msat(43, &node_b, &node_c, usage, ¶ms), 128);
2375 assert_eq!(scorer.channel_penalty_msat(44, &node_c, &node_d, usage, ¶ms), 128);
2377 scorer.payment_path_failed(&Path { hops: path, blinded_tail: None }, 43);
2379 assert_eq!(scorer.channel_penalty_msat(42, &node_a, &node_b, usage, ¶ms), 80);
2380 // Note that a default liquidity bound is used for B -> C as no channel exists
2381 assert_eq!(scorer.channel_penalty_msat(43, &node_b, &node_c, usage, ¶ms), 128);
2382 assert_eq!(scorer.channel_penalty_msat(44, &node_c, &node_d, usage, ¶ms), 128);
2386 fn reduces_liquidity_upper_bound_along_path_on_success() {
2387 let logger = TestLogger::new();
2388 let network_graph = network_graph(&logger);
2389 let params = ProbabilisticScoringFeeParameters {
2390 liquidity_penalty_multiplier_msat: 1_000,
2391 ..ProbabilisticScoringFeeParameters::zero_penalty()
2393 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2394 let sender = sender_node_id();
2395 let source = source_node_id();
2396 let target = target_node_id();
2397 let recipient = recipient_node_id();
2398 let usage = ChannelUsage {
2400 inflight_htlc_msat: 0,
2401 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2404 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 128);
2405 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 128);
2406 assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage, ¶ms), 128);
2408 scorer.payment_path_successful(&payment_path_for_amount(500));
2410 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 128);
2411 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2412 assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage, ¶ms), 300);
2416 fn decays_liquidity_bounds_over_time() {
2417 let logger = TestLogger::new();
2418 let network_graph = network_graph(&logger);
2419 let params = ProbabilisticScoringFeeParameters {
2420 liquidity_penalty_multiplier_msat: 1_000,
2421 considered_impossible_penalty_msat: u64::max_value(),
2422 ..ProbabilisticScoringFeeParameters::zero_penalty()
2424 let decay_params = ProbabilisticScoringDecayParameters {
2425 liquidity_offset_half_life: Duration::from_secs(10),
2426 ..ProbabilisticScoringDecayParameters::zero_penalty()
2428 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2429 let source = source_node_id();
2430 let target = target_node_id();
2432 let usage = ChannelUsage {
2434 inflight_htlc_msat: 0,
2435 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
2437 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2438 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
2439 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2_000);
2441 scorer.payment_path_failed(&payment_path_for_amount(768), 42);
2442 scorer.payment_path_failed(&payment_path_for_amount(128), 43);
2444 let usage = ChannelUsage { amount_msat: 128, ..usage };
2445 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2446 let usage = ChannelUsage { amount_msat: 256, ..usage };
2447 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 93);
2448 let usage = ChannelUsage { amount_msat: 768, ..usage };
2449 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1_479);
2450 let usage = ChannelUsage { amount_msat: 896, ..usage };
2451 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2453 SinceEpoch::advance(Duration::from_secs(9));
2454 let usage = ChannelUsage { amount_msat: 128, ..usage };
2455 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2456 let usage = ChannelUsage { amount_msat: 256, ..usage };
2457 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 93);
2458 let usage = ChannelUsage { amount_msat: 768, ..usage };
2459 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1_479);
2460 let usage = ChannelUsage { amount_msat: 896, ..usage };
2461 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2463 SinceEpoch::advance(Duration::from_secs(1));
2464 let usage = ChannelUsage { amount_msat: 64, ..usage };
2465 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2466 let usage = ChannelUsage { amount_msat: 128, ..usage };
2467 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 34);
2468 let usage = ChannelUsage { amount_msat: 896, ..usage };
2469 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1_970);
2470 let usage = ChannelUsage { amount_msat: 960, ..usage };
2471 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2473 // Fully decay liquidity lower bound.
2474 SinceEpoch::advance(Duration::from_secs(10 * 7));
2475 let usage = ChannelUsage { amount_msat: 0, ..usage };
2476 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2477 let usage = ChannelUsage { amount_msat: 1, ..usage };
2478 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2479 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
2480 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2_000);
2481 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2482 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2484 // Fully decay liquidity upper bound.
2485 SinceEpoch::advance(Duration::from_secs(10));
2486 let usage = ChannelUsage { amount_msat: 0, ..usage };
2487 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2488 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2489 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2491 SinceEpoch::advance(Duration::from_secs(10));
2492 let usage = ChannelUsage { amount_msat: 0, ..usage };
2493 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2494 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2495 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2499 fn decays_liquidity_bounds_without_shift_overflow() {
2500 let logger = TestLogger::new();
2501 let network_graph = network_graph(&logger);
2502 let params = ProbabilisticScoringFeeParameters {
2503 liquidity_penalty_multiplier_msat: 1_000,
2504 ..ProbabilisticScoringFeeParameters::zero_penalty()
2506 let decay_params = ProbabilisticScoringDecayParameters {
2507 liquidity_offset_half_life: Duration::from_secs(10),
2508 ..ProbabilisticScoringDecayParameters::default()
2510 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2511 let source = source_node_id();
2512 let target = target_node_id();
2513 let usage = ChannelUsage {
2515 inflight_htlc_msat: 0,
2516 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2518 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 125);
2520 scorer.payment_path_failed(&payment_path_for_amount(512), 42);
2521 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 281);
2523 // An unchecked right shift 64 bits or more in DirectedChannelLiquidity::decayed_offset_msat
2524 // would cause an overflow.
2525 SinceEpoch::advance(Duration::from_secs(10 * 64));
2526 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 125);
2528 SinceEpoch::advance(Duration::from_secs(10));
2529 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 125);
2533 fn restricts_liquidity_bounds_after_decay() {
2534 let logger = TestLogger::new();
2535 let network_graph = network_graph(&logger);
2536 let params = ProbabilisticScoringFeeParameters {
2537 liquidity_penalty_multiplier_msat: 1_000,
2538 ..ProbabilisticScoringFeeParameters::zero_penalty()
2540 let decay_params = ProbabilisticScoringDecayParameters {
2541 liquidity_offset_half_life: Duration::from_secs(10),
2542 ..ProbabilisticScoringDecayParameters::default()
2544 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2545 let source = source_node_id();
2546 let target = target_node_id();
2547 let usage = ChannelUsage {
2549 inflight_htlc_msat: 0,
2550 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2553 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2555 // More knowledge gives higher confidence (256, 768), meaning a lower penalty.
2556 scorer.payment_path_failed(&payment_path_for_amount(768), 42);
2557 scorer.payment_path_failed(&payment_path_for_amount(256), 43);
2558 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 281);
2560 // Decaying knowledge gives less confidence (128, 896), meaning a higher penalty.
2561 SinceEpoch::advance(Duration::from_secs(10));
2562 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 291);
2564 // Reducing the upper bound gives more confidence (128, 832) that the payment amount (512)
2565 // is closer to the upper bound, meaning a higher penalty.
2566 scorer.payment_path_successful(&payment_path_for_amount(64));
2567 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 331);
2569 // Increasing the lower bound gives more confidence (256, 832) that the payment amount (512)
2570 // is closer to the lower bound, meaning a lower penalty.
2571 scorer.payment_path_failed(&payment_path_for_amount(256), 43);
2572 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 245);
2574 // Further decaying affects the lower bound more than the upper bound (128, 928).
2575 SinceEpoch::advance(Duration::from_secs(10));
2576 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 280);
2580 fn restores_persisted_liquidity_bounds() {
2581 let logger = TestLogger::new();
2582 let network_graph = network_graph(&logger);
2583 let params = ProbabilisticScoringFeeParameters {
2584 liquidity_penalty_multiplier_msat: 1_000,
2585 considered_impossible_penalty_msat: u64::max_value(),
2586 ..ProbabilisticScoringFeeParameters::zero_penalty()
2588 let decay_params = ProbabilisticScoringDecayParameters {
2589 liquidity_offset_half_life: Duration::from_secs(10),
2590 ..ProbabilisticScoringDecayParameters::default()
2592 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2593 let source = source_node_id();
2594 let target = target_node_id();
2595 let usage = ChannelUsage {
2597 inflight_htlc_msat: 0,
2598 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2601 scorer.payment_path_failed(&payment_path_for_amount(500), 42);
2602 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2604 SinceEpoch::advance(Duration::from_secs(10));
2605 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 473);
2607 scorer.payment_path_failed(&payment_path_for_amount(250), 43);
2608 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2610 let mut serialized_scorer = Vec::new();
2611 scorer.write(&mut serialized_scorer).unwrap();
2613 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
2614 let deserialized_scorer =
2615 <ProbabilisticScorer>::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap();
2616 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2620 fn decays_persisted_liquidity_bounds() {
2621 let logger = TestLogger::new();
2622 let network_graph = network_graph(&logger);
2623 let params = ProbabilisticScoringFeeParameters {
2624 liquidity_penalty_multiplier_msat: 1_000,
2625 considered_impossible_penalty_msat: u64::max_value(),
2626 ..ProbabilisticScoringFeeParameters::zero_penalty()
2628 let decay_params = ProbabilisticScoringDecayParameters {
2629 liquidity_offset_half_life: Duration::from_secs(10),
2630 ..ProbabilisticScoringDecayParameters::zero_penalty()
2632 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2633 let source = source_node_id();
2634 let target = target_node_id();
2635 let usage = ChannelUsage {
2637 inflight_htlc_msat: 0,
2638 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2641 scorer.payment_path_failed(&payment_path_for_amount(500), 42);
2642 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2644 let mut serialized_scorer = Vec::new();
2645 scorer.write(&mut serialized_scorer).unwrap();
2647 SinceEpoch::advance(Duration::from_secs(10));
2649 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
2650 let deserialized_scorer =
2651 <ProbabilisticScorer>::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap();
2652 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 473);
2654 scorer.payment_path_failed(&payment_path_for_amount(250), 43);
2655 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2657 SinceEpoch::advance(Duration::from_secs(10));
2658 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 365);
2662 fn scores_realistic_payments() {
2663 // Shows the scores of "realistic" sends of 100k sats over channels of 1-10m sats (with a
2664 // 50k sat reserve).
2665 let logger = TestLogger::new();
2666 let network_graph = network_graph(&logger);
2667 let params = ProbabilisticScoringFeeParameters::default();
2668 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2669 let source = source_node_id();
2670 let target = target_node_id();
2672 let usage = ChannelUsage {
2673 amount_msat: 100_000_000,
2674 inflight_htlc_msat: 0,
2675 effective_capacity: EffectiveCapacity::Total { capacity_msat: 950_000_000, htlc_maximum_msat: 1_000 },
2677 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 4375);
2678 let usage = ChannelUsage {
2679 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2681 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2739);
2682 let usage = ChannelUsage {
2683 effective_capacity: EffectiveCapacity::Total { capacity_msat: 2_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2685 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2236);
2686 let usage = ChannelUsage {
2687 effective_capacity: EffectiveCapacity::Total { capacity_msat: 3_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2689 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1983);
2690 let usage = ChannelUsage {
2691 effective_capacity: EffectiveCapacity::Total { capacity_msat: 4_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2693 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1637);
2694 let usage = ChannelUsage {
2695 effective_capacity: EffectiveCapacity::Total { capacity_msat: 5_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2697 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1606);
2698 let usage = ChannelUsage {
2699 effective_capacity: EffectiveCapacity::Total { capacity_msat: 6_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2701 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1331);
2702 let usage = ChannelUsage {
2703 effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_450_000_000, htlc_maximum_msat: 1_000 }, ..usage
2705 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1387);
2706 let usage = ChannelUsage {
2707 effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2709 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1379);
2710 let usage = ChannelUsage {
2711 effective_capacity: EffectiveCapacity::Total { capacity_msat: 8_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2713 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1363);
2714 let usage = ChannelUsage {
2715 effective_capacity: EffectiveCapacity::Total { capacity_msat: 9_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2717 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1355);
2721 fn adds_base_penalty_to_liquidity_penalty() {
2722 let logger = TestLogger::new();
2723 let network_graph = network_graph(&logger);
2724 let source = source_node_id();
2725 let target = target_node_id();
2726 let usage = ChannelUsage {
2728 inflight_htlc_msat: 0,
2729 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2732 let params = ProbabilisticScoringFeeParameters {
2733 liquidity_penalty_multiplier_msat: 1_000,
2734 ..ProbabilisticScoringFeeParameters::zero_penalty()
2736 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2737 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 58);
2739 let params = ProbabilisticScoringFeeParameters {
2740 base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000,
2741 anti_probing_penalty_msat: 0, ..ProbabilisticScoringFeeParameters::zero_penalty()
2743 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2744 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 558);
2746 let params = ProbabilisticScoringFeeParameters {
2747 base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000,
2748 base_penalty_amount_multiplier_msat: (1 << 30),
2749 anti_probing_penalty_msat: 0, ..ProbabilisticScoringFeeParameters::zero_penalty()
2752 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2753 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 558 + 128);
2757 fn adds_amount_penalty_to_liquidity_penalty() {
2758 let logger = TestLogger::new();
2759 let network_graph = network_graph(&logger);
2760 let source = source_node_id();
2761 let target = target_node_id();
2762 let usage = ChannelUsage {
2763 amount_msat: 512_000,
2764 inflight_htlc_msat: 0,
2765 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
2768 let params = ProbabilisticScoringFeeParameters {
2769 liquidity_penalty_multiplier_msat: 1_000,
2770 liquidity_penalty_amount_multiplier_msat: 0,
2771 ..ProbabilisticScoringFeeParameters::zero_penalty()
2773 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2774 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2776 let params = ProbabilisticScoringFeeParameters {
2777 liquidity_penalty_multiplier_msat: 1_000,
2778 liquidity_penalty_amount_multiplier_msat: 256,
2779 ..ProbabilisticScoringFeeParameters::zero_penalty()
2781 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2782 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 337);
2786 fn calculates_log10_without_overflowing_u64_max_value() {
2787 let logger = TestLogger::new();
2788 let network_graph = network_graph(&logger);
2789 let source = source_node_id();
2790 let target = target_node_id();
2791 let usage = ChannelUsage {
2792 amount_msat: u64::max_value(),
2793 inflight_htlc_msat: 0,
2794 effective_capacity: EffectiveCapacity::Infinite,
2797 let params = ProbabilisticScoringFeeParameters {
2798 liquidity_penalty_multiplier_msat: 40_000,
2799 ..ProbabilisticScoringFeeParameters::zero_penalty()
2801 let decay_params = ProbabilisticScoringDecayParameters::zero_penalty();
2802 let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2803 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 80_000);
2807 fn accounts_for_inflight_htlc_usage() {
2808 let logger = TestLogger::new();
2809 let network_graph = network_graph(&logger);
2810 let params = ProbabilisticScoringFeeParameters {
2811 considered_impossible_penalty_msat: u64::max_value(),
2812 ..ProbabilisticScoringFeeParameters::zero_penalty()
2814 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2815 let source = source_node_id();
2816 let target = target_node_id();
2818 let usage = ChannelUsage {
2820 inflight_htlc_msat: 0,
2821 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2823 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2825 let usage = ChannelUsage { inflight_htlc_msat: 251, ..usage };
2826 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2830 fn removes_uncertainity_when_exact_liquidity_known() {
2831 let logger = TestLogger::new();
2832 let network_graph = network_graph(&logger);
2833 let params = ProbabilisticScoringFeeParameters::default();
2834 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2835 let source = source_node_id();
2836 let target = target_node_id();
2838 let base_penalty_msat = params.base_penalty_msat;
2839 let usage = ChannelUsage {
2841 inflight_htlc_msat: 0,
2842 effective_capacity: EffectiveCapacity::ExactLiquidity { liquidity_msat: 1_000 },
2844 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), base_penalty_msat);
2846 let usage = ChannelUsage { amount_msat: 1_000, ..usage };
2847 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), base_penalty_msat);
2849 let usage = ChannelUsage { amount_msat: 1_001, ..usage };
2850 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2854 fn remembers_historical_failures() {
2855 let logger = TestLogger::new();
2856 let network_graph = network_graph(&logger);
2857 let params = ProbabilisticScoringFeeParameters {
2858 historical_liquidity_penalty_multiplier_msat: 1024,
2859 historical_liquidity_penalty_amount_multiplier_msat: 1024,
2860 ..ProbabilisticScoringFeeParameters::zero_penalty()
2862 let decay_params = ProbabilisticScoringDecayParameters {
2863 liquidity_offset_half_life: Duration::from_secs(60 * 60),
2864 historical_no_updates_half_life: Duration::from_secs(10),
2866 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2867 let source = source_node_id();
2868 let target = target_node_id();
2870 let usage = ChannelUsage {
2872 inflight_htlc_msat: 0,
2873 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
2875 // With no historical data the normal liquidity penalty calculation is used.
2876 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 47);
2877 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
2879 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 42),
2882 scorer.payment_path_failed(&payment_path_for_amount(1), 42);
2883 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2048);
2884 // The "it failed" increment is 32, where the probability should lie fully in the first
2886 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
2887 Some(([32, 0, 0, 0, 0, 0, 0, 0], [32, 0, 0, 0, 0, 0, 0, 0])));
2888 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 1),
2890 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 500),
2893 // Even after we tell the scorer we definitely have enough available liquidity, it will
2894 // still remember that there was some failure in the past, and assign a non-0 penalty.
2895 scorer.payment_path_failed(&payment_path_for_amount(1000), 43);
2896 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 198);
2897 // The first octile should be decayed just slightly and the last octile has a new point.
2898 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
2899 Some(([31, 0, 0, 0, 0, 0, 0, 32], [31, 0, 0, 0, 0, 0, 0, 32])));
2901 // The exact success probability is a bit complicated and involves integer rounding, so we
2902 // simply check bounds here.
2903 let five_hundred_prob =
2904 scorer.historical_estimated_payment_success_probability(42, &target, 500).unwrap();
2905 assert!(five_hundred_prob > 0.5);
2906 assert!(five_hundred_prob < 0.52);
2908 scorer.historical_estimated_payment_success_probability(42, &target, 1).unwrap();
2909 assert!(one_prob < 1.0);
2910 assert!(one_prob > 0.99);
2912 // Advance the time forward 16 half-lives (which the docs claim will ensure all data is
2913 // gone), and check that we're back to where we started.
2914 SinceEpoch::advance(Duration::from_secs(10 * 16));
2915 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 47);
2916 // Once fully decayed we still have data, but its all-0s. In the future we may remove the
2917 // data entirely instead.
2918 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
2919 Some(([0; 8], [0; 8])));
2920 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 1), None);
2922 let mut usage = ChannelUsage {
2924 inflight_htlc_msat: 1024,
2925 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
2927 scorer.payment_path_failed(&payment_path_for_amount(1), 42);
2928 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2048);
2929 usage.inflight_htlc_msat = 0;
2930 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 409);
2932 let usage = ChannelUsage {
2934 inflight_htlc_msat: 0,
2935 effective_capacity: EffectiveCapacity::MaximumHTLC { amount_msat: 0 },
2937 assert_eq!(scorer.channel_penalty_msat(42, &target, &source, usage, ¶ms), 2048);
2939 // Advance to decay all liquidity offsets to zero.
2940 SinceEpoch::advance(Duration::from_secs(60 * 60 * 10));
2942 // Use a path in the opposite direction, which have zero for htlc_maximum_msat. This will
2943 // ensure that the effective capacity is zero to test division-by-zero edge cases.
2945 path_hop(target_pubkey(), 43, 2),
2946 path_hop(source_pubkey(), 42, 1),
2947 path_hop(sender_pubkey(), 41, 0),
2949 scorer.payment_path_failed(&Path { hops: path, blinded_tail: None }, 42);
2953 fn adds_anti_probing_penalty() {
2954 let logger = TestLogger::new();
2955 let network_graph = network_graph(&logger);
2956 let source = source_node_id();
2957 let target = target_node_id();
2958 let params = ProbabilisticScoringFeeParameters {
2959 anti_probing_penalty_msat: 500,
2960 ..ProbabilisticScoringFeeParameters::zero_penalty()
2962 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2964 // Check we receive no penalty for a low htlc_maximum_msat.
2965 let usage = ChannelUsage {
2966 amount_msat: 512_000,
2967 inflight_htlc_msat: 0,
2968 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
2970 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2972 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity.
2973 let usage = ChannelUsage {
2974 amount_msat: 512_000,
2975 inflight_htlc_msat: 0,
2976 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_024_000 },
2978 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 500);
2980 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity/2.
2981 let usage = ChannelUsage {
2982 amount_msat: 512_000,
2983 inflight_htlc_msat: 0,
2984 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 512_000 },
2986 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 500);
2988 // Check we receive no anti-probing penalty for htlc_maximum_msat == channel_capacity/2 - 1.
2989 let usage = ChannelUsage {
2990 amount_msat: 512_000,
2991 inflight_htlc_msat: 0,
2992 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 511_999 },
2994 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2998 fn scores_with_blinded_path() {
2999 // Make sure we'll account for a blinded path's final_value_msat in scoring
3000 let logger = TestLogger::new();
3001 let network_graph = network_graph(&logger);
3002 let params = ProbabilisticScoringFeeParameters {
3003 liquidity_penalty_multiplier_msat: 1_000,
3004 ..ProbabilisticScoringFeeParameters::zero_penalty()
3006 let decay_params = ProbabilisticScoringDecayParameters::default();
3007 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3008 let source = source_node_id();
3009 let target = target_node_id();
3010 let usage = ChannelUsage {
3012 inflight_htlc_msat: 0,
3013 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
3015 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
3017 let mut path = payment_path_for_amount(768);
3018 let recipient_hop = path.hops.pop().unwrap();
3019 let blinded_path = BlindedPath {
3020 introduction_node_id: path.hops.last().as_ref().unwrap().pubkey,
3021 blinding_point: test_utils::pubkey(42),
3023 BlindedHop { blinded_node_id: test_utils::pubkey(44), encrypted_payload: Vec::new() }
3026 path.blinded_tail = Some(BlindedTail {
3027 hops: blinded_path.blinded_hops,
3028 blinding_point: blinded_path.blinding_point,
3029 excess_final_cltv_expiry_delta: recipient_hop.cltv_expiry_delta,
3030 final_value_msat: recipient_hop.fee_msat,
3033 // Check the liquidity before and after scoring payment failures to ensure the blinded path's
3034 // final value is taken into account.
3035 assert!(scorer.channel_liquidities.get(&42).is_none());
3037 scorer.payment_path_failed(&path, 42);
3038 path.blinded_tail.as_mut().unwrap().final_value_msat = 256;
3039 scorer.payment_path_failed(&path, 43);
3041 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
3042 .as_directed(&source, &target, 0, 1_000, decay_params);
3043 assert_eq!(liquidity.min_liquidity_msat(), 256);
3044 assert_eq!(liquidity.max_liquidity_msat(), 768);