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