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