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),
1218 // On rust prior to 1.60 `Instant::duration_since` will panic if time goes backwards.
1219 // We write `last_updated` as wallclock time even though its ultimately an `Instant` (which
1220 // is a time from a monotonic clock usually represented as an offset against boot time).
1221 // Thus, we have to construct an `Instant` by subtracting the difference in wallclock time
1222 // from the one that was written. However, because `Instant` can panic if we construct one
1223 // in the future, we must handle wallclock time jumping backwards, which we do by simply
1224 // using `Instant::now()` in that case.
1225 let wall_clock_now = T::duration_since_epoch();
1227 let last_updated = if wall_clock_now > duration_since_epoch {
1228 now - (wall_clock_now - duration_since_epoch)
1231 min_liquidity_offset_msat,
1232 max_liquidity_offset_msat,
1240 use super::{ChannelLiquidity, ProbabilisticScoringParameters, ProbabilisticScorerUsingTime};
1241 use util::time::Time;
1242 use util::time::tests::SinceEpoch;
1244 use ln::features::{ChannelFeatures, NodeFeatures};
1245 use ln::msgs::{ChannelAnnouncement, ChannelUpdate, OptionalField, UnsignedChannelAnnouncement, UnsignedChannelUpdate};
1246 use routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId};
1247 use routing::router::RouteHop;
1248 use routing::scoring::{ChannelUsage, Score};
1249 use util::ser::{ReadableArgs, Writeable};
1250 use util::test_utils::TestLogger;
1252 use bitcoin::blockdata::constants::genesis_block;
1253 use bitcoin::hashes::Hash;
1254 use bitcoin::hashes::sha256d::Hash as Sha256dHash;
1255 use bitcoin::network::constants::Network;
1256 use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey};
1257 use core::time::Duration;
1260 fn source_privkey() -> SecretKey {
1261 SecretKey::from_slice(&[42; 32]).unwrap()
1264 fn target_privkey() -> SecretKey {
1265 SecretKey::from_slice(&[43; 32]).unwrap()
1268 fn source_pubkey() -> PublicKey {
1269 let secp_ctx = Secp256k1::new();
1270 PublicKey::from_secret_key(&secp_ctx, &source_privkey())
1273 fn target_pubkey() -> PublicKey {
1274 let secp_ctx = Secp256k1::new();
1275 PublicKey::from_secret_key(&secp_ctx, &target_privkey())
1278 fn source_node_id() -> NodeId {
1279 NodeId::from_pubkey(&source_pubkey())
1282 fn target_node_id() -> NodeId {
1283 NodeId::from_pubkey(&target_pubkey())
1286 // `ProbabilisticScorer` tests
1288 /// A probabilistic scorer for testing with time that can be manually advanced.
1289 type ProbabilisticScorer<'a> = ProbabilisticScorerUsingTime::<&'a NetworkGraph<&'a TestLogger>, &'a TestLogger, SinceEpoch>;
1291 fn sender_privkey() -> SecretKey {
1292 SecretKey::from_slice(&[41; 32]).unwrap()
1295 fn recipient_privkey() -> SecretKey {
1296 SecretKey::from_slice(&[45; 32]).unwrap()
1299 fn sender_pubkey() -> PublicKey {
1300 let secp_ctx = Secp256k1::new();
1301 PublicKey::from_secret_key(&secp_ctx, &sender_privkey())
1304 fn recipient_pubkey() -> PublicKey {
1305 let secp_ctx = Secp256k1::new();
1306 PublicKey::from_secret_key(&secp_ctx, &recipient_privkey())
1309 fn sender_node_id() -> NodeId {
1310 NodeId::from_pubkey(&sender_pubkey())
1313 fn recipient_node_id() -> NodeId {
1314 NodeId::from_pubkey(&recipient_pubkey())
1317 fn network_graph(logger: &TestLogger) -> NetworkGraph<&TestLogger> {
1318 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1319 let mut network_graph = NetworkGraph::new(genesis_hash, logger);
1320 add_channel(&mut network_graph, 42, source_privkey(), target_privkey());
1321 add_channel(&mut network_graph, 43, target_privkey(), recipient_privkey());
1327 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_1_key: SecretKey,
1328 node_2_key: SecretKey
1330 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1331 let node_1_secret = &SecretKey::from_slice(&[39; 32]).unwrap();
1332 let node_2_secret = &SecretKey::from_slice(&[40; 32]).unwrap();
1333 let secp_ctx = Secp256k1::new();
1334 let unsigned_announcement = UnsignedChannelAnnouncement {
1335 features: ChannelFeatures::known(),
1336 chain_hash: genesis_hash,
1338 node_id_1: PublicKey::from_secret_key(&secp_ctx, &node_1_key),
1339 node_id_2: PublicKey::from_secret_key(&secp_ctx, &node_2_key),
1340 bitcoin_key_1: PublicKey::from_secret_key(&secp_ctx, &node_1_secret),
1341 bitcoin_key_2: PublicKey::from_secret_key(&secp_ctx, &node_2_secret),
1342 excess_data: Vec::new(),
1344 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
1345 let signed_announcement = ChannelAnnouncement {
1346 node_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_key),
1347 node_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_key),
1348 bitcoin_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_secret),
1349 bitcoin_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_secret),
1350 contents: unsigned_announcement,
1352 let chain_source: Option<&::util::test_utils::TestChainSource> = None;
1353 network_graph.update_channel_from_announcement(
1354 &signed_announcement, &chain_source).unwrap();
1355 update_channel(network_graph, short_channel_id, node_1_key, 0);
1356 update_channel(network_graph, short_channel_id, node_2_key, 1);
1360 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_key: SecretKey,
1363 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1364 let secp_ctx = Secp256k1::new();
1365 let unsigned_update = UnsignedChannelUpdate {
1366 chain_hash: genesis_hash,
1370 cltv_expiry_delta: 18,
1371 htlc_minimum_msat: 0,
1372 htlc_maximum_msat: OptionalField::Present(1_000),
1374 fee_proportional_millionths: 0,
1375 excess_data: Vec::new(),
1377 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_update.encode()[..])[..]);
1378 let signed_update = ChannelUpdate {
1379 signature: secp_ctx.sign_ecdsa(&msghash, &node_key),
1380 contents: unsigned_update,
1382 network_graph.update_channel(&signed_update).unwrap();
1385 fn payment_path_for_amount(amount_msat: u64) -> Vec<RouteHop> {
1388 pubkey: source_pubkey(),
1389 node_features: NodeFeatures::known(),
1390 short_channel_id: 41,
1391 channel_features: ChannelFeatures::known(),
1393 cltv_expiry_delta: 18,
1396 pubkey: target_pubkey(),
1397 node_features: NodeFeatures::known(),
1398 short_channel_id: 42,
1399 channel_features: ChannelFeatures::known(),
1401 cltv_expiry_delta: 18,
1404 pubkey: recipient_pubkey(),
1405 node_features: NodeFeatures::known(),
1406 short_channel_id: 43,
1407 channel_features: ChannelFeatures::known(),
1408 fee_msat: amount_msat,
1409 cltv_expiry_delta: 18,
1415 fn liquidity_bounds_directed_from_lowest_node_id() {
1416 let logger = TestLogger::new();
1417 let last_updated = SinceEpoch::now();
1418 let network_graph = network_graph(&logger);
1419 let params = ProbabilisticScoringParameters::default();
1420 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1423 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated
1427 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated
1429 let source = source_node_id();
1430 let target = target_node_id();
1431 let recipient = recipient_node_id();
1432 assert!(source > target);
1433 assert!(target < recipient);
1435 // Update minimum liquidity.
1437 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
1438 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1439 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1440 assert_eq!(liquidity.min_liquidity_msat(), 100);
1441 assert_eq!(liquidity.max_liquidity_msat(), 300);
1443 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1444 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1445 assert_eq!(liquidity.min_liquidity_msat(), 700);
1446 assert_eq!(liquidity.max_liquidity_msat(), 900);
1448 scorer.channel_liquidities.get_mut(&42).unwrap()
1449 .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
1450 .set_min_liquidity_msat(200);
1452 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1453 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1454 assert_eq!(liquidity.min_liquidity_msat(), 200);
1455 assert_eq!(liquidity.max_liquidity_msat(), 300);
1457 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1458 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1459 assert_eq!(liquidity.min_liquidity_msat(), 700);
1460 assert_eq!(liquidity.max_liquidity_msat(), 800);
1462 // Update maximum liquidity.
1464 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1465 .as_directed(&target, &recipient, 1_000, liquidity_offset_half_life);
1466 assert_eq!(liquidity.min_liquidity_msat(), 700);
1467 assert_eq!(liquidity.max_liquidity_msat(), 900);
1469 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1470 .as_directed(&recipient, &target, 1_000, liquidity_offset_half_life);
1471 assert_eq!(liquidity.min_liquidity_msat(), 100);
1472 assert_eq!(liquidity.max_liquidity_msat(), 300);
1474 scorer.channel_liquidities.get_mut(&43).unwrap()
1475 .as_directed_mut(&target, &recipient, 1_000, liquidity_offset_half_life)
1476 .set_max_liquidity_msat(200);
1478 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1479 .as_directed(&target, &recipient, 1_000, liquidity_offset_half_life);
1480 assert_eq!(liquidity.min_liquidity_msat(), 0);
1481 assert_eq!(liquidity.max_liquidity_msat(), 200);
1483 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1484 .as_directed(&recipient, &target, 1_000, liquidity_offset_half_life);
1485 assert_eq!(liquidity.min_liquidity_msat(), 800);
1486 assert_eq!(liquidity.max_liquidity_msat(), 1000);
1490 fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() {
1491 let logger = TestLogger::new();
1492 let last_updated = SinceEpoch::now();
1493 let network_graph = network_graph(&logger);
1494 let params = ProbabilisticScoringParameters::default();
1495 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1498 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated
1500 let source = source_node_id();
1501 let target = target_node_id();
1502 assert!(source > target);
1504 // Check initial bounds.
1505 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
1506 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1507 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1508 assert_eq!(liquidity.min_liquidity_msat(), 400);
1509 assert_eq!(liquidity.max_liquidity_msat(), 800);
1511 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1512 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1513 assert_eq!(liquidity.min_liquidity_msat(), 200);
1514 assert_eq!(liquidity.max_liquidity_msat(), 600);
1516 // Reset from source to target.
1517 scorer.channel_liquidities.get_mut(&42).unwrap()
1518 .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
1519 .set_min_liquidity_msat(900);
1521 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1522 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1523 assert_eq!(liquidity.min_liquidity_msat(), 900);
1524 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1526 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1527 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1528 assert_eq!(liquidity.min_liquidity_msat(), 0);
1529 assert_eq!(liquidity.max_liquidity_msat(), 100);
1531 // Reset from target to source.
1532 scorer.channel_liquidities.get_mut(&42).unwrap()
1533 .as_directed_mut(&target, &source, 1_000, liquidity_offset_half_life)
1534 .set_min_liquidity_msat(400);
1536 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1537 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1538 assert_eq!(liquidity.min_liquidity_msat(), 0);
1539 assert_eq!(liquidity.max_liquidity_msat(), 600);
1541 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1542 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1543 assert_eq!(liquidity.min_liquidity_msat(), 400);
1544 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1548 fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() {
1549 let logger = TestLogger::new();
1550 let last_updated = SinceEpoch::now();
1551 let network_graph = network_graph(&logger);
1552 let params = ProbabilisticScoringParameters::default();
1553 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1556 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated
1558 let source = source_node_id();
1559 let target = target_node_id();
1560 assert!(source > target);
1562 // Check initial bounds.
1563 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
1564 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1565 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1566 assert_eq!(liquidity.min_liquidity_msat(), 400);
1567 assert_eq!(liquidity.max_liquidity_msat(), 800);
1569 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1570 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1571 assert_eq!(liquidity.min_liquidity_msat(), 200);
1572 assert_eq!(liquidity.max_liquidity_msat(), 600);
1574 // Reset from source to target.
1575 scorer.channel_liquidities.get_mut(&42).unwrap()
1576 .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
1577 .set_max_liquidity_msat(300);
1579 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1580 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1581 assert_eq!(liquidity.min_liquidity_msat(), 0);
1582 assert_eq!(liquidity.max_liquidity_msat(), 300);
1584 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1585 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1586 assert_eq!(liquidity.min_liquidity_msat(), 700);
1587 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1589 // Reset from target to source.
1590 scorer.channel_liquidities.get_mut(&42).unwrap()
1591 .as_directed_mut(&target, &source, 1_000, liquidity_offset_half_life)
1592 .set_max_liquidity_msat(600);
1594 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1595 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1596 assert_eq!(liquidity.min_liquidity_msat(), 400);
1597 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1599 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1600 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1601 assert_eq!(liquidity.min_liquidity_msat(), 0);
1602 assert_eq!(liquidity.max_liquidity_msat(), 600);
1606 fn increased_penalty_nearing_liquidity_upper_bound() {
1607 let logger = TestLogger::new();
1608 let network_graph = network_graph(&logger);
1609 let params = ProbabilisticScoringParameters {
1610 liquidity_penalty_multiplier_msat: 1_000,
1611 ..ProbabilisticScoringParameters::zero_penalty()
1613 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1614 let source = source_node_id();
1615 let target = target_node_id();
1617 let usage = ChannelUsage {
1619 inflight_htlc_msat: 0,
1620 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(1_000) },
1622 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1623 let usage = ChannelUsage { amount_msat: 10_240, ..usage };
1624 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1625 let usage = ChannelUsage { amount_msat: 102_400, ..usage };
1626 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 47);
1627 let usage = ChannelUsage { amount_msat: 1_024_000, ..usage };
1628 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
1630 let usage = ChannelUsage {
1632 inflight_htlc_msat: 0,
1633 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_000) },
1635 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 58);
1636 let usage = ChannelUsage { amount_msat: 256, ..usage };
1637 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
1638 let usage = ChannelUsage { amount_msat: 374, ..usage };
1639 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 198);
1640 let usage = ChannelUsage { amount_msat: 512, ..usage };
1641 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1642 let usage = ChannelUsage { amount_msat: 640, ..usage };
1643 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 425);
1644 let usage = ChannelUsage { amount_msat: 768, ..usage };
1645 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 602);
1646 let usage = ChannelUsage { amount_msat: 896, ..usage };
1647 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 902);
1651 fn constant_penalty_outside_liquidity_bounds() {
1652 let logger = TestLogger::new();
1653 let last_updated = SinceEpoch::now();
1654 let network_graph = network_graph(&logger);
1655 let params = ProbabilisticScoringParameters {
1656 liquidity_penalty_multiplier_msat: 1_000,
1657 ..ProbabilisticScoringParameters::zero_penalty()
1659 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1662 min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40, last_updated
1664 let source = source_node_id();
1665 let target = target_node_id();
1667 let usage = ChannelUsage {
1669 inflight_htlc_msat: 0,
1670 effective_capacity: EffectiveCapacity::Total { capacity_msat: 100, htlc_maximum_msat: Some(1_000) },
1672 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1673 let usage = ChannelUsage { amount_msat: 50, ..usage };
1674 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1675 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1676 let usage = ChannelUsage { amount_msat: 61, ..usage };
1677 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1681 fn does_not_further_penalize_own_channel() {
1682 let logger = TestLogger::new();
1683 let network_graph = network_graph(&logger);
1684 let params = ProbabilisticScoringParameters {
1685 liquidity_penalty_multiplier_msat: 1_000,
1686 ..ProbabilisticScoringParameters::zero_penalty()
1688 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1689 let sender = sender_node_id();
1690 let source = source_node_id();
1691 let usage = ChannelUsage {
1693 inflight_htlc_msat: 0,
1694 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
1696 let failed_path = payment_path_for_amount(500);
1697 let successful_path = payment_path_for_amount(200);
1699 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 301);
1701 scorer.payment_path_failed(&failed_path.iter().collect::<Vec<_>>(), 41);
1702 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 301);
1704 scorer.payment_path_successful(&successful_path.iter().collect::<Vec<_>>());
1705 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 301);
1709 fn sets_liquidity_lower_bound_on_downstream_failure() {
1710 let logger = TestLogger::new();
1711 let network_graph = network_graph(&logger);
1712 let params = ProbabilisticScoringParameters {
1713 liquidity_penalty_multiplier_msat: 1_000,
1714 ..ProbabilisticScoringParameters::zero_penalty()
1716 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1717 let source = source_node_id();
1718 let target = target_node_id();
1719 let path = payment_path_for_amount(500);
1721 let usage = ChannelUsage {
1723 inflight_htlc_msat: 0,
1724 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
1726 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 128);
1727 let usage = ChannelUsage { amount_msat: 500, ..usage };
1728 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 301);
1729 let usage = ChannelUsage { amount_msat: 750, ..usage };
1730 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 602);
1732 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 43);
1734 let usage = ChannelUsage { amount_msat: 250, ..usage };
1735 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1736 let usage = ChannelUsage { amount_msat: 500, ..usage };
1737 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1738 let usage = ChannelUsage { amount_msat: 750, ..usage };
1739 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1743 fn sets_liquidity_upper_bound_on_failure() {
1744 let logger = TestLogger::new();
1745 let network_graph = network_graph(&logger);
1746 let params = ProbabilisticScoringParameters {
1747 liquidity_penalty_multiplier_msat: 1_000,
1748 ..ProbabilisticScoringParameters::zero_penalty()
1750 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1751 let source = source_node_id();
1752 let target = target_node_id();
1753 let path = payment_path_for_amount(500);
1755 let usage = ChannelUsage {
1757 inflight_htlc_msat: 0,
1758 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
1760 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 128);
1761 let usage = ChannelUsage { amount_msat: 500, ..usage };
1762 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 301);
1763 let usage = ChannelUsage { amount_msat: 750, ..usage };
1764 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 602);
1766 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 42);
1768 let usage = ChannelUsage { amount_msat: 250, ..usage };
1769 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1770 let usage = ChannelUsage { amount_msat: 500, ..usage };
1771 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1772 let usage = ChannelUsage { amount_msat: 750, ..usage };
1773 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1777 fn reduces_liquidity_upper_bound_along_path_on_success() {
1778 let logger = TestLogger::new();
1779 let network_graph = network_graph(&logger);
1780 let params = ProbabilisticScoringParameters {
1781 liquidity_penalty_multiplier_msat: 1_000,
1782 ..ProbabilisticScoringParameters::zero_penalty()
1784 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1785 let sender = sender_node_id();
1786 let source = source_node_id();
1787 let target = target_node_id();
1788 let recipient = recipient_node_id();
1789 let usage = ChannelUsage {
1791 inflight_htlc_msat: 0,
1792 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
1794 let path = payment_path_for_amount(500);
1796 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 128);
1797 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 128);
1798 assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage), 128);
1800 scorer.payment_path_successful(&path.iter().collect::<Vec<_>>());
1802 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 128);
1803 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1804 assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage), 300);
1808 fn decays_liquidity_bounds_over_time() {
1809 let logger = TestLogger::new();
1810 let network_graph = network_graph(&logger);
1811 let params = ProbabilisticScoringParameters {
1812 liquidity_penalty_multiplier_msat: 1_000,
1813 liquidity_offset_half_life: Duration::from_secs(10),
1814 ..ProbabilisticScoringParameters::zero_penalty()
1816 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1817 let source = source_node_id();
1818 let target = target_node_id();
1820 let usage = ChannelUsage {
1822 inflight_htlc_msat: 0,
1823 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_000) },
1825 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1826 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
1827 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
1829 scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::<Vec<_>>(), 42);
1830 scorer.payment_path_failed(&payment_path_for_amount(128).iter().collect::<Vec<_>>(), 43);
1832 let usage = ChannelUsage { amount_msat: 128, ..usage };
1833 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1834 let usage = ChannelUsage { amount_msat: 256, ..usage };
1835 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 93);
1836 let usage = ChannelUsage { amount_msat: 768, ..usage };
1837 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1_479);
1838 let usage = ChannelUsage { amount_msat: 896, ..usage };
1839 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1841 SinceEpoch::advance(Duration::from_secs(9));
1842 let usage = ChannelUsage { amount_msat: 128, ..usage };
1843 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1844 let usage = ChannelUsage { amount_msat: 256, ..usage };
1845 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 93);
1846 let usage = ChannelUsage { amount_msat: 768, ..usage };
1847 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1_479);
1848 let usage = ChannelUsage { amount_msat: 896, ..usage };
1849 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1851 SinceEpoch::advance(Duration::from_secs(1));
1852 let usage = ChannelUsage { amount_msat: 64, ..usage };
1853 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1854 let usage = ChannelUsage { amount_msat: 128, ..usage };
1855 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 34);
1856 let usage = ChannelUsage { amount_msat: 896, ..usage };
1857 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1_970);
1858 let usage = ChannelUsage { amount_msat: 960, ..usage };
1859 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1861 // Fully decay liquidity lower bound.
1862 SinceEpoch::advance(Duration::from_secs(10 * 7));
1863 let usage = ChannelUsage { amount_msat: 0, ..usage };
1864 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1865 let usage = ChannelUsage { amount_msat: 1, ..usage };
1866 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1867 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
1868 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
1869 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
1870 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
1872 // Fully decay liquidity upper bound.
1873 SinceEpoch::advance(Duration::from_secs(10));
1874 let usage = ChannelUsage { amount_msat: 0, ..usage };
1875 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1876 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
1877 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
1879 SinceEpoch::advance(Duration::from_secs(10));
1880 let usage = ChannelUsage { amount_msat: 0, ..usage };
1881 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1882 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
1883 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
1887 fn decays_liquidity_bounds_without_shift_overflow() {
1888 let logger = TestLogger::new();
1889 let network_graph = network_graph(&logger);
1890 let params = ProbabilisticScoringParameters {
1891 liquidity_penalty_multiplier_msat: 1_000,
1892 liquidity_offset_half_life: Duration::from_secs(10),
1893 ..ProbabilisticScoringParameters::zero_penalty()
1895 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1896 let source = source_node_id();
1897 let target = target_node_id();
1898 let usage = ChannelUsage {
1900 inflight_htlc_msat: 0,
1901 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_000) },
1903 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
1905 scorer.payment_path_failed(&payment_path_for_amount(512).iter().collect::<Vec<_>>(), 42);
1906 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 281);
1908 // An unchecked right shift 64 bits or more in DirectedChannelLiquidity::decayed_offset_msat
1909 // would cause an overflow.
1910 SinceEpoch::advance(Duration::from_secs(10 * 64));
1911 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
1913 SinceEpoch::advance(Duration::from_secs(10));
1914 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
1918 fn restricts_liquidity_bounds_after_decay() {
1919 let logger = TestLogger::new();
1920 let network_graph = network_graph(&logger);
1921 let params = ProbabilisticScoringParameters {
1922 liquidity_penalty_multiplier_msat: 1_000,
1923 liquidity_offset_half_life: Duration::from_secs(10),
1924 ..ProbabilisticScoringParameters::zero_penalty()
1926 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1927 let source = source_node_id();
1928 let target = target_node_id();
1929 let usage = ChannelUsage {
1931 inflight_htlc_msat: 0,
1932 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_000) },
1935 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1937 // More knowledge gives higher confidence (256, 768), meaning a lower penalty.
1938 scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::<Vec<_>>(), 42);
1939 scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::<Vec<_>>(), 43);
1940 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 281);
1942 // Decaying knowledge gives less confidence (128, 896), meaning a higher penalty.
1943 SinceEpoch::advance(Duration::from_secs(10));
1944 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 291);
1946 // Reducing the upper bound gives more confidence (128, 832) that the payment amount (512)
1947 // is closer to the upper bound, meaning a higher penalty.
1948 scorer.payment_path_successful(&payment_path_for_amount(64).iter().collect::<Vec<_>>());
1949 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 331);
1951 // Increasing the lower bound gives more confidence (256, 832) that the payment amount (512)
1952 // is closer to the lower bound, meaning a lower penalty.
1953 scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::<Vec<_>>(), 43);
1954 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 245);
1956 // Further decaying affects the lower bound more than the upper bound (128, 928).
1957 SinceEpoch::advance(Duration::from_secs(10));
1958 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 280);
1962 fn restores_persisted_liquidity_bounds() {
1963 let logger = TestLogger::new();
1964 let network_graph = network_graph(&logger);
1965 let params = ProbabilisticScoringParameters {
1966 liquidity_penalty_multiplier_msat: 1_000,
1967 liquidity_offset_half_life: Duration::from_secs(10),
1968 ..ProbabilisticScoringParameters::zero_penalty()
1970 let mut scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger);
1971 let source = source_node_id();
1972 let target = target_node_id();
1973 let usage = ChannelUsage {
1975 inflight_htlc_msat: 0,
1976 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
1979 scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
1980 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1982 SinceEpoch::advance(Duration::from_secs(10));
1983 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 473);
1985 scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::<Vec<_>>(), 43);
1986 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1988 let mut serialized_scorer = Vec::new();
1989 scorer.write(&mut serialized_scorer).unwrap();
1991 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
1992 let deserialized_scorer =
1993 <ProbabilisticScorer>::read(&mut serialized_scorer, (params, &network_graph, &logger)).unwrap();
1994 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1998 fn decays_persisted_liquidity_bounds() {
1999 let logger = TestLogger::new();
2000 let network_graph = network_graph(&logger);
2001 let params = ProbabilisticScoringParameters {
2002 liquidity_penalty_multiplier_msat: 1_000,
2003 liquidity_offset_half_life: Duration::from_secs(10),
2004 ..ProbabilisticScoringParameters::zero_penalty()
2006 let mut scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger);
2007 let source = source_node_id();
2008 let target = target_node_id();
2009 let usage = ChannelUsage {
2011 inflight_htlc_msat: 0,
2012 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
2015 scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
2016 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2018 let mut serialized_scorer = Vec::new();
2019 scorer.write(&mut serialized_scorer).unwrap();
2021 SinceEpoch::advance(Duration::from_secs(10));
2023 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
2024 let deserialized_scorer =
2025 <ProbabilisticScorer>::read(&mut serialized_scorer, (params, &network_graph, &logger)).unwrap();
2026 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage), 473);
2028 scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::<Vec<_>>(), 43);
2029 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2031 SinceEpoch::advance(Duration::from_secs(10));
2032 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage), 365);
2036 fn scores_realistic_payments() {
2037 // Shows the scores of "realistic" sends of 100k sats over channels of 1-10m sats (with a
2038 // 50k sat reserve).
2039 let logger = TestLogger::new();
2040 let network_graph = network_graph(&logger);
2041 let params = ProbabilisticScoringParameters::default();
2042 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2043 let source = source_node_id();
2044 let target = target_node_id();
2046 let usage = ChannelUsage {
2047 amount_msat: 100_000_000,
2048 inflight_htlc_msat: 0,
2049 effective_capacity: EffectiveCapacity::Total { capacity_msat: 950_000_000, htlc_maximum_msat: Some(1_000) },
2051 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 3613);
2052 let usage = ChannelUsage {
2053 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2055 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1977);
2056 let usage = ChannelUsage {
2057 effective_capacity: EffectiveCapacity::Total { capacity_msat: 2_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2059 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1474);
2060 let usage = ChannelUsage {
2061 effective_capacity: EffectiveCapacity::Total { capacity_msat: 3_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2063 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1223);
2064 let usage = ChannelUsage {
2065 effective_capacity: EffectiveCapacity::Total { capacity_msat: 4_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2067 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 877);
2068 let usage = ChannelUsage {
2069 effective_capacity: EffectiveCapacity::Total { capacity_msat: 5_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2071 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 845);
2072 let usage = ChannelUsage {
2073 effective_capacity: EffectiveCapacity::Total { capacity_msat: 6_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: 7_450_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2079 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500);
2080 let usage = ChannelUsage {
2081 effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2083 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500);
2084 let usage = ChannelUsage {
2085 effective_capacity: EffectiveCapacity::Total { capacity_msat: 8_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2087 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500);
2088 let usage = ChannelUsage {
2089 effective_capacity: EffectiveCapacity::Total { capacity_msat: 9_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2091 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500);
2095 fn adds_base_penalty_to_liquidity_penalty() {
2096 let logger = TestLogger::new();
2097 let network_graph = network_graph(&logger);
2098 let source = source_node_id();
2099 let target = target_node_id();
2100 let usage = ChannelUsage {
2102 inflight_htlc_msat: 0,
2103 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_000) },
2106 let params = ProbabilisticScoringParameters {
2107 liquidity_penalty_multiplier_msat: 1_000,
2108 ..ProbabilisticScoringParameters::zero_penalty()
2110 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2111 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 58);
2113 let params = ProbabilisticScoringParameters {
2114 base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000,
2115 anti_probing_penalty_msat: 0, ..Default::default()
2117 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2118 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 558);
2122 fn adds_amount_penalty_to_liquidity_penalty() {
2123 let logger = TestLogger::new();
2124 let network_graph = network_graph(&logger);
2125 let source = source_node_id();
2126 let target = target_node_id();
2127 let usage = ChannelUsage {
2128 amount_msat: 512_000,
2129 inflight_htlc_msat: 0,
2130 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(1_000) },
2133 let params = ProbabilisticScoringParameters {
2134 liquidity_penalty_multiplier_msat: 1_000,
2135 amount_penalty_multiplier_msat: 0,
2136 ..ProbabilisticScoringParameters::zero_penalty()
2138 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2139 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2141 let params = ProbabilisticScoringParameters {
2142 liquidity_penalty_multiplier_msat: 1_000,
2143 amount_penalty_multiplier_msat: 256,
2144 ..ProbabilisticScoringParameters::zero_penalty()
2146 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2147 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 337);
2151 fn calculates_log10_without_overflowing_u64_max_value() {
2152 let logger = TestLogger::new();
2153 let network_graph = network_graph(&logger);
2154 let source = source_node_id();
2155 let target = target_node_id();
2156 let usage = ChannelUsage {
2157 amount_msat: u64::max_value(),
2158 inflight_htlc_msat: 0,
2159 effective_capacity: EffectiveCapacity::Infinite,
2162 let params = ProbabilisticScoringParameters {
2163 liquidity_penalty_multiplier_msat: 40_000,
2164 ..ProbabilisticScoringParameters::zero_penalty()
2166 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2167 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 80_000);
2171 fn accounts_for_inflight_htlc_usage() {
2172 let logger = TestLogger::new();
2173 let network_graph = network_graph(&logger);
2174 let params = ProbabilisticScoringParameters::default();
2175 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2176 let source = source_node_id();
2177 let target = target_node_id();
2179 let usage = ChannelUsage {
2181 inflight_htlc_msat: 0,
2182 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
2184 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2186 let usage = ChannelUsage { inflight_htlc_msat: 251, ..usage };
2187 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2191 fn removes_uncertainity_when_exact_liquidity_known() {
2192 let logger = TestLogger::new();
2193 let network_graph = network_graph(&logger);
2194 let params = ProbabilisticScoringParameters::default();
2195 let scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger);
2196 let source = source_node_id();
2197 let target = target_node_id();
2199 let base_penalty_msat = params.base_penalty_msat;
2200 let usage = ChannelUsage {
2202 inflight_htlc_msat: 0,
2203 effective_capacity: EffectiveCapacity::ExactLiquidity { liquidity_msat: 1_000 },
2205 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), base_penalty_msat);
2207 let usage = ChannelUsage { amount_msat: 1_000, ..usage };
2208 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), base_penalty_msat);
2210 let usage = ChannelUsage { amount_msat: 1_001, ..usage };
2211 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2215 fn adds_anti_probing_penalty() {
2216 let logger = TestLogger::new();
2217 let network_graph = network_graph(&logger);
2218 let source = source_node_id();
2219 let target = target_node_id();
2220 let params = ProbabilisticScoringParameters {
2221 anti_probing_penalty_msat: 500,
2222 ..ProbabilisticScoringParameters::zero_penalty()
2224 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2226 // Check we receive no penalty for a low htlc_maximum_msat.
2227 let usage = ChannelUsage {
2228 amount_msat: 512_000,
2229 inflight_htlc_msat: 0,
2230 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(1_000) },
2232 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2234 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity.
2235 let usage = ChannelUsage {
2236 amount_msat: 512_000,
2237 inflight_htlc_msat: 0,
2238 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(1_024_000) },
2240 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500);
2242 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity/2.
2243 let usage = ChannelUsage {
2244 amount_msat: 512_000,
2245 inflight_htlc_msat: 0,
2246 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(512_000) },
2248 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500);
2250 // Check we receive no anti-probing penalty for htlc_maximum_msat == channel_capacity/2 - 1.
2251 let usage = ChannelUsage {
2252 amount_msat: 512_000,
2253 inflight_htlc_msat: 0,
2254 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(511_999) },
2256 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
projects / rust-lightning / blob