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