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