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