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