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