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