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