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