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