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