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 /// Manual penalties used for the given nodes. Allows to set a particular penalty for a given
366 /// node. Note that a manual penalty of `u64::max_value()` means the node would not ever be
367 /// considered during path finding.
370 pub manual_node_penalties: HashMap<NodeId, u64>,
372 /// This penalty is applied when `htlc_maximum_msat` is equal to or larger than half of the
373 /// channel's capacity, which makes us prefer nodes with a smaller `htlc_maximum_msat`. We
374 /// treat such nodes preferentially as this makes balance discovery attacks harder to execute,
375 /// thereby creating an incentive to restrict `htlc_maximum_msat` and improve privacy.
377 /// Default value: 250 msat
378 pub anti_probing_penalty_msat: u64,
381 /// Accounting for channel liquidity balance uncertainty.
383 /// Direction is defined in terms of [`NodeId`] partial ordering, where the source node is the
384 /// first node in the ordering of the channel's counterparties. Thus, swapping the two liquidity
385 /// offset fields gives the opposite direction.
386 struct ChannelLiquidity<T: Time> {
387 /// Lower channel liquidity bound in terms of an offset from zero.
388 min_liquidity_offset_msat: u64,
390 /// Upper channel liquidity bound in terms of an offset from the effective capacity.
391 max_liquidity_offset_msat: u64,
393 /// Time when the liquidity bounds were last modified.
397 /// A snapshot of [`ChannelLiquidity`] in one direction assuming a certain channel capacity and
398 /// decayed with a given half life.
399 struct DirectedChannelLiquidity<L: Deref<Target = u64>, T: Time, U: Deref<Target = T>> {
400 min_liquidity_offset_msat: L,
401 max_liquidity_offset_msat: L,
408 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
409 /// Creates a new scorer using the given scoring parameters for sending payments from a node
410 /// through a network graph.
411 pub fn new(params: ProbabilisticScoringParameters, network_graph: G, logger: L) -> Self {
416 channel_liquidities: HashMap::new(),
421 fn with_channel(mut self, short_channel_id: u64, liquidity: ChannelLiquidity<T>) -> Self {
422 assert!(self.channel_liquidities.insert(short_channel_id, liquidity).is_none());
426 /// Dump the contents of this scorer into the configured logger.
428 /// Note that this writes roughly one line per channel for which we have a liquidity estimate,
429 /// which may be a substantial amount of log output.
430 pub fn debug_log_liquidity_stats(&self) {
431 let graph = self.network_graph.read_only();
432 for (scid, liq) in self.channel_liquidities.iter() {
433 if let Some(chan_debug) = graph.channels().get(scid) {
434 let log_direction = |source, target| {
435 if let Some((directed_info, _)) = chan_debug.as_directed_to(target) {
436 let amt = directed_info.effective_capacity().as_msat();
437 let dir_liq = liq.as_directed(source, target, amt, self.params.liquidity_offset_half_life);
438 log_debug!(self.logger, "Liquidity from {:?} to {:?} via {} is in the range ({}, {})",
439 source, target, scid, dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat());
441 log_debug!(self.logger, "No amount known for SCID {} from {:?} to {:?}", scid, source, target);
445 log_direction(&chan_debug.node_one, &chan_debug.node_two);
446 log_direction(&chan_debug.node_two, &chan_debug.node_one);
448 log_debug!(self.logger, "No network graph entry for SCID {}", scid);
453 /// Query the estimated minimum and maximum liquidity available for sending a payment over the
454 /// channel with `scid` towards the given `target` node.
455 pub fn estimated_channel_liquidity_range(&self, scid: u64, target: &NodeId) -> Option<(u64, u64)> {
456 let graph = self.network_graph.read_only();
458 if let Some(chan) = graph.channels().get(&scid) {
459 if let Some(liq) = self.channel_liquidities.get(&scid) {
460 if let Some((directed_info, source)) = chan.as_directed_to(target) {
461 let amt = directed_info.effective_capacity().as_msat();
462 let dir_liq = liq.as_directed(source, target, amt, self.params.liquidity_offset_half_life);
463 return Some((dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat()));
470 /// Marks the node with the given `node_id` as banned, i.e.,
471 /// it will be avoided during path finding.
472 pub fn add_banned(&mut self, node_id: &NodeId) {
473 self.params.manual_node_penalties.insert(*node_id, u64::max_value());
476 /// Removes the node with the given `node_id` from the list of nodes to avoid.
477 pub fn remove_banned(&mut self, node_id: &NodeId) {
478 self.params.manual_node_penalties.remove(node_id);
481 /// Sets a manual penalty for the given node.
482 pub fn set_manual_penalty(&mut self, node_id: &NodeId, penalty: u64) {
483 self.params.manual_node_penalties.insert(*node_id, penalty);
486 /// Removes the node with the given `node_id` from the list of manual penalties.
487 pub fn remove_manual_penalty(&mut self, node_id: &NodeId) {
488 self.params.manual_node_penalties.remove(node_id);
491 /// Clears the list of manual penalties that are applied during path finding.
492 pub fn clear_manual_penalties(&mut self) {
493 self.params.manual_node_penalties = HashMap::new();
497 impl ProbabilisticScoringParameters {
499 fn zero_penalty() -> Self {
501 base_penalty_msat: 0,
502 liquidity_penalty_multiplier_msat: 0,
503 liquidity_offset_half_life: Duration::from_secs(3600),
504 amount_penalty_multiplier_msat: 0,
505 manual_node_penalties: HashMap::new(),
506 anti_probing_penalty_msat: 0,
510 /// Marks all nodes in the given list as banned, i.e.,
511 /// they will be avoided during path finding.
512 pub fn add_banned_from_list(&mut self, node_ids: Vec<NodeId>) {
514 self.manual_node_penalties.insert(id, u64::max_value());
519 impl Default for ProbabilisticScoringParameters {
520 fn default() -> Self {
522 base_penalty_msat: 500,
523 liquidity_penalty_multiplier_msat: 40_000,
524 liquidity_offset_half_life: Duration::from_secs(3600),
525 amount_penalty_multiplier_msat: 256,
526 manual_node_penalties: HashMap::new(),
527 anti_probing_penalty_msat: 250,
532 impl<T: Time> ChannelLiquidity<T> {
536 min_liquidity_offset_msat: 0,
537 max_liquidity_offset_msat: 0,
538 last_updated: T::now(),
542 /// Returns a view of the channel liquidity directed from `source` to `target` assuming
545 &self, source: &NodeId, target: &NodeId, capacity_msat: u64, half_life: Duration
546 ) -> DirectedChannelLiquidity<&u64, T, &T> {
547 let (min_liquidity_offset_msat, max_liquidity_offset_msat) = if source < target {
548 (&self.min_liquidity_offset_msat, &self.max_liquidity_offset_msat)
550 (&self.max_liquidity_offset_msat, &self.min_liquidity_offset_msat)
553 DirectedChannelLiquidity {
554 min_liquidity_offset_msat,
555 max_liquidity_offset_msat,
557 last_updated: &self.last_updated,
563 /// Returns a mutable view of the channel liquidity directed from `source` to `target` assuming
566 &mut self, source: &NodeId, target: &NodeId, capacity_msat: u64, half_life: Duration
567 ) -> DirectedChannelLiquidity<&mut u64, T, &mut T> {
568 let (min_liquidity_offset_msat, max_liquidity_offset_msat) = if source < target {
569 (&mut self.min_liquidity_offset_msat, &mut self.max_liquidity_offset_msat)
571 (&mut self.max_liquidity_offset_msat, &mut self.min_liquidity_offset_msat)
574 DirectedChannelLiquidity {
575 min_liquidity_offset_msat,
576 max_liquidity_offset_msat,
578 last_updated: &mut self.last_updated,
585 /// Bounds `-log10` to avoid excessive liquidity penalties for payments with low success
587 const NEGATIVE_LOG10_UPPER_BOUND: u64 = 2;
589 /// The rough cutoff at which our precision falls off and we should stop bothering to try to log a
590 /// ratio, as X in 1/X.
591 const PRECISION_LOWER_BOUND_DENOMINATOR: u64 = approx::LOWER_BITS_BOUND;
593 /// The divisor used when computing the amount penalty.
594 const AMOUNT_PENALTY_DIVISOR: u64 = 1 << 20;
596 impl<L: Deref<Target = u64>, T: Time, U: Deref<Target = T>> DirectedChannelLiquidity<L, T, U> {
597 /// Returns a penalty for routing the given HTLC `amount_msat` through the channel in this
599 fn penalty_msat(&self, amount_msat: u64, params: &ProbabilisticScoringParameters) -> u64 {
600 let max_liquidity_msat = self.max_liquidity_msat();
601 let min_liquidity_msat = core::cmp::min(self.min_liquidity_msat(), max_liquidity_msat);
602 if amount_msat <= min_liquidity_msat {
604 } else if amount_msat >= max_liquidity_msat {
605 if amount_msat > max_liquidity_msat {
607 } else if max_liquidity_msat != self.capacity_msat {
608 // Avoid using the failed channel on retry.
611 // Equivalent to hitting the else clause below with the amount equal to the
612 // effective capacity and without any certainty on the liquidity upper bound.
613 let negative_log10_times_2048 = NEGATIVE_LOG10_UPPER_BOUND * 2048;
614 self.combined_penalty_msat(amount_msat, negative_log10_times_2048, params)
617 let numerator = (max_liquidity_msat - amount_msat).saturating_add(1);
618 let denominator = (max_liquidity_msat - min_liquidity_msat).saturating_add(1);
619 if amount_msat - min_liquidity_msat < denominator / PRECISION_LOWER_BOUND_DENOMINATOR {
620 // If the failure probability is < 1.5625% (as 1 - numerator/denominator < 1/64),
621 // don't bother trying to use the log approximation as it gets too noisy to be
622 // particularly helpful, instead just round down to 0 and return the base penalty.
623 params.base_penalty_msat
625 let negative_log10_times_2048 =
626 approx::negative_log10_times_2048(numerator, denominator);
627 self.combined_penalty_msat(amount_msat, negative_log10_times_2048, params)
632 /// Computes the liquidity and amount penalties and adds them to the base penalty.
634 fn combined_penalty_msat(
635 &self, amount_msat: u64, negative_log10_times_2048: u64,
636 params: &ProbabilisticScoringParameters
638 let liquidity_penalty_msat = {
639 // Upper bound the liquidity penalty to ensure some channel is selected.
640 let multiplier_msat = params.liquidity_penalty_multiplier_msat;
641 let max_penalty_msat = multiplier_msat.saturating_mul(NEGATIVE_LOG10_UPPER_BOUND);
642 (negative_log10_times_2048.saturating_mul(multiplier_msat) / 2048).min(max_penalty_msat)
644 let amount_penalty_msat = negative_log10_times_2048
645 .saturating_mul(params.amount_penalty_multiplier_msat)
646 .saturating_mul(amount_msat) / 2048 / AMOUNT_PENALTY_DIVISOR;
648 params.base_penalty_msat
649 .saturating_add(liquidity_penalty_msat)
650 .saturating_add(amount_penalty_msat)
653 /// Returns the lower bound of the channel liquidity balance in this direction.
654 fn min_liquidity_msat(&self) -> u64 {
655 self.decayed_offset_msat(*self.min_liquidity_offset_msat)
658 /// Returns the upper bound of the channel liquidity balance in this direction.
659 fn max_liquidity_msat(&self) -> u64 {
661 .checked_sub(self.decayed_offset_msat(*self.max_liquidity_offset_msat))
665 fn decayed_offset_msat(&self, offset_msat: u64) -> u64 {
666 self.now.duration_since(*self.last_updated).as_secs()
667 .checked_div(self.half_life.as_secs())
668 .and_then(|decays| offset_msat.checked_shr(decays as u32))
673 impl<L: DerefMut<Target = u64>, T: Time, U: DerefMut<Target = T>> DirectedChannelLiquidity<L, T, U> {
674 /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat`.
675 fn failed_at_channel<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
676 if amount_msat < self.max_liquidity_msat() {
677 log_debug!(logger, "Setting max liquidity of {} to {}", chan_descr, amount_msat);
678 self.set_max_liquidity_msat(amount_msat);
680 log_trace!(logger, "Max liquidity of {} already more than {}", chan_descr, amount_msat);
684 /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat` downstream.
685 fn failed_downstream<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
686 if amount_msat > self.min_liquidity_msat() {
687 log_debug!(logger, "Setting min liquidity of {} to {}", chan_descr, amount_msat);
688 self.set_min_liquidity_msat(amount_msat);
690 log_trace!(logger, "Min liquidity of {} already less than {}", chan_descr, amount_msat);
694 /// Adjusts the channel liquidity balance bounds when successfully routing `amount_msat`.
695 fn successful<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
696 let max_liquidity_msat = self.max_liquidity_msat().checked_sub(amount_msat).unwrap_or(0);
697 log_debug!(logger, "Subtracting {} from max liquidity of {} (setting it to {})", amount_msat, chan_descr, max_liquidity_msat);
698 self.set_max_liquidity_msat(max_liquidity_msat);
701 /// Adjusts the lower bound of the channel liquidity balance in this direction.
702 fn set_min_liquidity_msat(&mut self, amount_msat: u64) {
703 *self.min_liquidity_offset_msat = amount_msat;
704 *self.max_liquidity_offset_msat = if amount_msat > self.max_liquidity_msat() {
707 self.decayed_offset_msat(*self.max_liquidity_offset_msat)
709 *self.last_updated = self.now;
712 /// Adjusts the upper bound of the channel liquidity balance in this direction.
713 fn set_max_liquidity_msat(&mut self, amount_msat: u64) {
714 *self.max_liquidity_offset_msat = self.capacity_msat.checked_sub(amount_msat).unwrap_or(0);
715 *self.min_liquidity_offset_msat = if amount_msat < self.min_liquidity_msat() {
718 self.decayed_offset_msat(*self.min_liquidity_offset_msat)
720 *self.last_updated = self.now;
724 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Score for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
725 fn channel_penalty_msat(
726 &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage
728 if let Some(penalty) = self.params.manual_node_penalties.get(target) {
732 let mut anti_probing_penalty_msat = 0;
733 match usage.effective_capacity {
734 EffectiveCapacity::ExactLiquidity { liquidity_msat } => {
735 if usage.amount_msat > liquidity_msat {
736 return u64::max_value();
738 return self.params.base_penalty_msat;
741 EffectiveCapacity::Total { capacity_msat, htlc_maximum_msat: Some(htlc_maximum_msat) } => {
742 if htlc_maximum_msat >= capacity_msat/2 {
743 anti_probing_penalty_msat = self.params.anti_probing_penalty_msat;
749 let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
750 let amount_msat = usage.amount_msat;
751 let capacity_msat = usage.effective_capacity.as_msat()
752 .saturating_sub(usage.inflight_htlc_msat);
753 self.channel_liquidities
754 .get(&short_channel_id)
755 .unwrap_or(&ChannelLiquidity::new())
756 .as_directed(source, target, capacity_msat, liquidity_offset_half_life)
757 .penalty_msat(amount_msat, &self.params)
758 .saturating_add(anti_probing_penalty_msat)
761 fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
762 let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
763 let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
764 log_trace!(self.logger, "Scoring path through to SCID {} as having failed at {} msat", short_channel_id, amount_msat);
765 let network_graph = self.network_graph.read_only();
766 for (hop_idx, hop) in path.iter().enumerate() {
767 let target = NodeId::from_pubkey(&hop.pubkey);
768 let channel_directed_from_source = network_graph.channels()
769 .get(&hop.short_channel_id)
770 .and_then(|channel| channel.as_directed_to(&target));
772 if hop.short_channel_id == short_channel_id && hop_idx == 0 {
773 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);
776 // Only score announced channels.
777 if let Some((channel, source)) = channel_directed_from_source {
778 let capacity_msat = channel.effective_capacity().as_msat();
779 if hop.short_channel_id == short_channel_id {
780 self.channel_liquidities
781 .entry(hop.short_channel_id)
782 .or_insert_with(ChannelLiquidity::new)
783 .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life)
784 .failed_at_channel(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
788 self.channel_liquidities
789 .entry(hop.short_channel_id)
790 .or_insert_with(ChannelLiquidity::new)
791 .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life)
792 .failed_downstream(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
794 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).",
795 hop.short_channel_id);
800 fn payment_path_successful(&mut self, path: &[&RouteHop]) {
801 let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
802 let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
803 log_trace!(self.logger, "Scoring path through SCID {} as having succeeded at {} msat.",
804 path.split_last().map(|(hop, _)| hop.short_channel_id).unwrap_or(0), amount_msat);
805 let network_graph = self.network_graph.read_only();
807 let target = NodeId::from_pubkey(&hop.pubkey);
808 let channel_directed_from_source = network_graph.channels()
809 .get(&hop.short_channel_id)
810 .and_then(|channel| channel.as_directed_to(&target));
812 // Only score announced channels.
813 if let Some((channel, source)) = channel_directed_from_source {
814 let capacity_msat = channel.effective_capacity().as_msat();
815 self.channel_liquidities
816 .entry(hop.short_channel_id)
817 .or_insert_with(ChannelLiquidity::new)
818 .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life)
819 .successful(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
821 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).",
822 hop.short_channel_id);
829 const BITS: u32 = 64;
830 const HIGHEST_BIT: u32 = BITS - 1;
831 const LOWER_BITS: u32 = 6;
832 pub(super) const LOWER_BITS_BOUND: u64 = 1 << LOWER_BITS;
833 const LOWER_BITMASK: u64 = (1 << LOWER_BITS) - 1;
835 /// Look-up table for `log10(x) * 2048` where row `i` is used for each `x` having `i` as the
836 /// most significant bit. The next 4 bits of `x`, if applicable, are used for the second index.
837 const LOG10_TIMES_2048: [[u16; (LOWER_BITS_BOUND) as usize]; BITS as usize] = [
838 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
839 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
840 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
841 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
842 [617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
843 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
844 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977,
845 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977],
846 [1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233,
847 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431,
848 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594,
849 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731],
850 [1850, 1850, 1850, 1850, 1850, 1850, 1850, 1850, 1954, 1954, 1954, 1954, 1954, 1954, 1954, 1954,
851 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2133, 2133, 2133, 2133, 2133, 2133, 2133, 2133,
852 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2281, 2281, 2281, 2281, 2281, 2281, 2281, 2281,
853 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2409, 2409, 2409, 2409, 2409, 2409, 2409, 2409],
854 [2466, 2466, 2466, 2466, 2520, 2520, 2520, 2520, 2571, 2571, 2571, 2571, 2619, 2619, 2619, 2619,
855 2665, 2665, 2665, 2665, 2708, 2708, 2708, 2708, 2749, 2749, 2749, 2749, 2789, 2789, 2789, 2789,
856 2827, 2827, 2827, 2827, 2863, 2863, 2863, 2863, 2898, 2898, 2898, 2898, 2931, 2931, 2931, 2931,
857 2964, 2964, 2964, 2964, 2995, 2995, 2995, 2995, 3025, 3025, 3025, 3025, 3054, 3054, 3054, 3054],
858 [3083, 3083, 3110, 3110, 3136, 3136, 3162, 3162, 3187, 3187, 3212, 3212, 3235, 3235, 3259, 3259,
859 3281, 3281, 3303, 3303, 3324, 3324, 3345, 3345, 3366, 3366, 3386, 3386, 3405, 3405, 3424, 3424,
860 3443, 3443, 3462, 3462, 3479, 3479, 3497, 3497, 3514, 3514, 3531, 3531, 3548, 3548, 3564, 3564,
861 3580, 3580, 3596, 3596, 3612, 3612, 3627, 3627, 3642, 3642, 3656, 3656, 3671, 3671, 3685, 3685],
862 [3699, 3713, 3726, 3740, 3753, 3766, 3779, 3791, 3804, 3816, 3828, 3840, 3852, 3864, 3875, 3886,
863 3898, 3909, 3919, 3930, 3941, 3951, 3962, 3972, 3982, 3992, 4002, 4012, 4022, 4031, 4041, 4050,
864 4060, 4069, 4078, 4087, 4096, 4105, 4114, 4122, 4131, 4139, 4148, 4156, 4164, 4173, 4181, 4189,
865 4197, 4205, 4213, 4220, 4228, 4236, 4243, 4251, 4258, 4266, 4273, 4280, 4287, 4294, 4302, 4309],
866 [4316, 4329, 4343, 4356, 4369, 4382, 4395, 4408, 4420, 4433, 4445, 4457, 4468, 4480, 4492, 4503,
867 4514, 4525, 4536, 4547, 4557, 4568, 4578, 4589, 4599, 4609, 4619, 4629, 4638, 4648, 4657, 4667,
868 4676, 4685, 4695, 4704, 4713, 4721, 4730, 4739, 4747, 4756, 4764, 4773, 4781, 4789, 4797, 4805,
869 4813, 4821, 4829, 4837, 4845, 4852, 4860, 4867, 4875, 4882, 4889, 4897, 4904, 4911, 4918, 4925],
870 [4932, 4946, 4959, 4973, 4986, 4999, 5012, 5024, 5037, 5049, 5061, 5073, 5085, 5097, 5108, 5119,
871 5131, 5142, 5153, 5163, 5174, 5184, 5195, 5205, 5215, 5225, 5235, 5245, 5255, 5264, 5274, 5283,
872 5293, 5302, 5311, 5320, 5329, 5338, 5347, 5355, 5364, 5372, 5381, 5389, 5397, 5406, 5414, 5422,
873 5430, 5438, 5446, 5453, 5461, 5469, 5476, 5484, 5491, 5499, 5506, 5513, 5520, 5527, 5535, 5542],
874 [5549, 5562, 5576, 5589, 5603, 5615, 5628, 5641, 5653, 5666, 5678, 5690, 5701, 5713, 5725, 5736,
875 5747, 5758, 5769, 5780, 5790, 5801, 5811, 5822, 5832, 5842, 5852, 5862, 5871, 5881, 5890, 5900,
876 5909, 5918, 5928, 5937, 5946, 5954, 5963, 5972, 5980, 5989, 5997, 6006, 6014, 6022, 6030, 6038,
877 6046, 6054, 6062, 6070, 6078, 6085, 6093, 6100, 6108, 6115, 6122, 6130, 6137, 6144, 6151, 6158],
878 [6165, 6179, 6192, 6206, 6219, 6232, 6245, 6257, 6270, 6282, 6294, 6306, 6318, 6330, 6341, 6352,
879 6364, 6375, 6386, 6396, 6407, 6417, 6428, 6438, 6448, 6458, 6468, 6478, 6488, 6497, 6507, 6516,
880 6526, 6535, 6544, 6553, 6562, 6571, 6580, 6588, 6597, 6605, 6614, 6622, 6630, 6639, 6647, 6655,
881 6663, 6671, 6679, 6686, 6694, 6702, 6709, 6717, 6724, 6732, 6739, 6746, 6753, 6761, 6768, 6775],
882 [6782, 6795, 6809, 6822, 6836, 6849, 6861, 6874, 6886, 6899, 6911, 6923, 6934, 6946, 6958, 6969,
883 6980, 6991, 7002, 7013, 7023, 7034, 7044, 7055, 7065, 7075, 7085, 7095, 7104, 7114, 7124, 7133,
884 7142, 7151, 7161, 7170, 7179, 7187, 7196, 7205, 7213, 7222, 7230, 7239, 7247, 7255, 7263, 7271,
885 7279, 7287, 7295, 7303, 7311, 7318, 7326, 7333, 7341, 7348, 7355, 7363, 7370, 7377, 7384, 7391],
886 [7398, 7412, 7425, 7439, 7452, 7465, 7478, 7490, 7503, 7515, 7527, 7539, 7551, 7563, 7574, 7585,
887 7597, 7608, 7619, 7629, 7640, 7651, 7661, 7671, 7681, 7691, 7701, 7711, 7721, 7731, 7740, 7749,
888 7759, 7768, 7777, 7786, 7795, 7804, 7813, 7821, 7830, 7838, 7847, 7855, 7864, 7872, 7880, 7888,
889 7896, 7904, 7912, 7919, 7927, 7935, 7942, 7950, 7957, 7965, 7972, 7979, 7986, 7994, 8001, 8008],
890 [8015, 8028, 8042, 8055, 8069, 8082, 8094, 8107, 8119, 8132, 8144, 8156, 8167, 8179, 8191, 8202,
891 8213, 8224, 8235, 8246, 8256, 8267, 8277, 8288, 8298, 8308, 8318, 8328, 8337, 8347, 8357, 8366,
892 8375, 8384, 8394, 8403, 8412, 8420, 8429, 8438, 8446, 8455, 8463, 8472, 8480, 8488, 8496, 8504,
893 8512, 8520, 8528, 8536, 8544, 8551, 8559, 8566, 8574, 8581, 8588, 8596, 8603, 8610, 8617, 8624],
894 [8631, 8645, 8659, 8672, 8685, 8698, 8711, 8723, 8736, 8748, 8760, 8772, 8784, 8796, 8807, 8818,
895 8830, 8841, 8852, 8862, 8873, 8884, 8894, 8904, 8914, 8924, 8934, 8944, 8954, 8964, 8973, 8982,
896 8992, 9001, 9010, 9019, 9028, 9037, 9046, 9054, 9063, 9071, 9080, 9088, 9097, 9105, 9113, 9121,
897 9129, 9137, 9145, 9152, 9160, 9168, 9175, 9183, 9190, 9198, 9205, 9212, 9219, 9227, 9234, 9241],
898 [9248, 9261, 9275, 9288, 9302, 9315, 9327, 9340, 9352, 9365, 9377, 9389, 9400, 9412, 9424, 9435,
899 9446, 9457, 9468, 9479, 9490, 9500, 9510, 9521, 9531, 9541, 9551, 9561, 9570, 9580, 9590, 9599,
900 9608, 9617, 9627, 9636, 9645, 9653, 9662, 9671, 9679, 9688, 9696, 9705, 9713, 9721, 9729, 9737,
901 9745, 9753, 9761, 9769, 9777, 9784, 9792, 9799, 9807, 9814, 9821, 9829, 9836, 9843, 9850, 9857],
902 [9864, 9878, 9892, 9905, 9918, 9931, 9944, 9956, 9969, 9981, 9993, 10005, 10017, 10029, 10040, 10051,
903 10063, 10074, 10085, 10095, 10106, 10117, 10127, 10137, 10147, 10157, 10167, 10177, 10187, 10197, 10206, 10215,
904 10225, 10234, 10243, 10252, 10261, 10270, 10279, 10287, 10296, 10304, 10313, 10321, 10330, 10338, 10346, 10354,
905 10362, 10370, 10378, 10385, 10393, 10401, 10408, 10416, 10423, 10431, 10438, 10445, 10452, 10460, 10467, 10474],
906 [10481, 10494, 10508, 10521, 10535, 10548, 10560, 10573, 10585, 10598, 10610, 10622, 10634, 10645, 10657, 10668,
907 10679, 10690, 10701, 10712, 10723, 10733, 10743, 10754, 10764, 10774, 10784, 10794, 10803, 10813, 10823, 10832,
908 10841, 10851, 10860, 10869, 10878, 10886, 10895, 10904, 10912, 10921, 10929, 10938, 10946, 10954, 10962, 10970,
909 10978, 10986, 10994, 11002, 11010, 11017, 11025, 11032, 11040, 11047, 11054, 11062, 11069, 11076, 11083, 11090],
910 [11097, 11111, 11125, 11138, 11151, 11164, 11177, 11189, 11202, 11214, 11226, 11238, 11250, 11262, 11273, 11284,
911 11296, 11307, 11318, 11328, 11339, 11350, 11360, 11370, 11380, 11390, 11400, 11410, 11420, 11430, 11439, 11448,
912 11458, 11467, 11476, 11485, 11494, 11503, 11512, 11520, 11529, 11538, 11546, 11554, 11563, 11571, 11579, 11587,
913 11595, 11603, 11611, 11618, 11626, 11634, 11641, 11649, 11656, 11664, 11671, 11678, 11685, 11693, 11700, 11707],
914 [11714, 11727, 11741, 11754, 11768, 11781, 11793, 11806, 11818, 11831, 11843, 11855, 11867, 11878, 11890, 11901,
915 11912, 11923, 11934, 11945, 11956, 11966, 11976, 11987, 11997, 12007, 12017, 12027, 12036, 12046, 12056, 12065,
916 12074, 12084, 12093, 12102, 12111, 12119, 12128, 12137, 12146, 12154, 12162, 12171, 12179, 12187, 12195, 12203,
917 12211, 12219, 12227, 12235, 12243, 12250, 12258, 12265, 12273, 12280, 12287, 12295, 12302, 12309, 12316, 12323],
918 [12330, 12344, 12358, 12371, 12384, 12397, 12410, 12423, 12435, 12447, 12459, 12471, 12483, 12495, 12506, 12517,
919 12529, 12540, 12551, 12561, 12572, 12583, 12593, 12603, 12613, 12623, 12633, 12643, 12653, 12663, 12672, 12682,
920 12691, 12700, 12709, 12718, 12727, 12736, 12745, 12753, 12762, 12771, 12779, 12787, 12796, 12804, 12812, 12820,
921 12828, 12836, 12844, 12851, 12859, 12867, 12874, 12882, 12889, 12897, 12904, 12911, 12918, 12926, 12933, 12940],
922 [12947, 12960, 12974, 12987, 13001, 13014, 13026, 13039, 13051, 13064, 13076, 13088, 13100, 13111, 13123, 13134,
923 13145, 13156, 13167, 13178, 13189, 13199, 13209, 13220, 13230, 13240, 13250, 13260, 13269, 13279, 13289, 13298,
924 13307, 13317, 13326, 13335, 13344, 13352, 13361, 13370, 13379, 13387, 13395, 13404, 13412, 13420, 13428, 13436,
925 13444, 13452, 13460, 13468, 13476, 13483, 13491, 13498, 13506, 13513, 13521, 13528, 13535, 13542, 13549, 13556],
926 [13563, 13577, 13591, 13604, 13617, 13630, 13643, 13656, 13668, 13680, 13692, 13704, 13716, 13728, 13739, 13750,
927 13762, 13773, 13784, 13794, 13805, 13816, 13826, 13836, 13846, 13857, 13866, 13876, 13886, 13896, 13905, 13915,
928 13924, 13933, 13942, 13951, 13960, 13969, 13978, 13986, 13995, 14004, 14012, 14020, 14029, 14037, 14045, 14053,
929 14061, 14069, 14077, 14084, 14092, 14100, 14107, 14115, 14122, 14130, 14137, 14144, 14151, 14159, 14166, 14173],
930 [14180, 14194, 14207, 14220, 14234, 14247, 14259, 14272, 14284, 14297, 14309, 14321, 14333, 14344, 14356, 14367,
931 14378, 14389, 14400, 14411, 14422, 14432, 14443, 14453, 14463, 14473, 14483, 14493, 14502, 14512, 14522, 14531,
932 14540, 14550, 14559, 14568, 14577, 14586, 14594, 14603, 14612, 14620, 14628, 14637, 14645, 14653, 14661, 14669,
933 14677, 14685, 14693, 14701, 14709, 14716, 14724, 14731, 14739, 14746, 14754, 14761, 14768, 14775, 14782, 14789],
934 [14796, 14810, 14824, 14837, 14850, 14863, 14876, 14889, 14901, 14913, 14925, 14937, 14949, 14961, 14972, 14984,
935 14995, 15006, 15017, 15027, 15038, 15049, 15059, 15069, 15079, 15090, 15099, 15109, 15119, 15129, 15138, 15148,
936 15157, 15166, 15175, 15184, 15193, 15202, 15211, 15219, 15228, 15237, 15245, 15253, 15262, 15270, 15278, 15286,
937 15294, 15302, 15310, 15317, 15325, 15333, 15340, 15348, 15355, 15363, 15370, 15377, 15384, 15392, 15399, 15406],
938 [15413, 15427, 15440, 15453, 15467, 15480, 15492, 15505, 15517, 15530, 15542, 15554, 15566, 15577, 15589, 15600,
939 15611, 15622, 15633, 15644, 15655, 15665, 15676, 15686, 15696, 15706, 15716, 15726, 15736, 15745, 15755, 15764,
940 15773, 15783, 15792, 15801, 15810, 15819, 15827, 15836, 15845, 15853, 15862, 15870, 15878, 15886, 15894, 15903,
941 15910, 15918, 15926, 15934, 15942, 15949, 15957, 15964, 15972, 15979, 15987, 15994, 16001, 16008, 16015, 16022],
942 [16029, 16043, 16057, 16070, 16083, 16096, 16109, 16122, 16134, 16146, 16158, 16170, 16182, 16194, 16205, 16217,
943 16228, 16239, 16250, 16260, 16271, 16282, 16292, 16302, 16312, 16323, 16332, 16342, 16352, 16362, 16371, 16381,
944 16390, 16399, 16408, 16417, 16426, 16435, 16444, 16452, 16461, 16470, 16478, 16486, 16495, 16503, 16511, 16519,
945 16527, 16535, 16543, 16550, 16558, 16566, 16573, 16581, 16588, 16596, 16603, 16610, 16618, 16625, 16632, 16639],
946 [16646, 16660, 16673, 16686, 16700, 16713, 16725, 16738, 16751, 16763, 16775, 16787, 16799, 16810, 16822, 16833,
947 16844, 16855, 16866, 16877, 16888, 16898, 16909, 16919, 16929, 16939, 16949, 16959, 16969, 16978, 16988, 16997,
948 17006, 17016, 17025, 17034, 17043, 17052, 17060, 17069, 17078, 17086, 17095, 17103, 17111, 17119, 17127, 17136,
949 17143, 17151, 17159, 17167, 17175, 17182, 17190, 17197, 17205, 17212, 17220, 17227, 17234, 17241, 17248, 17255],
950 [17262, 17276, 17290, 17303, 17316, 17329, 17342, 17355, 17367, 17379, 17391, 17403, 17415, 17427, 17438, 17450,
951 17461, 17472, 17483, 17493, 17504, 17515, 17525, 17535, 17546, 17556, 17565, 17575, 17585, 17595, 17604, 17614,
952 17623, 17632, 17641, 17650, 17659, 17668, 17677, 17685, 17694, 17703, 17711, 17719, 17728, 17736, 17744, 17752,
953 17760, 17768, 17776, 17784, 17791, 17799, 17806, 17814, 17821, 17829, 17836, 17843, 17851, 17858, 17865, 17872],
954 [17879, 17893, 17906, 17920, 17933, 17946, 17958, 17971, 17984, 17996, 18008, 18020, 18032, 18043, 18055, 18066,
955 18077, 18088, 18099, 18110, 18121, 18131, 18142, 18152, 18162, 18172, 18182, 18192, 18202, 18211, 18221, 18230,
956 18239, 18249, 18258, 18267, 18276, 18285, 18293, 18302, 18311, 18319, 18328, 18336, 18344, 18352, 18360, 18369,
957 18377, 18384, 18392, 18400, 18408, 18415, 18423, 18430, 18438, 18445, 18453, 18460, 18467, 18474, 18481, 18488],
958 [18495, 18509, 18523, 18536, 18549, 18562, 18575, 18588, 18600, 18612, 18624, 18636, 18648, 18660, 18671, 18683,
959 18694, 18705, 18716, 18726, 18737, 18748, 18758, 18768, 18779, 18789, 18799, 18808, 18818, 18828, 18837, 18847,
960 18856, 18865, 18874, 18883, 18892, 18901, 18910, 18919, 18927, 18936, 18944, 18952, 18961, 18969, 18977, 18985,
961 18993, 19001, 19009, 19017, 19024, 19032, 19039, 19047, 19054, 19062, 19069, 19076, 19084, 19091, 19098, 19105],
962 [19112, 19126, 19139, 19153, 19166, 19179, 19191, 19204, 19217, 19229, 19241, 19253, 19265, 19276, 19288, 19299,
963 19310, 19321, 19332, 19343, 19354, 19364, 19375, 19385, 19395, 19405, 19415, 19425, 19435, 19444, 19454, 19463,
964 19472, 19482, 19491, 19500, 19509, 19518, 19526, 19535, 19544, 19552, 19561, 19569, 19577, 19585, 19594, 19602,
965 19610, 19617, 19625, 19633, 19641, 19648, 19656, 19663, 19671, 19678, 19686, 19693, 19700, 19707, 19714, 19721],
966 [19728, 19742, 19756, 19769, 19782, 19795, 19808, 19821, 19833, 19845, 19857, 19869, 19881, 19893, 19904, 19916,
967 19927, 19938, 19949, 19960, 19970, 19981, 19991, 20001, 20012, 20022, 20032, 20041, 20051, 20061, 20070, 20080,
968 20089, 20098, 20107, 20116, 20125, 20134, 20143, 20152, 20160, 20169, 20177, 20185, 20194, 20202, 20210, 20218,
969 20226, 20234, 20242, 20250, 20257, 20265, 20272, 20280, 20287, 20295, 20302, 20309, 20317, 20324, 20331, 20338],
970 [20345, 20359, 20372, 20386, 20399, 20412, 20425, 20437, 20450, 20462, 20474, 20486, 20498, 20509, 20521, 20532,
971 20543, 20554, 20565, 20576, 20587, 20597, 20608, 20618, 20628, 20638, 20648, 20658, 20668, 20677, 20687, 20696,
972 20705, 20715, 20724, 20733, 20742, 20751, 20759, 20768, 20777, 20785, 20794, 20802, 20810, 20818, 20827, 20835,
973 20843, 20850, 20858, 20866, 20874, 20881, 20889, 20896, 20904, 20911, 20919, 20926, 20933, 20940, 20947, 20954],
974 [20961, 20975, 20989, 21002, 21015, 21028, 21041, 21054, 21066, 21078, 21090, 21102, 21114, 21126, 21137, 21149,
975 21160, 21171, 21182, 21193, 21203, 21214, 21224, 21234, 21245, 21255, 21265, 21274, 21284, 21294, 21303, 21313,
976 21322, 21331, 21340, 21349, 21358, 21367, 21376, 21385, 21393, 21402, 21410, 21418, 21427, 21435, 21443, 21451,
977 21459, 21467, 21475, 21483, 21490, 21498, 21505, 21513, 21520, 21528, 21535, 21542, 21550, 21557, 21564, 21571],
978 [21578, 21592, 21605, 21619, 21632, 21645, 21658, 21670, 21683, 21695, 21707, 21719, 21731, 21742, 21754, 21765,
979 21776, 21787, 21798, 21809, 21820, 21830, 21841, 21851, 21861, 21871, 21881, 21891, 21901, 21910, 21920, 21929,
980 21938, 21948, 21957, 21966, 21975, 21984, 21992, 22001, 22010, 22018, 22027, 22035, 22043, 22051, 22060, 22068,
981 22076, 22083, 22091, 22099, 22107, 22114, 22122, 22129, 22137, 22144, 22152, 22159, 22166, 22173, 22180, 22187],
982 [22194, 22208, 22222, 22235, 22248, 22261, 22274, 22287, 22299, 22311, 22323, 22335, 22347, 22359, 22370, 22382,
983 22393, 22404, 22415, 22426, 22436, 22447, 22457, 22467, 22478, 22488, 22498, 22507, 22517, 22527, 22536, 22546,
984 22555, 22564, 22573, 22582, 22591, 22600, 22609, 22618, 22626, 22635, 22643, 22651, 22660, 22668, 22676, 22684,
985 22692, 22700, 22708, 22716, 22723, 22731, 22738, 22746, 22753, 22761, 22768, 22775, 22783, 22790, 22797, 22804],
986 [22811, 22825, 22838, 22852, 22865, 22878, 22891, 22903, 22916, 22928, 22940, 22952, 22964, 22975, 22987, 22998,
987 23009, 23020, 23031, 23042, 23053, 23063, 23074, 23084, 23094, 23104, 23114, 23124, 23134, 23143, 23153, 23162,
988 23171, 23181, 23190, 23199, 23208, 23217, 23225, 23234, 23243, 23251, 23260, 23268, 23276, 23284, 23293, 23301,
989 23309, 23316, 23324, 23332, 23340, 23347, 23355, 23363, 23370, 23377, 23385, 23392, 23399, 23406, 23413, 23420],
990 [23427, 23441, 23455, 23468, 23481, 23494, 23507, 23520, 23532, 23544, 23556, 23568, 23580, 23592, 23603, 23615,
991 23626, 23637, 23648, 23659, 23669, 23680, 23690, 23700, 23711, 23721, 23731, 23740, 23750, 23760, 23769, 23779,
992 23788, 23797, 23806, 23815, 23824, 23833, 23842, 23851, 23859, 23868, 23876, 23884, 23893, 23901, 23909, 23917,
993 23925, 23933, 23941, 23949, 23956, 23964, 23972, 23979, 23986, 23994, 24001, 24008, 24016, 24023, 24030, 24037],
994 [24044, 24058, 24071, 24085, 24098, 24111, 24124, 24136, 24149, 24161, 24173, 24185, 24197, 24208, 24220, 24231,
995 24242, 24253, 24264, 24275, 24286, 24296, 24307, 24317, 24327, 24337, 24347, 24357, 24367, 24376, 24386, 24395,
996 24405, 24414, 24423, 24432, 24441, 24450, 24458, 24467, 24476, 24484, 24493, 24501, 24509, 24517, 24526, 24534,
997 24542, 24550, 24557, 24565, 24573, 24580, 24588, 24596, 24603, 24610, 24618, 24625, 24632, 24639, 24646, 24653],
998 [24660, 24674, 24688, 24701, 24714, 24727, 24740, 24753, 24765, 24777, 24790, 24801, 24813, 24825, 24836, 24848,
999 24859, 24870, 24881, 24892, 24902, 24913, 24923, 24933, 24944, 24954, 24964, 24973, 24983, 24993, 25002, 25012,
1000 25021, 25030, 25039, 25048, 25057, 25066, 25075, 25084, 25092, 25101, 25109, 25117, 25126, 25134, 25142, 25150,
1001 25158, 25166, 25174, 25182, 25189, 25197, 25205, 25212, 25219, 25227, 25234, 25241, 25249, 25256, 25263, 25270],
1002 [25277, 25291, 25304, 25318, 25331, 25344, 25357, 25369, 25382, 25394, 25406, 25418, 25430, 25441, 25453, 25464,
1003 25475, 25486, 25497, 25508, 25519, 25529, 25540, 25550, 25560, 25570, 25580, 25590, 25600, 25609, 25619, 25628,
1004 25638, 25647, 25656, 25665, 25674, 25683, 25691, 25700, 25709, 25717, 25726, 25734, 25742, 25750, 25759, 25767,
1005 25775, 25783, 25790, 25798, 25806, 25813, 25821, 25829, 25836, 25843, 25851, 25858, 25865, 25872, 25879, 25886],
1006 [25893, 25907, 25921, 25934, 25947, 25960, 25973, 25986, 25998, 26010, 26023, 26034, 26046, 26058, 26069, 26081,
1007 26092, 26103, 26114, 26125, 26135, 26146, 26156, 26166, 26177, 26187, 26197, 26206, 26216, 26226, 26235, 26245,
1008 26254, 26263, 26272, 26281, 26290, 26299, 26308, 26317, 26325, 26334, 26342, 26351, 26359, 26367, 26375, 26383,
1009 26391, 26399, 26407, 26415, 26422, 26430, 26438, 26445, 26453, 26460, 26467, 26474, 26482, 26489, 26496, 26503],
1010 [26510, 26524, 26537, 26551, 26564, 26577, 26590, 26602, 26615, 26627, 26639, 26651, 26663, 26674, 26686, 26697,
1011 26708, 26719, 26730, 26741, 26752, 26762, 26773, 26783, 26793, 26803, 26813, 26823, 26833, 26842, 26852, 26861,
1012 26871, 26880, 26889, 26898, 26907, 26916, 26924, 26933, 26942, 26950, 26959, 26967, 26975, 26983, 26992, 27000,
1013 27008, 27016, 27023, 27031, 27039, 27046, 27054, 27062, 27069, 27076, 27084, 27091, 27098, 27105, 27112, 27119],
1014 [27126, 27140, 27154, 27167, 27180, 27193, 27206, 27219, 27231, 27243, 27256, 27267, 27279, 27291, 27302, 27314,
1015 27325, 27336, 27347, 27358, 27368, 27379, 27389, 27399, 27410, 27420, 27430, 27439, 27449, 27459, 27468, 27478,
1016 27487, 27496, 27505, 27514, 27523, 27532, 27541, 27550, 27558, 27567, 27575, 27584, 27592, 27600, 27608, 27616,
1017 27624, 27632, 27640, 27648, 27655, 27663, 27671, 27678, 27686, 27693, 27700, 27707, 27715, 27722, 27729, 27736],
1018 [27743, 27757, 27770, 27784, 27797, 27810, 27823, 27835, 27848, 27860, 27872, 27884, 27896, 27907, 27919, 27930,
1019 27941, 27952, 27963, 27974, 27985, 27995, 28006, 28016, 28026, 28036, 28046, 28056, 28066, 28075, 28085, 28094,
1020 28104, 28113, 28122, 28131, 28140, 28149, 28157, 28166, 28175, 28183, 28192, 28200, 28208, 28217, 28225, 28233,
1021 28241, 28249, 28256, 28264, 28272, 28280, 28287, 28295, 28302, 28309, 28317, 28324, 28331, 28338, 28345, 28352],
1022 [28359, 28373, 28387, 28400, 28413, 28426, 28439, 28452, 28464, 28476, 28489, 28501, 28512, 28524, 28535, 28547,
1023 28558, 28569, 28580, 28591, 28601, 28612, 28622, 28633, 28643, 28653, 28663, 28672, 28682, 28692, 28701, 28711,
1024 28720, 28729, 28738, 28747, 28756, 28765, 28774, 28783, 28791, 28800, 28808, 28817, 28825, 28833, 28841, 28849,
1025 28857, 28865, 28873, 28881, 28888, 28896, 28904, 28911, 28919, 28926, 28933, 28941, 28948, 28955, 28962, 28969],
1026 [28976, 28990, 29003, 29017, 29030, 29043, 29056, 29068, 29081, 29093, 29105, 29117, 29129, 29140, 29152, 29163,
1027 29174, 29185, 29196, 29207, 29218, 29228, 29239, 29249, 29259, 29269, 29279, 29289, 29299, 29308, 29318, 29327,
1028 29337, 29346, 29355, 29364, 29373, 29382, 29390, 29399, 29408, 29416, 29425, 29433, 29441, 29450, 29458, 29466,
1029 29474, 29482, 29489, 29497, 29505, 29513, 29520, 29528, 29535, 29542, 29550, 29557, 29564, 29571, 29578, 29585],
1030 [29592, 29606, 29620, 29633, 29646, 29659, 29672, 29685, 29697, 29709, 29722, 29734, 29745, 29757, 29768, 29780,
1031 29791, 29802, 29813, 29824, 29834, 29845, 29855, 29866, 29876, 29886, 29896, 29906, 29915, 29925, 29934, 29944,
1032 29953, 29962, 29971, 29980, 29989, 29998, 30007, 30016, 30024, 30033, 30041, 30050, 30058, 30066, 30074, 30082,
1033 30090, 30098, 30106, 30114, 30121, 30129, 30137, 30144, 30152, 30159, 30166, 30174, 30181, 30188, 30195, 30202],
1034 [30209, 30223, 30236, 30250, 30263, 30276, 30289, 30301, 30314, 30326, 30338, 30350, 30362, 30373, 30385, 30396,
1035 30407, 30418, 30429, 30440, 30451, 30461, 30472, 30482, 30492, 30502, 30512, 30522, 30532, 30541, 30551, 30560,
1036 30570, 30579, 30588, 30597, 30606, 30615, 30624, 30632, 30641, 30649, 30658, 30666, 30674, 30683, 30691, 30699,
1037 30707, 30715, 30722, 30730, 30738, 30746, 30753, 30761, 30768, 30775, 30783, 30790, 30797, 30804, 30811, 30818],
1038 [30825, 30839, 30853, 30866, 30879, 30892, 30905, 30918, 30930, 30943, 30955, 30967, 30978, 30990, 31001, 31013,
1039 31024, 31035, 31046, 31057, 31067, 31078, 31088, 31099, 31109, 31119, 31129, 31139, 31148, 31158, 31167, 31177,
1040 31186, 31195, 31204, 31213, 31222, 31231, 31240, 31249, 31257, 31266, 31274, 31283, 31291, 31299, 31307, 31315,
1041 31323, 31331, 31339, 31347, 31354, 31362, 31370, 31377, 31385, 31392, 31399, 31407, 31414, 31421, 31428, 31435],
1042 [31442, 31456, 31469, 31483, 31496, 31509, 31522, 31534, 31547, 31559, 31571, 31583, 31595, 31606, 31618, 31629,
1043 31640, 31652, 31662, 31673, 31684, 31694, 31705, 31715, 31725, 31735, 31745, 31755, 31765, 31774, 31784, 31793,
1044 31803, 31812, 31821, 31830, 31839, 31848, 31857, 31865, 31874, 31882, 31891, 31899, 31907, 31916, 31924, 31932,
1045 31940, 31948, 31955, 31963, 31971, 31979, 31986, 31994, 32001, 32008, 32016, 32023, 32030, 32037, 32044, 32052],
1046 [32058, 32072, 32086, 32099, 32112, 32125, 32138, 32151, 32163, 32176, 32188, 32200, 32211, 32223, 32234, 32246,
1047 32257, 32268, 32279, 32290, 32300, 32311, 32321, 32332, 32342, 32352, 32362, 32372, 32381, 32391, 32400, 32410,
1048 32419, 32428, 32437, 32446, 32455, 32464, 32473, 32482, 32490, 32499, 32507, 32516, 32524, 32532, 32540, 32548,
1049 32556, 32564, 32572, 32580, 32587, 32595, 32603, 32610, 32618, 32625, 32632, 32640, 32647, 32654, 32661, 32668],
1050 [32675, 32689, 32702, 32716, 32729, 32742, 32755, 32767, 32780, 32792, 32804, 32816, 32828, 32839, 32851, 32862,
1051 32873, 32885, 32895, 32906, 32917, 32927, 32938, 32948, 32958, 32968, 32978, 32988, 32998, 33007, 33017, 33026,
1052 33036, 33045, 33054, 33063, 33072, 33081, 33090, 33098, 33107, 33115, 33124, 33132, 33140, 33149, 33157, 33165,
1053 33173, 33181, 33188, 33196, 33204, 33212, 33219, 33227, 33234, 33241, 33249, 33256, 33263, 33270, 33278, 33285],
1054 [33292, 33305, 33319, 33332, 33345, 33358, 33371, 33384, 33396, 33409, 33421, 33433, 33444, 33456, 33467, 33479,
1055 33490, 33501, 33512, 33523, 33533, 33544, 33554, 33565, 33575, 33585, 33595, 33605, 33614, 33624, 33633, 33643,
1056 33652, 33661, 33670, 33680, 33688, 33697, 33706, 33715, 33723, 33732, 33740, 33749, 33757, 33765, 33773, 33781,
1057 33789, 33797, 33805, 33813, 33820, 33828, 33836, 33843, 33851, 33858, 33865, 33873, 33880, 33887, 33894, 33901],
1058 [33908, 33922, 33935, 33949, 33962, 33975, 33988, 34000, 34013, 34025, 34037, 34049, 34061, 34072, 34084, 34095,
1059 34106, 34118, 34128, 34139, 34150, 34160, 34171, 34181, 34191, 34201, 34211, 34221, 34231, 34240, 34250, 34259,
1060 34269, 34278, 34287, 34296, 34305, 34314, 34323, 34331, 34340, 34348, 34357, 34365, 34373, 34382, 34390, 34398,
1061 34406, 34414, 34422, 34429, 34437, 34445, 34452, 34460, 34467, 34475, 34482, 34489, 34496, 34503, 34511, 34518],
1062 [34525, 34538, 34552, 34565, 34578, 34591, 34604, 34617, 34629, 34642, 34654, 34666, 34677, 34689, 34700, 34712,
1063 34723, 34734, 34745, 34756, 34766, 34777, 34787, 34798, 34808, 34818, 34828, 34838, 34847, 34857, 34866, 34876,
1064 34885, 34894, 34904, 34913, 34921, 34930, 34939, 34948, 34956, 34965, 34973, 34982, 34990, 34998, 35006, 35014,
1065 35022, 35030, 35038, 35046, 35053, 35061, 35069, 35076, 35084, 35091, 35098, 35106, 35113, 35120, 35127, 35134],
1066 [35141, 35155, 35168, 35182, 35195, 35208, 35221, 35233, 35246, 35258, 35270, 35282, 35294, 35306, 35317, 35328,
1067 35340, 35351, 35361, 35372, 35383, 35393, 35404, 35414, 35424, 35434, 35444, 35454, 35464, 35473, 35483, 35492,
1068 35502, 35511, 35520, 35529, 35538, 35547, 35556, 35564, 35573, 35581, 35590, 35598, 35606, 35615, 35623, 35631,
1069 35639, 35647, 35655, 35662, 35670, 35678, 35685, 35693, 35700, 35708, 35715, 35722, 35729, 35736, 35744, 35751],
1070 [35758, 35771, 35785, 35798, 35811, 35824, 35837, 35850, 35862, 35875, 35887, 35899, 35910, 35922, 35934, 35945,
1071 35956, 35967, 35978, 35989, 35999, 36010, 36020, 36031, 36041, 36051, 36061, 36071, 36080, 36090, 36099, 36109,
1072 36118, 36127, 36137, 36146, 36154, 36163, 36172, 36181, 36189, 36198, 36206, 36215, 36223, 36231, 36239, 36247,
1073 36255, 36263, 36271, 36279, 36287, 36294, 36302, 36309, 36317, 36324, 36331, 36339, 36346, 36353, 36360, 36367],
1074 [36374, 36388, 36401, 36415, 36428, 36441, 36454, 36466, 36479, 36491, 36503, 36515, 36527, 36539, 36550, 36561,
1075 36573, 36584, 36594, 36605, 36616, 36626, 36637, 36647, 36657, 36667, 36677, 36687, 36697, 36706, 36716, 36725,
1076 36735, 36744, 36753, 36762, 36771, 36780, 36789, 36797, 36806, 36814, 36823, 36831, 36839, 36848, 36856, 36864,
1077 36872, 36880, 36888, 36895, 36903, 36911, 36918, 36926, 36933, 36941, 36948, 36955, 36962, 36969, 36977, 36984],
1078 [36991, 37004, 37018, 37031, 37044, 37057, 37070, 37083, 37095, 37108, 37120, 37132, 37143, 37155, 37167, 37178,
1079 37189, 37200, 37211, 37222, 37232, 37243, 37253, 37264, 37274, 37284, 37294, 37304, 37313, 37323, 37332, 37342,
1080 37351, 37360, 37370, 37379, 37388, 37396, 37405, 37414, 37422, 37431, 37439, 37448, 37456, 37464, 37472, 37480,
1081 37488, 37496, 37504, 37512, 37520, 37527, 37535, 37542, 37550, 37557, 37564, 37572, 37579, 37586, 37593, 37600],
1082 [37607, 37621, 37634, 37648, 37661, 37674, 37687, 37699, 37712, 37724, 37736, 37748, 37760, 37772, 37783, 37794,
1083 37806, 37817, 37828, 37838, 37849, 37859, 37870, 37880, 37890, 37900, 37910, 37920, 37930, 37939, 37949, 37958,
1084 37968, 37977, 37986, 37995, 38004, 38013, 38022, 38030, 38039, 38047, 38056, 38064, 38072, 38081, 38089, 38097,
1085 38105, 38113, 38121, 38128, 38136, 38144, 38151, 38159, 38166, 38174, 38181, 38188, 38195, 38202, 38210, 38217],
1086 [38224, 38237, 38251, 38264, 38278, 38290, 38303, 38316, 38328, 38341, 38353, 38365, 38376, 38388, 38400, 38411,
1087 38422, 38433, 38444, 38455, 38465, 38476, 38486, 38497, 38507, 38517, 38527, 38537, 38546, 38556, 38565, 38575,
1088 38584, 38593, 38603, 38612, 38621, 38629, 38638, 38647, 38655, 38664, 38672, 38681, 38689, 38697, 38705, 38713,
1089 38721, 38729, 38737, 38745, 38753, 38760, 38768, 38775, 38783, 38790, 38797, 38805, 38812, 38819, 38826, 38833],
1090 [38840, 38854, 38867, 38881, 38894, 38907, 38920, 38932, 38945, 38957, 38969, 38981, 38993, 39005, 39016, 39027,
1091 39039, 39050, 39061, 39071, 39082, 39092, 39103, 39113, 39123, 39133, 39143, 39153, 39163, 39172, 39182, 39191,
1092 39201, 39210, 39219, 39228, 39237, 39246, 39255, 39263, 39272, 39280, 39289, 39297, 39305, 39314, 39322, 39330,
1093 39338, 39346, 39354, 39361, 39369, 39377, 39384, 39392, 39399, 39407, 39414, 39421, 39428, 39436, 39443, 39450],
1096 /// Approximate `log10(numerator / denominator) * 2048` using a look-up table.
1098 pub fn negative_log10_times_2048(numerator: u64, denominator: u64) -> u64 {
1099 // Multiply the -1 through to avoid needing to use signed numbers.
1100 (log10_times_2048(denominator) - log10_times_2048(numerator)) as u64
1104 fn log10_times_2048(x: u64) -> u16 {
1105 debug_assert_ne!(x, 0);
1106 let most_significant_bit = HIGHEST_BIT - x.leading_zeros();
1107 let lower_bits = (x >> most_significant_bit.saturating_sub(LOWER_BITS)) & LOWER_BITMASK;
1108 LOG10_TIMES_2048[most_significant_bit as usize][lower_bits as usize]
1116 fn prints_negative_log10_times_2048_lookup_table() {
1117 for msb in 0..BITS {
1118 for i in 0..LOWER_BITS_BOUND {
1119 let x = ((LOWER_BITS_BOUND + i) << (HIGHEST_BIT - LOWER_BITS)) >> (HIGHEST_BIT - msb);
1120 let log10_times_2048 = ((x as f64).log10() * 2048.0).round() as u16;
1121 assert_eq!(log10_times_2048, LOG10_TIMES_2048[msb as usize][i as usize]);
1123 if i % LOWER_BITS_BOUND == 0 {
1124 print!("\t\t[{}, ", log10_times_2048);
1125 } else if i % LOWER_BITS_BOUND == LOWER_BITS_BOUND - 1 {
1126 println!("{}],", log10_times_2048);
1127 } else if i % (LOWER_BITS_BOUND/4) == LOWER_BITS_BOUND/4 - 1 {
1128 print!("{},\n\t\t\t", log10_times_2048);
1130 print!("{}, ", log10_times_2048);
1138 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Writeable for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1140 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
1141 write_tlv_fields!(w, {
1142 (0, self.channel_liquidities, required),
1148 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time>
1149 ReadableArgs<(ProbabilisticScoringParameters, G, L)> for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1152 r: &mut R, args: (ProbabilisticScoringParameters, G, L)
1153 ) -> Result<Self, DecodeError> {
1154 let (params, network_graph, logger) = args;
1155 let mut channel_liquidities = HashMap::new();
1156 read_tlv_fields!(r, {
1157 (0, channel_liquidities, required),
1163 channel_liquidities,
1168 impl<T: Time> Writeable for ChannelLiquidity<T> {
1170 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
1171 let duration_since_epoch = T::duration_since_epoch() - self.last_updated.elapsed();
1172 write_tlv_fields!(w, {
1173 (0, self.min_liquidity_offset_msat, required),
1174 (2, self.max_liquidity_offset_msat, required),
1175 (4, duration_since_epoch, required),
1181 impl<T: Time> Readable for ChannelLiquidity<T> {
1183 fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
1184 let mut min_liquidity_offset_msat = 0;
1185 let mut max_liquidity_offset_msat = 0;
1186 let mut duration_since_epoch = Duration::from_secs(0);
1187 read_tlv_fields!(r, {
1188 (0, min_liquidity_offset_msat, required),
1189 (2, max_liquidity_offset_msat, required),
1190 (4, duration_since_epoch, required),
1193 min_liquidity_offset_msat,
1194 max_liquidity_offset_msat,
1195 last_updated: T::now() - (T::duration_since_epoch() - duration_since_epoch),
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);