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