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