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