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