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