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