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