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