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