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 [`Score`] 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, ProbabilisticScoringParameters};
23 //! # use lightning::chain::keysinterface::{KeysManager, KeysInterface};
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 = ProbabilisticScoringParameters::default();
36 //! let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
38 //! // Or use custom channel penalties.
39 //! let params = ProbabilisticScoringParameters {
40 //! liquidity_penalty_multiplier_msat: 2 * 1000,
41 //! ..ProbabilisticScoringParameters::default()
43 //! let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
44 //! # let random_seed_bytes = [42u8; 32];
46 //! let route = find_route(&payer, &route_params, &network_graph, None, &logger, &scorer, &random_seed_bytes);
52 //! Persisting when built with feature `no-std` and restoring without it, or vice versa, uses
53 //! different types and thus is undefined.
55 //! [`find_route`]: crate::routing::router::find_route
57 use ln::msgs::DecodeError;
58 use routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId};
59 use routing::router::RouteHop;
60 use util::ser::{Readable, ReadableArgs, Writeable, Writer};
61 use util::logger::Logger;
66 use core::cell::{RefCell, RefMut};
67 use core::convert::TryInto;
68 use core::ops::{Deref, DerefMut};
69 use core::time::Duration;
71 use sync::{Mutex, MutexGuard};
73 /// We define Score ever-so-slightly differently based on whether we are being built for C bindings
74 /// or not. For users, `LockableScore` must somehow be writeable to disk. For Rust users, this is
75 /// no problem - you move a `Score` that implements `Writeable` into a `Mutex`, lock it, and now
76 /// you have the original, concrete, `Score` type, which presumably implements `Writeable`.
78 /// For C users, once you've moved the `Score` into a `LockableScore` all you have after locking it
79 /// is an opaque trait object with an opaque pointer with no type info. Users could take the unsafe
80 /// approach of blindly casting that opaque pointer to a concrete type and calling `Writeable` from
81 /// there, but other languages downstream of the C bindings (e.g. Java) can't even do that.
82 /// Instead, we really want `Score` and `LockableScore` to implement `Writeable` directly, which we
83 /// do here by defining `Score` differently for `cfg(c_bindings)`.
84 macro_rules! define_score { ($($supertrait: path)*) => {
85 /// An interface used to score payment channels for path finding.
87 /// Scoring is in terms of fees willing to be paid in order to avoid routing through a channel.
88 pub trait Score $(: $supertrait)* {
89 /// Returns the fee in msats willing to be paid to avoid routing `send_amt_msat` through the
90 /// given channel in the direction from `source` to `target`.
92 /// The channel's capacity (less any other MPP parts that are also being considered for use in
93 /// the same payment) is given by `capacity_msat`. It may be determined from various sources
94 /// such as a chain data, network gossip, or invoice hints. For invoice hints, a capacity near
95 /// [`u64::max_value`] is given to indicate sufficient capacity for the invoice's full amount.
96 /// Thus, implementations should be overflow-safe.
97 fn channel_penalty_msat(
98 &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage
101 /// Handles updating channel penalties after failing to route through a channel.
102 fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64);
104 /// Handles updating channel penalties after successfully routing along a path.
105 fn payment_path_successful(&mut self, path: &[&RouteHop]);
107 /// Handles updating channel penalties after a probe over the given path failed.
108 fn probe_failed(&mut self, path: &[&RouteHop], short_channel_id: u64);
110 /// Handles updating channel penalties after a probe over the given path succeeded.
111 fn probe_successful(&mut self, path: &[&RouteHop]);
114 impl<S: Score, T: DerefMut<Target=S> $(+ $supertrait)*> Score for T {
115 fn channel_penalty_msat(
116 &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage
118 self.deref().channel_penalty_msat(short_channel_id, source, target, usage)
121 fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
122 self.deref_mut().payment_path_failed(path, short_channel_id)
125 fn payment_path_successful(&mut self, path: &[&RouteHop]) {
126 self.deref_mut().payment_path_successful(path)
129 fn probe_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
130 self.deref_mut().probe_failed(path, short_channel_id)
133 fn probe_successful(&mut self, path: &[&RouteHop]) {
134 self.deref_mut().probe_successful(path)
140 define_score!(Writeable);
141 #[cfg(not(c_bindings))]
144 /// A scorer that is accessed under a lock.
146 /// Needed so that calls to [`Score::channel_penalty_msat`] in [`find_route`] can be made while
147 /// having shared ownership of a scorer but without requiring internal locking in [`Score`]
148 /// implementations. Internal locking would be detrimental to route finding performance and could
149 /// result in [`Score::channel_penalty_msat`] returning a different value for the same channel.
151 /// [`find_route`]: crate::routing::router::find_route
152 pub trait LockableScore<'a> {
153 /// The locked [`Score`] type.
154 type Locked: 'a + Score;
156 /// Returns the locked scorer.
157 fn lock(&'a self) -> Self::Locked;
160 /// Refers to a scorer that is accessible under lock and also writeable to disk
162 /// We need this trait to be able to pass in a scorer to `lightning-background-processor` that will enable us to
163 /// use the Persister to persist it.
164 pub trait WriteableScore<'a>: LockableScore<'a> + Writeable {}
166 #[cfg(not(c_bindings))]
167 impl<'a, T> WriteableScore<'a> for T where T: LockableScore<'a> + Writeable {}
170 impl<'a, T: 'a + Score> LockableScore<'a> for Mutex<T> {
171 type Locked = MutexGuard<'a, T>;
173 fn lock(&'a self) -> MutexGuard<'a, T> {
174 Mutex::lock(self).unwrap()
178 impl<'a, T: 'a + Score> LockableScore<'a> for RefCell<T> {
179 type Locked = RefMut<'a, T>;
181 fn lock(&'a self) -> RefMut<'a, T> {
187 /// A concrete implementation of [`LockableScore`] which supports multi-threading.
188 pub struct MultiThreadedLockableScore<S: Score> {
192 /// A locked `MultiThreadedLockableScore`.
193 pub struct MultiThreadedScoreLock<'a, S: Score>(MutexGuard<'a, S>);
195 impl<'a, T: Score + 'a> Score for MultiThreadedScoreLock<'a, T> {
196 fn channel_penalty_msat(&self, scid: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage) -> u64 {
197 self.0.channel_penalty_msat(scid, source, target, usage)
199 fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
200 self.0.payment_path_failed(path, short_channel_id)
202 fn payment_path_successful(&mut self, path: &[&RouteHop]) {
203 self.0.payment_path_successful(path)
205 fn probe_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
206 self.0.probe_failed(path, short_channel_id)
208 fn probe_successful(&mut self, path: &[&RouteHop]) {
209 self.0.probe_successful(path)
213 impl<'a, T: Score + 'a> Writeable for MultiThreadedScoreLock<'a, T> {
214 fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
220 impl<'a, T: Score + 'a> LockableScore<'a> for MultiThreadedLockableScore<T> {
221 type Locked = MultiThreadedScoreLock<'a, T>;
223 fn lock(&'a self) -> MultiThreadedScoreLock<'a, T> {
224 MultiThreadedScoreLock(Mutex::lock(&self.score).unwrap())
229 impl<T: Score> MultiThreadedLockableScore<T> {
230 /// Creates a new [`MultiThreadedLockableScore`] given an underlying [`Score`].
231 pub fn new(score: T) -> Self {
232 MultiThreadedLockableScore { score: Mutex::new(score) }
238 impl<'a, T: Writeable> Writeable for RefMut<'a, T> {
239 fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
240 T::write(&**self, writer)
246 impl<'a, S: Writeable> Writeable for MutexGuard<'a, S> {
247 fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
248 S::write(&**self, writer)
252 /// Proposed use of a channel passed as a parameter to [`Score::channel_penalty_msat`].
253 #[derive(Clone, Copy, Debug)]
254 pub struct ChannelUsage {
255 /// The amount to send through the channel, denominated in millisatoshis.
256 pub amount_msat: u64,
258 /// Total amount, denominated in millisatoshis, already allocated to send through the channel
259 /// as part of a multi-path payment.
260 pub inflight_htlc_msat: u64,
262 /// The effective capacity of the channel.
263 pub effective_capacity: EffectiveCapacity,
267 /// [`Score`] implementation that uses a fixed penalty.
268 pub struct FixedPenaltyScorer {
272 impl FixedPenaltyScorer {
273 /// Creates a new scorer using `penalty_msat`.
274 pub fn with_penalty(penalty_msat: u64) -> Self {
275 Self { penalty_msat }
279 impl Score for FixedPenaltyScorer {
280 fn channel_penalty_msat(&self, _: u64, _: &NodeId, _: &NodeId, _: ChannelUsage) -> u64 {
284 fn payment_path_failed(&mut self, _path: &[&RouteHop], _short_channel_id: u64) {}
286 fn payment_path_successful(&mut self, _path: &[&RouteHop]) {}
288 fn probe_failed(&mut self, _path: &[&RouteHop], _short_channel_id: u64) {}
290 fn probe_successful(&mut self, _path: &[&RouteHop]) {}
293 impl Writeable for FixedPenaltyScorer {
295 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
296 write_tlv_fields!(w, {});
301 impl ReadableArgs<u64> for FixedPenaltyScorer {
303 fn read<R: Read>(r: &mut R, penalty_msat: u64) -> Result<Self, DecodeError> {
304 read_tlv_fields!(r, {});
305 Ok(Self { penalty_msat })
309 #[cfg(not(feature = "no-std"))]
310 type ConfiguredTime = std::time::Instant;
311 #[cfg(feature = "no-std")]
312 use util::time::Eternity;
313 #[cfg(feature = "no-std")]
314 type ConfiguredTime = Eternity;
316 /// [`Score`] implementation using channel success probability distributions.
318 /// Based on *Optimally Reliable & Cheap Payment Flows on the Lightning Network* by Rene Pickhardt
319 /// and Stefan Richter [[1]]. Given the uncertainty of channel liquidity balances, probability
320 /// distributions are defined based on knowledge learned from successful and unsuccessful attempts.
321 /// Then the negative `log10` of the success probability is used to determine the cost of routing a
322 /// specific HTLC amount through a channel.
324 /// Knowledge about channel liquidity balances takes the form of upper and lower bounds on the
325 /// possible liquidity. Certainty of the bounds is decreased over time using a decay function. See
326 /// [`ProbabilisticScoringParameters`] for details.
328 /// Since the scorer aims to learn the current channel liquidity balances, it works best for nodes
329 /// with high payment volume or that actively probe the [`NetworkGraph`]. Nodes with low payment
330 /// volume are more likely to experience failed payment paths, which would need to be retried.
334 /// Mixing the `no-std` feature between serialization and deserialization results in undefined
337 /// [1]: https://arxiv.org/abs/2107.05322
338 pub type ProbabilisticScorer<G, L> = ProbabilisticScorerUsingTime::<G, L, ConfiguredTime>;
340 /// Probabilistic [`Score`] implementation.
342 /// (C-not exported) generally all users should use the [`ProbabilisticScorer`] type alias.
343 pub struct ProbabilisticScorerUsingTime<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time>
344 where L::Target: Logger {
345 params: ProbabilisticScoringParameters,
348 // TODO: Remove entries of closed channels.
349 channel_liquidities: HashMap<u64, ChannelLiquidity<T>>,
352 /// Parameters for configuring [`ProbabilisticScorer`].
354 /// Used to configure base, liquidity, and amount penalties, the sum of which comprises the channel
355 /// penalty (i.e., the amount in msats willing to be paid to avoid routing through the channel).
357 /// The penalty applied to any channel by the [`ProbabilisticScorer`] is the sum of each of the
360 pub struct ProbabilisticScoringParameters {
361 /// A fixed penalty in msats to apply to each channel.
363 /// Default value: 500 msat
364 pub base_penalty_msat: u64,
366 /// A multiplier used with the payment amount to calculate a fixed penalty applied to each
367 /// channel, in excess of the [`base_penalty_msat`].
369 /// The purpose of the amount penalty is to avoid having fees dominate the channel cost (i.e.,
370 /// fees plus penalty) for large payments. The penalty is computed as the product of this
371 /// multiplier and `2^30`ths of the payment amount.
373 /// ie `base_penalty_amount_multiplier_msat * amount_msat / 2^30`
375 /// Default value: 8,192 msat
377 /// [`base_penalty_msat`]: Self::base_penalty_msat
378 pub base_penalty_amount_multiplier_msat: u64,
380 /// A multiplier used in conjunction with the negative `log10` of the channel's success
381 /// probability for a payment, as determined by our latest estimates of the channel's
382 /// liquidity, to determine the liquidity penalty.
384 /// The penalty is based in part on the knowledge learned from prior successful and unsuccessful
385 /// payments. This knowledge is decayed over time based on [`liquidity_offset_half_life`]. The
386 /// penalty is effectively limited to `2 * liquidity_penalty_multiplier_msat` (corresponding to
387 /// lower bounding the success probability to `0.01`) when the amount falls within the
388 /// uncertainty bounds of the channel liquidity balance. Amounts above the upper bound will
389 /// result in a `u64::max_value` penalty, however.
391 /// Default value: 30,000 msat
393 /// [`liquidity_offset_half_life`]: Self::liquidity_offset_half_life
394 pub liquidity_penalty_multiplier_msat: u64,
396 /// The time required to elapse before any knowledge learned about channel liquidity balances is
399 /// The bounds are defined in terms of offsets and are initially zero. Increasing the offsets
400 /// gives tighter bounds on the channel liquidity balance. Thus, halving the offsets decreases
401 /// the certainty of the channel liquidity balance.
403 /// Default value: 1 hour
407 /// When built with the `no-std` feature, time will never elapse. Therefore, the channel
408 /// liquidity knowledge will never decay except when the bounds cross.
409 pub liquidity_offset_half_life: Duration,
411 /// A multiplier used in conjunction with a payment amount and the negative `log10` of the
412 /// channel's success probability for the payment, as determined by our latest estimates of the
413 /// channel's liquidity, to determine the amount penalty.
415 /// The purpose of the amount penalty is to avoid having fees dominate the channel cost (i.e.,
416 /// fees plus penalty) for large payments. The penalty is computed as the product of this
417 /// multiplier and `2^20`ths of the payment amount, weighted by the negative `log10` of the
418 /// success probability.
420 /// `-log10(success_probability) * liquidity_penalty_amount_multiplier_msat * amount_msat / 2^20`
422 /// In practice, this means for 0.1 success probability (`-log10(0.1) == 1`) each `2^20`th of
423 /// the amount will result in a penalty of the multiplier. And, as the success probability
424 /// decreases, the negative `log10` weighting will increase dramatically. For higher success
425 /// probabilities, the multiplier will have a decreasing effect as the negative `log10` will
428 /// Default value: 192 msat
429 pub liquidity_penalty_amount_multiplier_msat: u64,
431 /// A multiplier used in conjunction with the negative `log10` of the channel's success
432 /// probability for the payment, as determined based on the history of our estimates of the
433 /// channel's available liquidity, to determine a penalty.
435 /// This penalty is similar to [`liquidity_penalty_multiplier_msat`], however, instead of using
436 /// only our latest estimate for the current liquidity available in the channel, it estimates
437 /// success probability based on the estimated liquidity available in the channel through
438 /// history. Specifically, every time we update our liquidity bounds on a given channel, we
439 /// track which of several buckets those bounds fall into, exponentially decaying the
440 /// probability of each bucket as new samples are added.
442 /// Default value: 10,000 msat
444 /// [`liquidity_penalty_multiplier_msat`]: Self::liquidity_penalty_multiplier_msat
445 pub historical_liquidity_penalty_multiplier_msat: u64,
447 /// A multiplier used in conjunction with the payment amount and the negative `log10` of the
448 /// channel's success probability for the payment, as determined based on the history of our
449 /// estimates of the channel's available liquidity, to determine a penalty.
451 /// The purpose of the amount penalty is to avoid having fees dominate the channel cost for
452 /// large payments. The penalty is computed as the product of this multiplier and the `2^20`ths
453 /// of the payment amount, weighted by the negative `log10` of the success probability.
455 /// This penalty is similar to [`liquidity_penalty_amount_multiplier_msat`], however, instead
456 /// of using only our latest estimate for the current liquidity available in the channel, it
457 /// estimates success probability based on the estimated liquidity available in the channel
458 /// through history. Specifically, every time we update our liquidity bounds on a given
459 /// channel, we track which of several buckets those bounds fall into, exponentially decaying
460 /// the probability of each bucket as new samples are added.
462 /// Default value: 64 msat
464 /// [`liquidity_penalty_amount_multiplier_msat`]: Self::liquidity_penalty_amount_multiplier_msat
465 pub historical_liquidity_penalty_amount_multiplier_msat: u64,
467 /// If we aren't learning any new datapoints for a channel, the historical liquidity bounds
468 /// tracking can simply live on with increasingly stale data. Instead, when a channel has not
469 /// seen a liquidity estimate update for this amount of time, the historical datapoints are
472 /// Note that after 16 or more half lives all historical data will be completely gone.
474 /// Default value: 14 days
475 pub historical_no_updates_half_life: Duration,
477 /// Manual penalties used for the given nodes. Allows to set a particular penalty for a given
478 /// node. Note that a manual penalty of `u64::max_value()` means the node would not ever be
479 /// considered during path finding.
482 pub manual_node_penalties: HashMap<NodeId, u64>,
484 /// This penalty is applied when `htlc_maximum_msat` is equal to or larger than half of the
485 /// channel's capacity, which makes us prefer nodes with a smaller `htlc_maximum_msat`. We
486 /// treat such nodes preferentially as this makes balance discovery attacks harder to execute,
487 /// thereby creating an incentive to restrict `htlc_maximum_msat` and improve privacy.
489 /// Default value: 250 msat
490 pub anti_probing_penalty_msat: u64,
492 /// This penalty is applied when the amount we're attempting to send over a channel exceeds our
493 /// current estimate of the channel's available liquidity.
495 /// Note that in this case all other penalties, including the
496 /// [`liquidity_penalty_multiplier_msat`] and [`liquidity_penalty_amount_multiplier_msat`]-based
497 /// penalties, as well as the [`base_penalty_msat`] and the [`anti_probing_penalty_msat`], if
498 /// applicable, are still included in the overall penalty.
500 /// If you wish to avoid creating paths with such channels entirely, setting this to a value of
501 /// `u64::max_value()` will guarantee that.
503 /// Default value: 1_0000_0000_000 msat (1 Bitcoin)
505 /// [`liquidity_penalty_multiplier_msat`]: Self::liquidity_penalty_multiplier_msat
506 /// [`liquidity_penalty_amount_multiplier_msat`]: Self::liquidity_penalty_amount_multiplier_msat
507 /// [`base_penalty_msat`]: Self::base_penalty_msat
508 /// [`anti_probing_penalty_msat`]: Self::anti_probing_penalty_msat
509 pub considered_impossible_penalty_msat: u64,
512 /// Tracks the historical state of a distribution as a weighted average of how much time was spent
513 /// in each of 8 buckets.
514 #[derive(Clone, Copy)]
515 struct HistoricalBucketRangeTracker {
519 impl HistoricalBucketRangeTracker {
520 fn new() -> Self { Self { buckets: [0; 8] } }
521 fn track_datapoint(&mut self, bucket_idx: u8) {
522 // We have 8 leaky buckets for min and max liquidity. Each bucket tracks the amount of time
523 // we spend in each bucket as a 16-bit fixed-point number with a 5 bit fractional part.
525 // Each time we update our liquidity estimate, we add 32 (1.0 in our fixed-point system) to
526 // the buckets for the current min and max liquidity offset positions.
528 // We then decay each bucket by multiplying by 2047/2048 (avoiding dividing by a
529 // non-power-of-two). This ensures we can't actually overflow the u16 - when we get to
530 // 63,457 adding 32 and decaying by 2047/2048 leaves us back at 63,457.
532 // In total, this allows us to track data for the last 8,000 or so payments across a given
535 // These constants are a balance - we try to fit in 2 bytes per bucket to reduce overhead,
536 // and need to balance having more bits in the decimal part (to ensure decay isn't too
537 // non-linear) with having too few bits in the mantissa, causing us to not store very many
540 // The constants were picked experimentally, selecting a decay amount that restricts us
541 // from overflowing buckets without having to cap them manually.
542 debug_assert!(bucket_idx < 8);
544 for e in self.buckets.iter_mut() {
545 *e = ((*e as u32) * 2047 / 2048) as u16;
547 self.buckets[bucket_idx as usize] = self.buckets[bucket_idx as usize].saturating_add(32);
550 /// Decay all buckets by the given number of half-lives. Used to more aggressively remove old
551 /// datapoints as we receive newer information.
552 fn time_decay_data(&mut self, half_lives: u32) {
553 for e in self.buckets.iter_mut() {
554 *e = e.checked_shr(half_lives).unwrap_or(0);
559 impl_writeable_tlv_based!(HistoricalBucketRangeTracker, { (0, buckets, required) });
561 struct HistoricalMinMaxBuckets<'a> {
562 min_liquidity_offset_history: &'a HistoricalBucketRangeTracker,
563 max_liquidity_offset_history: &'a HistoricalBucketRangeTracker,
566 impl HistoricalMinMaxBuckets<'_> {
568 fn calculate_success_probability_times_billion(&self, required_decays: u32, payment_amt_64th_bucket: u8) -> Option<u64> {
569 // If historical penalties are enabled, calculate the penalty by walking the set of
570 // historical liquidity bucket (min, max) combinations (where min_idx < max_idx) and, for
571 // each, calculate the probability of success given our payment amount, then total the
572 // weighted average probability of success.
574 // We use a sliding scale to decide which point within a given bucket will be compared to
575 // the amount being sent - for lower-bounds, the amount being sent is compared to the lower
576 // edge of the first bucket (i.e. zero), but compared to the upper 7/8ths of the last
577 // bucket (i.e. 9 times the index, or 63), with each bucket in between increasing the
578 // comparison point by 1/64th. For upper-bounds, the same applies, however with an offset
579 // of 1/64th (i.e. starting at one and ending at 64). This avoids failing to assign
580 // penalties to channels at the edges.
582 // If we used the bottom edge of buckets, we'd end up never assigning any penalty at all to
583 // such a channel when sending less than ~0.19% of the channel's capacity (e.g. ~200k sats
584 // for a 1 BTC channel!).
586 // If we used the middle of each bucket we'd never assign any penalty at all when sending
587 // less than 1/16th of a channel's capacity, or 1/8th if we used the top of the bucket.
588 let mut total_valid_points_tracked = 0;
590 // Rather than actually decaying the individual buckets, which would lose precision, we
591 // simply track whether all buckets would be decayed to zero, in which case we treat it as
592 // if we had no data.
593 let mut is_fully_decayed = true;
594 let mut check_track_bucket_contains_undecayed_points =
595 |bucket_val: u16| if bucket_val.checked_shr(required_decays).unwrap_or(0) > 0 { is_fully_decayed = false; };
597 for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate() {
598 check_track_bucket_contains_undecayed_points(*min_bucket);
599 for max_bucket in self.max_liquidity_offset_history.buckets.iter().take(8 - min_idx) {
600 total_valid_points_tracked += (*min_bucket as u64) * (*max_bucket as u64);
601 check_track_bucket_contains_undecayed_points(*max_bucket);
604 // If the total valid points is smaller than 1.0 (i.e. 32 in our fixed-point scheme), treat
605 // it as if we were fully decayed.
606 if total_valid_points_tracked.checked_shr(required_decays).unwrap_or(0) < 32*32 || is_fully_decayed {
610 let mut cumulative_success_prob_times_billion = 0;
611 for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate() {
612 for (max_idx, max_bucket) in self.max_liquidity_offset_history.buckets.iter().enumerate().take(8 - min_idx) {
613 let bucket_prob_times_million = (*min_bucket as u64) * (*max_bucket as u64)
614 * 1024 * 1024 / total_valid_points_tracked;
615 let min_64th_bucket = min_idx as u8 * 9;
616 let max_64th_bucket = (7 - max_idx as u8) * 9 + 1;
617 if payment_amt_64th_bucket > max_64th_bucket {
618 // Success probability 0, the payment amount is above the max liquidity
619 } else if payment_amt_64th_bucket <= min_64th_bucket {
620 cumulative_success_prob_times_billion += bucket_prob_times_million * 1024;
622 cumulative_success_prob_times_billion += bucket_prob_times_million *
623 ((max_64th_bucket - payment_amt_64th_bucket) as u64) * 1024 /
624 ((max_64th_bucket - min_64th_bucket) as u64);
629 Some(cumulative_success_prob_times_billion)
633 /// Accounting for channel liquidity balance uncertainty.
635 /// Direction is defined in terms of [`NodeId`] partial ordering, where the source node is the
636 /// first node in the ordering of the channel's counterparties. Thus, swapping the two liquidity
637 /// offset fields gives the opposite direction.
638 struct ChannelLiquidity<T: Time> {
639 /// Lower channel liquidity bound in terms of an offset from zero.
640 min_liquidity_offset_msat: u64,
642 /// Upper channel liquidity bound in terms of an offset from the effective capacity.
643 max_liquidity_offset_msat: u64,
645 /// Time when the liquidity bounds were last modified.
648 min_liquidity_offset_history: HistoricalBucketRangeTracker,
649 max_liquidity_offset_history: HistoricalBucketRangeTracker,
652 /// A snapshot of [`ChannelLiquidity`] in one direction assuming a certain channel capacity and
653 /// decayed with a given half life.
654 struct DirectedChannelLiquidity<'a, L: Deref<Target = u64>, BRT: Deref<Target = HistoricalBucketRangeTracker>, T: Time, U: Deref<Target = T>> {
655 min_liquidity_offset_msat: L,
656 max_liquidity_offset_msat: L,
657 min_liquidity_offset_history: BRT,
658 max_liquidity_offset_history: BRT,
662 params: &'a ProbabilisticScoringParameters,
665 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
666 /// Creates a new scorer using the given scoring parameters for sending payments from a node
667 /// through a network graph.
668 pub fn new(params: ProbabilisticScoringParameters, network_graph: G, logger: L) -> Self {
673 channel_liquidities: HashMap::new(),
678 fn with_channel(mut self, short_channel_id: u64, liquidity: ChannelLiquidity<T>) -> Self {
679 assert!(self.channel_liquidities.insert(short_channel_id, liquidity).is_none());
683 /// Dump the contents of this scorer into the configured logger.
685 /// Note that this writes roughly one line per channel for which we have a liquidity estimate,
686 /// which may be a substantial amount of log output.
687 pub fn debug_log_liquidity_stats(&self) {
688 let graph = self.network_graph.read_only();
689 for (scid, liq) in self.channel_liquidities.iter() {
690 if let Some(chan_debug) = graph.channels().get(scid) {
691 let log_direction = |source, target| {
692 if let Some((directed_info, _)) = chan_debug.as_directed_to(target) {
693 let amt = directed_info.effective_capacity().as_msat();
694 let dir_liq = liq.as_directed(source, target, amt, &self.params);
695 log_debug!(self.logger, "Liquidity from {:?} to {:?} via {} is in the range ({}, {})",
696 source, target, scid, dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat());
698 log_debug!(self.logger, "No amount known for SCID {} from {:?} to {:?}", scid, source, target);
702 log_direction(&chan_debug.node_one, &chan_debug.node_two);
703 log_direction(&chan_debug.node_two, &chan_debug.node_one);
705 log_debug!(self.logger, "No network graph entry for SCID {}", scid);
710 /// Query the estimated minimum and maximum liquidity available for sending a payment over the
711 /// channel with `scid` towards the given `target` node.
712 pub fn estimated_channel_liquidity_range(&self, scid: u64, target: &NodeId) -> Option<(u64, u64)> {
713 let graph = self.network_graph.read_only();
715 if let Some(chan) = graph.channels().get(&scid) {
716 if let Some(liq) = self.channel_liquidities.get(&scid) {
717 if let Some((directed_info, source)) = chan.as_directed_to(target) {
718 let amt = directed_info.effective_capacity().as_msat();
719 let dir_liq = liq.as_directed(source, target, amt, &self.params);
720 return Some((dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat()));
727 /// Marks the node with the given `node_id` as banned, i.e.,
728 /// it will be avoided during path finding.
729 pub fn add_banned(&mut self, node_id: &NodeId) {
730 self.params.manual_node_penalties.insert(*node_id, u64::max_value());
733 /// Removes the node with the given `node_id` from the list of nodes to avoid.
734 pub fn remove_banned(&mut self, node_id: &NodeId) {
735 self.params.manual_node_penalties.remove(node_id);
738 /// Sets a manual penalty for the given node.
739 pub fn set_manual_penalty(&mut self, node_id: &NodeId, penalty: u64) {
740 self.params.manual_node_penalties.insert(*node_id, penalty);
743 /// Removes the node with the given `node_id` from the list of manual penalties.
744 pub fn remove_manual_penalty(&mut self, node_id: &NodeId) {
745 self.params.manual_node_penalties.remove(node_id);
748 /// Clears the list of manual penalties that are applied during path finding.
749 pub fn clear_manual_penalties(&mut self) {
750 self.params.manual_node_penalties = HashMap::new();
754 impl ProbabilisticScoringParameters {
756 fn zero_penalty() -> Self {
758 base_penalty_msat: 0,
759 base_penalty_amount_multiplier_msat: 0,
760 liquidity_penalty_multiplier_msat: 0,
761 liquidity_offset_half_life: Duration::from_secs(3600),
762 liquidity_penalty_amount_multiplier_msat: 0,
763 historical_liquidity_penalty_multiplier_msat: 0,
764 historical_liquidity_penalty_amount_multiplier_msat: 0,
765 historical_no_updates_half_life: Duration::from_secs(60 * 60 * 24 * 14),
766 manual_node_penalties: HashMap::new(),
767 anti_probing_penalty_msat: 0,
768 considered_impossible_penalty_msat: 0,
772 /// Marks all nodes in the given list as banned, i.e.,
773 /// they will be avoided during path finding.
774 pub fn add_banned_from_list(&mut self, node_ids: Vec<NodeId>) {
776 self.manual_node_penalties.insert(id, u64::max_value());
781 impl Default for ProbabilisticScoringParameters {
782 fn default() -> Self {
784 base_penalty_msat: 500,
785 base_penalty_amount_multiplier_msat: 8192,
786 liquidity_penalty_multiplier_msat: 30_000,
787 liquidity_offset_half_life: Duration::from_secs(3600),
788 liquidity_penalty_amount_multiplier_msat: 192,
789 historical_liquidity_penalty_multiplier_msat: 10_000,
790 historical_liquidity_penalty_amount_multiplier_msat: 64,
791 historical_no_updates_half_life: Duration::from_secs(60 * 60 * 24 * 14),
792 manual_node_penalties: HashMap::new(),
793 anti_probing_penalty_msat: 250,
794 considered_impossible_penalty_msat: 1_0000_0000_000,
799 impl<T: Time> ChannelLiquidity<T> {
803 min_liquidity_offset_msat: 0,
804 max_liquidity_offset_msat: 0,
805 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
806 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
807 last_updated: T::now(),
811 /// Returns a view of the channel liquidity directed from `source` to `target` assuming
814 &self, source: &NodeId, target: &NodeId, capacity_msat: u64, params: &'a ProbabilisticScoringParameters
815 ) -> DirectedChannelLiquidity<'a, &u64, &HistoricalBucketRangeTracker, T, &T> {
816 let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) =
818 (&self.min_liquidity_offset_msat, &self.max_liquidity_offset_msat,
819 &self.min_liquidity_offset_history, &self.max_liquidity_offset_history)
821 (&self.max_liquidity_offset_msat, &self.min_liquidity_offset_msat,
822 &self.max_liquidity_offset_history, &self.min_liquidity_offset_history)
825 DirectedChannelLiquidity {
826 min_liquidity_offset_msat,
827 max_liquidity_offset_msat,
828 min_liquidity_offset_history,
829 max_liquidity_offset_history,
831 last_updated: &self.last_updated,
837 /// Returns a mutable view of the channel liquidity directed from `source` to `target` assuming
839 fn as_directed_mut<'a>(
840 &mut self, source: &NodeId, target: &NodeId, capacity_msat: u64, params: &'a ProbabilisticScoringParameters
841 ) -> DirectedChannelLiquidity<'a, &mut u64, &mut HistoricalBucketRangeTracker, T, &mut T> {
842 let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) =
844 (&mut self.min_liquidity_offset_msat, &mut self.max_liquidity_offset_msat,
845 &mut self.min_liquidity_offset_history, &mut self.max_liquidity_offset_history)
847 (&mut self.max_liquidity_offset_msat, &mut self.min_liquidity_offset_msat,
848 &mut self.max_liquidity_offset_history, &mut self.min_liquidity_offset_history)
851 DirectedChannelLiquidity {
852 min_liquidity_offset_msat,
853 max_liquidity_offset_msat,
854 min_liquidity_offset_history,
855 max_liquidity_offset_history,
857 last_updated: &mut self.last_updated,
864 /// Bounds `-log10` to avoid excessive liquidity penalties for payments with low success
866 const NEGATIVE_LOG10_UPPER_BOUND: u64 = 2;
868 /// The rough cutoff at which our precision falls off and we should stop bothering to try to log a
869 /// ratio, as X in 1/X.
870 const PRECISION_LOWER_BOUND_DENOMINATOR: u64 = approx::LOWER_BITS_BOUND;
872 /// The divisor used when computing the amount penalty.
873 const AMOUNT_PENALTY_DIVISOR: u64 = 1 << 20;
874 const BASE_AMOUNT_PENALTY_DIVISOR: u64 = 1 << 30;
876 impl<L: Deref<Target = u64>, BRT: Deref<Target = HistoricalBucketRangeTracker>, T: Time, U: Deref<Target = T>> DirectedChannelLiquidity<'_, L, BRT, T, U> {
877 /// Returns a liquidity penalty for routing the given HTLC `amount_msat` through the channel in
879 fn penalty_msat(&self, amount_msat: u64, params: &ProbabilisticScoringParameters) -> u64 {
880 let max_liquidity_msat = self.max_liquidity_msat();
881 let min_liquidity_msat = core::cmp::min(self.min_liquidity_msat(), max_liquidity_msat);
883 let mut res = if amount_msat <= min_liquidity_msat {
885 } else if amount_msat >= max_liquidity_msat {
886 // Equivalent to hitting the else clause below with the amount equal to the effective
887 // capacity and without any certainty on the liquidity upper bound, plus the
888 // impossibility penalty.
889 let negative_log10_times_2048 = NEGATIVE_LOG10_UPPER_BOUND * 2048;
890 Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
891 params.liquidity_penalty_multiplier_msat,
892 params.liquidity_penalty_amount_multiplier_msat)
893 .saturating_add(params.considered_impossible_penalty_msat)
895 let numerator = (max_liquidity_msat - amount_msat).saturating_add(1);
896 let denominator = (max_liquidity_msat - min_liquidity_msat).saturating_add(1);
897 if amount_msat - min_liquidity_msat < denominator / PRECISION_LOWER_BOUND_DENOMINATOR {
898 // If the failure probability is < 1.5625% (as 1 - numerator/denominator < 1/64),
899 // don't bother trying to use the log approximation as it gets too noisy to be
900 // particularly helpful, instead just round down to 0.
903 let negative_log10_times_2048 =
904 approx::negative_log10_times_2048(numerator, denominator);
905 Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
906 params.liquidity_penalty_multiplier_msat,
907 params.liquidity_penalty_amount_multiplier_msat)
911 if params.historical_liquidity_penalty_multiplier_msat != 0 ||
912 params.historical_liquidity_penalty_amount_multiplier_msat != 0 {
913 let required_decays = self.now.duration_since(*self.last_updated).as_secs()
914 .checked_div(params.historical_no_updates_half_life.as_secs())
915 .map_or(u32::max_value(), |decays| cmp::min(decays, u32::max_value() as u64) as u32);
916 let payment_amt_64th_bucket = amount_msat * 64 / self.capacity_msat;
917 debug_assert!(payment_amt_64th_bucket <= 64);
918 if payment_amt_64th_bucket > 64 { return res; }
920 let buckets = HistoricalMinMaxBuckets {
921 min_liquidity_offset_history: &self.min_liquidity_offset_history,
922 max_liquidity_offset_history: &self.max_liquidity_offset_history,
924 if let Some(cumulative_success_prob_times_billion) = buckets
925 .calculate_success_probability_times_billion(required_decays, payment_amt_64th_bucket as u8) {
926 let historical_negative_log10_times_2048 = approx::negative_log10_times_2048(cumulative_success_prob_times_billion + 1, 1024 * 1024 * 1024);
927 res = res.saturating_add(Self::combined_penalty_msat(amount_msat,
928 historical_negative_log10_times_2048, params.historical_liquidity_penalty_multiplier_msat,
929 params.historical_liquidity_penalty_amount_multiplier_msat));
931 // If we don't have any valid points (or, once decayed, we have less than a full
932 // point), redo the non-historical calculation with no liquidity bounds tracked and
933 // the historical penalty multipliers.
934 let max_capacity = self.capacity_msat.saturating_sub(amount_msat).saturating_add(1);
935 let negative_log10_times_2048 =
936 approx::negative_log10_times_2048(max_capacity, self.capacity_msat.saturating_add(1));
937 res = res.saturating_add(Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
938 params.historical_liquidity_penalty_multiplier_msat,
939 params.historical_liquidity_penalty_amount_multiplier_msat));
947 /// Computes the liquidity penalty from the penalty multipliers.
949 fn combined_penalty_msat(amount_msat: u64, negative_log10_times_2048: u64,
950 liquidity_penalty_multiplier_msat: u64, liquidity_penalty_amount_multiplier_msat: u64,
952 let liquidity_penalty_msat = {
953 // Upper bound the liquidity penalty to ensure some channel is selected.
954 let multiplier_msat = liquidity_penalty_multiplier_msat;
955 let max_penalty_msat = multiplier_msat.saturating_mul(NEGATIVE_LOG10_UPPER_BOUND);
956 (negative_log10_times_2048.saturating_mul(multiplier_msat) / 2048).min(max_penalty_msat)
958 let amount_penalty_msat = negative_log10_times_2048
959 .saturating_mul(liquidity_penalty_amount_multiplier_msat)
960 .saturating_mul(amount_msat) / 2048 / AMOUNT_PENALTY_DIVISOR;
962 liquidity_penalty_msat.saturating_add(amount_penalty_msat)
965 /// Returns the lower bound of the channel liquidity balance in this direction.
966 fn min_liquidity_msat(&self) -> u64 {
967 self.decayed_offset_msat(*self.min_liquidity_offset_msat)
970 /// Returns the upper bound of the channel liquidity balance in this direction.
971 fn max_liquidity_msat(&self) -> u64 {
973 .checked_sub(self.decayed_offset_msat(*self.max_liquidity_offset_msat))
977 fn decayed_offset_msat(&self, offset_msat: u64) -> u64 {
978 self.now.duration_since(*self.last_updated).as_secs()
979 .checked_div(self.params.liquidity_offset_half_life.as_secs())
980 .and_then(|decays| offset_msat.checked_shr(decays as u32))
985 impl<L: DerefMut<Target = u64>, BRT: DerefMut<Target = HistoricalBucketRangeTracker>, T: Time, U: DerefMut<Target = T>> DirectedChannelLiquidity<'_, L, BRT, T, U> {
986 /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat`.
987 fn failed_at_channel<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
988 let existing_max_msat = self.max_liquidity_msat();
989 if amount_msat < existing_max_msat {
990 log_debug!(logger, "Setting max liquidity of {} from {} to {}", chan_descr, existing_max_msat, amount_msat);
991 self.set_max_liquidity_msat(amount_msat);
993 log_trace!(logger, "Max liquidity of {} is {} (already less than or equal to {})",
994 chan_descr, existing_max_msat, amount_msat);
998 /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat` downstream.
999 fn failed_downstream<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
1000 let existing_min_msat = self.min_liquidity_msat();
1001 if amount_msat > existing_min_msat {
1002 log_debug!(logger, "Setting min liquidity of {} from {} to {}", existing_min_msat, chan_descr, amount_msat);
1003 self.set_min_liquidity_msat(amount_msat);
1005 log_trace!(logger, "Min liquidity of {} is {} (already greater than or equal to {})",
1006 chan_descr, existing_min_msat, amount_msat);
1010 /// Adjusts the channel liquidity balance bounds when successfully routing `amount_msat`.
1011 fn successful<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
1012 let max_liquidity_msat = self.max_liquidity_msat().checked_sub(amount_msat).unwrap_or(0);
1013 log_debug!(logger, "Subtracting {} from max liquidity of {} (setting it to {})", amount_msat, chan_descr, max_liquidity_msat);
1014 self.set_max_liquidity_msat(max_liquidity_msat);
1017 fn update_history_buckets(&mut self) {
1018 let half_lives = self.now.duration_since(*self.last_updated).as_secs()
1019 .checked_div(self.params.historical_no_updates_half_life.as_secs())
1020 .map(|v| v.try_into().unwrap_or(u32::max_value())).unwrap_or(u32::max_value());
1021 self.min_liquidity_offset_history.time_decay_data(half_lives);
1022 self.max_liquidity_offset_history.time_decay_data(half_lives);
1024 debug_assert!(*self.min_liquidity_offset_msat <= self.capacity_msat);
1025 self.min_liquidity_offset_history.track_datapoint(
1026 // Ensure the bucket index we pass is in the range [0, 7], even if the liquidity offset
1027 // is zero or the channel's capacity, though the second should generally never happen.
1028 (self.min_liquidity_offset_msat.saturating_sub(1) * 8 / self.capacity_msat)
1029 .try_into().unwrap_or(32)); // 32 is bogus for 8 buckets, and will be ignored
1030 debug_assert!(*self.max_liquidity_offset_msat <= self.capacity_msat);
1031 self.max_liquidity_offset_history.track_datapoint(
1032 // Ensure the bucket index we pass is in the range [0, 7], even if the liquidity offset
1033 // is zero or the channel's capacity, though the second should generally never happen.
1034 (self.max_liquidity_offset_msat.saturating_sub(1) * 8 / self.capacity_msat)
1035 .try_into().unwrap_or(32)); // 32 is bogus for 8 buckets, and will be ignored
1038 /// Adjusts the lower bound of the channel liquidity balance in this direction.
1039 fn set_min_liquidity_msat(&mut self, amount_msat: u64) {
1040 *self.min_liquidity_offset_msat = amount_msat;
1041 *self.max_liquidity_offset_msat = if amount_msat > self.max_liquidity_msat() {
1044 self.decayed_offset_msat(*self.max_liquidity_offset_msat)
1046 self.update_history_buckets();
1047 *self.last_updated = self.now;
1050 /// Adjusts the upper bound of the channel liquidity balance in this direction.
1051 fn set_max_liquidity_msat(&mut self, amount_msat: u64) {
1052 *self.max_liquidity_offset_msat = self.capacity_msat.checked_sub(amount_msat).unwrap_or(0);
1053 *self.min_liquidity_offset_msat = if amount_msat < self.min_liquidity_msat() {
1056 self.decayed_offset_msat(*self.min_liquidity_offset_msat)
1058 self.update_history_buckets();
1059 *self.last_updated = self.now;
1063 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Score for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1064 fn channel_penalty_msat(
1065 &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage
1067 if let Some(penalty) = self.params.manual_node_penalties.get(target) {
1071 let base_penalty_msat = self.params.base_penalty_msat.saturating_add(
1072 self.params.base_penalty_amount_multiplier_msat
1073 .saturating_mul(usage.amount_msat) / BASE_AMOUNT_PENALTY_DIVISOR);
1075 let mut anti_probing_penalty_msat = 0;
1076 match usage.effective_capacity {
1077 EffectiveCapacity::ExactLiquidity { liquidity_msat } => {
1078 if usage.amount_msat > liquidity_msat {
1079 return u64::max_value();
1081 return base_penalty_msat;
1084 EffectiveCapacity::Total { capacity_msat, htlc_maximum_msat: Some(htlc_maximum_msat) } => {
1085 if htlc_maximum_msat >= capacity_msat/2 {
1086 anti_probing_penalty_msat = self.params.anti_probing_penalty_msat;
1092 let amount_msat = usage.amount_msat;
1093 let capacity_msat = usage.effective_capacity.as_msat()
1094 .saturating_sub(usage.inflight_htlc_msat);
1095 self.channel_liquidities
1096 .get(&short_channel_id)
1097 .unwrap_or(&ChannelLiquidity::new())
1098 .as_directed(source, target, capacity_msat, &self.params)
1099 .penalty_msat(amount_msat, &self.params)
1100 .saturating_add(anti_probing_penalty_msat)
1101 .saturating_add(base_penalty_msat)
1104 fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
1105 let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
1106 log_trace!(self.logger, "Scoring path through to SCID {} as having failed at {} msat", short_channel_id, amount_msat);
1107 let network_graph = self.network_graph.read_only();
1108 for (hop_idx, hop) in path.iter().enumerate() {
1109 let target = NodeId::from_pubkey(&hop.pubkey);
1110 let channel_directed_from_source = network_graph.channels()
1111 .get(&hop.short_channel_id)
1112 .and_then(|channel| channel.as_directed_to(&target));
1114 if hop.short_channel_id == short_channel_id && hop_idx == 0 {
1115 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);
1118 // Only score announced channels.
1119 if let Some((channel, source)) = channel_directed_from_source {
1120 let capacity_msat = channel.effective_capacity().as_msat();
1121 if hop.short_channel_id == short_channel_id {
1122 self.channel_liquidities
1123 .entry(hop.short_channel_id)
1124 .or_insert_with(ChannelLiquidity::new)
1125 .as_directed_mut(source, &target, capacity_msat, &self.params)
1126 .failed_at_channel(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1130 self.channel_liquidities
1131 .entry(hop.short_channel_id)
1132 .or_insert_with(ChannelLiquidity::new)
1133 .as_directed_mut(source, &target, capacity_msat, &self.params)
1134 .failed_downstream(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1136 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).",
1137 hop.short_channel_id);
1142 fn payment_path_successful(&mut self, path: &[&RouteHop]) {
1143 let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
1144 log_trace!(self.logger, "Scoring path through SCID {} as having succeeded at {} msat.",
1145 path.split_last().map(|(hop, _)| hop.short_channel_id).unwrap_or(0), amount_msat);
1146 let network_graph = self.network_graph.read_only();
1148 let target = NodeId::from_pubkey(&hop.pubkey);
1149 let channel_directed_from_source = network_graph.channels()
1150 .get(&hop.short_channel_id)
1151 .and_then(|channel| channel.as_directed_to(&target));
1153 // Only score announced channels.
1154 if let Some((channel, source)) = channel_directed_from_source {
1155 let capacity_msat = channel.effective_capacity().as_msat();
1156 self.channel_liquidities
1157 .entry(hop.short_channel_id)
1158 .or_insert_with(ChannelLiquidity::new)
1159 .as_directed_mut(source, &target, capacity_msat, &self.params)
1160 .successful(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1162 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).",
1163 hop.short_channel_id);
1168 fn probe_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
1169 self.payment_path_failed(path, short_channel_id)
1172 fn probe_successful(&mut self, path: &[&RouteHop]) {
1173 self.payment_path_failed(path, u64::max_value())
1178 const BITS: u32 = 64;
1179 const HIGHEST_BIT: u32 = BITS - 1;
1180 const LOWER_BITS: u32 = 6;
1181 pub(super) const LOWER_BITS_BOUND: u64 = 1 << LOWER_BITS;
1182 const LOWER_BITMASK: u64 = (1 << LOWER_BITS) - 1;
1184 /// Look-up table for `log10(x) * 2048` where row `i` is used for each `x` having `i` as the
1185 /// most significant bit. The next 4 bits of `x`, if applicable, are used for the second index.
1186 const LOG10_TIMES_2048: [[u16; (LOWER_BITS_BOUND) as usize]; BITS as usize] = [
1187 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1188 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1189 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1190 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
1191 [617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
1192 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
1193 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977,
1194 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977],
1195 [1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233,
1196 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431,
1197 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594,
1198 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731],
1199 [1850, 1850, 1850, 1850, 1850, 1850, 1850, 1850, 1954, 1954, 1954, 1954, 1954, 1954, 1954, 1954,
1200 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2133, 2133, 2133, 2133, 2133, 2133, 2133, 2133,
1201 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2281, 2281, 2281, 2281, 2281, 2281, 2281, 2281,
1202 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2409, 2409, 2409, 2409, 2409, 2409, 2409, 2409],
1203 [2466, 2466, 2466, 2466, 2520, 2520, 2520, 2520, 2571, 2571, 2571, 2571, 2619, 2619, 2619, 2619,
1204 2665, 2665, 2665, 2665, 2708, 2708, 2708, 2708, 2749, 2749, 2749, 2749, 2789, 2789, 2789, 2789,
1205 2827, 2827, 2827, 2827, 2863, 2863, 2863, 2863, 2898, 2898, 2898, 2898, 2931, 2931, 2931, 2931,
1206 2964, 2964, 2964, 2964, 2995, 2995, 2995, 2995, 3025, 3025, 3025, 3025, 3054, 3054, 3054, 3054],
1207 [3083, 3083, 3110, 3110, 3136, 3136, 3162, 3162, 3187, 3187, 3212, 3212, 3235, 3235, 3259, 3259,
1208 3281, 3281, 3303, 3303, 3324, 3324, 3345, 3345, 3366, 3366, 3386, 3386, 3405, 3405, 3424, 3424,
1209 3443, 3443, 3462, 3462, 3479, 3479, 3497, 3497, 3514, 3514, 3531, 3531, 3548, 3548, 3564, 3564,
1210 3580, 3580, 3596, 3596, 3612, 3612, 3627, 3627, 3642, 3642, 3656, 3656, 3671, 3671, 3685, 3685],
1211 [3699, 3713, 3726, 3740, 3753, 3766, 3779, 3791, 3804, 3816, 3828, 3840, 3852, 3864, 3875, 3886,
1212 3898, 3909, 3919, 3930, 3941, 3951, 3962, 3972, 3982, 3992, 4002, 4012, 4022, 4031, 4041, 4050,
1213 4060, 4069, 4078, 4087, 4096, 4105, 4114, 4122, 4131, 4139, 4148, 4156, 4164, 4173, 4181, 4189,
1214 4197, 4205, 4213, 4220, 4228, 4236, 4243, 4251, 4258, 4266, 4273, 4280, 4287, 4294, 4302, 4309],
1215 [4316, 4329, 4343, 4356, 4369, 4382, 4395, 4408, 4420, 4433, 4445, 4457, 4468, 4480, 4492, 4503,
1216 4514, 4525, 4536, 4547, 4557, 4568, 4578, 4589, 4599, 4609, 4619, 4629, 4638, 4648, 4657, 4667,
1217 4676, 4685, 4695, 4704, 4713, 4721, 4730, 4739, 4747, 4756, 4764, 4773, 4781, 4789, 4797, 4805,
1218 4813, 4821, 4829, 4837, 4845, 4852, 4860, 4867, 4875, 4882, 4889, 4897, 4904, 4911, 4918, 4925],
1219 [4932, 4946, 4959, 4973, 4986, 4999, 5012, 5024, 5037, 5049, 5061, 5073, 5085, 5097, 5108, 5119,
1220 5131, 5142, 5153, 5163, 5174, 5184, 5195, 5205, 5215, 5225, 5235, 5245, 5255, 5264, 5274, 5283,
1221 5293, 5302, 5311, 5320, 5329, 5338, 5347, 5355, 5364, 5372, 5381, 5389, 5397, 5406, 5414, 5422,
1222 5430, 5438, 5446, 5453, 5461, 5469, 5476, 5484, 5491, 5499, 5506, 5513, 5520, 5527, 5535, 5542],
1223 [5549, 5562, 5576, 5589, 5603, 5615, 5628, 5641, 5653, 5666, 5678, 5690, 5701, 5713, 5725, 5736,
1224 5747, 5758, 5769, 5780, 5790, 5801, 5811, 5822, 5832, 5842, 5852, 5862, 5871, 5881, 5890, 5900,
1225 5909, 5918, 5928, 5937, 5946, 5954, 5963, 5972, 5980, 5989, 5997, 6006, 6014, 6022, 6030, 6038,
1226 6046, 6054, 6062, 6070, 6078, 6085, 6093, 6100, 6108, 6115, 6122, 6130, 6137, 6144, 6151, 6158],
1227 [6165, 6179, 6192, 6206, 6219, 6232, 6245, 6257, 6270, 6282, 6294, 6306, 6318, 6330, 6341, 6352,
1228 6364, 6375, 6386, 6396, 6407, 6417, 6428, 6438, 6448, 6458, 6468, 6478, 6488, 6497, 6507, 6516,
1229 6526, 6535, 6544, 6553, 6562, 6571, 6580, 6588, 6597, 6605, 6614, 6622, 6630, 6639, 6647, 6655,
1230 6663, 6671, 6679, 6686, 6694, 6702, 6709, 6717, 6724, 6732, 6739, 6746, 6753, 6761, 6768, 6775],
1231 [6782, 6795, 6809, 6822, 6836, 6849, 6861, 6874, 6886, 6899, 6911, 6923, 6934, 6946, 6958, 6969,
1232 6980, 6991, 7002, 7013, 7023, 7034, 7044, 7055, 7065, 7075, 7085, 7095, 7104, 7114, 7124, 7133,
1233 7142, 7151, 7161, 7170, 7179, 7187, 7196, 7205, 7213, 7222, 7230, 7239, 7247, 7255, 7263, 7271,
1234 7279, 7287, 7295, 7303, 7311, 7318, 7326, 7333, 7341, 7348, 7355, 7363, 7370, 7377, 7384, 7391],
1235 [7398, 7412, 7425, 7439, 7452, 7465, 7478, 7490, 7503, 7515, 7527, 7539, 7551, 7563, 7574, 7585,
1236 7597, 7608, 7619, 7629, 7640, 7651, 7661, 7671, 7681, 7691, 7701, 7711, 7721, 7731, 7740, 7749,
1237 7759, 7768, 7777, 7786, 7795, 7804, 7813, 7821, 7830, 7838, 7847, 7855, 7864, 7872, 7880, 7888,
1238 7896, 7904, 7912, 7919, 7927, 7935, 7942, 7950, 7957, 7965, 7972, 7979, 7986, 7994, 8001, 8008],
1239 [8015, 8028, 8042, 8055, 8069, 8082, 8094, 8107, 8119, 8132, 8144, 8156, 8167, 8179, 8191, 8202,
1240 8213, 8224, 8235, 8246, 8256, 8267, 8277, 8288, 8298, 8308, 8318, 8328, 8337, 8347, 8357, 8366,
1241 8375, 8384, 8394, 8403, 8412, 8420, 8429, 8438, 8446, 8455, 8463, 8472, 8480, 8488, 8496, 8504,
1242 8512, 8520, 8528, 8536, 8544, 8551, 8559, 8566, 8574, 8581, 8588, 8596, 8603, 8610, 8617, 8624],
1243 [8631, 8645, 8659, 8672, 8685, 8698, 8711, 8723, 8736, 8748, 8760, 8772, 8784, 8796, 8807, 8818,
1244 8830, 8841, 8852, 8862, 8873, 8884, 8894, 8904, 8914, 8924, 8934, 8944, 8954, 8964, 8973, 8982,
1245 8992, 9001, 9010, 9019, 9028, 9037, 9046, 9054, 9063, 9071, 9080, 9088, 9097, 9105, 9113, 9121,
1246 9129, 9137, 9145, 9152, 9160, 9168, 9175, 9183, 9190, 9198, 9205, 9212, 9219, 9227, 9234, 9241],
1247 [9248, 9261, 9275, 9288, 9302, 9315, 9327, 9340, 9352, 9365, 9377, 9389, 9400, 9412, 9424, 9435,
1248 9446, 9457, 9468, 9479, 9490, 9500, 9510, 9521, 9531, 9541, 9551, 9561, 9570, 9580, 9590, 9599,
1249 9608, 9617, 9627, 9636, 9645, 9653, 9662, 9671, 9679, 9688, 9696, 9705, 9713, 9721, 9729, 9737,
1250 9745, 9753, 9761, 9769, 9777, 9784, 9792, 9799, 9807, 9814, 9821, 9829, 9836, 9843, 9850, 9857],
1251 [9864, 9878, 9892, 9905, 9918, 9931, 9944, 9956, 9969, 9981, 9993, 10005, 10017, 10029, 10040, 10051,
1252 10063, 10074, 10085, 10095, 10106, 10117, 10127, 10137, 10147, 10157, 10167, 10177, 10187, 10197, 10206, 10215,
1253 10225, 10234, 10243, 10252, 10261, 10270, 10279, 10287, 10296, 10304, 10313, 10321, 10330, 10338, 10346, 10354,
1254 10362, 10370, 10378, 10385, 10393, 10401, 10408, 10416, 10423, 10431, 10438, 10445, 10452, 10460, 10467, 10474],
1255 [10481, 10494, 10508, 10521, 10535, 10548, 10560, 10573, 10585, 10598, 10610, 10622, 10634, 10645, 10657, 10668,
1256 10679, 10690, 10701, 10712, 10723, 10733, 10743, 10754, 10764, 10774, 10784, 10794, 10803, 10813, 10823, 10832,
1257 10841, 10851, 10860, 10869, 10878, 10886, 10895, 10904, 10912, 10921, 10929, 10938, 10946, 10954, 10962, 10970,
1258 10978, 10986, 10994, 11002, 11010, 11017, 11025, 11032, 11040, 11047, 11054, 11062, 11069, 11076, 11083, 11090],
1259 [11097, 11111, 11125, 11138, 11151, 11164, 11177, 11189, 11202, 11214, 11226, 11238, 11250, 11262, 11273, 11284,
1260 11296, 11307, 11318, 11328, 11339, 11350, 11360, 11370, 11380, 11390, 11400, 11410, 11420, 11430, 11439, 11448,
1261 11458, 11467, 11476, 11485, 11494, 11503, 11512, 11520, 11529, 11538, 11546, 11554, 11563, 11571, 11579, 11587,
1262 11595, 11603, 11611, 11618, 11626, 11634, 11641, 11649, 11656, 11664, 11671, 11678, 11685, 11693, 11700, 11707],
1263 [11714, 11727, 11741, 11754, 11768, 11781, 11793, 11806, 11818, 11831, 11843, 11855, 11867, 11878, 11890, 11901,
1264 11912, 11923, 11934, 11945, 11956, 11966, 11976, 11987, 11997, 12007, 12017, 12027, 12036, 12046, 12056, 12065,
1265 12074, 12084, 12093, 12102, 12111, 12119, 12128, 12137, 12146, 12154, 12162, 12171, 12179, 12187, 12195, 12203,
1266 12211, 12219, 12227, 12235, 12243, 12250, 12258, 12265, 12273, 12280, 12287, 12295, 12302, 12309, 12316, 12323],
1267 [12330, 12344, 12358, 12371, 12384, 12397, 12410, 12423, 12435, 12447, 12459, 12471, 12483, 12495, 12506, 12517,
1268 12529, 12540, 12551, 12561, 12572, 12583, 12593, 12603, 12613, 12623, 12633, 12643, 12653, 12663, 12672, 12682,
1269 12691, 12700, 12709, 12718, 12727, 12736, 12745, 12753, 12762, 12771, 12779, 12787, 12796, 12804, 12812, 12820,
1270 12828, 12836, 12844, 12851, 12859, 12867, 12874, 12882, 12889, 12897, 12904, 12911, 12918, 12926, 12933, 12940],
1271 [12947, 12960, 12974, 12987, 13001, 13014, 13026, 13039, 13051, 13064, 13076, 13088, 13100, 13111, 13123, 13134,
1272 13145, 13156, 13167, 13178, 13189, 13199, 13209, 13220, 13230, 13240, 13250, 13260, 13269, 13279, 13289, 13298,
1273 13307, 13317, 13326, 13335, 13344, 13352, 13361, 13370, 13379, 13387, 13395, 13404, 13412, 13420, 13428, 13436,
1274 13444, 13452, 13460, 13468, 13476, 13483, 13491, 13498, 13506, 13513, 13521, 13528, 13535, 13542, 13549, 13556],
1275 [13563, 13577, 13591, 13604, 13617, 13630, 13643, 13656, 13668, 13680, 13692, 13704, 13716, 13728, 13739, 13750,
1276 13762, 13773, 13784, 13794, 13805, 13816, 13826, 13836, 13846, 13857, 13866, 13876, 13886, 13896, 13905, 13915,
1277 13924, 13933, 13942, 13951, 13960, 13969, 13978, 13986, 13995, 14004, 14012, 14020, 14029, 14037, 14045, 14053,
1278 14061, 14069, 14077, 14084, 14092, 14100, 14107, 14115, 14122, 14130, 14137, 14144, 14151, 14159, 14166, 14173],
1279 [14180, 14194, 14207, 14220, 14234, 14247, 14259, 14272, 14284, 14297, 14309, 14321, 14333, 14344, 14356, 14367,
1280 14378, 14389, 14400, 14411, 14422, 14432, 14443, 14453, 14463, 14473, 14483, 14493, 14502, 14512, 14522, 14531,
1281 14540, 14550, 14559, 14568, 14577, 14586, 14594, 14603, 14612, 14620, 14628, 14637, 14645, 14653, 14661, 14669,
1282 14677, 14685, 14693, 14701, 14709, 14716, 14724, 14731, 14739, 14746, 14754, 14761, 14768, 14775, 14782, 14789],
1283 [14796, 14810, 14824, 14837, 14850, 14863, 14876, 14889, 14901, 14913, 14925, 14937, 14949, 14961, 14972, 14984,
1284 14995, 15006, 15017, 15027, 15038, 15049, 15059, 15069, 15079, 15090, 15099, 15109, 15119, 15129, 15138, 15148,
1285 15157, 15166, 15175, 15184, 15193, 15202, 15211, 15219, 15228, 15237, 15245, 15253, 15262, 15270, 15278, 15286,
1286 15294, 15302, 15310, 15317, 15325, 15333, 15340, 15348, 15355, 15363, 15370, 15377, 15384, 15392, 15399, 15406],
1287 [15413, 15427, 15440, 15453, 15467, 15480, 15492, 15505, 15517, 15530, 15542, 15554, 15566, 15577, 15589, 15600,
1288 15611, 15622, 15633, 15644, 15655, 15665, 15676, 15686, 15696, 15706, 15716, 15726, 15736, 15745, 15755, 15764,
1289 15773, 15783, 15792, 15801, 15810, 15819, 15827, 15836, 15845, 15853, 15862, 15870, 15878, 15886, 15894, 15903,
1290 15910, 15918, 15926, 15934, 15942, 15949, 15957, 15964, 15972, 15979, 15987, 15994, 16001, 16008, 16015, 16022],
1291 [16029, 16043, 16057, 16070, 16083, 16096, 16109, 16122, 16134, 16146, 16158, 16170, 16182, 16194, 16205, 16217,
1292 16228, 16239, 16250, 16260, 16271, 16282, 16292, 16302, 16312, 16323, 16332, 16342, 16352, 16362, 16371, 16381,
1293 16390, 16399, 16408, 16417, 16426, 16435, 16444, 16452, 16461, 16470, 16478, 16486, 16495, 16503, 16511, 16519,
1294 16527, 16535, 16543, 16550, 16558, 16566, 16573, 16581, 16588, 16596, 16603, 16610, 16618, 16625, 16632, 16639],
1295 [16646, 16660, 16673, 16686, 16700, 16713, 16725, 16738, 16751, 16763, 16775, 16787, 16799, 16810, 16822, 16833,
1296 16844, 16855, 16866, 16877, 16888, 16898, 16909, 16919, 16929, 16939, 16949, 16959, 16969, 16978, 16988, 16997,
1297 17006, 17016, 17025, 17034, 17043, 17052, 17060, 17069, 17078, 17086, 17095, 17103, 17111, 17119, 17127, 17136,
1298 17143, 17151, 17159, 17167, 17175, 17182, 17190, 17197, 17205, 17212, 17220, 17227, 17234, 17241, 17248, 17255],
1299 [17262, 17276, 17290, 17303, 17316, 17329, 17342, 17355, 17367, 17379, 17391, 17403, 17415, 17427, 17438, 17450,
1300 17461, 17472, 17483, 17493, 17504, 17515, 17525, 17535, 17546, 17556, 17565, 17575, 17585, 17595, 17604, 17614,
1301 17623, 17632, 17641, 17650, 17659, 17668, 17677, 17685, 17694, 17703, 17711, 17719, 17728, 17736, 17744, 17752,
1302 17760, 17768, 17776, 17784, 17791, 17799, 17806, 17814, 17821, 17829, 17836, 17843, 17851, 17858, 17865, 17872],
1303 [17879, 17893, 17906, 17920, 17933, 17946, 17958, 17971, 17984, 17996, 18008, 18020, 18032, 18043, 18055, 18066,
1304 18077, 18088, 18099, 18110, 18121, 18131, 18142, 18152, 18162, 18172, 18182, 18192, 18202, 18211, 18221, 18230,
1305 18239, 18249, 18258, 18267, 18276, 18285, 18293, 18302, 18311, 18319, 18328, 18336, 18344, 18352, 18360, 18369,
1306 18377, 18384, 18392, 18400, 18408, 18415, 18423, 18430, 18438, 18445, 18453, 18460, 18467, 18474, 18481, 18488],
1307 [18495, 18509, 18523, 18536, 18549, 18562, 18575, 18588, 18600, 18612, 18624, 18636, 18648, 18660, 18671, 18683,
1308 18694, 18705, 18716, 18726, 18737, 18748, 18758, 18768, 18779, 18789, 18799, 18808, 18818, 18828, 18837, 18847,
1309 18856, 18865, 18874, 18883, 18892, 18901, 18910, 18919, 18927, 18936, 18944, 18952, 18961, 18969, 18977, 18985,
1310 18993, 19001, 19009, 19017, 19024, 19032, 19039, 19047, 19054, 19062, 19069, 19076, 19084, 19091, 19098, 19105],
1311 [19112, 19126, 19139, 19153, 19166, 19179, 19191, 19204, 19217, 19229, 19241, 19253, 19265, 19276, 19288, 19299,
1312 19310, 19321, 19332, 19343, 19354, 19364, 19375, 19385, 19395, 19405, 19415, 19425, 19435, 19444, 19454, 19463,
1313 19472, 19482, 19491, 19500, 19509, 19518, 19526, 19535, 19544, 19552, 19561, 19569, 19577, 19585, 19594, 19602,
1314 19610, 19617, 19625, 19633, 19641, 19648, 19656, 19663, 19671, 19678, 19686, 19693, 19700, 19707, 19714, 19721],
1315 [19728, 19742, 19756, 19769, 19782, 19795, 19808, 19821, 19833, 19845, 19857, 19869, 19881, 19893, 19904, 19916,
1316 19927, 19938, 19949, 19960, 19970, 19981, 19991, 20001, 20012, 20022, 20032, 20041, 20051, 20061, 20070, 20080,
1317 20089, 20098, 20107, 20116, 20125, 20134, 20143, 20152, 20160, 20169, 20177, 20185, 20194, 20202, 20210, 20218,
1318 20226, 20234, 20242, 20250, 20257, 20265, 20272, 20280, 20287, 20295, 20302, 20309, 20317, 20324, 20331, 20338],
1319 [20345, 20359, 20372, 20386, 20399, 20412, 20425, 20437, 20450, 20462, 20474, 20486, 20498, 20509, 20521, 20532,
1320 20543, 20554, 20565, 20576, 20587, 20597, 20608, 20618, 20628, 20638, 20648, 20658, 20668, 20677, 20687, 20696,
1321 20705, 20715, 20724, 20733, 20742, 20751, 20759, 20768, 20777, 20785, 20794, 20802, 20810, 20818, 20827, 20835,
1322 20843, 20850, 20858, 20866, 20874, 20881, 20889, 20896, 20904, 20911, 20919, 20926, 20933, 20940, 20947, 20954],
1323 [20961, 20975, 20989, 21002, 21015, 21028, 21041, 21054, 21066, 21078, 21090, 21102, 21114, 21126, 21137, 21149,
1324 21160, 21171, 21182, 21193, 21203, 21214, 21224, 21234, 21245, 21255, 21265, 21274, 21284, 21294, 21303, 21313,
1325 21322, 21331, 21340, 21349, 21358, 21367, 21376, 21385, 21393, 21402, 21410, 21418, 21427, 21435, 21443, 21451,
1326 21459, 21467, 21475, 21483, 21490, 21498, 21505, 21513, 21520, 21528, 21535, 21542, 21550, 21557, 21564, 21571],
1327 [21578, 21592, 21605, 21619, 21632, 21645, 21658, 21670, 21683, 21695, 21707, 21719, 21731, 21742, 21754, 21765,
1328 21776, 21787, 21798, 21809, 21820, 21830, 21841, 21851, 21861, 21871, 21881, 21891, 21901, 21910, 21920, 21929,
1329 21938, 21948, 21957, 21966, 21975, 21984, 21992, 22001, 22010, 22018, 22027, 22035, 22043, 22051, 22060, 22068,
1330 22076, 22083, 22091, 22099, 22107, 22114, 22122, 22129, 22137, 22144, 22152, 22159, 22166, 22173, 22180, 22187],
1331 [22194, 22208, 22222, 22235, 22248, 22261, 22274, 22287, 22299, 22311, 22323, 22335, 22347, 22359, 22370, 22382,
1332 22393, 22404, 22415, 22426, 22436, 22447, 22457, 22467, 22478, 22488, 22498, 22507, 22517, 22527, 22536, 22546,
1333 22555, 22564, 22573, 22582, 22591, 22600, 22609, 22618, 22626, 22635, 22643, 22651, 22660, 22668, 22676, 22684,
1334 22692, 22700, 22708, 22716, 22723, 22731, 22738, 22746, 22753, 22761, 22768, 22775, 22783, 22790, 22797, 22804],
1335 [22811, 22825, 22838, 22852, 22865, 22878, 22891, 22903, 22916, 22928, 22940, 22952, 22964, 22975, 22987, 22998,
1336 23009, 23020, 23031, 23042, 23053, 23063, 23074, 23084, 23094, 23104, 23114, 23124, 23134, 23143, 23153, 23162,
1337 23171, 23181, 23190, 23199, 23208, 23217, 23225, 23234, 23243, 23251, 23260, 23268, 23276, 23284, 23293, 23301,
1338 23309, 23316, 23324, 23332, 23340, 23347, 23355, 23363, 23370, 23377, 23385, 23392, 23399, 23406, 23413, 23420],
1339 [23427, 23441, 23455, 23468, 23481, 23494, 23507, 23520, 23532, 23544, 23556, 23568, 23580, 23592, 23603, 23615,
1340 23626, 23637, 23648, 23659, 23669, 23680, 23690, 23700, 23711, 23721, 23731, 23740, 23750, 23760, 23769, 23779,
1341 23788, 23797, 23806, 23815, 23824, 23833, 23842, 23851, 23859, 23868, 23876, 23884, 23893, 23901, 23909, 23917,
1342 23925, 23933, 23941, 23949, 23956, 23964, 23972, 23979, 23986, 23994, 24001, 24008, 24016, 24023, 24030, 24037],
1343 [24044, 24058, 24071, 24085, 24098, 24111, 24124, 24136, 24149, 24161, 24173, 24185, 24197, 24208, 24220, 24231,
1344 24242, 24253, 24264, 24275, 24286, 24296, 24307, 24317, 24327, 24337, 24347, 24357, 24367, 24376, 24386, 24395,
1345 24405, 24414, 24423, 24432, 24441, 24450, 24458, 24467, 24476, 24484, 24493, 24501, 24509, 24517, 24526, 24534,
1346 24542, 24550, 24557, 24565, 24573, 24580, 24588, 24596, 24603, 24610, 24618, 24625, 24632, 24639, 24646, 24653],
1347 [24660, 24674, 24688, 24701, 24714, 24727, 24740, 24753, 24765, 24777, 24790, 24801, 24813, 24825, 24836, 24848,
1348 24859, 24870, 24881, 24892, 24902, 24913, 24923, 24933, 24944, 24954, 24964, 24973, 24983, 24993, 25002, 25012,
1349 25021, 25030, 25039, 25048, 25057, 25066, 25075, 25084, 25092, 25101, 25109, 25117, 25126, 25134, 25142, 25150,
1350 25158, 25166, 25174, 25182, 25189, 25197, 25205, 25212, 25219, 25227, 25234, 25241, 25249, 25256, 25263, 25270],
1351 [25277, 25291, 25304, 25318, 25331, 25344, 25357, 25369, 25382, 25394, 25406, 25418, 25430, 25441, 25453, 25464,
1352 25475, 25486, 25497, 25508, 25519, 25529, 25540, 25550, 25560, 25570, 25580, 25590, 25600, 25609, 25619, 25628,
1353 25638, 25647, 25656, 25665, 25674, 25683, 25691, 25700, 25709, 25717, 25726, 25734, 25742, 25750, 25759, 25767,
1354 25775, 25783, 25790, 25798, 25806, 25813, 25821, 25829, 25836, 25843, 25851, 25858, 25865, 25872, 25879, 25886],
1355 [25893, 25907, 25921, 25934, 25947, 25960, 25973, 25986, 25998, 26010, 26023, 26034, 26046, 26058, 26069, 26081,
1356 26092, 26103, 26114, 26125, 26135, 26146, 26156, 26166, 26177, 26187, 26197, 26206, 26216, 26226, 26235, 26245,
1357 26254, 26263, 26272, 26281, 26290, 26299, 26308, 26317, 26325, 26334, 26342, 26351, 26359, 26367, 26375, 26383,
1358 26391, 26399, 26407, 26415, 26422, 26430, 26438, 26445, 26453, 26460, 26467, 26474, 26482, 26489, 26496, 26503],
1359 [26510, 26524, 26537, 26551, 26564, 26577, 26590, 26602, 26615, 26627, 26639, 26651, 26663, 26674, 26686, 26697,
1360 26708, 26719, 26730, 26741, 26752, 26762, 26773, 26783, 26793, 26803, 26813, 26823, 26833, 26842, 26852, 26861,
1361 26871, 26880, 26889, 26898, 26907, 26916, 26924, 26933, 26942, 26950, 26959, 26967, 26975, 26983, 26992, 27000,
1362 27008, 27016, 27023, 27031, 27039, 27046, 27054, 27062, 27069, 27076, 27084, 27091, 27098, 27105, 27112, 27119],
1363 [27126, 27140, 27154, 27167, 27180, 27193, 27206, 27219, 27231, 27243, 27256, 27267, 27279, 27291, 27302, 27314,
1364 27325, 27336, 27347, 27358, 27368, 27379, 27389, 27399, 27410, 27420, 27430, 27439, 27449, 27459, 27468, 27478,
1365 27487, 27496, 27505, 27514, 27523, 27532, 27541, 27550, 27558, 27567, 27575, 27584, 27592, 27600, 27608, 27616,
1366 27624, 27632, 27640, 27648, 27655, 27663, 27671, 27678, 27686, 27693, 27700, 27707, 27715, 27722, 27729, 27736],
1367 [27743, 27757, 27770, 27784, 27797, 27810, 27823, 27835, 27848, 27860, 27872, 27884, 27896, 27907, 27919, 27930,
1368 27941, 27952, 27963, 27974, 27985, 27995, 28006, 28016, 28026, 28036, 28046, 28056, 28066, 28075, 28085, 28094,
1369 28104, 28113, 28122, 28131, 28140, 28149, 28157, 28166, 28175, 28183, 28192, 28200, 28208, 28217, 28225, 28233,
1370 28241, 28249, 28256, 28264, 28272, 28280, 28287, 28295, 28302, 28309, 28317, 28324, 28331, 28338, 28345, 28352],
1371 [28359, 28373, 28387, 28400, 28413, 28426, 28439, 28452, 28464, 28476, 28489, 28501, 28512, 28524, 28535, 28547,
1372 28558, 28569, 28580, 28591, 28601, 28612, 28622, 28633, 28643, 28653, 28663, 28672, 28682, 28692, 28701, 28711,
1373 28720, 28729, 28738, 28747, 28756, 28765, 28774, 28783, 28791, 28800, 28808, 28817, 28825, 28833, 28841, 28849,
1374 28857, 28865, 28873, 28881, 28888, 28896, 28904, 28911, 28919, 28926, 28933, 28941, 28948, 28955, 28962, 28969],
1375 [28976, 28990, 29003, 29017, 29030, 29043, 29056, 29068, 29081, 29093, 29105, 29117, 29129, 29140, 29152, 29163,
1376 29174, 29185, 29196, 29207, 29218, 29228, 29239, 29249, 29259, 29269, 29279, 29289, 29299, 29308, 29318, 29327,
1377 29337, 29346, 29355, 29364, 29373, 29382, 29390, 29399, 29408, 29416, 29425, 29433, 29441, 29450, 29458, 29466,
1378 29474, 29482, 29489, 29497, 29505, 29513, 29520, 29528, 29535, 29542, 29550, 29557, 29564, 29571, 29578, 29585],
1379 [29592, 29606, 29620, 29633, 29646, 29659, 29672, 29685, 29697, 29709, 29722, 29734, 29745, 29757, 29768, 29780,
1380 29791, 29802, 29813, 29824, 29834, 29845, 29855, 29866, 29876, 29886, 29896, 29906, 29915, 29925, 29934, 29944,
1381 29953, 29962, 29971, 29980, 29989, 29998, 30007, 30016, 30024, 30033, 30041, 30050, 30058, 30066, 30074, 30082,
1382 30090, 30098, 30106, 30114, 30121, 30129, 30137, 30144, 30152, 30159, 30166, 30174, 30181, 30188, 30195, 30202],
1383 [30209, 30223, 30236, 30250, 30263, 30276, 30289, 30301, 30314, 30326, 30338, 30350, 30362, 30373, 30385, 30396,
1384 30407, 30418, 30429, 30440, 30451, 30461, 30472, 30482, 30492, 30502, 30512, 30522, 30532, 30541, 30551, 30560,
1385 30570, 30579, 30588, 30597, 30606, 30615, 30624, 30632, 30641, 30649, 30658, 30666, 30674, 30683, 30691, 30699,
1386 30707, 30715, 30722, 30730, 30738, 30746, 30753, 30761, 30768, 30775, 30783, 30790, 30797, 30804, 30811, 30818],
1387 [30825, 30839, 30853, 30866, 30879, 30892, 30905, 30918, 30930, 30943, 30955, 30967, 30978, 30990, 31001, 31013,
1388 31024, 31035, 31046, 31057, 31067, 31078, 31088, 31099, 31109, 31119, 31129, 31139, 31148, 31158, 31167, 31177,
1389 31186, 31195, 31204, 31213, 31222, 31231, 31240, 31249, 31257, 31266, 31274, 31283, 31291, 31299, 31307, 31315,
1390 31323, 31331, 31339, 31347, 31354, 31362, 31370, 31377, 31385, 31392, 31399, 31407, 31414, 31421, 31428, 31435],
1391 [31442, 31456, 31469, 31483, 31496, 31509, 31522, 31534, 31547, 31559, 31571, 31583, 31595, 31606, 31618, 31629,
1392 31640, 31652, 31662, 31673, 31684, 31694, 31705, 31715, 31725, 31735, 31745, 31755, 31765, 31774, 31784, 31793,
1393 31803, 31812, 31821, 31830, 31839, 31848, 31857, 31865, 31874, 31882, 31891, 31899, 31907, 31916, 31924, 31932,
1394 31940, 31948, 31955, 31963, 31971, 31979, 31986, 31994, 32001, 32008, 32016, 32023, 32030, 32037, 32044, 32052],
1395 [32058, 32072, 32086, 32099, 32112, 32125, 32138, 32151, 32163, 32176, 32188, 32200, 32211, 32223, 32234, 32246,
1396 32257, 32268, 32279, 32290, 32300, 32311, 32321, 32332, 32342, 32352, 32362, 32372, 32381, 32391, 32400, 32410,
1397 32419, 32428, 32437, 32446, 32455, 32464, 32473, 32482, 32490, 32499, 32507, 32516, 32524, 32532, 32540, 32548,
1398 32556, 32564, 32572, 32580, 32587, 32595, 32603, 32610, 32618, 32625, 32632, 32640, 32647, 32654, 32661, 32668],
1399 [32675, 32689, 32702, 32716, 32729, 32742, 32755, 32767, 32780, 32792, 32804, 32816, 32828, 32839, 32851, 32862,
1400 32873, 32885, 32895, 32906, 32917, 32927, 32938, 32948, 32958, 32968, 32978, 32988, 32998, 33007, 33017, 33026,
1401 33036, 33045, 33054, 33063, 33072, 33081, 33090, 33098, 33107, 33115, 33124, 33132, 33140, 33149, 33157, 33165,
1402 33173, 33181, 33188, 33196, 33204, 33212, 33219, 33227, 33234, 33241, 33249, 33256, 33263, 33270, 33278, 33285],
1403 [33292, 33305, 33319, 33332, 33345, 33358, 33371, 33384, 33396, 33409, 33421, 33433, 33444, 33456, 33467, 33479,
1404 33490, 33501, 33512, 33523, 33533, 33544, 33554, 33565, 33575, 33585, 33595, 33605, 33614, 33624, 33633, 33643,
1405 33652, 33661, 33670, 33680, 33688, 33697, 33706, 33715, 33723, 33732, 33740, 33749, 33757, 33765, 33773, 33781,
1406 33789, 33797, 33805, 33813, 33820, 33828, 33836, 33843, 33851, 33858, 33865, 33873, 33880, 33887, 33894, 33901],
1407 [33908, 33922, 33935, 33949, 33962, 33975, 33988, 34000, 34013, 34025, 34037, 34049, 34061, 34072, 34084, 34095,
1408 34106, 34118, 34128, 34139, 34150, 34160, 34171, 34181, 34191, 34201, 34211, 34221, 34231, 34240, 34250, 34259,
1409 34269, 34278, 34287, 34296, 34305, 34314, 34323, 34331, 34340, 34348, 34357, 34365, 34373, 34382, 34390, 34398,
1410 34406, 34414, 34422, 34429, 34437, 34445, 34452, 34460, 34467, 34475, 34482, 34489, 34496, 34503, 34511, 34518],
1411 [34525, 34538, 34552, 34565, 34578, 34591, 34604, 34617, 34629, 34642, 34654, 34666, 34677, 34689, 34700, 34712,
1412 34723, 34734, 34745, 34756, 34766, 34777, 34787, 34798, 34808, 34818, 34828, 34838, 34847, 34857, 34866, 34876,
1413 34885, 34894, 34904, 34913, 34921, 34930, 34939, 34948, 34956, 34965, 34973, 34982, 34990, 34998, 35006, 35014,
1414 35022, 35030, 35038, 35046, 35053, 35061, 35069, 35076, 35084, 35091, 35098, 35106, 35113, 35120, 35127, 35134],
1415 [35141, 35155, 35168, 35182, 35195, 35208, 35221, 35233, 35246, 35258, 35270, 35282, 35294, 35306, 35317, 35328,
1416 35340, 35351, 35361, 35372, 35383, 35393, 35404, 35414, 35424, 35434, 35444, 35454, 35464, 35473, 35483, 35492,
1417 35502, 35511, 35520, 35529, 35538, 35547, 35556, 35564, 35573, 35581, 35590, 35598, 35606, 35615, 35623, 35631,
1418 35639, 35647, 35655, 35662, 35670, 35678, 35685, 35693, 35700, 35708, 35715, 35722, 35729, 35736, 35744, 35751],
1419 [35758, 35771, 35785, 35798, 35811, 35824, 35837, 35850, 35862, 35875, 35887, 35899, 35910, 35922, 35934, 35945,
1420 35956, 35967, 35978, 35989, 35999, 36010, 36020, 36031, 36041, 36051, 36061, 36071, 36080, 36090, 36099, 36109,
1421 36118, 36127, 36137, 36146, 36154, 36163, 36172, 36181, 36189, 36198, 36206, 36215, 36223, 36231, 36239, 36247,
1422 36255, 36263, 36271, 36279, 36287, 36294, 36302, 36309, 36317, 36324, 36331, 36339, 36346, 36353, 36360, 36367],
1423 [36374, 36388, 36401, 36415, 36428, 36441, 36454, 36466, 36479, 36491, 36503, 36515, 36527, 36539, 36550, 36561,
1424 36573, 36584, 36594, 36605, 36616, 36626, 36637, 36647, 36657, 36667, 36677, 36687, 36697, 36706, 36716, 36725,
1425 36735, 36744, 36753, 36762, 36771, 36780, 36789, 36797, 36806, 36814, 36823, 36831, 36839, 36848, 36856, 36864,
1426 36872, 36880, 36888, 36895, 36903, 36911, 36918, 36926, 36933, 36941, 36948, 36955, 36962, 36969, 36977, 36984],
1427 [36991, 37004, 37018, 37031, 37044, 37057, 37070, 37083, 37095, 37108, 37120, 37132, 37143, 37155, 37167, 37178,
1428 37189, 37200, 37211, 37222, 37232, 37243, 37253, 37264, 37274, 37284, 37294, 37304, 37313, 37323, 37332, 37342,
1429 37351, 37360, 37370, 37379, 37388, 37396, 37405, 37414, 37422, 37431, 37439, 37448, 37456, 37464, 37472, 37480,
1430 37488, 37496, 37504, 37512, 37520, 37527, 37535, 37542, 37550, 37557, 37564, 37572, 37579, 37586, 37593, 37600],
1431 [37607, 37621, 37634, 37648, 37661, 37674, 37687, 37699, 37712, 37724, 37736, 37748, 37760, 37772, 37783, 37794,
1432 37806, 37817, 37828, 37838, 37849, 37859, 37870, 37880, 37890, 37900, 37910, 37920, 37930, 37939, 37949, 37958,
1433 37968, 37977, 37986, 37995, 38004, 38013, 38022, 38030, 38039, 38047, 38056, 38064, 38072, 38081, 38089, 38097,
1434 38105, 38113, 38121, 38128, 38136, 38144, 38151, 38159, 38166, 38174, 38181, 38188, 38195, 38202, 38210, 38217],
1435 [38224, 38237, 38251, 38264, 38278, 38290, 38303, 38316, 38328, 38341, 38353, 38365, 38376, 38388, 38400, 38411,
1436 38422, 38433, 38444, 38455, 38465, 38476, 38486, 38497, 38507, 38517, 38527, 38537, 38546, 38556, 38565, 38575,
1437 38584, 38593, 38603, 38612, 38621, 38629, 38638, 38647, 38655, 38664, 38672, 38681, 38689, 38697, 38705, 38713,
1438 38721, 38729, 38737, 38745, 38753, 38760, 38768, 38775, 38783, 38790, 38797, 38805, 38812, 38819, 38826, 38833],
1439 [38840, 38854, 38867, 38881, 38894, 38907, 38920, 38932, 38945, 38957, 38969, 38981, 38993, 39005, 39016, 39027,
1440 39039, 39050, 39061, 39071, 39082, 39092, 39103, 39113, 39123, 39133, 39143, 39153, 39163, 39172, 39182, 39191,
1441 39201, 39210, 39219, 39228, 39237, 39246, 39255, 39263, 39272, 39280, 39289, 39297, 39305, 39314, 39322, 39330,
1442 39338, 39346, 39354, 39361, 39369, 39377, 39384, 39392, 39399, 39407, 39414, 39421, 39428, 39436, 39443, 39450],
1445 /// Approximate `log10(numerator / denominator) * 2048` using a look-up table.
1447 pub fn negative_log10_times_2048(numerator: u64, denominator: u64) -> u64 {
1448 // Multiply the -1 through to avoid needing to use signed numbers.
1449 (log10_times_2048(denominator) - log10_times_2048(numerator)) as u64
1453 fn log10_times_2048(x: u64) -> u16 {
1454 debug_assert_ne!(x, 0);
1455 let most_significant_bit = HIGHEST_BIT - x.leading_zeros();
1456 let lower_bits = (x >> most_significant_bit.saturating_sub(LOWER_BITS)) & LOWER_BITMASK;
1457 LOG10_TIMES_2048[most_significant_bit as usize][lower_bits as usize]
1465 fn prints_negative_log10_times_2048_lookup_table() {
1466 for msb in 0..BITS {
1467 for i in 0..LOWER_BITS_BOUND {
1468 let x = ((LOWER_BITS_BOUND + i) << (HIGHEST_BIT - LOWER_BITS)) >> (HIGHEST_BIT - msb);
1469 let log10_times_2048 = ((x as f64).log10() * 2048.0).round() as u16;
1470 assert_eq!(log10_times_2048, LOG10_TIMES_2048[msb as usize][i as usize]);
1472 if i % LOWER_BITS_BOUND == 0 {
1473 print!("\t\t[{}, ", log10_times_2048);
1474 } else if i % LOWER_BITS_BOUND == LOWER_BITS_BOUND - 1 {
1475 println!("{}],", log10_times_2048);
1476 } else if i % (LOWER_BITS_BOUND/4) == LOWER_BITS_BOUND/4 - 1 {
1477 print!("{},\n\t\t\t", log10_times_2048);
1479 print!("{}, ", log10_times_2048);
1487 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Writeable for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1489 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
1490 write_tlv_fields!(w, {
1491 (0, self.channel_liquidities, required),
1497 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time>
1498 ReadableArgs<(ProbabilisticScoringParameters, G, L)> for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1501 r: &mut R, args: (ProbabilisticScoringParameters, G, L)
1502 ) -> Result<Self, DecodeError> {
1503 let (params, network_graph, logger) = args;
1504 let mut channel_liquidities = HashMap::new();
1505 read_tlv_fields!(r, {
1506 (0, channel_liquidities, required),
1512 channel_liquidities,
1517 impl<T: Time> Writeable for ChannelLiquidity<T> {
1519 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
1520 let duration_since_epoch = T::duration_since_epoch() - self.last_updated.elapsed();
1521 write_tlv_fields!(w, {
1522 (0, self.min_liquidity_offset_msat, required),
1523 (1, Some(self.min_liquidity_offset_history), option),
1524 (2, self.max_liquidity_offset_msat, required),
1525 (3, Some(self.max_liquidity_offset_history), option),
1526 (4, duration_since_epoch, required),
1532 impl<T: Time> Readable for ChannelLiquidity<T> {
1534 fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
1535 let mut min_liquidity_offset_msat = 0;
1536 let mut max_liquidity_offset_msat = 0;
1537 let mut min_liquidity_offset_history = Some(HistoricalBucketRangeTracker::new());
1538 let mut max_liquidity_offset_history = Some(HistoricalBucketRangeTracker::new());
1539 let mut duration_since_epoch = Duration::from_secs(0);
1540 read_tlv_fields!(r, {
1541 (0, min_liquidity_offset_msat, required),
1542 (1, min_liquidity_offset_history, option),
1543 (2, max_liquidity_offset_msat, required),
1544 (3, max_liquidity_offset_history, option),
1545 (4, duration_since_epoch, required),
1547 // On rust prior to 1.60 `Instant::duration_since` will panic if time goes backwards.
1548 // We write `last_updated` as wallclock time even though its ultimately an `Instant` (which
1549 // is a time from a monotonic clock usually represented as an offset against boot time).
1550 // Thus, we have to construct an `Instant` by subtracting the difference in wallclock time
1551 // from the one that was written. However, because `Instant` can panic if we construct one
1552 // in the future, we must handle wallclock time jumping backwards, which we do by simply
1553 // using `Instant::now()` in that case.
1554 let wall_clock_now = T::duration_since_epoch();
1556 let last_updated = if wall_clock_now > duration_since_epoch {
1557 now - (wall_clock_now - duration_since_epoch)
1560 min_liquidity_offset_msat,
1561 max_liquidity_offset_msat,
1562 min_liquidity_offset_history: min_liquidity_offset_history.unwrap(),
1563 max_liquidity_offset_history: max_liquidity_offset_history.unwrap(),
1571 use super::{ChannelLiquidity, HistoricalBucketRangeTracker, ProbabilisticScoringParameters, ProbabilisticScorerUsingTime};
1572 use util::time::Time;
1573 use util::time::tests::SinceEpoch;
1575 use ln::channelmanager;
1576 use ln::msgs::{ChannelAnnouncement, ChannelUpdate, UnsignedChannelAnnouncement, UnsignedChannelUpdate};
1577 use routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId};
1578 use routing::router::RouteHop;
1579 use routing::scoring::{ChannelUsage, Score};
1580 use util::ser::{ReadableArgs, Writeable};
1581 use util::test_utils::TestLogger;
1583 use bitcoin::blockdata::constants::genesis_block;
1584 use bitcoin::hashes::Hash;
1585 use bitcoin::hashes::sha256d::Hash as Sha256dHash;
1586 use bitcoin::network::constants::Network;
1587 use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey};
1588 use core::time::Duration;
1591 fn source_privkey() -> SecretKey {
1592 SecretKey::from_slice(&[42; 32]).unwrap()
1595 fn target_privkey() -> SecretKey {
1596 SecretKey::from_slice(&[43; 32]).unwrap()
1599 fn source_pubkey() -> PublicKey {
1600 let secp_ctx = Secp256k1::new();
1601 PublicKey::from_secret_key(&secp_ctx, &source_privkey())
1604 fn target_pubkey() -> PublicKey {
1605 let secp_ctx = Secp256k1::new();
1606 PublicKey::from_secret_key(&secp_ctx, &target_privkey())
1609 fn source_node_id() -> NodeId {
1610 NodeId::from_pubkey(&source_pubkey())
1613 fn target_node_id() -> NodeId {
1614 NodeId::from_pubkey(&target_pubkey())
1617 // `ProbabilisticScorer` tests
1619 /// A probabilistic scorer for testing with time that can be manually advanced.
1620 type ProbabilisticScorer<'a> = ProbabilisticScorerUsingTime::<&'a NetworkGraph<&'a TestLogger>, &'a TestLogger, SinceEpoch>;
1622 fn sender_privkey() -> SecretKey {
1623 SecretKey::from_slice(&[41; 32]).unwrap()
1626 fn recipient_privkey() -> SecretKey {
1627 SecretKey::from_slice(&[45; 32]).unwrap()
1630 fn sender_pubkey() -> PublicKey {
1631 let secp_ctx = Secp256k1::new();
1632 PublicKey::from_secret_key(&secp_ctx, &sender_privkey())
1635 fn recipient_pubkey() -> PublicKey {
1636 let secp_ctx = Secp256k1::new();
1637 PublicKey::from_secret_key(&secp_ctx, &recipient_privkey())
1640 fn sender_node_id() -> NodeId {
1641 NodeId::from_pubkey(&sender_pubkey())
1644 fn recipient_node_id() -> NodeId {
1645 NodeId::from_pubkey(&recipient_pubkey())
1648 fn network_graph(logger: &TestLogger) -> NetworkGraph<&TestLogger> {
1649 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1650 let mut network_graph = NetworkGraph::new(genesis_hash, logger);
1651 add_channel(&mut network_graph, 42, source_privkey(), target_privkey());
1652 add_channel(&mut network_graph, 43, target_privkey(), recipient_privkey());
1658 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_1_key: SecretKey,
1659 node_2_key: SecretKey
1661 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1662 let node_1_secret = &SecretKey::from_slice(&[39; 32]).unwrap();
1663 let node_2_secret = &SecretKey::from_slice(&[40; 32]).unwrap();
1664 let secp_ctx = Secp256k1::new();
1665 let unsigned_announcement = UnsignedChannelAnnouncement {
1666 features: channelmanager::provided_channel_features(),
1667 chain_hash: genesis_hash,
1669 node_id_1: PublicKey::from_secret_key(&secp_ctx, &node_1_key),
1670 node_id_2: PublicKey::from_secret_key(&secp_ctx, &node_2_key),
1671 bitcoin_key_1: PublicKey::from_secret_key(&secp_ctx, &node_1_secret),
1672 bitcoin_key_2: PublicKey::from_secret_key(&secp_ctx, &node_2_secret),
1673 excess_data: Vec::new(),
1675 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
1676 let signed_announcement = ChannelAnnouncement {
1677 node_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_key),
1678 node_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_key),
1679 bitcoin_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_secret),
1680 bitcoin_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_secret),
1681 contents: unsigned_announcement,
1683 let chain_source: Option<&::util::test_utils::TestChainSource> = None;
1684 network_graph.update_channel_from_announcement(
1685 &signed_announcement, &chain_source).unwrap();
1686 update_channel(network_graph, short_channel_id, node_1_key, 0);
1687 update_channel(network_graph, short_channel_id, node_2_key, 1);
1691 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_key: SecretKey,
1694 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1695 let secp_ctx = Secp256k1::new();
1696 let unsigned_update = UnsignedChannelUpdate {
1697 chain_hash: genesis_hash,
1701 cltv_expiry_delta: 18,
1702 htlc_minimum_msat: 0,
1703 htlc_maximum_msat: 1_000,
1705 fee_proportional_millionths: 0,
1706 excess_data: Vec::new(),
1708 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_update.encode()[..])[..]);
1709 let signed_update = ChannelUpdate {
1710 signature: secp_ctx.sign_ecdsa(&msghash, &node_key),
1711 contents: unsigned_update,
1713 network_graph.update_channel(&signed_update).unwrap();
1716 fn payment_path_for_amount(amount_msat: u64) -> Vec<RouteHop> {
1719 pubkey: source_pubkey(),
1720 node_features: channelmanager::provided_node_features(),
1721 short_channel_id: 41,
1722 channel_features: channelmanager::provided_channel_features(),
1724 cltv_expiry_delta: 18,
1727 pubkey: target_pubkey(),
1728 node_features: channelmanager::provided_node_features(),
1729 short_channel_id: 42,
1730 channel_features: channelmanager::provided_channel_features(),
1732 cltv_expiry_delta: 18,
1735 pubkey: recipient_pubkey(),
1736 node_features: channelmanager::provided_node_features(),
1737 short_channel_id: 43,
1738 channel_features: channelmanager::provided_channel_features(),
1739 fee_msat: amount_msat,
1740 cltv_expiry_delta: 18,
1746 fn liquidity_bounds_directed_from_lowest_node_id() {
1747 let logger = TestLogger::new();
1748 let last_updated = SinceEpoch::now();
1749 let network_graph = network_graph(&logger);
1750 let params = ProbabilisticScoringParameters::default();
1751 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1754 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated,
1755 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1756 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1760 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated,
1761 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1762 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1764 let source = source_node_id();
1765 let target = target_node_id();
1766 let recipient = recipient_node_id();
1767 assert!(source > target);
1768 assert!(target < recipient);
1770 // Update minimum liquidity.
1772 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1773 .as_directed(&source, &target, 1_000, &scorer.params);
1774 assert_eq!(liquidity.min_liquidity_msat(), 100);
1775 assert_eq!(liquidity.max_liquidity_msat(), 300);
1777 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1778 .as_directed(&target, &source, 1_000, &scorer.params);
1779 assert_eq!(liquidity.min_liquidity_msat(), 700);
1780 assert_eq!(liquidity.max_liquidity_msat(), 900);
1782 scorer.channel_liquidities.get_mut(&42).unwrap()
1783 .as_directed_mut(&source, &target, 1_000, &scorer.params)
1784 .set_min_liquidity_msat(200);
1786 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1787 .as_directed(&source, &target, 1_000, &scorer.params);
1788 assert_eq!(liquidity.min_liquidity_msat(), 200);
1789 assert_eq!(liquidity.max_liquidity_msat(), 300);
1791 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1792 .as_directed(&target, &source, 1_000, &scorer.params);
1793 assert_eq!(liquidity.min_liquidity_msat(), 700);
1794 assert_eq!(liquidity.max_liquidity_msat(), 800);
1796 // Update maximum liquidity.
1798 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1799 .as_directed(&target, &recipient, 1_000, &scorer.params);
1800 assert_eq!(liquidity.min_liquidity_msat(), 700);
1801 assert_eq!(liquidity.max_liquidity_msat(), 900);
1803 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1804 .as_directed(&recipient, &target, 1_000, &scorer.params);
1805 assert_eq!(liquidity.min_liquidity_msat(), 100);
1806 assert_eq!(liquidity.max_liquidity_msat(), 300);
1808 scorer.channel_liquidities.get_mut(&43).unwrap()
1809 .as_directed_mut(&target, &recipient, 1_000, &scorer.params)
1810 .set_max_liquidity_msat(200);
1812 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1813 .as_directed(&target, &recipient, 1_000, &scorer.params);
1814 assert_eq!(liquidity.min_liquidity_msat(), 0);
1815 assert_eq!(liquidity.max_liquidity_msat(), 200);
1817 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1818 .as_directed(&recipient, &target, 1_000, &scorer.params);
1819 assert_eq!(liquidity.min_liquidity_msat(), 800);
1820 assert_eq!(liquidity.max_liquidity_msat(), 1000);
1824 fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() {
1825 let logger = TestLogger::new();
1826 let last_updated = SinceEpoch::now();
1827 let network_graph = network_graph(&logger);
1828 let params = ProbabilisticScoringParameters::default();
1829 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1832 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated,
1833 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1834 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1836 let source = source_node_id();
1837 let target = target_node_id();
1838 assert!(source > target);
1840 // Check initial bounds.
1841 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1842 .as_directed(&source, &target, 1_000, &scorer.params);
1843 assert_eq!(liquidity.min_liquidity_msat(), 400);
1844 assert_eq!(liquidity.max_liquidity_msat(), 800);
1846 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1847 .as_directed(&target, &source, 1_000, &scorer.params);
1848 assert_eq!(liquidity.min_liquidity_msat(), 200);
1849 assert_eq!(liquidity.max_liquidity_msat(), 600);
1851 // Reset from source to target.
1852 scorer.channel_liquidities.get_mut(&42).unwrap()
1853 .as_directed_mut(&source, &target, 1_000, &scorer.params)
1854 .set_min_liquidity_msat(900);
1856 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1857 .as_directed(&source, &target, 1_000, &scorer.params);
1858 assert_eq!(liquidity.min_liquidity_msat(), 900);
1859 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1861 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1862 .as_directed(&target, &source, 1_000, &scorer.params);
1863 assert_eq!(liquidity.min_liquidity_msat(), 0);
1864 assert_eq!(liquidity.max_liquidity_msat(), 100);
1866 // Reset from target to source.
1867 scorer.channel_liquidities.get_mut(&42).unwrap()
1868 .as_directed_mut(&target, &source, 1_000, &scorer.params)
1869 .set_min_liquidity_msat(400);
1871 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1872 .as_directed(&source, &target, 1_000, &scorer.params);
1873 assert_eq!(liquidity.min_liquidity_msat(), 0);
1874 assert_eq!(liquidity.max_liquidity_msat(), 600);
1876 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1877 .as_directed(&target, &source, 1_000, &scorer.params);
1878 assert_eq!(liquidity.min_liquidity_msat(), 400);
1879 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1883 fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() {
1884 let logger = TestLogger::new();
1885 let last_updated = SinceEpoch::now();
1886 let network_graph = network_graph(&logger);
1887 let params = ProbabilisticScoringParameters::default();
1888 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1891 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated,
1892 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1893 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1895 let source = source_node_id();
1896 let target = target_node_id();
1897 assert!(source > target);
1899 // Check initial bounds.
1900 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1901 .as_directed(&source, &target, 1_000, &scorer.params);
1902 assert_eq!(liquidity.min_liquidity_msat(), 400);
1903 assert_eq!(liquidity.max_liquidity_msat(), 800);
1905 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1906 .as_directed(&target, &source, 1_000, &scorer.params);
1907 assert_eq!(liquidity.min_liquidity_msat(), 200);
1908 assert_eq!(liquidity.max_liquidity_msat(), 600);
1910 // Reset from source to target.
1911 scorer.channel_liquidities.get_mut(&42).unwrap()
1912 .as_directed_mut(&source, &target, 1_000, &scorer.params)
1913 .set_max_liquidity_msat(300);
1915 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1916 .as_directed(&source, &target, 1_000, &scorer.params);
1917 assert_eq!(liquidity.min_liquidity_msat(), 0);
1918 assert_eq!(liquidity.max_liquidity_msat(), 300);
1920 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1921 .as_directed(&target, &source, 1_000, &scorer.params);
1922 assert_eq!(liquidity.min_liquidity_msat(), 700);
1923 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1925 // Reset from target to source.
1926 scorer.channel_liquidities.get_mut(&42).unwrap()
1927 .as_directed_mut(&target, &source, 1_000, &scorer.params)
1928 .set_max_liquidity_msat(600);
1930 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1931 .as_directed(&source, &target, 1_000, &scorer.params);
1932 assert_eq!(liquidity.min_liquidity_msat(), 400);
1933 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1935 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1936 .as_directed(&target, &source, 1_000, &scorer.params);
1937 assert_eq!(liquidity.min_liquidity_msat(), 0);
1938 assert_eq!(liquidity.max_liquidity_msat(), 600);
1942 fn increased_penalty_nearing_liquidity_upper_bound() {
1943 let logger = TestLogger::new();
1944 let network_graph = network_graph(&logger);
1945 let params = ProbabilisticScoringParameters {
1946 liquidity_penalty_multiplier_msat: 1_000,
1947 ..ProbabilisticScoringParameters::zero_penalty()
1949 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1950 let source = source_node_id();
1951 let target = target_node_id();
1953 let usage = ChannelUsage {
1955 inflight_htlc_msat: 0,
1956 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(1_000) },
1958 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1959 let usage = ChannelUsage { amount_msat: 10_240, ..usage };
1960 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1961 let usage = ChannelUsage { amount_msat: 102_400, ..usage };
1962 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 47);
1963 let usage = ChannelUsage { amount_msat: 1_023_999, ..usage };
1964 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
1966 let usage = ChannelUsage {
1968 inflight_htlc_msat: 0,
1969 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_000) },
1971 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 58);
1972 let usage = ChannelUsage { amount_msat: 256, ..usage };
1973 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
1974 let usage = ChannelUsage { amount_msat: 374, ..usage };
1975 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 198);
1976 let usage = ChannelUsage { amount_msat: 512, ..usage };
1977 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1978 let usage = ChannelUsage { amount_msat: 640, ..usage };
1979 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 425);
1980 let usage = ChannelUsage { amount_msat: 768, ..usage };
1981 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 602);
1982 let usage = ChannelUsage { amount_msat: 896, ..usage };
1983 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 902);
1987 fn constant_penalty_outside_liquidity_bounds() {
1988 let logger = TestLogger::new();
1989 let last_updated = SinceEpoch::now();
1990 let network_graph = network_graph(&logger);
1991 let params = ProbabilisticScoringParameters {
1992 liquidity_penalty_multiplier_msat: 1_000,
1993 considered_impossible_penalty_msat: u64::max_value(),
1994 ..ProbabilisticScoringParameters::zero_penalty()
1996 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1999 min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40, last_updated,
2000 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2001 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2003 let source = source_node_id();
2004 let target = target_node_id();
2006 let usage = ChannelUsage {
2008 inflight_htlc_msat: 0,
2009 effective_capacity: EffectiveCapacity::Total { capacity_msat: 100, htlc_maximum_msat: Some(1_000) },
2011 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2012 let usage = ChannelUsage { amount_msat: 50, ..usage };
2013 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2014 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2015 let usage = ChannelUsage { amount_msat: 61, ..usage };
2016 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2020 fn does_not_further_penalize_own_channel() {
2021 let logger = TestLogger::new();
2022 let network_graph = network_graph(&logger);
2023 let params = ProbabilisticScoringParameters {
2024 liquidity_penalty_multiplier_msat: 1_000,
2025 ..ProbabilisticScoringParameters::zero_penalty()
2027 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2028 let sender = sender_node_id();
2029 let source = source_node_id();
2030 let usage = ChannelUsage {
2032 inflight_htlc_msat: 0,
2033 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
2035 let failed_path = payment_path_for_amount(500);
2036 let successful_path = payment_path_for_amount(200);
2038 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 301);
2040 scorer.payment_path_failed(&failed_path.iter().collect::<Vec<_>>(), 41);
2041 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 301);
2043 scorer.payment_path_successful(&successful_path.iter().collect::<Vec<_>>());
2044 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 301);
2048 fn sets_liquidity_lower_bound_on_downstream_failure() {
2049 let logger = TestLogger::new();
2050 let network_graph = network_graph(&logger);
2051 let params = ProbabilisticScoringParameters {
2052 liquidity_penalty_multiplier_msat: 1_000,
2053 ..ProbabilisticScoringParameters::zero_penalty()
2055 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2056 let source = source_node_id();
2057 let target = target_node_id();
2058 let path = payment_path_for_amount(500);
2060 let usage = ChannelUsage {
2062 inflight_htlc_msat: 0,
2063 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
2065 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 128);
2066 let usage = ChannelUsage { amount_msat: 500, ..usage };
2067 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 301);
2068 let usage = ChannelUsage { amount_msat: 750, ..usage };
2069 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 602);
2071 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 43);
2073 let usage = ChannelUsage { amount_msat: 250, ..usage };
2074 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2075 let usage = ChannelUsage { amount_msat: 500, ..usage };
2076 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2077 let usage = ChannelUsage { amount_msat: 750, ..usage };
2078 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2082 fn sets_liquidity_upper_bound_on_failure() {
2083 let logger = TestLogger::new();
2084 let network_graph = network_graph(&logger);
2085 let params = ProbabilisticScoringParameters {
2086 liquidity_penalty_multiplier_msat: 1_000,
2087 considered_impossible_penalty_msat: u64::max_value(),
2088 ..ProbabilisticScoringParameters::zero_penalty()
2090 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2091 let source = source_node_id();
2092 let target = target_node_id();
2093 let path = payment_path_for_amount(500);
2095 let usage = ChannelUsage {
2097 inflight_htlc_msat: 0,
2098 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
2100 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 128);
2101 let usage = ChannelUsage { amount_msat: 500, ..usage };
2102 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 301);
2103 let usage = ChannelUsage { amount_msat: 750, ..usage };
2104 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 602);
2106 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 42);
2108 let usage = ChannelUsage { amount_msat: 250, ..usage };
2109 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2110 let usage = ChannelUsage { amount_msat: 500, ..usage };
2111 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2112 let usage = ChannelUsage { amount_msat: 750, ..usage };
2113 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2117 fn reduces_liquidity_upper_bound_along_path_on_success() {
2118 let logger = TestLogger::new();
2119 let network_graph = network_graph(&logger);
2120 let params = ProbabilisticScoringParameters {
2121 liquidity_penalty_multiplier_msat: 1_000,
2122 ..ProbabilisticScoringParameters::zero_penalty()
2124 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2125 let sender = sender_node_id();
2126 let source = source_node_id();
2127 let target = target_node_id();
2128 let recipient = recipient_node_id();
2129 let usage = ChannelUsage {
2131 inflight_htlc_msat: 0,
2132 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
2134 let path = payment_path_for_amount(500);
2136 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 128);
2137 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 128);
2138 assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage), 128);
2140 scorer.payment_path_successful(&path.iter().collect::<Vec<_>>());
2142 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 128);
2143 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2144 assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage), 300);
2148 fn decays_liquidity_bounds_over_time() {
2149 let logger = TestLogger::new();
2150 let network_graph = network_graph(&logger);
2151 let params = ProbabilisticScoringParameters {
2152 liquidity_penalty_multiplier_msat: 1_000,
2153 liquidity_offset_half_life: Duration::from_secs(10),
2154 considered_impossible_penalty_msat: u64::max_value(),
2155 ..ProbabilisticScoringParameters::zero_penalty()
2157 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2158 let source = source_node_id();
2159 let target = target_node_id();
2161 let usage = ChannelUsage {
2163 inflight_htlc_msat: 0,
2164 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_024) },
2166 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2167 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
2168 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
2170 scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::<Vec<_>>(), 42);
2171 scorer.payment_path_failed(&payment_path_for_amount(128).iter().collect::<Vec<_>>(), 43);
2173 let usage = ChannelUsage { amount_msat: 128, ..usage };
2174 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2175 let usage = ChannelUsage { amount_msat: 256, ..usage };
2176 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 93);
2177 let usage = ChannelUsage { amount_msat: 768, ..usage };
2178 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1_479);
2179 let usage = ChannelUsage { amount_msat: 896, ..usage };
2180 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2182 SinceEpoch::advance(Duration::from_secs(9));
2183 let usage = ChannelUsage { amount_msat: 128, ..usage };
2184 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2185 let usage = ChannelUsage { amount_msat: 256, ..usage };
2186 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 93);
2187 let usage = ChannelUsage { amount_msat: 768, ..usage };
2188 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1_479);
2189 let usage = ChannelUsage { amount_msat: 896, ..usage };
2190 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2192 SinceEpoch::advance(Duration::from_secs(1));
2193 let usage = ChannelUsage { amount_msat: 64, ..usage };
2194 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2195 let usage = ChannelUsage { amount_msat: 128, ..usage };
2196 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 34);
2197 let usage = ChannelUsage { amount_msat: 896, ..usage };
2198 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1_970);
2199 let usage = ChannelUsage { amount_msat: 960, ..usage };
2200 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2202 // Fully decay liquidity lower bound.
2203 SinceEpoch::advance(Duration::from_secs(10 * 7));
2204 let usage = ChannelUsage { amount_msat: 0, ..usage };
2205 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2206 let usage = ChannelUsage { amount_msat: 1, ..usage };
2207 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2208 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
2209 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
2210 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2211 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2213 // Fully decay liquidity upper bound.
2214 SinceEpoch::advance(Duration::from_secs(10));
2215 let usage = ChannelUsage { amount_msat: 0, ..usage };
2216 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2217 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2218 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2220 SinceEpoch::advance(Duration::from_secs(10));
2221 let usage = ChannelUsage { amount_msat: 0, ..usage };
2222 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2223 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2224 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2228 fn decays_liquidity_bounds_without_shift_overflow() {
2229 let logger = TestLogger::new();
2230 let network_graph = network_graph(&logger);
2231 let params = ProbabilisticScoringParameters {
2232 liquidity_penalty_multiplier_msat: 1_000,
2233 liquidity_offset_half_life: Duration::from_secs(10),
2234 ..ProbabilisticScoringParameters::zero_penalty()
2236 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2237 let source = source_node_id();
2238 let target = target_node_id();
2239 let usage = ChannelUsage {
2241 inflight_htlc_msat: 0,
2242 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_000) },
2244 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
2246 scorer.payment_path_failed(&payment_path_for_amount(512).iter().collect::<Vec<_>>(), 42);
2247 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 281);
2249 // An unchecked right shift 64 bits or more in DirectedChannelLiquidity::decayed_offset_msat
2250 // would cause an overflow.
2251 SinceEpoch::advance(Duration::from_secs(10 * 64));
2252 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
2254 SinceEpoch::advance(Duration::from_secs(10));
2255 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
2259 fn restricts_liquidity_bounds_after_decay() {
2260 let logger = TestLogger::new();
2261 let network_graph = network_graph(&logger);
2262 let params = ProbabilisticScoringParameters {
2263 liquidity_penalty_multiplier_msat: 1_000,
2264 liquidity_offset_half_life: Duration::from_secs(10),
2265 ..ProbabilisticScoringParameters::zero_penalty()
2267 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2268 let source = source_node_id();
2269 let target = target_node_id();
2270 let usage = ChannelUsage {
2272 inflight_htlc_msat: 0,
2273 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_000) },
2276 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2278 // More knowledge gives higher confidence (256, 768), meaning a lower penalty.
2279 scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::<Vec<_>>(), 42);
2280 scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::<Vec<_>>(), 43);
2281 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 281);
2283 // Decaying knowledge gives less confidence (128, 896), meaning a higher penalty.
2284 SinceEpoch::advance(Duration::from_secs(10));
2285 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 291);
2287 // Reducing the upper bound gives more confidence (128, 832) that the payment amount (512)
2288 // is closer to the upper bound, meaning a higher penalty.
2289 scorer.payment_path_successful(&payment_path_for_amount(64).iter().collect::<Vec<_>>());
2290 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 331);
2292 // Increasing the lower bound gives more confidence (256, 832) that the payment amount (512)
2293 // is closer to the lower bound, meaning a lower penalty.
2294 scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::<Vec<_>>(), 43);
2295 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 245);
2297 // Further decaying affects the lower bound more than the upper bound (128, 928).
2298 SinceEpoch::advance(Duration::from_secs(10));
2299 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 280);
2303 fn restores_persisted_liquidity_bounds() {
2304 let logger = TestLogger::new();
2305 let network_graph = network_graph(&logger);
2306 let params = ProbabilisticScoringParameters {
2307 liquidity_penalty_multiplier_msat: 1_000,
2308 liquidity_offset_half_life: Duration::from_secs(10),
2309 considered_impossible_penalty_msat: u64::max_value(),
2310 ..ProbabilisticScoringParameters::zero_penalty()
2312 let mut scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger);
2313 let source = source_node_id();
2314 let target = target_node_id();
2315 let usage = ChannelUsage {
2317 inflight_htlc_msat: 0,
2318 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
2321 scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
2322 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2324 SinceEpoch::advance(Duration::from_secs(10));
2325 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 473);
2327 scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::<Vec<_>>(), 43);
2328 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2330 let mut serialized_scorer = Vec::new();
2331 scorer.write(&mut serialized_scorer).unwrap();
2333 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
2334 let deserialized_scorer =
2335 <ProbabilisticScorer>::read(&mut serialized_scorer, (params, &network_graph, &logger)).unwrap();
2336 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2340 fn decays_persisted_liquidity_bounds() {
2341 let logger = TestLogger::new();
2342 let network_graph = network_graph(&logger);
2343 let params = ProbabilisticScoringParameters {
2344 liquidity_penalty_multiplier_msat: 1_000,
2345 liquidity_offset_half_life: Duration::from_secs(10),
2346 considered_impossible_penalty_msat: u64::max_value(),
2347 ..ProbabilisticScoringParameters::zero_penalty()
2349 let mut scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger);
2350 let source = source_node_id();
2351 let target = target_node_id();
2352 let usage = ChannelUsage {
2354 inflight_htlc_msat: 0,
2355 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
2358 scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
2359 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2361 let mut serialized_scorer = Vec::new();
2362 scorer.write(&mut serialized_scorer).unwrap();
2364 SinceEpoch::advance(Duration::from_secs(10));
2366 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
2367 let deserialized_scorer =
2368 <ProbabilisticScorer>::read(&mut serialized_scorer, (params, &network_graph, &logger)).unwrap();
2369 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage), 473);
2371 scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::<Vec<_>>(), 43);
2372 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2374 SinceEpoch::advance(Duration::from_secs(10));
2375 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage), 365);
2379 fn scores_realistic_payments() {
2380 // Shows the scores of "realistic" sends of 100k sats over channels of 1-10m sats (with a
2381 // 50k sat reserve).
2382 let logger = TestLogger::new();
2383 let network_graph = network_graph(&logger);
2384 let params = ProbabilisticScoringParameters::default();
2385 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2386 let source = source_node_id();
2387 let target = target_node_id();
2389 let usage = ChannelUsage {
2390 amount_msat: 100_000_000,
2391 inflight_htlc_msat: 0,
2392 effective_capacity: EffectiveCapacity::Total { capacity_msat: 950_000_000, htlc_maximum_msat: Some(1_000) },
2394 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 4375);
2395 let usage = ChannelUsage {
2396 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2398 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2739);
2399 let usage = ChannelUsage {
2400 effective_capacity: EffectiveCapacity::Total { capacity_msat: 2_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2402 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2236);
2403 let usage = ChannelUsage {
2404 effective_capacity: EffectiveCapacity::Total { capacity_msat: 3_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2406 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1983);
2407 let usage = ChannelUsage {
2408 effective_capacity: EffectiveCapacity::Total { capacity_msat: 4_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2410 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1637);
2411 let usage = ChannelUsage {
2412 effective_capacity: EffectiveCapacity::Total { capacity_msat: 5_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2414 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1606);
2415 let usage = ChannelUsage {
2416 effective_capacity: EffectiveCapacity::Total { capacity_msat: 6_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2418 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1331);
2419 let usage = ChannelUsage {
2420 effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_450_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2422 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1387);
2423 let usage = ChannelUsage {
2424 effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2426 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1379);
2427 let usage = ChannelUsage {
2428 effective_capacity: EffectiveCapacity::Total { capacity_msat: 8_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2430 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1363);
2431 let usage = ChannelUsage {
2432 effective_capacity: EffectiveCapacity::Total { capacity_msat: 9_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2434 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1355);
2438 fn adds_base_penalty_to_liquidity_penalty() {
2439 let logger = TestLogger::new();
2440 let network_graph = network_graph(&logger);
2441 let source = source_node_id();
2442 let target = target_node_id();
2443 let usage = ChannelUsage {
2445 inflight_htlc_msat: 0,
2446 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_000) },
2449 let params = ProbabilisticScoringParameters {
2450 liquidity_penalty_multiplier_msat: 1_000,
2451 ..ProbabilisticScoringParameters::zero_penalty()
2453 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2454 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 58);
2456 let params = ProbabilisticScoringParameters {
2457 base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000,
2458 anti_probing_penalty_msat: 0, ..ProbabilisticScoringParameters::zero_penalty()
2460 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2461 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 558);
2463 let params = ProbabilisticScoringParameters {
2464 base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000,
2465 base_penalty_amount_multiplier_msat: (1 << 30),
2466 anti_probing_penalty_msat: 0, ..ProbabilisticScoringParameters::zero_penalty()
2469 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2470 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 558 + 128);
2474 fn adds_amount_penalty_to_liquidity_penalty() {
2475 let logger = TestLogger::new();
2476 let network_graph = network_graph(&logger);
2477 let source = source_node_id();
2478 let target = target_node_id();
2479 let usage = ChannelUsage {
2480 amount_msat: 512_000,
2481 inflight_htlc_msat: 0,
2482 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(1_000) },
2485 let params = ProbabilisticScoringParameters {
2486 liquidity_penalty_multiplier_msat: 1_000,
2487 liquidity_penalty_amount_multiplier_msat: 0,
2488 ..ProbabilisticScoringParameters::zero_penalty()
2490 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2491 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2493 let params = ProbabilisticScoringParameters {
2494 liquidity_penalty_multiplier_msat: 1_000,
2495 liquidity_penalty_amount_multiplier_msat: 256,
2496 ..ProbabilisticScoringParameters::zero_penalty()
2498 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2499 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 337);
2503 fn calculates_log10_without_overflowing_u64_max_value() {
2504 let logger = TestLogger::new();
2505 let network_graph = network_graph(&logger);
2506 let source = source_node_id();
2507 let target = target_node_id();
2508 let usage = ChannelUsage {
2509 amount_msat: u64::max_value(),
2510 inflight_htlc_msat: 0,
2511 effective_capacity: EffectiveCapacity::Infinite,
2514 let params = ProbabilisticScoringParameters {
2515 liquidity_penalty_multiplier_msat: 40_000,
2516 ..ProbabilisticScoringParameters::zero_penalty()
2518 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2519 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 80_000);
2523 fn accounts_for_inflight_htlc_usage() {
2524 let logger = TestLogger::new();
2525 let network_graph = network_graph(&logger);
2526 let params = ProbabilisticScoringParameters {
2527 considered_impossible_penalty_msat: u64::max_value(),
2528 ..ProbabilisticScoringParameters::zero_penalty()
2530 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2531 let source = source_node_id();
2532 let target = target_node_id();
2534 let usage = ChannelUsage {
2536 inflight_htlc_msat: 0,
2537 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
2539 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2541 let usage = ChannelUsage { inflight_htlc_msat: 251, ..usage };
2542 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2546 fn removes_uncertainity_when_exact_liquidity_known() {
2547 let logger = TestLogger::new();
2548 let network_graph = network_graph(&logger);
2549 let params = ProbabilisticScoringParameters::default();
2550 let scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger);
2551 let source = source_node_id();
2552 let target = target_node_id();
2554 let base_penalty_msat = params.base_penalty_msat;
2555 let usage = ChannelUsage {
2557 inflight_htlc_msat: 0,
2558 effective_capacity: EffectiveCapacity::ExactLiquidity { liquidity_msat: 1_000 },
2560 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), base_penalty_msat);
2562 let usage = ChannelUsage { amount_msat: 1_000, ..usage };
2563 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), base_penalty_msat);
2565 let usage = ChannelUsage { amount_msat: 1_001, ..usage };
2566 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2570 fn remembers_historical_failures() {
2571 let logger = TestLogger::new();
2572 let network_graph = network_graph(&logger);
2573 let params = ProbabilisticScoringParameters {
2574 historical_liquidity_penalty_multiplier_msat: 1024,
2575 historical_liquidity_penalty_amount_multiplier_msat: 1024,
2576 historical_no_updates_half_life: Duration::from_secs(10),
2577 ..ProbabilisticScoringParameters::zero_penalty()
2579 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2580 let source = source_node_id();
2581 let target = target_node_id();
2583 let usage = ChannelUsage {
2585 inflight_htlc_msat: 0,
2586 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_024) },
2588 // With no historical data the normal liquidity penalty calculation is used.
2589 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 47);
2591 scorer.payment_path_failed(&payment_path_for_amount(1).iter().collect::<Vec<_>>(), 42);
2592 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2048);
2594 // Even after we tell the scorer we definitely have enough available liquidity, it will
2595 // still remember that there was some failure in the past, and assign a non-0 penalty.
2596 scorer.payment_path_failed(&payment_path_for_amount(1000).iter().collect::<Vec<_>>(), 43);
2597 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 198);
2599 // Advance the time forward 16 half-lives (which the docs claim will ensure all data is
2600 // gone), and check that we're back to where we started.
2601 SinceEpoch::advance(Duration::from_secs(10 * 16));
2602 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 47);
2606 fn adds_anti_probing_penalty() {
2607 let logger = TestLogger::new();
2608 let network_graph = network_graph(&logger);
2609 let source = source_node_id();
2610 let target = target_node_id();
2611 let params = ProbabilisticScoringParameters {
2612 anti_probing_penalty_msat: 500,
2613 ..ProbabilisticScoringParameters::zero_penalty()
2615 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2617 // Check we receive no penalty for a low htlc_maximum_msat.
2618 let usage = ChannelUsage {
2619 amount_msat: 512_000,
2620 inflight_htlc_msat: 0,
2621 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(1_000) },
2623 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2625 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity.
2626 let usage = ChannelUsage {
2627 amount_msat: 512_000,
2628 inflight_htlc_msat: 0,
2629 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(1_024_000) },
2631 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500);
2633 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity/2.
2634 let usage = ChannelUsage {
2635 amount_msat: 512_000,
2636 inflight_htlc_msat: 0,
2637 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(512_000) },
2639 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500);
2641 // Check we receive no anti-probing penalty for htlc_maximum_msat == channel_capacity/2 - 1.
2642 let usage = ChannelUsage {
2643 amount_msat: 512_000,
2644 inflight_htlc_msat: 0,
2645 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(511_999) },
2647 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);