1 // This file is Copyright its original authors, visible in version control
4 // This file is licensed under the Apache License, Version 2.0 <LICENSE-APACHE
5 // or http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
6 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your option.
7 // You may not use this file except in accordance with one or both of these
10 //! Utilities for scoring payment channels.
12 //! [`ProbabilisticScorer`] may be given to [`find_route`] to score payment channels during path
13 //! finding when a custom [`Score`] implementation is not needed.
18 //! # extern crate secp256k1;
20 //! # use lightning::routing::network_graph::NetworkGraph;
21 //! # use lightning::routing::router::{RouteParameters, find_route};
22 //! # use lightning::routing::scoring::{ProbabilisticScorer, ProbabilisticScoringParameters, Scorer, ScoringParameters};
23 //! # use lightning::chain::keysinterface::{KeysManager, KeysInterface};
24 //! # use lightning::util::logger::{Logger, Record};
25 //! # use secp256k1::key::PublicKey;
27 //! # struct FakeLogger {};
28 //! # impl Logger for FakeLogger {
29 //! # fn log(&self, record: &Record) { unimplemented!() }
31 //! # fn find_scored_route(payer: PublicKey, route_params: RouteParameters, network_graph: NetworkGraph) {
32 //! # let logger = FakeLogger {};
34 //! // Use the default channel penalties.
35 //! let params = ProbabilisticScoringParameters::default();
36 //! let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
38 //! // Or use custom channel penalties.
39 //! let params = ProbabilisticScoringParameters {
40 //! liquidity_penalty_multiplier_msat: 2 * 1000,
41 //! ..ProbabilisticScoringParameters::default()
43 //! let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
44 //! # let random_seed_bytes = [42u8; 32];
46 //! let route = find_route(&payer, &route_params, &network_graph, None, &logger, &scorer, &random_seed_bytes);
52 //! Persisting when built with feature `no-std` and restoring without it, or vice versa, uses
53 //! different types and thus is undefined.
55 //! [`find_route`]: crate::routing::router::find_route
57 use ln::msgs::DecodeError;
58 use routing::network_graph::{NetworkGraph, NodeId};
59 use routing::router::RouteHop;
60 use util::ser::{Readable, ReadableArgs, Writeable, Writer};
61 use util::logger::Logger;
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());
627 /// Dump the contents of this scorer into the configured logger.
629 /// Note that this writes roughly one line per channel for which we have a liquidity estimate,
630 /// which may be a substantial amount of log output.
631 pub fn debug_log_liquidity_stats(&self) {
632 let graph = self.network_graph.read_only();
633 for (scid, liq) in self.channel_liquidities.iter() {
634 if let Some(chan_debug) = graph.channels().get(scid) {
635 let log_direction = |source, target| {
636 if let Some((directed_info, _)) = chan_debug.as_directed_to(target) {
637 let amt = directed_info.effective_capacity().as_msat();
638 let dir_liq = liq.as_directed(source, target, amt, self.params.liquidity_offset_half_life);
639 log_debug!(self.logger, "Liquidity from {:?} to {:?} via {} is in the range ({}, {})",
640 source, target, scid, dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat());
642 log_debug!(self.logger, "No amount known for SCID {} from {:?} to {:?}", scid, source, target);
646 log_direction(&chan_debug.node_one, &chan_debug.node_two);
647 log_direction(&chan_debug.node_two, &chan_debug.node_one);
649 log_debug!(self.logger, "No network graph entry for SCID {}", scid);
655 impl ProbabilisticScoringParameters {
657 fn zero_penalty() -> Self {
659 base_penalty_msat: 0,
660 liquidity_penalty_multiplier_msat: 0,
661 liquidity_offset_half_life: Duration::from_secs(3600),
662 amount_penalty_multiplier_msat: 0,
667 impl Default for ProbabilisticScoringParameters {
668 fn default() -> Self {
670 base_penalty_msat: 500,
671 liquidity_penalty_multiplier_msat: 40_000,
672 liquidity_offset_half_life: Duration::from_secs(3600),
673 amount_penalty_multiplier_msat: 256,
678 impl<T: Time> ChannelLiquidity<T> {
682 min_liquidity_offset_msat: 0,
683 max_liquidity_offset_msat: 0,
684 last_updated: T::now(),
688 /// Returns a view of the channel liquidity directed from `source` to `target` assuming
691 &self, source: &NodeId, target: &NodeId, capacity_msat: u64, half_life: Duration
692 ) -> DirectedChannelLiquidity<&u64, T, &T> {
693 let (min_liquidity_offset_msat, max_liquidity_offset_msat) = if source < target {
694 (&self.min_liquidity_offset_msat, &self.max_liquidity_offset_msat)
696 (&self.max_liquidity_offset_msat, &self.min_liquidity_offset_msat)
699 DirectedChannelLiquidity {
700 min_liquidity_offset_msat,
701 max_liquidity_offset_msat,
703 last_updated: &self.last_updated,
709 /// Returns a mutable view of the channel liquidity directed from `source` to `target` assuming
712 &mut self, source: &NodeId, target: &NodeId, capacity_msat: u64, half_life: Duration
713 ) -> DirectedChannelLiquidity<&mut u64, T, &mut T> {
714 let (min_liquidity_offset_msat, max_liquidity_offset_msat) = if source < target {
715 (&mut self.min_liquidity_offset_msat, &mut self.max_liquidity_offset_msat)
717 (&mut self.max_liquidity_offset_msat, &mut self.min_liquidity_offset_msat)
720 DirectedChannelLiquidity {
721 min_liquidity_offset_msat,
722 max_liquidity_offset_msat,
724 last_updated: &mut self.last_updated,
731 /// Bounds `-log10` to avoid excessive liquidity penalties for payments with low success
733 const NEGATIVE_LOG10_UPPER_BOUND: u64 = 2;
735 /// The rough cutoff at which our precision falls off and we should stop bothering to try to log a
736 /// ratio, as X in 1/X.
737 const PRECISION_LOWER_BOUND_DENOMINATOR: u64 = approx::LOWER_BITS_BOUND;
739 /// The divisor used when computing the amount penalty.
740 const AMOUNT_PENALTY_DIVISOR: u64 = 1 << 20;
742 impl<L: Deref<Target = u64>, T: Time, U: Deref<Target = T>> DirectedChannelLiquidity<L, T, U> {
743 /// Returns a penalty for routing the given HTLC `amount_msat` through the channel in this
745 fn penalty_msat(&self, amount_msat: u64, params: ProbabilisticScoringParameters) -> u64 {
746 let max_liquidity_msat = self.max_liquidity_msat();
747 let min_liquidity_msat = core::cmp::min(self.min_liquidity_msat(), max_liquidity_msat);
748 if amount_msat <= min_liquidity_msat {
750 } else if amount_msat >= max_liquidity_msat {
751 if amount_msat > max_liquidity_msat {
753 } else if max_liquidity_msat != self.capacity_msat {
754 // Avoid using the failed channel on retry.
757 // Equivalent to hitting the else clause below with the amount equal to the
758 // effective capacity and without any certainty on the liquidity upper bound.
759 let negative_log10_times_2048 = NEGATIVE_LOG10_UPPER_BOUND * 2048;
760 self.combined_penalty_msat(amount_msat, negative_log10_times_2048, params)
763 let numerator = (max_liquidity_msat - amount_msat).saturating_add(1);
764 let denominator = (max_liquidity_msat - min_liquidity_msat).saturating_add(1);
765 if amount_msat - min_liquidity_msat < denominator / PRECISION_LOWER_BOUND_DENOMINATOR {
766 // If the failure probability is < 1.5625% (as 1 - numerator/denominator < 1/64),
767 // don't bother trying to use the log approximation as it gets too noisy to be
768 // particularly helpful, instead just round down to 0 and return the base penalty.
769 params.base_penalty_msat
771 let negative_log10_times_2048 =
772 approx::negative_log10_times_2048(numerator, denominator);
773 self.combined_penalty_msat(amount_msat, negative_log10_times_2048, params)
778 /// Computes the liquidity and amount penalties and adds them to the base penalty.
780 fn combined_penalty_msat(
781 &self, amount_msat: u64, negative_log10_times_2048: u64,
782 params: ProbabilisticScoringParameters
784 let liquidity_penalty_msat = {
785 // Upper bound the liquidity penalty to ensure some channel is selected.
786 let multiplier_msat = params.liquidity_penalty_multiplier_msat;
787 let max_penalty_msat = multiplier_msat.saturating_mul(NEGATIVE_LOG10_UPPER_BOUND);
788 (negative_log10_times_2048.saturating_mul(multiplier_msat) / 2048).min(max_penalty_msat)
790 let amount_penalty_msat = negative_log10_times_2048
791 .saturating_mul(params.amount_penalty_multiplier_msat)
792 .saturating_mul(amount_msat) / 2048 / AMOUNT_PENALTY_DIVISOR;
794 params.base_penalty_msat
795 .saturating_add(liquidity_penalty_msat)
796 .saturating_add(amount_penalty_msat)
799 /// Returns the lower bound of the channel liquidity balance in this direction.
800 fn min_liquidity_msat(&self) -> u64 {
801 self.decayed_offset_msat(*self.min_liquidity_offset_msat)
804 /// Returns the upper bound of the channel liquidity balance in this direction.
805 fn max_liquidity_msat(&self) -> u64 {
807 .checked_sub(self.decayed_offset_msat(*self.max_liquidity_offset_msat))
811 fn decayed_offset_msat(&self, offset_msat: u64) -> u64 {
812 self.now.duration_since(*self.last_updated).as_secs()
813 .checked_div(self.half_life.as_secs())
814 .and_then(|decays| offset_msat.checked_shr(decays as u32))
819 impl<L: DerefMut<Target = u64>, T: Time, U: DerefMut<Target = T>> DirectedChannelLiquidity<L, T, U> {
820 /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat`.
821 fn failed_at_channel<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
822 if amount_msat < self.max_liquidity_msat() {
823 log_debug!(logger, "Setting max liquidity of {} to {}", chan_descr, amount_msat);
824 self.set_max_liquidity_msat(amount_msat);
826 log_trace!(logger, "Max liquidity of {} already more than {}", chan_descr, amount_msat);
830 /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat` downstream.
831 fn failed_downstream<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
832 if amount_msat > self.min_liquidity_msat() {
833 log_debug!(logger, "Setting min liquidity of {} to {}", chan_descr, amount_msat);
834 self.set_min_liquidity_msat(amount_msat);
836 log_trace!(logger, "Min liquidity of {} already less than {}", chan_descr, amount_msat);
840 /// Adjusts the channel liquidity balance bounds when successfully routing `amount_msat`.
841 fn successful<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
842 let max_liquidity_msat = self.max_liquidity_msat().checked_sub(amount_msat).unwrap_or(0);
843 log_debug!(logger, "Subtracting {} from max liquidity of {} (setting it to {})", amount_msat, chan_descr, max_liquidity_msat);
844 self.set_max_liquidity_msat(max_liquidity_msat);
847 /// Adjusts the lower bound of the channel liquidity balance in this direction.
848 fn set_min_liquidity_msat(&mut self, amount_msat: u64) {
849 *self.min_liquidity_offset_msat = amount_msat;
850 *self.max_liquidity_offset_msat = if amount_msat > self.max_liquidity_msat() {
853 self.decayed_offset_msat(*self.max_liquidity_offset_msat)
855 *self.last_updated = self.now;
858 /// Adjusts the upper bound of the channel liquidity balance in this direction.
859 fn set_max_liquidity_msat(&mut self, amount_msat: u64) {
860 *self.max_liquidity_offset_msat = self.capacity_msat.checked_sub(amount_msat).unwrap_or(0);
861 *self.min_liquidity_offset_msat = if amount_msat < self.min_liquidity_msat() {
864 self.decayed_offset_msat(*self.min_liquidity_offset_msat)
866 *self.last_updated = self.now;
870 impl<G: Deref<Target = NetworkGraph>, L: Deref, T: Time> Score for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
871 fn channel_penalty_msat(
872 &self, short_channel_id: u64, amount_msat: u64, capacity_msat: u64, source: &NodeId,
875 let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
876 self.channel_liquidities
877 .get(&short_channel_id)
878 .unwrap_or(&ChannelLiquidity::new())
879 .as_directed(source, target, capacity_msat, liquidity_offset_half_life)
880 .penalty_msat(amount_msat, self.params)
883 fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
884 let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
885 let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
886 log_trace!(self.logger, "Scoring path through to SCID {} as having failed at {} msat", short_channel_id, amount_msat);
887 let network_graph = self.network_graph.read_only();
888 for (hop_idx, hop) in path.iter().enumerate() {
889 let target = NodeId::from_pubkey(&hop.pubkey);
890 let channel_directed_from_source = network_graph.channels()
891 .get(&hop.short_channel_id)
892 .and_then(|channel| channel.as_directed_to(&target));
894 if hop.short_channel_id == short_channel_id && hop_idx == 0 {
895 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);
898 // Only score announced channels.
899 if let Some((channel, source)) = channel_directed_from_source {
900 let capacity_msat = channel.effective_capacity().as_msat();
901 if hop.short_channel_id == short_channel_id {
902 self.channel_liquidities
903 .entry(hop.short_channel_id)
904 .or_insert_with(ChannelLiquidity::new)
905 .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life)
906 .failed_at_channel(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
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 .failed_downstream(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
916 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).",
917 hop.short_channel_id);
922 fn payment_path_successful(&mut self, path: &[&RouteHop]) {
923 let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
924 let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
925 log_trace!(self.logger, "Scoring path through SCID {} as having succeeded at {} msat.",
926 path.split_last().map(|(hop, _)| hop.short_channel_id).unwrap_or(0), amount_msat);
927 let network_graph = self.network_graph.read_only();
929 let target = NodeId::from_pubkey(&hop.pubkey);
930 let channel_directed_from_source = network_graph.channels()
931 .get(&hop.short_channel_id)
932 .and_then(|channel| channel.as_directed_to(&target));
934 // Only score announced channels.
935 if let Some((channel, source)) = channel_directed_from_source {
936 let capacity_msat = channel.effective_capacity().as_msat();
937 self.channel_liquidities
938 .entry(hop.short_channel_id)
939 .or_insert_with(ChannelLiquidity::new)
940 .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life)
941 .successful(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
943 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).",
944 hop.short_channel_id);
951 const BITS: u32 = 64;
952 const HIGHEST_BIT: u32 = BITS - 1;
953 const LOWER_BITS: u32 = 6;
954 pub(super) const LOWER_BITS_BOUND: u64 = 1 << LOWER_BITS;
955 const LOWER_BITMASK: u64 = (1 << LOWER_BITS) - 1;
957 /// Look-up table for `log10(x) * 2048` where row `i` is used for each `x` having `i` as the
958 /// most significant bit. The next 4 bits of `x`, if applicable, are used for the second index.
959 const LOG10_TIMES_2048: [[u16; (LOWER_BITS_BOUND) as usize]; BITS as usize] = [
960 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
961 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
962 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
963 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
964 [617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
965 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
966 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977,
967 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977],
968 [1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233,
969 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431,
970 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594,
971 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731],
972 [1850, 1850, 1850, 1850, 1850, 1850, 1850, 1850, 1954, 1954, 1954, 1954, 1954, 1954, 1954, 1954,
973 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2133, 2133, 2133, 2133, 2133, 2133, 2133, 2133,
974 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2281, 2281, 2281, 2281, 2281, 2281, 2281, 2281,
975 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2409, 2409, 2409, 2409, 2409, 2409, 2409, 2409],
976 [2466, 2466, 2466, 2466, 2520, 2520, 2520, 2520, 2571, 2571, 2571, 2571, 2619, 2619, 2619, 2619,
977 2665, 2665, 2665, 2665, 2708, 2708, 2708, 2708, 2749, 2749, 2749, 2749, 2789, 2789, 2789, 2789,
978 2827, 2827, 2827, 2827, 2863, 2863, 2863, 2863, 2898, 2898, 2898, 2898, 2931, 2931, 2931, 2931,
979 2964, 2964, 2964, 2964, 2995, 2995, 2995, 2995, 3025, 3025, 3025, 3025, 3054, 3054, 3054, 3054],
980 [3083, 3083, 3110, 3110, 3136, 3136, 3162, 3162, 3187, 3187, 3212, 3212, 3235, 3235, 3259, 3259,
981 3281, 3281, 3303, 3303, 3324, 3324, 3345, 3345, 3366, 3366, 3386, 3386, 3405, 3405, 3424, 3424,
982 3443, 3443, 3462, 3462, 3479, 3479, 3497, 3497, 3514, 3514, 3531, 3531, 3548, 3548, 3564, 3564,
983 3580, 3580, 3596, 3596, 3612, 3612, 3627, 3627, 3642, 3642, 3656, 3656, 3671, 3671, 3685, 3685],
984 [3699, 3713, 3726, 3740, 3753, 3766, 3779, 3791, 3804, 3816, 3828, 3840, 3852, 3864, 3875, 3886,
985 3898, 3909, 3919, 3930, 3941, 3951, 3962, 3972, 3982, 3992, 4002, 4012, 4022, 4031, 4041, 4050,
986 4060, 4069, 4078, 4087, 4096, 4105, 4114, 4122, 4131, 4139, 4148, 4156, 4164, 4173, 4181, 4189,
987 4197, 4205, 4213, 4220, 4228, 4236, 4243, 4251, 4258, 4266, 4273, 4280, 4287, 4294, 4302, 4309],
988 [4316, 4329, 4343, 4356, 4369, 4382, 4395, 4408, 4420, 4433, 4445, 4457, 4468, 4480, 4492, 4503,
989 4514, 4525, 4536, 4547, 4557, 4568, 4578, 4589, 4599, 4609, 4619, 4629, 4638, 4648, 4657, 4667,
990 4676, 4685, 4695, 4704, 4713, 4721, 4730, 4739, 4747, 4756, 4764, 4773, 4781, 4789, 4797, 4805,
991 4813, 4821, 4829, 4837, 4845, 4852, 4860, 4867, 4875, 4882, 4889, 4897, 4904, 4911, 4918, 4925],
992 [4932, 4946, 4959, 4973, 4986, 4999, 5012, 5024, 5037, 5049, 5061, 5073, 5085, 5097, 5108, 5119,
993 5131, 5142, 5153, 5163, 5174, 5184, 5195, 5205, 5215, 5225, 5235, 5245, 5255, 5264, 5274, 5283,
994 5293, 5302, 5311, 5320, 5329, 5338, 5347, 5355, 5364, 5372, 5381, 5389, 5397, 5406, 5414, 5422,
995 5430, 5438, 5446, 5453, 5461, 5469, 5476, 5484, 5491, 5499, 5506, 5513, 5520, 5527, 5535, 5542],
996 [5549, 5562, 5576, 5589, 5603, 5615, 5628, 5641, 5653, 5666, 5678, 5690, 5701, 5713, 5725, 5736,
997 5747, 5758, 5769, 5780, 5790, 5801, 5811, 5822, 5832, 5842, 5852, 5862, 5871, 5881, 5890, 5900,
998 5909, 5918, 5928, 5937, 5946, 5954, 5963, 5972, 5980, 5989, 5997, 6006, 6014, 6022, 6030, 6038,
999 6046, 6054, 6062, 6070, 6078, 6085, 6093, 6100, 6108, 6115, 6122, 6130, 6137, 6144, 6151, 6158],
1000 [6165, 6179, 6192, 6206, 6219, 6232, 6245, 6257, 6270, 6282, 6294, 6306, 6318, 6330, 6341, 6352,
1001 6364, 6375, 6386, 6396, 6407, 6417, 6428, 6438, 6448, 6458, 6468, 6478, 6488, 6497, 6507, 6516,
1002 6526, 6535, 6544, 6553, 6562, 6571, 6580, 6588, 6597, 6605, 6614, 6622, 6630, 6639, 6647, 6655,
1003 6663, 6671, 6679, 6686, 6694, 6702, 6709, 6717, 6724, 6732, 6739, 6746, 6753, 6761, 6768, 6775],
1004 [6782, 6795, 6809, 6822, 6836, 6849, 6861, 6874, 6886, 6899, 6911, 6923, 6934, 6946, 6958, 6969,
1005 6980, 6991, 7002, 7013, 7023, 7034, 7044, 7055, 7065, 7075, 7085, 7095, 7104, 7114, 7124, 7133,
1006 7142, 7151, 7161, 7170, 7179, 7187, 7196, 7205, 7213, 7222, 7230, 7239, 7247, 7255, 7263, 7271,
1007 7279, 7287, 7295, 7303, 7311, 7318, 7326, 7333, 7341, 7348, 7355, 7363, 7370, 7377, 7384, 7391],
1008 [7398, 7412, 7425, 7439, 7452, 7465, 7478, 7490, 7503, 7515, 7527, 7539, 7551, 7563, 7574, 7585,
1009 7597, 7608, 7619, 7629, 7640, 7651, 7661, 7671, 7681, 7691, 7701, 7711, 7721, 7731, 7740, 7749,
1010 7759, 7768, 7777, 7786, 7795, 7804, 7813, 7821, 7830, 7838, 7847, 7855, 7864, 7872, 7880, 7888,
1011 7896, 7904, 7912, 7919, 7927, 7935, 7942, 7950, 7957, 7965, 7972, 7979, 7986, 7994, 8001, 8008],
1012 [8015, 8028, 8042, 8055, 8069, 8082, 8094, 8107, 8119, 8132, 8144, 8156, 8167, 8179, 8191, 8202,
1013 8213, 8224, 8235, 8246, 8256, 8267, 8277, 8288, 8298, 8308, 8318, 8328, 8337, 8347, 8357, 8366,
1014 8375, 8384, 8394, 8403, 8412, 8420, 8429, 8438, 8446, 8455, 8463, 8472, 8480, 8488, 8496, 8504,
1015 8512, 8520, 8528, 8536, 8544, 8551, 8559, 8566, 8574, 8581, 8588, 8596, 8603, 8610, 8617, 8624],
1016 [8631, 8645, 8659, 8672, 8685, 8698, 8711, 8723, 8736, 8748, 8760, 8772, 8784, 8796, 8807, 8818,
1017 8830, 8841, 8852, 8862, 8873, 8884, 8894, 8904, 8914, 8924, 8934, 8944, 8954, 8964, 8973, 8982,
1018 8992, 9001, 9010, 9019, 9028, 9037, 9046, 9054, 9063, 9071, 9080, 9088, 9097, 9105, 9113, 9121,
1019 9129, 9137, 9145, 9152, 9160, 9168, 9175, 9183, 9190, 9198, 9205, 9212, 9219, 9227, 9234, 9241],
1020 [9248, 9261, 9275, 9288, 9302, 9315, 9327, 9340, 9352, 9365, 9377, 9389, 9400, 9412, 9424, 9435,
1021 9446, 9457, 9468, 9479, 9490, 9500, 9510, 9521, 9531, 9541, 9551, 9561, 9570, 9580, 9590, 9599,
1022 9608, 9617, 9627, 9636, 9645, 9653, 9662, 9671, 9679, 9688, 9696, 9705, 9713, 9721, 9729, 9737,
1023 9745, 9753, 9761, 9769, 9777, 9784, 9792, 9799, 9807, 9814, 9821, 9829, 9836, 9843, 9850, 9857],
1024 [9864, 9878, 9892, 9905, 9918, 9931, 9944, 9956, 9969, 9981, 9993, 10005, 10017, 10029, 10040, 10051,
1025 10063, 10074, 10085, 10095, 10106, 10117, 10127, 10137, 10147, 10157, 10167, 10177, 10187, 10197, 10206, 10215,
1026 10225, 10234, 10243, 10252, 10261, 10270, 10279, 10287, 10296, 10304, 10313, 10321, 10330, 10338, 10346, 10354,
1027 10362, 10370, 10378, 10385, 10393, 10401, 10408, 10416, 10423, 10431, 10438, 10445, 10452, 10460, 10467, 10474],
1028 [10481, 10494, 10508, 10521, 10535, 10548, 10560, 10573, 10585, 10598, 10610, 10622, 10634, 10645, 10657, 10668,
1029 10679, 10690, 10701, 10712, 10723, 10733, 10743, 10754, 10764, 10774, 10784, 10794, 10803, 10813, 10823, 10832,
1030 10841, 10851, 10860, 10869, 10878, 10886, 10895, 10904, 10912, 10921, 10929, 10938, 10946, 10954, 10962, 10970,
1031 10978, 10986, 10994, 11002, 11010, 11017, 11025, 11032, 11040, 11047, 11054, 11062, 11069, 11076, 11083, 11090],
1032 [11097, 11111, 11125, 11138, 11151, 11164, 11177, 11189, 11202, 11214, 11226, 11238, 11250, 11262, 11273, 11284,
1033 11296, 11307, 11318, 11328, 11339, 11350, 11360, 11370, 11380, 11390, 11400, 11410, 11420, 11430, 11439, 11448,
1034 11458, 11467, 11476, 11485, 11494, 11503, 11512, 11520, 11529, 11538, 11546, 11554, 11563, 11571, 11579, 11587,
1035 11595, 11603, 11611, 11618, 11626, 11634, 11641, 11649, 11656, 11664, 11671, 11678, 11685, 11693, 11700, 11707],
1036 [11714, 11727, 11741, 11754, 11768, 11781, 11793, 11806, 11818, 11831, 11843, 11855, 11867, 11878, 11890, 11901,
1037 11912, 11923, 11934, 11945, 11956, 11966, 11976, 11987, 11997, 12007, 12017, 12027, 12036, 12046, 12056, 12065,
1038 12074, 12084, 12093, 12102, 12111, 12119, 12128, 12137, 12146, 12154, 12162, 12171, 12179, 12187, 12195, 12203,
1039 12211, 12219, 12227, 12235, 12243, 12250, 12258, 12265, 12273, 12280, 12287, 12295, 12302, 12309, 12316, 12323],
1040 [12330, 12344, 12358, 12371, 12384, 12397, 12410, 12423, 12435, 12447, 12459, 12471, 12483, 12495, 12506, 12517,
1041 12529, 12540, 12551, 12561, 12572, 12583, 12593, 12603, 12613, 12623, 12633, 12643, 12653, 12663, 12672, 12682,
1042 12691, 12700, 12709, 12718, 12727, 12736, 12745, 12753, 12762, 12771, 12779, 12787, 12796, 12804, 12812, 12820,
1043 12828, 12836, 12844, 12851, 12859, 12867, 12874, 12882, 12889, 12897, 12904, 12911, 12918, 12926, 12933, 12940],
1044 [12947, 12960, 12974, 12987, 13001, 13014, 13026, 13039, 13051, 13064, 13076, 13088, 13100, 13111, 13123, 13134,
1045 13145, 13156, 13167, 13178, 13189, 13199, 13209, 13220, 13230, 13240, 13250, 13260, 13269, 13279, 13289, 13298,
1046 13307, 13317, 13326, 13335, 13344, 13352, 13361, 13370, 13379, 13387, 13395, 13404, 13412, 13420, 13428, 13436,
1047 13444, 13452, 13460, 13468, 13476, 13483, 13491, 13498, 13506, 13513, 13521, 13528, 13535, 13542, 13549, 13556],
1048 [13563, 13577, 13591, 13604, 13617, 13630, 13643, 13656, 13668, 13680, 13692, 13704, 13716, 13728, 13739, 13750,
1049 13762, 13773, 13784, 13794, 13805, 13816, 13826, 13836, 13846, 13857, 13866, 13876, 13886, 13896, 13905, 13915,
1050 13924, 13933, 13942, 13951, 13960, 13969, 13978, 13986, 13995, 14004, 14012, 14020, 14029, 14037, 14045, 14053,
1051 14061, 14069, 14077, 14084, 14092, 14100, 14107, 14115, 14122, 14130, 14137, 14144, 14151, 14159, 14166, 14173],
1052 [14180, 14194, 14207, 14220, 14234, 14247, 14259, 14272, 14284, 14297, 14309, 14321, 14333, 14344, 14356, 14367,
1053 14378, 14389, 14400, 14411, 14422, 14432, 14443, 14453, 14463, 14473, 14483, 14493, 14502, 14512, 14522, 14531,
1054 14540, 14550, 14559, 14568, 14577, 14586, 14594, 14603, 14612, 14620, 14628, 14637, 14645, 14653, 14661, 14669,
1055 14677, 14685, 14693, 14701, 14709, 14716, 14724, 14731, 14739, 14746, 14754, 14761, 14768, 14775, 14782, 14789],
1056 [14796, 14810, 14824, 14837, 14850, 14863, 14876, 14889, 14901, 14913, 14925, 14937, 14949, 14961, 14972, 14984,
1057 14995, 15006, 15017, 15027, 15038, 15049, 15059, 15069, 15079, 15090, 15099, 15109, 15119, 15129, 15138, 15148,
1058 15157, 15166, 15175, 15184, 15193, 15202, 15211, 15219, 15228, 15237, 15245, 15253, 15262, 15270, 15278, 15286,
1059 15294, 15302, 15310, 15317, 15325, 15333, 15340, 15348, 15355, 15363, 15370, 15377, 15384, 15392, 15399, 15406],
1060 [15413, 15427, 15440, 15453, 15467, 15480, 15492, 15505, 15517, 15530, 15542, 15554, 15566, 15577, 15589, 15600,
1061 15611, 15622, 15633, 15644, 15655, 15665, 15676, 15686, 15696, 15706, 15716, 15726, 15736, 15745, 15755, 15764,
1062 15773, 15783, 15792, 15801, 15810, 15819, 15827, 15836, 15845, 15853, 15862, 15870, 15878, 15886, 15894, 15903,
1063 15910, 15918, 15926, 15934, 15942, 15949, 15957, 15964, 15972, 15979, 15987, 15994, 16001, 16008, 16015, 16022],
1064 [16029, 16043, 16057, 16070, 16083, 16096, 16109, 16122, 16134, 16146, 16158, 16170, 16182, 16194, 16205, 16217,
1065 16228, 16239, 16250, 16260, 16271, 16282, 16292, 16302, 16312, 16323, 16332, 16342, 16352, 16362, 16371, 16381,
1066 16390, 16399, 16408, 16417, 16426, 16435, 16444, 16452, 16461, 16470, 16478, 16486, 16495, 16503, 16511, 16519,
1067 16527, 16535, 16543, 16550, 16558, 16566, 16573, 16581, 16588, 16596, 16603, 16610, 16618, 16625, 16632, 16639],
1068 [16646, 16660, 16673, 16686, 16700, 16713, 16725, 16738, 16751, 16763, 16775, 16787, 16799, 16810, 16822, 16833,
1069 16844, 16855, 16866, 16877, 16888, 16898, 16909, 16919, 16929, 16939, 16949, 16959, 16969, 16978, 16988, 16997,
1070 17006, 17016, 17025, 17034, 17043, 17052, 17060, 17069, 17078, 17086, 17095, 17103, 17111, 17119, 17127, 17136,
1071 17143, 17151, 17159, 17167, 17175, 17182, 17190, 17197, 17205, 17212, 17220, 17227, 17234, 17241, 17248, 17255],
1072 [17262, 17276, 17290, 17303, 17316, 17329, 17342, 17355, 17367, 17379, 17391, 17403, 17415, 17427, 17438, 17450,
1073 17461, 17472, 17483, 17493, 17504, 17515, 17525, 17535, 17546, 17556, 17565, 17575, 17585, 17595, 17604, 17614,
1074 17623, 17632, 17641, 17650, 17659, 17668, 17677, 17685, 17694, 17703, 17711, 17719, 17728, 17736, 17744, 17752,
1075 17760, 17768, 17776, 17784, 17791, 17799, 17806, 17814, 17821, 17829, 17836, 17843, 17851, 17858, 17865, 17872],
1076 [17879, 17893, 17906, 17920, 17933, 17946, 17958, 17971, 17984, 17996, 18008, 18020, 18032, 18043, 18055, 18066,
1077 18077, 18088, 18099, 18110, 18121, 18131, 18142, 18152, 18162, 18172, 18182, 18192, 18202, 18211, 18221, 18230,
1078 18239, 18249, 18258, 18267, 18276, 18285, 18293, 18302, 18311, 18319, 18328, 18336, 18344, 18352, 18360, 18369,
1079 18377, 18384, 18392, 18400, 18408, 18415, 18423, 18430, 18438, 18445, 18453, 18460, 18467, 18474, 18481, 18488],
1080 [18495, 18509, 18523, 18536, 18549, 18562, 18575, 18588, 18600, 18612, 18624, 18636, 18648, 18660, 18671, 18683,
1081 18694, 18705, 18716, 18726, 18737, 18748, 18758, 18768, 18779, 18789, 18799, 18808, 18818, 18828, 18837, 18847,
1082 18856, 18865, 18874, 18883, 18892, 18901, 18910, 18919, 18927, 18936, 18944, 18952, 18961, 18969, 18977, 18985,
1083 18993, 19001, 19009, 19017, 19024, 19032, 19039, 19047, 19054, 19062, 19069, 19076, 19084, 19091, 19098, 19105],
1084 [19112, 19126, 19139, 19153, 19166, 19179, 19191, 19204, 19217, 19229, 19241, 19253, 19265, 19276, 19288, 19299,
1085 19310, 19321, 19332, 19343, 19354, 19364, 19375, 19385, 19395, 19405, 19415, 19425, 19435, 19444, 19454, 19463,
1086 19472, 19482, 19491, 19500, 19509, 19518, 19526, 19535, 19544, 19552, 19561, 19569, 19577, 19585, 19594, 19602,
1087 19610, 19617, 19625, 19633, 19641, 19648, 19656, 19663, 19671, 19678, 19686, 19693, 19700, 19707, 19714, 19721],
1088 [19728, 19742, 19756, 19769, 19782, 19795, 19808, 19821, 19833, 19845, 19857, 19869, 19881, 19893, 19904, 19916,
1089 19927, 19938, 19949, 19960, 19970, 19981, 19991, 20001, 20012, 20022, 20032, 20041, 20051, 20061, 20070, 20080,
1090 20089, 20098, 20107, 20116, 20125, 20134, 20143, 20152, 20160, 20169, 20177, 20185, 20194, 20202, 20210, 20218,
1091 20226, 20234, 20242, 20250, 20257, 20265, 20272, 20280, 20287, 20295, 20302, 20309, 20317, 20324, 20331, 20338],
1092 [20345, 20359, 20372, 20386, 20399, 20412, 20425, 20437, 20450, 20462, 20474, 20486, 20498, 20509, 20521, 20532,
1093 20543, 20554, 20565, 20576, 20587, 20597, 20608, 20618, 20628, 20638, 20648, 20658, 20668, 20677, 20687, 20696,
1094 20705, 20715, 20724, 20733, 20742, 20751, 20759, 20768, 20777, 20785, 20794, 20802, 20810, 20818, 20827, 20835,
1095 20843, 20850, 20858, 20866, 20874, 20881, 20889, 20896, 20904, 20911, 20919, 20926, 20933, 20940, 20947, 20954],
1096 [20961, 20975, 20989, 21002, 21015, 21028, 21041, 21054, 21066, 21078, 21090, 21102, 21114, 21126, 21137, 21149,
1097 21160, 21171, 21182, 21193, 21203, 21214, 21224, 21234, 21245, 21255, 21265, 21274, 21284, 21294, 21303, 21313,
1098 21322, 21331, 21340, 21349, 21358, 21367, 21376, 21385, 21393, 21402, 21410, 21418, 21427, 21435, 21443, 21451,
1099 21459, 21467, 21475, 21483, 21490, 21498, 21505, 21513, 21520, 21528, 21535, 21542, 21550, 21557, 21564, 21571],
1100 [21578, 21592, 21605, 21619, 21632, 21645, 21658, 21670, 21683, 21695, 21707, 21719, 21731, 21742, 21754, 21765,
1101 21776, 21787, 21798, 21809, 21820, 21830, 21841, 21851, 21861, 21871, 21881, 21891, 21901, 21910, 21920, 21929,
1102 21938, 21948, 21957, 21966, 21975, 21984, 21992, 22001, 22010, 22018, 22027, 22035, 22043, 22051, 22060, 22068,
1103 22076, 22083, 22091, 22099, 22107, 22114, 22122, 22129, 22137, 22144, 22152, 22159, 22166, 22173, 22180, 22187],
1104 [22194, 22208, 22222, 22235, 22248, 22261, 22274, 22287, 22299, 22311, 22323, 22335, 22347, 22359, 22370, 22382,
1105 22393, 22404, 22415, 22426, 22436, 22447, 22457, 22467, 22478, 22488, 22498, 22507, 22517, 22527, 22536, 22546,
1106 22555, 22564, 22573, 22582, 22591, 22600, 22609, 22618, 22626, 22635, 22643, 22651, 22660, 22668, 22676, 22684,
1107 22692, 22700, 22708, 22716, 22723, 22731, 22738, 22746, 22753, 22761, 22768, 22775, 22783, 22790, 22797, 22804],
1108 [22811, 22825, 22838, 22852, 22865, 22878, 22891, 22903, 22916, 22928, 22940, 22952, 22964, 22975, 22987, 22998,
1109 23009, 23020, 23031, 23042, 23053, 23063, 23074, 23084, 23094, 23104, 23114, 23124, 23134, 23143, 23153, 23162,
1110 23171, 23181, 23190, 23199, 23208, 23217, 23225, 23234, 23243, 23251, 23260, 23268, 23276, 23284, 23293, 23301,
1111 23309, 23316, 23324, 23332, 23340, 23347, 23355, 23363, 23370, 23377, 23385, 23392, 23399, 23406, 23413, 23420],
1112 [23427, 23441, 23455, 23468, 23481, 23494, 23507, 23520, 23532, 23544, 23556, 23568, 23580, 23592, 23603, 23615,
1113 23626, 23637, 23648, 23659, 23669, 23680, 23690, 23700, 23711, 23721, 23731, 23740, 23750, 23760, 23769, 23779,
1114 23788, 23797, 23806, 23815, 23824, 23833, 23842, 23851, 23859, 23868, 23876, 23884, 23893, 23901, 23909, 23917,
1115 23925, 23933, 23941, 23949, 23956, 23964, 23972, 23979, 23986, 23994, 24001, 24008, 24016, 24023, 24030, 24037],
1116 [24044, 24058, 24071, 24085, 24098, 24111, 24124, 24136, 24149, 24161, 24173, 24185, 24197, 24208, 24220, 24231,
1117 24242, 24253, 24264, 24275, 24286, 24296, 24307, 24317, 24327, 24337, 24347, 24357, 24367, 24376, 24386, 24395,
1118 24405, 24414, 24423, 24432, 24441, 24450, 24458, 24467, 24476, 24484, 24493, 24501, 24509, 24517, 24526, 24534,
1119 24542, 24550, 24557, 24565, 24573, 24580, 24588, 24596, 24603, 24610, 24618, 24625, 24632, 24639, 24646, 24653],
1120 [24660, 24674, 24688, 24701, 24714, 24727, 24740, 24753, 24765, 24777, 24790, 24801, 24813, 24825, 24836, 24848,
1121 24859, 24870, 24881, 24892, 24902, 24913, 24923, 24933, 24944, 24954, 24964, 24973, 24983, 24993, 25002, 25012,
1122 25021, 25030, 25039, 25048, 25057, 25066, 25075, 25084, 25092, 25101, 25109, 25117, 25126, 25134, 25142, 25150,
1123 25158, 25166, 25174, 25182, 25189, 25197, 25205, 25212, 25219, 25227, 25234, 25241, 25249, 25256, 25263, 25270],
1124 [25277, 25291, 25304, 25318, 25331, 25344, 25357, 25369, 25382, 25394, 25406, 25418, 25430, 25441, 25453, 25464,
1125 25475, 25486, 25497, 25508, 25519, 25529, 25540, 25550, 25560, 25570, 25580, 25590, 25600, 25609, 25619, 25628,
1126 25638, 25647, 25656, 25665, 25674, 25683, 25691, 25700, 25709, 25717, 25726, 25734, 25742, 25750, 25759, 25767,
1127 25775, 25783, 25790, 25798, 25806, 25813, 25821, 25829, 25836, 25843, 25851, 25858, 25865, 25872, 25879, 25886],
1128 [25893, 25907, 25921, 25934, 25947, 25960, 25973, 25986, 25998, 26010, 26023, 26034, 26046, 26058, 26069, 26081,
1129 26092, 26103, 26114, 26125, 26135, 26146, 26156, 26166, 26177, 26187, 26197, 26206, 26216, 26226, 26235, 26245,
1130 26254, 26263, 26272, 26281, 26290, 26299, 26308, 26317, 26325, 26334, 26342, 26351, 26359, 26367, 26375, 26383,
1131 26391, 26399, 26407, 26415, 26422, 26430, 26438, 26445, 26453, 26460, 26467, 26474, 26482, 26489, 26496, 26503],
1132 [26510, 26524, 26537, 26551, 26564, 26577, 26590, 26602, 26615, 26627, 26639, 26651, 26663, 26674, 26686, 26697,
1133 26708, 26719, 26730, 26741, 26752, 26762, 26773, 26783, 26793, 26803, 26813, 26823, 26833, 26842, 26852, 26861,
1134 26871, 26880, 26889, 26898, 26907, 26916, 26924, 26933, 26942, 26950, 26959, 26967, 26975, 26983, 26992, 27000,
1135 27008, 27016, 27023, 27031, 27039, 27046, 27054, 27062, 27069, 27076, 27084, 27091, 27098, 27105, 27112, 27119],
1136 [27126, 27140, 27154, 27167, 27180, 27193, 27206, 27219, 27231, 27243, 27256, 27267, 27279, 27291, 27302, 27314,
1137 27325, 27336, 27347, 27358, 27368, 27379, 27389, 27399, 27410, 27420, 27430, 27439, 27449, 27459, 27468, 27478,
1138 27487, 27496, 27505, 27514, 27523, 27532, 27541, 27550, 27558, 27567, 27575, 27584, 27592, 27600, 27608, 27616,
1139 27624, 27632, 27640, 27648, 27655, 27663, 27671, 27678, 27686, 27693, 27700, 27707, 27715, 27722, 27729, 27736],
1140 [27743, 27757, 27770, 27784, 27797, 27810, 27823, 27835, 27848, 27860, 27872, 27884, 27896, 27907, 27919, 27930,
1141 27941, 27952, 27963, 27974, 27985, 27995, 28006, 28016, 28026, 28036, 28046, 28056, 28066, 28075, 28085, 28094,
1142 28104, 28113, 28122, 28131, 28140, 28149, 28157, 28166, 28175, 28183, 28192, 28200, 28208, 28217, 28225, 28233,
1143 28241, 28249, 28256, 28264, 28272, 28280, 28287, 28295, 28302, 28309, 28317, 28324, 28331, 28338, 28345, 28352],
1144 [28359, 28373, 28387, 28400, 28413, 28426, 28439, 28452, 28464, 28476, 28489, 28501, 28512, 28524, 28535, 28547,
1145 28558, 28569, 28580, 28591, 28601, 28612, 28622, 28633, 28643, 28653, 28663, 28672, 28682, 28692, 28701, 28711,
1146 28720, 28729, 28738, 28747, 28756, 28765, 28774, 28783, 28791, 28800, 28808, 28817, 28825, 28833, 28841, 28849,
1147 28857, 28865, 28873, 28881, 28888, 28896, 28904, 28911, 28919, 28926, 28933, 28941, 28948, 28955, 28962, 28969],
1148 [28976, 28990, 29003, 29017, 29030, 29043, 29056, 29068, 29081, 29093, 29105, 29117, 29129, 29140, 29152, 29163,
1149 29174, 29185, 29196, 29207, 29218, 29228, 29239, 29249, 29259, 29269, 29279, 29289, 29299, 29308, 29318, 29327,
1150 29337, 29346, 29355, 29364, 29373, 29382, 29390, 29399, 29408, 29416, 29425, 29433, 29441, 29450, 29458, 29466,
1151 29474, 29482, 29489, 29497, 29505, 29513, 29520, 29528, 29535, 29542, 29550, 29557, 29564, 29571, 29578, 29585],
1152 [29592, 29606, 29620, 29633, 29646, 29659, 29672, 29685, 29697, 29709, 29722, 29734, 29745, 29757, 29768, 29780,
1153 29791, 29802, 29813, 29824, 29834, 29845, 29855, 29866, 29876, 29886, 29896, 29906, 29915, 29925, 29934, 29944,
1154 29953, 29962, 29971, 29980, 29989, 29998, 30007, 30016, 30024, 30033, 30041, 30050, 30058, 30066, 30074, 30082,
1155 30090, 30098, 30106, 30114, 30121, 30129, 30137, 30144, 30152, 30159, 30166, 30174, 30181, 30188, 30195, 30202],
1156 [30209, 30223, 30236, 30250, 30263, 30276, 30289, 30301, 30314, 30326, 30338, 30350, 30362, 30373, 30385, 30396,
1157 30407, 30418, 30429, 30440, 30451, 30461, 30472, 30482, 30492, 30502, 30512, 30522, 30532, 30541, 30551, 30560,
1158 30570, 30579, 30588, 30597, 30606, 30615, 30624, 30632, 30641, 30649, 30658, 30666, 30674, 30683, 30691, 30699,
1159 30707, 30715, 30722, 30730, 30738, 30746, 30753, 30761, 30768, 30775, 30783, 30790, 30797, 30804, 30811, 30818],
1160 [30825, 30839, 30853, 30866, 30879, 30892, 30905, 30918, 30930, 30943, 30955, 30967, 30978, 30990, 31001, 31013,
1161 31024, 31035, 31046, 31057, 31067, 31078, 31088, 31099, 31109, 31119, 31129, 31139, 31148, 31158, 31167, 31177,
1162 31186, 31195, 31204, 31213, 31222, 31231, 31240, 31249, 31257, 31266, 31274, 31283, 31291, 31299, 31307, 31315,
1163 31323, 31331, 31339, 31347, 31354, 31362, 31370, 31377, 31385, 31392, 31399, 31407, 31414, 31421, 31428, 31435],
1164 [31442, 31456, 31469, 31483, 31496, 31509, 31522, 31534, 31547, 31559, 31571, 31583, 31595, 31606, 31618, 31629,
1165 31640, 31652, 31662, 31673, 31684, 31694, 31705, 31715, 31725, 31735, 31745, 31755, 31765, 31774, 31784, 31793,
1166 31803, 31812, 31821, 31830, 31839, 31848, 31857, 31865, 31874, 31882, 31891, 31899, 31907, 31916, 31924, 31932,
1167 31940, 31948, 31955, 31963, 31971, 31979, 31986, 31994, 32001, 32008, 32016, 32023, 32030, 32037, 32044, 32052],
1168 [32058, 32072, 32086, 32099, 32112, 32125, 32138, 32151, 32163, 32176, 32188, 32200, 32211, 32223, 32234, 32246,
1169 32257, 32268, 32279, 32290, 32300, 32311, 32321, 32332, 32342, 32352, 32362, 32372, 32381, 32391, 32400, 32410,
1170 32419, 32428, 32437, 32446, 32455, 32464, 32473, 32482, 32490, 32499, 32507, 32516, 32524, 32532, 32540, 32548,
1171 32556, 32564, 32572, 32580, 32587, 32595, 32603, 32610, 32618, 32625, 32632, 32640, 32647, 32654, 32661, 32668],
1172 [32675, 32689, 32702, 32716, 32729, 32742, 32755, 32767, 32780, 32792, 32804, 32816, 32828, 32839, 32851, 32862,
1173 32873, 32885, 32895, 32906, 32917, 32927, 32938, 32948, 32958, 32968, 32978, 32988, 32998, 33007, 33017, 33026,
1174 33036, 33045, 33054, 33063, 33072, 33081, 33090, 33098, 33107, 33115, 33124, 33132, 33140, 33149, 33157, 33165,
1175 33173, 33181, 33188, 33196, 33204, 33212, 33219, 33227, 33234, 33241, 33249, 33256, 33263, 33270, 33278, 33285],
1176 [33292, 33305, 33319, 33332, 33345, 33358, 33371, 33384, 33396, 33409, 33421, 33433, 33444, 33456, 33467, 33479,
1177 33490, 33501, 33512, 33523, 33533, 33544, 33554, 33565, 33575, 33585, 33595, 33605, 33614, 33624, 33633, 33643,
1178 33652, 33661, 33670, 33680, 33688, 33697, 33706, 33715, 33723, 33732, 33740, 33749, 33757, 33765, 33773, 33781,
1179 33789, 33797, 33805, 33813, 33820, 33828, 33836, 33843, 33851, 33858, 33865, 33873, 33880, 33887, 33894, 33901],
1180 [33908, 33922, 33935, 33949, 33962, 33975, 33988, 34000, 34013, 34025, 34037, 34049, 34061, 34072, 34084, 34095,
1181 34106, 34118, 34128, 34139, 34150, 34160, 34171, 34181, 34191, 34201, 34211, 34221, 34231, 34240, 34250, 34259,
1182 34269, 34278, 34287, 34296, 34305, 34314, 34323, 34331, 34340, 34348, 34357, 34365, 34373, 34382, 34390, 34398,
1183 34406, 34414, 34422, 34429, 34437, 34445, 34452, 34460, 34467, 34475, 34482, 34489, 34496, 34503, 34511, 34518],
1184 [34525, 34538, 34552, 34565, 34578, 34591, 34604, 34617, 34629, 34642, 34654, 34666, 34677, 34689, 34700, 34712,
1185 34723, 34734, 34745, 34756, 34766, 34777, 34787, 34798, 34808, 34818, 34828, 34838, 34847, 34857, 34866, 34876,
1186 34885, 34894, 34904, 34913, 34921, 34930, 34939, 34948, 34956, 34965, 34973, 34982, 34990, 34998, 35006, 35014,
1187 35022, 35030, 35038, 35046, 35053, 35061, 35069, 35076, 35084, 35091, 35098, 35106, 35113, 35120, 35127, 35134],
1188 [35141, 35155, 35168, 35182, 35195, 35208, 35221, 35233, 35246, 35258, 35270, 35282, 35294, 35306, 35317, 35328,
1189 35340, 35351, 35361, 35372, 35383, 35393, 35404, 35414, 35424, 35434, 35444, 35454, 35464, 35473, 35483, 35492,
1190 35502, 35511, 35520, 35529, 35538, 35547, 35556, 35564, 35573, 35581, 35590, 35598, 35606, 35615, 35623, 35631,
1191 35639, 35647, 35655, 35662, 35670, 35678, 35685, 35693, 35700, 35708, 35715, 35722, 35729, 35736, 35744, 35751],
1192 [35758, 35771, 35785, 35798, 35811, 35824, 35837, 35850, 35862, 35875, 35887, 35899, 35910, 35922, 35934, 35945,
1193 35956, 35967, 35978, 35989, 35999, 36010, 36020, 36031, 36041, 36051, 36061, 36071, 36080, 36090, 36099, 36109,
1194 36118, 36127, 36137, 36146, 36154, 36163, 36172, 36181, 36189, 36198, 36206, 36215, 36223, 36231, 36239, 36247,
1195 36255, 36263, 36271, 36279, 36287, 36294, 36302, 36309, 36317, 36324, 36331, 36339, 36346, 36353, 36360, 36367],
1196 [36374, 36388, 36401, 36415, 36428, 36441, 36454, 36466, 36479, 36491, 36503, 36515, 36527, 36539, 36550, 36561,
1197 36573, 36584, 36594, 36605, 36616, 36626, 36637, 36647, 36657, 36667, 36677, 36687, 36697, 36706, 36716, 36725,
1198 36735, 36744, 36753, 36762, 36771, 36780, 36789, 36797, 36806, 36814, 36823, 36831, 36839, 36848, 36856, 36864,
1199 36872, 36880, 36888, 36895, 36903, 36911, 36918, 36926, 36933, 36941, 36948, 36955, 36962, 36969, 36977, 36984],
1200 [36991, 37004, 37018, 37031, 37044, 37057, 37070, 37083, 37095, 37108, 37120, 37132, 37143, 37155, 37167, 37178,
1201 37189, 37200, 37211, 37222, 37232, 37243, 37253, 37264, 37274, 37284, 37294, 37304, 37313, 37323, 37332, 37342,
1202 37351, 37360, 37370, 37379, 37388, 37396, 37405, 37414, 37422, 37431, 37439, 37448, 37456, 37464, 37472, 37480,
1203 37488, 37496, 37504, 37512, 37520, 37527, 37535, 37542, 37550, 37557, 37564, 37572, 37579, 37586, 37593, 37600],
1204 [37607, 37621, 37634, 37648, 37661, 37674, 37687, 37699, 37712, 37724, 37736, 37748, 37760, 37772, 37783, 37794,
1205 37806, 37817, 37828, 37838, 37849, 37859, 37870, 37880, 37890, 37900, 37910, 37920, 37930, 37939, 37949, 37958,
1206 37968, 37977, 37986, 37995, 38004, 38013, 38022, 38030, 38039, 38047, 38056, 38064, 38072, 38081, 38089, 38097,
1207 38105, 38113, 38121, 38128, 38136, 38144, 38151, 38159, 38166, 38174, 38181, 38188, 38195, 38202, 38210, 38217],
1208 [38224, 38237, 38251, 38264, 38278, 38290, 38303, 38316, 38328, 38341, 38353, 38365, 38376, 38388, 38400, 38411,
1209 38422, 38433, 38444, 38455, 38465, 38476, 38486, 38497, 38507, 38517, 38527, 38537, 38546, 38556, 38565, 38575,
1210 38584, 38593, 38603, 38612, 38621, 38629, 38638, 38647, 38655, 38664, 38672, 38681, 38689, 38697, 38705, 38713,
1211 38721, 38729, 38737, 38745, 38753, 38760, 38768, 38775, 38783, 38790, 38797, 38805, 38812, 38819, 38826, 38833],
1212 [38840, 38854, 38867, 38881, 38894, 38907, 38920, 38932, 38945, 38957, 38969, 38981, 38993, 39005, 39016, 39027,
1213 39039, 39050, 39061, 39071, 39082, 39092, 39103, 39113, 39123, 39133, 39143, 39153, 39163, 39172, 39182, 39191,
1214 39201, 39210, 39219, 39228, 39237, 39246, 39255, 39263, 39272, 39280, 39289, 39297, 39305, 39314, 39322, 39330,
1215 39338, 39346, 39354, 39361, 39369, 39377, 39384, 39392, 39399, 39407, 39414, 39421, 39428, 39436, 39443, 39450],
1218 /// Approximate `log10(numerator / denominator) * 2048` using a look-up table.
1220 pub fn negative_log10_times_2048(numerator: u64, denominator: u64) -> u64 {
1221 // Multiply the -1 through to avoid needing to use signed numbers.
1222 (log10_times_2048(denominator) - log10_times_2048(numerator)) as u64
1226 fn log10_times_2048(x: u64) -> u16 {
1227 debug_assert_ne!(x, 0);
1228 let most_significant_bit = HIGHEST_BIT - x.leading_zeros();
1229 let lower_bits = (x >> most_significant_bit.saturating_sub(LOWER_BITS)) & LOWER_BITMASK;
1230 LOG10_TIMES_2048[most_significant_bit as usize][lower_bits as usize]
1238 fn prints_negative_log10_times_2048_lookup_table() {
1239 for msb in 0..BITS {
1240 for i in 0..LOWER_BITS_BOUND {
1241 let x = ((LOWER_BITS_BOUND + i) << (HIGHEST_BIT - LOWER_BITS)) >> (HIGHEST_BIT - msb);
1242 let log10_times_2048 = ((x as f64).log10() * 2048.0).round() as u16;
1243 assert_eq!(log10_times_2048, LOG10_TIMES_2048[msb as usize][i as usize]);
1245 if i % LOWER_BITS_BOUND == 0 {
1246 print!("\t\t[{}, ", log10_times_2048);
1247 } else if i % LOWER_BITS_BOUND == LOWER_BITS_BOUND - 1 {
1248 println!("{}],", log10_times_2048);
1249 } else if i % (LOWER_BITS_BOUND/4) == LOWER_BITS_BOUND/4 - 1 {
1250 print!("{},\n\t\t\t", log10_times_2048);
1252 print!("{}, ", log10_times_2048);
1260 impl<G: Deref<Target = NetworkGraph>, L: Deref, T: Time> Writeable for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1262 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
1263 write_tlv_fields!(w, {
1264 (0, self.channel_liquidities, required)
1270 impl<G: Deref<Target = NetworkGraph>, L: Deref, T: Time>
1271 ReadableArgs<(ProbabilisticScoringParameters, G, L)> for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1274 r: &mut R, args: (ProbabilisticScoringParameters, G, L)
1275 ) -> Result<Self, DecodeError> {
1276 let (params, network_graph, logger) = args;
1277 let mut channel_liquidities = HashMap::new();
1278 read_tlv_fields!(r, {
1279 (0, channel_liquidities, required)
1285 channel_liquidities,
1290 impl<T: Time> Writeable for ChannelLiquidity<T> {
1292 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
1293 let duration_since_epoch = T::duration_since_epoch() - self.last_updated.elapsed();
1294 write_tlv_fields!(w, {
1295 (0, self.min_liquidity_offset_msat, required),
1296 (2, self.max_liquidity_offset_msat, required),
1297 (4, duration_since_epoch, required),
1303 impl<T: Time> Readable for ChannelLiquidity<T> {
1305 fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
1306 let mut min_liquidity_offset_msat = 0;
1307 let mut max_liquidity_offset_msat = 0;
1308 let mut duration_since_epoch = Duration::from_secs(0);
1309 read_tlv_fields!(r, {
1310 (0, min_liquidity_offset_msat, required),
1311 (2, max_liquidity_offset_msat, required),
1312 (4, duration_since_epoch, required),
1315 min_liquidity_offset_msat,
1316 max_liquidity_offset_msat,
1317 last_updated: T::now() - (T::duration_since_epoch() - duration_since_epoch),
1322 pub(crate) mod time {
1324 use core::time::Duration;
1325 /// A measurement of time.
1326 pub trait Time: Copy + Sub<Duration, Output = Self> where Self: Sized {
1327 /// Returns an instance corresponding to the current moment.
1330 /// Returns the amount of time elapsed since `self` was created.
1331 fn elapsed(&self) -> Duration;
1333 /// Returns the amount of time passed between `earlier` and `self`.
1334 fn duration_since(&self, earlier: Self) -> Duration;
1336 /// Returns the amount of time passed since the beginning of [`Time`].
1338 /// Used during (de-)serialization.
1339 fn duration_since_epoch() -> Duration;
1342 /// A state in which time has no meaning.
1343 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
1344 pub struct Eternity;
1346 #[cfg(not(feature = "no-std"))]
1347 impl Time for std::time::Instant {
1349 std::time::Instant::now()
1352 fn duration_since(&self, earlier: Self) -> Duration {
1353 self.duration_since(earlier)
1356 fn duration_since_epoch() -> Duration {
1357 use std::time::SystemTime;
1358 SystemTime::now().duration_since(SystemTime::UNIX_EPOCH).unwrap()
1361 fn elapsed(&self) -> Duration {
1362 std::time::Instant::elapsed(self)
1366 impl Time for Eternity {
1371 fn duration_since(&self, _earlier: Self) -> Duration {
1372 Duration::from_secs(0)
1375 fn duration_since_epoch() -> Duration {
1376 Duration::from_secs(0)
1379 fn elapsed(&self) -> Duration {
1380 Duration::from_secs(0)
1384 impl Sub<Duration> for Eternity {
1387 fn sub(self, _other: Duration) -> Self {
1393 pub(crate) use self::time::Time;
1397 use super::{ChannelLiquidity, ProbabilisticScoringParameters, ProbabilisticScorerUsingTime, ScoringParameters, ScorerUsingTime, Time};
1398 use super::time::Eternity;
1400 use ln::features::{ChannelFeatures, NodeFeatures};
1401 use ln::msgs::{ChannelAnnouncement, ChannelUpdate, OptionalField, UnsignedChannelAnnouncement, UnsignedChannelUpdate};
1402 use routing::scoring::Score;
1403 use routing::network_graph::{NetworkGraph, NodeId};
1404 use routing::router::RouteHop;
1405 use util::ser::{Readable, ReadableArgs, Writeable};
1406 use util::test_utils::TestLogger;
1408 use bitcoin::blockdata::constants::genesis_block;
1409 use bitcoin::hashes::Hash;
1410 use bitcoin::hashes::sha256d::Hash as Sha256dHash;
1411 use bitcoin::network::constants::Network;
1412 use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey};
1413 use core::cell::Cell;
1415 use core::time::Duration;
1420 /// Time that can be advanced manually in tests.
1421 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
1422 struct SinceEpoch(Duration);
1426 static ELAPSED: Cell<Duration> = core::cell::Cell::new(Duration::from_secs(0));
1429 fn advance(duration: Duration) {
1430 Self::ELAPSED.with(|elapsed| elapsed.set(elapsed.get() + duration))
1434 impl Time for SinceEpoch {
1436 Self(Self::duration_since_epoch())
1439 fn duration_since(&self, earlier: Self) -> Duration {
1443 fn duration_since_epoch() -> Duration {
1444 Self::ELAPSED.with(|elapsed| elapsed.get())
1447 fn elapsed(&self) -> Duration {
1448 Self::duration_since_epoch() - self.0
1452 impl Sub<Duration> for SinceEpoch {
1455 fn sub(self, other: Duration) -> Self {
1456 Self(self.0 - other)
1461 fn time_passes_when_advanced() {
1462 let now = SinceEpoch::now();
1463 assert_eq!(now.elapsed(), Duration::from_secs(0));
1465 SinceEpoch::advance(Duration::from_secs(1));
1466 SinceEpoch::advance(Duration::from_secs(1));
1468 let elapsed = now.elapsed();
1469 let later = SinceEpoch::now();
1471 assert_eq!(elapsed, Duration::from_secs(2));
1472 assert_eq!(later - elapsed, now);
1476 fn time_never_passes_in_an_eternity() {
1477 let now = Eternity::now();
1478 let elapsed = now.elapsed();
1479 let later = Eternity::now();
1481 assert_eq!(now.elapsed(), Duration::from_secs(0));
1482 assert_eq!(later - elapsed, now);
1487 /// A scorer for testing with time that can be manually advanced.
1488 type Scorer = ScorerUsingTime::<SinceEpoch>;
1490 fn source_privkey() -> SecretKey {
1491 SecretKey::from_slice(&[42; 32]).unwrap()
1494 fn target_privkey() -> SecretKey {
1495 SecretKey::from_slice(&[43; 32]).unwrap()
1498 fn source_pubkey() -> PublicKey {
1499 let secp_ctx = Secp256k1::new();
1500 PublicKey::from_secret_key(&secp_ctx, &source_privkey())
1503 fn target_pubkey() -> PublicKey {
1504 let secp_ctx = Secp256k1::new();
1505 PublicKey::from_secret_key(&secp_ctx, &target_privkey())
1508 fn source_node_id() -> NodeId {
1509 NodeId::from_pubkey(&source_pubkey())
1512 fn target_node_id() -> NodeId {
1513 NodeId::from_pubkey(&target_pubkey())
1517 fn penalizes_without_channel_failures() {
1518 let scorer = Scorer::new(ScoringParameters {
1519 base_penalty_msat: 1_000,
1520 failure_penalty_msat: 512,
1521 failure_penalty_half_life: Duration::from_secs(1),
1522 overuse_penalty_start_1024th: 1024,
1523 overuse_penalty_msat_per_1024th: 0,
1525 let source = source_node_id();
1526 let target = target_node_id();
1527 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1529 SinceEpoch::advance(Duration::from_secs(1));
1530 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1534 fn accumulates_channel_failure_penalties() {
1535 let mut scorer = Scorer::new(ScoringParameters {
1536 base_penalty_msat: 1_000,
1537 failure_penalty_msat: 64,
1538 failure_penalty_half_life: Duration::from_secs(10),
1539 overuse_penalty_start_1024th: 1024,
1540 overuse_penalty_msat_per_1024th: 0,
1542 let source = source_node_id();
1543 let target = target_node_id();
1544 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1546 scorer.payment_path_failed(&[], 42);
1547 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_064);
1549 scorer.payment_path_failed(&[], 42);
1550 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_128);
1552 scorer.payment_path_failed(&[], 42);
1553 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_192);
1557 fn decays_channel_failure_penalties_over_time() {
1558 let mut scorer = Scorer::new(ScoringParameters {
1559 base_penalty_msat: 1_000,
1560 failure_penalty_msat: 512,
1561 failure_penalty_half_life: Duration::from_secs(10),
1562 overuse_penalty_start_1024th: 1024,
1563 overuse_penalty_msat_per_1024th: 0,
1565 let source = source_node_id();
1566 let target = target_node_id();
1567 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1569 scorer.payment_path_failed(&[], 42);
1570 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1572 SinceEpoch::advance(Duration::from_secs(9));
1573 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1575 SinceEpoch::advance(Duration::from_secs(1));
1576 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1578 SinceEpoch::advance(Duration::from_secs(10 * 8));
1579 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_001);
1581 SinceEpoch::advance(Duration::from_secs(10));
1582 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1584 SinceEpoch::advance(Duration::from_secs(10));
1585 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1589 fn decays_channel_failure_penalties_without_shift_overflow() {
1590 let mut scorer = Scorer::new(ScoringParameters {
1591 base_penalty_msat: 1_000,
1592 failure_penalty_msat: 512,
1593 failure_penalty_half_life: Duration::from_secs(10),
1594 overuse_penalty_start_1024th: 1024,
1595 overuse_penalty_msat_per_1024th: 0,
1597 let source = source_node_id();
1598 let target = target_node_id();
1599 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1601 scorer.payment_path_failed(&[], 42);
1602 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1604 // An unchecked right shift 64 bits or more in ChannelFailure::decayed_penalty_msat would
1605 // cause an overflow.
1606 SinceEpoch::advance(Duration::from_secs(10 * 64));
1607 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1609 SinceEpoch::advance(Duration::from_secs(10));
1610 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1614 fn accumulates_channel_failure_penalties_after_decay() {
1615 let mut scorer = Scorer::new(ScoringParameters {
1616 base_penalty_msat: 1_000,
1617 failure_penalty_msat: 512,
1618 failure_penalty_half_life: Duration::from_secs(10),
1619 overuse_penalty_start_1024th: 1024,
1620 overuse_penalty_msat_per_1024th: 0,
1622 let source = source_node_id();
1623 let target = target_node_id();
1624 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1626 scorer.payment_path_failed(&[], 42);
1627 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1629 SinceEpoch::advance(Duration::from_secs(10));
1630 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1632 scorer.payment_path_failed(&[], 42);
1633 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_768);
1635 SinceEpoch::advance(Duration::from_secs(10));
1636 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_384);
1640 fn reduces_channel_failure_penalties_after_success() {
1641 let mut scorer = Scorer::new(ScoringParameters {
1642 base_penalty_msat: 1_000,
1643 failure_penalty_msat: 512,
1644 failure_penalty_half_life: Duration::from_secs(10),
1645 overuse_penalty_start_1024th: 1024,
1646 overuse_penalty_msat_per_1024th: 0,
1648 let source = source_node_id();
1649 let target = target_node_id();
1650 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_000);
1652 scorer.payment_path_failed(&[], 42);
1653 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1655 SinceEpoch::advance(Duration::from_secs(10));
1656 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1658 let hop = RouteHop {
1659 pubkey: PublicKey::from_slice(target.as_slice()).unwrap(),
1660 node_features: NodeFeatures::known(),
1661 short_channel_id: 42,
1662 channel_features: ChannelFeatures::known(),
1664 cltv_expiry_delta: 18,
1666 scorer.payment_path_successful(&[&hop]);
1667 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_128);
1669 SinceEpoch::advance(Duration::from_secs(10));
1670 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_064);
1674 fn restores_persisted_channel_failure_penalties() {
1675 let mut scorer = Scorer::new(ScoringParameters {
1676 base_penalty_msat: 1_000,
1677 failure_penalty_msat: 512,
1678 failure_penalty_half_life: Duration::from_secs(10),
1679 overuse_penalty_start_1024th: 1024,
1680 overuse_penalty_msat_per_1024th: 0,
1682 let source = source_node_id();
1683 let target = target_node_id();
1685 scorer.payment_path_failed(&[], 42);
1686 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1688 SinceEpoch::advance(Duration::from_secs(10));
1689 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1691 scorer.payment_path_failed(&[], 43);
1692 assert_eq!(scorer.channel_penalty_msat(43, 1, 1, &source, &target), 1_512);
1694 let mut serialized_scorer = Vec::new();
1695 scorer.write(&mut serialized_scorer).unwrap();
1697 let deserialized_scorer = <Scorer>::read(&mut io::Cursor::new(&serialized_scorer)).unwrap();
1698 assert_eq!(deserialized_scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1699 assert_eq!(deserialized_scorer.channel_penalty_msat(43, 1, 1, &source, &target), 1_512);
1703 fn decays_persisted_channel_failure_penalties() {
1704 let mut scorer = Scorer::new(ScoringParameters {
1705 base_penalty_msat: 1_000,
1706 failure_penalty_msat: 512,
1707 failure_penalty_half_life: Duration::from_secs(10),
1708 overuse_penalty_start_1024th: 1024,
1709 overuse_penalty_msat_per_1024th: 0,
1711 let source = source_node_id();
1712 let target = target_node_id();
1714 scorer.payment_path_failed(&[], 42);
1715 assert_eq!(scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_512);
1717 let mut serialized_scorer = Vec::new();
1718 scorer.write(&mut serialized_scorer).unwrap();
1720 SinceEpoch::advance(Duration::from_secs(10));
1722 let deserialized_scorer = <Scorer>::read(&mut io::Cursor::new(&serialized_scorer)).unwrap();
1723 assert_eq!(deserialized_scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_256);
1725 SinceEpoch::advance(Duration::from_secs(10));
1726 assert_eq!(deserialized_scorer.channel_penalty_msat(42, 1, 1, &source, &target), 1_128);
1730 fn charges_per_1024th_penalty() {
1731 let scorer = Scorer::new(ScoringParameters {
1732 base_penalty_msat: 0,
1733 failure_penalty_msat: 0,
1734 failure_penalty_half_life: Duration::from_secs(0),
1735 overuse_penalty_start_1024th: 256,
1736 overuse_penalty_msat_per_1024th: 100,
1738 let source = source_node_id();
1739 let target = target_node_id();
1741 assert_eq!(scorer.channel_penalty_msat(42, 1_000, 1_024_000, &source, &target), 0);
1742 assert_eq!(scorer.channel_penalty_msat(42, 256_999, 1_024_000, &source, &target), 0);
1743 assert_eq!(scorer.channel_penalty_msat(42, 257_000, 1_024_000, &source, &target), 100);
1744 assert_eq!(scorer.channel_penalty_msat(42, 258_000, 1_024_000, &source, &target), 200);
1745 assert_eq!(scorer.channel_penalty_msat(42, 512_000, 1_024_000, &source, &target), 256 * 100);
1748 // `ProbabilisticScorer` tests
1750 /// A probabilistic scorer for testing with time that can be manually advanced.
1751 type ProbabilisticScorer<'a> = ProbabilisticScorerUsingTime::<&'a NetworkGraph, &'a TestLogger, SinceEpoch>;
1753 fn sender_privkey() -> SecretKey {
1754 SecretKey::from_slice(&[41; 32]).unwrap()
1757 fn recipient_privkey() -> SecretKey {
1758 SecretKey::from_slice(&[45; 32]).unwrap()
1761 fn sender_pubkey() -> PublicKey {
1762 let secp_ctx = Secp256k1::new();
1763 PublicKey::from_secret_key(&secp_ctx, &sender_privkey())
1766 fn recipient_pubkey() -> PublicKey {
1767 let secp_ctx = Secp256k1::new();
1768 PublicKey::from_secret_key(&secp_ctx, &recipient_privkey())
1771 fn sender_node_id() -> NodeId {
1772 NodeId::from_pubkey(&sender_pubkey())
1775 fn recipient_node_id() -> NodeId {
1776 NodeId::from_pubkey(&recipient_pubkey())
1779 fn network_graph() -> NetworkGraph {
1780 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1781 let mut network_graph = NetworkGraph::new(genesis_hash);
1782 add_channel(&mut network_graph, 42, source_privkey(), target_privkey());
1783 add_channel(&mut network_graph, 43, target_privkey(), recipient_privkey());
1789 network_graph: &mut NetworkGraph, short_channel_id: u64, node_1_key: SecretKey,
1790 node_2_key: SecretKey
1792 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1793 let node_1_secret = &SecretKey::from_slice(&[39; 32]).unwrap();
1794 let node_2_secret = &SecretKey::from_slice(&[40; 32]).unwrap();
1795 let secp_ctx = Secp256k1::new();
1796 let unsigned_announcement = UnsignedChannelAnnouncement {
1797 features: ChannelFeatures::known(),
1798 chain_hash: genesis_hash,
1800 node_id_1: PublicKey::from_secret_key(&secp_ctx, &node_1_key),
1801 node_id_2: PublicKey::from_secret_key(&secp_ctx, &node_2_key),
1802 bitcoin_key_1: PublicKey::from_secret_key(&secp_ctx, &node_1_secret),
1803 bitcoin_key_2: PublicKey::from_secret_key(&secp_ctx, &node_2_secret),
1804 excess_data: Vec::new(),
1806 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
1807 let signed_announcement = ChannelAnnouncement {
1808 node_signature_1: secp_ctx.sign(&msghash, &node_1_key),
1809 node_signature_2: secp_ctx.sign(&msghash, &node_2_key),
1810 bitcoin_signature_1: secp_ctx.sign(&msghash, &node_1_secret),
1811 bitcoin_signature_2: secp_ctx.sign(&msghash, &node_2_secret),
1812 contents: unsigned_announcement,
1814 let chain_source: Option<&::util::test_utils::TestChainSource> = None;
1815 network_graph.update_channel_from_announcement(
1816 &signed_announcement, &chain_source, &secp_ctx).unwrap();
1817 update_channel(network_graph, short_channel_id, node_1_key, 0);
1818 update_channel(network_graph, short_channel_id, node_2_key, 1);
1822 network_graph: &mut NetworkGraph, short_channel_id: u64, node_key: SecretKey, flags: u8
1824 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1825 let secp_ctx = Secp256k1::new();
1826 let unsigned_update = UnsignedChannelUpdate {
1827 chain_hash: genesis_hash,
1831 cltv_expiry_delta: 18,
1832 htlc_minimum_msat: 0,
1833 htlc_maximum_msat: OptionalField::Present(1_000),
1835 fee_proportional_millionths: 0,
1836 excess_data: Vec::new(),
1838 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_update.encode()[..])[..]);
1839 let signed_update = ChannelUpdate {
1840 signature: secp_ctx.sign(&msghash, &node_key),
1841 contents: unsigned_update,
1843 network_graph.update_channel(&signed_update, &secp_ctx).unwrap();
1846 fn payment_path_for_amount(amount_msat: u64) -> Vec<RouteHop> {
1849 pubkey: source_pubkey(),
1850 node_features: NodeFeatures::known(),
1851 short_channel_id: 41,
1852 channel_features: ChannelFeatures::known(),
1854 cltv_expiry_delta: 18,
1857 pubkey: target_pubkey(),
1858 node_features: NodeFeatures::known(),
1859 short_channel_id: 42,
1860 channel_features: ChannelFeatures::known(),
1862 cltv_expiry_delta: 18,
1865 pubkey: recipient_pubkey(),
1866 node_features: NodeFeatures::known(),
1867 short_channel_id: 43,
1868 channel_features: ChannelFeatures::known(),
1869 fee_msat: amount_msat,
1870 cltv_expiry_delta: 18,
1876 fn liquidity_bounds_directed_from_lowest_node_id() {
1877 let logger = TestLogger::new();
1878 let last_updated = SinceEpoch::now();
1879 let network_graph = network_graph();
1880 let params = ProbabilisticScoringParameters::default();
1881 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1884 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated
1888 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated
1890 let source = source_node_id();
1891 let target = target_node_id();
1892 let recipient = recipient_node_id();
1893 assert!(source > target);
1894 assert!(target < recipient);
1896 // Update minimum liquidity.
1898 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
1899 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1900 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1901 assert_eq!(liquidity.min_liquidity_msat(), 100);
1902 assert_eq!(liquidity.max_liquidity_msat(), 300);
1904 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1905 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1906 assert_eq!(liquidity.min_liquidity_msat(), 700);
1907 assert_eq!(liquidity.max_liquidity_msat(), 900);
1909 scorer.channel_liquidities.get_mut(&42).unwrap()
1910 .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
1911 .set_min_liquidity_msat(200);
1913 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1914 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1915 assert_eq!(liquidity.min_liquidity_msat(), 200);
1916 assert_eq!(liquidity.max_liquidity_msat(), 300);
1918 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1919 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1920 assert_eq!(liquidity.min_liquidity_msat(), 700);
1921 assert_eq!(liquidity.max_liquidity_msat(), 800);
1923 // Update maximum liquidity.
1925 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1926 .as_directed(&target, &recipient, 1_000, liquidity_offset_half_life);
1927 assert_eq!(liquidity.min_liquidity_msat(), 700);
1928 assert_eq!(liquidity.max_liquidity_msat(), 900);
1930 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1931 .as_directed(&recipient, &target, 1_000, liquidity_offset_half_life);
1932 assert_eq!(liquidity.min_liquidity_msat(), 100);
1933 assert_eq!(liquidity.max_liquidity_msat(), 300);
1935 scorer.channel_liquidities.get_mut(&43).unwrap()
1936 .as_directed_mut(&target, &recipient, 1_000, liquidity_offset_half_life)
1937 .set_max_liquidity_msat(200);
1939 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1940 .as_directed(&target, &recipient, 1_000, liquidity_offset_half_life);
1941 assert_eq!(liquidity.min_liquidity_msat(), 0);
1942 assert_eq!(liquidity.max_liquidity_msat(), 200);
1944 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1945 .as_directed(&recipient, &target, 1_000, liquidity_offset_half_life);
1946 assert_eq!(liquidity.min_liquidity_msat(), 800);
1947 assert_eq!(liquidity.max_liquidity_msat(), 1000);
1951 fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() {
1952 let logger = TestLogger::new();
1953 let last_updated = SinceEpoch::now();
1954 let network_graph = network_graph();
1955 let params = ProbabilisticScoringParameters::default();
1956 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1959 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated
1961 let source = source_node_id();
1962 let target = target_node_id();
1963 assert!(source > target);
1965 // Check initial bounds.
1966 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
1967 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1968 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1969 assert_eq!(liquidity.min_liquidity_msat(), 400);
1970 assert_eq!(liquidity.max_liquidity_msat(), 800);
1972 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1973 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1974 assert_eq!(liquidity.min_liquidity_msat(), 200);
1975 assert_eq!(liquidity.max_liquidity_msat(), 600);
1977 // Reset from source to target.
1978 scorer.channel_liquidities.get_mut(&42).unwrap()
1979 .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
1980 .set_min_liquidity_msat(900);
1982 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1983 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1984 assert_eq!(liquidity.min_liquidity_msat(), 900);
1985 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1987 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1988 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1989 assert_eq!(liquidity.min_liquidity_msat(), 0);
1990 assert_eq!(liquidity.max_liquidity_msat(), 100);
1992 // Reset from target to source.
1993 scorer.channel_liquidities.get_mut(&42).unwrap()
1994 .as_directed_mut(&target, &source, 1_000, liquidity_offset_half_life)
1995 .set_min_liquidity_msat(400);
1997 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1998 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1999 assert_eq!(liquidity.min_liquidity_msat(), 0);
2000 assert_eq!(liquidity.max_liquidity_msat(), 600);
2002 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2003 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
2004 assert_eq!(liquidity.min_liquidity_msat(), 400);
2005 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2009 fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() {
2010 let logger = TestLogger::new();
2011 let last_updated = SinceEpoch::now();
2012 let network_graph = network_graph();
2013 let params = ProbabilisticScoringParameters::default();
2014 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
2017 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated
2019 let source = source_node_id();
2020 let target = target_node_id();
2021 assert!(source > target);
2023 // Check initial bounds.
2024 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
2025 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2026 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
2027 assert_eq!(liquidity.min_liquidity_msat(), 400);
2028 assert_eq!(liquidity.max_liquidity_msat(), 800);
2030 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2031 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
2032 assert_eq!(liquidity.min_liquidity_msat(), 200);
2033 assert_eq!(liquidity.max_liquidity_msat(), 600);
2035 // Reset from source to target.
2036 scorer.channel_liquidities.get_mut(&42).unwrap()
2037 .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
2038 .set_max_liquidity_msat(300);
2040 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2041 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
2042 assert_eq!(liquidity.min_liquidity_msat(), 0);
2043 assert_eq!(liquidity.max_liquidity_msat(), 300);
2045 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2046 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
2047 assert_eq!(liquidity.min_liquidity_msat(), 700);
2048 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2050 // Reset from target to source.
2051 scorer.channel_liquidities.get_mut(&42).unwrap()
2052 .as_directed_mut(&target, &source, 1_000, liquidity_offset_half_life)
2053 .set_max_liquidity_msat(600);
2055 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2056 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
2057 assert_eq!(liquidity.min_liquidity_msat(), 400);
2058 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2060 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2061 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
2062 assert_eq!(liquidity.min_liquidity_msat(), 0);
2063 assert_eq!(liquidity.max_liquidity_msat(), 600);
2067 fn increased_penalty_nearing_liquidity_upper_bound() {
2068 let logger = TestLogger::new();
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);
2075 let source = source_node_id();
2076 let target = target_node_id();
2078 assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024_000, &source, &target), 0);
2079 assert_eq!(scorer.channel_penalty_msat(42, 10_240, 1_024_000, &source, &target), 0);
2080 assert_eq!(scorer.channel_penalty_msat(42, 102_400, 1_024_000, &source, &target), 47);
2081 assert_eq!(scorer.channel_penalty_msat(42, 1_024_000, 1_024_000, &source, &target), 2_000);
2083 assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 58);
2084 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 125);
2085 assert_eq!(scorer.channel_penalty_msat(42, 374, 1_024, &source, &target), 198);
2086 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 300);
2087 assert_eq!(scorer.channel_penalty_msat(42, 640, 1_024, &source, &target), 425);
2088 assert_eq!(scorer.channel_penalty_msat(42, 768, 1_024, &source, &target), 602);
2089 assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), 902);
2093 fn constant_penalty_outside_liquidity_bounds() {
2094 let logger = TestLogger::new();
2095 let last_updated = SinceEpoch::now();
2096 let network_graph = network_graph();
2097 let params = ProbabilisticScoringParameters {
2098 liquidity_penalty_multiplier_msat: 1_000,
2099 ..ProbabilisticScoringParameters::zero_penalty()
2101 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
2104 min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40, last_updated
2106 let source = source_node_id();
2107 let target = target_node_id();
2109 assert_eq!(scorer.channel_penalty_msat(42, 39, 100, &source, &target), 0);
2110 assert_ne!(scorer.channel_penalty_msat(42, 50, 100, &source, &target), 0);
2111 assert_ne!(scorer.channel_penalty_msat(42, 50, 100, &source, &target), u64::max_value());
2112 assert_eq!(scorer.channel_penalty_msat(42, 61, 100, &source, &target), u64::max_value());
2116 fn does_not_further_penalize_own_channel() {
2117 let logger = TestLogger::new();
2118 let network_graph = network_graph();
2119 let params = ProbabilisticScoringParameters {
2120 liquidity_penalty_multiplier_msat: 1_000,
2121 ..ProbabilisticScoringParameters::zero_penalty()
2123 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2124 let sender = sender_node_id();
2125 let source = source_node_id();
2126 let failed_path = payment_path_for_amount(500);
2127 let successful_path = payment_path_for_amount(200);
2129 assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 301);
2131 scorer.payment_path_failed(&failed_path.iter().collect::<Vec<_>>(), 41);
2132 assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 301);
2134 scorer.payment_path_successful(&successful_path.iter().collect::<Vec<_>>());
2135 assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 301);
2139 fn sets_liquidity_lower_bound_on_downstream_failure() {
2140 let logger = TestLogger::new();
2141 let network_graph = network_graph();
2142 let params = ProbabilisticScoringParameters {
2143 liquidity_penalty_multiplier_msat: 1_000,
2144 ..ProbabilisticScoringParameters::zero_penalty()
2146 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2147 let source = source_node_id();
2148 let target = target_node_id();
2149 let path = payment_path_for_amount(500);
2151 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 128);
2152 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 301);
2153 assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 602);
2155 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 43);
2157 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 0);
2158 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 0);
2159 assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 300);
2163 fn sets_liquidity_upper_bound_on_failure() {
2164 let logger = TestLogger::new();
2165 let network_graph = network_graph();
2166 let params = ProbabilisticScoringParameters {
2167 liquidity_penalty_multiplier_msat: 1_000,
2168 ..ProbabilisticScoringParameters::zero_penalty()
2170 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2171 let source = source_node_id();
2172 let target = target_node_id();
2173 let path = payment_path_for_amount(500);
2175 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 128);
2176 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 301);
2177 assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 602);
2179 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 42);
2181 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 300);
2182 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), u64::max_value());
2183 assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), u64::max_value());
2187 fn reduces_liquidity_upper_bound_along_path_on_success() {
2188 let logger = TestLogger::new();
2189 let network_graph = network_graph();
2190 let params = ProbabilisticScoringParameters {
2191 liquidity_penalty_multiplier_msat: 1_000,
2192 ..ProbabilisticScoringParameters::zero_penalty()
2194 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2195 let sender = sender_node_id();
2196 let source = source_node_id();
2197 let target = target_node_id();
2198 let recipient = recipient_node_id();
2199 let path = payment_path_for_amount(500);
2201 assert_eq!(scorer.channel_penalty_msat(41, 250, 1_000, &sender, &source), 128);
2202 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 128);
2203 assert_eq!(scorer.channel_penalty_msat(43, 250, 1_000, &target, &recipient), 128);
2205 scorer.payment_path_successful(&path.iter().collect::<Vec<_>>());
2207 assert_eq!(scorer.channel_penalty_msat(41, 250, 1_000, &sender, &source), 128);
2208 assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 300);
2209 assert_eq!(scorer.channel_penalty_msat(43, 250, 1_000, &target, &recipient), 300);
2213 fn decays_liquidity_bounds_over_time() {
2214 let logger = TestLogger::new();
2215 let network_graph = network_graph();
2216 let params = ProbabilisticScoringParameters {
2217 liquidity_penalty_multiplier_msat: 1_000,
2218 liquidity_offset_half_life: Duration::from_secs(10),
2219 ..ProbabilisticScoringParameters::zero_penalty()
2221 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2222 let source = source_node_id();
2223 let target = target_node_id();
2225 assert_eq!(scorer.channel_penalty_msat(42, 0, 1_024, &source, &target), 0);
2226 assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024, &source, &target), 2_000);
2228 scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::<Vec<_>>(), 42);
2229 scorer.payment_path_failed(&payment_path_for_amount(128).iter().collect::<Vec<_>>(), 43);
2231 assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 0);
2232 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 93);
2233 assert_eq!(scorer.channel_penalty_msat(42, 768, 1_024, &source, &target), 1_479);
2234 assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), u64::max_value());
2236 SinceEpoch::advance(Duration::from_secs(9));
2237 assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 0);
2238 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 93);
2239 assert_eq!(scorer.channel_penalty_msat(42, 768, 1_024, &source, &target), 1_479);
2240 assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), u64::max_value());
2242 SinceEpoch::advance(Duration::from_secs(1));
2243 assert_eq!(scorer.channel_penalty_msat(42, 64, 1_024, &source, &target), 0);
2244 assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 34);
2245 assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), 1_970);
2246 assert_eq!(scorer.channel_penalty_msat(42, 960, 1_024, &source, &target), u64::max_value());
2248 // Fully decay liquidity lower bound.
2249 SinceEpoch::advance(Duration::from_secs(10 * 7));
2250 assert_eq!(scorer.channel_penalty_msat(42, 0, 1_024, &source, &target), 0);
2251 assert_eq!(scorer.channel_penalty_msat(42, 1, 1_024, &source, &target), 0);
2252 assert_eq!(scorer.channel_penalty_msat(42, 1_023, 1_024, &source, &target), 2_000);
2253 assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024, &source, &target), 2_000);
2255 // Fully decay liquidity upper bound.
2256 SinceEpoch::advance(Duration::from_secs(10));
2257 assert_eq!(scorer.channel_penalty_msat(42, 0, 1_024, &source, &target), 0);
2258 assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024, &source, &target), 2_000);
2260 SinceEpoch::advance(Duration::from_secs(10));
2261 assert_eq!(scorer.channel_penalty_msat(42, 0, 1_024, &source, &target), 0);
2262 assert_eq!(scorer.channel_penalty_msat(42, 1_024, 1_024, &source, &target), 2_000);
2266 fn decays_liquidity_bounds_without_shift_overflow() {
2267 let logger = TestLogger::new();
2268 let network_graph = network_graph();
2269 let params = ProbabilisticScoringParameters {
2270 liquidity_penalty_multiplier_msat: 1_000,
2271 liquidity_offset_half_life: Duration::from_secs(10),
2272 ..ProbabilisticScoringParameters::zero_penalty()
2274 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2275 let source = source_node_id();
2276 let target = target_node_id();
2277 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 125);
2279 scorer.payment_path_failed(&payment_path_for_amount(512).iter().collect::<Vec<_>>(), 42);
2280 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 281);
2282 // An unchecked right shift 64 bits or more in DirectedChannelLiquidity::decayed_offset_msat
2283 // would cause an overflow.
2284 SinceEpoch::advance(Duration::from_secs(10 * 64));
2285 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 125);
2287 SinceEpoch::advance(Duration::from_secs(10));
2288 assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 125);
2292 fn restricts_liquidity_bounds_after_decay() {
2293 let logger = TestLogger::new();
2294 let network_graph = network_graph();
2295 let params = ProbabilisticScoringParameters {
2296 liquidity_penalty_multiplier_msat: 1_000,
2297 liquidity_offset_half_life: Duration::from_secs(10),
2298 ..ProbabilisticScoringParameters::zero_penalty()
2300 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2301 let source = source_node_id();
2302 let target = target_node_id();
2304 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 300);
2306 // More knowledge gives higher confidence (256, 768), meaning a lower penalty.
2307 scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::<Vec<_>>(), 42);
2308 scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::<Vec<_>>(), 43);
2309 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 281);
2311 // Decaying knowledge gives less confidence (128, 896), meaning a higher penalty.
2312 SinceEpoch::advance(Duration::from_secs(10));
2313 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 291);
2315 // Reducing the upper bound gives more confidence (128, 832) that the payment amount (512)
2316 // is closer to the upper bound, meaning a higher penalty.
2317 scorer.payment_path_successful(&payment_path_for_amount(64).iter().collect::<Vec<_>>());
2318 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 331);
2320 // Increasing the lower bound gives more confidence (256, 832) that the payment amount (512)
2321 // is closer to the lower bound, meaning a lower penalty.
2322 scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::<Vec<_>>(), 43);
2323 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 245);
2325 // Further decaying affects the lower bound more than the upper bound (128, 928).
2326 SinceEpoch::advance(Duration::from_secs(10));
2327 assert_eq!(scorer.channel_penalty_msat(42, 512, 1_024, &source, &target), 280);
2331 fn restores_persisted_liquidity_bounds() {
2332 let logger = TestLogger::new();
2333 let network_graph = network_graph();
2334 let params = ProbabilisticScoringParameters {
2335 liquidity_penalty_multiplier_msat: 1_000,
2336 liquidity_offset_half_life: Duration::from_secs(10),
2337 ..ProbabilisticScoringParameters::zero_penalty()
2339 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2340 let source = source_node_id();
2341 let target = target_node_id();
2343 scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
2344 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), u64::max_value());
2346 SinceEpoch::advance(Duration::from_secs(10));
2347 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 473);
2349 scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::<Vec<_>>(), 43);
2350 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300);
2352 let mut serialized_scorer = Vec::new();
2353 scorer.write(&mut serialized_scorer).unwrap();
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), 300);
2362 fn decays_persisted_liquidity_bounds() {
2363 let logger = TestLogger::new();
2364 let network_graph = network_graph();
2365 let params = ProbabilisticScoringParameters {
2366 liquidity_penalty_multiplier_msat: 1_000,
2367 liquidity_offset_half_life: Duration::from_secs(10),
2368 ..ProbabilisticScoringParameters::zero_penalty()
2370 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2371 let source = source_node_id();
2372 let target = target_node_id();
2374 scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
2375 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), u64::max_value());
2377 let mut serialized_scorer = Vec::new();
2378 scorer.write(&mut serialized_scorer).unwrap();
2380 SinceEpoch::advance(Duration::from_secs(10));
2382 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
2383 let deserialized_scorer =
2384 <ProbabilisticScorer>::read(&mut serialized_scorer, (params, &network_graph, &logger)).unwrap();
2385 assert_eq!(deserialized_scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 473);
2387 scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::<Vec<_>>(), 43);
2388 assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300);
2390 SinceEpoch::advance(Duration::from_secs(10));
2391 assert_eq!(deserialized_scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 365);
2395 fn scores_realistic_payments() {
2396 // Shows the scores of "realistic" sends of 100k sats over channels of 1-10m sats (with a
2397 // 50k sat reserve).
2398 let logger = TestLogger::new();
2399 let network_graph = network_graph();
2400 let params = ProbabilisticScoringParameters::default();
2401 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2402 let source = source_node_id();
2403 let target = target_node_id();
2405 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 950_000_000, &source, &target), 3613);
2406 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 1_950_000_000, &source, &target), 1977);
2407 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 2_950_000_000, &source, &target), 1474);
2408 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 3_950_000_000, &source, &target), 1223);
2409 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 4_950_000_000, &source, &target), 877);
2410 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 5_950_000_000, &source, &target), 845);
2411 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 6_950_000_000, &source, &target), 500);
2412 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 7_450_000_000, &source, &target), 500);
2413 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 7_950_000_000, &source, &target), 500);
2414 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 8_950_000_000, &source, &target), 500);
2415 assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 9_950_000_000, &source, &target), 500);
2419 fn adds_base_penalty_to_liquidity_penalty() {
2420 let logger = TestLogger::new();
2421 let network_graph = network_graph();
2422 let source = source_node_id();
2423 let target = target_node_id();
2425 let params = ProbabilisticScoringParameters {
2426 liquidity_penalty_multiplier_msat: 1_000,
2427 ..ProbabilisticScoringParameters::zero_penalty()
2429 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2430 assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 58);
2432 let params = ProbabilisticScoringParameters {
2433 base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000, ..Default::default()
2435 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2436 assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 558);
2440 fn adds_amount_penalty_to_liquidity_penalty() {
2441 let logger = TestLogger::new();
2442 let network_graph = network_graph();
2443 let source = source_node_id();
2444 let target = target_node_id();
2446 let params = ProbabilisticScoringParameters {
2447 liquidity_penalty_multiplier_msat: 1_000,
2448 amount_penalty_multiplier_msat: 0,
2449 ..ProbabilisticScoringParameters::zero_penalty()
2451 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2452 assert_eq!(scorer.channel_penalty_msat(42, 512_000, 1_024_000, &source, &target), 300);
2454 let params = ProbabilisticScoringParameters {
2455 liquidity_penalty_multiplier_msat: 1_000,
2456 amount_penalty_multiplier_msat: 256,
2457 ..ProbabilisticScoringParameters::zero_penalty()
2459 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2460 assert_eq!(scorer.channel_penalty_msat(42, 512_000, 1_024_000, &source, &target), 337);
2464 fn calculates_log10_without_overflowing_u64_max_value() {
2465 let logger = TestLogger::new();
2466 let network_graph = network_graph();
2467 let source = source_node_id();
2468 let target = target_node_id();
2470 let params = ProbabilisticScoringParameters {
2471 liquidity_penalty_multiplier_msat: 40_000,
2472 ..ProbabilisticScoringParameters::zero_penalty()
2474 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2476 scorer.channel_penalty_msat(42, u64::max_value(), u64::max_value(), &source, &target),