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