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