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.read_only(), 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::ops::{Deref, DerefMut};
68 use core::time::Duration;
70 use sync::{Mutex, MutexGuard};
72 /// We define Score ever-so-slightly differently based on whether we are being built for C bindings
73 /// or not. For users, `LockableScore` must somehow be writeable to disk. For Rust users, this is
74 /// no problem - you move a `Score` that implements `Writeable` into a `Mutex`, lock it, and now
75 /// you have the original, concrete, `Score` type, which presumably implements `Writeable`.
77 /// For C users, once you've moved the `Score` into a `LockableScore` all you have after locking it
78 /// is an opaque trait object with an opaque pointer with no type info. Users could take the unsafe
79 /// approach of blindly casting that opaque pointer to a concrete type and calling `Writeable` from
80 /// there, but other languages downstream of the C bindings (e.g. Java) can't even do that.
81 /// Instead, we really want `Score` and `LockableScore` to implement `Writeable` directly, which we
82 /// do here by defining `Score` differently for `cfg(c_bindings)`.
83 macro_rules! define_score { ($($supertrait: path)*) => {
84 /// An interface used to score payment channels for path finding.
86 /// Scoring is in terms of fees willing to be paid in order to avoid routing through a channel.
87 pub trait Score $(: $supertrait)* {
88 /// Returns the fee in msats willing to be paid to avoid routing `send_amt_msat` through the
89 /// given channel in the direction from `source` to `target`.
91 /// The channel's capacity (less any other MPP parts that are also being considered for use in
92 /// the same payment) is given by `capacity_msat`. It may be determined from various sources
93 /// such as a chain data, network gossip, or invoice hints. For invoice hints, a capacity near
94 /// [`u64::max_value`] is given to indicate sufficient capacity for the invoice's full amount.
95 /// Thus, implementations should be overflow-safe.
96 fn channel_penalty_msat(
97 &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage
100 /// Handles updating channel penalties after failing to route through a channel.
101 fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64);
103 /// Handles updating channel penalties after successfully routing along a path.
104 fn payment_path_successful(&mut self, path: &[&RouteHop]);
107 impl<S: Score, T: DerefMut<Target=S> $(+ $supertrait)*> Score for T {
108 fn channel_penalty_msat(
109 &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage
111 self.deref().channel_penalty_msat(short_channel_id, source, target, usage)
114 fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
115 self.deref_mut().payment_path_failed(path, short_channel_id)
118 fn payment_path_successful(&mut self, path: &[&RouteHop]) {
119 self.deref_mut().payment_path_successful(path)
125 define_score!(Writeable);
126 #[cfg(not(c_bindings))]
129 /// A scorer that is accessed under a lock.
131 /// Needed so that calls to [`Score::channel_penalty_msat`] in [`find_route`] can be made while
132 /// having shared ownership of a scorer but without requiring internal locking in [`Score`]
133 /// implementations. Internal locking would be detrimental to route finding performance and could
134 /// result in [`Score::channel_penalty_msat`] returning a different value for the same channel.
136 /// [`find_route`]: crate::routing::router::find_route
137 pub trait LockableScore<'a> {
138 /// The locked [`Score`] type.
139 type Locked: 'a + Score;
141 /// Returns the locked scorer.
142 fn lock(&'a self) -> Self::Locked;
145 /// Refers to a scorer that is accessible under lock and also writeable to disk
147 /// We need this trait to be able to pass in a scorer to `lightning-background-processor` that will enable us to
148 /// use the Persister to persist it.
149 pub trait WriteableScore<'a>: LockableScore<'a> + Writeable {}
151 impl<'a, T> WriteableScore<'a> for T where T: LockableScore<'a> + Writeable {}
154 impl<'a, T: 'a + Score> LockableScore<'a> for Mutex<T> {
155 type Locked = MutexGuard<'a, T>;
157 fn lock(&'a self) -> MutexGuard<'a, T> {
158 Mutex::lock(self).unwrap()
162 impl<'a, T: 'a + Score> LockableScore<'a> for RefCell<T> {
163 type Locked = RefMut<'a, T>;
165 fn lock(&'a self) -> RefMut<'a, T> {
171 /// A concrete implementation of [`LockableScore`] which supports multi-threading.
172 pub struct MultiThreadedLockableScore<S: Score> {
177 impl<'a, T: Score + 'a> LockableScore<'a> for MultiThreadedLockableScore<T> {
178 type Locked = MutexGuard<'a, T>;
180 fn lock(&'a self) -> MutexGuard<'a, T> {
181 Mutex::lock(&self.score).unwrap()
186 impl<T: Score> MultiThreadedLockableScore<T> {
187 /// Creates a new [`MultiThreadedLockableScore`] given an underlying [`Score`].
188 pub fn new(score: T) -> Self {
189 MultiThreadedLockableScore { score: Mutex::new(score) }
195 impl<'a, T: Writeable> Writeable for RefMut<'a, T> {
196 fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
197 T::write(&**self, writer)
203 impl<'a, S: Writeable> Writeable for MutexGuard<'a, S> {
204 fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
205 S::write(&**self, writer)
209 /// Proposed use of a channel passed as a parameter to [`Score::channel_penalty_msat`].
210 #[derive(Clone, Copy)]
211 pub struct ChannelUsage {
212 /// The amount to send through the channel, denominated in millisatoshis.
213 pub amount_msat: u64,
215 /// Total amount, denominated in millisatoshis, already allocated to send through the channel
216 /// as part of a multi-path payment.
217 pub inflight_htlc_msat: u64,
219 /// The effective capacity of the channel.
220 pub effective_capacity: EffectiveCapacity,
224 /// [`Score`] implementation that uses a fixed penalty.
225 pub struct FixedPenaltyScorer {
229 impl FixedPenaltyScorer {
230 /// Creates a new scorer using `penalty_msat`.
231 pub fn with_penalty(penalty_msat: u64) -> Self {
232 Self { penalty_msat }
236 impl Score for FixedPenaltyScorer {
237 fn channel_penalty_msat(&self, _: u64, _: &NodeId, _: &NodeId, _: ChannelUsage) -> u64 {
241 fn payment_path_failed(&mut self, _path: &[&RouteHop], _short_channel_id: u64) {}
243 fn payment_path_successful(&mut self, _path: &[&RouteHop]) {}
246 impl Writeable for FixedPenaltyScorer {
248 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
249 write_tlv_fields!(w, {});
254 impl ReadableArgs<u64> for FixedPenaltyScorer {
256 fn read<R: Read>(r: &mut R, penalty_msat: u64) -> Result<Self, DecodeError> {
257 read_tlv_fields!(r, {});
258 Ok(Self { penalty_msat })
262 #[cfg(not(feature = "no-std"))]
263 type ConfiguredTime = std::time::Instant;
264 #[cfg(feature = "no-std")]
265 use util::time::Eternity;
266 #[cfg(feature = "no-std")]
267 type ConfiguredTime = Eternity;
269 /// [`Score`] implementation using channel success probability distributions.
271 /// Based on *Optimally Reliable & Cheap Payment Flows on the Lightning Network* by Rene Pickhardt
272 /// and Stefan Richter [[1]]. Given the uncertainty of channel liquidity balances, probability
273 /// distributions are defined based on knowledge learned from successful and unsuccessful attempts.
274 /// Then the negative `log10` of the success probability is used to determine the cost of routing a
275 /// specific HTLC amount through a channel.
277 /// Knowledge about channel liquidity balances takes the form of upper and lower bounds on the
278 /// possible liquidity. Certainty of the bounds is decreased over time using a decay function. See
279 /// [`ProbabilisticScoringParameters`] for details.
281 /// Since the scorer aims to learn the current channel liquidity balances, it works best for nodes
282 /// with high payment volume or that actively probe the [`NetworkGraph`]. Nodes with low payment
283 /// volume are more likely to experience failed payment paths, which would need to be retried.
287 /// Mixing the `no-std` feature between serialization and deserialization results in undefined
290 /// [1]: https://arxiv.org/abs/2107.05322
291 pub type ProbabilisticScorer<G, L> = ProbabilisticScorerUsingTime::<G, L, ConfiguredTime>;
293 /// Probabilistic [`Score`] implementation.
295 /// (C-not exported) generally all users should use the [`ProbabilisticScorer`] type alias.
296 pub struct ProbabilisticScorerUsingTime<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time>
297 where L::Target: Logger {
298 params: ProbabilisticScoringParameters,
301 // TODO: Remove entries of closed channels.
302 channel_liquidities: HashMap<u64, ChannelLiquidity<T>>,
305 /// Parameters for configuring [`ProbabilisticScorer`].
307 /// Used to configure base, liquidity, and amount penalties, the sum of which comprises the channel
308 /// penalty (i.e., the amount in msats willing to be paid to avoid routing through the channel).
310 pub struct ProbabilisticScoringParameters {
311 /// A fixed penalty in msats to apply to each channel.
313 /// Default value: 500 msat
314 pub base_penalty_msat: u64,
316 /// A multiplier used in conjunction with the negative `log10` of the channel's success
317 /// probability for a payment to determine the liquidity penalty.
319 /// The penalty is based in part on the knowledge learned from prior successful and unsuccessful
320 /// payments. This knowledge is decayed over time based on [`liquidity_offset_half_life`]. The
321 /// penalty is effectively limited to `2 * liquidity_penalty_multiplier_msat` (corresponding to
322 /// lower bounding the success probability to `0.01`) when the amount falls within the
323 /// uncertainty bounds of the channel liquidity balance. Amounts above the upper bound will
324 /// result in a `u64::max_value` penalty, however.
326 /// Default value: 40,000 msat
328 /// [`liquidity_offset_half_life`]: Self::liquidity_offset_half_life
329 pub liquidity_penalty_multiplier_msat: u64,
331 /// The time required to elapse before any knowledge learned about channel liquidity balances is
334 /// The bounds are defined in terms of offsets and are initially zero. Increasing the offsets
335 /// gives tighter bounds on the channel liquidity balance. Thus, halving the offsets decreases
336 /// the certainty of the channel liquidity balance.
338 /// Default value: 1 hour
342 /// When built with the `no-std` feature, time will never elapse. Therefore, the channel
343 /// liquidity knowledge will never decay except when the bounds cross.
344 pub liquidity_offset_half_life: Duration,
346 /// A multiplier used in conjunction with a payment amount and the negative `log10` of the
347 /// channel's success probability for the payment to determine the amount penalty.
349 /// The purpose of the amount penalty is to avoid having fees dominate the channel cost (i.e.,
350 /// fees plus penalty) for large payments. The penalty is computed as the product of this
351 /// multiplier and `2^20`ths of the payment amount, weighted by the negative `log10` of the
352 /// success probability.
354 /// `-log10(success_probability) * amount_penalty_multiplier_msat * amount_msat / 2^20`
356 /// In practice, this means for 0.1 success probability (`-log10(0.1) == 1`) each `2^20`th of
357 /// the amount will result in a penalty of the multiplier. And, as the success probability
358 /// decreases, the negative `log10` weighting will increase dramatically. For higher success
359 /// probabilities, the multiplier will have a decreasing effect as the negative `log10` will
362 /// Default value: 256 msat
363 pub amount_penalty_multiplier_msat: u64,
365 /// A list of nodes that won't be considered during path finding.
368 pub banned_nodes: HashSet<NodeId>,
371 /// Accounting for channel liquidity balance uncertainty.
373 /// Direction is defined in terms of [`NodeId`] partial ordering, where the source node is the
374 /// first node in the ordering of the channel's counterparties. Thus, swapping the two liquidity
375 /// offset fields gives the opposite direction.
376 struct ChannelLiquidity<T: Time> {
377 /// Lower channel liquidity bound in terms of an offset from zero.
378 min_liquidity_offset_msat: u64,
380 /// Upper channel liquidity bound in terms of an offset from the effective capacity.
381 max_liquidity_offset_msat: u64,
383 /// Time when the liquidity bounds were last modified.
387 /// A snapshot of [`ChannelLiquidity`] in one direction assuming a certain channel capacity and
388 /// decayed with a given half life.
389 struct DirectedChannelLiquidity<L: Deref<Target = u64>, T: Time, U: Deref<Target = T>> {
390 min_liquidity_offset_msat: L,
391 max_liquidity_offset_msat: L,
398 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
399 /// Creates a new scorer using the given scoring parameters for sending payments from a node
400 /// through a network graph.
401 pub fn new(params: ProbabilisticScoringParameters, network_graph: G, logger: L) -> Self {
406 channel_liquidities: HashMap::new(),
411 fn with_channel(mut self, short_channel_id: u64, liquidity: ChannelLiquidity<T>) -> Self {
412 assert!(self.channel_liquidities.insert(short_channel_id, liquidity).is_none());
416 /// Dump the contents of this scorer into the configured logger.
418 /// Note that this writes roughly one line per channel for which we have a liquidity estimate,
419 /// which may be a substantial amount of log output.
420 pub fn debug_log_liquidity_stats(&self) {
421 let graph = self.network_graph.read_only();
422 for (scid, liq) in self.channel_liquidities.iter() {
423 if let Some(chan_debug) = graph.channels().get(scid) {
424 let log_direction = |source, target| {
425 if let Some((directed_info, _)) = chan_debug.as_directed_to(target) {
426 let amt = directed_info.effective_capacity().as_msat();
427 let dir_liq = liq.as_directed(source, target, amt, self.params.liquidity_offset_half_life);
428 log_debug!(self.logger, "Liquidity from {:?} to {:?} via {} is in the range ({}, {})",
429 source, target, scid, dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat());
431 log_debug!(self.logger, "No amount known for SCID {} from {:?} to {:?}", scid, source, target);
435 log_direction(&chan_debug.node_one, &chan_debug.node_two);
436 log_direction(&chan_debug.node_two, &chan_debug.node_one);
438 log_debug!(self.logger, "No network graph entry for SCID {}", scid);
443 /// Query the estimated minimum and maximum liquidity available for sending a payment over the
444 /// channel with `scid` towards the given `target` node.
445 pub fn estimated_channel_liquidity_range(&self, scid: u64, target: &NodeId) -> Option<(u64, u64)> {
446 let graph = self.network_graph.read_only();
448 if let Some(chan) = graph.channels().get(&scid) {
449 if let Some(liq) = self.channel_liquidities.get(&scid) {
450 if let Some((directed_info, source)) = chan.as_directed_to(target) {
451 let amt = directed_info.effective_capacity().as_msat();
452 let dir_liq = liq.as_directed(source, target, amt, self.params.liquidity_offset_half_life);
453 return Some((dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat()));
460 /// Marks the node with the given `node_id` as banned, i.e.,
461 /// it will be avoided during path finding.
462 pub fn add_banned(&mut self, node_id: &NodeId) {
463 self.params.banned_nodes.insert(*node_id);
466 /// Removes the node with the given `node_id` from the list of nodes to avoid.
467 pub fn remove_banned(&mut self, node_id: &NodeId) {
468 self.params.banned_nodes.remove(node_id);
471 /// Clears the list of nodes that are avoided during path finding.
472 pub fn clear_banned(&mut self) {
473 self.params.banned_nodes = HashSet::new();
477 impl ProbabilisticScoringParameters {
479 fn zero_penalty() -> Self {
481 base_penalty_msat: 0,
482 liquidity_penalty_multiplier_msat: 0,
483 liquidity_offset_half_life: Duration::from_secs(3600),
484 amount_penalty_multiplier_msat: 0,
485 banned_nodes: HashSet::new(),
489 /// Marks all nodes in the given list as banned, i.e.,
490 /// they will be avoided during path finding.
491 pub fn add_banned_from_list(&mut self, node_ids: Vec<NodeId>) {
493 self.banned_nodes.insert(id);
498 impl Default for ProbabilisticScoringParameters {
499 fn default() -> Self {
501 base_penalty_msat: 500,
502 liquidity_penalty_multiplier_msat: 40_000,
503 liquidity_offset_half_life: Duration::from_secs(3600),
504 amount_penalty_multiplier_msat: 256,
505 banned_nodes: HashSet::new(),
510 impl<T: Time> ChannelLiquidity<T> {
514 min_liquidity_offset_msat: 0,
515 max_liquidity_offset_msat: 0,
516 last_updated: T::now(),
520 /// Returns a view of the channel liquidity directed from `source` to `target` assuming
523 &self, source: &NodeId, target: &NodeId, capacity_msat: u64, half_life: Duration
524 ) -> DirectedChannelLiquidity<&u64, T, &T> {
525 let (min_liquidity_offset_msat, max_liquidity_offset_msat) = if source < target {
526 (&self.min_liquidity_offset_msat, &self.max_liquidity_offset_msat)
528 (&self.max_liquidity_offset_msat, &self.min_liquidity_offset_msat)
531 DirectedChannelLiquidity {
532 min_liquidity_offset_msat,
533 max_liquidity_offset_msat,
535 last_updated: &self.last_updated,
541 /// Returns a mutable view of the channel liquidity directed from `source` to `target` assuming
544 &mut self, source: &NodeId, target: &NodeId, capacity_msat: u64, half_life: Duration
545 ) -> DirectedChannelLiquidity<&mut u64, T, &mut T> {
546 let (min_liquidity_offset_msat, max_liquidity_offset_msat) = if source < target {
547 (&mut self.min_liquidity_offset_msat, &mut self.max_liquidity_offset_msat)
549 (&mut self.max_liquidity_offset_msat, &mut self.min_liquidity_offset_msat)
552 DirectedChannelLiquidity {
553 min_liquidity_offset_msat,
554 max_liquidity_offset_msat,
556 last_updated: &mut self.last_updated,
563 /// Bounds `-log10` to avoid excessive liquidity penalties for payments with low success
565 const NEGATIVE_LOG10_UPPER_BOUND: u64 = 2;
567 /// The rough cutoff at which our precision falls off and we should stop bothering to try to log a
568 /// ratio, as X in 1/X.
569 const PRECISION_LOWER_BOUND_DENOMINATOR: u64 = approx::LOWER_BITS_BOUND;
571 /// The divisor used when computing the amount penalty.
572 const AMOUNT_PENALTY_DIVISOR: u64 = 1 << 20;
574 impl<L: Deref<Target = u64>, T: Time, U: Deref<Target = T>> DirectedChannelLiquidity<L, T, U> {
575 /// Returns a penalty for routing the given HTLC `amount_msat` through the channel in this
577 fn penalty_msat(&self, amount_msat: u64, params: &ProbabilisticScoringParameters) -> u64 {
578 let max_liquidity_msat = self.max_liquidity_msat();
579 let min_liquidity_msat = core::cmp::min(self.min_liquidity_msat(), max_liquidity_msat);
580 if amount_msat <= min_liquidity_msat {
582 } else if amount_msat >= max_liquidity_msat {
583 if amount_msat > max_liquidity_msat {
585 } else if max_liquidity_msat != self.capacity_msat {
586 // Avoid using the failed channel on retry.
589 // Equivalent to hitting the else clause below with the amount equal to the
590 // effective capacity and without any certainty on the liquidity upper bound.
591 let negative_log10_times_2048 = NEGATIVE_LOG10_UPPER_BOUND * 2048;
592 self.combined_penalty_msat(amount_msat, negative_log10_times_2048, params)
595 let numerator = (max_liquidity_msat - amount_msat).saturating_add(1);
596 let denominator = (max_liquidity_msat - min_liquidity_msat).saturating_add(1);
597 if amount_msat - min_liquidity_msat < denominator / PRECISION_LOWER_BOUND_DENOMINATOR {
598 // If the failure probability is < 1.5625% (as 1 - numerator/denominator < 1/64),
599 // don't bother trying to use the log approximation as it gets too noisy to be
600 // particularly helpful, instead just round down to 0 and return the base penalty.
601 params.base_penalty_msat
603 let negative_log10_times_2048 =
604 approx::negative_log10_times_2048(numerator, denominator);
605 self.combined_penalty_msat(amount_msat, negative_log10_times_2048, params)
610 /// Computes the liquidity and amount penalties and adds them to the base penalty.
612 fn combined_penalty_msat(
613 &self, amount_msat: u64, negative_log10_times_2048: u64,
614 params: &ProbabilisticScoringParameters
616 let liquidity_penalty_msat = {
617 // Upper bound the liquidity penalty to ensure some channel is selected.
618 let multiplier_msat = params.liquidity_penalty_multiplier_msat;
619 let max_penalty_msat = multiplier_msat.saturating_mul(NEGATIVE_LOG10_UPPER_BOUND);
620 (negative_log10_times_2048.saturating_mul(multiplier_msat) / 2048).min(max_penalty_msat)
622 let amount_penalty_msat = negative_log10_times_2048
623 .saturating_mul(params.amount_penalty_multiplier_msat)
624 .saturating_mul(amount_msat) / 2048 / AMOUNT_PENALTY_DIVISOR;
626 params.base_penalty_msat
627 .saturating_add(liquidity_penalty_msat)
628 .saturating_add(amount_penalty_msat)
631 /// Returns the lower bound of the channel liquidity balance in this direction.
632 fn min_liquidity_msat(&self) -> u64 {
633 self.decayed_offset_msat(*self.min_liquidity_offset_msat)
636 /// Returns the upper bound of the channel liquidity balance in this direction.
637 fn max_liquidity_msat(&self) -> u64 {
639 .checked_sub(self.decayed_offset_msat(*self.max_liquidity_offset_msat))
643 fn decayed_offset_msat(&self, offset_msat: u64) -> u64 {
644 self.now.duration_since(*self.last_updated).as_secs()
645 .checked_div(self.half_life.as_secs())
646 .and_then(|decays| offset_msat.checked_shr(decays as u32))
651 impl<L: DerefMut<Target = u64>, T: Time, U: DerefMut<Target = T>> DirectedChannelLiquidity<L, T, U> {
652 /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat`.
653 fn failed_at_channel<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
654 if amount_msat < self.max_liquidity_msat() {
655 log_debug!(logger, "Setting max liquidity of {} to {}", chan_descr, amount_msat);
656 self.set_max_liquidity_msat(amount_msat);
658 log_trace!(logger, "Max liquidity of {} already more than {}", chan_descr, amount_msat);
662 /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat` downstream.
663 fn failed_downstream<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
664 if amount_msat > self.min_liquidity_msat() {
665 log_debug!(logger, "Setting min liquidity of {} to {}", chan_descr, amount_msat);
666 self.set_min_liquidity_msat(amount_msat);
668 log_trace!(logger, "Min liquidity of {} already less than {}", chan_descr, amount_msat);
672 /// Adjusts the channel liquidity balance bounds when successfully routing `amount_msat`.
673 fn successful<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
674 let max_liquidity_msat = self.max_liquidity_msat().checked_sub(amount_msat).unwrap_or(0);
675 log_debug!(logger, "Subtracting {} from max liquidity of {} (setting it to {})", amount_msat, chan_descr, max_liquidity_msat);
676 self.set_max_liquidity_msat(max_liquidity_msat);
679 /// Adjusts the lower bound of the channel liquidity balance in this direction.
680 fn set_min_liquidity_msat(&mut self, amount_msat: u64) {
681 *self.min_liquidity_offset_msat = amount_msat;
682 *self.max_liquidity_offset_msat = if amount_msat > self.max_liquidity_msat() {
685 self.decayed_offset_msat(*self.max_liquidity_offset_msat)
687 *self.last_updated = self.now;
690 /// Adjusts the upper bound of the channel liquidity balance in this direction.
691 fn set_max_liquidity_msat(&mut self, amount_msat: u64) {
692 *self.max_liquidity_offset_msat = self.capacity_msat.checked_sub(amount_msat).unwrap_or(0);
693 *self.min_liquidity_offset_msat = if amount_msat < self.min_liquidity_msat() {
696 self.decayed_offset_msat(*self.min_liquidity_offset_msat)
698 *self.last_updated = self.now;
702 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Score for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
703 fn channel_penalty_msat(
704 &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage
706 if self.params.banned_nodes.contains(source) || self.params.banned_nodes.contains(target) {
707 return u64::max_value();
710 if let EffectiveCapacity::ExactLiquidity { liquidity_msat } = usage.effective_capacity {
711 if usage.amount_msat > liquidity_msat {
712 return u64::max_value();
714 return self.params.base_penalty_msat;
718 let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
719 let amount_msat = usage.amount_msat;
720 let capacity_msat = usage.effective_capacity.as_msat()
721 .saturating_sub(usage.inflight_htlc_msat);
722 self.channel_liquidities
723 .get(&short_channel_id)
724 .unwrap_or(&ChannelLiquidity::new())
725 .as_directed(source, target, capacity_msat, liquidity_offset_half_life)
726 .penalty_msat(amount_msat, &self.params)
729 fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
730 let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
731 let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
732 log_trace!(self.logger, "Scoring path through to SCID {} as having failed at {} msat", short_channel_id, amount_msat);
733 let network_graph = self.network_graph.read_only();
734 for (hop_idx, hop) in path.iter().enumerate() {
735 let target = NodeId::from_pubkey(&hop.pubkey);
736 let channel_directed_from_source = network_graph.channels()
737 .get(&hop.short_channel_id)
738 .and_then(|channel| channel.as_directed_to(&target));
740 if hop.short_channel_id == short_channel_id && hop_idx == 0 {
741 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);
744 // Only score announced channels.
745 if let Some((channel, source)) = channel_directed_from_source {
746 let capacity_msat = channel.effective_capacity().as_msat();
747 if hop.short_channel_id == short_channel_id {
748 self.channel_liquidities
749 .entry(hop.short_channel_id)
750 .or_insert_with(ChannelLiquidity::new)
751 .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life)
752 .failed_at_channel(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
756 self.channel_liquidities
757 .entry(hop.short_channel_id)
758 .or_insert_with(ChannelLiquidity::new)
759 .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life)
760 .failed_downstream(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
762 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).",
763 hop.short_channel_id);
768 fn payment_path_successful(&mut self, path: &[&RouteHop]) {
769 let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
770 let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
771 log_trace!(self.logger, "Scoring path through SCID {} as having succeeded at {} msat.",
772 path.split_last().map(|(hop, _)| hop.short_channel_id).unwrap_or(0), amount_msat);
773 let network_graph = self.network_graph.read_only();
775 let target = NodeId::from_pubkey(&hop.pubkey);
776 let channel_directed_from_source = network_graph.channels()
777 .get(&hop.short_channel_id)
778 .and_then(|channel| channel.as_directed_to(&target));
780 // Only score announced channels.
781 if let Some((channel, source)) = channel_directed_from_source {
782 let capacity_msat = channel.effective_capacity().as_msat();
783 self.channel_liquidities
784 .entry(hop.short_channel_id)
785 .or_insert_with(ChannelLiquidity::new)
786 .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life)
787 .successful(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
789 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).",
790 hop.short_channel_id);
797 const BITS: u32 = 64;
798 const HIGHEST_BIT: u32 = BITS - 1;
799 const LOWER_BITS: u32 = 6;
800 pub(super) const LOWER_BITS_BOUND: u64 = 1 << LOWER_BITS;
801 const LOWER_BITMASK: u64 = (1 << LOWER_BITS) - 1;
803 /// Look-up table for `log10(x) * 2048` where row `i` is used for each `x` having `i` as the
804 /// most significant bit. The next 4 bits of `x`, if applicable, are used for the second index.
805 const LOG10_TIMES_2048: [[u16; (LOWER_BITS_BOUND) as usize]; BITS as usize] = [
806 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
807 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
808 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
809 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
810 [617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
811 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
812 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977,
813 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977],
814 [1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233,
815 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431,
816 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594,
817 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731],
818 [1850, 1850, 1850, 1850, 1850, 1850, 1850, 1850, 1954, 1954, 1954, 1954, 1954, 1954, 1954, 1954,
819 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2133, 2133, 2133, 2133, 2133, 2133, 2133, 2133,
820 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2281, 2281, 2281, 2281, 2281, 2281, 2281, 2281,
821 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2409, 2409, 2409, 2409, 2409, 2409, 2409, 2409],
822 [2466, 2466, 2466, 2466, 2520, 2520, 2520, 2520, 2571, 2571, 2571, 2571, 2619, 2619, 2619, 2619,
823 2665, 2665, 2665, 2665, 2708, 2708, 2708, 2708, 2749, 2749, 2749, 2749, 2789, 2789, 2789, 2789,
824 2827, 2827, 2827, 2827, 2863, 2863, 2863, 2863, 2898, 2898, 2898, 2898, 2931, 2931, 2931, 2931,
825 2964, 2964, 2964, 2964, 2995, 2995, 2995, 2995, 3025, 3025, 3025, 3025, 3054, 3054, 3054, 3054],
826 [3083, 3083, 3110, 3110, 3136, 3136, 3162, 3162, 3187, 3187, 3212, 3212, 3235, 3235, 3259, 3259,
827 3281, 3281, 3303, 3303, 3324, 3324, 3345, 3345, 3366, 3366, 3386, 3386, 3405, 3405, 3424, 3424,
828 3443, 3443, 3462, 3462, 3479, 3479, 3497, 3497, 3514, 3514, 3531, 3531, 3548, 3548, 3564, 3564,
829 3580, 3580, 3596, 3596, 3612, 3612, 3627, 3627, 3642, 3642, 3656, 3656, 3671, 3671, 3685, 3685],
830 [3699, 3713, 3726, 3740, 3753, 3766, 3779, 3791, 3804, 3816, 3828, 3840, 3852, 3864, 3875, 3886,
831 3898, 3909, 3919, 3930, 3941, 3951, 3962, 3972, 3982, 3992, 4002, 4012, 4022, 4031, 4041, 4050,
832 4060, 4069, 4078, 4087, 4096, 4105, 4114, 4122, 4131, 4139, 4148, 4156, 4164, 4173, 4181, 4189,
833 4197, 4205, 4213, 4220, 4228, 4236, 4243, 4251, 4258, 4266, 4273, 4280, 4287, 4294, 4302, 4309],
834 [4316, 4329, 4343, 4356, 4369, 4382, 4395, 4408, 4420, 4433, 4445, 4457, 4468, 4480, 4492, 4503,
835 4514, 4525, 4536, 4547, 4557, 4568, 4578, 4589, 4599, 4609, 4619, 4629, 4638, 4648, 4657, 4667,
836 4676, 4685, 4695, 4704, 4713, 4721, 4730, 4739, 4747, 4756, 4764, 4773, 4781, 4789, 4797, 4805,
837 4813, 4821, 4829, 4837, 4845, 4852, 4860, 4867, 4875, 4882, 4889, 4897, 4904, 4911, 4918, 4925],
838 [4932, 4946, 4959, 4973, 4986, 4999, 5012, 5024, 5037, 5049, 5061, 5073, 5085, 5097, 5108, 5119,
839 5131, 5142, 5153, 5163, 5174, 5184, 5195, 5205, 5215, 5225, 5235, 5245, 5255, 5264, 5274, 5283,
840 5293, 5302, 5311, 5320, 5329, 5338, 5347, 5355, 5364, 5372, 5381, 5389, 5397, 5406, 5414, 5422,
841 5430, 5438, 5446, 5453, 5461, 5469, 5476, 5484, 5491, 5499, 5506, 5513, 5520, 5527, 5535, 5542],
842 [5549, 5562, 5576, 5589, 5603, 5615, 5628, 5641, 5653, 5666, 5678, 5690, 5701, 5713, 5725, 5736,
843 5747, 5758, 5769, 5780, 5790, 5801, 5811, 5822, 5832, 5842, 5852, 5862, 5871, 5881, 5890, 5900,
844 5909, 5918, 5928, 5937, 5946, 5954, 5963, 5972, 5980, 5989, 5997, 6006, 6014, 6022, 6030, 6038,
845 6046, 6054, 6062, 6070, 6078, 6085, 6093, 6100, 6108, 6115, 6122, 6130, 6137, 6144, 6151, 6158],
846 [6165, 6179, 6192, 6206, 6219, 6232, 6245, 6257, 6270, 6282, 6294, 6306, 6318, 6330, 6341, 6352,
847 6364, 6375, 6386, 6396, 6407, 6417, 6428, 6438, 6448, 6458, 6468, 6478, 6488, 6497, 6507, 6516,
848 6526, 6535, 6544, 6553, 6562, 6571, 6580, 6588, 6597, 6605, 6614, 6622, 6630, 6639, 6647, 6655,
849 6663, 6671, 6679, 6686, 6694, 6702, 6709, 6717, 6724, 6732, 6739, 6746, 6753, 6761, 6768, 6775],
850 [6782, 6795, 6809, 6822, 6836, 6849, 6861, 6874, 6886, 6899, 6911, 6923, 6934, 6946, 6958, 6969,
851 6980, 6991, 7002, 7013, 7023, 7034, 7044, 7055, 7065, 7075, 7085, 7095, 7104, 7114, 7124, 7133,
852 7142, 7151, 7161, 7170, 7179, 7187, 7196, 7205, 7213, 7222, 7230, 7239, 7247, 7255, 7263, 7271,
853 7279, 7287, 7295, 7303, 7311, 7318, 7326, 7333, 7341, 7348, 7355, 7363, 7370, 7377, 7384, 7391],
854 [7398, 7412, 7425, 7439, 7452, 7465, 7478, 7490, 7503, 7515, 7527, 7539, 7551, 7563, 7574, 7585,
855 7597, 7608, 7619, 7629, 7640, 7651, 7661, 7671, 7681, 7691, 7701, 7711, 7721, 7731, 7740, 7749,
856 7759, 7768, 7777, 7786, 7795, 7804, 7813, 7821, 7830, 7838, 7847, 7855, 7864, 7872, 7880, 7888,
857 7896, 7904, 7912, 7919, 7927, 7935, 7942, 7950, 7957, 7965, 7972, 7979, 7986, 7994, 8001, 8008],
858 [8015, 8028, 8042, 8055, 8069, 8082, 8094, 8107, 8119, 8132, 8144, 8156, 8167, 8179, 8191, 8202,
859 8213, 8224, 8235, 8246, 8256, 8267, 8277, 8288, 8298, 8308, 8318, 8328, 8337, 8347, 8357, 8366,
860 8375, 8384, 8394, 8403, 8412, 8420, 8429, 8438, 8446, 8455, 8463, 8472, 8480, 8488, 8496, 8504,
861 8512, 8520, 8528, 8536, 8544, 8551, 8559, 8566, 8574, 8581, 8588, 8596, 8603, 8610, 8617, 8624],
862 [8631, 8645, 8659, 8672, 8685, 8698, 8711, 8723, 8736, 8748, 8760, 8772, 8784, 8796, 8807, 8818,
863 8830, 8841, 8852, 8862, 8873, 8884, 8894, 8904, 8914, 8924, 8934, 8944, 8954, 8964, 8973, 8982,
864 8992, 9001, 9010, 9019, 9028, 9037, 9046, 9054, 9063, 9071, 9080, 9088, 9097, 9105, 9113, 9121,
865 9129, 9137, 9145, 9152, 9160, 9168, 9175, 9183, 9190, 9198, 9205, 9212, 9219, 9227, 9234, 9241],
866 [9248, 9261, 9275, 9288, 9302, 9315, 9327, 9340, 9352, 9365, 9377, 9389, 9400, 9412, 9424, 9435,
867 9446, 9457, 9468, 9479, 9490, 9500, 9510, 9521, 9531, 9541, 9551, 9561, 9570, 9580, 9590, 9599,
868 9608, 9617, 9627, 9636, 9645, 9653, 9662, 9671, 9679, 9688, 9696, 9705, 9713, 9721, 9729, 9737,
869 9745, 9753, 9761, 9769, 9777, 9784, 9792, 9799, 9807, 9814, 9821, 9829, 9836, 9843, 9850, 9857],
870 [9864, 9878, 9892, 9905, 9918, 9931, 9944, 9956, 9969, 9981, 9993, 10005, 10017, 10029, 10040, 10051,
871 10063, 10074, 10085, 10095, 10106, 10117, 10127, 10137, 10147, 10157, 10167, 10177, 10187, 10197, 10206, 10215,
872 10225, 10234, 10243, 10252, 10261, 10270, 10279, 10287, 10296, 10304, 10313, 10321, 10330, 10338, 10346, 10354,
873 10362, 10370, 10378, 10385, 10393, 10401, 10408, 10416, 10423, 10431, 10438, 10445, 10452, 10460, 10467, 10474],
874 [10481, 10494, 10508, 10521, 10535, 10548, 10560, 10573, 10585, 10598, 10610, 10622, 10634, 10645, 10657, 10668,
875 10679, 10690, 10701, 10712, 10723, 10733, 10743, 10754, 10764, 10774, 10784, 10794, 10803, 10813, 10823, 10832,
876 10841, 10851, 10860, 10869, 10878, 10886, 10895, 10904, 10912, 10921, 10929, 10938, 10946, 10954, 10962, 10970,
877 10978, 10986, 10994, 11002, 11010, 11017, 11025, 11032, 11040, 11047, 11054, 11062, 11069, 11076, 11083, 11090],
878 [11097, 11111, 11125, 11138, 11151, 11164, 11177, 11189, 11202, 11214, 11226, 11238, 11250, 11262, 11273, 11284,
879 11296, 11307, 11318, 11328, 11339, 11350, 11360, 11370, 11380, 11390, 11400, 11410, 11420, 11430, 11439, 11448,
880 11458, 11467, 11476, 11485, 11494, 11503, 11512, 11520, 11529, 11538, 11546, 11554, 11563, 11571, 11579, 11587,
881 11595, 11603, 11611, 11618, 11626, 11634, 11641, 11649, 11656, 11664, 11671, 11678, 11685, 11693, 11700, 11707],
882 [11714, 11727, 11741, 11754, 11768, 11781, 11793, 11806, 11818, 11831, 11843, 11855, 11867, 11878, 11890, 11901,
883 11912, 11923, 11934, 11945, 11956, 11966, 11976, 11987, 11997, 12007, 12017, 12027, 12036, 12046, 12056, 12065,
884 12074, 12084, 12093, 12102, 12111, 12119, 12128, 12137, 12146, 12154, 12162, 12171, 12179, 12187, 12195, 12203,
885 12211, 12219, 12227, 12235, 12243, 12250, 12258, 12265, 12273, 12280, 12287, 12295, 12302, 12309, 12316, 12323],
886 [12330, 12344, 12358, 12371, 12384, 12397, 12410, 12423, 12435, 12447, 12459, 12471, 12483, 12495, 12506, 12517,
887 12529, 12540, 12551, 12561, 12572, 12583, 12593, 12603, 12613, 12623, 12633, 12643, 12653, 12663, 12672, 12682,
888 12691, 12700, 12709, 12718, 12727, 12736, 12745, 12753, 12762, 12771, 12779, 12787, 12796, 12804, 12812, 12820,
889 12828, 12836, 12844, 12851, 12859, 12867, 12874, 12882, 12889, 12897, 12904, 12911, 12918, 12926, 12933, 12940],
890 [12947, 12960, 12974, 12987, 13001, 13014, 13026, 13039, 13051, 13064, 13076, 13088, 13100, 13111, 13123, 13134,
891 13145, 13156, 13167, 13178, 13189, 13199, 13209, 13220, 13230, 13240, 13250, 13260, 13269, 13279, 13289, 13298,
892 13307, 13317, 13326, 13335, 13344, 13352, 13361, 13370, 13379, 13387, 13395, 13404, 13412, 13420, 13428, 13436,
893 13444, 13452, 13460, 13468, 13476, 13483, 13491, 13498, 13506, 13513, 13521, 13528, 13535, 13542, 13549, 13556],
894 [13563, 13577, 13591, 13604, 13617, 13630, 13643, 13656, 13668, 13680, 13692, 13704, 13716, 13728, 13739, 13750,
895 13762, 13773, 13784, 13794, 13805, 13816, 13826, 13836, 13846, 13857, 13866, 13876, 13886, 13896, 13905, 13915,
896 13924, 13933, 13942, 13951, 13960, 13969, 13978, 13986, 13995, 14004, 14012, 14020, 14029, 14037, 14045, 14053,
897 14061, 14069, 14077, 14084, 14092, 14100, 14107, 14115, 14122, 14130, 14137, 14144, 14151, 14159, 14166, 14173],
898 [14180, 14194, 14207, 14220, 14234, 14247, 14259, 14272, 14284, 14297, 14309, 14321, 14333, 14344, 14356, 14367,
899 14378, 14389, 14400, 14411, 14422, 14432, 14443, 14453, 14463, 14473, 14483, 14493, 14502, 14512, 14522, 14531,
900 14540, 14550, 14559, 14568, 14577, 14586, 14594, 14603, 14612, 14620, 14628, 14637, 14645, 14653, 14661, 14669,
901 14677, 14685, 14693, 14701, 14709, 14716, 14724, 14731, 14739, 14746, 14754, 14761, 14768, 14775, 14782, 14789],
902 [14796, 14810, 14824, 14837, 14850, 14863, 14876, 14889, 14901, 14913, 14925, 14937, 14949, 14961, 14972, 14984,
903 14995, 15006, 15017, 15027, 15038, 15049, 15059, 15069, 15079, 15090, 15099, 15109, 15119, 15129, 15138, 15148,
904 15157, 15166, 15175, 15184, 15193, 15202, 15211, 15219, 15228, 15237, 15245, 15253, 15262, 15270, 15278, 15286,
905 15294, 15302, 15310, 15317, 15325, 15333, 15340, 15348, 15355, 15363, 15370, 15377, 15384, 15392, 15399, 15406],
906 [15413, 15427, 15440, 15453, 15467, 15480, 15492, 15505, 15517, 15530, 15542, 15554, 15566, 15577, 15589, 15600,
907 15611, 15622, 15633, 15644, 15655, 15665, 15676, 15686, 15696, 15706, 15716, 15726, 15736, 15745, 15755, 15764,
908 15773, 15783, 15792, 15801, 15810, 15819, 15827, 15836, 15845, 15853, 15862, 15870, 15878, 15886, 15894, 15903,
909 15910, 15918, 15926, 15934, 15942, 15949, 15957, 15964, 15972, 15979, 15987, 15994, 16001, 16008, 16015, 16022],
910 [16029, 16043, 16057, 16070, 16083, 16096, 16109, 16122, 16134, 16146, 16158, 16170, 16182, 16194, 16205, 16217,
911 16228, 16239, 16250, 16260, 16271, 16282, 16292, 16302, 16312, 16323, 16332, 16342, 16352, 16362, 16371, 16381,
912 16390, 16399, 16408, 16417, 16426, 16435, 16444, 16452, 16461, 16470, 16478, 16486, 16495, 16503, 16511, 16519,
913 16527, 16535, 16543, 16550, 16558, 16566, 16573, 16581, 16588, 16596, 16603, 16610, 16618, 16625, 16632, 16639],
914 [16646, 16660, 16673, 16686, 16700, 16713, 16725, 16738, 16751, 16763, 16775, 16787, 16799, 16810, 16822, 16833,
915 16844, 16855, 16866, 16877, 16888, 16898, 16909, 16919, 16929, 16939, 16949, 16959, 16969, 16978, 16988, 16997,
916 17006, 17016, 17025, 17034, 17043, 17052, 17060, 17069, 17078, 17086, 17095, 17103, 17111, 17119, 17127, 17136,
917 17143, 17151, 17159, 17167, 17175, 17182, 17190, 17197, 17205, 17212, 17220, 17227, 17234, 17241, 17248, 17255],
918 [17262, 17276, 17290, 17303, 17316, 17329, 17342, 17355, 17367, 17379, 17391, 17403, 17415, 17427, 17438, 17450,
919 17461, 17472, 17483, 17493, 17504, 17515, 17525, 17535, 17546, 17556, 17565, 17575, 17585, 17595, 17604, 17614,
920 17623, 17632, 17641, 17650, 17659, 17668, 17677, 17685, 17694, 17703, 17711, 17719, 17728, 17736, 17744, 17752,
921 17760, 17768, 17776, 17784, 17791, 17799, 17806, 17814, 17821, 17829, 17836, 17843, 17851, 17858, 17865, 17872],
922 [17879, 17893, 17906, 17920, 17933, 17946, 17958, 17971, 17984, 17996, 18008, 18020, 18032, 18043, 18055, 18066,
923 18077, 18088, 18099, 18110, 18121, 18131, 18142, 18152, 18162, 18172, 18182, 18192, 18202, 18211, 18221, 18230,
924 18239, 18249, 18258, 18267, 18276, 18285, 18293, 18302, 18311, 18319, 18328, 18336, 18344, 18352, 18360, 18369,
925 18377, 18384, 18392, 18400, 18408, 18415, 18423, 18430, 18438, 18445, 18453, 18460, 18467, 18474, 18481, 18488],
926 [18495, 18509, 18523, 18536, 18549, 18562, 18575, 18588, 18600, 18612, 18624, 18636, 18648, 18660, 18671, 18683,
927 18694, 18705, 18716, 18726, 18737, 18748, 18758, 18768, 18779, 18789, 18799, 18808, 18818, 18828, 18837, 18847,
928 18856, 18865, 18874, 18883, 18892, 18901, 18910, 18919, 18927, 18936, 18944, 18952, 18961, 18969, 18977, 18985,
929 18993, 19001, 19009, 19017, 19024, 19032, 19039, 19047, 19054, 19062, 19069, 19076, 19084, 19091, 19098, 19105],
930 [19112, 19126, 19139, 19153, 19166, 19179, 19191, 19204, 19217, 19229, 19241, 19253, 19265, 19276, 19288, 19299,
931 19310, 19321, 19332, 19343, 19354, 19364, 19375, 19385, 19395, 19405, 19415, 19425, 19435, 19444, 19454, 19463,
932 19472, 19482, 19491, 19500, 19509, 19518, 19526, 19535, 19544, 19552, 19561, 19569, 19577, 19585, 19594, 19602,
933 19610, 19617, 19625, 19633, 19641, 19648, 19656, 19663, 19671, 19678, 19686, 19693, 19700, 19707, 19714, 19721],
934 [19728, 19742, 19756, 19769, 19782, 19795, 19808, 19821, 19833, 19845, 19857, 19869, 19881, 19893, 19904, 19916,
935 19927, 19938, 19949, 19960, 19970, 19981, 19991, 20001, 20012, 20022, 20032, 20041, 20051, 20061, 20070, 20080,
936 20089, 20098, 20107, 20116, 20125, 20134, 20143, 20152, 20160, 20169, 20177, 20185, 20194, 20202, 20210, 20218,
937 20226, 20234, 20242, 20250, 20257, 20265, 20272, 20280, 20287, 20295, 20302, 20309, 20317, 20324, 20331, 20338],
938 [20345, 20359, 20372, 20386, 20399, 20412, 20425, 20437, 20450, 20462, 20474, 20486, 20498, 20509, 20521, 20532,
939 20543, 20554, 20565, 20576, 20587, 20597, 20608, 20618, 20628, 20638, 20648, 20658, 20668, 20677, 20687, 20696,
940 20705, 20715, 20724, 20733, 20742, 20751, 20759, 20768, 20777, 20785, 20794, 20802, 20810, 20818, 20827, 20835,
941 20843, 20850, 20858, 20866, 20874, 20881, 20889, 20896, 20904, 20911, 20919, 20926, 20933, 20940, 20947, 20954],
942 [20961, 20975, 20989, 21002, 21015, 21028, 21041, 21054, 21066, 21078, 21090, 21102, 21114, 21126, 21137, 21149,
943 21160, 21171, 21182, 21193, 21203, 21214, 21224, 21234, 21245, 21255, 21265, 21274, 21284, 21294, 21303, 21313,
944 21322, 21331, 21340, 21349, 21358, 21367, 21376, 21385, 21393, 21402, 21410, 21418, 21427, 21435, 21443, 21451,
945 21459, 21467, 21475, 21483, 21490, 21498, 21505, 21513, 21520, 21528, 21535, 21542, 21550, 21557, 21564, 21571],
946 [21578, 21592, 21605, 21619, 21632, 21645, 21658, 21670, 21683, 21695, 21707, 21719, 21731, 21742, 21754, 21765,
947 21776, 21787, 21798, 21809, 21820, 21830, 21841, 21851, 21861, 21871, 21881, 21891, 21901, 21910, 21920, 21929,
948 21938, 21948, 21957, 21966, 21975, 21984, 21992, 22001, 22010, 22018, 22027, 22035, 22043, 22051, 22060, 22068,
949 22076, 22083, 22091, 22099, 22107, 22114, 22122, 22129, 22137, 22144, 22152, 22159, 22166, 22173, 22180, 22187],
950 [22194, 22208, 22222, 22235, 22248, 22261, 22274, 22287, 22299, 22311, 22323, 22335, 22347, 22359, 22370, 22382,
951 22393, 22404, 22415, 22426, 22436, 22447, 22457, 22467, 22478, 22488, 22498, 22507, 22517, 22527, 22536, 22546,
952 22555, 22564, 22573, 22582, 22591, 22600, 22609, 22618, 22626, 22635, 22643, 22651, 22660, 22668, 22676, 22684,
953 22692, 22700, 22708, 22716, 22723, 22731, 22738, 22746, 22753, 22761, 22768, 22775, 22783, 22790, 22797, 22804],
954 [22811, 22825, 22838, 22852, 22865, 22878, 22891, 22903, 22916, 22928, 22940, 22952, 22964, 22975, 22987, 22998,
955 23009, 23020, 23031, 23042, 23053, 23063, 23074, 23084, 23094, 23104, 23114, 23124, 23134, 23143, 23153, 23162,
956 23171, 23181, 23190, 23199, 23208, 23217, 23225, 23234, 23243, 23251, 23260, 23268, 23276, 23284, 23293, 23301,
957 23309, 23316, 23324, 23332, 23340, 23347, 23355, 23363, 23370, 23377, 23385, 23392, 23399, 23406, 23413, 23420],
958 [23427, 23441, 23455, 23468, 23481, 23494, 23507, 23520, 23532, 23544, 23556, 23568, 23580, 23592, 23603, 23615,
959 23626, 23637, 23648, 23659, 23669, 23680, 23690, 23700, 23711, 23721, 23731, 23740, 23750, 23760, 23769, 23779,
960 23788, 23797, 23806, 23815, 23824, 23833, 23842, 23851, 23859, 23868, 23876, 23884, 23893, 23901, 23909, 23917,
961 23925, 23933, 23941, 23949, 23956, 23964, 23972, 23979, 23986, 23994, 24001, 24008, 24016, 24023, 24030, 24037],
962 [24044, 24058, 24071, 24085, 24098, 24111, 24124, 24136, 24149, 24161, 24173, 24185, 24197, 24208, 24220, 24231,
963 24242, 24253, 24264, 24275, 24286, 24296, 24307, 24317, 24327, 24337, 24347, 24357, 24367, 24376, 24386, 24395,
964 24405, 24414, 24423, 24432, 24441, 24450, 24458, 24467, 24476, 24484, 24493, 24501, 24509, 24517, 24526, 24534,
965 24542, 24550, 24557, 24565, 24573, 24580, 24588, 24596, 24603, 24610, 24618, 24625, 24632, 24639, 24646, 24653],
966 [24660, 24674, 24688, 24701, 24714, 24727, 24740, 24753, 24765, 24777, 24790, 24801, 24813, 24825, 24836, 24848,
967 24859, 24870, 24881, 24892, 24902, 24913, 24923, 24933, 24944, 24954, 24964, 24973, 24983, 24993, 25002, 25012,
968 25021, 25030, 25039, 25048, 25057, 25066, 25075, 25084, 25092, 25101, 25109, 25117, 25126, 25134, 25142, 25150,
969 25158, 25166, 25174, 25182, 25189, 25197, 25205, 25212, 25219, 25227, 25234, 25241, 25249, 25256, 25263, 25270],
970 [25277, 25291, 25304, 25318, 25331, 25344, 25357, 25369, 25382, 25394, 25406, 25418, 25430, 25441, 25453, 25464,
971 25475, 25486, 25497, 25508, 25519, 25529, 25540, 25550, 25560, 25570, 25580, 25590, 25600, 25609, 25619, 25628,
972 25638, 25647, 25656, 25665, 25674, 25683, 25691, 25700, 25709, 25717, 25726, 25734, 25742, 25750, 25759, 25767,
973 25775, 25783, 25790, 25798, 25806, 25813, 25821, 25829, 25836, 25843, 25851, 25858, 25865, 25872, 25879, 25886],
974 [25893, 25907, 25921, 25934, 25947, 25960, 25973, 25986, 25998, 26010, 26023, 26034, 26046, 26058, 26069, 26081,
975 26092, 26103, 26114, 26125, 26135, 26146, 26156, 26166, 26177, 26187, 26197, 26206, 26216, 26226, 26235, 26245,
976 26254, 26263, 26272, 26281, 26290, 26299, 26308, 26317, 26325, 26334, 26342, 26351, 26359, 26367, 26375, 26383,
977 26391, 26399, 26407, 26415, 26422, 26430, 26438, 26445, 26453, 26460, 26467, 26474, 26482, 26489, 26496, 26503],
978 [26510, 26524, 26537, 26551, 26564, 26577, 26590, 26602, 26615, 26627, 26639, 26651, 26663, 26674, 26686, 26697,
979 26708, 26719, 26730, 26741, 26752, 26762, 26773, 26783, 26793, 26803, 26813, 26823, 26833, 26842, 26852, 26861,
980 26871, 26880, 26889, 26898, 26907, 26916, 26924, 26933, 26942, 26950, 26959, 26967, 26975, 26983, 26992, 27000,
981 27008, 27016, 27023, 27031, 27039, 27046, 27054, 27062, 27069, 27076, 27084, 27091, 27098, 27105, 27112, 27119],
982 [27126, 27140, 27154, 27167, 27180, 27193, 27206, 27219, 27231, 27243, 27256, 27267, 27279, 27291, 27302, 27314,
983 27325, 27336, 27347, 27358, 27368, 27379, 27389, 27399, 27410, 27420, 27430, 27439, 27449, 27459, 27468, 27478,
984 27487, 27496, 27505, 27514, 27523, 27532, 27541, 27550, 27558, 27567, 27575, 27584, 27592, 27600, 27608, 27616,
985 27624, 27632, 27640, 27648, 27655, 27663, 27671, 27678, 27686, 27693, 27700, 27707, 27715, 27722, 27729, 27736],
986 [27743, 27757, 27770, 27784, 27797, 27810, 27823, 27835, 27848, 27860, 27872, 27884, 27896, 27907, 27919, 27930,
987 27941, 27952, 27963, 27974, 27985, 27995, 28006, 28016, 28026, 28036, 28046, 28056, 28066, 28075, 28085, 28094,
988 28104, 28113, 28122, 28131, 28140, 28149, 28157, 28166, 28175, 28183, 28192, 28200, 28208, 28217, 28225, 28233,
989 28241, 28249, 28256, 28264, 28272, 28280, 28287, 28295, 28302, 28309, 28317, 28324, 28331, 28338, 28345, 28352],
990 [28359, 28373, 28387, 28400, 28413, 28426, 28439, 28452, 28464, 28476, 28489, 28501, 28512, 28524, 28535, 28547,
991 28558, 28569, 28580, 28591, 28601, 28612, 28622, 28633, 28643, 28653, 28663, 28672, 28682, 28692, 28701, 28711,
992 28720, 28729, 28738, 28747, 28756, 28765, 28774, 28783, 28791, 28800, 28808, 28817, 28825, 28833, 28841, 28849,
993 28857, 28865, 28873, 28881, 28888, 28896, 28904, 28911, 28919, 28926, 28933, 28941, 28948, 28955, 28962, 28969],
994 [28976, 28990, 29003, 29017, 29030, 29043, 29056, 29068, 29081, 29093, 29105, 29117, 29129, 29140, 29152, 29163,
995 29174, 29185, 29196, 29207, 29218, 29228, 29239, 29249, 29259, 29269, 29279, 29289, 29299, 29308, 29318, 29327,
996 29337, 29346, 29355, 29364, 29373, 29382, 29390, 29399, 29408, 29416, 29425, 29433, 29441, 29450, 29458, 29466,
997 29474, 29482, 29489, 29497, 29505, 29513, 29520, 29528, 29535, 29542, 29550, 29557, 29564, 29571, 29578, 29585],
998 [29592, 29606, 29620, 29633, 29646, 29659, 29672, 29685, 29697, 29709, 29722, 29734, 29745, 29757, 29768, 29780,
999 29791, 29802, 29813, 29824, 29834, 29845, 29855, 29866, 29876, 29886, 29896, 29906, 29915, 29925, 29934, 29944,
1000 29953, 29962, 29971, 29980, 29989, 29998, 30007, 30016, 30024, 30033, 30041, 30050, 30058, 30066, 30074, 30082,
1001 30090, 30098, 30106, 30114, 30121, 30129, 30137, 30144, 30152, 30159, 30166, 30174, 30181, 30188, 30195, 30202],
1002 [30209, 30223, 30236, 30250, 30263, 30276, 30289, 30301, 30314, 30326, 30338, 30350, 30362, 30373, 30385, 30396,
1003 30407, 30418, 30429, 30440, 30451, 30461, 30472, 30482, 30492, 30502, 30512, 30522, 30532, 30541, 30551, 30560,
1004 30570, 30579, 30588, 30597, 30606, 30615, 30624, 30632, 30641, 30649, 30658, 30666, 30674, 30683, 30691, 30699,
1005 30707, 30715, 30722, 30730, 30738, 30746, 30753, 30761, 30768, 30775, 30783, 30790, 30797, 30804, 30811, 30818],
1006 [30825, 30839, 30853, 30866, 30879, 30892, 30905, 30918, 30930, 30943, 30955, 30967, 30978, 30990, 31001, 31013,
1007 31024, 31035, 31046, 31057, 31067, 31078, 31088, 31099, 31109, 31119, 31129, 31139, 31148, 31158, 31167, 31177,
1008 31186, 31195, 31204, 31213, 31222, 31231, 31240, 31249, 31257, 31266, 31274, 31283, 31291, 31299, 31307, 31315,
1009 31323, 31331, 31339, 31347, 31354, 31362, 31370, 31377, 31385, 31392, 31399, 31407, 31414, 31421, 31428, 31435],
1010 [31442, 31456, 31469, 31483, 31496, 31509, 31522, 31534, 31547, 31559, 31571, 31583, 31595, 31606, 31618, 31629,
1011 31640, 31652, 31662, 31673, 31684, 31694, 31705, 31715, 31725, 31735, 31745, 31755, 31765, 31774, 31784, 31793,
1012 31803, 31812, 31821, 31830, 31839, 31848, 31857, 31865, 31874, 31882, 31891, 31899, 31907, 31916, 31924, 31932,
1013 31940, 31948, 31955, 31963, 31971, 31979, 31986, 31994, 32001, 32008, 32016, 32023, 32030, 32037, 32044, 32052],
1014 [32058, 32072, 32086, 32099, 32112, 32125, 32138, 32151, 32163, 32176, 32188, 32200, 32211, 32223, 32234, 32246,
1015 32257, 32268, 32279, 32290, 32300, 32311, 32321, 32332, 32342, 32352, 32362, 32372, 32381, 32391, 32400, 32410,
1016 32419, 32428, 32437, 32446, 32455, 32464, 32473, 32482, 32490, 32499, 32507, 32516, 32524, 32532, 32540, 32548,
1017 32556, 32564, 32572, 32580, 32587, 32595, 32603, 32610, 32618, 32625, 32632, 32640, 32647, 32654, 32661, 32668],
1018 [32675, 32689, 32702, 32716, 32729, 32742, 32755, 32767, 32780, 32792, 32804, 32816, 32828, 32839, 32851, 32862,
1019 32873, 32885, 32895, 32906, 32917, 32927, 32938, 32948, 32958, 32968, 32978, 32988, 32998, 33007, 33017, 33026,
1020 33036, 33045, 33054, 33063, 33072, 33081, 33090, 33098, 33107, 33115, 33124, 33132, 33140, 33149, 33157, 33165,
1021 33173, 33181, 33188, 33196, 33204, 33212, 33219, 33227, 33234, 33241, 33249, 33256, 33263, 33270, 33278, 33285],
1022 [33292, 33305, 33319, 33332, 33345, 33358, 33371, 33384, 33396, 33409, 33421, 33433, 33444, 33456, 33467, 33479,
1023 33490, 33501, 33512, 33523, 33533, 33544, 33554, 33565, 33575, 33585, 33595, 33605, 33614, 33624, 33633, 33643,
1024 33652, 33661, 33670, 33680, 33688, 33697, 33706, 33715, 33723, 33732, 33740, 33749, 33757, 33765, 33773, 33781,
1025 33789, 33797, 33805, 33813, 33820, 33828, 33836, 33843, 33851, 33858, 33865, 33873, 33880, 33887, 33894, 33901],
1026 [33908, 33922, 33935, 33949, 33962, 33975, 33988, 34000, 34013, 34025, 34037, 34049, 34061, 34072, 34084, 34095,
1027 34106, 34118, 34128, 34139, 34150, 34160, 34171, 34181, 34191, 34201, 34211, 34221, 34231, 34240, 34250, 34259,
1028 34269, 34278, 34287, 34296, 34305, 34314, 34323, 34331, 34340, 34348, 34357, 34365, 34373, 34382, 34390, 34398,
1029 34406, 34414, 34422, 34429, 34437, 34445, 34452, 34460, 34467, 34475, 34482, 34489, 34496, 34503, 34511, 34518],
1030 [34525, 34538, 34552, 34565, 34578, 34591, 34604, 34617, 34629, 34642, 34654, 34666, 34677, 34689, 34700, 34712,
1031 34723, 34734, 34745, 34756, 34766, 34777, 34787, 34798, 34808, 34818, 34828, 34838, 34847, 34857, 34866, 34876,
1032 34885, 34894, 34904, 34913, 34921, 34930, 34939, 34948, 34956, 34965, 34973, 34982, 34990, 34998, 35006, 35014,
1033 35022, 35030, 35038, 35046, 35053, 35061, 35069, 35076, 35084, 35091, 35098, 35106, 35113, 35120, 35127, 35134],
1034 [35141, 35155, 35168, 35182, 35195, 35208, 35221, 35233, 35246, 35258, 35270, 35282, 35294, 35306, 35317, 35328,
1035 35340, 35351, 35361, 35372, 35383, 35393, 35404, 35414, 35424, 35434, 35444, 35454, 35464, 35473, 35483, 35492,
1036 35502, 35511, 35520, 35529, 35538, 35547, 35556, 35564, 35573, 35581, 35590, 35598, 35606, 35615, 35623, 35631,
1037 35639, 35647, 35655, 35662, 35670, 35678, 35685, 35693, 35700, 35708, 35715, 35722, 35729, 35736, 35744, 35751],
1038 [35758, 35771, 35785, 35798, 35811, 35824, 35837, 35850, 35862, 35875, 35887, 35899, 35910, 35922, 35934, 35945,
1039 35956, 35967, 35978, 35989, 35999, 36010, 36020, 36031, 36041, 36051, 36061, 36071, 36080, 36090, 36099, 36109,
1040 36118, 36127, 36137, 36146, 36154, 36163, 36172, 36181, 36189, 36198, 36206, 36215, 36223, 36231, 36239, 36247,
1041 36255, 36263, 36271, 36279, 36287, 36294, 36302, 36309, 36317, 36324, 36331, 36339, 36346, 36353, 36360, 36367],
1042 [36374, 36388, 36401, 36415, 36428, 36441, 36454, 36466, 36479, 36491, 36503, 36515, 36527, 36539, 36550, 36561,
1043 36573, 36584, 36594, 36605, 36616, 36626, 36637, 36647, 36657, 36667, 36677, 36687, 36697, 36706, 36716, 36725,
1044 36735, 36744, 36753, 36762, 36771, 36780, 36789, 36797, 36806, 36814, 36823, 36831, 36839, 36848, 36856, 36864,
1045 36872, 36880, 36888, 36895, 36903, 36911, 36918, 36926, 36933, 36941, 36948, 36955, 36962, 36969, 36977, 36984],
1046 [36991, 37004, 37018, 37031, 37044, 37057, 37070, 37083, 37095, 37108, 37120, 37132, 37143, 37155, 37167, 37178,
1047 37189, 37200, 37211, 37222, 37232, 37243, 37253, 37264, 37274, 37284, 37294, 37304, 37313, 37323, 37332, 37342,
1048 37351, 37360, 37370, 37379, 37388, 37396, 37405, 37414, 37422, 37431, 37439, 37448, 37456, 37464, 37472, 37480,
1049 37488, 37496, 37504, 37512, 37520, 37527, 37535, 37542, 37550, 37557, 37564, 37572, 37579, 37586, 37593, 37600],
1050 [37607, 37621, 37634, 37648, 37661, 37674, 37687, 37699, 37712, 37724, 37736, 37748, 37760, 37772, 37783, 37794,
1051 37806, 37817, 37828, 37838, 37849, 37859, 37870, 37880, 37890, 37900, 37910, 37920, 37930, 37939, 37949, 37958,
1052 37968, 37977, 37986, 37995, 38004, 38013, 38022, 38030, 38039, 38047, 38056, 38064, 38072, 38081, 38089, 38097,
1053 38105, 38113, 38121, 38128, 38136, 38144, 38151, 38159, 38166, 38174, 38181, 38188, 38195, 38202, 38210, 38217],
1054 [38224, 38237, 38251, 38264, 38278, 38290, 38303, 38316, 38328, 38341, 38353, 38365, 38376, 38388, 38400, 38411,
1055 38422, 38433, 38444, 38455, 38465, 38476, 38486, 38497, 38507, 38517, 38527, 38537, 38546, 38556, 38565, 38575,
1056 38584, 38593, 38603, 38612, 38621, 38629, 38638, 38647, 38655, 38664, 38672, 38681, 38689, 38697, 38705, 38713,
1057 38721, 38729, 38737, 38745, 38753, 38760, 38768, 38775, 38783, 38790, 38797, 38805, 38812, 38819, 38826, 38833],
1058 [38840, 38854, 38867, 38881, 38894, 38907, 38920, 38932, 38945, 38957, 38969, 38981, 38993, 39005, 39016, 39027,
1059 39039, 39050, 39061, 39071, 39082, 39092, 39103, 39113, 39123, 39133, 39143, 39153, 39163, 39172, 39182, 39191,
1060 39201, 39210, 39219, 39228, 39237, 39246, 39255, 39263, 39272, 39280, 39289, 39297, 39305, 39314, 39322, 39330,
1061 39338, 39346, 39354, 39361, 39369, 39377, 39384, 39392, 39399, 39407, 39414, 39421, 39428, 39436, 39443, 39450],
1064 /// Approximate `log10(numerator / denominator) * 2048` using a look-up table.
1066 pub fn negative_log10_times_2048(numerator: u64, denominator: u64) -> u64 {
1067 // Multiply the -1 through to avoid needing to use signed numbers.
1068 (log10_times_2048(denominator) - log10_times_2048(numerator)) as u64
1072 fn log10_times_2048(x: u64) -> u16 {
1073 debug_assert_ne!(x, 0);
1074 let most_significant_bit = HIGHEST_BIT - x.leading_zeros();
1075 let lower_bits = (x >> most_significant_bit.saturating_sub(LOWER_BITS)) & LOWER_BITMASK;
1076 LOG10_TIMES_2048[most_significant_bit as usize][lower_bits as usize]
1084 fn prints_negative_log10_times_2048_lookup_table() {
1085 for msb in 0..BITS {
1086 for i in 0..LOWER_BITS_BOUND {
1087 let x = ((LOWER_BITS_BOUND + i) << (HIGHEST_BIT - LOWER_BITS)) >> (HIGHEST_BIT - msb);
1088 let log10_times_2048 = ((x as f64).log10() * 2048.0).round() as u16;
1089 assert_eq!(log10_times_2048, LOG10_TIMES_2048[msb as usize][i as usize]);
1091 if i % LOWER_BITS_BOUND == 0 {
1092 print!("\t\t[{}, ", log10_times_2048);
1093 } else if i % LOWER_BITS_BOUND == LOWER_BITS_BOUND - 1 {
1094 println!("{}],", log10_times_2048);
1095 } else if i % (LOWER_BITS_BOUND/4) == LOWER_BITS_BOUND/4 - 1 {
1096 print!("{},\n\t\t\t", log10_times_2048);
1098 print!("{}, ", log10_times_2048);
1106 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Writeable for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1108 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
1109 write_tlv_fields!(w, {
1110 (0, self.channel_liquidities, required),
1116 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time>
1117 ReadableArgs<(ProbabilisticScoringParameters, G, L)> for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1120 r: &mut R, args: (ProbabilisticScoringParameters, G, L)
1121 ) -> Result<Self, DecodeError> {
1122 let (params, network_graph, logger) = args;
1123 let mut channel_liquidities = HashMap::new();
1124 read_tlv_fields!(r, {
1125 (0, channel_liquidities, required),
1131 channel_liquidities,
1136 impl<T: Time> Writeable for ChannelLiquidity<T> {
1138 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
1139 let duration_since_epoch = T::duration_since_epoch() - self.last_updated.elapsed();
1140 write_tlv_fields!(w, {
1141 (0, self.min_liquidity_offset_msat, required),
1142 (2, self.max_liquidity_offset_msat, required),
1143 (4, duration_since_epoch, required),
1149 impl<T: Time> Readable for ChannelLiquidity<T> {
1151 fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
1152 let mut min_liquidity_offset_msat = 0;
1153 let mut max_liquidity_offset_msat = 0;
1154 let mut duration_since_epoch = Duration::from_secs(0);
1155 read_tlv_fields!(r, {
1156 (0, min_liquidity_offset_msat, required),
1157 (2, max_liquidity_offset_msat, required),
1158 (4, duration_since_epoch, required),
1161 min_liquidity_offset_msat,
1162 max_liquidity_offset_msat,
1163 last_updated: T::now() - (T::duration_since_epoch() - duration_since_epoch),
1170 use super::{ChannelLiquidity, ProbabilisticScoringParameters, ProbabilisticScorerUsingTime};
1171 use util::time::Time;
1172 use util::time::tests::SinceEpoch;
1174 use ln::features::{ChannelFeatures, NodeFeatures};
1175 use ln::msgs::{ChannelAnnouncement, ChannelUpdate, OptionalField, UnsignedChannelAnnouncement, UnsignedChannelUpdate};
1176 use routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId};
1177 use routing::router::RouteHop;
1178 use routing::scoring::{ChannelUsage, Score};
1179 use util::ser::{ReadableArgs, Writeable};
1180 use util::test_utils::TestLogger;
1182 use bitcoin::blockdata::constants::genesis_block;
1183 use bitcoin::hashes::Hash;
1184 use bitcoin::hashes::sha256d::Hash as Sha256dHash;
1185 use bitcoin::network::constants::Network;
1186 use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey};
1187 use core::time::Duration;
1190 fn source_privkey() -> SecretKey {
1191 SecretKey::from_slice(&[42; 32]).unwrap()
1194 fn target_privkey() -> SecretKey {
1195 SecretKey::from_slice(&[43; 32]).unwrap()
1198 fn source_pubkey() -> PublicKey {
1199 let secp_ctx = Secp256k1::new();
1200 PublicKey::from_secret_key(&secp_ctx, &source_privkey())
1203 fn target_pubkey() -> PublicKey {
1204 let secp_ctx = Secp256k1::new();
1205 PublicKey::from_secret_key(&secp_ctx, &target_privkey())
1208 fn source_node_id() -> NodeId {
1209 NodeId::from_pubkey(&source_pubkey())
1212 fn target_node_id() -> NodeId {
1213 NodeId::from_pubkey(&target_pubkey())
1216 // `ProbabilisticScorer` tests
1218 /// A probabilistic scorer for testing with time that can be manually advanced.
1219 type ProbabilisticScorer<'a> = ProbabilisticScorerUsingTime::<&'a NetworkGraph<&'a TestLogger>, &'a TestLogger, SinceEpoch>;
1221 fn sender_privkey() -> SecretKey {
1222 SecretKey::from_slice(&[41; 32]).unwrap()
1225 fn recipient_privkey() -> SecretKey {
1226 SecretKey::from_slice(&[45; 32]).unwrap()
1229 fn sender_pubkey() -> PublicKey {
1230 let secp_ctx = Secp256k1::new();
1231 PublicKey::from_secret_key(&secp_ctx, &sender_privkey())
1234 fn recipient_pubkey() -> PublicKey {
1235 let secp_ctx = Secp256k1::new();
1236 PublicKey::from_secret_key(&secp_ctx, &recipient_privkey())
1239 fn sender_node_id() -> NodeId {
1240 NodeId::from_pubkey(&sender_pubkey())
1243 fn recipient_node_id() -> NodeId {
1244 NodeId::from_pubkey(&recipient_pubkey())
1247 fn network_graph(logger: &TestLogger) -> NetworkGraph<&TestLogger> {
1248 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1249 let mut network_graph = NetworkGraph::new(genesis_hash, logger);
1250 add_channel(&mut network_graph, 42, source_privkey(), target_privkey());
1251 add_channel(&mut network_graph, 43, target_privkey(), recipient_privkey());
1257 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_1_key: SecretKey,
1258 node_2_key: SecretKey
1260 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1261 let node_1_secret = &SecretKey::from_slice(&[39; 32]).unwrap();
1262 let node_2_secret = &SecretKey::from_slice(&[40; 32]).unwrap();
1263 let secp_ctx = Secp256k1::new();
1264 let unsigned_announcement = UnsignedChannelAnnouncement {
1265 features: ChannelFeatures::known(),
1266 chain_hash: genesis_hash,
1268 node_id_1: PublicKey::from_secret_key(&secp_ctx, &node_1_key),
1269 node_id_2: PublicKey::from_secret_key(&secp_ctx, &node_2_key),
1270 bitcoin_key_1: PublicKey::from_secret_key(&secp_ctx, &node_1_secret),
1271 bitcoin_key_2: PublicKey::from_secret_key(&secp_ctx, &node_2_secret),
1272 excess_data: Vec::new(),
1274 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
1275 let signed_announcement = ChannelAnnouncement {
1276 node_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_key),
1277 node_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_key),
1278 bitcoin_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_secret),
1279 bitcoin_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_secret),
1280 contents: unsigned_announcement,
1282 let chain_source: Option<&::util::test_utils::TestChainSource> = None;
1283 network_graph.update_channel_from_announcement(
1284 &signed_announcement, &chain_source).unwrap();
1285 update_channel(network_graph, short_channel_id, node_1_key, 0);
1286 update_channel(network_graph, short_channel_id, node_2_key, 1);
1290 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_key: SecretKey,
1293 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1294 let secp_ctx = Secp256k1::new();
1295 let unsigned_update = UnsignedChannelUpdate {
1296 chain_hash: genesis_hash,
1300 cltv_expiry_delta: 18,
1301 htlc_minimum_msat: 0,
1302 htlc_maximum_msat: OptionalField::Present(1_000),
1304 fee_proportional_millionths: 0,
1305 excess_data: Vec::new(),
1307 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_update.encode()[..])[..]);
1308 let signed_update = ChannelUpdate {
1309 signature: secp_ctx.sign_ecdsa(&msghash, &node_key),
1310 contents: unsigned_update,
1312 network_graph.update_channel(&signed_update).unwrap();
1315 fn payment_path_for_amount(amount_msat: u64) -> Vec<RouteHop> {
1318 pubkey: source_pubkey(),
1319 node_features: NodeFeatures::known(),
1320 short_channel_id: 41,
1321 channel_features: ChannelFeatures::known(),
1323 cltv_expiry_delta: 18,
1326 pubkey: target_pubkey(),
1327 node_features: NodeFeatures::known(),
1328 short_channel_id: 42,
1329 channel_features: ChannelFeatures::known(),
1331 cltv_expiry_delta: 18,
1334 pubkey: recipient_pubkey(),
1335 node_features: NodeFeatures::known(),
1336 short_channel_id: 43,
1337 channel_features: ChannelFeatures::known(),
1338 fee_msat: amount_msat,
1339 cltv_expiry_delta: 18,
1345 fn liquidity_bounds_directed_from_lowest_node_id() {
1346 let logger = TestLogger::new();
1347 let last_updated = SinceEpoch::now();
1348 let network_graph = network_graph(&logger);
1349 let params = ProbabilisticScoringParameters::default();
1350 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1353 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated
1357 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated
1359 let source = source_node_id();
1360 let target = target_node_id();
1361 let recipient = recipient_node_id();
1362 assert!(source > target);
1363 assert!(target < recipient);
1365 // Update minimum liquidity.
1367 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
1368 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1369 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1370 assert_eq!(liquidity.min_liquidity_msat(), 100);
1371 assert_eq!(liquidity.max_liquidity_msat(), 300);
1373 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1374 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1375 assert_eq!(liquidity.min_liquidity_msat(), 700);
1376 assert_eq!(liquidity.max_liquidity_msat(), 900);
1378 scorer.channel_liquidities.get_mut(&42).unwrap()
1379 .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
1380 .set_min_liquidity_msat(200);
1382 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1383 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1384 assert_eq!(liquidity.min_liquidity_msat(), 200);
1385 assert_eq!(liquidity.max_liquidity_msat(), 300);
1387 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1388 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1389 assert_eq!(liquidity.min_liquidity_msat(), 700);
1390 assert_eq!(liquidity.max_liquidity_msat(), 800);
1392 // Update maximum liquidity.
1394 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1395 .as_directed(&target, &recipient, 1_000, liquidity_offset_half_life);
1396 assert_eq!(liquidity.min_liquidity_msat(), 700);
1397 assert_eq!(liquidity.max_liquidity_msat(), 900);
1399 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1400 .as_directed(&recipient, &target, 1_000, liquidity_offset_half_life);
1401 assert_eq!(liquidity.min_liquidity_msat(), 100);
1402 assert_eq!(liquidity.max_liquidity_msat(), 300);
1404 scorer.channel_liquidities.get_mut(&43).unwrap()
1405 .as_directed_mut(&target, &recipient, 1_000, liquidity_offset_half_life)
1406 .set_max_liquidity_msat(200);
1408 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1409 .as_directed(&target, &recipient, 1_000, liquidity_offset_half_life);
1410 assert_eq!(liquidity.min_liquidity_msat(), 0);
1411 assert_eq!(liquidity.max_liquidity_msat(), 200);
1413 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1414 .as_directed(&recipient, &target, 1_000, liquidity_offset_half_life);
1415 assert_eq!(liquidity.min_liquidity_msat(), 800);
1416 assert_eq!(liquidity.max_liquidity_msat(), 1000);
1420 fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() {
1421 let logger = TestLogger::new();
1422 let last_updated = SinceEpoch::now();
1423 let network_graph = network_graph(&logger);
1424 let params = ProbabilisticScoringParameters::default();
1425 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1428 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated
1430 let source = source_node_id();
1431 let target = target_node_id();
1432 assert!(source > target);
1434 // Check initial bounds.
1435 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
1436 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1437 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1438 assert_eq!(liquidity.min_liquidity_msat(), 400);
1439 assert_eq!(liquidity.max_liquidity_msat(), 800);
1441 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1442 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1443 assert_eq!(liquidity.min_liquidity_msat(), 200);
1444 assert_eq!(liquidity.max_liquidity_msat(), 600);
1446 // Reset from source to target.
1447 scorer.channel_liquidities.get_mut(&42).unwrap()
1448 .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
1449 .set_min_liquidity_msat(900);
1451 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1452 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1453 assert_eq!(liquidity.min_liquidity_msat(), 900);
1454 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1456 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1457 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1458 assert_eq!(liquidity.min_liquidity_msat(), 0);
1459 assert_eq!(liquidity.max_liquidity_msat(), 100);
1461 // Reset from target to source.
1462 scorer.channel_liquidities.get_mut(&42).unwrap()
1463 .as_directed_mut(&target, &source, 1_000, liquidity_offset_half_life)
1464 .set_min_liquidity_msat(400);
1466 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1467 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1468 assert_eq!(liquidity.min_liquidity_msat(), 0);
1469 assert_eq!(liquidity.max_liquidity_msat(), 600);
1471 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1472 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1473 assert_eq!(liquidity.min_liquidity_msat(), 400);
1474 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1478 fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() {
1479 let logger = TestLogger::new();
1480 let last_updated = SinceEpoch::now();
1481 let network_graph = network_graph(&logger);
1482 let params = ProbabilisticScoringParameters::default();
1483 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1486 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated
1488 let source = source_node_id();
1489 let target = target_node_id();
1490 assert!(source > target);
1492 // Check initial bounds.
1493 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
1494 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1495 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1496 assert_eq!(liquidity.min_liquidity_msat(), 400);
1497 assert_eq!(liquidity.max_liquidity_msat(), 800);
1499 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1500 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1501 assert_eq!(liquidity.min_liquidity_msat(), 200);
1502 assert_eq!(liquidity.max_liquidity_msat(), 600);
1504 // Reset from source to target.
1505 scorer.channel_liquidities.get_mut(&42).unwrap()
1506 .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
1507 .set_max_liquidity_msat(300);
1509 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1510 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1511 assert_eq!(liquidity.min_liquidity_msat(), 0);
1512 assert_eq!(liquidity.max_liquidity_msat(), 300);
1514 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1515 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1516 assert_eq!(liquidity.min_liquidity_msat(), 700);
1517 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1519 // Reset from target to source.
1520 scorer.channel_liquidities.get_mut(&42).unwrap()
1521 .as_directed_mut(&target, &source, 1_000, liquidity_offset_half_life)
1522 .set_max_liquidity_msat(600);
1524 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1525 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1526 assert_eq!(liquidity.min_liquidity_msat(), 400);
1527 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1529 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1530 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1531 assert_eq!(liquidity.min_liquidity_msat(), 0);
1532 assert_eq!(liquidity.max_liquidity_msat(), 600);
1536 fn increased_penalty_nearing_liquidity_upper_bound() {
1537 let logger = TestLogger::new();
1538 let network_graph = network_graph(&logger);
1539 let params = ProbabilisticScoringParameters {
1540 liquidity_penalty_multiplier_msat: 1_000,
1541 ..ProbabilisticScoringParameters::zero_penalty()
1543 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1544 let source = source_node_id();
1545 let target = target_node_id();
1547 let usage = ChannelUsage {
1549 inflight_htlc_msat: 0,
1550 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000 },
1552 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1553 let usage = ChannelUsage { amount_msat: 10_240, ..usage };
1554 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1555 let usage = ChannelUsage { amount_msat: 102_400, ..usage };
1556 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 47);
1557 let usage = ChannelUsage { amount_msat: 1_024_000, ..usage };
1558 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
1560 let usage = ChannelUsage {
1562 inflight_htlc_msat: 0,
1563 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024 },
1565 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 58);
1566 let usage = ChannelUsage { amount_msat: 256, ..usage };
1567 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
1568 let usage = ChannelUsage { amount_msat: 374, ..usage };
1569 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 198);
1570 let usage = ChannelUsage { amount_msat: 512, ..usage };
1571 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1572 let usage = ChannelUsage { amount_msat: 640, ..usage };
1573 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 425);
1574 let usage = ChannelUsage { amount_msat: 768, ..usage };
1575 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 602);
1576 let usage = ChannelUsage { amount_msat: 896, ..usage };
1577 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 902);
1581 fn constant_penalty_outside_liquidity_bounds() {
1582 let logger = TestLogger::new();
1583 let last_updated = SinceEpoch::now();
1584 let network_graph = network_graph(&logger);
1585 let params = ProbabilisticScoringParameters {
1586 liquidity_penalty_multiplier_msat: 1_000,
1587 ..ProbabilisticScoringParameters::zero_penalty()
1589 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1592 min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40, last_updated
1594 let source = source_node_id();
1595 let target = target_node_id();
1597 let usage = ChannelUsage {
1599 inflight_htlc_msat: 0,
1600 effective_capacity: EffectiveCapacity::Total { capacity_msat: 100 },
1602 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1603 let usage = ChannelUsage { amount_msat: 50, ..usage };
1604 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1605 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1606 let usage = ChannelUsage { amount_msat: 61, ..usage };
1607 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1611 fn does_not_further_penalize_own_channel() {
1612 let logger = TestLogger::new();
1613 let network_graph = network_graph(&logger);
1614 let params = ProbabilisticScoringParameters {
1615 liquidity_penalty_multiplier_msat: 1_000,
1616 ..ProbabilisticScoringParameters::zero_penalty()
1618 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1619 let sender = sender_node_id();
1620 let source = source_node_id();
1621 let usage = ChannelUsage {
1623 inflight_htlc_msat: 0,
1624 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000 },
1626 let failed_path = payment_path_for_amount(500);
1627 let successful_path = payment_path_for_amount(200);
1629 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 301);
1631 scorer.payment_path_failed(&failed_path.iter().collect::<Vec<_>>(), 41);
1632 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 301);
1634 scorer.payment_path_successful(&successful_path.iter().collect::<Vec<_>>());
1635 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 301);
1639 fn sets_liquidity_lower_bound_on_downstream_failure() {
1640 let logger = TestLogger::new();
1641 let network_graph = network_graph(&logger);
1642 let params = ProbabilisticScoringParameters {
1643 liquidity_penalty_multiplier_msat: 1_000,
1644 ..ProbabilisticScoringParameters::zero_penalty()
1646 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1647 let source = source_node_id();
1648 let target = target_node_id();
1649 let path = payment_path_for_amount(500);
1651 let usage = ChannelUsage {
1653 inflight_htlc_msat: 0,
1654 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000 },
1656 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 128);
1657 let usage = ChannelUsage { amount_msat: 500, ..usage };
1658 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 301);
1659 let usage = ChannelUsage { amount_msat: 750, ..usage };
1660 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 602);
1662 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 43);
1664 let usage = ChannelUsage { amount_msat: 250, ..usage };
1665 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1666 let usage = ChannelUsage { amount_msat: 500, ..usage };
1667 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1668 let usage = ChannelUsage { amount_msat: 750, ..usage };
1669 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1673 fn sets_liquidity_upper_bound_on_failure() {
1674 let logger = TestLogger::new();
1675 let network_graph = network_graph(&logger);
1676 let params = ProbabilisticScoringParameters {
1677 liquidity_penalty_multiplier_msat: 1_000,
1678 ..ProbabilisticScoringParameters::zero_penalty()
1680 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1681 let source = source_node_id();
1682 let target = target_node_id();
1683 let path = payment_path_for_amount(500);
1685 let usage = ChannelUsage {
1687 inflight_htlc_msat: 0,
1688 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000 },
1690 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 128);
1691 let usage = ChannelUsage { amount_msat: 500, ..usage };
1692 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 301);
1693 let usage = ChannelUsage { amount_msat: 750, ..usage };
1694 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 602);
1696 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 42);
1698 let usage = ChannelUsage { amount_msat: 250, ..usage };
1699 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1700 let usage = ChannelUsage { amount_msat: 500, ..usage };
1701 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1702 let usage = ChannelUsage { amount_msat: 750, ..usage };
1703 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1707 fn reduces_liquidity_upper_bound_along_path_on_success() {
1708 let logger = TestLogger::new();
1709 let network_graph = network_graph(&logger);
1710 let params = ProbabilisticScoringParameters {
1711 liquidity_penalty_multiplier_msat: 1_000,
1712 ..ProbabilisticScoringParameters::zero_penalty()
1714 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1715 let sender = sender_node_id();
1716 let source = source_node_id();
1717 let target = target_node_id();
1718 let recipient = recipient_node_id();
1719 let usage = ChannelUsage {
1721 inflight_htlc_msat: 0,
1722 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000 },
1724 let path = payment_path_for_amount(500);
1726 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 128);
1727 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 128);
1728 assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage), 128);
1730 scorer.payment_path_successful(&path.iter().collect::<Vec<_>>());
1732 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 128);
1733 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1734 assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage), 300);
1738 fn decays_liquidity_bounds_over_time() {
1739 let logger = TestLogger::new();
1740 let network_graph = network_graph(&logger);
1741 let params = ProbabilisticScoringParameters {
1742 liquidity_penalty_multiplier_msat: 1_000,
1743 liquidity_offset_half_life: Duration::from_secs(10),
1744 ..ProbabilisticScoringParameters::zero_penalty()
1746 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1747 let source = source_node_id();
1748 let target = target_node_id();
1750 let usage = ChannelUsage {
1752 inflight_htlc_msat: 0,
1753 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024 },
1755 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1756 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
1757 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
1759 scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::<Vec<_>>(), 42);
1760 scorer.payment_path_failed(&payment_path_for_amount(128).iter().collect::<Vec<_>>(), 43);
1762 let usage = ChannelUsage { amount_msat: 128, ..usage };
1763 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1764 let usage = ChannelUsage { amount_msat: 256, ..usage };
1765 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 93);
1766 let usage = ChannelUsage { amount_msat: 768, ..usage };
1767 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1_479);
1768 let usage = ChannelUsage { amount_msat: 896, ..usage };
1769 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1771 SinceEpoch::advance(Duration::from_secs(9));
1772 let usage = ChannelUsage { amount_msat: 128, ..usage };
1773 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1774 let usage = ChannelUsage { amount_msat: 256, ..usage };
1775 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 93);
1776 let usage = ChannelUsage { amount_msat: 768, ..usage };
1777 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1_479);
1778 let usage = ChannelUsage { amount_msat: 896, ..usage };
1779 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1781 SinceEpoch::advance(Duration::from_secs(1));
1782 let usage = ChannelUsage { amount_msat: 64, ..usage };
1783 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1784 let usage = ChannelUsage { amount_msat: 128, ..usage };
1785 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 34);
1786 let usage = ChannelUsage { amount_msat: 896, ..usage };
1787 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1_970);
1788 let usage = ChannelUsage { amount_msat: 960, ..usage };
1789 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1791 // Fully decay liquidity lower bound.
1792 SinceEpoch::advance(Duration::from_secs(10 * 7));
1793 let usage = ChannelUsage { amount_msat: 0, ..usage };
1794 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1795 let usage = ChannelUsage { amount_msat: 1, ..usage };
1796 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1797 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
1798 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
1799 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
1800 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
1802 // Fully decay liquidity upper bound.
1803 SinceEpoch::advance(Duration::from_secs(10));
1804 let usage = ChannelUsage { amount_msat: 0, ..usage };
1805 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1806 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
1807 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
1809 SinceEpoch::advance(Duration::from_secs(10));
1810 let usage = ChannelUsage { amount_msat: 0, ..usage };
1811 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1812 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
1813 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
1817 fn decays_liquidity_bounds_without_shift_overflow() {
1818 let logger = TestLogger::new();
1819 let network_graph = network_graph(&logger);
1820 let params = ProbabilisticScoringParameters {
1821 liquidity_penalty_multiplier_msat: 1_000,
1822 liquidity_offset_half_life: Duration::from_secs(10),
1823 ..ProbabilisticScoringParameters::zero_penalty()
1825 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1826 let source = source_node_id();
1827 let target = target_node_id();
1828 let usage = ChannelUsage {
1830 inflight_htlc_msat: 0,
1831 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024 },
1833 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
1835 scorer.payment_path_failed(&payment_path_for_amount(512).iter().collect::<Vec<_>>(), 42);
1836 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 281);
1838 // An unchecked right shift 64 bits or more in DirectedChannelLiquidity::decayed_offset_msat
1839 // would cause an overflow.
1840 SinceEpoch::advance(Duration::from_secs(10 * 64));
1841 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
1843 SinceEpoch::advance(Duration::from_secs(10));
1844 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
1848 fn restricts_liquidity_bounds_after_decay() {
1849 let logger = TestLogger::new();
1850 let network_graph = network_graph(&logger);
1851 let params = ProbabilisticScoringParameters {
1852 liquidity_penalty_multiplier_msat: 1_000,
1853 liquidity_offset_half_life: Duration::from_secs(10),
1854 ..ProbabilisticScoringParameters::zero_penalty()
1856 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1857 let source = source_node_id();
1858 let target = target_node_id();
1859 let usage = ChannelUsage {
1861 inflight_htlc_msat: 0,
1862 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024 },
1865 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1867 // More knowledge gives higher confidence (256, 768), meaning a lower penalty.
1868 scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::<Vec<_>>(), 42);
1869 scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::<Vec<_>>(), 43);
1870 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 281);
1872 // Decaying knowledge gives less confidence (128, 896), meaning a higher penalty.
1873 SinceEpoch::advance(Duration::from_secs(10));
1874 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 291);
1876 // Reducing the upper bound gives more confidence (128, 832) that the payment amount (512)
1877 // is closer to the upper bound, meaning a higher penalty.
1878 scorer.payment_path_successful(&payment_path_for_amount(64).iter().collect::<Vec<_>>());
1879 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 331);
1881 // Increasing the lower bound gives more confidence (256, 832) that the payment amount (512)
1882 // is closer to the lower bound, meaning a lower penalty.
1883 scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::<Vec<_>>(), 43);
1884 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 245);
1886 // Further decaying affects the lower bound more than the upper bound (128, 928).
1887 SinceEpoch::advance(Duration::from_secs(10));
1888 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 280);
1892 fn restores_persisted_liquidity_bounds() {
1893 let logger = TestLogger::new();
1894 let network_graph = network_graph(&logger);
1895 let params = ProbabilisticScoringParameters {
1896 liquidity_penalty_multiplier_msat: 1_000,
1897 liquidity_offset_half_life: Duration::from_secs(10),
1898 ..ProbabilisticScoringParameters::zero_penalty()
1900 let mut scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger);
1901 let source = source_node_id();
1902 let target = target_node_id();
1903 let usage = ChannelUsage {
1905 inflight_htlc_msat: 0,
1906 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000 },
1909 scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
1910 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1912 SinceEpoch::advance(Duration::from_secs(10));
1913 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 473);
1915 scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::<Vec<_>>(), 43);
1916 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1918 let mut serialized_scorer = Vec::new();
1919 scorer.write(&mut serialized_scorer).unwrap();
1921 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
1922 let deserialized_scorer =
1923 <ProbabilisticScorer>::read(&mut serialized_scorer, (params, &network_graph, &logger)).unwrap();
1924 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1928 fn decays_persisted_liquidity_bounds() {
1929 let logger = TestLogger::new();
1930 let network_graph = network_graph(&logger);
1931 let params = ProbabilisticScoringParameters {
1932 liquidity_penalty_multiplier_msat: 1_000,
1933 liquidity_offset_half_life: Duration::from_secs(10),
1934 ..ProbabilisticScoringParameters::zero_penalty()
1936 let mut scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger);
1937 let source = source_node_id();
1938 let target = target_node_id();
1939 let usage = ChannelUsage {
1941 inflight_htlc_msat: 0,
1942 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000 },
1945 scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
1946 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1948 let mut serialized_scorer = Vec::new();
1949 scorer.write(&mut serialized_scorer).unwrap();
1951 SinceEpoch::advance(Duration::from_secs(10));
1953 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
1954 let deserialized_scorer =
1955 <ProbabilisticScorer>::read(&mut serialized_scorer, (params, &network_graph, &logger)).unwrap();
1956 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage), 473);
1958 scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::<Vec<_>>(), 43);
1959 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1961 SinceEpoch::advance(Duration::from_secs(10));
1962 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage), 365);
1966 fn scores_realistic_payments() {
1967 // Shows the scores of "realistic" sends of 100k sats over channels of 1-10m sats (with a
1968 // 50k sat reserve).
1969 let logger = TestLogger::new();
1970 let network_graph = network_graph(&logger);
1971 let params = ProbabilisticScoringParameters::default();
1972 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1973 let source = source_node_id();
1974 let target = target_node_id();
1976 let usage = ChannelUsage {
1977 amount_msat: 100_000_000,
1978 inflight_htlc_msat: 0,
1979 effective_capacity: EffectiveCapacity::Total { capacity_msat: 950_000_000 },
1981 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 3613);
1982 let usage = ChannelUsage {
1983 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_950_000_000 }, ..usage
1985 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1977);
1986 let usage = ChannelUsage {
1987 effective_capacity: EffectiveCapacity::Total { capacity_msat: 2_950_000_000 }, ..usage
1989 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1474);
1990 let usage = ChannelUsage {
1991 effective_capacity: EffectiveCapacity::Total { capacity_msat: 3_950_000_000 }, ..usage
1993 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1223);
1994 let usage = ChannelUsage {
1995 effective_capacity: EffectiveCapacity::Total { capacity_msat: 4_950_000_000 }, ..usage
1997 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 877);
1998 let usage = ChannelUsage {
1999 effective_capacity: EffectiveCapacity::Total { capacity_msat: 5_950_000_000 }, ..usage
2001 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 845);
2002 let usage = ChannelUsage {
2003 effective_capacity: EffectiveCapacity::Total { capacity_msat: 6_950_000_000 }, ..usage
2005 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500);
2006 let usage = ChannelUsage {
2007 effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_450_000_000 }, ..usage
2009 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500);
2010 let usage = ChannelUsage {
2011 effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_950_000_000 }, ..usage
2013 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500);
2014 let usage = ChannelUsage {
2015 effective_capacity: EffectiveCapacity::Total { capacity_msat: 8_950_000_000 }, ..usage
2017 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500);
2018 let usage = ChannelUsage {
2019 effective_capacity: EffectiveCapacity::Total { capacity_msat: 9_950_000_000 }, ..usage
2021 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500);
2025 fn adds_base_penalty_to_liquidity_penalty() {
2026 let logger = TestLogger::new();
2027 let network_graph = network_graph(&logger);
2028 let source = source_node_id();
2029 let target = target_node_id();
2030 let usage = ChannelUsage {
2032 inflight_htlc_msat: 0,
2033 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024 },
2036 let params = ProbabilisticScoringParameters {
2037 liquidity_penalty_multiplier_msat: 1_000,
2038 ..ProbabilisticScoringParameters::zero_penalty()
2040 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2041 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 58);
2043 let params = ProbabilisticScoringParameters {
2044 base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000, ..Default::default()
2046 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2047 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 558);
2051 fn adds_amount_penalty_to_liquidity_penalty() {
2052 let logger = TestLogger::new();
2053 let network_graph = network_graph(&logger);
2054 let source = source_node_id();
2055 let target = target_node_id();
2056 let usage = ChannelUsage {
2057 amount_msat: 512_000,
2058 inflight_htlc_msat: 0,
2059 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000 },
2062 let params = ProbabilisticScoringParameters {
2063 liquidity_penalty_multiplier_msat: 1_000,
2064 amount_penalty_multiplier_msat: 0,
2065 ..ProbabilisticScoringParameters::zero_penalty()
2067 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2068 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2070 let params = ProbabilisticScoringParameters {
2071 liquidity_penalty_multiplier_msat: 1_000,
2072 amount_penalty_multiplier_msat: 256,
2073 ..ProbabilisticScoringParameters::zero_penalty()
2075 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2076 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 337);
2080 fn calculates_log10_without_overflowing_u64_max_value() {
2081 let logger = TestLogger::new();
2082 let network_graph = network_graph(&logger);
2083 let source = source_node_id();
2084 let target = target_node_id();
2085 let usage = ChannelUsage {
2086 amount_msat: u64::max_value(),
2087 inflight_htlc_msat: 0,
2088 effective_capacity: EffectiveCapacity::Infinite,
2091 let params = ProbabilisticScoringParameters {
2092 liquidity_penalty_multiplier_msat: 40_000,
2093 ..ProbabilisticScoringParameters::zero_penalty()
2095 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2096 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 80_000);
2100 fn accounts_for_inflight_htlc_usage() {
2101 let logger = TestLogger::new();
2102 let network_graph = network_graph(&logger);
2103 let params = ProbabilisticScoringParameters::default();
2104 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2105 let source = source_node_id();
2106 let target = target_node_id();
2108 let usage = ChannelUsage {
2110 inflight_htlc_msat: 0,
2111 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000 },
2113 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2115 let usage = ChannelUsage { inflight_htlc_msat: 251, ..usage };
2116 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2120 fn removes_uncertainity_when_exact_liquidity_known() {
2121 let logger = TestLogger::new();
2122 let network_graph = network_graph(&logger);
2123 let params = ProbabilisticScoringParameters::default();
2124 let scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger);
2125 let source = source_node_id();
2126 let target = target_node_id();
2128 let base_penalty_msat = params.base_penalty_msat;
2129 let usage = ChannelUsage {
2131 inflight_htlc_msat: 0,
2132 effective_capacity: EffectiveCapacity::ExactLiquidity { liquidity_msat: 1_000 },
2134 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), base_penalty_msat);
2136 let usage = ChannelUsage { amount_msat: 1_000, ..usage };
2137 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), base_penalty_msat);
2139 let usage = ChannelUsage { amount_msat: 1_001, ..usage };
2140 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());