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