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