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 {
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 {
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 /// A trait which can both lookup and update routing channel penalty scores.
127 /// This is used in places where both bounds are required and implemented for all types which
128 /// implement [`ScoreLookUp`] and [`ScoreUpdate`].
130 /// Bindings users may need to manually implement this for their custom scoring implementations.
131 pub trait Score : ScoreLookUp + ScoreUpdate $(+ $supertrait)* {}
133 #[cfg(not(c_bindings))]
134 impl<T: ScoreLookUp + ScoreUpdate $(+ $supertrait)*> Score for T {}
136 #[cfg(not(c_bindings))]
137 impl<S: ScoreLookUp, T: Deref<Target=S>> ScoreLookUp for T {
138 type ScoreParams = S::ScoreParams;
139 fn channel_penalty_msat(
140 &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage, score_params: &Self::ScoreParams
142 self.deref().channel_penalty_msat(short_channel_id, source, target, usage, score_params)
146 #[cfg(not(c_bindings))]
147 impl<S: ScoreUpdate, T: DerefMut<Target=S>> ScoreUpdate for T {
148 fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64) {
149 self.deref_mut().payment_path_failed(path, short_channel_id)
152 fn payment_path_successful(&mut self, path: &Path) {
153 self.deref_mut().payment_path_successful(path)
156 fn probe_failed(&mut self, path: &Path, short_channel_id: u64) {
157 self.deref_mut().probe_failed(path, short_channel_id)
160 fn probe_successful(&mut self, path: &Path) {
161 self.deref_mut().probe_successful(path)
167 define_score!(Writeable);
169 #[cfg(not(c_bindings))]
172 /// A scorer that is accessed under a lock.
174 /// Needed so that calls to [`ScoreLookUp::channel_penalty_msat`] in [`find_route`] can be made while
175 /// having shared ownership of a scorer but without requiring internal locking in [`ScoreUpdate`]
176 /// implementations. Internal locking would be detrimental to route finding performance and could
177 /// result in [`ScoreLookUp::channel_penalty_msat`] returning a different value for the same channel.
179 /// [`find_route`]: crate::routing::router::find_route
180 pub trait LockableScore<'a> {
181 /// The [`ScoreUpdate`] type.
182 type ScoreUpdate: 'a + ScoreUpdate;
183 /// The [`ScoreLookUp`] type.
184 type ScoreLookUp: 'a + ScoreLookUp;
186 /// The write locked [`ScoreUpdate`] type.
187 type WriteLocked: DerefMut<Target = Self::ScoreUpdate> + Sized;
189 /// The read locked [`ScoreLookUp`] type.
190 type ReadLocked: Deref<Target = Self::ScoreLookUp> + Sized;
192 /// Returns read locked scorer.
193 fn read_lock(&'a self) -> Self::ReadLocked;
195 /// Returns write locked scorer.
196 fn write_lock(&'a self) -> Self::WriteLocked;
199 /// Refers to a scorer that is accessible under lock and also writeable to disk
201 /// We need this trait to be able to pass in a scorer to `lightning-background-processor` that will enable us to
202 /// use the Persister to persist it.
203 pub trait WriteableScore<'a>: LockableScore<'a> + Writeable {}
205 #[cfg(not(c_bindings))]
206 impl<'a, T> WriteableScore<'a> for T where T: LockableScore<'a> + Writeable {}
207 #[cfg(not(c_bindings))]
208 impl<'a, T: Score + 'a> LockableScore<'a> for Mutex<T> {
209 type ScoreUpdate = T;
210 type ScoreLookUp = T;
212 type WriteLocked = MutexGuard<'a, Self::ScoreUpdate>;
213 type ReadLocked = MutexGuard<'a, Self::ScoreLookUp>;
215 fn read_lock(&'a self) -> Self::ReadLocked {
216 Mutex::lock(self).unwrap()
219 fn write_lock(&'a self) -> Self::WriteLocked {
220 Mutex::lock(self).unwrap()
224 #[cfg(not(c_bindings))]
225 impl<'a, T: Score + 'a> LockableScore<'a> for RefCell<T> {
226 type ScoreUpdate = T;
227 type ScoreLookUp = T;
229 type WriteLocked = RefMut<'a, Self::ScoreUpdate>;
230 type ReadLocked = Ref<'a, Self::ScoreLookUp>;
232 fn write_lock(&'a self) -> Self::WriteLocked {
236 fn read_lock(&'a self) -> Self::ReadLocked {
241 #[cfg(not(c_bindings))]
242 impl<'a, T: Score + 'a> LockableScore<'a> for RwLock<T> {
243 type ScoreUpdate = T;
244 type ScoreLookUp = T;
246 type WriteLocked = RwLockWriteGuard<'a, Self::ScoreLookUp>;
247 type ReadLocked = RwLockReadGuard<'a, Self::ScoreUpdate>;
249 fn read_lock(&'a self) -> Self::ReadLocked {
250 RwLock::read(self).unwrap()
253 fn write_lock(&'a self) -> Self::WriteLocked {
254 RwLock::write(self).unwrap()
259 /// A concrete implementation of [`LockableScore`] which supports multi-threading.
260 pub struct MultiThreadedLockableScore<T: Score> {
265 impl<'a, T: Score + 'a> LockableScore<'a> for MultiThreadedLockableScore<T> {
266 type ScoreUpdate = T;
267 type ScoreLookUp = T;
268 type WriteLocked = MultiThreadedScoreLockWrite<'a, Self::ScoreUpdate>;
269 type ReadLocked = MultiThreadedScoreLockRead<'a, Self::ScoreLookUp>;
271 fn read_lock(&'a self) -> Self::ReadLocked {
272 MultiThreadedScoreLockRead(self.score.read().unwrap())
275 fn write_lock(&'a self) -> Self::WriteLocked {
276 MultiThreadedScoreLockWrite(self.score.write().unwrap())
281 impl<T: Score> Writeable for MultiThreadedLockableScore<T> {
282 fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
283 self.score.read().unwrap().write(writer)
288 impl<'a, T: Score + 'a> WriteableScore<'a> for MultiThreadedLockableScore<T> {}
291 impl<T: Score> MultiThreadedLockableScore<T> {
292 /// Creates a new [`MultiThreadedLockableScore`] given an underlying [`Score`].
293 pub fn new(score: T) -> Self {
294 MultiThreadedLockableScore { score: RwLock::new(score) }
299 /// A locked `MultiThreadedLockableScore`.
300 pub struct MultiThreadedScoreLockRead<'a, T: Score>(RwLockReadGuard<'a, T>);
303 /// A locked `MultiThreadedLockableScore`.
304 pub struct MultiThreadedScoreLockWrite<'a, T: Score>(RwLockWriteGuard<'a, T>);
307 impl<'a, T: 'a + Score> Deref for MultiThreadedScoreLockRead<'a, T> {
310 fn deref(&self) -> &Self::Target {
316 impl<'a, T: Score> ScoreLookUp for MultiThreadedScoreLockRead<'a, T> {
317 type ScoreParams = T::ScoreParams;
318 fn channel_penalty_msat(&self, short_channel_id: u64, source: &NodeId,
319 target: &NodeId, usage: ChannelUsage, score_params: &Self::ScoreParams
321 self.0.channel_penalty_msat(short_channel_id, source, target, usage, score_params)
326 impl<'a, T: Score> Writeable for MultiThreadedScoreLockWrite<'a, T> {
327 fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
333 impl<'a, T: 'a + Score> Deref for MultiThreadedScoreLockWrite<'a, T> {
336 fn deref(&self) -> &Self::Target {
342 impl<'a, T: 'a + Score> DerefMut for MultiThreadedScoreLockWrite<'a, T> {
343 fn deref_mut(&mut self) -> &mut Self::Target {
349 impl<'a, T: Score> ScoreUpdate for MultiThreadedScoreLockWrite<'a, T> {
350 fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64) {
351 self.0.payment_path_failed(path, short_channel_id)
354 fn payment_path_successful(&mut self, path: &Path) {
355 self.0.payment_path_successful(path)
358 fn probe_failed(&mut self, path: &Path, short_channel_id: u64) {
359 self.0.probe_failed(path, short_channel_id)
362 fn probe_successful(&mut self, path: &Path) {
363 self.0.probe_successful(path)
368 /// Proposed use of a channel passed as a parameter to [`ScoreLookUp::channel_penalty_msat`].
369 #[derive(Clone, Copy, Debug, PartialEq)]
370 pub struct ChannelUsage {
371 /// The amount to send through the channel, denominated in millisatoshis.
372 pub amount_msat: u64,
374 /// Total amount, denominated in millisatoshis, already allocated to send through the channel
375 /// as part of a multi-path payment.
376 pub inflight_htlc_msat: u64,
378 /// The effective capacity of the channel.
379 pub effective_capacity: EffectiveCapacity,
383 /// [`ScoreLookUp`] implementation that uses a fixed penalty.
384 pub struct FixedPenaltyScorer {
388 impl FixedPenaltyScorer {
389 /// Creates a new scorer using `penalty_msat`.
390 pub fn with_penalty(penalty_msat: u64) -> Self {
391 Self { penalty_msat }
395 impl ScoreLookUp for FixedPenaltyScorer {
396 type ScoreParams = ();
397 fn channel_penalty_msat(&self, _: u64, _: &NodeId, _: &NodeId, _: ChannelUsage, _score_params: &Self::ScoreParams) -> u64 {
402 impl ScoreUpdate for FixedPenaltyScorer {
403 fn payment_path_failed(&mut self, _path: &Path, _short_channel_id: u64) {}
405 fn payment_path_successful(&mut self, _path: &Path) {}
407 fn probe_failed(&mut self, _path: &Path, _short_channel_id: u64) {}
409 fn probe_successful(&mut self, _path: &Path) {}
412 impl Writeable for FixedPenaltyScorer {
414 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
415 write_tlv_fields!(w, {});
420 impl ReadableArgs<u64> for FixedPenaltyScorer {
422 fn read<R: Read>(r: &mut R, penalty_msat: u64) -> Result<Self, DecodeError> {
423 read_tlv_fields!(r, {});
424 Ok(Self { penalty_msat })
428 #[cfg(not(feature = "no-std"))]
429 /// [`ScoreLookUp`] implementation using channel success probability distributions.
431 /// Channels are tracked with upper and lower liquidity bounds - when an HTLC fails at a channel,
432 /// we learn that the upper-bound on the available liquidity is lower than the amount of the HTLC.
433 /// When a payment is forwarded through a channel (but fails later in the route), we learn the
434 /// lower-bound on the channel's available liquidity must be at least the value of the HTLC.
436 /// These bounds are then used to determine a success probability using the formula from
437 /// *Optimally Reliable & Cheap Payment Flows on the Lightning Network* by Rene Pickhardt
438 /// and Stefan Richter [[1]] (i.e. `(upper_bound - payment_amount) / (upper_bound - lower_bound)`).
440 /// This probability is combined with the [`liquidity_penalty_multiplier_msat`] and
441 /// [`liquidity_penalty_amount_multiplier_msat`] parameters to calculate a concrete penalty in
442 /// milli-satoshis. The penalties, when added across all hops, have the property of being linear in
443 /// terms of the entire path's success probability. This allows the router to directly compare
444 /// penalties for different paths. See the documentation of those parameters for the exact formulas.
446 /// The liquidity bounds are decayed by halving them every [`liquidity_offset_half_life`].
448 /// Further, we track the history of our upper and lower liquidity bounds for each channel,
449 /// allowing us to assign a second penalty (using [`historical_liquidity_penalty_multiplier_msat`]
450 /// and [`historical_liquidity_penalty_amount_multiplier_msat`]) based on the same probability
451 /// formula, but using the history of a channel rather than our latest estimates for the liquidity
456 /// Mixing the `no-std` feature between serialization and deserialization results in undefined
459 /// [1]: https://arxiv.org/abs/2107.05322
460 /// [`liquidity_penalty_multiplier_msat`]: ProbabilisticScoringFeeParameters::liquidity_penalty_multiplier_msat
461 /// [`liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringFeeParameters::liquidity_penalty_amount_multiplier_msat
462 /// [`liquidity_offset_half_life`]: ProbabilisticScoringDecayParameters::liquidity_offset_half_life
463 /// [`historical_liquidity_penalty_multiplier_msat`]: ProbabilisticScoringFeeParameters::historical_liquidity_penalty_multiplier_msat
464 /// [`historical_liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringFeeParameters::historical_liquidity_penalty_amount_multiplier_msat
465 pub type ProbabilisticScorer<G, L> = ProbabilisticScorerUsingTime::<G, L, crate::util::time::MonotonicTime>;
467 #[cfg(feature = "no-std")]
468 /// [`ScoreLookUp`] implementation using channel success probability distributions.
470 /// Channels are tracked with upper and lower liquidity bounds - when an HTLC fails at a channel,
471 /// we learn that the upper-bound on the available liquidity is lower than the amount of the HTLC.
472 /// When a payment is forwarded through a channel (but fails later in the route), we learn the
473 /// lower-bound on the channel's available liquidity must be at least the value of the HTLC.
475 /// These bounds are then used to determine a success probability using the formula from
476 /// *Optimally Reliable & Cheap Payment Flows on the Lightning Network* by Rene Pickhardt
477 /// and Stefan Richter [[1]] (i.e. `(upper_bound - payment_amount) / (upper_bound - lower_bound)`).
479 /// This probability is combined with the [`liquidity_penalty_multiplier_msat`] and
480 /// [`liquidity_penalty_amount_multiplier_msat`] parameters to calculate a concrete penalty in
481 /// milli-satoshis. The penalties, when added across all hops, have the property of being linear in
482 /// terms of the entire path's success probability. This allows the router to directly compare
483 /// penalties for different paths. See the documentation of those parameters for the exact formulas.
485 /// The liquidity bounds are decayed by halving them every [`liquidity_offset_half_life`].
487 /// Further, we track the history of our upper and lower liquidity bounds for each channel,
488 /// allowing us to assign a second penalty (using [`historical_liquidity_penalty_multiplier_msat`]
489 /// and [`historical_liquidity_penalty_amount_multiplier_msat`]) based on the same probability
490 /// formula, but using the history of a channel rather than our latest estimates for the liquidity
495 /// Mixing the `no-std` feature between serialization and deserialization results in undefined
498 /// [1]: https://arxiv.org/abs/2107.05322
499 /// [`liquidity_penalty_multiplier_msat`]: ProbabilisticScoringFeeParameters::liquidity_penalty_multiplier_msat
500 /// [`liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringFeeParameters::liquidity_penalty_amount_multiplier_msat
501 /// [`liquidity_offset_half_life`]: ProbabilisticScoringDecayParameters::liquidity_offset_half_life
502 /// [`historical_liquidity_penalty_multiplier_msat`]: ProbabilisticScoringFeeParameters::historical_liquidity_penalty_multiplier_msat
503 /// [`historical_liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringFeeParameters::historical_liquidity_penalty_amount_multiplier_msat
504 pub type ProbabilisticScorer<G, L> = ProbabilisticScorerUsingTime::<G, L, crate::util::time::Eternity>;
506 /// Probabilistic [`ScoreLookUp`] implementation.
508 /// This is not exported to bindings users generally all users should use the [`ProbabilisticScorer`] type alias.
509 pub struct ProbabilisticScorerUsingTime<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time>
510 where L::Target: Logger {
511 decay_params: ProbabilisticScoringDecayParameters,
514 // TODO: Remove entries of closed channels.
515 channel_liquidities: HashMap<u64, ChannelLiquidity<T>>,
518 /// Parameters for configuring [`ProbabilisticScorer`].
520 /// Used to configure base, liquidity, and amount penalties, the sum of which comprises the channel
521 /// penalty (i.e., the amount in msats willing to be paid to avoid routing through the channel).
523 /// The penalty applied to any channel by the [`ProbabilisticScorer`] is the sum of each of the
526 pub struct ProbabilisticScoringFeeParameters {
527 /// A fixed penalty in msats to apply to each channel.
529 /// Default value: 500 msat
530 pub base_penalty_msat: u64,
532 /// A multiplier used with the total amount flowing over a channel to calculate a fixed penalty
533 /// applied to each channel, in excess of the [`base_penalty_msat`].
535 /// The purpose of the amount penalty is to avoid having fees dominate the channel cost (i.e.,
536 /// fees plus penalty) for large payments. The penalty is computed as the product of this
537 /// multiplier and `2^30`ths of the total amount flowing over a channel (i.e. the payment
538 /// amount plus the amount of any other HTLCs flowing we sent over the same channel).
540 /// ie `base_penalty_amount_multiplier_msat * amount_msat / 2^30`
542 /// Default value: 8,192 msat
544 /// [`base_penalty_msat`]: Self::base_penalty_msat
545 pub base_penalty_amount_multiplier_msat: u64,
547 /// A multiplier used in conjunction with the negative `log10` of the channel's success
548 /// probability for a payment, as determined by our latest estimates of the channel's
549 /// liquidity, to determine the liquidity penalty.
551 /// The penalty is based in part on the knowledge learned from prior successful and unsuccessful
552 /// payments. This knowledge is decayed over time based on [`liquidity_offset_half_life`]. The
553 /// penalty is effectively limited to `2 * liquidity_penalty_multiplier_msat` (corresponding to
554 /// lower bounding the success probability to `0.01`) when the amount falls within the
555 /// uncertainty bounds of the channel liquidity balance. Amounts above the upper bound will
556 /// result in a `u64::max_value` penalty, however.
558 /// `-log10(success_probability) * liquidity_penalty_multiplier_msat`
560 /// Default value: 30,000 msat
562 /// [`liquidity_offset_half_life`]: ProbabilisticScoringDecayParameters::liquidity_offset_half_life
563 pub liquidity_penalty_multiplier_msat: u64,
565 /// A multiplier used in conjunction with the total amount flowing over a channel and the
566 /// negative `log10` of the channel's success probability for the payment, as determined by our
567 /// latest estimates of the channel's liquidity, to determine the amount penalty.
569 /// The purpose of the amount penalty is to avoid having fees dominate the channel cost (i.e.,
570 /// fees plus penalty) for large payments. The penalty is computed as the product of this
571 /// multiplier and `2^20`ths of the amount flowing over this channel, weighted by the negative
572 /// `log10` of the success probability.
574 /// `-log10(success_probability) * liquidity_penalty_amount_multiplier_msat * amount_msat / 2^20`
576 /// In practice, this means for 0.1 success probability (`-log10(0.1) == 1`) each `2^20`th of
577 /// the amount will result in a penalty of the multiplier. And, as the success probability
578 /// decreases, the negative `log10` weighting will increase dramatically. For higher success
579 /// probabilities, the multiplier will have a decreasing effect as the negative `log10` will
582 /// Default value: 192 msat
583 pub liquidity_penalty_amount_multiplier_msat: u64,
585 /// A multiplier used in conjunction with the negative `log10` of the channel's success
586 /// probability for the payment, as determined based on the history of our estimates of the
587 /// channel's available liquidity, to determine a penalty.
589 /// This penalty is similar to [`liquidity_penalty_multiplier_msat`], however, instead of using
590 /// only our latest estimate for the current liquidity available in the channel, it estimates
591 /// success probability based on the estimated liquidity available in the channel through
592 /// history. Specifically, every time we update our liquidity bounds on a given channel, we
593 /// track which of several buckets those bounds fall into, exponentially decaying the
594 /// probability of each bucket as new samples are added.
596 /// Default value: 10,000 msat
598 /// [`liquidity_penalty_multiplier_msat`]: Self::liquidity_penalty_multiplier_msat
599 pub historical_liquidity_penalty_multiplier_msat: u64,
601 /// A multiplier used in conjunction with the total amount flowing over a channel and the
602 /// negative `log10` of the channel's success probability for the payment, as determined based
603 /// on the history of our estimates of the channel's available liquidity, to determine a
606 /// The purpose of the amount penalty is to avoid having fees dominate the channel cost for
607 /// large payments. The penalty is computed as the product of this multiplier and `2^20`ths
608 /// of the amount flowing over this channel, weighted by the negative `log10` of the success
611 /// This penalty is similar to [`liquidity_penalty_amount_multiplier_msat`], however, instead
612 /// of using only our latest estimate for the current liquidity available in the channel, it
613 /// estimates success probability based on the estimated liquidity available in the channel
614 /// through history. Specifically, every time we update our liquidity bounds on a given
615 /// channel, we track which of several buckets those bounds fall into, exponentially decaying
616 /// the probability of each bucket as new samples are added.
618 /// Default value: 64 msat
620 /// [`liquidity_penalty_amount_multiplier_msat`]: Self::liquidity_penalty_amount_multiplier_msat
621 pub historical_liquidity_penalty_amount_multiplier_msat: u64,
623 /// Manual penalties used for the given nodes. Allows to set a particular penalty for a given
624 /// node. Note that a manual penalty of `u64::max_value()` means the node would not ever be
625 /// considered during path finding.
627 /// This is not exported to bindings users
628 pub manual_node_penalties: HashMap<NodeId, u64>,
630 /// This penalty is applied when `htlc_maximum_msat` is equal to or larger than half of the
631 /// channel's capacity, (ie. htlc_maximum_msat >= 0.5 * channel_capacity) which makes us
632 /// prefer nodes with a smaller `htlc_maximum_msat`. We treat such nodes preferentially
633 /// as this makes balance discovery attacks harder to execute, thereby creating an incentive
634 /// to restrict `htlc_maximum_msat` and improve privacy.
636 /// Default value: 250 msat
637 pub anti_probing_penalty_msat: u64,
639 /// This penalty is applied when the total amount flowing over a channel exceeds our current
640 /// estimate of the channel's available liquidity. The total amount is the amount of the
641 /// current HTLC plus any HTLCs which we've sent over the same channel.
643 /// Note that in this case all other penalties, including the
644 /// [`liquidity_penalty_multiplier_msat`] and [`liquidity_penalty_amount_multiplier_msat`]-based
645 /// penalties, as well as the [`base_penalty_msat`] and the [`anti_probing_penalty_msat`], if
646 /// applicable, are still included in the overall penalty.
648 /// If you wish to avoid creating paths with such channels entirely, setting this to a value of
649 /// `u64::max_value()` will guarantee that.
651 /// Default value: 1_0000_0000_000 msat (1 Bitcoin)
653 /// [`liquidity_penalty_multiplier_msat`]: Self::liquidity_penalty_multiplier_msat
654 /// [`liquidity_penalty_amount_multiplier_msat`]: Self::liquidity_penalty_amount_multiplier_msat
655 /// [`base_penalty_msat`]: Self::base_penalty_msat
656 /// [`anti_probing_penalty_msat`]: Self::anti_probing_penalty_msat
657 pub considered_impossible_penalty_msat: u64,
659 /// In order to calculate most of the scores above, we must first convert a lower and upper
660 /// bound on the available liquidity in a channel into the probability that we think a payment
661 /// will succeed. That probability is derived from a Probability Density Function for where we
662 /// think the liquidity in a channel likely lies, given such bounds.
664 /// If this flag is set, that PDF is simply a constant - we assume that the actual available
665 /// liquidity in a channel is just as likely to be at any point between our lower and upper
668 /// If this flag is *not* set, that PDF is `(x - 0.5*capacity) ^ 2`. That is, we use an
669 /// exponential curve which expects the liquidity of a channel to lie "at the edges". This
670 /// matches experimental results - most routing nodes do not aggressively rebalance their
671 /// channels and flows in the network are often unbalanced, leaving liquidity usually
674 /// Thus, for the "best" routes, leave this flag `false`. However, the flag does imply a number
675 /// of floating-point multiplications in the hottest routing code, which may lead to routing
676 /// performance degradation on some machines.
678 /// Default value: false
679 pub linear_success_probability: bool,
682 impl Default for ProbabilisticScoringFeeParameters {
683 fn default() -> Self {
685 base_penalty_msat: 500,
686 base_penalty_amount_multiplier_msat: 8192,
687 liquidity_penalty_multiplier_msat: 30_000,
688 liquidity_penalty_amount_multiplier_msat: 192,
689 manual_node_penalties: HashMap::new(),
690 anti_probing_penalty_msat: 250,
691 considered_impossible_penalty_msat: 1_0000_0000_000,
692 historical_liquidity_penalty_multiplier_msat: 10_000,
693 historical_liquidity_penalty_amount_multiplier_msat: 64,
694 linear_success_probability: false,
699 impl ProbabilisticScoringFeeParameters {
700 /// Marks the node with the given `node_id` as banned,
701 /// i.e it will be avoided during path finding.
702 pub fn add_banned(&mut self, node_id: &NodeId) {
703 self.manual_node_penalties.insert(*node_id, u64::max_value());
706 /// Marks all nodes in the given list as banned, i.e.,
707 /// they will be avoided during path finding.
708 pub fn add_banned_from_list(&mut self, node_ids: Vec<NodeId>) {
710 self.manual_node_penalties.insert(id, u64::max_value());
714 /// Removes the node with the given `node_id` from the list of nodes to avoid.
715 pub fn remove_banned(&mut self, node_id: &NodeId) {
716 self.manual_node_penalties.remove(node_id);
719 /// Sets a manual penalty for the given node.
720 pub fn set_manual_penalty(&mut self, node_id: &NodeId, penalty: u64) {
721 self.manual_node_penalties.insert(*node_id, penalty);
724 /// Removes the node with the given `node_id` from the list of manual penalties.
725 pub fn remove_manual_penalty(&mut self, node_id: &NodeId) {
726 self.manual_node_penalties.remove(node_id);
729 /// Clears the list of manual penalties that are applied during path finding.
730 pub fn clear_manual_penalties(&mut self) {
731 self.manual_node_penalties = HashMap::new();
736 impl ProbabilisticScoringFeeParameters {
737 fn zero_penalty() -> Self {
739 base_penalty_msat: 0,
740 base_penalty_amount_multiplier_msat: 0,
741 liquidity_penalty_multiplier_msat: 0,
742 liquidity_penalty_amount_multiplier_msat: 0,
743 historical_liquidity_penalty_multiplier_msat: 0,
744 historical_liquidity_penalty_amount_multiplier_msat: 0,
745 manual_node_penalties: HashMap::new(),
746 anti_probing_penalty_msat: 0,
747 considered_impossible_penalty_msat: 0,
748 linear_success_probability: true,
753 /// Parameters for configuring [`ProbabilisticScorer`].
755 /// Used to configure decay parameters that are static throughout the lifetime of the scorer.
756 /// these decay parameters affect the score of the channel penalty and are not changed on a
757 /// per-route penalty cost call.
758 #[derive(Copy, Clone)]
759 pub struct ProbabilisticScoringDecayParameters {
760 /// If we aren't learning any new datapoints for a channel, the historical liquidity bounds
761 /// tracking can simply live on with increasingly stale data. Instead, when a channel has not
762 /// seen a liquidity estimate update for this amount of time, the historical datapoints are
764 /// For an example of historical_no_updates_half_life being used see [`historical_estimated_channel_liquidity_probabilities`]
766 /// Note that after 16 or more half lives all historical data will be completely gone.
768 /// Default value: 14 days
770 /// [`historical_estimated_channel_liquidity_probabilities`]: ProbabilisticScorerUsingTime::historical_estimated_channel_liquidity_probabilities
771 pub historical_no_updates_half_life: Duration,
773 /// Whenever this amount of time elapses since the last update to a channel's liquidity bounds,
774 /// the distance from the bounds to "zero" is cut in half. In other words, the lower-bound on
775 /// the available liquidity is halved and the upper-bound moves half-way to the channel's total
778 /// Because halving the liquidity bounds grows the uncertainty on the channel's liquidity,
779 /// the penalty for an amount within the new bounds may change. See the [`ProbabilisticScorer`]
780 /// struct documentation for more info on the way the liquidity bounds are used.
782 /// For example, if the channel's capacity is 1 million sats, and the current upper and lower
783 /// liquidity bounds are 200,000 sats and 600,000 sats, after this amount of time the upper
784 /// and lower liquidity bounds will be decayed to 100,000 and 800,000 sats.
786 /// Default value: 6 hours
790 /// When built with the `no-std` feature, time will never elapse. Therefore, the channel
791 /// liquidity knowledge will never decay except when the bounds cross.
792 pub liquidity_offset_half_life: Duration,
795 impl Default for ProbabilisticScoringDecayParameters {
796 fn default() -> Self {
798 liquidity_offset_half_life: Duration::from_secs(6 * 60 * 60),
799 historical_no_updates_half_life: Duration::from_secs(60 * 60 * 24 * 14),
805 impl ProbabilisticScoringDecayParameters {
806 fn zero_penalty() -> Self {
808 liquidity_offset_half_life: Duration::from_secs(6 * 60 * 60),
809 historical_no_updates_half_life: Duration::from_secs(60 * 60 * 24 * 14),
814 /// Accounting for channel liquidity balance uncertainty.
816 /// Direction is defined in terms of [`NodeId`] partial ordering, where the source node is the
817 /// first node in the ordering of the channel's counterparties. Thus, swapping the two liquidity
818 /// offset fields gives the opposite direction.
819 struct ChannelLiquidity<T: Time> {
820 /// Lower channel liquidity bound in terms of an offset from zero.
821 min_liquidity_offset_msat: u64,
823 /// Upper channel liquidity bound in terms of an offset from the effective capacity.
824 max_liquidity_offset_msat: u64,
826 /// Time when the liquidity bounds were last modified.
829 min_liquidity_offset_history: HistoricalBucketRangeTracker,
830 max_liquidity_offset_history: HistoricalBucketRangeTracker,
833 /// A snapshot of [`ChannelLiquidity`] in one direction assuming a certain channel capacity and
834 /// decayed with a given half life.
835 struct DirectedChannelLiquidity<L: Deref<Target = u64>, BRT: Deref<Target = HistoricalBucketRangeTracker>, T: Time, U: Deref<Target = T>> {
836 min_liquidity_offset_msat: L,
837 max_liquidity_offset_msat: L,
838 liquidity_history: HistoricalMinMaxBuckets<BRT>,
842 decay_params: ProbabilisticScoringDecayParameters,
845 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
846 /// Creates a new scorer using the given scoring parameters for sending payments from a node
847 /// through a network graph.
848 pub fn new(decay_params: ProbabilisticScoringDecayParameters, network_graph: G, logger: L) -> Self {
853 channel_liquidities: HashMap::new(),
858 fn with_channel(mut self, short_channel_id: u64, liquidity: ChannelLiquidity<T>) -> Self {
859 assert!(self.channel_liquidities.insert(short_channel_id, liquidity).is_none());
863 /// Dump the contents of this scorer into the configured logger.
865 /// Note that this writes roughly one line per channel for which we have a liquidity estimate,
866 /// which may be a substantial amount of log output.
867 pub fn debug_log_liquidity_stats(&self) {
870 let graph = self.network_graph.read_only();
871 for (scid, liq) in self.channel_liquidities.iter() {
872 if let Some(chan_debug) = graph.channels().get(scid) {
873 let log_direction = |source, target| {
874 if let Some((directed_info, _)) = chan_debug.as_directed_to(target) {
875 let amt = directed_info.effective_capacity().as_msat();
876 let dir_liq = liq.as_directed(source, target, amt, self.decay_params);
878 let (min_buckets, max_buckets) = dir_liq.liquidity_history
879 .get_decayed_buckets(now, *dir_liq.last_updated,
880 self.decay_params.historical_no_updates_half_life)
881 .unwrap_or(([0; 32], [0; 32]));
883 log_debug!(self.logger, core::concat!(
884 "Liquidity from {} to {} via {} is in the range ({}, {}).\n",
885 "\tHistorical min liquidity bucket relative probabilities:\n",
886 "\t\t{} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {}\n",
887 "\tHistorical max liquidity bucket relative probabilities:\n",
888 "\t\t{} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {}"),
889 source, target, scid, dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat(),
890 min_buckets[ 0], min_buckets[ 1], min_buckets[ 2], min_buckets[ 3],
891 min_buckets[ 4], min_buckets[ 5], min_buckets[ 6], min_buckets[ 7],
892 min_buckets[ 8], min_buckets[ 9], min_buckets[10], min_buckets[11],
893 min_buckets[12], min_buckets[13], min_buckets[14], min_buckets[15],
894 min_buckets[16], min_buckets[17], min_buckets[18], min_buckets[19],
895 min_buckets[20], min_buckets[21], min_buckets[22], min_buckets[23],
896 min_buckets[24], min_buckets[25], min_buckets[26], min_buckets[27],
897 min_buckets[28], min_buckets[29], min_buckets[30], min_buckets[31],
898 // Note that the liquidity buckets are an offset from the edge, so we
899 // inverse the max order to get the probabilities from zero.
900 max_buckets[31], max_buckets[30], max_buckets[29], max_buckets[28],
901 max_buckets[27], max_buckets[26], max_buckets[25], max_buckets[24],
902 max_buckets[23], max_buckets[22], max_buckets[21], max_buckets[20],
903 max_buckets[19], max_buckets[18], max_buckets[17], max_buckets[16],
904 max_buckets[15], max_buckets[14], max_buckets[13], max_buckets[12],
905 max_buckets[11], max_buckets[10], max_buckets[ 9], max_buckets[ 8],
906 max_buckets[ 7], max_buckets[ 6], max_buckets[ 5], max_buckets[ 4],
907 max_buckets[ 3], max_buckets[ 2], max_buckets[ 1], max_buckets[ 0]);
909 log_debug!(self.logger, "No amount known for SCID {} from {:?} to {:?}", scid, source, target);
913 log_direction(&chan_debug.node_one, &chan_debug.node_two);
914 log_direction(&chan_debug.node_two, &chan_debug.node_one);
916 log_debug!(self.logger, "No network graph entry for SCID {}", scid);
921 /// Query the estimated minimum and maximum liquidity available for sending a payment over the
922 /// channel with `scid` towards the given `target` node.
923 pub fn estimated_channel_liquidity_range(&self, scid: u64, target: &NodeId) -> Option<(u64, u64)> {
924 let graph = self.network_graph.read_only();
926 if let Some(chan) = graph.channels().get(&scid) {
927 if let Some(liq) = self.channel_liquidities.get(&scid) {
928 if let Some((directed_info, source)) = chan.as_directed_to(target) {
929 let amt = directed_info.effective_capacity().as_msat();
930 let dir_liq = liq.as_directed(source, target, amt, self.decay_params);
931 return Some((dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat()));
938 /// Query the historical estimated minimum and maximum liquidity available for sending a
939 /// payment over the channel with `scid` towards the given `target` node.
941 /// Returns two sets of 32 buckets. The first set describes the lower-bound liquidity history,
942 /// the second set describes the upper-bound liquidity history. Each bucket describes the
943 /// relative frequency at which we've seen a liquidity bound in the bucket's range relative to
944 /// the channel's total capacity, on an arbitrary scale. Because the values are slowly decayed,
945 /// more recent data points are weighted more heavily than older datapoints.
947 /// Note that the range of each bucket varies by its location to provide more granular results
948 /// at the edges of a channel's capacity, where it is more likely to sit.
950 /// When scoring, the estimated probability that an upper-/lower-bound lies in a given bucket
951 /// is calculated by dividing that bucket's value with the total value of all buckets.
953 /// For example, using a lower bucket count for illustrative purposes, a value of
954 /// `[0, 0, 0, ..., 0, 32]` indicates that we believe the probability of a bound being very
955 /// close to the channel's capacity to be 100%, and have never (recently) seen it in any other
956 /// bucket. A value of `[31, 0, 0, ..., 0, 0, 32]` indicates we've seen the bound being both
957 /// in the top and bottom bucket, and roughly with similar (recent) frequency.
959 /// Because the datapoints are decayed slowly over time, values will eventually return to
960 /// `Some(([1; 32], [1; 32]))` and then to `None` once no datapoints remain.
962 /// In order to fetch a single success probability from the buckets provided here, as used in
963 /// the scoring model, see [`Self::historical_estimated_payment_success_probability`].
964 pub fn historical_estimated_channel_liquidity_probabilities(&self, scid: u64, target: &NodeId)
965 -> Option<([u16; 32], [u16; 32])> {
966 let graph = self.network_graph.read_only();
968 if let Some(chan) = graph.channels().get(&scid) {
969 if let Some(liq) = self.channel_liquidities.get(&scid) {
970 if let Some((directed_info, source)) = chan.as_directed_to(target) {
971 let amt = directed_info.effective_capacity().as_msat();
972 let dir_liq = liq.as_directed(source, target, amt, self.decay_params);
974 let (min_buckets, mut max_buckets) =
975 dir_liq.liquidity_history.get_decayed_buckets(
976 dir_liq.now, *dir_liq.last_updated,
977 self.decay_params.historical_no_updates_half_life
980 // Note that the liquidity buckets are an offset from the edge, so we inverse
981 // the max order to get the probabilities from zero.
982 max_buckets.reverse();
983 return Some((min_buckets, max_buckets));
990 /// Query the probability of payment success sending the given `amount_msat` over the channel
991 /// with `scid` towards the given `target` node, based on the historical estimated liquidity
994 /// These are the same bounds as returned by
995 /// [`Self::historical_estimated_channel_liquidity_probabilities`] (but not those returned by
996 /// [`Self::estimated_channel_liquidity_range`]).
997 pub fn historical_estimated_payment_success_probability(
998 &self, scid: u64, target: &NodeId, amount_msat: u64, params: &ProbabilisticScoringFeeParameters)
1000 let graph = self.network_graph.read_only();
1002 if let Some(chan) = graph.channels().get(&scid) {
1003 if let Some(liq) = self.channel_liquidities.get(&scid) {
1004 if let Some((directed_info, source)) = chan.as_directed_to(target) {
1005 let capacity_msat = directed_info.effective_capacity().as_msat();
1006 let dir_liq = liq.as_directed(source, target, capacity_msat, self.decay_params);
1008 return dir_liq.liquidity_history.calculate_success_probability_times_billion(
1009 dir_liq.now, *dir_liq.last_updated,
1010 self.decay_params.historical_no_updates_half_life, ¶ms, amount_msat,
1012 ).map(|p| p as f64 / (1024 * 1024 * 1024) as f64);
1020 impl<T: Time> ChannelLiquidity<T> {
1024 min_liquidity_offset_msat: 0,
1025 max_liquidity_offset_msat: 0,
1026 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1027 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1028 last_updated: T::now(),
1032 /// Returns a view of the channel liquidity directed from `source` to `target` assuming
1033 /// `capacity_msat`.
1035 &self, source: &NodeId, target: &NodeId, capacity_msat: u64, decay_params: ProbabilisticScoringDecayParameters
1036 ) -> DirectedChannelLiquidity<&u64, &HistoricalBucketRangeTracker, T, &T> {
1037 let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) =
1038 if source < target {
1039 (&self.min_liquidity_offset_msat, &self.max_liquidity_offset_msat,
1040 &self.min_liquidity_offset_history, &self.max_liquidity_offset_history)
1042 (&self.max_liquidity_offset_msat, &self.min_liquidity_offset_msat,
1043 &self.max_liquidity_offset_history, &self.min_liquidity_offset_history)
1046 DirectedChannelLiquidity {
1047 min_liquidity_offset_msat,
1048 max_liquidity_offset_msat,
1049 liquidity_history: HistoricalMinMaxBuckets {
1050 min_liquidity_offset_history,
1051 max_liquidity_offset_history,
1054 last_updated: &self.last_updated,
1056 decay_params: decay_params,
1060 /// Returns a mutable view of the channel liquidity directed from `source` to `target` assuming
1061 /// `capacity_msat`.
1063 &mut self, source: &NodeId, target: &NodeId, capacity_msat: u64, decay_params: ProbabilisticScoringDecayParameters
1064 ) -> DirectedChannelLiquidity<&mut u64, &mut HistoricalBucketRangeTracker, T, &mut T> {
1065 let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) =
1066 if source < target {
1067 (&mut self.min_liquidity_offset_msat, &mut self.max_liquidity_offset_msat,
1068 &mut self.min_liquidity_offset_history, &mut self.max_liquidity_offset_history)
1070 (&mut self.max_liquidity_offset_msat, &mut self.min_liquidity_offset_msat,
1071 &mut self.max_liquidity_offset_history, &mut self.min_liquidity_offset_history)
1074 DirectedChannelLiquidity {
1075 min_liquidity_offset_msat,
1076 max_liquidity_offset_msat,
1077 liquidity_history: HistoricalMinMaxBuckets {
1078 min_liquidity_offset_history,
1079 max_liquidity_offset_history,
1082 last_updated: &mut self.last_updated,
1084 decay_params: decay_params,
1089 /// Bounds `-log10` to avoid excessive liquidity penalties for payments with low success
1091 const NEGATIVE_LOG10_UPPER_BOUND: u64 = 2;
1093 /// The rough cutoff at which our precision falls off and we should stop bothering to try to log a
1094 /// ratio, as X in 1/X.
1095 const PRECISION_LOWER_BOUND_DENOMINATOR: u64 = approx::LOWER_BITS_BOUND;
1097 /// The divisor used when computing the amount penalty.
1098 const AMOUNT_PENALTY_DIVISOR: u64 = 1 << 20;
1099 const BASE_AMOUNT_PENALTY_DIVISOR: u64 = 1 << 30;
1101 /// Raises three `f64`s to the 3rd power, without `powi` because it requires `std` (dunno why).
1103 fn three_f64_pow_3(a: f64, b: f64, c: f64) -> (f64, f64, f64) {
1104 (a * a * a, b * b * b, c * c * c)
1107 /// Given liquidity bounds, calculates the success probability (in the form of a numerator and
1108 /// denominator) of an HTLC. This is a key assumption in our scoring models.
1110 /// Must not return a numerator or denominator greater than 2^31 for arguments less than 2^31.
1112 /// min_zero_implies_no_successes signals that a `min_liquidity_msat` of 0 means we've not
1113 /// (recently) seen an HTLC successfully complete over this channel.
1115 fn success_probability(
1116 amount_msat: u64, min_liquidity_msat: u64, max_liquidity_msat: u64, capacity_msat: u64,
1117 params: &ProbabilisticScoringFeeParameters, min_zero_implies_no_successes: bool,
1119 debug_assert!(min_liquidity_msat <= amount_msat);
1120 debug_assert!(amount_msat < max_liquidity_msat);
1121 debug_assert!(max_liquidity_msat <= capacity_msat);
1123 let (numerator, mut denominator) =
1124 if params.linear_success_probability {
1125 (max_liquidity_msat - amount_msat,
1126 (max_liquidity_msat - min_liquidity_msat).saturating_add(1))
1128 let capacity = capacity_msat as f64;
1129 let min = (min_liquidity_msat as f64) / capacity;
1130 let max = (max_liquidity_msat as f64) / capacity;
1131 let amount = (amount_msat as f64) / capacity;
1133 // Assume the channel has a probability density function of (x - 0.5)^2 for values from
1134 // 0 to 1 (where 1 is the channel's full capacity). The success probability given some
1135 // liquidity bounds is thus the integral under the curve from the amount to maximum
1136 // estimated liquidity, divided by the same integral from the minimum to the maximum
1137 // estimated liquidity bounds.
1139 // Because the integral from x to y is simply (y - 0.5)^3 - (x - 0.5)^3, we can
1140 // calculate the cumulative density function between the min/max bounds trivially. Note
1141 // that we don't bother to normalize the CDF to total to 1, as it will come out in the
1142 // division of num / den.
1143 let (max_pow, amt_pow, min_pow) = three_f64_pow_3(max - 0.5, amount - 0.5, min - 0.5);
1144 let num = max_pow - amt_pow;
1145 let den = max_pow - min_pow;
1147 // Because our numerator and denominator max out at 0.5^3 we need to multiply them by
1148 // quite a large factor to get something useful (ideally in the 2^30 range).
1149 const BILLIONISH: f64 = 1024.0 * 1024.0 * 1024.0;
1150 let numerator = (num * BILLIONISH) as u64 + 1;
1151 let denominator = (den * BILLIONISH) as u64 + 1;
1152 debug_assert!(numerator <= 1 << 30, "Got large numerator ({}) from float {}.", numerator, num);
1153 debug_assert!(denominator <= 1 << 30, "Got large denominator ({}) from float {}.", denominator, den);
1154 (numerator, denominator)
1157 if min_zero_implies_no_successes && min_liquidity_msat == 0 &&
1158 denominator < u64::max_value() / 21
1160 // If we have no knowledge of the channel, scale probability down by ~75%
1161 // Note that we prefer to increase the denominator rather than decrease the numerator as
1162 // the denominator is more likely to be larger and thus provide greater precision. This is
1163 // mostly an overoptimization but makes a large difference in tests.
1164 denominator = denominator * 21 / 16
1167 (numerator, denominator)
1170 impl<L: Deref<Target = u64>, BRT: Deref<Target = HistoricalBucketRangeTracker>, T: Time, U: Deref<Target = T>> DirectedChannelLiquidity< L, BRT, T, U> {
1171 /// Returns a liquidity penalty for routing the given HTLC `amount_msat` through the channel in
1173 fn penalty_msat(&self, amount_msat: u64, score_params: &ProbabilisticScoringFeeParameters) -> u64 {
1174 let available_capacity = self.capacity_msat;
1175 let max_liquidity_msat = self.max_liquidity_msat();
1176 let min_liquidity_msat = core::cmp::min(self.min_liquidity_msat(), max_liquidity_msat);
1178 let mut res = if amount_msat <= min_liquidity_msat {
1180 } else if amount_msat >= max_liquidity_msat {
1181 // Equivalent to hitting the else clause below with the amount equal to the effective
1182 // capacity and without any certainty on the liquidity upper bound, plus the
1183 // impossibility penalty.
1184 let negative_log10_times_2048 = NEGATIVE_LOG10_UPPER_BOUND * 2048;
1185 Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
1186 score_params.liquidity_penalty_multiplier_msat,
1187 score_params.liquidity_penalty_amount_multiplier_msat)
1188 .saturating_add(score_params.considered_impossible_penalty_msat)
1190 let (numerator, denominator) = success_probability(amount_msat,
1191 min_liquidity_msat, max_liquidity_msat, available_capacity, score_params, false);
1192 if denominator - numerator < denominator / PRECISION_LOWER_BOUND_DENOMINATOR {
1193 // If the failure probability is < 1.5625% (as 1 - numerator/denominator < 1/64),
1194 // don't bother trying to use the log approximation as it gets too noisy to be
1195 // particularly helpful, instead just round down to 0.
1198 let negative_log10_times_2048 =
1199 approx::negative_log10_times_2048(numerator, denominator);
1200 Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
1201 score_params.liquidity_penalty_multiplier_msat,
1202 score_params.liquidity_penalty_amount_multiplier_msat)
1206 if amount_msat >= available_capacity {
1207 // We're trying to send more than the capacity, use a max penalty.
1208 res = res.saturating_add(Self::combined_penalty_msat(amount_msat,
1209 NEGATIVE_LOG10_UPPER_BOUND * 2048,
1210 score_params.historical_liquidity_penalty_multiplier_msat,
1211 score_params.historical_liquidity_penalty_amount_multiplier_msat));
1215 if score_params.historical_liquidity_penalty_multiplier_msat != 0 ||
1216 score_params.historical_liquidity_penalty_amount_multiplier_msat != 0 {
1217 if let Some(cumulative_success_prob_times_billion) = self.liquidity_history
1218 .calculate_success_probability_times_billion(self.now, *self.last_updated,
1219 self.decay_params.historical_no_updates_half_life, score_params, amount_msat,
1222 let historical_negative_log10_times_2048 = approx::negative_log10_times_2048(cumulative_success_prob_times_billion + 1, 1024 * 1024 * 1024);
1223 res = res.saturating_add(Self::combined_penalty_msat(amount_msat,
1224 historical_negative_log10_times_2048, score_params.historical_liquidity_penalty_multiplier_msat,
1225 score_params.historical_liquidity_penalty_amount_multiplier_msat));
1227 // If we don't have any valid points (or, once decayed, we have less than a full
1228 // point), redo the non-historical calculation with no liquidity bounds tracked and
1229 // the historical penalty multipliers.
1230 let (numerator, denominator) = success_probability(amount_msat, 0,
1231 available_capacity, available_capacity, score_params, true);
1232 let negative_log10_times_2048 =
1233 approx::negative_log10_times_2048(numerator, denominator);
1234 res = res.saturating_add(Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
1235 score_params.historical_liquidity_penalty_multiplier_msat,
1236 score_params.historical_liquidity_penalty_amount_multiplier_msat));
1243 /// Computes the liquidity penalty from the penalty multipliers.
1245 fn combined_penalty_msat(amount_msat: u64, mut negative_log10_times_2048: u64,
1246 liquidity_penalty_multiplier_msat: u64, liquidity_penalty_amount_multiplier_msat: u64,
1248 negative_log10_times_2048 =
1249 negative_log10_times_2048.min(NEGATIVE_LOG10_UPPER_BOUND * 2048);
1251 // Upper bound the liquidity penalty to ensure some channel is selected.
1252 let liquidity_penalty_msat = negative_log10_times_2048
1253 .saturating_mul(liquidity_penalty_multiplier_msat) / 2048;
1254 let amount_penalty_msat = negative_log10_times_2048
1255 .saturating_mul(liquidity_penalty_amount_multiplier_msat)
1256 .saturating_mul(amount_msat) / 2048 / AMOUNT_PENALTY_DIVISOR;
1258 liquidity_penalty_msat.saturating_add(amount_penalty_msat)
1261 /// Returns the lower bound of the channel liquidity balance in this direction.
1263 fn min_liquidity_msat(&self) -> u64 {
1264 self.decayed_offset_msat(*self.min_liquidity_offset_msat)
1267 /// Returns the upper bound of the channel liquidity balance in this direction.
1269 fn max_liquidity_msat(&self) -> u64 {
1271 .saturating_sub(self.decayed_offset_msat(*self.max_liquidity_offset_msat))
1274 fn decayed_offset_msat(&self, offset_msat: u64) -> u64 {
1275 let half_life = self.decay_params.liquidity_offset_half_life.as_secs();
1277 // Decay the offset by the appropriate number of half lives. If half of the next half
1278 // life has passed, approximate an additional three-quarter life to help smooth out the
1280 let elapsed_time = self.now.duration_since(*self.last_updated).as_secs();
1281 let half_decays = elapsed_time / (half_life / 2);
1282 let decays = half_decays / 2;
1283 let decayed_offset_msat = offset_msat.checked_shr(decays as u32).unwrap_or(0);
1284 if half_decays % 2 == 0 {
1287 // 11_585 / 16_384 ~= core::f64::consts::FRAC_1_SQRT_2
1289 (decayed_offset_msat as u128 * 11_585 / 16_384) as u64
1297 impl<L: DerefMut<Target = u64>, BRT: DerefMut<Target = HistoricalBucketRangeTracker>, T: Time, U: DerefMut<Target = T>> DirectedChannelLiquidity<L, BRT, T, U> {
1298 /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat`.
1299 fn failed_at_channel<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
1300 let existing_max_msat = self.max_liquidity_msat();
1301 if amount_msat < existing_max_msat {
1302 log_debug!(logger, "Setting max liquidity of {} from {} to {}", chan_descr, existing_max_msat, amount_msat);
1303 self.set_max_liquidity_msat(amount_msat);
1305 log_trace!(logger, "Max liquidity of {} is {} (already less than or equal to {})",
1306 chan_descr, existing_max_msat, amount_msat);
1308 self.update_history_buckets(0);
1311 /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat` downstream.
1312 fn failed_downstream<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
1313 let existing_min_msat = self.min_liquidity_msat();
1314 if amount_msat > existing_min_msat {
1315 log_debug!(logger, "Setting min liquidity of {} from {} to {}", existing_min_msat, chan_descr, amount_msat);
1316 self.set_min_liquidity_msat(amount_msat);
1318 log_trace!(logger, "Min liquidity of {} is {} (already greater than or equal to {})",
1319 chan_descr, existing_min_msat, amount_msat);
1321 self.update_history_buckets(0);
1324 /// Adjusts the channel liquidity balance bounds when successfully routing `amount_msat`.
1325 fn successful<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
1326 let max_liquidity_msat = self.max_liquidity_msat().checked_sub(amount_msat).unwrap_or(0);
1327 log_debug!(logger, "Subtracting {} from max liquidity of {} (setting it to {})", amount_msat, chan_descr, max_liquidity_msat);
1328 self.set_max_liquidity_msat(max_liquidity_msat);
1329 self.update_history_buckets(amount_msat);
1332 /// Updates the history buckets for this channel. Because the history buckets track what we now
1333 /// know about the channel's state *prior to our payment* (i.e. what we assume is "steady
1334 /// state"), we allow the caller to set an offset applied to our liquidity bounds which
1335 /// represents the amount of the successful payment we just made.
1336 fn update_history_buckets(&mut self, bucket_offset_msat: u64) {
1337 let half_lives = self.now.duration_since(*self.last_updated).as_secs()
1338 .checked_div(self.decay_params.historical_no_updates_half_life.as_secs())
1339 .map(|v| v.try_into().unwrap_or(u32::max_value())).unwrap_or(u32::max_value());
1340 self.liquidity_history.min_liquidity_offset_history.time_decay_data(half_lives);
1341 self.liquidity_history.max_liquidity_offset_history.time_decay_data(half_lives);
1343 let min_liquidity_offset_msat = self.decayed_offset_msat(*self.min_liquidity_offset_msat);
1344 self.liquidity_history.min_liquidity_offset_history.track_datapoint(
1345 min_liquidity_offset_msat + bucket_offset_msat, self.capacity_msat
1347 let max_liquidity_offset_msat = self.decayed_offset_msat(*self.max_liquidity_offset_msat);
1348 self.liquidity_history.max_liquidity_offset_history.track_datapoint(
1349 max_liquidity_offset_msat.saturating_sub(bucket_offset_msat), self.capacity_msat
1353 /// Adjusts the lower bound of the channel liquidity balance in this direction.
1354 fn set_min_liquidity_msat(&mut self, amount_msat: u64) {
1355 *self.min_liquidity_offset_msat = amount_msat;
1356 *self.max_liquidity_offset_msat = if amount_msat > self.max_liquidity_msat() {
1359 self.decayed_offset_msat(*self.max_liquidity_offset_msat)
1361 *self.last_updated = self.now;
1364 /// Adjusts the upper bound of the channel liquidity balance in this direction.
1365 fn set_max_liquidity_msat(&mut self, amount_msat: u64) {
1366 *self.max_liquidity_offset_msat = self.capacity_msat.checked_sub(amount_msat).unwrap_or(0);
1367 *self.min_liquidity_offset_msat = if amount_msat < self.min_liquidity_msat() {
1370 self.decayed_offset_msat(*self.min_liquidity_offset_msat)
1372 *self.last_updated = self.now;
1376 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> ScoreLookUp for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1377 type ScoreParams = ProbabilisticScoringFeeParameters;
1378 fn channel_penalty_msat(
1379 &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage, score_params: &ProbabilisticScoringFeeParameters
1381 if let Some(penalty) = score_params.manual_node_penalties.get(target) {
1385 let base_penalty_msat = score_params.base_penalty_msat.saturating_add(
1386 score_params.base_penalty_amount_multiplier_msat
1387 .saturating_mul(usage.amount_msat) / BASE_AMOUNT_PENALTY_DIVISOR);
1389 let mut anti_probing_penalty_msat = 0;
1390 match usage.effective_capacity {
1391 EffectiveCapacity::ExactLiquidity { liquidity_msat: amount_msat } |
1392 EffectiveCapacity::HintMaxHTLC { amount_msat } =>
1394 if usage.amount_msat > amount_msat {
1395 return u64::max_value();
1397 return base_penalty_msat;
1400 EffectiveCapacity::Total { capacity_msat, htlc_maximum_msat } => {
1401 if htlc_maximum_msat >= capacity_msat/2 {
1402 anti_probing_penalty_msat = score_params.anti_probing_penalty_msat;
1408 let amount_msat = usage.amount_msat.saturating_add(usage.inflight_htlc_msat);
1409 let capacity_msat = usage.effective_capacity.as_msat();
1410 self.channel_liquidities
1411 .get(&short_channel_id)
1412 .unwrap_or(&ChannelLiquidity::new())
1413 .as_directed(source, target, capacity_msat, self.decay_params)
1414 .penalty_msat(amount_msat, score_params)
1415 .saturating_add(anti_probing_penalty_msat)
1416 .saturating_add(base_penalty_msat)
1420 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> ScoreUpdate for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1421 fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64) {
1422 let amount_msat = path.final_value_msat();
1423 log_trace!(self.logger, "Scoring path through to SCID {} as having failed at {} msat", short_channel_id, amount_msat);
1424 let network_graph = self.network_graph.read_only();
1425 for (hop_idx, hop) in path.hops.iter().enumerate() {
1426 let target = NodeId::from_pubkey(&hop.pubkey);
1427 let channel_directed_from_source = network_graph.channels()
1428 .get(&hop.short_channel_id)
1429 .and_then(|channel| channel.as_directed_to(&target));
1431 let at_failed_channel = hop.short_channel_id == short_channel_id;
1432 if at_failed_channel && hop_idx == 0 {
1433 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);
1436 // Only score announced channels.
1437 if let Some((channel, source)) = channel_directed_from_source {
1438 let capacity_msat = channel.effective_capacity().as_msat();
1439 if at_failed_channel {
1440 self.channel_liquidities
1441 .entry(hop.short_channel_id)
1442 .or_insert_with(ChannelLiquidity::new)
1443 .as_directed_mut(source, &target, capacity_msat, self.decay_params)
1444 .failed_at_channel(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1446 self.channel_liquidities
1447 .entry(hop.short_channel_id)
1448 .or_insert_with(ChannelLiquidity::new)
1449 .as_directed_mut(source, &target, capacity_msat, self.decay_params)
1450 .failed_downstream(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1453 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).",
1454 hop.short_channel_id);
1456 if at_failed_channel { break; }
1460 fn payment_path_successful(&mut self, path: &Path) {
1461 let amount_msat = path.final_value_msat();
1462 log_trace!(self.logger, "Scoring path through SCID {} as having succeeded at {} msat.",
1463 path.hops.split_last().map(|(hop, _)| hop.short_channel_id).unwrap_or(0), amount_msat);
1464 let network_graph = self.network_graph.read_only();
1465 for hop in &path.hops {
1466 let target = NodeId::from_pubkey(&hop.pubkey);
1467 let channel_directed_from_source = network_graph.channels()
1468 .get(&hop.short_channel_id)
1469 .and_then(|channel| channel.as_directed_to(&target));
1471 // Only score announced channels.
1472 if let Some((channel, source)) = channel_directed_from_source {
1473 let capacity_msat = channel.effective_capacity().as_msat();
1474 self.channel_liquidities
1475 .entry(hop.short_channel_id)
1476 .or_insert_with(ChannelLiquidity::new)
1477 .as_directed_mut(source, &target, capacity_msat, self.decay_params)
1478 .successful(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1480 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).",
1481 hop.short_channel_id);
1486 fn probe_failed(&mut self, path: &Path, short_channel_id: u64) {
1487 self.payment_path_failed(path, short_channel_id)
1490 fn probe_successful(&mut self, path: &Path) {
1491 self.payment_path_failed(path, u64::max_value())
1496 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Score for ProbabilisticScorerUsingTime<G, L, T>
1497 where L::Target: Logger {}
1500 const BITS: u32 = 64;
1501 const HIGHEST_BIT: u32 = BITS - 1;
1502 const LOWER_BITS: u32 = 6;
1503 pub(super) const LOWER_BITS_BOUND: u64 = 1 << LOWER_BITS;
1504 const LOWER_BITMASK: u64 = (1 << LOWER_BITS) - 1;
1506 /// Look-up table for `log10(x) * 2048` where row `i` is used for each `x` having `i` as the
1507 /// most significant bit. The next 4 bits of `x`, if applicable, are used for the second index.
1508 const LOG10_TIMES_2048: [[u16; (LOWER_BITS_BOUND) as usize]; BITS as usize] = [
1509 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1510 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1511 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1512 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
1513 [617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
1514 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
1515 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977,
1516 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977],
1517 [1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233,
1518 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431,
1519 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594,
1520 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731],
1521 [1850, 1850, 1850, 1850, 1850, 1850, 1850, 1850, 1954, 1954, 1954, 1954, 1954, 1954, 1954, 1954,
1522 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2133, 2133, 2133, 2133, 2133, 2133, 2133, 2133,
1523 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2281, 2281, 2281, 2281, 2281, 2281, 2281, 2281,
1524 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2409, 2409, 2409, 2409, 2409, 2409, 2409, 2409],
1525 [2466, 2466, 2466, 2466, 2520, 2520, 2520, 2520, 2571, 2571, 2571, 2571, 2619, 2619, 2619, 2619,
1526 2665, 2665, 2665, 2665, 2708, 2708, 2708, 2708, 2749, 2749, 2749, 2749, 2789, 2789, 2789, 2789,
1527 2827, 2827, 2827, 2827, 2863, 2863, 2863, 2863, 2898, 2898, 2898, 2898, 2931, 2931, 2931, 2931,
1528 2964, 2964, 2964, 2964, 2995, 2995, 2995, 2995, 3025, 3025, 3025, 3025, 3054, 3054, 3054, 3054],
1529 [3083, 3083, 3110, 3110, 3136, 3136, 3162, 3162, 3187, 3187, 3212, 3212, 3235, 3235, 3259, 3259,
1530 3281, 3281, 3303, 3303, 3324, 3324, 3345, 3345, 3366, 3366, 3386, 3386, 3405, 3405, 3424, 3424,
1531 3443, 3443, 3462, 3462, 3479, 3479, 3497, 3497, 3514, 3514, 3531, 3531, 3548, 3548, 3564, 3564,
1532 3580, 3580, 3596, 3596, 3612, 3612, 3627, 3627, 3642, 3642, 3656, 3656, 3671, 3671, 3685, 3685],
1533 [3699, 3713, 3726, 3740, 3753, 3766, 3779, 3791, 3804, 3816, 3828, 3840, 3852, 3864, 3875, 3886,
1534 3898, 3909, 3919, 3930, 3941, 3951, 3962, 3972, 3982, 3992, 4002, 4012, 4022, 4031, 4041, 4050,
1535 4060, 4069, 4078, 4087, 4096, 4105, 4114, 4122, 4131, 4139, 4148, 4156, 4164, 4173, 4181, 4189,
1536 4197, 4205, 4213, 4220, 4228, 4236, 4243, 4251, 4258, 4266, 4273, 4280, 4287, 4294, 4302, 4309],
1537 [4316, 4329, 4343, 4356, 4369, 4382, 4395, 4408, 4420, 4433, 4445, 4457, 4468, 4480, 4492, 4503,
1538 4514, 4525, 4536, 4547, 4557, 4568, 4578, 4589, 4599, 4609, 4619, 4629, 4638, 4648, 4657, 4667,
1539 4676, 4685, 4695, 4704, 4713, 4721, 4730, 4739, 4747, 4756, 4764, 4773, 4781, 4789, 4797, 4805,
1540 4813, 4821, 4829, 4837, 4845, 4852, 4860, 4867, 4875, 4882, 4889, 4897, 4904, 4911, 4918, 4925],
1541 [4932, 4946, 4959, 4973, 4986, 4999, 5012, 5024, 5037, 5049, 5061, 5073, 5085, 5097, 5108, 5119,
1542 5131, 5142, 5153, 5163, 5174, 5184, 5195, 5205, 5215, 5225, 5235, 5245, 5255, 5264, 5274, 5283,
1543 5293, 5302, 5311, 5320, 5329, 5338, 5347, 5355, 5364, 5372, 5381, 5389, 5397, 5406, 5414, 5422,
1544 5430, 5438, 5446, 5453, 5461, 5469, 5476, 5484, 5491, 5499, 5506, 5513, 5520, 5527, 5535, 5542],
1545 [5549, 5562, 5576, 5589, 5603, 5615, 5628, 5641, 5653, 5666, 5678, 5690, 5701, 5713, 5725, 5736,
1546 5747, 5758, 5769, 5780, 5790, 5801, 5811, 5822, 5832, 5842, 5852, 5862, 5871, 5881, 5890, 5900,
1547 5909, 5918, 5928, 5937, 5946, 5954, 5963, 5972, 5980, 5989, 5997, 6006, 6014, 6022, 6030, 6038,
1548 6046, 6054, 6062, 6070, 6078, 6085, 6093, 6100, 6108, 6115, 6122, 6130, 6137, 6144, 6151, 6158],
1549 [6165, 6179, 6192, 6206, 6219, 6232, 6245, 6257, 6270, 6282, 6294, 6306, 6318, 6330, 6341, 6352,
1550 6364, 6375, 6386, 6396, 6407, 6417, 6428, 6438, 6448, 6458, 6468, 6478, 6488, 6497, 6507, 6516,
1551 6526, 6535, 6544, 6553, 6562, 6571, 6580, 6588, 6597, 6605, 6614, 6622, 6630, 6639, 6647, 6655,
1552 6663, 6671, 6679, 6686, 6694, 6702, 6709, 6717, 6724, 6732, 6739, 6746, 6753, 6761, 6768, 6775],
1553 [6782, 6795, 6809, 6822, 6836, 6849, 6861, 6874, 6886, 6899, 6911, 6923, 6934, 6946, 6958, 6969,
1554 6980, 6991, 7002, 7013, 7023, 7034, 7044, 7055, 7065, 7075, 7085, 7095, 7104, 7114, 7124, 7133,
1555 7142, 7151, 7161, 7170, 7179, 7187, 7196, 7205, 7213, 7222, 7230, 7239, 7247, 7255, 7263, 7271,
1556 7279, 7287, 7295, 7303, 7311, 7318, 7326, 7333, 7341, 7348, 7355, 7363, 7370, 7377, 7384, 7391],
1557 [7398, 7412, 7425, 7439, 7452, 7465, 7478, 7490, 7503, 7515, 7527, 7539, 7551, 7563, 7574, 7585,
1558 7597, 7608, 7619, 7629, 7640, 7651, 7661, 7671, 7681, 7691, 7701, 7711, 7721, 7731, 7740, 7749,
1559 7759, 7768, 7777, 7786, 7795, 7804, 7813, 7821, 7830, 7838, 7847, 7855, 7864, 7872, 7880, 7888,
1560 7896, 7904, 7912, 7919, 7927, 7935, 7942, 7950, 7957, 7965, 7972, 7979, 7986, 7994, 8001, 8008],
1561 [8015, 8028, 8042, 8055, 8069, 8082, 8094, 8107, 8119, 8132, 8144, 8156, 8167, 8179, 8191, 8202,
1562 8213, 8224, 8235, 8246, 8256, 8267, 8277, 8288, 8298, 8308, 8318, 8328, 8337, 8347, 8357, 8366,
1563 8375, 8384, 8394, 8403, 8412, 8420, 8429, 8438, 8446, 8455, 8463, 8472, 8480, 8488, 8496, 8504,
1564 8512, 8520, 8528, 8536, 8544, 8551, 8559, 8566, 8574, 8581, 8588, 8596, 8603, 8610, 8617, 8624],
1565 [8631, 8645, 8659, 8672, 8685, 8698, 8711, 8723, 8736, 8748, 8760, 8772, 8784, 8796, 8807, 8818,
1566 8830, 8841, 8852, 8862, 8873, 8884, 8894, 8904, 8914, 8924, 8934, 8944, 8954, 8964, 8973, 8982,
1567 8992, 9001, 9010, 9019, 9028, 9037, 9046, 9054, 9063, 9071, 9080, 9088, 9097, 9105, 9113, 9121,
1568 9129, 9137, 9145, 9152, 9160, 9168, 9175, 9183, 9190, 9198, 9205, 9212, 9219, 9227, 9234, 9241],
1569 [9248, 9261, 9275, 9288, 9302, 9315, 9327, 9340, 9352, 9365, 9377, 9389, 9400, 9412, 9424, 9435,
1570 9446, 9457, 9468, 9479, 9490, 9500, 9510, 9521, 9531, 9541, 9551, 9561, 9570, 9580, 9590, 9599,
1571 9608, 9617, 9627, 9636, 9645, 9653, 9662, 9671, 9679, 9688, 9696, 9705, 9713, 9721, 9729, 9737,
1572 9745, 9753, 9761, 9769, 9777, 9784, 9792, 9799, 9807, 9814, 9821, 9829, 9836, 9843, 9850, 9857],
1573 [9864, 9878, 9892, 9905, 9918, 9931, 9944, 9956, 9969, 9981, 9993, 10005, 10017, 10029, 10040, 10051,
1574 10063, 10074, 10085, 10095, 10106, 10117, 10127, 10137, 10147, 10157, 10167, 10177, 10187, 10197, 10206, 10215,
1575 10225, 10234, 10243, 10252, 10261, 10270, 10279, 10287, 10296, 10304, 10313, 10321, 10330, 10338, 10346, 10354,
1576 10362, 10370, 10378, 10385, 10393, 10401, 10408, 10416, 10423, 10431, 10438, 10445, 10452, 10460, 10467, 10474],
1577 [10481, 10494, 10508, 10521, 10535, 10548, 10560, 10573, 10585, 10598, 10610, 10622, 10634, 10645, 10657, 10668,
1578 10679, 10690, 10701, 10712, 10723, 10733, 10743, 10754, 10764, 10774, 10784, 10794, 10803, 10813, 10823, 10832,
1579 10841, 10851, 10860, 10869, 10878, 10886, 10895, 10904, 10912, 10921, 10929, 10938, 10946, 10954, 10962, 10970,
1580 10978, 10986, 10994, 11002, 11010, 11017, 11025, 11032, 11040, 11047, 11054, 11062, 11069, 11076, 11083, 11090],
1581 [11097, 11111, 11125, 11138, 11151, 11164, 11177, 11189, 11202, 11214, 11226, 11238, 11250, 11262, 11273, 11284,
1582 11296, 11307, 11318, 11328, 11339, 11350, 11360, 11370, 11380, 11390, 11400, 11410, 11420, 11430, 11439, 11448,
1583 11458, 11467, 11476, 11485, 11494, 11503, 11512, 11520, 11529, 11538, 11546, 11554, 11563, 11571, 11579, 11587,
1584 11595, 11603, 11611, 11618, 11626, 11634, 11641, 11649, 11656, 11664, 11671, 11678, 11685, 11693, 11700, 11707],
1585 [11714, 11727, 11741, 11754, 11768, 11781, 11793, 11806, 11818, 11831, 11843, 11855, 11867, 11878, 11890, 11901,
1586 11912, 11923, 11934, 11945, 11956, 11966, 11976, 11987, 11997, 12007, 12017, 12027, 12036, 12046, 12056, 12065,
1587 12074, 12084, 12093, 12102, 12111, 12119, 12128, 12137, 12146, 12154, 12162, 12171, 12179, 12187, 12195, 12203,
1588 12211, 12219, 12227, 12235, 12243, 12250, 12258, 12265, 12273, 12280, 12287, 12295, 12302, 12309, 12316, 12323],
1589 [12330, 12344, 12358, 12371, 12384, 12397, 12410, 12423, 12435, 12447, 12459, 12471, 12483, 12495, 12506, 12517,
1590 12529, 12540, 12551, 12561, 12572, 12583, 12593, 12603, 12613, 12623, 12633, 12643, 12653, 12663, 12672, 12682,
1591 12691, 12700, 12709, 12718, 12727, 12736, 12745, 12753, 12762, 12771, 12779, 12787, 12796, 12804, 12812, 12820,
1592 12828, 12836, 12844, 12851, 12859, 12867, 12874, 12882, 12889, 12897, 12904, 12911, 12918, 12926, 12933, 12940],
1593 [12947, 12960, 12974, 12987, 13001, 13014, 13026, 13039, 13051, 13064, 13076, 13088, 13100, 13111, 13123, 13134,
1594 13145, 13156, 13167, 13178, 13189, 13199, 13209, 13220, 13230, 13240, 13250, 13260, 13269, 13279, 13289, 13298,
1595 13307, 13317, 13326, 13335, 13344, 13352, 13361, 13370, 13379, 13387, 13395, 13404, 13412, 13420, 13428, 13436,
1596 13444, 13452, 13460, 13468, 13476, 13483, 13491, 13498, 13506, 13513, 13521, 13528, 13535, 13542, 13549, 13556],
1597 [13563, 13577, 13591, 13604, 13617, 13630, 13643, 13656, 13668, 13680, 13692, 13704, 13716, 13728, 13739, 13750,
1598 13762, 13773, 13784, 13794, 13805, 13816, 13826, 13836, 13846, 13857, 13866, 13876, 13886, 13896, 13905, 13915,
1599 13924, 13933, 13942, 13951, 13960, 13969, 13978, 13986, 13995, 14004, 14012, 14020, 14029, 14037, 14045, 14053,
1600 14061, 14069, 14077, 14084, 14092, 14100, 14107, 14115, 14122, 14130, 14137, 14144, 14151, 14159, 14166, 14173],
1601 [14180, 14194, 14207, 14220, 14234, 14247, 14259, 14272, 14284, 14297, 14309, 14321, 14333, 14344, 14356, 14367,
1602 14378, 14389, 14400, 14411, 14422, 14432, 14443, 14453, 14463, 14473, 14483, 14493, 14502, 14512, 14522, 14531,
1603 14540, 14550, 14559, 14568, 14577, 14586, 14594, 14603, 14612, 14620, 14628, 14637, 14645, 14653, 14661, 14669,
1604 14677, 14685, 14693, 14701, 14709, 14716, 14724, 14731, 14739, 14746, 14754, 14761, 14768, 14775, 14782, 14789],
1605 [14796, 14810, 14824, 14837, 14850, 14863, 14876, 14889, 14901, 14913, 14925, 14937, 14949, 14961, 14972, 14984,
1606 14995, 15006, 15017, 15027, 15038, 15049, 15059, 15069, 15079, 15090, 15099, 15109, 15119, 15129, 15138, 15148,
1607 15157, 15166, 15175, 15184, 15193, 15202, 15211, 15219, 15228, 15237, 15245, 15253, 15262, 15270, 15278, 15286,
1608 15294, 15302, 15310, 15317, 15325, 15333, 15340, 15348, 15355, 15363, 15370, 15377, 15384, 15392, 15399, 15406],
1609 [15413, 15427, 15440, 15453, 15467, 15480, 15492, 15505, 15517, 15530, 15542, 15554, 15566, 15577, 15589, 15600,
1610 15611, 15622, 15633, 15644, 15655, 15665, 15676, 15686, 15696, 15706, 15716, 15726, 15736, 15745, 15755, 15764,
1611 15773, 15783, 15792, 15801, 15810, 15819, 15827, 15836, 15845, 15853, 15862, 15870, 15878, 15886, 15894, 15903,
1612 15910, 15918, 15926, 15934, 15942, 15949, 15957, 15964, 15972, 15979, 15987, 15994, 16001, 16008, 16015, 16022],
1613 [16029, 16043, 16057, 16070, 16083, 16096, 16109, 16122, 16134, 16146, 16158, 16170, 16182, 16194, 16205, 16217,
1614 16228, 16239, 16250, 16260, 16271, 16282, 16292, 16302, 16312, 16323, 16332, 16342, 16352, 16362, 16371, 16381,
1615 16390, 16399, 16408, 16417, 16426, 16435, 16444, 16452, 16461, 16470, 16478, 16486, 16495, 16503, 16511, 16519,
1616 16527, 16535, 16543, 16550, 16558, 16566, 16573, 16581, 16588, 16596, 16603, 16610, 16618, 16625, 16632, 16639],
1617 [16646, 16660, 16673, 16686, 16700, 16713, 16725, 16738, 16751, 16763, 16775, 16787, 16799, 16810, 16822, 16833,
1618 16844, 16855, 16866, 16877, 16888, 16898, 16909, 16919, 16929, 16939, 16949, 16959, 16969, 16978, 16988, 16997,
1619 17006, 17016, 17025, 17034, 17043, 17052, 17060, 17069, 17078, 17086, 17095, 17103, 17111, 17119, 17127, 17136,
1620 17143, 17151, 17159, 17167, 17175, 17182, 17190, 17197, 17205, 17212, 17220, 17227, 17234, 17241, 17248, 17255],
1621 [17262, 17276, 17290, 17303, 17316, 17329, 17342, 17355, 17367, 17379, 17391, 17403, 17415, 17427, 17438, 17450,
1622 17461, 17472, 17483, 17493, 17504, 17515, 17525, 17535, 17546, 17556, 17565, 17575, 17585, 17595, 17604, 17614,
1623 17623, 17632, 17641, 17650, 17659, 17668, 17677, 17685, 17694, 17703, 17711, 17719, 17728, 17736, 17744, 17752,
1624 17760, 17768, 17776, 17784, 17791, 17799, 17806, 17814, 17821, 17829, 17836, 17843, 17851, 17858, 17865, 17872],
1625 [17879, 17893, 17906, 17920, 17933, 17946, 17958, 17971, 17984, 17996, 18008, 18020, 18032, 18043, 18055, 18066,
1626 18077, 18088, 18099, 18110, 18121, 18131, 18142, 18152, 18162, 18172, 18182, 18192, 18202, 18211, 18221, 18230,
1627 18239, 18249, 18258, 18267, 18276, 18285, 18293, 18302, 18311, 18319, 18328, 18336, 18344, 18352, 18360, 18369,
1628 18377, 18384, 18392, 18400, 18408, 18415, 18423, 18430, 18438, 18445, 18453, 18460, 18467, 18474, 18481, 18488],
1629 [18495, 18509, 18523, 18536, 18549, 18562, 18575, 18588, 18600, 18612, 18624, 18636, 18648, 18660, 18671, 18683,
1630 18694, 18705, 18716, 18726, 18737, 18748, 18758, 18768, 18779, 18789, 18799, 18808, 18818, 18828, 18837, 18847,
1631 18856, 18865, 18874, 18883, 18892, 18901, 18910, 18919, 18927, 18936, 18944, 18952, 18961, 18969, 18977, 18985,
1632 18993, 19001, 19009, 19017, 19024, 19032, 19039, 19047, 19054, 19062, 19069, 19076, 19084, 19091, 19098, 19105],
1633 [19112, 19126, 19139, 19153, 19166, 19179, 19191, 19204, 19217, 19229, 19241, 19253, 19265, 19276, 19288, 19299,
1634 19310, 19321, 19332, 19343, 19354, 19364, 19375, 19385, 19395, 19405, 19415, 19425, 19435, 19444, 19454, 19463,
1635 19472, 19482, 19491, 19500, 19509, 19518, 19526, 19535, 19544, 19552, 19561, 19569, 19577, 19585, 19594, 19602,
1636 19610, 19617, 19625, 19633, 19641, 19648, 19656, 19663, 19671, 19678, 19686, 19693, 19700, 19707, 19714, 19721],
1637 [19728, 19742, 19756, 19769, 19782, 19795, 19808, 19821, 19833, 19845, 19857, 19869, 19881, 19893, 19904, 19916,
1638 19927, 19938, 19949, 19960, 19970, 19981, 19991, 20001, 20012, 20022, 20032, 20041, 20051, 20061, 20070, 20080,
1639 20089, 20098, 20107, 20116, 20125, 20134, 20143, 20152, 20160, 20169, 20177, 20185, 20194, 20202, 20210, 20218,
1640 20226, 20234, 20242, 20250, 20257, 20265, 20272, 20280, 20287, 20295, 20302, 20309, 20317, 20324, 20331, 20338],
1641 [20345, 20359, 20372, 20386, 20399, 20412, 20425, 20437, 20450, 20462, 20474, 20486, 20498, 20509, 20521, 20532,
1642 20543, 20554, 20565, 20576, 20587, 20597, 20608, 20618, 20628, 20638, 20648, 20658, 20668, 20677, 20687, 20696,
1643 20705, 20715, 20724, 20733, 20742, 20751, 20759, 20768, 20777, 20785, 20794, 20802, 20810, 20818, 20827, 20835,
1644 20843, 20850, 20858, 20866, 20874, 20881, 20889, 20896, 20904, 20911, 20919, 20926, 20933, 20940, 20947, 20954],
1645 [20961, 20975, 20989, 21002, 21015, 21028, 21041, 21054, 21066, 21078, 21090, 21102, 21114, 21126, 21137, 21149,
1646 21160, 21171, 21182, 21193, 21203, 21214, 21224, 21234, 21245, 21255, 21265, 21274, 21284, 21294, 21303, 21313,
1647 21322, 21331, 21340, 21349, 21358, 21367, 21376, 21385, 21393, 21402, 21410, 21418, 21427, 21435, 21443, 21451,
1648 21459, 21467, 21475, 21483, 21490, 21498, 21505, 21513, 21520, 21528, 21535, 21542, 21550, 21557, 21564, 21571],
1649 [21578, 21592, 21605, 21619, 21632, 21645, 21658, 21670, 21683, 21695, 21707, 21719, 21731, 21742, 21754, 21765,
1650 21776, 21787, 21798, 21809, 21820, 21830, 21841, 21851, 21861, 21871, 21881, 21891, 21901, 21910, 21920, 21929,
1651 21938, 21948, 21957, 21966, 21975, 21984, 21992, 22001, 22010, 22018, 22027, 22035, 22043, 22051, 22060, 22068,
1652 22076, 22083, 22091, 22099, 22107, 22114, 22122, 22129, 22137, 22144, 22152, 22159, 22166, 22173, 22180, 22187],
1653 [22194, 22208, 22222, 22235, 22248, 22261, 22274, 22287, 22299, 22311, 22323, 22335, 22347, 22359, 22370, 22382,
1654 22393, 22404, 22415, 22426, 22436, 22447, 22457, 22467, 22478, 22488, 22498, 22507, 22517, 22527, 22536, 22546,
1655 22555, 22564, 22573, 22582, 22591, 22600, 22609, 22618, 22626, 22635, 22643, 22651, 22660, 22668, 22676, 22684,
1656 22692, 22700, 22708, 22716, 22723, 22731, 22738, 22746, 22753, 22761, 22768, 22775, 22783, 22790, 22797, 22804],
1657 [22811, 22825, 22838, 22852, 22865, 22878, 22891, 22903, 22916, 22928, 22940, 22952, 22964, 22975, 22987, 22998,
1658 23009, 23020, 23031, 23042, 23053, 23063, 23074, 23084, 23094, 23104, 23114, 23124, 23134, 23143, 23153, 23162,
1659 23171, 23181, 23190, 23199, 23208, 23217, 23225, 23234, 23243, 23251, 23260, 23268, 23276, 23284, 23293, 23301,
1660 23309, 23316, 23324, 23332, 23340, 23347, 23355, 23363, 23370, 23377, 23385, 23392, 23399, 23406, 23413, 23420],
1661 [23427, 23441, 23455, 23468, 23481, 23494, 23507, 23520, 23532, 23544, 23556, 23568, 23580, 23592, 23603, 23615,
1662 23626, 23637, 23648, 23659, 23669, 23680, 23690, 23700, 23711, 23721, 23731, 23740, 23750, 23760, 23769, 23779,
1663 23788, 23797, 23806, 23815, 23824, 23833, 23842, 23851, 23859, 23868, 23876, 23884, 23893, 23901, 23909, 23917,
1664 23925, 23933, 23941, 23949, 23956, 23964, 23972, 23979, 23986, 23994, 24001, 24008, 24016, 24023, 24030, 24037],
1665 [24044, 24058, 24071, 24085, 24098, 24111, 24124, 24136, 24149, 24161, 24173, 24185, 24197, 24208, 24220, 24231,
1666 24242, 24253, 24264, 24275, 24286, 24296, 24307, 24317, 24327, 24337, 24347, 24357, 24367, 24376, 24386, 24395,
1667 24405, 24414, 24423, 24432, 24441, 24450, 24458, 24467, 24476, 24484, 24493, 24501, 24509, 24517, 24526, 24534,
1668 24542, 24550, 24557, 24565, 24573, 24580, 24588, 24596, 24603, 24610, 24618, 24625, 24632, 24639, 24646, 24653],
1669 [24660, 24674, 24688, 24701, 24714, 24727, 24740, 24753, 24765, 24777, 24790, 24801, 24813, 24825, 24836, 24848,
1670 24859, 24870, 24881, 24892, 24902, 24913, 24923, 24933, 24944, 24954, 24964, 24973, 24983, 24993, 25002, 25012,
1671 25021, 25030, 25039, 25048, 25057, 25066, 25075, 25084, 25092, 25101, 25109, 25117, 25126, 25134, 25142, 25150,
1672 25158, 25166, 25174, 25182, 25189, 25197, 25205, 25212, 25219, 25227, 25234, 25241, 25249, 25256, 25263, 25270],
1673 [25277, 25291, 25304, 25318, 25331, 25344, 25357, 25369, 25382, 25394, 25406, 25418, 25430, 25441, 25453, 25464,
1674 25475, 25486, 25497, 25508, 25519, 25529, 25540, 25550, 25560, 25570, 25580, 25590, 25600, 25609, 25619, 25628,
1675 25638, 25647, 25656, 25665, 25674, 25683, 25691, 25700, 25709, 25717, 25726, 25734, 25742, 25750, 25759, 25767,
1676 25775, 25783, 25790, 25798, 25806, 25813, 25821, 25829, 25836, 25843, 25851, 25858, 25865, 25872, 25879, 25886],
1677 [25893, 25907, 25921, 25934, 25947, 25960, 25973, 25986, 25998, 26010, 26023, 26034, 26046, 26058, 26069, 26081,
1678 26092, 26103, 26114, 26125, 26135, 26146, 26156, 26166, 26177, 26187, 26197, 26206, 26216, 26226, 26235, 26245,
1679 26254, 26263, 26272, 26281, 26290, 26299, 26308, 26317, 26325, 26334, 26342, 26351, 26359, 26367, 26375, 26383,
1680 26391, 26399, 26407, 26415, 26422, 26430, 26438, 26445, 26453, 26460, 26467, 26474, 26482, 26489, 26496, 26503],
1681 [26510, 26524, 26537, 26551, 26564, 26577, 26590, 26602, 26615, 26627, 26639, 26651, 26663, 26674, 26686, 26697,
1682 26708, 26719, 26730, 26741, 26752, 26762, 26773, 26783, 26793, 26803, 26813, 26823, 26833, 26842, 26852, 26861,
1683 26871, 26880, 26889, 26898, 26907, 26916, 26924, 26933, 26942, 26950, 26959, 26967, 26975, 26983, 26992, 27000,
1684 27008, 27016, 27023, 27031, 27039, 27046, 27054, 27062, 27069, 27076, 27084, 27091, 27098, 27105, 27112, 27119],
1685 [27126, 27140, 27154, 27167, 27180, 27193, 27206, 27219, 27231, 27243, 27256, 27267, 27279, 27291, 27302, 27314,
1686 27325, 27336, 27347, 27358, 27368, 27379, 27389, 27399, 27410, 27420, 27430, 27439, 27449, 27459, 27468, 27478,
1687 27487, 27496, 27505, 27514, 27523, 27532, 27541, 27550, 27558, 27567, 27575, 27584, 27592, 27600, 27608, 27616,
1688 27624, 27632, 27640, 27648, 27655, 27663, 27671, 27678, 27686, 27693, 27700, 27707, 27715, 27722, 27729, 27736],
1689 [27743, 27757, 27770, 27784, 27797, 27810, 27823, 27835, 27848, 27860, 27872, 27884, 27896, 27907, 27919, 27930,
1690 27941, 27952, 27963, 27974, 27985, 27995, 28006, 28016, 28026, 28036, 28046, 28056, 28066, 28075, 28085, 28094,
1691 28104, 28113, 28122, 28131, 28140, 28149, 28157, 28166, 28175, 28183, 28192, 28200, 28208, 28217, 28225, 28233,
1692 28241, 28249, 28256, 28264, 28272, 28280, 28287, 28295, 28302, 28309, 28317, 28324, 28331, 28338, 28345, 28352],
1693 [28359, 28373, 28387, 28400, 28413, 28426, 28439, 28452, 28464, 28476, 28489, 28501, 28512, 28524, 28535, 28547,
1694 28558, 28569, 28580, 28591, 28601, 28612, 28622, 28633, 28643, 28653, 28663, 28672, 28682, 28692, 28701, 28711,
1695 28720, 28729, 28738, 28747, 28756, 28765, 28774, 28783, 28791, 28800, 28808, 28817, 28825, 28833, 28841, 28849,
1696 28857, 28865, 28873, 28881, 28888, 28896, 28904, 28911, 28919, 28926, 28933, 28941, 28948, 28955, 28962, 28969],
1697 [28976, 28990, 29003, 29017, 29030, 29043, 29056, 29068, 29081, 29093, 29105, 29117, 29129, 29140, 29152, 29163,
1698 29174, 29185, 29196, 29207, 29218, 29228, 29239, 29249, 29259, 29269, 29279, 29289, 29299, 29308, 29318, 29327,
1699 29337, 29346, 29355, 29364, 29373, 29382, 29390, 29399, 29408, 29416, 29425, 29433, 29441, 29450, 29458, 29466,
1700 29474, 29482, 29489, 29497, 29505, 29513, 29520, 29528, 29535, 29542, 29550, 29557, 29564, 29571, 29578, 29585],
1701 [29592, 29606, 29620, 29633, 29646, 29659, 29672, 29685, 29697, 29709, 29722, 29734, 29745, 29757, 29768, 29780,
1702 29791, 29802, 29813, 29824, 29834, 29845, 29855, 29866, 29876, 29886, 29896, 29906, 29915, 29925, 29934, 29944,
1703 29953, 29962, 29971, 29980, 29989, 29998, 30007, 30016, 30024, 30033, 30041, 30050, 30058, 30066, 30074, 30082,
1704 30090, 30098, 30106, 30114, 30121, 30129, 30137, 30144, 30152, 30159, 30166, 30174, 30181, 30188, 30195, 30202],
1705 [30209, 30223, 30236, 30250, 30263, 30276, 30289, 30301, 30314, 30326, 30338, 30350, 30362, 30373, 30385, 30396,
1706 30407, 30418, 30429, 30440, 30451, 30461, 30472, 30482, 30492, 30502, 30512, 30522, 30532, 30541, 30551, 30560,
1707 30570, 30579, 30588, 30597, 30606, 30615, 30624, 30632, 30641, 30649, 30658, 30666, 30674, 30683, 30691, 30699,
1708 30707, 30715, 30722, 30730, 30738, 30746, 30753, 30761, 30768, 30775, 30783, 30790, 30797, 30804, 30811, 30818],
1709 [30825, 30839, 30853, 30866, 30879, 30892, 30905, 30918, 30930, 30943, 30955, 30967, 30978, 30990, 31001, 31013,
1710 31024, 31035, 31046, 31057, 31067, 31078, 31088, 31099, 31109, 31119, 31129, 31139, 31148, 31158, 31167, 31177,
1711 31186, 31195, 31204, 31213, 31222, 31231, 31240, 31249, 31257, 31266, 31274, 31283, 31291, 31299, 31307, 31315,
1712 31323, 31331, 31339, 31347, 31354, 31362, 31370, 31377, 31385, 31392, 31399, 31407, 31414, 31421, 31428, 31435],
1713 [31442, 31456, 31469, 31483, 31496, 31509, 31522, 31534, 31547, 31559, 31571, 31583, 31595, 31606, 31618, 31629,
1714 31640, 31652, 31662, 31673, 31684, 31694, 31705, 31715, 31725, 31735, 31745, 31755, 31765, 31774, 31784, 31793,
1715 31803, 31812, 31821, 31830, 31839, 31848, 31857, 31865, 31874, 31882, 31891, 31899, 31907, 31916, 31924, 31932,
1716 31940, 31948, 31955, 31963, 31971, 31979, 31986, 31994, 32001, 32008, 32016, 32023, 32030, 32037, 32044, 32052],
1717 [32058, 32072, 32086, 32099, 32112, 32125, 32138, 32151, 32163, 32176, 32188, 32200, 32211, 32223, 32234, 32246,
1718 32257, 32268, 32279, 32290, 32300, 32311, 32321, 32332, 32342, 32352, 32362, 32372, 32381, 32391, 32400, 32410,
1719 32419, 32428, 32437, 32446, 32455, 32464, 32473, 32482, 32490, 32499, 32507, 32516, 32524, 32532, 32540, 32548,
1720 32556, 32564, 32572, 32580, 32587, 32595, 32603, 32610, 32618, 32625, 32632, 32640, 32647, 32654, 32661, 32668],
1721 [32675, 32689, 32702, 32716, 32729, 32742, 32755, 32767, 32780, 32792, 32804, 32816, 32828, 32839, 32851, 32862,
1722 32873, 32885, 32895, 32906, 32917, 32927, 32938, 32948, 32958, 32968, 32978, 32988, 32998, 33007, 33017, 33026,
1723 33036, 33045, 33054, 33063, 33072, 33081, 33090, 33098, 33107, 33115, 33124, 33132, 33140, 33149, 33157, 33165,
1724 33173, 33181, 33188, 33196, 33204, 33212, 33219, 33227, 33234, 33241, 33249, 33256, 33263, 33270, 33278, 33285],
1725 [33292, 33305, 33319, 33332, 33345, 33358, 33371, 33384, 33396, 33409, 33421, 33433, 33444, 33456, 33467, 33479,
1726 33490, 33501, 33512, 33523, 33533, 33544, 33554, 33565, 33575, 33585, 33595, 33605, 33614, 33624, 33633, 33643,
1727 33652, 33661, 33670, 33680, 33688, 33697, 33706, 33715, 33723, 33732, 33740, 33749, 33757, 33765, 33773, 33781,
1728 33789, 33797, 33805, 33813, 33820, 33828, 33836, 33843, 33851, 33858, 33865, 33873, 33880, 33887, 33894, 33901],
1729 [33908, 33922, 33935, 33949, 33962, 33975, 33988, 34000, 34013, 34025, 34037, 34049, 34061, 34072, 34084, 34095,
1730 34106, 34118, 34128, 34139, 34150, 34160, 34171, 34181, 34191, 34201, 34211, 34221, 34231, 34240, 34250, 34259,
1731 34269, 34278, 34287, 34296, 34305, 34314, 34323, 34331, 34340, 34348, 34357, 34365, 34373, 34382, 34390, 34398,
1732 34406, 34414, 34422, 34429, 34437, 34445, 34452, 34460, 34467, 34475, 34482, 34489, 34496, 34503, 34511, 34518],
1733 [34525, 34538, 34552, 34565, 34578, 34591, 34604, 34617, 34629, 34642, 34654, 34666, 34677, 34689, 34700, 34712,
1734 34723, 34734, 34745, 34756, 34766, 34777, 34787, 34798, 34808, 34818, 34828, 34838, 34847, 34857, 34866, 34876,
1735 34885, 34894, 34904, 34913, 34921, 34930, 34939, 34948, 34956, 34965, 34973, 34982, 34990, 34998, 35006, 35014,
1736 35022, 35030, 35038, 35046, 35053, 35061, 35069, 35076, 35084, 35091, 35098, 35106, 35113, 35120, 35127, 35134],
1737 [35141, 35155, 35168, 35182, 35195, 35208, 35221, 35233, 35246, 35258, 35270, 35282, 35294, 35306, 35317, 35328,
1738 35340, 35351, 35361, 35372, 35383, 35393, 35404, 35414, 35424, 35434, 35444, 35454, 35464, 35473, 35483, 35492,
1739 35502, 35511, 35520, 35529, 35538, 35547, 35556, 35564, 35573, 35581, 35590, 35598, 35606, 35615, 35623, 35631,
1740 35639, 35647, 35655, 35662, 35670, 35678, 35685, 35693, 35700, 35708, 35715, 35722, 35729, 35736, 35744, 35751],
1741 [35758, 35771, 35785, 35798, 35811, 35824, 35837, 35850, 35862, 35875, 35887, 35899, 35910, 35922, 35934, 35945,
1742 35956, 35967, 35978, 35989, 35999, 36010, 36020, 36031, 36041, 36051, 36061, 36071, 36080, 36090, 36099, 36109,
1743 36118, 36127, 36137, 36146, 36154, 36163, 36172, 36181, 36189, 36198, 36206, 36215, 36223, 36231, 36239, 36247,
1744 36255, 36263, 36271, 36279, 36287, 36294, 36302, 36309, 36317, 36324, 36331, 36339, 36346, 36353, 36360, 36367],
1745 [36374, 36388, 36401, 36415, 36428, 36441, 36454, 36466, 36479, 36491, 36503, 36515, 36527, 36539, 36550, 36561,
1746 36573, 36584, 36594, 36605, 36616, 36626, 36637, 36647, 36657, 36667, 36677, 36687, 36697, 36706, 36716, 36725,
1747 36735, 36744, 36753, 36762, 36771, 36780, 36789, 36797, 36806, 36814, 36823, 36831, 36839, 36848, 36856, 36864,
1748 36872, 36880, 36888, 36895, 36903, 36911, 36918, 36926, 36933, 36941, 36948, 36955, 36962, 36969, 36977, 36984],
1749 [36991, 37004, 37018, 37031, 37044, 37057, 37070, 37083, 37095, 37108, 37120, 37132, 37143, 37155, 37167, 37178,
1750 37189, 37200, 37211, 37222, 37232, 37243, 37253, 37264, 37274, 37284, 37294, 37304, 37313, 37323, 37332, 37342,
1751 37351, 37360, 37370, 37379, 37388, 37396, 37405, 37414, 37422, 37431, 37439, 37448, 37456, 37464, 37472, 37480,
1752 37488, 37496, 37504, 37512, 37520, 37527, 37535, 37542, 37550, 37557, 37564, 37572, 37579, 37586, 37593, 37600],
1753 [37607, 37621, 37634, 37648, 37661, 37674, 37687, 37699, 37712, 37724, 37736, 37748, 37760, 37772, 37783, 37794,
1754 37806, 37817, 37828, 37838, 37849, 37859, 37870, 37880, 37890, 37900, 37910, 37920, 37930, 37939, 37949, 37958,
1755 37968, 37977, 37986, 37995, 38004, 38013, 38022, 38030, 38039, 38047, 38056, 38064, 38072, 38081, 38089, 38097,
1756 38105, 38113, 38121, 38128, 38136, 38144, 38151, 38159, 38166, 38174, 38181, 38188, 38195, 38202, 38210, 38217],
1757 [38224, 38237, 38251, 38264, 38278, 38290, 38303, 38316, 38328, 38341, 38353, 38365, 38376, 38388, 38400, 38411,
1758 38422, 38433, 38444, 38455, 38465, 38476, 38486, 38497, 38507, 38517, 38527, 38537, 38546, 38556, 38565, 38575,
1759 38584, 38593, 38603, 38612, 38621, 38629, 38638, 38647, 38655, 38664, 38672, 38681, 38689, 38697, 38705, 38713,
1760 38721, 38729, 38737, 38745, 38753, 38760, 38768, 38775, 38783, 38790, 38797, 38805, 38812, 38819, 38826, 38833],
1761 [38840, 38854, 38867, 38881, 38894, 38907, 38920, 38932, 38945, 38957, 38969, 38981, 38993, 39005, 39016, 39027,
1762 39039, 39050, 39061, 39071, 39082, 39092, 39103, 39113, 39123, 39133, 39143, 39153, 39163, 39172, 39182, 39191,
1763 39201, 39210, 39219, 39228, 39237, 39246, 39255, 39263, 39272, 39280, 39289, 39297, 39305, 39314, 39322, 39330,
1764 39338, 39346, 39354, 39361, 39369, 39377, 39384, 39392, 39399, 39407, 39414, 39421, 39428, 39436, 39443, 39450],
1767 /// Approximate `log10(numerator / denominator) * 2048` using a look-up table.
1769 pub fn negative_log10_times_2048(numerator: u64, denominator: u64) -> u64 {
1770 // Multiply the -1 through to avoid needing to use signed numbers.
1771 (log10_times_2048(denominator) - log10_times_2048(numerator)) as u64
1775 fn log10_times_2048(x: u64) -> u16 {
1776 debug_assert_ne!(x, 0);
1777 let most_significant_bit = HIGHEST_BIT - x.leading_zeros();
1778 let lower_bits = (x >> most_significant_bit.saturating_sub(LOWER_BITS)) & LOWER_BITMASK;
1779 LOG10_TIMES_2048[most_significant_bit as usize][lower_bits as usize]
1787 fn prints_negative_log10_times_2048_lookup_table() {
1788 for msb in 0..BITS {
1789 for i in 0..LOWER_BITS_BOUND {
1790 let x = ((LOWER_BITS_BOUND + i) << (HIGHEST_BIT - LOWER_BITS)) >> (HIGHEST_BIT - msb);
1791 let log10_times_2048 = ((x as f64).log10() * 2048.0).round() as u16;
1792 assert_eq!(log10_times_2048, LOG10_TIMES_2048[msb as usize][i as usize]);
1794 if i % LOWER_BITS_BOUND == 0 {
1795 print!("\t\t[{}, ", log10_times_2048);
1796 } else if i % LOWER_BITS_BOUND == LOWER_BITS_BOUND - 1 {
1797 println!("{}],", log10_times_2048);
1798 } else if i % (LOWER_BITS_BOUND/4) == LOWER_BITS_BOUND/4 - 1 {
1799 print!("{},\n\t\t\t", log10_times_2048);
1801 print!("{}, ", log10_times_2048);
1809 mod bucketed_history {
1812 // Because liquidity is often skewed heavily in one direction, we store historical state
1813 // distribution in buckets of different size. For backwards compatibility, buckets of size 1/8th
1814 // must fit evenly into the buckets here.
1816 // The smallest bucket is 2^-14th of the channel, for each of our 32 buckets here we define the
1817 // width of the bucket in 2^14'ths of the channel. This increases exponentially until we reach
1818 // a full 16th of the channel's capacity, which is reapeated a few times for backwards
1819 // compatibility. The four middle buckets represent full octiles of the channel's capacity.
1821 // For a 1 BTC channel, this let's us differentiate between failures in the bottom 6k sats, or
1822 // between the 12,000th sat and 24,000th sat, while only needing to store and operate on 32
1823 // buckets in total.
1825 const BUCKET_START_POS: [u16; 33] = [
1826 0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 3072, 4096, 6144, 8192, 10240, 12288,
1827 13312, 14336, 15360, 15872, 16128, 16256, 16320, 16352, 16368, 16376, 16380, 16382, 16383, 16384,
1830 const LEGACY_TO_BUCKET_RANGE: [(u8, u8); 8] = [
1831 (0, 12), (12, 14), (14, 15), (15, 16), (16, 17), (17, 18), (18, 20), (20, 32)
1834 const POSITION_TICKS: u16 = 1 << 14;
1836 fn pos_to_bucket(pos: u16) -> usize {
1837 for bucket in 0..32 {
1838 if pos < BUCKET_START_POS[bucket + 1] {
1842 debug_assert!(false);
1848 fn check_bucket_maps() {
1849 const BUCKET_WIDTH_IN_16384S: [u16; 32] = [
1850 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 1024, 1024, 2048, 2048,
1851 2048, 2048, 1024, 1024, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 1];
1853 let mut min_size_iter = 0;
1854 let mut legacy_bucket_iter = 0;
1855 for (bucket, width) in BUCKET_WIDTH_IN_16384S.iter().enumerate() {
1856 assert_eq!(BUCKET_START_POS[bucket], min_size_iter);
1857 for i in 0..*width {
1858 assert_eq!(pos_to_bucket(min_size_iter + i) as usize, bucket);
1860 min_size_iter += *width;
1861 if min_size_iter % (POSITION_TICKS / 8) == 0 {
1862 assert_eq!(LEGACY_TO_BUCKET_RANGE[legacy_bucket_iter].1 as usize, bucket + 1);
1863 if legacy_bucket_iter + 1 < 8 {
1864 assert_eq!(LEGACY_TO_BUCKET_RANGE[legacy_bucket_iter + 1].0 as usize, bucket + 1);
1866 legacy_bucket_iter += 1;
1869 assert_eq!(BUCKET_START_POS[32], POSITION_TICKS);
1870 assert_eq!(min_size_iter, POSITION_TICKS);
1874 fn amount_to_pos(amount_msat: u64, capacity_msat: u64) -> u16 {
1875 let pos = if amount_msat < u64::max_value() / (POSITION_TICKS as u64) {
1876 (amount_msat * (POSITION_TICKS as u64) / capacity_msat.saturating_add(1))
1877 .try_into().unwrap_or(POSITION_TICKS)
1879 // Only use 128-bit arithmetic when multiplication will overflow to avoid 128-bit
1880 // division. This branch should only be hit in fuzz testing since the amount would
1881 // need to be over 2.88 million BTC in practice.
1882 ((amount_msat as u128) * (POSITION_TICKS as u128)
1883 / (capacity_msat as u128).saturating_add(1))
1884 .try_into().unwrap_or(POSITION_TICKS)
1886 // If we are running in a client that doesn't validate gossip, its possible for a channel's
1887 // capacity to change due to a `channel_update` message which, if received while a payment
1888 // is in-flight, could cause this to fail. Thus, we only assert in test.
1890 debug_assert!(pos < POSITION_TICKS);
1894 /// Prior to LDK 0.0.117 we used eight buckets which were split evenly across the either
1895 /// octiles. This was changed to use 32 buckets for accuracy reasons in 0.0.117, however we
1896 /// support reading the legacy values here for backwards compatibility.
1897 pub(super) struct LegacyHistoricalBucketRangeTracker {
1901 impl LegacyHistoricalBucketRangeTracker {
1902 pub(crate) fn into_current(&self) -> HistoricalBucketRangeTracker {
1903 let mut buckets = [0; 32];
1904 for (idx, legacy_bucket) in self.buckets.iter().enumerate() {
1905 let mut new_val = *legacy_bucket;
1906 let (start, end) = LEGACY_TO_BUCKET_RANGE[idx];
1907 new_val /= (end - start) as u16;
1908 for i in start..end {
1909 buckets[i as usize] = new_val;
1912 HistoricalBucketRangeTracker { buckets }
1916 /// Tracks the historical state of a distribution as a weighted average of how much time was spent
1917 /// in each of 32 buckets.
1918 #[derive(Clone, Copy)]
1919 pub(super) struct HistoricalBucketRangeTracker {
1923 /// Buckets are stored in fixed point numbers with a 5 bit fractional part. Thus, the value
1924 /// "one" is 32, or this constant.
1925 pub const BUCKET_FIXED_POINT_ONE: u16 = 32;
1927 impl HistoricalBucketRangeTracker {
1928 pub(super) fn new() -> Self { Self { buckets: [0; 32] } }
1929 pub(super) fn track_datapoint(&mut self, liquidity_offset_msat: u64, capacity_msat: u64) {
1930 // We have 32 leaky buckets for min and max liquidity. Each bucket tracks the amount of time
1931 // we spend in each bucket as a 16-bit fixed-point number with a 5 bit fractional part.
1933 // Each time we update our liquidity estimate, we add 32 (1.0 in our fixed-point system) to
1934 // the buckets for the current min and max liquidity offset positions.
1936 // We then decay each bucket by multiplying by 2047/2048 (avoiding dividing by a
1937 // non-power-of-two). This ensures we can't actually overflow the u16 - when we get to
1938 // 63,457 adding 32 and decaying by 2047/2048 leaves us back at 63,457.
1940 // In total, this allows us to track data for the last 8,000 or so payments across a given
1943 // These constants are a balance - we try to fit in 2 bytes per bucket to reduce overhead,
1944 // and need to balance having more bits in the decimal part (to ensure decay isn't too
1945 // non-linear) with having too few bits in the mantissa, causing us to not store very many
1948 // The constants were picked experimentally, selecting a decay amount that restricts us
1949 // from overflowing buckets without having to cap them manually.
1951 let pos: u16 = amount_to_pos(liquidity_offset_msat, capacity_msat);
1952 if pos < POSITION_TICKS {
1953 for e in self.buckets.iter_mut() {
1954 *e = ((*e as u32) * 2047 / 2048) as u16;
1956 let bucket = pos_to_bucket(pos);
1957 self.buckets[bucket] = self.buckets[bucket].saturating_add(BUCKET_FIXED_POINT_ONE);
1960 /// Decay all buckets by the given number of half-lives. Used to more aggressively remove old
1961 /// datapoints as we receive newer information.
1963 pub(super) fn time_decay_data(&mut self, half_lives: u32) {
1964 for e in self.buckets.iter_mut() {
1965 *e = e.checked_shr(half_lives).unwrap_or(0);
1970 impl_writeable_tlv_based!(HistoricalBucketRangeTracker, { (0, buckets, required) });
1971 impl_writeable_tlv_based!(LegacyHistoricalBucketRangeTracker, { (0, buckets, required) });
1973 /// A set of buckets representing the history of where we've seen the minimum- and maximum-
1974 /// liquidity bounds for a given channel.
1975 pub(super) struct HistoricalMinMaxBuckets<D: Deref<Target = HistoricalBucketRangeTracker>> {
1976 /// Buckets tracking where and how often we've seen the minimum liquidity bound for a
1978 pub(super) min_liquidity_offset_history: D,
1979 /// Buckets tracking where and how often we've seen the maximum liquidity bound for a
1981 pub(super) max_liquidity_offset_history: D,
1984 impl<D: Deref<Target = HistoricalBucketRangeTracker>> HistoricalMinMaxBuckets<D> {
1985 pub(super) fn get_decayed_buckets<T: Time>(&self, now: T, last_updated: T, half_life: Duration)
1986 -> Option<([u16; 32], [u16; 32])> {
1987 let (_, required_decays) = self.get_total_valid_points(now, last_updated, half_life)?;
1989 let mut min_buckets = *self.min_liquidity_offset_history;
1990 min_buckets.time_decay_data(required_decays);
1991 let mut max_buckets = *self.max_liquidity_offset_history;
1992 max_buckets.time_decay_data(required_decays);
1993 Some((min_buckets.buckets, max_buckets.buckets))
1996 pub(super) fn get_total_valid_points<T: Time>(&self, now: T, last_updated: T, half_life: Duration)
1997 -> Option<(u64, u32)> {
1998 let required_decays = now.duration_since(last_updated).as_secs()
1999 .checked_div(half_life.as_secs())
2000 .map_or(u32::max_value(), |decays| cmp::min(decays, u32::max_value() as u64) as u32);
2002 let mut total_valid_points_tracked = 0;
2003 for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate() {
2004 for max_bucket in self.max_liquidity_offset_history.buckets.iter().take(32 - min_idx) {
2005 total_valid_points_tracked += (*min_bucket as u64) * (*max_bucket as u64);
2009 // If the total valid points is smaller than 1.0 (i.e. 32 in our fixed-point scheme),
2010 // treat it as if we were fully decayed.
2011 const FULLY_DECAYED: u16 = BUCKET_FIXED_POINT_ONE * BUCKET_FIXED_POINT_ONE;
2012 if total_valid_points_tracked.checked_shr(required_decays).unwrap_or(0) < FULLY_DECAYED.into() {
2016 Some((total_valid_points_tracked, required_decays))
2020 pub(super) fn calculate_success_probability_times_billion<T: Time>(
2021 &self, now: T, last_updated: T, half_life: Duration,
2022 params: &ProbabilisticScoringFeeParameters, amount_msat: u64, capacity_msat: u64
2024 // If historical penalties are enabled, we try to calculate a probability of success
2025 // given our historical distribution of min- and max-liquidity bounds in a channel.
2026 // To do so, we walk the set of historical liquidity bucket (min, max) combinations
2027 // (where min_idx < max_idx, as having a minimum above our maximum is an invalid
2028 // state). For each pair, we calculate the probability as if the bucket's corresponding
2029 // min- and max- liquidity bounds were our current liquidity bounds and then multiply
2030 // that probability by the weight of the selected buckets.
2031 let payment_pos = amount_to_pos(amount_msat, capacity_msat);
2032 if payment_pos >= POSITION_TICKS { return None; }
2034 // Check if all our buckets are zero, once decayed and treat it as if we had no data. We
2035 // don't actually use the decayed buckets, though, as that would lose precision.
2036 let (total_valid_points_tracked, _)
2037 = self.get_total_valid_points(now, last_updated, half_life)?;
2039 let mut cumulative_success_prob_times_billion = 0;
2040 // Special-case the 0th min bucket - it generally means we failed a payment, so only
2041 // consider the highest (i.e. largest-offset-from-max-capacity) max bucket for all
2042 // points against the 0th min bucket. This avoids the case where we fail to route
2043 // increasingly lower values over a channel, but treat each failure as a separate
2044 // datapoint, many of which may have relatively high maximum-available-liquidity
2045 // values, which will result in us thinking we have some nontrivial probability of
2046 // routing up to that amount.
2047 if self.min_liquidity_offset_history.buckets[0] != 0 {
2048 let mut highest_max_bucket_with_points = 0; // The highest max-bucket with any data
2049 let mut total_max_points = 0; // Total points in max-buckets to consider
2050 for (max_idx, max_bucket) in self.max_liquidity_offset_history.buckets.iter().enumerate() {
2051 if *max_bucket >= BUCKET_FIXED_POINT_ONE {
2052 highest_max_bucket_with_points = cmp::max(highest_max_bucket_with_points, max_idx);
2054 total_max_points += *max_bucket as u64;
2056 let max_bucket_end_pos = BUCKET_START_POS[32 - highest_max_bucket_with_points] - 1;
2057 if payment_pos < max_bucket_end_pos {
2058 let (numerator, denominator) = success_probability(payment_pos as u64, 0,
2059 max_bucket_end_pos as u64, POSITION_TICKS as u64 - 1, params, true);
2060 let bucket_prob_times_billion =
2061 (self.min_liquidity_offset_history.buckets[0] as u64) * total_max_points
2062 * 1024 * 1024 * 1024 / total_valid_points_tracked;
2063 cumulative_success_prob_times_billion += bucket_prob_times_billion *
2064 numerator / denominator;
2068 for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate().skip(1) {
2069 let min_bucket_start_pos = BUCKET_START_POS[min_idx];
2070 for (max_idx, max_bucket) in self.max_liquidity_offset_history.buckets.iter().enumerate().take(32 - min_idx) {
2071 let max_bucket_end_pos = BUCKET_START_POS[32 - max_idx] - 1;
2072 // Note that this multiply can only barely not overflow - two 16 bit ints plus
2073 // 30 bits is 62 bits.
2074 let bucket_prob_times_billion = (*min_bucket as u64) * (*max_bucket as u64)
2075 * 1024 * 1024 * 1024 / total_valid_points_tracked;
2076 if payment_pos >= max_bucket_end_pos {
2077 // Success probability 0, the payment amount may be above the max liquidity
2079 } else if payment_pos < min_bucket_start_pos {
2080 cumulative_success_prob_times_billion += bucket_prob_times_billion;
2082 let (numerator, denominator) = success_probability(payment_pos as u64,
2083 min_bucket_start_pos as u64, max_bucket_end_pos as u64,
2084 POSITION_TICKS as u64 - 1, params, true);
2085 cumulative_success_prob_times_billion += bucket_prob_times_billion *
2086 numerator / denominator;
2091 Some(cumulative_success_prob_times_billion)
2095 use bucketed_history::{LegacyHistoricalBucketRangeTracker, HistoricalBucketRangeTracker, HistoricalMinMaxBuckets};
2097 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Writeable for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
2099 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
2100 write_tlv_fields!(w, {
2101 (0, self.channel_liquidities, required),
2107 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time>
2108 ReadableArgs<(ProbabilisticScoringDecayParameters, G, L)> for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
2111 r: &mut R, args: (ProbabilisticScoringDecayParameters, G, L)
2112 ) -> Result<Self, DecodeError> {
2113 let (decay_params, network_graph, logger) = args;
2114 let mut channel_liquidities = HashMap::new();
2115 read_tlv_fields!(r, {
2116 (0, channel_liquidities, required),
2122 channel_liquidities,
2127 impl<T: Time> Writeable for ChannelLiquidity<T> {
2129 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
2130 let duration_since_epoch = T::duration_since_epoch() - self.last_updated.elapsed();
2131 write_tlv_fields!(w, {
2132 (0, self.min_liquidity_offset_msat, required),
2133 // 1 was the min_liquidity_offset_history in octile form
2134 (2, self.max_liquidity_offset_msat, required),
2135 // 3 was the max_liquidity_offset_history in octile form
2136 (4, duration_since_epoch, required),
2137 (5, Some(self.min_liquidity_offset_history), option),
2138 (7, Some(self.max_liquidity_offset_history), option),
2144 impl<T: Time> Readable for ChannelLiquidity<T> {
2146 fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
2147 let mut min_liquidity_offset_msat = 0;
2148 let mut max_liquidity_offset_msat = 0;
2149 let mut legacy_min_liq_offset_history: Option<LegacyHistoricalBucketRangeTracker> = None;
2150 let mut legacy_max_liq_offset_history: Option<LegacyHistoricalBucketRangeTracker> = None;
2151 let mut min_liquidity_offset_history: Option<HistoricalBucketRangeTracker> = None;
2152 let mut max_liquidity_offset_history: Option<HistoricalBucketRangeTracker> = None;
2153 let mut duration_since_epoch = Duration::from_secs(0);
2154 read_tlv_fields!(r, {
2155 (0, min_liquidity_offset_msat, required),
2156 (1, legacy_min_liq_offset_history, option),
2157 (2, max_liquidity_offset_msat, required),
2158 (3, legacy_max_liq_offset_history, option),
2159 (4, duration_since_epoch, required),
2160 (5, min_liquidity_offset_history, option),
2161 (7, max_liquidity_offset_history, option),
2163 // On rust prior to 1.60 `Instant::duration_since` will panic if time goes backwards.
2164 // We write `last_updated` as wallclock time even though its ultimately an `Instant` (which
2165 // is a time from a monotonic clock usually represented as an offset against boot time).
2166 // Thus, we have to construct an `Instant` by subtracting the difference in wallclock time
2167 // from the one that was written. However, because `Instant` can panic if we construct one
2168 // in the future, we must handle wallclock time jumping backwards, which we do by simply
2169 // using `Instant::now()` in that case.
2170 let wall_clock_now = T::duration_since_epoch();
2172 let last_updated = if wall_clock_now > duration_since_epoch {
2173 now - (wall_clock_now - duration_since_epoch)
2175 if min_liquidity_offset_history.is_none() {
2176 if let Some(legacy_buckets) = legacy_min_liq_offset_history {
2177 min_liquidity_offset_history = Some(legacy_buckets.into_current());
2179 min_liquidity_offset_history = Some(HistoricalBucketRangeTracker::new());
2182 if max_liquidity_offset_history.is_none() {
2183 if let Some(legacy_buckets) = legacy_max_liq_offset_history {
2184 max_liquidity_offset_history = Some(legacy_buckets.into_current());
2186 max_liquidity_offset_history = Some(HistoricalBucketRangeTracker::new());
2190 min_liquidity_offset_msat,
2191 max_liquidity_offset_msat,
2192 min_liquidity_offset_history: min_liquidity_offset_history.unwrap(),
2193 max_liquidity_offset_history: max_liquidity_offset_history.unwrap(),
2201 use super::{ChannelLiquidity, HistoricalBucketRangeTracker, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters, ProbabilisticScorerUsingTime};
2202 use crate::blinded_path::{BlindedHop, BlindedPath};
2203 use crate::util::config::UserConfig;
2204 use crate::util::time::Time;
2205 use crate::util::time::tests::SinceEpoch;
2207 use crate::ln::channelmanager;
2208 use crate::ln::msgs::{ChannelAnnouncement, ChannelUpdate, UnsignedChannelAnnouncement, UnsignedChannelUpdate};
2209 use crate::routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId};
2210 use crate::routing::router::{BlindedTail, Path, RouteHop};
2211 use crate::routing::scoring::{ChannelUsage, ScoreLookUp, ScoreUpdate};
2212 use crate::util::ser::{ReadableArgs, Writeable};
2213 use crate::util::test_utils::{self, TestLogger};
2215 use bitcoin::blockdata::constants::ChainHash;
2216 use bitcoin::hashes::Hash;
2217 use bitcoin::hashes::sha256d::Hash as Sha256dHash;
2218 use bitcoin::network::constants::Network;
2219 use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey};
2220 use core::time::Duration;
2223 fn source_privkey() -> SecretKey {
2224 SecretKey::from_slice(&[42; 32]).unwrap()
2227 fn target_privkey() -> SecretKey {
2228 SecretKey::from_slice(&[43; 32]).unwrap()
2231 fn source_pubkey() -> PublicKey {
2232 let secp_ctx = Secp256k1::new();
2233 PublicKey::from_secret_key(&secp_ctx, &source_privkey())
2236 fn target_pubkey() -> PublicKey {
2237 let secp_ctx = Secp256k1::new();
2238 PublicKey::from_secret_key(&secp_ctx, &target_privkey())
2241 fn source_node_id() -> NodeId {
2242 NodeId::from_pubkey(&source_pubkey())
2245 fn target_node_id() -> NodeId {
2246 NodeId::from_pubkey(&target_pubkey())
2249 // `ProbabilisticScorer` tests
2251 /// A probabilistic scorer for testing with time that can be manually advanced.
2252 type ProbabilisticScorer<'a> = ProbabilisticScorerUsingTime::<&'a NetworkGraph<&'a TestLogger>, &'a TestLogger, SinceEpoch>;
2254 fn sender_privkey() -> SecretKey {
2255 SecretKey::from_slice(&[41; 32]).unwrap()
2258 fn recipient_privkey() -> SecretKey {
2259 SecretKey::from_slice(&[45; 32]).unwrap()
2262 fn sender_pubkey() -> PublicKey {
2263 let secp_ctx = Secp256k1::new();
2264 PublicKey::from_secret_key(&secp_ctx, &sender_privkey())
2267 fn recipient_pubkey() -> PublicKey {
2268 let secp_ctx = Secp256k1::new();
2269 PublicKey::from_secret_key(&secp_ctx, &recipient_privkey())
2272 fn sender_node_id() -> NodeId {
2273 NodeId::from_pubkey(&sender_pubkey())
2276 fn recipient_node_id() -> NodeId {
2277 NodeId::from_pubkey(&recipient_pubkey())
2280 fn network_graph(logger: &TestLogger) -> NetworkGraph<&TestLogger> {
2281 let mut network_graph = NetworkGraph::new(Network::Testnet, logger);
2282 add_channel(&mut network_graph, 42, source_privkey(), target_privkey());
2283 add_channel(&mut network_graph, 43, target_privkey(), recipient_privkey());
2289 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_1_key: SecretKey,
2290 node_2_key: SecretKey
2292 let genesis_hash = ChainHash::using_genesis_block(Network::Testnet);
2293 let node_1_secret = &SecretKey::from_slice(&[39; 32]).unwrap();
2294 let node_2_secret = &SecretKey::from_slice(&[40; 32]).unwrap();
2295 let secp_ctx = Secp256k1::new();
2296 let unsigned_announcement = UnsignedChannelAnnouncement {
2297 features: channelmanager::provided_channel_features(&UserConfig::default()),
2298 chain_hash: genesis_hash,
2300 node_id_1: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_1_key)),
2301 node_id_2: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_2_key)),
2302 bitcoin_key_1: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_1_secret)),
2303 bitcoin_key_2: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_2_secret)),
2304 excess_data: Vec::new(),
2306 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
2307 let signed_announcement = ChannelAnnouncement {
2308 node_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_key),
2309 node_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_key),
2310 bitcoin_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_secret),
2311 bitcoin_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_secret),
2312 contents: unsigned_announcement,
2314 let chain_source: Option<&crate::util::test_utils::TestChainSource> = None;
2315 network_graph.update_channel_from_announcement(
2316 &signed_announcement, &chain_source).unwrap();
2317 update_channel(network_graph, short_channel_id, node_1_key, 0, 1_000, 100);
2318 update_channel(network_graph, short_channel_id, node_2_key, 1, 0, 100);
2322 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_key: SecretKey,
2323 flags: u8, htlc_maximum_msat: u64, timestamp: u32,
2325 let genesis_hash = ChainHash::using_genesis_block(Network::Testnet);
2326 let secp_ctx = Secp256k1::new();
2327 let unsigned_update = UnsignedChannelUpdate {
2328 chain_hash: genesis_hash,
2332 cltv_expiry_delta: 18,
2333 htlc_minimum_msat: 0,
2336 fee_proportional_millionths: 0,
2337 excess_data: Vec::new(),
2339 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_update.encode()[..])[..]);
2340 let signed_update = ChannelUpdate {
2341 signature: secp_ctx.sign_ecdsa(&msghash, &node_key),
2342 contents: unsigned_update,
2344 network_graph.update_channel(&signed_update).unwrap();
2347 fn path_hop(pubkey: PublicKey, short_channel_id: u64, fee_msat: u64) -> RouteHop {
2348 let config = UserConfig::default();
2351 node_features: channelmanager::provided_node_features(&config),
2353 channel_features: channelmanager::provided_channel_features(&config),
2355 cltv_expiry_delta: 18,
2356 maybe_announced_channel: true,
2360 fn payment_path_for_amount(amount_msat: u64) -> Path {
2363 path_hop(source_pubkey(), 41, 1),
2364 path_hop(target_pubkey(), 42, 2),
2365 path_hop(recipient_pubkey(), 43, amount_msat),
2366 ], blinded_tail: None,
2371 fn liquidity_bounds_directed_from_lowest_node_id() {
2372 let logger = TestLogger::new();
2373 let last_updated = SinceEpoch::now();
2374 let network_graph = network_graph(&logger);
2375 let decay_params = ProbabilisticScoringDecayParameters::default();
2376 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2379 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated,
2380 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2381 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2385 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated,
2386 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2387 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2389 let source = source_node_id();
2390 let target = target_node_id();
2391 let recipient = recipient_node_id();
2392 assert!(source > target);
2393 assert!(target < recipient);
2395 // Update minimum liquidity.
2397 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2398 .as_directed(&source, &target, 1_000, decay_params);
2399 assert_eq!(liquidity.min_liquidity_msat(), 100);
2400 assert_eq!(liquidity.max_liquidity_msat(), 300);
2402 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2403 .as_directed(&target, &source, 1_000, decay_params);
2404 assert_eq!(liquidity.min_liquidity_msat(), 700);
2405 assert_eq!(liquidity.max_liquidity_msat(), 900);
2407 scorer.channel_liquidities.get_mut(&42).unwrap()
2408 .as_directed_mut(&source, &target, 1_000, decay_params)
2409 .set_min_liquidity_msat(200);
2411 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2412 .as_directed(&source, &target, 1_000, decay_params);
2413 assert_eq!(liquidity.min_liquidity_msat(), 200);
2414 assert_eq!(liquidity.max_liquidity_msat(), 300);
2416 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2417 .as_directed(&target, &source, 1_000, decay_params);
2418 assert_eq!(liquidity.min_liquidity_msat(), 700);
2419 assert_eq!(liquidity.max_liquidity_msat(), 800);
2421 // Update maximum liquidity.
2423 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2424 .as_directed(&target, &recipient, 1_000, decay_params);
2425 assert_eq!(liquidity.min_liquidity_msat(), 700);
2426 assert_eq!(liquidity.max_liquidity_msat(), 900);
2428 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2429 .as_directed(&recipient, &target, 1_000, decay_params);
2430 assert_eq!(liquidity.min_liquidity_msat(), 100);
2431 assert_eq!(liquidity.max_liquidity_msat(), 300);
2433 scorer.channel_liquidities.get_mut(&43).unwrap()
2434 .as_directed_mut(&target, &recipient, 1_000, decay_params)
2435 .set_max_liquidity_msat(200);
2437 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2438 .as_directed(&target, &recipient, 1_000, decay_params);
2439 assert_eq!(liquidity.min_liquidity_msat(), 0);
2440 assert_eq!(liquidity.max_liquidity_msat(), 200);
2442 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2443 .as_directed(&recipient, &target, 1_000, decay_params);
2444 assert_eq!(liquidity.min_liquidity_msat(), 800);
2445 assert_eq!(liquidity.max_liquidity_msat(), 1000);
2449 fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() {
2450 let logger = TestLogger::new();
2451 let last_updated = SinceEpoch::now();
2452 let network_graph = network_graph(&logger);
2453 let decay_params = ProbabilisticScoringDecayParameters::default();
2454 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2457 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated,
2458 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2459 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2461 let source = source_node_id();
2462 let target = target_node_id();
2463 assert!(source > target);
2465 // Check initial bounds.
2466 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2467 .as_directed(&source, &target, 1_000, decay_params);
2468 assert_eq!(liquidity.min_liquidity_msat(), 400);
2469 assert_eq!(liquidity.max_liquidity_msat(), 800);
2471 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2472 .as_directed(&target, &source, 1_000, decay_params);
2473 assert_eq!(liquidity.min_liquidity_msat(), 200);
2474 assert_eq!(liquidity.max_liquidity_msat(), 600);
2476 // Reset from source to target.
2477 scorer.channel_liquidities.get_mut(&42).unwrap()
2478 .as_directed_mut(&source, &target, 1_000, decay_params)
2479 .set_min_liquidity_msat(900);
2481 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2482 .as_directed(&source, &target, 1_000, decay_params);
2483 assert_eq!(liquidity.min_liquidity_msat(), 900);
2484 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2486 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2487 .as_directed(&target, &source, 1_000, decay_params);
2488 assert_eq!(liquidity.min_liquidity_msat(), 0);
2489 assert_eq!(liquidity.max_liquidity_msat(), 100);
2491 // Reset from target to source.
2492 scorer.channel_liquidities.get_mut(&42).unwrap()
2493 .as_directed_mut(&target, &source, 1_000, decay_params)
2494 .set_min_liquidity_msat(400);
2496 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2497 .as_directed(&source, &target, 1_000, decay_params);
2498 assert_eq!(liquidity.min_liquidity_msat(), 0);
2499 assert_eq!(liquidity.max_liquidity_msat(), 600);
2501 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2502 .as_directed(&target, &source, 1_000, decay_params);
2503 assert_eq!(liquidity.min_liquidity_msat(), 400);
2504 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2508 fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() {
2509 let logger = TestLogger::new();
2510 let last_updated = SinceEpoch::now();
2511 let network_graph = network_graph(&logger);
2512 let decay_params = ProbabilisticScoringDecayParameters::default();
2513 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2516 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated,
2517 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2518 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2520 let source = source_node_id();
2521 let target = target_node_id();
2522 assert!(source > target);
2524 // Check initial bounds.
2525 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2526 .as_directed(&source, &target, 1_000, decay_params);
2527 assert_eq!(liquidity.min_liquidity_msat(), 400);
2528 assert_eq!(liquidity.max_liquidity_msat(), 800);
2530 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2531 .as_directed(&target, &source, 1_000, decay_params);
2532 assert_eq!(liquidity.min_liquidity_msat(), 200);
2533 assert_eq!(liquidity.max_liquidity_msat(), 600);
2535 // Reset from source to target.
2536 scorer.channel_liquidities.get_mut(&42).unwrap()
2537 .as_directed_mut(&source, &target, 1_000, decay_params)
2538 .set_max_liquidity_msat(300);
2540 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2541 .as_directed(&source, &target, 1_000, decay_params);
2542 assert_eq!(liquidity.min_liquidity_msat(), 0);
2543 assert_eq!(liquidity.max_liquidity_msat(), 300);
2545 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2546 .as_directed(&target, &source, 1_000, decay_params);
2547 assert_eq!(liquidity.min_liquidity_msat(), 700);
2548 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2550 // Reset from target to source.
2551 scorer.channel_liquidities.get_mut(&42).unwrap()
2552 .as_directed_mut(&target, &source, 1_000, decay_params)
2553 .set_max_liquidity_msat(600);
2555 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2556 .as_directed(&source, &target, 1_000, decay_params);
2557 assert_eq!(liquidity.min_liquidity_msat(), 400);
2558 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2560 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2561 .as_directed(&target, &source, 1_000, decay_params);
2562 assert_eq!(liquidity.min_liquidity_msat(), 0);
2563 assert_eq!(liquidity.max_liquidity_msat(), 600);
2567 fn increased_penalty_nearing_liquidity_upper_bound() {
2568 let logger = TestLogger::new();
2569 let network_graph = network_graph(&logger);
2570 let params = ProbabilisticScoringFeeParameters {
2571 liquidity_penalty_multiplier_msat: 1_000,
2572 ..ProbabilisticScoringFeeParameters::zero_penalty()
2574 let decay_params = ProbabilisticScoringDecayParameters::default();
2575 let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2576 let source = source_node_id();
2577 let target = target_node_id();
2579 let usage = ChannelUsage {
2581 inflight_htlc_msat: 0,
2582 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
2584 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2585 let usage = ChannelUsage { amount_msat: 10_240, ..usage };
2586 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2587 let usage = ChannelUsage { amount_msat: 102_400, ..usage };
2588 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 47);
2589 let usage = ChannelUsage { amount_msat: 1_023_999, ..usage };
2590 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2_000);
2592 let usage = ChannelUsage {
2594 inflight_htlc_msat: 0,
2595 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2597 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 58);
2598 let usage = ChannelUsage { amount_msat: 256, ..usage };
2599 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 125);
2600 let usage = ChannelUsage { amount_msat: 374, ..usage };
2601 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 198);
2602 let usage = ChannelUsage { amount_msat: 512, ..usage };
2603 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2604 let usage = ChannelUsage { amount_msat: 640, ..usage };
2605 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 425);
2606 let usage = ChannelUsage { amount_msat: 768, ..usage };
2607 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 602);
2608 let usage = ChannelUsage { amount_msat: 896, ..usage };
2609 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 902);
2613 fn constant_penalty_outside_liquidity_bounds() {
2614 let logger = TestLogger::new();
2615 let last_updated = SinceEpoch::now();
2616 let network_graph = network_graph(&logger);
2617 let params = ProbabilisticScoringFeeParameters {
2618 liquidity_penalty_multiplier_msat: 1_000,
2619 considered_impossible_penalty_msat: u64::max_value(),
2620 ..ProbabilisticScoringFeeParameters::zero_penalty()
2622 let decay_params = ProbabilisticScoringDecayParameters {
2623 ..ProbabilisticScoringDecayParameters::zero_penalty()
2625 let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2628 min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40, last_updated,
2629 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2630 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2632 let source = source_node_id();
2633 let target = target_node_id();
2635 let usage = ChannelUsage {
2637 inflight_htlc_msat: 0,
2638 effective_capacity: EffectiveCapacity::Total { capacity_msat: 100, htlc_maximum_msat: 1_000 },
2640 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2641 let usage = ChannelUsage { amount_msat: 50, ..usage };
2642 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2643 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2644 let usage = ChannelUsage { amount_msat: 61, ..usage };
2645 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2649 fn does_not_further_penalize_own_channel() {
2650 let logger = TestLogger::new();
2651 let network_graph = network_graph(&logger);
2652 let params = ProbabilisticScoringFeeParameters {
2653 liquidity_penalty_multiplier_msat: 1_000,
2654 ..ProbabilisticScoringFeeParameters::zero_penalty()
2656 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2657 let sender = sender_node_id();
2658 let source = source_node_id();
2659 let usage = ChannelUsage {
2661 inflight_htlc_msat: 0,
2662 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2664 let failed_path = payment_path_for_amount(500);
2665 let successful_path = payment_path_for_amount(200);
2667 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 301);
2669 scorer.payment_path_failed(&failed_path, 41);
2670 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 301);
2672 scorer.payment_path_successful(&successful_path);
2673 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 301);
2677 fn sets_liquidity_lower_bound_on_downstream_failure() {
2678 let logger = TestLogger::new();
2679 let network_graph = network_graph(&logger);
2680 let params = ProbabilisticScoringFeeParameters {
2681 liquidity_penalty_multiplier_msat: 1_000,
2682 ..ProbabilisticScoringFeeParameters::zero_penalty()
2684 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2685 let source = source_node_id();
2686 let target = target_node_id();
2687 let path = payment_path_for_amount(500);
2689 let usage = ChannelUsage {
2691 inflight_htlc_msat: 0,
2692 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2694 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 128);
2695 let usage = ChannelUsage { amount_msat: 500, ..usage };
2696 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 301);
2697 let usage = ChannelUsage { amount_msat: 750, ..usage };
2698 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 602);
2700 scorer.payment_path_failed(&path, 43);
2702 let usage = ChannelUsage { amount_msat: 250, ..usage };
2703 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2704 let usage = ChannelUsage { amount_msat: 500, ..usage };
2705 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2706 let usage = ChannelUsage { amount_msat: 750, ..usage };
2707 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2711 fn sets_liquidity_upper_bound_on_failure() {
2712 let logger = TestLogger::new();
2713 let network_graph = network_graph(&logger);
2714 let params = ProbabilisticScoringFeeParameters {
2715 liquidity_penalty_multiplier_msat: 1_000,
2716 considered_impossible_penalty_msat: u64::max_value(),
2717 ..ProbabilisticScoringFeeParameters::zero_penalty()
2719 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2720 let source = source_node_id();
2721 let target = target_node_id();
2722 let path = payment_path_for_amount(500);
2724 let usage = ChannelUsage {
2726 inflight_htlc_msat: 0,
2727 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2729 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 128);
2730 let usage = ChannelUsage { amount_msat: 500, ..usage };
2731 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 301);
2732 let usage = ChannelUsage { amount_msat: 750, ..usage };
2733 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 602);
2735 scorer.payment_path_failed(&path, 42);
2737 let usage = ChannelUsage { amount_msat: 250, ..usage };
2738 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2739 let usage = ChannelUsage { amount_msat: 500, ..usage };
2740 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2741 let usage = ChannelUsage { amount_msat: 750, ..usage };
2742 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2746 fn ignores_channels_after_removed_failed_channel() {
2747 // Previously, if we'd tried to send over a channel which was removed from the network
2748 // graph before we call `payment_path_failed` (which is the default if the we get a "no
2749 // such channel" error in the `InvoicePayer`), we would call `failed_downstream` on all
2750 // channels in the route, even ones which they payment never reached. This tests to ensure
2751 // we do not score such channels.
2752 let secp_ctx = Secp256k1::new();
2753 let logger = TestLogger::new();
2754 let mut network_graph = NetworkGraph::new(Network::Testnet, &logger);
2755 let secret_a = SecretKey::from_slice(&[42; 32]).unwrap();
2756 let secret_b = SecretKey::from_slice(&[43; 32]).unwrap();
2757 let secret_c = SecretKey::from_slice(&[44; 32]).unwrap();
2758 let secret_d = SecretKey::from_slice(&[45; 32]).unwrap();
2759 add_channel(&mut network_graph, 42, secret_a, secret_b);
2760 // Don't add the channel from B -> C.
2761 add_channel(&mut network_graph, 44, secret_c, secret_d);
2763 let pub_a = PublicKey::from_secret_key(&secp_ctx, &secret_a);
2764 let pub_b = PublicKey::from_secret_key(&secp_ctx, &secret_b);
2765 let pub_c = PublicKey::from_secret_key(&secp_ctx, &secret_c);
2766 let pub_d = PublicKey::from_secret_key(&secp_ctx, &secret_d);
2769 path_hop(pub_b, 42, 1),
2770 path_hop(pub_c, 43, 2),
2771 path_hop(pub_d, 44, 100),
2774 let node_a = NodeId::from_pubkey(&pub_a);
2775 let node_b = NodeId::from_pubkey(&pub_b);
2776 let node_c = NodeId::from_pubkey(&pub_c);
2777 let node_d = NodeId::from_pubkey(&pub_d);
2779 let params = ProbabilisticScoringFeeParameters {
2780 liquidity_penalty_multiplier_msat: 1_000,
2781 ..ProbabilisticScoringFeeParameters::zero_penalty()
2783 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2785 let usage = ChannelUsage {
2787 inflight_htlc_msat: 0,
2788 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2790 assert_eq!(scorer.channel_penalty_msat(42, &node_a, &node_b, usage, ¶ms), 128);
2791 // Note that a default liquidity bound is used for B -> C as no channel exists
2792 assert_eq!(scorer.channel_penalty_msat(43, &node_b, &node_c, usage, ¶ms), 128);
2793 assert_eq!(scorer.channel_penalty_msat(44, &node_c, &node_d, usage, ¶ms), 128);
2795 scorer.payment_path_failed(&Path { hops: path, blinded_tail: None }, 43);
2797 assert_eq!(scorer.channel_penalty_msat(42, &node_a, &node_b, usage, ¶ms), 80);
2798 // Note that a default liquidity bound is used for B -> C as no channel exists
2799 assert_eq!(scorer.channel_penalty_msat(43, &node_b, &node_c, usage, ¶ms), 128);
2800 assert_eq!(scorer.channel_penalty_msat(44, &node_c, &node_d, usage, ¶ms), 128);
2804 fn reduces_liquidity_upper_bound_along_path_on_success() {
2805 let logger = TestLogger::new();
2806 let network_graph = network_graph(&logger);
2807 let params = ProbabilisticScoringFeeParameters {
2808 liquidity_penalty_multiplier_msat: 1_000,
2809 ..ProbabilisticScoringFeeParameters::zero_penalty()
2811 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2812 let sender = sender_node_id();
2813 let source = source_node_id();
2814 let target = target_node_id();
2815 let recipient = recipient_node_id();
2816 let usage = ChannelUsage {
2818 inflight_htlc_msat: 0,
2819 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2822 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 128);
2823 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 128);
2824 assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage, ¶ms), 128);
2826 scorer.payment_path_successful(&payment_path_for_amount(500));
2828 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage, ¶ms), 128);
2829 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2830 assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage, ¶ms), 300);
2834 fn decays_liquidity_bounds_over_time() {
2835 let logger = TestLogger::new();
2836 let network_graph = network_graph(&logger);
2837 let params = ProbabilisticScoringFeeParameters {
2838 liquidity_penalty_multiplier_msat: 1_000,
2839 considered_impossible_penalty_msat: u64::max_value(),
2840 ..ProbabilisticScoringFeeParameters::zero_penalty()
2842 let decay_params = ProbabilisticScoringDecayParameters {
2843 liquidity_offset_half_life: Duration::from_secs(10),
2844 ..ProbabilisticScoringDecayParameters::zero_penalty()
2846 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2847 let source = source_node_id();
2848 let target = target_node_id();
2850 let usage = ChannelUsage {
2852 inflight_htlc_msat: 0,
2853 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
2855 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2856 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
2857 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2_000);
2859 scorer.payment_path_failed(&payment_path_for_amount(768), 42);
2860 scorer.payment_path_failed(&payment_path_for_amount(128), 43);
2862 // Initial penalties
2863 let usage = ChannelUsage { amount_msat: 128, ..usage };
2864 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2865 let usage = ChannelUsage { amount_msat: 256, ..usage };
2866 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 93);
2867 let usage = ChannelUsage { amount_msat: 768, ..usage };
2868 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1_479);
2869 let usage = ChannelUsage { amount_msat: 896, ..usage };
2870 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2873 SinceEpoch::advance(Duration::from_secs(4));
2874 let usage = ChannelUsage { amount_msat: 128, ..usage };
2875 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2876 let usage = ChannelUsage { amount_msat: 256, ..usage };
2877 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 93);
2878 let usage = ChannelUsage { amount_msat: 768, ..usage };
2879 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1_479);
2880 let usage = ChannelUsage { amount_msat: 896, ..usage };
2881 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2883 // Half decay (i.e., three-quarter life)
2884 SinceEpoch::advance(Duration::from_secs(1));
2885 let usage = ChannelUsage { amount_msat: 128, ..usage };
2886 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 22);
2887 let usage = ChannelUsage { amount_msat: 256, ..usage };
2888 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 106);
2889 let usage = ChannelUsage { amount_msat: 768, ..usage };
2890 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 921);
2891 let usage = ChannelUsage { amount_msat: 896, ..usage };
2892 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2894 // One decay (i.e., half life)
2895 SinceEpoch::advance(Duration::from_secs(5));
2896 let usage = ChannelUsage { amount_msat: 64, ..usage };
2897 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2898 let usage = ChannelUsage { amount_msat: 128, ..usage };
2899 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 34);
2900 let usage = ChannelUsage { amount_msat: 896, ..usage };
2901 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1_970);
2902 let usage = ChannelUsage { amount_msat: 960, ..usage };
2903 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2905 // Fully decay liquidity lower bound.
2906 SinceEpoch::advance(Duration::from_secs(10 * 7));
2907 let usage = ChannelUsage { amount_msat: 0, ..usage };
2908 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2909 let usage = ChannelUsage { amount_msat: 1, ..usage };
2910 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2911 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
2912 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2_000);
2913 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2914 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2916 // Fully decay liquidity upper bound.
2917 SinceEpoch::advance(Duration::from_secs(10));
2918 let usage = ChannelUsage { amount_msat: 0, ..usage };
2919 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2920 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2921 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2923 SinceEpoch::advance(Duration::from_secs(10));
2924 let usage = ChannelUsage { amount_msat: 0, ..usage };
2925 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
2926 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2927 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
2931 fn decays_liquidity_bounds_without_shift_overflow() {
2932 let logger = TestLogger::new();
2933 let network_graph = network_graph(&logger);
2934 let params = ProbabilisticScoringFeeParameters {
2935 liquidity_penalty_multiplier_msat: 1_000,
2936 ..ProbabilisticScoringFeeParameters::zero_penalty()
2938 let decay_params = ProbabilisticScoringDecayParameters {
2939 liquidity_offset_half_life: Duration::from_secs(10),
2940 ..ProbabilisticScoringDecayParameters::default()
2942 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2943 let source = source_node_id();
2944 let target = target_node_id();
2945 let usage = ChannelUsage {
2947 inflight_htlc_msat: 0,
2948 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2950 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 125);
2952 scorer.payment_path_failed(&payment_path_for_amount(512), 42);
2953 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 281);
2955 // An unchecked right shift 64 bits or more in DirectedChannelLiquidity::decayed_offset_msat
2956 // would cause an overflow.
2957 SinceEpoch::advance(Duration::from_secs(10 * 64));
2958 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 125);
2960 SinceEpoch::advance(Duration::from_secs(10));
2961 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 125);
2965 fn restricts_liquidity_bounds_after_decay() {
2966 let logger = TestLogger::new();
2967 let network_graph = network_graph(&logger);
2968 let params = ProbabilisticScoringFeeParameters {
2969 liquidity_penalty_multiplier_msat: 1_000,
2970 ..ProbabilisticScoringFeeParameters::zero_penalty()
2972 let decay_params = ProbabilisticScoringDecayParameters {
2973 liquidity_offset_half_life: Duration::from_secs(10),
2974 ..ProbabilisticScoringDecayParameters::default()
2976 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2977 let source = source_node_id();
2978 let target = target_node_id();
2979 let usage = ChannelUsage {
2981 inflight_htlc_msat: 0,
2982 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2985 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
2987 // More knowledge gives higher confidence (256, 768), meaning a lower penalty.
2988 scorer.payment_path_failed(&payment_path_for_amount(768), 42);
2989 scorer.payment_path_failed(&payment_path_for_amount(256), 43);
2990 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 281);
2992 // Decaying knowledge gives less confidence (128, 896), meaning a higher penalty.
2993 SinceEpoch::advance(Duration::from_secs(10));
2994 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 291);
2996 // Reducing the upper bound gives more confidence (128, 832) that the payment amount (512)
2997 // is closer to the upper bound, meaning a higher penalty.
2998 scorer.payment_path_successful(&payment_path_for_amount(64));
2999 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 331);
3001 // Increasing the lower bound gives more confidence (256, 832) that the payment amount (512)
3002 // is closer to the lower bound, meaning a lower penalty.
3003 scorer.payment_path_failed(&payment_path_for_amount(256), 43);
3004 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 245);
3006 // Further decaying affects the lower bound more than the upper bound (128, 928).
3007 SinceEpoch::advance(Duration::from_secs(10));
3008 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 280);
3012 fn restores_persisted_liquidity_bounds() {
3013 let logger = TestLogger::new();
3014 let network_graph = network_graph(&logger);
3015 let params = ProbabilisticScoringFeeParameters {
3016 liquidity_penalty_multiplier_msat: 1_000,
3017 considered_impossible_penalty_msat: u64::max_value(),
3018 ..ProbabilisticScoringFeeParameters::zero_penalty()
3020 let decay_params = ProbabilisticScoringDecayParameters {
3021 liquidity_offset_half_life: Duration::from_secs(10),
3022 ..ProbabilisticScoringDecayParameters::default()
3024 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3025 let source = source_node_id();
3026 let target = target_node_id();
3027 let usage = ChannelUsage {
3029 inflight_htlc_msat: 0,
3030 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
3033 scorer.payment_path_failed(&payment_path_for_amount(500), 42);
3034 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
3036 SinceEpoch::advance(Duration::from_secs(10));
3037 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 473);
3039 scorer.payment_path_failed(&payment_path_for_amount(250), 43);
3040 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
3042 let mut serialized_scorer = Vec::new();
3043 scorer.write(&mut serialized_scorer).unwrap();
3045 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
3046 let deserialized_scorer =
3047 <ProbabilisticScorer>::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap();
3048 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
3052 fn decays_persisted_liquidity_bounds() {
3053 let logger = TestLogger::new();
3054 let network_graph = network_graph(&logger);
3055 let params = ProbabilisticScoringFeeParameters {
3056 liquidity_penalty_multiplier_msat: 1_000,
3057 considered_impossible_penalty_msat: u64::max_value(),
3058 ..ProbabilisticScoringFeeParameters::zero_penalty()
3060 let decay_params = ProbabilisticScoringDecayParameters {
3061 liquidity_offset_half_life: Duration::from_secs(10),
3062 ..ProbabilisticScoringDecayParameters::zero_penalty()
3064 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3065 let source = source_node_id();
3066 let target = target_node_id();
3067 let usage = ChannelUsage {
3069 inflight_htlc_msat: 0,
3070 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
3073 scorer.payment_path_failed(&payment_path_for_amount(500), 42);
3074 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
3076 let mut serialized_scorer = Vec::new();
3077 scorer.write(&mut serialized_scorer).unwrap();
3079 SinceEpoch::advance(Duration::from_secs(10));
3081 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
3082 let deserialized_scorer =
3083 <ProbabilisticScorer>::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap();
3084 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 473);
3086 scorer.payment_path_failed(&payment_path_for_amount(250), 43);
3087 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
3089 SinceEpoch::advance(Duration::from_secs(10));
3090 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 370);
3094 fn scores_realistic_payments() {
3095 // Shows the scores of "realistic" sends of 100k sats over channels of 1-10m sats (with a
3096 // 50k sat reserve).
3097 let logger = TestLogger::new();
3098 let network_graph = network_graph(&logger);
3099 let params = ProbabilisticScoringFeeParameters::default();
3100 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3101 let source = source_node_id();
3102 let target = target_node_id();
3104 let usage = ChannelUsage {
3105 amount_msat: 100_000_000,
3106 inflight_htlc_msat: 0,
3107 effective_capacity: EffectiveCapacity::Total { capacity_msat: 950_000_000, htlc_maximum_msat: 1_000 },
3109 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 11497);
3110 let usage = ChannelUsage {
3111 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3113 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 7408);
3114 let usage = ChannelUsage {
3115 effective_capacity: EffectiveCapacity::Total { capacity_msat: 2_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3117 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 6151);
3118 let usage = ChannelUsage {
3119 effective_capacity: EffectiveCapacity::Total { capacity_msat: 3_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3121 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 5427);
3122 let usage = ChannelUsage {
3123 effective_capacity: EffectiveCapacity::Total { capacity_msat: 4_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3125 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 4955);
3126 let usage = ChannelUsage {
3127 effective_capacity: EffectiveCapacity::Total { capacity_msat: 5_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3129 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 4736);
3130 let usage = ChannelUsage {
3131 effective_capacity: EffectiveCapacity::Total { capacity_msat: 6_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3133 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 4484);
3134 let usage = ChannelUsage {
3135 effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_450_000_000, htlc_maximum_msat: 1_000 }, ..usage
3137 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 4484);
3138 let usage = ChannelUsage {
3139 effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3141 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 4263);
3142 let usage = ChannelUsage {
3143 effective_capacity: EffectiveCapacity::Total { capacity_msat: 8_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3145 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 4263);
3146 let usage = ChannelUsage {
3147 effective_capacity: EffectiveCapacity::Total { capacity_msat: 9_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3149 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 4044);
3153 fn adds_base_penalty_to_liquidity_penalty() {
3154 let logger = TestLogger::new();
3155 let network_graph = network_graph(&logger);
3156 let source = source_node_id();
3157 let target = target_node_id();
3158 let usage = ChannelUsage {
3160 inflight_htlc_msat: 0,
3161 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
3164 let params = ProbabilisticScoringFeeParameters {
3165 liquidity_penalty_multiplier_msat: 1_000,
3166 ..ProbabilisticScoringFeeParameters::zero_penalty()
3168 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3169 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 58);
3171 let params = ProbabilisticScoringFeeParameters {
3172 base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000,
3173 anti_probing_penalty_msat: 0, ..ProbabilisticScoringFeeParameters::zero_penalty()
3175 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3176 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 558);
3178 let params = ProbabilisticScoringFeeParameters {
3179 base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000,
3180 base_penalty_amount_multiplier_msat: (1 << 30),
3181 anti_probing_penalty_msat: 0, ..ProbabilisticScoringFeeParameters::zero_penalty()
3184 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3185 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 558 + 128);
3189 fn adds_amount_penalty_to_liquidity_penalty() {
3190 let logger = TestLogger::new();
3191 let network_graph = network_graph(&logger);
3192 let source = source_node_id();
3193 let target = target_node_id();
3194 let usage = ChannelUsage {
3195 amount_msat: 512_000,
3196 inflight_htlc_msat: 0,
3197 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
3200 let params = ProbabilisticScoringFeeParameters {
3201 liquidity_penalty_multiplier_msat: 1_000,
3202 liquidity_penalty_amount_multiplier_msat: 0,
3203 ..ProbabilisticScoringFeeParameters::zero_penalty()
3205 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3206 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
3208 let params = ProbabilisticScoringFeeParameters {
3209 liquidity_penalty_multiplier_msat: 1_000,
3210 liquidity_penalty_amount_multiplier_msat: 256,
3211 ..ProbabilisticScoringFeeParameters::zero_penalty()
3213 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3214 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 337);
3218 fn calculates_log10_without_overflowing_u64_max_value() {
3219 let logger = TestLogger::new();
3220 let network_graph = network_graph(&logger);
3221 let source = source_node_id();
3222 let target = target_node_id();
3223 let usage = ChannelUsage {
3224 amount_msat: u64::max_value(),
3225 inflight_htlc_msat: 0,
3226 effective_capacity: EffectiveCapacity::Infinite,
3229 let params = ProbabilisticScoringFeeParameters {
3230 liquidity_penalty_multiplier_msat: 40_000,
3231 ..ProbabilisticScoringFeeParameters::zero_penalty()
3233 let decay_params = ProbabilisticScoringDecayParameters::zero_penalty();
3234 let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3235 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 80_000);
3239 fn accounts_for_inflight_htlc_usage() {
3240 let logger = TestLogger::new();
3241 let network_graph = network_graph(&logger);
3242 let params = ProbabilisticScoringFeeParameters {
3243 considered_impossible_penalty_msat: u64::max_value(),
3244 ..ProbabilisticScoringFeeParameters::zero_penalty()
3246 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3247 let source = source_node_id();
3248 let target = target_node_id();
3250 let usage = ChannelUsage {
3252 inflight_htlc_msat: 0,
3253 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
3255 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
3257 let usage = ChannelUsage { inflight_htlc_msat: 251, ..usage };
3258 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
3262 fn removes_uncertainity_when_exact_liquidity_known() {
3263 let logger = TestLogger::new();
3264 let network_graph = network_graph(&logger);
3265 let params = ProbabilisticScoringFeeParameters::default();
3266 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3267 let source = source_node_id();
3268 let target = target_node_id();
3270 let base_penalty_msat = params.base_penalty_msat;
3271 let usage = ChannelUsage {
3273 inflight_htlc_msat: 0,
3274 effective_capacity: EffectiveCapacity::ExactLiquidity { liquidity_msat: 1_000 },
3276 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), base_penalty_msat);
3278 let usage = ChannelUsage { amount_msat: 1_000, ..usage };
3279 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), base_penalty_msat);
3281 let usage = ChannelUsage { amount_msat: 1_001, ..usage };
3282 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value());
3286 fn remembers_historical_failures() {
3287 let logger = TestLogger::new();
3288 let network_graph = network_graph(&logger);
3289 let params = ProbabilisticScoringFeeParameters {
3290 historical_liquidity_penalty_multiplier_msat: 1024,
3291 historical_liquidity_penalty_amount_multiplier_msat: 1024,
3292 ..ProbabilisticScoringFeeParameters::zero_penalty()
3294 let decay_params = ProbabilisticScoringDecayParameters {
3295 liquidity_offset_half_life: Duration::from_secs(60 * 60),
3296 historical_no_updates_half_life: Duration::from_secs(10),
3298 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3299 let source = source_node_id();
3300 let target = target_node_id();
3302 let usage = ChannelUsage {
3304 inflight_htlc_msat: 0,
3305 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
3307 let usage_1 = ChannelUsage {
3309 inflight_htlc_msat: 0,
3310 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
3313 // With no historical data the normal liquidity penalty calculation is used.
3314 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 168);
3315 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3317 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 42, ¶ms),
3320 scorer.payment_path_failed(&payment_path_for_amount(1), 42);
3321 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2048);
3322 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage_1, ¶ms), 249);
3323 // The "it failed" increment is 32, where the probability should lie several buckets into
3324 // the first octile.
3325 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3326 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],
3327 [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])));
3328 assert!(scorer.historical_estimated_payment_success_probability(42, &target, 1, ¶ms)
3330 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 500, ¶ms),
3333 // Even after we tell the scorer we definitely have enough available liquidity, it will
3334 // still remember that there was some failure in the past, and assign a non-0 penalty.
3335 scorer.payment_path_failed(&payment_path_for_amount(1000), 43);
3336 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 105);
3337 // The first points should be decayed just slightly and the last bucket has a new point.
3338 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3339 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],
3340 [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])));
3342 // The exact success probability is a bit complicated and involves integer rounding, so we
3343 // simply check bounds here.
3344 let five_hundred_prob =
3345 scorer.historical_estimated_payment_success_probability(42, &target, 500, ¶ms).unwrap();
3346 assert!(five_hundred_prob > 0.59);
3347 assert!(five_hundred_prob < 0.60);
3349 scorer.historical_estimated_payment_success_probability(42, &target, 1, ¶ms).unwrap();
3350 assert!(one_prob < 0.85);
3351 assert!(one_prob > 0.84);
3353 // Advance the time forward 16 half-lives (which the docs claim will ensure all data is
3354 // gone), and check that we're back to where we started.
3355 SinceEpoch::advance(Duration::from_secs(10 * 16));
3356 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 168);
3357 // Once fully decayed we still have data, but its all-0s. In the future we may remove the
3358 // data entirely instead.
3359 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3361 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 1, ¶ms), None);
3363 let mut usage = ChannelUsage {
3365 inflight_htlc_msat: 1024,
3366 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
3368 scorer.payment_path_failed(&payment_path_for_amount(1), 42);
3369 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 2050);
3370 usage.inflight_htlc_msat = 0;
3371 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 866);
3373 let usage = ChannelUsage {
3375 inflight_htlc_msat: 0,
3376 effective_capacity: EffectiveCapacity::AdvertisedMaxHTLC { amount_msat: 0 },
3378 assert_eq!(scorer.channel_penalty_msat(42, &target, &source, usage, ¶ms), 2048);
3380 // Advance to decay all liquidity offsets to zero.
3381 SinceEpoch::advance(Duration::from_secs(60 * 60 * 10));
3383 // Use a path in the opposite direction, which have zero for htlc_maximum_msat. This will
3384 // ensure that the effective capacity is zero to test division-by-zero edge cases.
3386 path_hop(target_pubkey(), 43, 2),
3387 path_hop(source_pubkey(), 42, 1),
3388 path_hop(sender_pubkey(), 41, 0),
3390 scorer.payment_path_failed(&Path { hops: path, blinded_tail: None }, 42);
3394 fn adds_anti_probing_penalty() {
3395 let logger = TestLogger::new();
3396 let network_graph = network_graph(&logger);
3397 let source = source_node_id();
3398 let target = target_node_id();
3399 let params = ProbabilisticScoringFeeParameters {
3400 anti_probing_penalty_msat: 500,
3401 ..ProbabilisticScoringFeeParameters::zero_penalty()
3403 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3405 // Check we receive no penalty for a low htlc_maximum_msat.
3406 let usage = ChannelUsage {
3407 amount_msat: 512_000,
3408 inflight_htlc_msat: 0,
3409 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
3411 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
3413 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity.
3414 let usage = ChannelUsage {
3415 amount_msat: 512_000,
3416 inflight_htlc_msat: 0,
3417 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_024_000 },
3419 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 500);
3421 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity/2.
3422 let usage = ChannelUsage {
3423 amount_msat: 512_000,
3424 inflight_htlc_msat: 0,
3425 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 512_000 },
3427 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 500);
3429 // Check we receive no anti-probing penalty for htlc_maximum_msat == channel_capacity/2 - 1.
3430 let usage = ChannelUsage {
3431 amount_msat: 512_000,
3432 inflight_htlc_msat: 0,
3433 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 511_999 },
3435 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0);
3439 fn scores_with_blinded_path() {
3440 // Make sure we'll account for a blinded path's final_value_msat in scoring
3441 let logger = TestLogger::new();
3442 let network_graph = network_graph(&logger);
3443 let params = ProbabilisticScoringFeeParameters {
3444 liquidity_penalty_multiplier_msat: 1_000,
3445 ..ProbabilisticScoringFeeParameters::zero_penalty()
3447 let decay_params = ProbabilisticScoringDecayParameters::default();
3448 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3449 let source = source_node_id();
3450 let target = target_node_id();
3451 let usage = ChannelUsage {
3453 inflight_htlc_msat: 0,
3454 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
3456 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 300);
3458 let mut path = payment_path_for_amount(768);
3459 let recipient_hop = path.hops.pop().unwrap();
3460 let blinded_path = BlindedPath {
3461 introduction_node_id: path.hops.last().as_ref().unwrap().pubkey,
3462 blinding_point: test_utils::pubkey(42),
3464 BlindedHop { blinded_node_id: test_utils::pubkey(44), encrypted_payload: Vec::new() }
3467 path.blinded_tail = Some(BlindedTail {
3468 hops: blinded_path.blinded_hops,
3469 blinding_point: blinded_path.blinding_point,
3470 excess_final_cltv_expiry_delta: recipient_hop.cltv_expiry_delta,
3471 final_value_msat: recipient_hop.fee_msat,
3474 // Check the liquidity before and after scoring payment failures to ensure the blinded path's
3475 // final value is taken into account.
3476 assert!(scorer.channel_liquidities.get(&42).is_none());
3478 scorer.payment_path_failed(&path, 42);
3479 path.blinded_tail.as_mut().unwrap().final_value_msat = 256;
3480 scorer.payment_path_failed(&path, 43);
3482 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
3483 .as_directed(&source, &target, 1_000, decay_params);
3484 assert_eq!(liquidity.min_liquidity_msat(), 256);
3485 assert_eq!(liquidity.max_liquidity_msat(), 768);
3489 fn realistic_historical_failures() {
3490 // The motivation for the unequal sized buckets came largely from attempting to pay 10k
3491 // sats over a one bitcoin channel. This tests that case explicitly, ensuring that we score
3493 let logger = TestLogger::new();
3494 let mut network_graph = network_graph(&logger);
3495 let params = ProbabilisticScoringFeeParameters {
3496 historical_liquidity_penalty_multiplier_msat: 1024,
3497 historical_liquidity_penalty_amount_multiplier_msat: 1024,
3498 ..ProbabilisticScoringFeeParameters::zero_penalty()
3500 let decay_params = ProbabilisticScoringDecayParameters {
3501 liquidity_offset_half_life: Duration::from_secs(60 * 60),
3502 historical_no_updates_half_life: Duration::from_secs(10),
3503 ..ProbabilisticScoringDecayParameters::default()
3506 let capacity_msat = 100_000_000_000;
3507 update_channel(&mut network_graph, 42, source_privkey(), 0, capacity_msat, 200);
3508 update_channel(&mut network_graph, 42, target_privkey(), 1, capacity_msat, 200);
3510 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3511 let source = source_node_id();
3512 let target = target_node_id();
3514 let mut amount_msat = 10_000_000;
3515 let usage = ChannelUsage {
3517 inflight_htlc_msat: 0,
3518 effective_capacity: EffectiveCapacity::Total { capacity_msat, htlc_maximum_msat: capacity_msat },
3520 // With no historical data the normal liquidity penalty calculation is used, which results
3521 // in a success probability of ~75%.
3522 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 1269);
3523 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3525 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 42, ¶ms),
3528 // Fail to pay once, and then check the buckets and penalty.
3529 scorer.payment_path_failed(&payment_path_for_amount(amount_msat), 42);
3530 // The penalty should be the maximum penalty, as the payment we're scoring is now in the
3531 // same bucket which is the only maximum datapoint.
3532 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms),
3533 2048 + 2048 * amount_msat / super::AMOUNT_PENALTY_DIVISOR);
3534 // The "it failed" increment is 32, which we should apply to the first upper-bound (between
3535 // 6k sats and 12k sats).
3536 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3537 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],
3538 [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])));
3539 // The success probability estimate itself should be zero.
3540 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, amount_msat, ¶ms),
3543 // Now test again with the amount in the bottom bucket.
3545 // The new amount is entirely within the only minimum bucket with score, so the probability
3546 // we assign is 1/2.
3547 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, amount_msat, ¶ms),
3550 // ...but once we see a failure, we consider the payment to be substantially less likely,
3551 // even though not a probability of zero as we still look at the second max bucket which
3553 scorer.payment_path_failed(&payment_path_for_amount(amount_msat), 42);
3554 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3555 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],
3556 [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])));
3557 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, amount_msat, ¶ms),