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