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