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