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,
2020 fn payment_path_for_amount(amount_msat: u64) -> Path {
2023 path_hop(source_pubkey(), 41, 1),
2024 path_hop(target_pubkey(), 42, 2),
2025 path_hop(recipient_pubkey(), 43, amount_msat),
2026 ], blinded_tail: None,
2031 fn liquidity_bounds_directed_from_lowest_node_id() {
2032 let logger = TestLogger::new();
2033 let last_updated = SinceEpoch::now();
2034 let network_graph = network_graph(&logger);
2035 let decay_params = ProbabilisticScoringDecayParameters::default();
2036 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2039 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated,
2040 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2041 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2045 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated,
2046 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2047 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2049 let source = source_node_id();
2050 let target = target_node_id();
2051 let recipient = recipient_node_id();
2052 assert!(source > target);
2053 assert!(target < recipient);
2055 // Update minimum liquidity.
2057 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2058 .as_directed(&source, &target, 0, 1_000, decay_params);
2059 assert_eq!(liquidity.min_liquidity_msat(), 100);
2060 assert_eq!(liquidity.max_liquidity_msat(), 300);
2062 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2063 .as_directed(&target, &source, 0, 1_000, decay_params);
2064 assert_eq!(liquidity.min_liquidity_msat(), 700);
2065 assert_eq!(liquidity.max_liquidity_msat(), 900);
2067 scorer.channel_liquidities.get_mut(&42).unwrap()
2068 .as_directed_mut(&source, &target, 0, 1_000, decay_params)
2069 .set_min_liquidity_msat(200);
2071 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2072 .as_directed(&source, &target, 0, 1_000, decay_params);
2073 assert_eq!(liquidity.min_liquidity_msat(), 200);
2074 assert_eq!(liquidity.max_liquidity_msat(), 300);
2076 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2077 .as_directed(&target, &source, 0, 1_000, decay_params);
2078 assert_eq!(liquidity.min_liquidity_msat(), 700);
2079 assert_eq!(liquidity.max_liquidity_msat(), 800);
2081 // Update maximum liquidity.
2083 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2084 .as_directed(&target, &recipient, 0, 1_000, decay_params);
2085 assert_eq!(liquidity.min_liquidity_msat(), 700);
2086 assert_eq!(liquidity.max_liquidity_msat(), 900);
2088 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2089 .as_directed(&recipient, &target, 0, 1_000, decay_params);
2090 assert_eq!(liquidity.min_liquidity_msat(), 100);
2091 assert_eq!(liquidity.max_liquidity_msat(), 300);
2093 scorer.channel_liquidities.get_mut(&43).unwrap()
2094 .as_directed_mut(&target, &recipient, 0, 1_000, decay_params)
2095 .set_max_liquidity_msat(200);
2097 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2098 .as_directed(&target, &recipient, 0, 1_000, decay_params);
2099 assert_eq!(liquidity.min_liquidity_msat(), 0);
2100 assert_eq!(liquidity.max_liquidity_msat(), 200);
2102 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2103 .as_directed(&recipient, &target, 0, 1_000, decay_params);
2104 assert_eq!(liquidity.min_liquidity_msat(), 800);
2105 assert_eq!(liquidity.max_liquidity_msat(), 1000);
2109 fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() {
2110 let logger = TestLogger::new();
2111 let last_updated = SinceEpoch::now();
2112 let network_graph = network_graph(&logger);
2113 let decay_params = ProbabilisticScoringDecayParameters::default();
2114 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2117 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated,
2118 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2119 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2121 let source = source_node_id();
2122 let target = target_node_id();
2123 assert!(source > target);
2125 // Check initial bounds.
2126 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2127 .as_directed(&source, &target, 0, 1_000, decay_params);
2128 assert_eq!(liquidity.min_liquidity_msat(), 400);
2129 assert_eq!(liquidity.max_liquidity_msat(), 800);
2131 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2132 .as_directed(&target, &source, 0, 1_000, decay_params);
2133 assert_eq!(liquidity.min_liquidity_msat(), 200);
2134 assert_eq!(liquidity.max_liquidity_msat(), 600);
2136 // Reset from source to target.
2137 scorer.channel_liquidities.get_mut(&42).unwrap()
2138 .as_directed_mut(&source, &target, 0, 1_000, decay_params)
2139 .set_min_liquidity_msat(900);
2141 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2142 .as_directed(&source, &target, 0, 1_000, decay_params);
2143 assert_eq!(liquidity.min_liquidity_msat(), 900);
2144 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2146 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2147 .as_directed(&target, &source, 0, 1_000, decay_params);
2148 assert_eq!(liquidity.min_liquidity_msat(), 0);
2149 assert_eq!(liquidity.max_liquidity_msat(), 100);
2151 // Reset from target to source.
2152 scorer.channel_liquidities.get_mut(&42).unwrap()
2153 .as_directed_mut(&target, &source, 0, 1_000, decay_params)
2154 .set_min_liquidity_msat(400);
2156 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2157 .as_directed(&source, &target, 0, 1_000, decay_params);
2158 assert_eq!(liquidity.min_liquidity_msat(), 0);
2159 assert_eq!(liquidity.max_liquidity_msat(), 600);
2161 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2162 .as_directed(&target, &source, 0, 1_000, decay_params);
2163 assert_eq!(liquidity.min_liquidity_msat(), 400);
2164 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2168 fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() {
2169 let logger = TestLogger::new();
2170 let last_updated = SinceEpoch::now();
2171 let network_graph = network_graph(&logger);
2172 let decay_params = ProbabilisticScoringDecayParameters::default();
2173 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2176 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated,
2177 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2178 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2180 let source = source_node_id();
2181 let target = target_node_id();
2182 assert!(source > target);
2184 // Check initial bounds.
2185 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2186 .as_directed(&source, &target, 0, 1_000, decay_params);
2187 assert_eq!(liquidity.min_liquidity_msat(), 400);
2188 assert_eq!(liquidity.max_liquidity_msat(), 800);
2190 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2191 .as_directed(&target, &source, 0, 1_000, decay_params);
2192 assert_eq!(liquidity.min_liquidity_msat(), 200);
2193 assert_eq!(liquidity.max_liquidity_msat(), 600);
2195 // Reset from source to target.
2196 scorer.channel_liquidities.get_mut(&42).unwrap()
2197 .as_directed_mut(&source, &target, 0, 1_000, decay_params)
2198 .set_max_liquidity_msat(300);
2200 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2201 .as_directed(&source, &target, 0, 1_000, decay_params);
2202 assert_eq!(liquidity.min_liquidity_msat(), 0);
2203 assert_eq!(liquidity.max_liquidity_msat(), 300);
2205 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2206 .as_directed(&target, &source, 0, 1_000, decay_params);
2207 assert_eq!(liquidity.min_liquidity_msat(), 700);
2208 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2210 // Reset from target to source.
2211 scorer.channel_liquidities.get_mut(&42).unwrap()
2212 .as_directed_mut(&target, &source, 0, 1_000, decay_params)
2213 .set_max_liquidity_msat(600);
2215 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2216 .as_directed(&source, &target, 0, 1_000, decay_params);
2217 assert_eq!(liquidity.min_liquidity_msat(), 400);
2218 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2220 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2221 .as_directed(&target, &source, 0, 1_000, decay_params);
2222 assert_eq!(liquidity.min_liquidity_msat(), 0);
2223 assert_eq!(liquidity.max_liquidity_msat(), 600);
2227 fn increased_penalty_nearing_liquidity_upper_bound() {
2228 let logger = TestLogger::new();
2229 let network_graph = network_graph(&logger);
2230 let params = ProbabilisticScoringFeeParameters {
2231 liquidity_penalty_multiplier_msat: 1_000,
2232 ..ProbabilisticScoringFeeParameters::zero_penalty()
2234 let decay_params = ProbabilisticScoringDecayParameters::default();
2235 let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2236 let source = source_node_id();
2237 let target = target_node_id();
2239 let usage = ChannelUsage {
2241 inflight_htlc_msat: 0,
2242 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
2244 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2245 let usage = ChannelUsage { amount_msat: 10_240, ..usage };
2246 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2247 let usage = ChannelUsage { amount_msat: 102_400, ..usage };
2248 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 47);
2249 let usage = ChannelUsage { amount_msat: 1_023_999, ..usage };
2250 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2_000);
2252 let usage = ChannelUsage {
2254 inflight_htlc_msat: 0,
2255 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2257 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 58);
2258 let usage = ChannelUsage { amount_msat: 256, ..usage };
2259 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 125);
2260 let usage = ChannelUsage { amount_msat: 374, ..usage };
2261 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 198);
2262 let usage = ChannelUsage { amount_msat: 512, ..usage };
2263 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2264 let usage = ChannelUsage { amount_msat: 640, ..usage };
2265 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 425);
2266 let usage = ChannelUsage { amount_msat: 768, ..usage };
2267 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 602);
2268 let usage = ChannelUsage { amount_msat: 896, ..usage };
2269 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 902);
2273 fn constant_penalty_outside_liquidity_bounds() {
2274 let logger = TestLogger::new();
2275 let last_updated = SinceEpoch::now();
2276 let network_graph = network_graph(&logger);
2277 let params = ProbabilisticScoringFeeParameters {
2278 liquidity_penalty_multiplier_msat: 1_000,
2279 considered_impossible_penalty_msat: u64::max_value(),
2280 ..ProbabilisticScoringFeeParameters::zero_penalty()
2282 let decay_params = ProbabilisticScoringDecayParameters {
2283 ..ProbabilisticScoringDecayParameters::zero_penalty()
2285 let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2288 min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40, last_updated,
2289 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2290 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2292 let source = source_node_id();
2293 let target = target_node_id();
2295 let usage = ChannelUsage {
2297 inflight_htlc_msat: 0,
2298 effective_capacity: EffectiveCapacity::Total { capacity_msat: 100, htlc_maximum_msat: 1_000 },
2300 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2301 let usage = ChannelUsage { amount_msat: 50, ..usage };
2302 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2303 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2304 let usage = ChannelUsage { amount_msat: 61, ..usage };
2305 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2309 fn does_not_further_penalize_own_channel() {
2310 let logger = TestLogger::new();
2311 let network_graph = network_graph(&logger);
2312 let params = ProbabilisticScoringFeeParameters {
2313 liquidity_penalty_multiplier_msat: 1_000,
2314 ..ProbabilisticScoringFeeParameters::zero_penalty()
2316 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2317 let sender = sender_node_id();
2318 let source = source_node_id();
2319 let usage = ChannelUsage {
2321 inflight_htlc_msat: 0,
2322 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2324 let failed_path = payment_path_for_amount(500);
2325 let successful_path = payment_path_for_amount(200);
2327 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 301);
2329 scorer.payment_path_failed(&failed_path, 41);
2330 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 301);
2332 scorer.payment_path_successful(&successful_path);
2333 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 301);
2337 fn sets_liquidity_lower_bound_on_downstream_failure() {
2338 let logger = TestLogger::new();
2339 let network_graph = network_graph(&logger);
2340 let params = ProbabilisticScoringFeeParameters {
2341 liquidity_penalty_multiplier_msat: 1_000,
2342 ..ProbabilisticScoringFeeParameters::zero_penalty()
2344 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2345 let source = source_node_id();
2346 let target = target_node_id();
2347 let path = payment_path_for_amount(500);
2349 let usage = ChannelUsage {
2351 inflight_htlc_msat: 0,
2352 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2354 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 128);
2355 let usage = ChannelUsage { amount_msat: 500, ..usage };
2356 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 301);
2357 let usage = ChannelUsage { amount_msat: 750, ..usage };
2358 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 602);
2360 scorer.payment_path_failed(&path, 43);
2362 let usage = ChannelUsage { amount_msat: 250, ..usage };
2363 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2364 let usage = ChannelUsage { amount_msat: 500, ..usage };
2365 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2366 let usage = ChannelUsage { amount_msat: 750, ..usage };
2367 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2371 fn sets_liquidity_upper_bound_on_failure() {
2372 let logger = TestLogger::new();
2373 let network_graph = network_graph(&logger);
2374 let params = ProbabilisticScoringFeeParameters {
2375 liquidity_penalty_multiplier_msat: 1_000,
2376 considered_impossible_penalty_msat: u64::max_value(),
2377 ..ProbabilisticScoringFeeParameters::zero_penalty()
2379 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2380 let source = source_node_id();
2381 let target = target_node_id();
2382 let path = payment_path_for_amount(500);
2384 let usage = ChannelUsage {
2386 inflight_htlc_msat: 0,
2387 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2389 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 128);
2390 let usage = ChannelUsage { amount_msat: 500, ..usage };
2391 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 301);
2392 let usage = ChannelUsage { amount_msat: 750, ..usage };
2393 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 602);
2395 scorer.payment_path_failed(&path, 42);
2397 let usage = ChannelUsage { amount_msat: 250, ..usage };
2398 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2399 let usage = ChannelUsage { amount_msat: 500, ..usage };
2400 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2401 let usage = ChannelUsage { amount_msat: 750, ..usage };
2402 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2406 fn ignores_channels_after_removed_failed_channel() {
2407 // Previously, if we'd tried to send over a channel which was removed from the network
2408 // graph before we call `payment_path_failed` (which is the default if the we get a "no
2409 // such channel" error in the `InvoicePayer`), we would call `failed_downstream` on all
2410 // channels in the route, even ones which they payment never reached. This tests to ensure
2411 // we do not score such channels.
2412 let secp_ctx = Secp256k1::new();
2413 let logger = TestLogger::new();
2414 let mut network_graph = NetworkGraph::new(Network::Testnet, &logger);
2415 let secret_a = SecretKey::from_slice(&[42; 32]).unwrap();
2416 let secret_b = SecretKey::from_slice(&[43; 32]).unwrap();
2417 let secret_c = SecretKey::from_slice(&[44; 32]).unwrap();
2418 let secret_d = SecretKey::from_slice(&[45; 32]).unwrap();
2419 add_channel(&mut network_graph, 42, secret_a, secret_b);
2420 // Don't add the channel from B -> C.
2421 add_channel(&mut network_graph, 44, secret_c, secret_d);
2423 let pub_a = PublicKey::from_secret_key(&secp_ctx, &secret_a);
2424 let pub_b = PublicKey::from_secret_key(&secp_ctx, &secret_b);
2425 let pub_c = PublicKey::from_secret_key(&secp_ctx, &secret_c);
2426 let pub_d = PublicKey::from_secret_key(&secp_ctx, &secret_d);
2429 path_hop(pub_b, 42, 1),
2430 path_hop(pub_c, 43, 2),
2431 path_hop(pub_d, 44, 100),
2434 let node_a = NodeId::from_pubkey(&pub_a);
2435 let node_b = NodeId::from_pubkey(&pub_b);
2436 let node_c = NodeId::from_pubkey(&pub_c);
2437 let node_d = NodeId::from_pubkey(&pub_d);
2439 let params = ProbabilisticScoringFeeParameters {
2440 liquidity_penalty_multiplier_msat: 1_000,
2441 ..ProbabilisticScoringFeeParameters::zero_penalty()
2443 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2445 let usage = ChannelUsage {
2447 inflight_htlc_msat: 0,
2448 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2450 assert_eq!(scorer.channel_penalty_msat(42, &node_a, &node_b, usage, ¶ms), 128);
2451 // Note that a default liquidity bound is used for B -> C as no channel exists
2452 assert_eq!(scorer.channel_penalty_msat(43, &node_b, &node_c, usage, ¶ms), 128);
2453 assert_eq!(scorer.channel_penalty_msat(44, &node_c, &node_d, usage, ¶ms), 128);
2455 scorer.payment_path_failed(&Path { hops: path, blinded_tail: None }, 43);
2457 assert_eq!(scorer.channel_penalty_msat(42, &node_a, &node_b, usage, ¶ms), 80);
2458 // Note that a default liquidity bound is used for B -> C as no channel exists
2459 assert_eq!(scorer.channel_penalty_msat(43, &node_b, &node_c, usage, ¶ms), 128);
2460 assert_eq!(scorer.channel_penalty_msat(44, &node_c, &node_d, usage, ¶ms), 128);
2464 fn reduces_liquidity_upper_bound_along_path_on_success() {
2465 let logger = TestLogger::new();
2466 let network_graph = network_graph(&logger);
2467 let params = ProbabilisticScoringFeeParameters {
2468 liquidity_penalty_multiplier_msat: 1_000,
2469 ..ProbabilisticScoringFeeParameters::zero_penalty()
2471 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2472 let sender = sender_node_id();
2473 let source = source_node_id();
2474 let target = target_node_id();
2475 let recipient = recipient_node_id();
2476 let usage = ChannelUsage {
2478 inflight_htlc_msat: 0,
2479 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2482 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 128);
2483 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 128);
2484 assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage, ¶ms), 128);
2486 scorer.payment_path_successful(&payment_path_for_amount(500));
2488 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 128);
2489 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2490 assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage, ¶ms), 300);
2494 fn decays_liquidity_bounds_over_time() {
2495 let logger = TestLogger::new();
2496 let network_graph = network_graph(&logger);
2497 let params = ProbabilisticScoringFeeParameters {
2498 liquidity_penalty_multiplier_msat: 1_000,
2499 considered_impossible_penalty_msat: u64::max_value(),
2500 ..ProbabilisticScoringFeeParameters::zero_penalty()
2502 let decay_params = ProbabilisticScoringDecayParameters {
2503 liquidity_offset_half_life: Duration::from_secs(10),
2504 ..ProbabilisticScoringDecayParameters::zero_penalty()
2506 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2507 let source = source_node_id();
2508 let target = target_node_id();
2510 let usage = ChannelUsage {
2512 inflight_htlc_msat: 0,
2513 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
2515 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2516 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
2517 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2_000);
2519 scorer.payment_path_failed(&payment_path_for_amount(768), 42);
2520 scorer.payment_path_failed(&payment_path_for_amount(128), 43);
2522 // Initial penalties
2523 let usage = ChannelUsage { amount_msat: 128, ..usage };
2524 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2525 let usage = ChannelUsage { amount_msat: 256, ..usage };
2526 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 93);
2527 let usage = ChannelUsage { amount_msat: 768, ..usage };
2528 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1_479);
2529 let usage = ChannelUsage { amount_msat: 896, ..usage };
2530 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2533 SinceEpoch::advance(Duration::from_secs(4));
2534 let usage = ChannelUsage { amount_msat: 128, ..usage };
2535 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2536 let usage = ChannelUsage { amount_msat: 256, ..usage };
2537 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 93);
2538 let usage = ChannelUsage { amount_msat: 768, ..usage };
2539 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1_479);
2540 let usage = ChannelUsage { amount_msat: 896, ..usage };
2541 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2543 // Half decay (i.e., three-quarter life)
2544 SinceEpoch::advance(Duration::from_secs(1));
2545 let usage = ChannelUsage { amount_msat: 128, ..usage };
2546 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 22);
2547 let usage = ChannelUsage { amount_msat: 256, ..usage };
2548 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 106);
2549 let usage = ChannelUsage { amount_msat: 768, ..usage };
2550 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 916);
2551 let usage = ChannelUsage { amount_msat: 896, ..usage };
2552 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2554 // One decay (i.e., half life)
2555 SinceEpoch::advance(Duration::from_secs(5));
2556 let usage = ChannelUsage { amount_msat: 64, ..usage };
2557 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2558 let usage = ChannelUsage { amount_msat: 128, ..usage };
2559 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 34);
2560 let usage = ChannelUsage { amount_msat: 896, ..usage };
2561 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1_970);
2562 let usage = ChannelUsage { amount_msat: 960, ..usage };
2563 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2565 // Fully decay liquidity lower bound.
2566 SinceEpoch::advance(Duration::from_secs(10 * 7));
2567 let usage = ChannelUsage { amount_msat: 0, ..usage };
2568 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2569 let usage = ChannelUsage { amount_msat: 1, ..usage };
2570 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2571 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
2572 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2_000);
2573 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2574 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2576 // Fully decay liquidity upper bound.
2577 SinceEpoch::advance(Duration::from_secs(10));
2578 let usage = ChannelUsage { amount_msat: 0, ..usage };
2579 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2580 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2581 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2583 SinceEpoch::advance(Duration::from_secs(10));
2584 let usage = ChannelUsage { amount_msat: 0, ..usage };
2585 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2586 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2587 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2591 fn decays_liquidity_bounds_without_shift_overflow() {
2592 let logger = TestLogger::new();
2593 let network_graph = network_graph(&logger);
2594 let params = ProbabilisticScoringFeeParameters {
2595 liquidity_penalty_multiplier_msat: 1_000,
2596 ..ProbabilisticScoringFeeParameters::zero_penalty()
2598 let decay_params = ProbabilisticScoringDecayParameters {
2599 liquidity_offset_half_life: Duration::from_secs(10),
2600 ..ProbabilisticScoringDecayParameters::default()
2602 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2603 let source = source_node_id();
2604 let target = target_node_id();
2605 let usage = ChannelUsage {
2607 inflight_htlc_msat: 0,
2608 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2610 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 125);
2612 scorer.payment_path_failed(&payment_path_for_amount(512), 42);
2613 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 281);
2615 // An unchecked right shift 64 bits or more in DirectedChannelLiquidity::decayed_offset_msat
2616 // would cause an overflow.
2617 SinceEpoch::advance(Duration::from_secs(10 * 64));
2618 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 125);
2620 SinceEpoch::advance(Duration::from_secs(10));
2621 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 125);
2625 fn restricts_liquidity_bounds_after_decay() {
2626 let logger = TestLogger::new();
2627 let network_graph = network_graph(&logger);
2628 let params = ProbabilisticScoringFeeParameters {
2629 liquidity_penalty_multiplier_msat: 1_000,
2630 ..ProbabilisticScoringFeeParameters::zero_penalty()
2632 let decay_params = ProbabilisticScoringDecayParameters {
2633 liquidity_offset_half_life: Duration::from_secs(10),
2634 ..ProbabilisticScoringDecayParameters::default()
2636 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2637 let source = source_node_id();
2638 let target = target_node_id();
2639 let usage = ChannelUsage {
2641 inflight_htlc_msat: 0,
2642 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2645 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2647 // More knowledge gives higher confidence (256, 768), meaning a lower penalty.
2648 scorer.payment_path_failed(&payment_path_for_amount(768), 42);
2649 scorer.payment_path_failed(&payment_path_for_amount(256), 43);
2650 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 281);
2652 // Decaying knowledge gives less confidence (128, 896), meaning a higher penalty.
2653 SinceEpoch::advance(Duration::from_secs(10));
2654 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 291);
2656 // Reducing the upper bound gives more confidence (128, 832) that the payment amount (512)
2657 // is closer to the upper bound, meaning a higher penalty.
2658 scorer.payment_path_successful(&payment_path_for_amount(64));
2659 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 331);
2661 // Increasing the lower bound gives more confidence (256, 832) that the payment amount (512)
2662 // is closer to the lower bound, meaning a lower penalty.
2663 scorer.payment_path_failed(&payment_path_for_amount(256), 43);
2664 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 245);
2666 // Further decaying affects the lower bound more than the upper bound (128, 928).
2667 SinceEpoch::advance(Duration::from_secs(10));
2668 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 280);
2672 fn restores_persisted_liquidity_bounds() {
2673 let logger = TestLogger::new();
2674 let network_graph = network_graph(&logger);
2675 let params = ProbabilisticScoringFeeParameters {
2676 liquidity_penalty_multiplier_msat: 1_000,
2677 considered_impossible_penalty_msat: u64::max_value(),
2678 ..ProbabilisticScoringFeeParameters::zero_penalty()
2680 let decay_params = ProbabilisticScoringDecayParameters {
2681 liquidity_offset_half_life: Duration::from_secs(10),
2682 ..ProbabilisticScoringDecayParameters::default()
2684 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2685 let source = source_node_id();
2686 let target = target_node_id();
2687 let usage = ChannelUsage {
2689 inflight_htlc_msat: 0,
2690 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2693 scorer.payment_path_failed(&payment_path_for_amount(500), 42);
2694 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2696 SinceEpoch::advance(Duration::from_secs(10));
2697 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 473);
2699 scorer.payment_path_failed(&payment_path_for_amount(250), 43);
2700 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2702 let mut serialized_scorer = Vec::new();
2703 scorer.write(&mut serialized_scorer).unwrap();
2705 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
2706 let deserialized_scorer =
2707 <ProbabilisticScorer>::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap();
2708 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2712 fn decays_persisted_liquidity_bounds() {
2713 let logger = TestLogger::new();
2714 let network_graph = network_graph(&logger);
2715 let params = ProbabilisticScoringFeeParameters {
2716 liquidity_penalty_multiplier_msat: 1_000,
2717 considered_impossible_penalty_msat: u64::max_value(),
2718 ..ProbabilisticScoringFeeParameters::zero_penalty()
2720 let decay_params = ProbabilisticScoringDecayParameters {
2721 liquidity_offset_half_life: Duration::from_secs(10),
2722 ..ProbabilisticScoringDecayParameters::zero_penalty()
2724 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2725 let source = source_node_id();
2726 let target = target_node_id();
2727 let usage = ChannelUsage {
2729 inflight_htlc_msat: 0,
2730 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2733 scorer.payment_path_failed(&payment_path_for_amount(500), 42);
2734 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2736 let mut serialized_scorer = Vec::new();
2737 scorer.write(&mut serialized_scorer).unwrap();
2739 SinceEpoch::advance(Duration::from_secs(10));
2741 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
2742 let deserialized_scorer =
2743 <ProbabilisticScorer>::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap();
2744 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 473);
2746 scorer.payment_path_failed(&payment_path_for_amount(250), 43);
2747 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2749 SinceEpoch::advance(Duration::from_secs(10));
2750 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 365);
2754 fn scores_realistic_payments() {
2755 // Shows the scores of "realistic" sends of 100k sats over channels of 1-10m sats (with a
2756 // 50k sat reserve).
2757 let logger = TestLogger::new();
2758 let network_graph = network_graph(&logger);
2759 let params = ProbabilisticScoringFeeParameters::default();
2760 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2761 let source = source_node_id();
2762 let target = target_node_id();
2764 let usage = ChannelUsage {
2765 amount_msat: 100_000_000,
2766 inflight_htlc_msat: 0,
2767 effective_capacity: EffectiveCapacity::Total { capacity_msat: 950_000_000, htlc_maximum_msat: 1_000 },
2769 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 4375);
2770 let usage = ChannelUsage {
2771 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2773 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2739);
2774 let usage = ChannelUsage {
2775 effective_capacity: EffectiveCapacity::Total { capacity_msat: 2_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2777 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2236);
2778 let usage = ChannelUsage {
2779 effective_capacity: EffectiveCapacity::Total { capacity_msat: 3_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2781 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1983);
2782 let usage = ChannelUsage {
2783 effective_capacity: EffectiveCapacity::Total { capacity_msat: 4_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2785 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1637);
2786 let usage = ChannelUsage {
2787 effective_capacity: EffectiveCapacity::Total { capacity_msat: 5_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2789 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1606);
2790 let usage = ChannelUsage {
2791 effective_capacity: EffectiveCapacity::Total { capacity_msat: 6_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2793 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1331);
2794 let usage = ChannelUsage {
2795 effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_450_000_000, htlc_maximum_msat: 1_000 }, ..usage
2797 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1387);
2798 let usage = ChannelUsage {
2799 effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2801 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1379);
2802 let usage = ChannelUsage {
2803 effective_capacity: EffectiveCapacity::Total { capacity_msat: 8_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2805 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1363);
2806 let usage = ChannelUsage {
2807 effective_capacity: EffectiveCapacity::Total { capacity_msat: 9_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2809 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1355);
2813 fn adds_base_penalty_to_liquidity_penalty() {
2814 let logger = TestLogger::new();
2815 let network_graph = network_graph(&logger);
2816 let source = source_node_id();
2817 let target = target_node_id();
2818 let usage = ChannelUsage {
2820 inflight_htlc_msat: 0,
2821 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2824 let params = ProbabilisticScoringFeeParameters {
2825 liquidity_penalty_multiplier_msat: 1_000,
2826 ..ProbabilisticScoringFeeParameters::zero_penalty()
2828 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2829 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 58);
2831 let params = ProbabilisticScoringFeeParameters {
2832 base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000,
2833 anti_probing_penalty_msat: 0, ..ProbabilisticScoringFeeParameters::zero_penalty()
2835 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2836 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 558);
2838 let params = ProbabilisticScoringFeeParameters {
2839 base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000,
2840 base_penalty_amount_multiplier_msat: (1 << 30),
2841 anti_probing_penalty_msat: 0, ..ProbabilisticScoringFeeParameters::zero_penalty()
2844 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2845 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 558 + 128);
2849 fn adds_amount_penalty_to_liquidity_penalty() {
2850 let logger = TestLogger::new();
2851 let network_graph = network_graph(&logger);
2852 let source = source_node_id();
2853 let target = target_node_id();
2854 let usage = ChannelUsage {
2855 amount_msat: 512_000,
2856 inflight_htlc_msat: 0,
2857 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
2860 let params = ProbabilisticScoringFeeParameters {
2861 liquidity_penalty_multiplier_msat: 1_000,
2862 liquidity_penalty_amount_multiplier_msat: 0,
2863 ..ProbabilisticScoringFeeParameters::zero_penalty()
2865 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2866 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2868 let params = ProbabilisticScoringFeeParameters {
2869 liquidity_penalty_multiplier_msat: 1_000,
2870 liquidity_penalty_amount_multiplier_msat: 256,
2871 ..ProbabilisticScoringFeeParameters::zero_penalty()
2873 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2874 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 337);
2878 fn calculates_log10_without_overflowing_u64_max_value() {
2879 let logger = TestLogger::new();
2880 let network_graph = network_graph(&logger);
2881 let source = source_node_id();
2882 let target = target_node_id();
2883 let usage = ChannelUsage {
2884 amount_msat: u64::max_value(),
2885 inflight_htlc_msat: 0,
2886 effective_capacity: EffectiveCapacity::Infinite,
2889 let params = ProbabilisticScoringFeeParameters {
2890 liquidity_penalty_multiplier_msat: 40_000,
2891 ..ProbabilisticScoringFeeParameters::zero_penalty()
2893 let decay_params = ProbabilisticScoringDecayParameters::zero_penalty();
2894 let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2895 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 80_000);
2899 fn accounts_for_inflight_htlc_usage() {
2900 let logger = TestLogger::new();
2901 let network_graph = network_graph(&logger);
2902 let params = ProbabilisticScoringFeeParameters {
2903 considered_impossible_penalty_msat: u64::max_value(),
2904 ..ProbabilisticScoringFeeParameters::zero_penalty()
2906 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2907 let source = source_node_id();
2908 let target = target_node_id();
2910 let usage = ChannelUsage {
2912 inflight_htlc_msat: 0,
2913 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2915 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2917 let usage = ChannelUsage { inflight_htlc_msat: 251, ..usage };
2918 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2922 fn removes_uncertainity_when_exact_liquidity_known() {
2923 let logger = TestLogger::new();
2924 let network_graph = network_graph(&logger);
2925 let params = ProbabilisticScoringFeeParameters::default();
2926 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2927 let source = source_node_id();
2928 let target = target_node_id();
2930 let base_penalty_msat = params.base_penalty_msat;
2931 let usage = ChannelUsage {
2933 inflight_htlc_msat: 0,
2934 effective_capacity: EffectiveCapacity::ExactLiquidity { liquidity_msat: 1_000 },
2936 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), base_penalty_msat);
2938 let usage = ChannelUsage { amount_msat: 1_000, ..usage };
2939 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), base_penalty_msat);
2941 let usage = ChannelUsage { amount_msat: 1_001, ..usage };
2942 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2946 fn remembers_historical_failures() {
2947 let logger = TestLogger::new();
2948 let network_graph = network_graph(&logger);
2949 let params = ProbabilisticScoringFeeParameters {
2950 historical_liquidity_penalty_multiplier_msat: 1024,
2951 historical_liquidity_penalty_amount_multiplier_msat: 1024,
2952 ..ProbabilisticScoringFeeParameters::zero_penalty()
2954 let decay_params = ProbabilisticScoringDecayParameters {
2955 liquidity_offset_half_life: Duration::from_secs(60 * 60),
2956 historical_no_updates_half_life: Duration::from_secs(10),
2958 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2959 let source = source_node_id();
2960 let target = target_node_id();
2962 let usage = ChannelUsage {
2964 inflight_htlc_msat: 0,
2965 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
2967 // With no historical data the normal liquidity penalty calculation is used.
2968 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 47);
2969 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
2971 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 42),
2974 scorer.payment_path_failed(&payment_path_for_amount(1), 42);
2975 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2048);
2976 // The "it failed" increment is 32, where the probability should lie fully in the first
2978 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
2979 Some(([32, 0, 0, 0, 0, 0, 0, 0], [32, 0, 0, 0, 0, 0, 0, 0])));
2980 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 1),
2982 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 500),
2985 // Even after we tell the scorer we definitely have enough available liquidity, it will
2986 // still remember that there was some failure in the past, and assign a non-0 penalty.
2987 scorer.payment_path_failed(&payment_path_for_amount(1000), 43);
2988 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 198);
2989 // The first octile should be decayed just slightly and the last octile has a new point.
2990 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
2991 Some(([31, 0, 0, 0, 0, 0, 0, 32], [31, 0, 0, 0, 0, 0, 0, 32])));
2993 // The exact success probability is a bit complicated and involves integer rounding, so we
2994 // simply check bounds here.
2995 let five_hundred_prob =
2996 scorer.historical_estimated_payment_success_probability(42, &target, 500).unwrap();
2997 assert!(five_hundred_prob > 0.5);
2998 assert!(five_hundred_prob < 0.52);
3000 scorer.historical_estimated_payment_success_probability(42, &target, 1).unwrap();
3001 assert!(one_prob < 1.0);
3002 assert!(one_prob > 0.99);
3004 // Advance the time forward 16 half-lives (which the docs claim will ensure all data is
3005 // gone), and check that we're back to where we started.
3006 SinceEpoch::advance(Duration::from_secs(10 * 16));
3007 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 47);
3008 // Once fully decayed we still have data, but its all-0s. In the future we may remove the
3009 // data entirely instead.
3010 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3011 Some(([0; 8], [0; 8])));
3012 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 1), None);
3014 let mut usage = ChannelUsage {
3016 inflight_htlc_msat: 1024,
3017 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
3019 scorer.payment_path_failed(&payment_path_for_amount(1), 42);
3020 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2048);
3021 usage.inflight_htlc_msat = 0;
3022 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 409);
3024 let usage = ChannelUsage {
3026 inflight_htlc_msat: 0,
3027 effective_capacity: EffectiveCapacity::AdvertisedMaxHTLC { amount_msat: 0 },
3029 assert_eq!(scorer.channel_penalty_msat(42, &target, &source, usage, ¶ms), 2048);
3031 // Advance to decay all liquidity offsets to zero.
3032 SinceEpoch::advance(Duration::from_secs(60 * 60 * 10));
3034 // Use a path in the opposite direction, which have zero for htlc_maximum_msat. This will
3035 // ensure that the effective capacity is zero to test division-by-zero edge cases.
3037 path_hop(target_pubkey(), 43, 2),
3038 path_hop(source_pubkey(), 42, 1),
3039 path_hop(sender_pubkey(), 41, 0),
3041 scorer.payment_path_failed(&Path { hops: path, blinded_tail: None }, 42);
3045 fn adds_anti_probing_penalty() {
3046 let logger = TestLogger::new();
3047 let network_graph = network_graph(&logger);
3048 let source = source_node_id();
3049 let target = target_node_id();
3050 let params = ProbabilisticScoringFeeParameters {
3051 anti_probing_penalty_msat: 500,
3052 ..ProbabilisticScoringFeeParameters::zero_penalty()
3054 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3056 // Check we receive no penalty for a low htlc_maximum_msat.
3057 let usage = ChannelUsage {
3058 amount_msat: 512_000,
3059 inflight_htlc_msat: 0,
3060 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
3062 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
3064 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity.
3065 let usage = ChannelUsage {
3066 amount_msat: 512_000,
3067 inflight_htlc_msat: 0,
3068 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_024_000 },
3070 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 500);
3072 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity/2.
3073 let usage = ChannelUsage {
3074 amount_msat: 512_000,
3075 inflight_htlc_msat: 0,
3076 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 512_000 },
3078 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 500);
3080 // Check we receive no anti-probing penalty for htlc_maximum_msat == channel_capacity/2 - 1.
3081 let usage = ChannelUsage {
3082 amount_msat: 512_000,
3083 inflight_htlc_msat: 0,
3084 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 511_999 },
3086 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
3090 fn scores_with_blinded_path() {
3091 // Make sure we'll account for a blinded path's final_value_msat in scoring
3092 let logger = TestLogger::new();
3093 let network_graph = network_graph(&logger);
3094 let params = ProbabilisticScoringFeeParameters {
3095 liquidity_penalty_multiplier_msat: 1_000,
3096 ..ProbabilisticScoringFeeParameters::zero_penalty()
3098 let decay_params = ProbabilisticScoringDecayParameters::default();
3099 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3100 let source = source_node_id();
3101 let target = target_node_id();
3102 let usage = ChannelUsage {
3104 inflight_htlc_msat: 0,
3105 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
3107 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
3109 let mut path = payment_path_for_amount(768);
3110 let recipient_hop = path.hops.pop().unwrap();
3111 let blinded_path = BlindedPath {
3112 introduction_node_id: path.hops.last().as_ref().unwrap().pubkey,
3113 blinding_point: test_utils::pubkey(42),
3115 BlindedHop { blinded_node_id: test_utils::pubkey(44), encrypted_payload: Vec::new() }
3118 path.blinded_tail = Some(BlindedTail {
3119 hops: blinded_path.blinded_hops,
3120 blinding_point: blinded_path.blinding_point,
3121 excess_final_cltv_expiry_delta: recipient_hop.cltv_expiry_delta,
3122 final_value_msat: recipient_hop.fee_msat,
3125 // Check the liquidity before and after scoring payment failures to ensure the blinded path's
3126 // final value is taken into account.
3127 assert!(scorer.channel_liquidities.get(&42).is_none());
3129 scorer.payment_path_failed(&path, 42);
3130 path.blinded_tail.as_mut().unwrap().final_value_msat = 256;
3131 scorer.payment_path_failed(&path, 43);
3133 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
3134 .as_directed(&source, &target, 0, 1_000, decay_params);
3135 assert_eq!(liquidity.min_liquidity_msat(), 256);
3136 assert_eq!(liquidity.max_liquidity_msat(), 768);