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