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