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