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;
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 crate::ln::msgs::DecodeError;
58 use crate::routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId};
59 use crate::routing::router::RouteHop;
60 use crate::util::ser::{Readable, ReadableArgs, Writeable, Writer};
61 use crate::util::logger::Logger;
62 use crate::util::time::Time;
64 use crate::prelude::*;
66 use core::cell::{RefCell, RefMut};
67 use core::convert::TryInto;
68 use core::ops::{Deref, DerefMut};
69 use core::time::Duration;
70 use crate::io::{self, Read};
71 use crate::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 #[cfg(not(c_bindings))]
167 impl<'a, T> WriteableScore<'a> for T where T: LockableScore<'a> + Writeable {}
168 /// This is not exported to bindings users
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> {
191 /// A locked `MultiThreadedLockableScore`.
192 pub struct MultiThreadedScoreLock<'a, S: Score>(MutexGuard<'a, S>);
194 impl<'a, T: Score + 'a> Score for MultiThreadedScoreLock<'a, T> {
195 fn channel_penalty_msat(&self, scid: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage) -> u64 {
196 self.0.channel_penalty_msat(scid, source, target, usage)
198 fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
199 self.0.payment_path_failed(path, short_channel_id)
201 fn payment_path_successful(&mut self, path: &[&RouteHop]) {
202 self.0.payment_path_successful(path)
204 fn probe_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
205 self.0.probe_failed(path, short_channel_id)
207 fn probe_successful(&mut self, path: &[&RouteHop]) {
208 self.0.probe_successful(path)
212 impl<'a, T: Score + 'a> Writeable for MultiThreadedScoreLock<'a, T> {
213 fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
219 impl<'a, T: Score + 'a> LockableScore<'a> for MultiThreadedLockableScore<T> {
220 type Locked = MultiThreadedScoreLock<'a, T>;
222 fn lock(&'a self) -> MultiThreadedScoreLock<'a, T> {
223 MultiThreadedScoreLock(Mutex::lock(&self.score).unwrap())
228 impl<T: Score> Writeable for MultiThreadedLockableScore<T> {
229 fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
230 self.lock().write(writer)
235 impl<'a, T: Score + 'a> WriteableScore<'a> for MultiThreadedLockableScore<T> {}
238 impl<T: Score> MultiThreadedLockableScore<T> {
239 /// Creates a new [`MultiThreadedLockableScore`] given an underlying [`Score`].
240 pub fn new(score: T) -> Self {
241 MultiThreadedLockableScore { score: Mutex::new(score) }
246 /// This is not exported to bindings users
247 impl<'a, T: Writeable> Writeable for RefMut<'a, T> {
248 fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
249 T::write(&**self, writer)
254 /// This is not exported to bindings users
255 impl<'a, S: Writeable> Writeable for MutexGuard<'a, S> {
256 fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
257 S::write(&**self, writer)
261 /// Proposed use of a channel passed as a parameter to [`Score::channel_penalty_msat`].
262 #[derive(Clone, Copy, Debug, PartialEq)]
263 pub struct ChannelUsage {
264 /// The amount to send through the channel, denominated in millisatoshis.
265 pub amount_msat: u64,
267 /// Total amount, denominated in millisatoshis, already allocated to send through the channel
268 /// as part of a multi-path payment.
269 pub inflight_htlc_msat: u64,
271 /// The effective capacity of the channel.
272 pub effective_capacity: EffectiveCapacity,
276 /// [`Score`] implementation that uses a fixed penalty.
277 pub struct FixedPenaltyScorer {
281 impl FixedPenaltyScorer {
282 /// Creates a new scorer using `penalty_msat`.
283 pub fn with_penalty(penalty_msat: u64) -> Self {
284 Self { penalty_msat }
288 impl Score for FixedPenaltyScorer {
289 fn channel_penalty_msat(&self, _: u64, _: &NodeId, _: &NodeId, _: ChannelUsage) -> u64 {
293 fn payment_path_failed(&mut self, _path: &[&RouteHop], _short_channel_id: u64) {}
295 fn payment_path_successful(&mut self, _path: &[&RouteHop]) {}
297 fn probe_failed(&mut self, _path: &[&RouteHop], _short_channel_id: u64) {}
299 fn probe_successful(&mut self, _path: &[&RouteHop]) {}
302 impl Writeable for FixedPenaltyScorer {
304 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
305 write_tlv_fields!(w, {});
310 impl ReadableArgs<u64> for FixedPenaltyScorer {
312 fn read<R: Read>(r: &mut R, penalty_msat: u64) -> Result<Self, DecodeError> {
313 read_tlv_fields!(r, {});
314 Ok(Self { penalty_msat })
318 #[cfg(not(feature = "no-std"))]
319 type ConfiguredTime = std::time::Instant;
320 #[cfg(feature = "no-std")]
321 use crate::util::time::Eternity;
322 #[cfg(feature = "no-std")]
323 type ConfiguredTime = Eternity;
325 /// [`Score`] implementation using channel success probability distributions.
327 /// Channels are tracked with upper and lower liquidity bounds - when an HTLC fails at a channel,
328 /// we learn that the upper-bound on the available liquidity is lower than the amount of the HTLC.
329 /// When a payment is forwarded through a channel (but fails later in the route), we learn the
330 /// lower-bound on the channel's available liquidity must be at least the value of the HTLC.
332 /// These bounds are then used to determine a success probability using the formula from
333 /// *Optimally Reliable & Cheap Payment Flows on the Lightning Network* by Rene Pickhardt
334 /// and Stefan Richter [[1]] (i.e. `(upper_bound - payment_amount) / (upper_bound - lower_bound)`).
336 /// This probability is combined with the [`liquidity_penalty_multiplier_msat`] and
337 /// [`liquidity_penalty_amount_multiplier_msat`] parameters to calculate a concrete penalty in
338 /// milli-satoshis. The penalties, when added across all hops, have the property of being linear in
339 /// terms of the entire path's success probability. This allows the router to directly compare
340 /// penalties for different paths. See the documentation of those parameters for the exact formulas.
342 /// The liquidity bounds are decayed by halving them every [`liquidity_offset_half_life`].
344 /// Further, we track the history of our upper and lower liquidity bounds for each channel,
345 /// allowing us to assign a second penalty (using [`historical_liquidity_penalty_multiplier_msat`]
346 /// and [`historical_liquidity_penalty_amount_multiplier_msat`]) based on the same probability
347 /// formula, but using the history of a channel rather than our latest estimates for the liquidity
352 /// Mixing the `no-std` feature between serialization and deserialization results in undefined
355 /// [1]: https://arxiv.org/abs/2107.05322
356 /// [`liquidity_penalty_multiplier_msat`]: ProbabilisticScoringParameters::liquidity_penalty_multiplier_msat
357 /// [`liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringParameters::liquidity_penalty_amount_multiplier_msat
358 /// [`liquidity_offset_half_life`]: ProbabilisticScoringParameters::liquidity_offset_half_life
359 /// [`historical_liquidity_penalty_multiplier_msat`]: ProbabilisticScoringParameters::historical_liquidity_penalty_multiplier_msat
360 /// [`historical_liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringParameters::historical_liquidity_penalty_amount_multiplier_msat
361 pub type ProbabilisticScorer<G, L> = ProbabilisticScorerUsingTime::<G, L, ConfiguredTime>;
363 /// Probabilistic [`Score`] implementation.
365 /// This is not exported to bindings users generally all users should use the [`ProbabilisticScorer`] type alias.
366 pub struct ProbabilisticScorerUsingTime<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time>
367 where L::Target: Logger {
368 params: ProbabilisticScoringParameters,
371 // TODO: Remove entries of closed channels.
372 channel_liquidities: HashMap<u64, ChannelLiquidity<T>>,
375 /// Parameters for configuring [`ProbabilisticScorer`].
377 /// Used to configure base, liquidity, and amount penalties, the sum of which comprises the channel
378 /// penalty (i.e., the amount in msats willing to be paid to avoid routing through the channel).
380 /// The penalty applied to any channel by the [`ProbabilisticScorer`] is the sum of each of the
383 pub struct ProbabilisticScoringParameters {
384 /// A fixed penalty in msats to apply to each channel.
386 /// Default value: 500 msat
387 pub base_penalty_msat: u64,
389 /// A multiplier used with the payment amount to calculate a fixed penalty applied to each
390 /// channel, in excess of the [`base_penalty_msat`].
392 /// The purpose of the amount penalty is to avoid having fees dominate the channel cost (i.e.,
393 /// fees plus penalty) for large payments. The penalty is computed as the product of this
394 /// multiplier and `2^30`ths of the payment amount.
396 /// ie `base_penalty_amount_multiplier_msat * amount_msat / 2^30`
398 /// Default value: 8,192 msat
400 /// [`base_penalty_msat`]: Self::base_penalty_msat
401 pub base_penalty_amount_multiplier_msat: u64,
403 /// A multiplier used in conjunction with the negative `log10` of the channel's success
404 /// probability for a payment, as determined by our latest estimates of the channel's
405 /// liquidity, to determine the liquidity penalty.
407 /// The penalty is based in part on the knowledge learned from prior successful and unsuccessful
408 /// payments. This knowledge is decayed over time based on [`liquidity_offset_half_life`]. The
409 /// penalty is effectively limited to `2 * liquidity_penalty_multiplier_msat` (corresponding to
410 /// lower bounding the success probability to `0.01`) when the amount falls within the
411 /// uncertainty bounds of the channel liquidity balance. Amounts above the upper bound will
412 /// result in a `u64::max_value` penalty, however.
414 /// `-log10(success_probability) * liquidity_penalty_multiplier_msat`
416 /// Default value: 30,000 msat
418 /// [`liquidity_offset_half_life`]: Self::liquidity_offset_half_life
419 pub liquidity_penalty_multiplier_msat: u64,
421 /// Whenever this amount of time elapses since the last update to a channel's liquidity bounds,
422 /// the distance from the bounds to "zero" is cut in half. In other words, the lower-bound on
423 /// the available liquidity is halved and the upper-bound moves half-way to the channel's total
426 /// Because halving the liquidity bounds grows the uncertainty on the channel's liquidity,
427 /// the penalty for an amount within the new bounds may change. See the [`ProbabilisticScorer`]
428 /// struct documentation for more info on the way the liquidity bounds are used.
430 /// For example, if the channel's capacity is 1 million sats, and the current upper and lower
431 /// liquidity bounds are 200,000 sats and 600,000 sats, after this amount of time the upper
432 /// and lower liquidity bounds will be decayed to 100,000 and 800,000 sats.
434 /// Default value: 6 hours
438 /// When built with the `no-std` feature, time will never elapse. Therefore, the channel
439 /// liquidity knowledge will never decay except when the bounds cross.
440 pub liquidity_offset_half_life: Duration,
442 /// A multiplier used in conjunction with a payment amount and the negative `log10` of the
443 /// channel's success probability for the payment, as determined by our latest estimates of the
444 /// channel's liquidity, to determine the amount penalty.
446 /// The purpose of the amount penalty is to avoid having fees dominate the channel cost (i.e.,
447 /// fees plus penalty) for large payments. The penalty is computed as the product of this
448 /// multiplier and `2^20`ths of the payment amount, weighted by the negative `log10` of the
449 /// success probability.
451 /// `-log10(success_probability) * liquidity_penalty_amount_multiplier_msat * amount_msat / 2^20`
453 /// In practice, this means for 0.1 success probability (`-log10(0.1) == 1`) each `2^20`th of
454 /// the amount will result in a penalty of the multiplier. And, as the success probability
455 /// decreases, the negative `log10` weighting will increase dramatically. For higher success
456 /// probabilities, the multiplier will have a decreasing effect as the negative `log10` will
459 /// Default value: 192 msat
460 pub liquidity_penalty_amount_multiplier_msat: u64,
462 /// A multiplier used in conjunction with the negative `log10` of the channel's success
463 /// probability for the payment, as determined based on the history of our estimates of the
464 /// channel's available liquidity, to determine a penalty.
466 /// This penalty is similar to [`liquidity_penalty_multiplier_msat`], however, instead of using
467 /// only our latest estimate for the current liquidity available in the channel, it estimates
468 /// success probability based on the estimated liquidity available in the channel through
469 /// history. Specifically, every time we update our liquidity bounds on a given channel, we
470 /// track which of several buckets those bounds fall into, exponentially decaying the
471 /// probability of each bucket as new samples are added.
473 /// Default value: 10,000 msat
475 /// [`liquidity_penalty_multiplier_msat`]: Self::liquidity_penalty_multiplier_msat
476 pub historical_liquidity_penalty_multiplier_msat: u64,
478 /// A multiplier used in conjunction with the payment amount and the negative `log10` of the
479 /// channel's success probability for the payment, as determined based on the history of our
480 /// estimates of the channel's available liquidity, to determine a penalty.
482 /// The purpose of the amount penalty is to avoid having fees dominate the channel cost for
483 /// large payments. The penalty is computed as the product of this multiplier and the `2^20`ths
484 /// of the payment amount, weighted by the negative `log10` of the success probability.
486 /// This penalty is similar to [`liquidity_penalty_amount_multiplier_msat`], however, instead
487 /// of using only our latest estimate for the current liquidity available in the channel, it
488 /// estimates success probability based on the estimated liquidity available in the channel
489 /// through history. Specifically, every time we update our liquidity bounds on a given
490 /// channel, we track which of several buckets those bounds fall into, exponentially decaying
491 /// the probability of each bucket as new samples are added.
493 /// Default value: 64 msat
495 /// [`liquidity_penalty_amount_multiplier_msat`]: Self::liquidity_penalty_amount_multiplier_msat
496 pub historical_liquidity_penalty_amount_multiplier_msat: u64,
498 /// If we aren't learning any new datapoints for a channel, the historical liquidity bounds
499 /// tracking can simply live on with increasingly stale data. Instead, when a channel has not
500 /// seen a liquidity estimate update for this amount of time, the historical datapoints are
503 /// Note that after 16 or more half lives all historical data will be completely gone.
505 /// Default value: 14 days
506 pub historical_no_updates_half_life: Duration,
508 /// Manual penalties used for the given nodes. Allows to set a particular penalty for a given
509 /// node. Note that a manual penalty of `u64::max_value()` means the node would not ever be
510 /// considered during path finding.
512 /// This is not exported to bindings users
513 pub manual_node_penalties: HashMap<NodeId, u64>,
515 /// This penalty is applied when `htlc_maximum_msat` is equal to or larger than half of the
516 /// channel's capacity, which makes us prefer nodes with a smaller `htlc_maximum_msat`. We
517 /// treat such nodes preferentially as this makes balance discovery attacks harder to execute,
518 /// thereby creating an incentive to restrict `htlc_maximum_msat` and improve privacy.
520 /// Default value: 250 msat
521 pub anti_probing_penalty_msat: u64,
523 /// This penalty is applied when the amount we're attempting to send over a channel exceeds our
524 /// current estimate of the channel's available liquidity.
526 /// Note that in this case all other penalties, including the
527 /// [`liquidity_penalty_multiplier_msat`] and [`liquidity_penalty_amount_multiplier_msat`]-based
528 /// penalties, as well as the [`base_penalty_msat`] and the [`anti_probing_penalty_msat`], if
529 /// applicable, are still included in the overall penalty.
531 /// If you wish to avoid creating paths with such channels entirely, setting this to a value of
532 /// `u64::max_value()` will guarantee that.
534 /// Default value: 1_0000_0000_000 msat (1 Bitcoin)
536 /// [`liquidity_penalty_multiplier_msat`]: Self::liquidity_penalty_multiplier_msat
537 /// [`liquidity_penalty_amount_multiplier_msat`]: Self::liquidity_penalty_amount_multiplier_msat
538 /// [`base_penalty_msat`]: Self::base_penalty_msat
539 /// [`anti_probing_penalty_msat`]: Self::anti_probing_penalty_msat
540 pub considered_impossible_penalty_msat: u64,
543 /// Tracks the historical state of a distribution as a weighted average of how much time was spent
544 /// in each of 8 buckets.
545 #[derive(Clone, Copy)]
546 struct HistoricalBucketRangeTracker {
550 impl HistoricalBucketRangeTracker {
551 fn new() -> Self { Self { buckets: [0; 8] } }
552 fn track_datapoint(&mut self, liquidity_offset_msat: u64, capacity_msat: u64) {
553 // We have 8 leaky buckets for min and max liquidity. Each bucket tracks the amount of time
554 // we spend in each bucket as a 16-bit fixed-point number with a 5 bit fractional part.
556 // Each time we update our liquidity estimate, we add 32 (1.0 in our fixed-point system) to
557 // the buckets for the current min and max liquidity offset positions.
559 // We then decay each bucket by multiplying by 2047/2048 (avoiding dividing by a
560 // non-power-of-two). This ensures we can't actually overflow the u16 - when we get to
561 // 63,457 adding 32 and decaying by 2047/2048 leaves us back at 63,457.
563 // In total, this allows us to track data for the last 8,000 or so payments across a given
566 // These constants are a balance - we try to fit in 2 bytes per bucket to reduce overhead,
567 // and need to balance having more bits in the decimal part (to ensure decay isn't too
568 // non-linear) with having too few bits in the mantissa, causing us to not store very many
571 // The constants were picked experimentally, selecting a decay amount that restricts us
572 // from overflowing buckets without having to cap them manually.
574 // Ensure the bucket index is in the range [0, 7], even if the liquidity offset is zero or
575 // the channel's capacity, though the second should generally never happen.
576 debug_assert!(liquidity_offset_msat <= capacity_msat);
577 let bucket_idx: u8 = (liquidity_offset_msat * 8 / capacity_msat.saturating_add(1))
578 .try_into().unwrap_or(32); // 32 is bogus for 8 buckets, and will be ignored
579 debug_assert!(bucket_idx < 8);
581 for e in self.buckets.iter_mut() {
582 *e = ((*e as u32) * 2047 / 2048) as u16;
584 self.buckets[bucket_idx as usize] = self.buckets[bucket_idx as usize].saturating_add(32);
587 /// Decay all buckets by the given number of half-lives. Used to more aggressively remove old
588 /// datapoints as we receive newer information.
589 fn time_decay_data(&mut self, half_lives: u32) {
590 for e in self.buckets.iter_mut() {
591 *e = e.checked_shr(half_lives).unwrap_or(0);
596 impl_writeable_tlv_based!(HistoricalBucketRangeTracker, { (0, buckets, required) });
598 struct HistoricalMinMaxBuckets<'a> {
599 min_liquidity_offset_history: &'a HistoricalBucketRangeTracker,
600 max_liquidity_offset_history: &'a HistoricalBucketRangeTracker,
603 impl HistoricalMinMaxBuckets<'_> {
605 fn get_decayed_buckets<T: Time>(&self, now: T, last_updated: T, half_life: Duration)
606 -> ([u16; 8], [u16; 8], u32) {
607 let required_decays = now.duration_since(last_updated).as_secs()
608 .checked_div(half_life.as_secs())
609 .map_or(u32::max_value(), |decays| cmp::min(decays, u32::max_value() as u64) as u32);
610 let mut min_buckets = *self.min_liquidity_offset_history;
611 min_buckets.time_decay_data(required_decays);
612 let mut max_buckets = *self.max_liquidity_offset_history;
613 max_buckets.time_decay_data(required_decays);
614 (min_buckets.buckets, max_buckets.buckets, required_decays)
618 fn calculate_success_probability_times_billion<T: Time>(
619 &self, now: T, last_updated: T, half_life: Duration, payment_amt_64th_bucket: u8)
621 // If historical penalties are enabled, calculate the penalty by walking the set of
622 // historical liquidity bucket (min, max) combinations (where min_idx < max_idx) and, for
623 // each, calculate the probability of success given our payment amount, then total the
624 // weighted average probability of success.
626 // We use a sliding scale to decide which point within a given bucket will be compared to
627 // the amount being sent - for lower-bounds, the amount being sent is compared to the lower
628 // edge of the first bucket (i.e. zero), but compared to the upper 7/8ths of the last
629 // bucket (i.e. 9 times the index, or 63), with each bucket in between increasing the
630 // comparison point by 1/64th. For upper-bounds, the same applies, however with an offset
631 // of 1/64th (i.e. starting at one and ending at 64). This avoids failing to assign
632 // penalties to channels at the edges.
634 // If we used the bottom edge of buckets, we'd end up never assigning any penalty at all to
635 // such a channel when sending less than ~0.19% of the channel's capacity (e.g. ~200k sats
636 // for a 1 BTC channel!).
638 // If we used the middle of each bucket we'd never assign any penalty at all when sending
639 // less than 1/16th of a channel's capacity, or 1/8th if we used the top of the bucket.
640 let mut total_valid_points_tracked = 0;
642 // Check if all our buckets are zero, once decayed and treat it as if we had no data. We
643 // don't actually use the decayed buckets, though, as that would lose precision.
644 let (decayed_min_buckets, decayed_max_buckets, required_decays) =
645 self.get_decayed_buckets(now, last_updated, half_life);
646 if decayed_min_buckets.iter().all(|v| *v == 0) || decayed_max_buckets.iter().all(|v| *v == 0) {
650 for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate() {
651 for max_bucket in self.max_liquidity_offset_history.buckets.iter().take(8 - min_idx) {
652 total_valid_points_tracked += (*min_bucket as u64) * (*max_bucket as u64);
655 // If the total valid points is smaller than 1.0 (i.e. 32 in our fixed-point scheme), treat
656 // it as if we were fully decayed.
657 if total_valid_points_tracked.checked_shr(required_decays).unwrap_or(0) < 32*32 {
661 let mut cumulative_success_prob_times_billion = 0;
662 for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate() {
663 for (max_idx, max_bucket) in self.max_liquidity_offset_history.buckets.iter().enumerate().take(8 - min_idx) {
664 let bucket_prob_times_million = (*min_bucket as u64) * (*max_bucket as u64)
665 * 1024 * 1024 / total_valid_points_tracked;
666 let min_64th_bucket = min_idx as u8 * 9;
667 let max_64th_bucket = (7 - max_idx as u8) * 9 + 1;
668 if payment_amt_64th_bucket > max_64th_bucket {
669 // Success probability 0, the payment amount is above the max liquidity
670 } else if payment_amt_64th_bucket <= min_64th_bucket {
671 cumulative_success_prob_times_billion += bucket_prob_times_million * 1024;
673 cumulative_success_prob_times_billion += bucket_prob_times_million *
674 ((max_64th_bucket - payment_amt_64th_bucket) as u64) * 1024 /
675 ((max_64th_bucket - min_64th_bucket) as u64);
680 Some(cumulative_success_prob_times_billion)
684 /// Accounting for channel liquidity balance uncertainty.
686 /// Direction is defined in terms of [`NodeId`] partial ordering, where the source node is the
687 /// first node in the ordering of the channel's counterparties. Thus, swapping the two liquidity
688 /// offset fields gives the opposite direction.
689 struct ChannelLiquidity<T: Time> {
690 /// Lower channel liquidity bound in terms of an offset from zero.
691 min_liquidity_offset_msat: u64,
693 /// Upper channel liquidity bound in terms of an offset from the effective capacity.
694 max_liquidity_offset_msat: u64,
696 /// Time when the liquidity bounds were last modified.
699 min_liquidity_offset_history: HistoricalBucketRangeTracker,
700 max_liquidity_offset_history: HistoricalBucketRangeTracker,
703 /// A snapshot of [`ChannelLiquidity`] in one direction assuming a certain channel capacity and
704 /// decayed with a given half life.
705 struct DirectedChannelLiquidity<'a, L: Deref<Target = u64>, BRT: Deref<Target = HistoricalBucketRangeTracker>, T: Time, U: Deref<Target = T>> {
706 min_liquidity_offset_msat: L,
707 max_liquidity_offset_msat: L,
708 min_liquidity_offset_history: BRT,
709 max_liquidity_offset_history: BRT,
710 inflight_htlc_msat: u64,
714 params: &'a ProbabilisticScoringParameters,
717 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
718 /// Creates a new scorer using the given scoring parameters for sending payments from a node
719 /// through a network graph.
720 pub fn new(params: ProbabilisticScoringParameters, network_graph: G, logger: L) -> Self {
725 channel_liquidities: HashMap::new(),
730 fn with_channel(mut self, short_channel_id: u64, liquidity: ChannelLiquidity<T>) -> Self {
731 assert!(self.channel_liquidities.insert(short_channel_id, liquidity).is_none());
735 /// Dump the contents of this scorer into the configured logger.
737 /// Note that this writes roughly one line per channel for which we have a liquidity estimate,
738 /// which may be a substantial amount of log output.
739 pub fn debug_log_liquidity_stats(&self) {
742 let graph = self.network_graph.read_only();
743 for (scid, liq) in self.channel_liquidities.iter() {
744 if let Some(chan_debug) = graph.channels().get(scid) {
745 let log_direction = |source, target| {
746 if let Some((directed_info, _)) = chan_debug.as_directed_to(target) {
747 let amt = directed_info.effective_capacity().as_msat();
748 let dir_liq = liq.as_directed(source, target, 0, amt, &self.params);
750 let buckets = HistoricalMinMaxBuckets {
751 min_liquidity_offset_history: &dir_liq.min_liquidity_offset_history,
752 max_liquidity_offset_history: &dir_liq.max_liquidity_offset_history,
754 let (min_buckets, max_buckets, _) = buckets.get_decayed_buckets(now,
755 *dir_liq.last_updated, self.params.historical_no_updates_half_life);
757 log_debug!(self.logger, core::concat!(
758 "Liquidity from {} to {} via {} is in the range ({}, {}).\n",
759 "\tHistorical min liquidity octile relative probabilities: {} {} {} {} {} {} {} {}\n",
760 "\tHistorical max liquidity octile relative probabilities: {} {} {} {} {} {} {} {}"),
761 source, target, scid, dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat(),
762 min_buckets[0], min_buckets[1], min_buckets[2], min_buckets[3],
763 min_buckets[4], min_buckets[5], min_buckets[6], min_buckets[7],
764 // Note that the liquidity buckets are an offset from the edge, so we
765 // inverse the max order to get the probabilities from zero.
766 max_buckets[7], max_buckets[6], max_buckets[5], max_buckets[4],
767 max_buckets[3], max_buckets[2], max_buckets[1], max_buckets[0]);
769 log_debug!(self.logger, "No amount known for SCID {} from {:?} to {:?}", scid, source, target);
773 log_direction(&chan_debug.node_one, &chan_debug.node_two);
774 log_direction(&chan_debug.node_two, &chan_debug.node_one);
776 log_debug!(self.logger, "No network graph entry for SCID {}", scid);
781 /// Query the estimated minimum and maximum liquidity available for sending a payment over the
782 /// channel with `scid` towards the given `target` node.
783 pub fn estimated_channel_liquidity_range(&self, scid: u64, target: &NodeId) -> Option<(u64, u64)> {
784 let graph = self.network_graph.read_only();
786 if let Some(chan) = graph.channels().get(&scid) {
787 if let Some(liq) = self.channel_liquidities.get(&scid) {
788 if let Some((directed_info, source)) = chan.as_directed_to(target) {
789 let amt = directed_info.effective_capacity().as_msat();
790 let dir_liq = liq.as_directed(source, target, 0, amt, &self.params);
791 return Some((dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat()));
798 /// Query the historical estimated minimum and maximum liquidity available for sending a
799 /// payment over the channel with `scid` towards the given `target` node.
801 /// Returns two sets of 8 buckets. The first set describes the octiles for lower-bound
802 /// liquidity estimates, the second set describes the octiles for upper-bound liquidity
803 /// estimates. Each bucket describes the relative frequency at which we've seen a liquidity
804 /// bound in the octile relative to the channel's total capacity, on an arbitrary scale.
805 /// Because the values are slowly decayed, more recent data points are weighted more heavily
806 /// than older datapoints.
808 /// When scoring, the estimated probability that an upper-/lower-bound lies in a given octile
809 /// relative to the channel's total capacity is calculated by dividing that bucket's value with
810 /// the total of all buckets for the given bound.
812 /// For example, a value of `[0, 0, 0, 0, 0, 0, 32]` indicates that we believe the probability
813 /// of a bound being in the top octile to be 100%, and have never (recently) seen it in any
814 /// other octiles. A value of `[31, 0, 0, 0, 0, 0, 0, 32]` indicates we've seen the bound being
815 /// both in the top and bottom octile, and roughly with similar (recent) frequency.
817 /// Because the datapoints are decayed slowly over time, values will eventually return to
818 /// `Some(([0; 8], [0; 8]))`.
819 pub fn historical_estimated_channel_liquidity_probabilities(&self, scid: u64, target: &NodeId)
820 -> Option<([u16; 8], [u16; 8])> {
821 let graph = self.network_graph.read_only();
823 if let Some(chan) = graph.channels().get(&scid) {
824 if let Some(liq) = self.channel_liquidities.get(&scid) {
825 if let Some((directed_info, source)) = chan.as_directed_to(target) {
826 let amt = directed_info.effective_capacity().as_msat();
827 let dir_liq = liq.as_directed(source, target, 0, amt, &self.params);
829 let buckets = HistoricalMinMaxBuckets {
830 min_liquidity_offset_history: &dir_liq.min_liquidity_offset_history,
831 max_liquidity_offset_history: &dir_liq.max_liquidity_offset_history,
833 let (min_buckets, mut max_buckets, _) = buckets.get_decayed_buckets(T::now(),
834 *dir_liq.last_updated, self.params.historical_no_updates_half_life);
835 // Note that the liquidity buckets are an offset from the edge, so we inverse
836 // the max order to get the probabilities from zero.
837 max_buckets.reverse();
838 return Some((min_buckets, max_buckets));
845 /// Marks the node with the given `node_id` as banned, i.e.,
846 /// it will be avoided during path finding.
847 pub fn add_banned(&mut self, node_id: &NodeId) {
848 self.params.manual_node_penalties.insert(*node_id, u64::max_value());
851 /// Removes the node with the given `node_id` from the list of nodes to avoid.
852 pub fn remove_banned(&mut self, node_id: &NodeId) {
853 self.params.manual_node_penalties.remove(node_id);
856 /// Sets a manual penalty for the given node.
857 pub fn set_manual_penalty(&mut self, node_id: &NodeId, penalty: u64) {
858 self.params.manual_node_penalties.insert(*node_id, penalty);
861 /// Removes the node with the given `node_id` from the list of manual penalties.
862 pub fn remove_manual_penalty(&mut self, node_id: &NodeId) {
863 self.params.manual_node_penalties.remove(node_id);
866 /// Clears the list of manual penalties that are applied during path finding.
867 pub fn clear_manual_penalties(&mut self) {
868 self.params.manual_node_penalties = HashMap::new();
872 impl ProbabilisticScoringParameters {
874 fn zero_penalty() -> Self {
876 base_penalty_msat: 0,
877 base_penalty_amount_multiplier_msat: 0,
878 liquidity_penalty_multiplier_msat: 0,
879 liquidity_offset_half_life: Duration::from_secs(6 * 60 * 60),
880 liquidity_penalty_amount_multiplier_msat: 0,
881 historical_liquidity_penalty_multiplier_msat: 0,
882 historical_liquidity_penalty_amount_multiplier_msat: 0,
883 historical_no_updates_half_life: Duration::from_secs(60 * 60 * 24 * 14),
884 manual_node_penalties: HashMap::new(),
885 anti_probing_penalty_msat: 0,
886 considered_impossible_penalty_msat: 0,
890 /// Marks all nodes in the given list as banned, i.e.,
891 /// they will be avoided during path finding.
892 pub fn add_banned_from_list(&mut self, node_ids: Vec<NodeId>) {
894 self.manual_node_penalties.insert(id, u64::max_value());
899 impl Default for ProbabilisticScoringParameters {
900 fn default() -> Self {
902 base_penalty_msat: 500,
903 base_penalty_amount_multiplier_msat: 8192,
904 liquidity_penalty_multiplier_msat: 30_000,
905 liquidity_offset_half_life: Duration::from_secs(6 * 60 * 60),
906 liquidity_penalty_amount_multiplier_msat: 192,
907 historical_liquidity_penalty_multiplier_msat: 10_000,
908 historical_liquidity_penalty_amount_multiplier_msat: 64,
909 historical_no_updates_half_life: Duration::from_secs(60 * 60 * 24 * 14),
910 manual_node_penalties: HashMap::new(),
911 anti_probing_penalty_msat: 250,
912 considered_impossible_penalty_msat: 1_0000_0000_000,
917 impl<T: Time> ChannelLiquidity<T> {
921 min_liquidity_offset_msat: 0,
922 max_liquidity_offset_msat: 0,
923 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
924 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
925 last_updated: T::now(),
929 /// Returns a view of the channel liquidity directed from `source` to `target` assuming
932 &self, source: &NodeId, target: &NodeId, inflight_htlc_msat: u64, capacity_msat: u64,
933 params: &'a ProbabilisticScoringParameters
934 ) -> DirectedChannelLiquidity<'a, &u64, &HistoricalBucketRangeTracker, T, &T> {
935 let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) =
937 (&self.min_liquidity_offset_msat, &self.max_liquidity_offset_msat,
938 &self.min_liquidity_offset_history, &self.max_liquidity_offset_history)
940 (&self.max_liquidity_offset_msat, &self.min_liquidity_offset_msat,
941 &self.max_liquidity_offset_history, &self.min_liquidity_offset_history)
944 DirectedChannelLiquidity {
945 min_liquidity_offset_msat,
946 max_liquidity_offset_msat,
947 min_liquidity_offset_history,
948 max_liquidity_offset_history,
951 last_updated: &self.last_updated,
957 /// Returns a mutable view of the channel liquidity directed from `source` to `target` assuming
959 fn as_directed_mut<'a>(
960 &mut self, source: &NodeId, target: &NodeId, inflight_htlc_msat: u64, capacity_msat: u64,
961 params: &'a ProbabilisticScoringParameters
962 ) -> DirectedChannelLiquidity<'a, &mut u64, &mut HistoricalBucketRangeTracker, T, &mut T> {
963 let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) =
965 (&mut self.min_liquidity_offset_msat, &mut self.max_liquidity_offset_msat,
966 &mut self.min_liquidity_offset_history, &mut self.max_liquidity_offset_history)
968 (&mut self.max_liquidity_offset_msat, &mut self.min_liquidity_offset_msat,
969 &mut self.max_liquidity_offset_history, &mut self.min_liquidity_offset_history)
972 DirectedChannelLiquidity {
973 min_liquidity_offset_msat,
974 max_liquidity_offset_msat,
975 min_liquidity_offset_history,
976 max_liquidity_offset_history,
979 last_updated: &mut self.last_updated,
986 /// Bounds `-log10` to avoid excessive liquidity penalties for payments with low success
988 const NEGATIVE_LOG10_UPPER_BOUND: u64 = 2;
990 /// The rough cutoff at which our precision falls off and we should stop bothering to try to log a
991 /// ratio, as X in 1/X.
992 const PRECISION_LOWER_BOUND_DENOMINATOR: u64 = approx::LOWER_BITS_BOUND;
994 /// The divisor used when computing the amount penalty.
995 const AMOUNT_PENALTY_DIVISOR: u64 = 1 << 20;
996 const BASE_AMOUNT_PENALTY_DIVISOR: u64 = 1 << 30;
998 impl<L: Deref<Target = u64>, BRT: Deref<Target = HistoricalBucketRangeTracker>, T: Time, U: Deref<Target = T>> DirectedChannelLiquidity<'_, L, BRT, T, U> {
999 /// Returns a liquidity penalty for routing the given HTLC `amount_msat` through the channel in
1001 fn penalty_msat(&self, amount_msat: u64, params: &ProbabilisticScoringParameters) -> u64 {
1002 let max_liquidity_msat = self.max_liquidity_msat();
1003 let min_liquidity_msat = core::cmp::min(self.min_liquidity_msat(), max_liquidity_msat);
1005 let mut res = if amount_msat <= min_liquidity_msat {
1007 } else if amount_msat >= max_liquidity_msat {
1008 // Equivalent to hitting the else clause below with the amount equal to the effective
1009 // capacity and without any certainty on the liquidity upper bound, plus the
1010 // impossibility penalty.
1011 let negative_log10_times_2048 = NEGATIVE_LOG10_UPPER_BOUND * 2048;
1012 Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
1013 params.liquidity_penalty_multiplier_msat,
1014 params.liquidity_penalty_amount_multiplier_msat)
1015 .saturating_add(params.considered_impossible_penalty_msat)
1017 let numerator = (max_liquidity_msat - amount_msat).saturating_add(1);
1018 let denominator = (max_liquidity_msat - min_liquidity_msat).saturating_add(1);
1019 if amount_msat - min_liquidity_msat < denominator / PRECISION_LOWER_BOUND_DENOMINATOR {
1020 // If the failure probability is < 1.5625% (as 1 - numerator/denominator < 1/64),
1021 // don't bother trying to use the log approximation as it gets too noisy to be
1022 // particularly helpful, instead just round down to 0.
1025 let negative_log10_times_2048 =
1026 approx::negative_log10_times_2048(numerator, denominator);
1027 Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
1028 params.liquidity_penalty_multiplier_msat,
1029 params.liquidity_penalty_amount_multiplier_msat)
1033 if params.historical_liquidity_penalty_multiplier_msat != 0 ||
1034 params.historical_liquidity_penalty_amount_multiplier_msat != 0 {
1035 let payment_amt_64th_bucket = if amount_msat < u64::max_value() / 64 {
1036 amount_msat * 64 / self.capacity_msat.saturating_add(1)
1038 // Only use 128-bit arithmetic when multiplication will overflow to avoid 128-bit
1039 // division. This branch should only be hit in fuzz testing since the amount would
1040 // need to be over 2.88 million BTC in practice.
1041 ((amount_msat as u128) * 64 / (self.capacity_msat as u128).saturating_add(1))
1042 .try_into().unwrap_or(65)
1044 #[cfg(not(fuzzing))]
1045 debug_assert!(payment_amt_64th_bucket <= 64);
1046 if payment_amt_64th_bucket > 64 { return res; }
1048 let buckets = HistoricalMinMaxBuckets {
1049 min_liquidity_offset_history: &self.min_liquidity_offset_history,
1050 max_liquidity_offset_history: &self.max_liquidity_offset_history,
1052 if let Some(cumulative_success_prob_times_billion) = buckets
1053 .calculate_success_probability_times_billion(self.now, *self.last_updated,
1054 params.historical_no_updates_half_life, payment_amt_64th_bucket as u8)
1056 let historical_negative_log10_times_2048 = approx::negative_log10_times_2048(cumulative_success_prob_times_billion + 1, 1024 * 1024 * 1024);
1057 res = res.saturating_add(Self::combined_penalty_msat(amount_msat,
1058 historical_negative_log10_times_2048, params.historical_liquidity_penalty_multiplier_msat,
1059 params.historical_liquidity_penalty_amount_multiplier_msat));
1061 // If we don't have any valid points (or, once decayed, we have less than a full
1062 // point), redo the non-historical calculation with no liquidity bounds tracked and
1063 // the historical penalty multipliers.
1064 let available_capacity = self.available_capacity();
1065 let numerator = available_capacity.saturating_sub(amount_msat).saturating_add(1);
1066 let denominator = available_capacity.saturating_add(1);
1067 let negative_log10_times_2048 =
1068 approx::negative_log10_times_2048(numerator, denominator);
1069 res = res.saturating_add(Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
1070 params.historical_liquidity_penalty_multiplier_msat,
1071 params.historical_liquidity_penalty_amount_multiplier_msat));
1078 /// Computes the liquidity penalty from the penalty multipliers.
1080 fn combined_penalty_msat(amount_msat: u64, negative_log10_times_2048: u64,
1081 liquidity_penalty_multiplier_msat: u64, liquidity_penalty_amount_multiplier_msat: u64,
1083 let liquidity_penalty_msat = {
1084 // Upper bound the liquidity penalty to ensure some channel is selected.
1085 let multiplier_msat = liquidity_penalty_multiplier_msat;
1086 let max_penalty_msat = multiplier_msat.saturating_mul(NEGATIVE_LOG10_UPPER_BOUND);
1087 (negative_log10_times_2048.saturating_mul(multiplier_msat) / 2048).min(max_penalty_msat)
1089 let amount_penalty_msat = negative_log10_times_2048
1090 .saturating_mul(liquidity_penalty_amount_multiplier_msat)
1091 .saturating_mul(amount_msat) / 2048 / AMOUNT_PENALTY_DIVISOR;
1093 liquidity_penalty_msat.saturating_add(amount_penalty_msat)
1096 /// Returns the lower bound of the channel liquidity balance in this direction.
1097 fn min_liquidity_msat(&self) -> u64 {
1098 self.decayed_offset_msat(*self.min_liquidity_offset_msat)
1101 /// Returns the upper bound of the channel liquidity balance in this direction.
1102 fn max_liquidity_msat(&self) -> u64 {
1103 self.available_capacity()
1104 .saturating_sub(self.decayed_offset_msat(*self.max_liquidity_offset_msat))
1107 /// Returns the capacity minus the in-flight HTLCs in this direction.
1108 fn available_capacity(&self) -> u64 {
1109 self.capacity_msat.saturating_sub(self.inflight_htlc_msat)
1112 fn decayed_offset_msat(&self, offset_msat: u64) -> u64 {
1113 self.now.duration_since(*self.last_updated).as_secs()
1114 .checked_div(self.params.liquidity_offset_half_life.as_secs())
1115 .and_then(|decays| offset_msat.checked_shr(decays as u32))
1120 impl<L: DerefMut<Target = u64>, BRT: DerefMut<Target = HistoricalBucketRangeTracker>, T: Time, U: DerefMut<Target = T>> DirectedChannelLiquidity<'_, L, BRT, T, U> {
1121 /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat`.
1122 fn failed_at_channel<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
1123 let existing_max_msat = self.max_liquidity_msat();
1124 if amount_msat < existing_max_msat {
1125 log_debug!(logger, "Setting max liquidity of {} from {} to {}", chan_descr, existing_max_msat, amount_msat);
1126 self.set_max_liquidity_msat(amount_msat);
1128 log_trace!(logger, "Max liquidity of {} is {} (already less than or equal to {})",
1129 chan_descr, existing_max_msat, amount_msat);
1131 self.update_history_buckets();
1134 /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat` downstream.
1135 fn failed_downstream<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
1136 let existing_min_msat = self.min_liquidity_msat();
1137 if amount_msat > existing_min_msat {
1138 log_debug!(logger, "Setting min liquidity of {} from {} to {}", existing_min_msat, chan_descr, amount_msat);
1139 self.set_min_liquidity_msat(amount_msat);
1141 log_trace!(logger, "Min liquidity of {} is {} (already greater than or equal to {})",
1142 chan_descr, existing_min_msat, amount_msat);
1144 self.update_history_buckets();
1147 /// Adjusts the channel liquidity balance bounds when successfully routing `amount_msat`.
1148 fn successful<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
1149 let max_liquidity_msat = self.max_liquidity_msat().checked_sub(amount_msat).unwrap_or(0);
1150 log_debug!(logger, "Subtracting {} from max liquidity of {} (setting it to {})", amount_msat, chan_descr, max_liquidity_msat);
1151 self.set_max_liquidity_msat(max_liquidity_msat);
1152 self.update_history_buckets();
1155 fn update_history_buckets(&mut self) {
1156 let half_lives = self.now.duration_since(*self.last_updated).as_secs()
1157 .checked_div(self.params.historical_no_updates_half_life.as_secs())
1158 .map(|v| v.try_into().unwrap_or(u32::max_value())).unwrap_or(u32::max_value());
1159 self.min_liquidity_offset_history.time_decay_data(half_lives);
1160 self.max_liquidity_offset_history.time_decay_data(half_lives);
1162 let min_liquidity_offset_msat = self.decayed_offset_msat(*self.min_liquidity_offset_msat);
1163 self.min_liquidity_offset_history.track_datapoint(
1164 min_liquidity_offset_msat, self.capacity_msat
1166 let max_liquidity_offset_msat = self.decayed_offset_msat(*self.max_liquidity_offset_msat);
1167 self.max_liquidity_offset_history.track_datapoint(
1168 max_liquidity_offset_msat, self.capacity_msat
1172 /// Adjusts the lower bound of the channel liquidity balance in this direction.
1173 fn set_min_liquidity_msat(&mut self, amount_msat: u64) {
1174 *self.min_liquidity_offset_msat = amount_msat;
1175 *self.max_liquidity_offset_msat = if amount_msat > self.max_liquidity_msat() {
1178 self.decayed_offset_msat(*self.max_liquidity_offset_msat)
1180 *self.last_updated = self.now;
1183 /// Adjusts the upper bound of the channel liquidity balance in this direction.
1184 fn set_max_liquidity_msat(&mut self, amount_msat: u64) {
1185 *self.max_liquidity_offset_msat = self.capacity_msat.checked_sub(amount_msat).unwrap_or(0);
1186 *self.min_liquidity_offset_msat = if amount_msat < self.min_liquidity_msat() {
1189 self.decayed_offset_msat(*self.min_liquidity_offset_msat)
1191 *self.last_updated = self.now;
1195 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Score for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1196 fn channel_penalty_msat(
1197 &self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage
1199 if let Some(penalty) = self.params.manual_node_penalties.get(target) {
1203 let base_penalty_msat = self.params.base_penalty_msat.saturating_add(
1204 self.params.base_penalty_amount_multiplier_msat
1205 .saturating_mul(usage.amount_msat) / BASE_AMOUNT_PENALTY_DIVISOR);
1207 let mut anti_probing_penalty_msat = 0;
1208 match usage.effective_capacity {
1209 EffectiveCapacity::ExactLiquidity { liquidity_msat } => {
1210 if usage.amount_msat > liquidity_msat {
1211 return u64::max_value();
1213 return base_penalty_msat;
1216 EffectiveCapacity::Total { capacity_msat, htlc_maximum_msat } => {
1217 if htlc_maximum_msat >= capacity_msat/2 {
1218 anti_probing_penalty_msat = self.params.anti_probing_penalty_msat;
1224 let amount_msat = usage.amount_msat;
1225 let capacity_msat = usage.effective_capacity.as_msat();
1226 let inflight_htlc_msat = usage.inflight_htlc_msat;
1227 self.channel_liquidities
1228 .get(&short_channel_id)
1229 .unwrap_or(&ChannelLiquidity::new())
1230 .as_directed(source, target, inflight_htlc_msat, capacity_msat, &self.params)
1231 .penalty_msat(amount_msat, &self.params)
1232 .saturating_add(anti_probing_penalty_msat)
1233 .saturating_add(base_penalty_msat)
1236 fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
1237 let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
1238 log_trace!(self.logger, "Scoring path through to SCID {} as having failed at {} msat", short_channel_id, amount_msat);
1239 let network_graph = self.network_graph.read_only();
1240 for (hop_idx, hop) in path.iter().enumerate() {
1241 let target = NodeId::from_pubkey(&hop.pubkey);
1242 let channel_directed_from_source = network_graph.channels()
1243 .get(&hop.short_channel_id)
1244 .and_then(|channel| channel.as_directed_to(&target));
1246 let at_failed_channel = hop.short_channel_id == short_channel_id;
1247 if at_failed_channel && hop_idx == 0 {
1248 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);
1251 // Only score announced channels.
1252 if let Some((channel, source)) = channel_directed_from_source {
1253 let capacity_msat = channel.effective_capacity().as_msat();
1254 if at_failed_channel {
1255 self.channel_liquidities
1256 .entry(hop.short_channel_id)
1257 .or_insert_with(ChannelLiquidity::new)
1258 .as_directed_mut(source, &target, 0, capacity_msat, &self.params)
1259 .failed_at_channel(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1261 self.channel_liquidities
1262 .entry(hop.short_channel_id)
1263 .or_insert_with(ChannelLiquidity::new)
1264 .as_directed_mut(source, &target, 0, capacity_msat, &self.params)
1265 .failed_downstream(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1268 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).",
1269 hop.short_channel_id);
1271 if at_failed_channel { break; }
1275 fn payment_path_successful(&mut self, path: &[&RouteHop]) {
1276 let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
1277 log_trace!(self.logger, "Scoring path through SCID {} as having succeeded at {} msat.",
1278 path.split_last().map(|(hop, _)| hop.short_channel_id).unwrap_or(0), amount_msat);
1279 let network_graph = self.network_graph.read_only();
1281 let target = NodeId::from_pubkey(&hop.pubkey);
1282 let channel_directed_from_source = network_graph.channels()
1283 .get(&hop.short_channel_id)
1284 .and_then(|channel| channel.as_directed_to(&target));
1286 // Only score announced channels.
1287 if let Some((channel, source)) = channel_directed_from_source {
1288 let capacity_msat = channel.effective_capacity().as_msat();
1289 self.channel_liquidities
1290 .entry(hop.short_channel_id)
1291 .or_insert_with(ChannelLiquidity::new)
1292 .as_directed_mut(source, &target, 0, capacity_msat, &self.params)
1293 .successful(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1295 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).",
1296 hop.short_channel_id);
1301 fn probe_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
1302 self.payment_path_failed(path, short_channel_id)
1305 fn probe_successful(&mut self, path: &[&RouteHop]) {
1306 self.payment_path_failed(path, u64::max_value())
1311 const BITS: u32 = 64;
1312 const HIGHEST_BIT: u32 = BITS - 1;
1313 const LOWER_BITS: u32 = 6;
1314 pub(super) const LOWER_BITS_BOUND: u64 = 1 << LOWER_BITS;
1315 const LOWER_BITMASK: u64 = (1 << LOWER_BITS) - 1;
1317 /// Look-up table for `log10(x) * 2048` where row `i` is used for each `x` having `i` as the
1318 /// most significant bit. The next 4 bits of `x`, if applicable, are used for the second index.
1319 const LOG10_TIMES_2048: [[u16; (LOWER_BITS_BOUND) as usize]; BITS as usize] = [
1320 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1321 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1322 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1323 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
1324 [617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
1325 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
1326 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977,
1327 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977],
1328 [1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233,
1329 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431,
1330 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594,
1331 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731],
1332 [1850, 1850, 1850, 1850, 1850, 1850, 1850, 1850, 1954, 1954, 1954, 1954, 1954, 1954, 1954, 1954,
1333 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2133, 2133, 2133, 2133, 2133, 2133, 2133, 2133,
1334 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2281, 2281, 2281, 2281, 2281, 2281, 2281, 2281,
1335 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2409, 2409, 2409, 2409, 2409, 2409, 2409, 2409],
1336 [2466, 2466, 2466, 2466, 2520, 2520, 2520, 2520, 2571, 2571, 2571, 2571, 2619, 2619, 2619, 2619,
1337 2665, 2665, 2665, 2665, 2708, 2708, 2708, 2708, 2749, 2749, 2749, 2749, 2789, 2789, 2789, 2789,
1338 2827, 2827, 2827, 2827, 2863, 2863, 2863, 2863, 2898, 2898, 2898, 2898, 2931, 2931, 2931, 2931,
1339 2964, 2964, 2964, 2964, 2995, 2995, 2995, 2995, 3025, 3025, 3025, 3025, 3054, 3054, 3054, 3054],
1340 [3083, 3083, 3110, 3110, 3136, 3136, 3162, 3162, 3187, 3187, 3212, 3212, 3235, 3235, 3259, 3259,
1341 3281, 3281, 3303, 3303, 3324, 3324, 3345, 3345, 3366, 3366, 3386, 3386, 3405, 3405, 3424, 3424,
1342 3443, 3443, 3462, 3462, 3479, 3479, 3497, 3497, 3514, 3514, 3531, 3531, 3548, 3548, 3564, 3564,
1343 3580, 3580, 3596, 3596, 3612, 3612, 3627, 3627, 3642, 3642, 3656, 3656, 3671, 3671, 3685, 3685],
1344 [3699, 3713, 3726, 3740, 3753, 3766, 3779, 3791, 3804, 3816, 3828, 3840, 3852, 3864, 3875, 3886,
1345 3898, 3909, 3919, 3930, 3941, 3951, 3962, 3972, 3982, 3992, 4002, 4012, 4022, 4031, 4041, 4050,
1346 4060, 4069, 4078, 4087, 4096, 4105, 4114, 4122, 4131, 4139, 4148, 4156, 4164, 4173, 4181, 4189,
1347 4197, 4205, 4213, 4220, 4228, 4236, 4243, 4251, 4258, 4266, 4273, 4280, 4287, 4294, 4302, 4309],
1348 [4316, 4329, 4343, 4356, 4369, 4382, 4395, 4408, 4420, 4433, 4445, 4457, 4468, 4480, 4492, 4503,
1349 4514, 4525, 4536, 4547, 4557, 4568, 4578, 4589, 4599, 4609, 4619, 4629, 4638, 4648, 4657, 4667,
1350 4676, 4685, 4695, 4704, 4713, 4721, 4730, 4739, 4747, 4756, 4764, 4773, 4781, 4789, 4797, 4805,
1351 4813, 4821, 4829, 4837, 4845, 4852, 4860, 4867, 4875, 4882, 4889, 4897, 4904, 4911, 4918, 4925],
1352 [4932, 4946, 4959, 4973, 4986, 4999, 5012, 5024, 5037, 5049, 5061, 5073, 5085, 5097, 5108, 5119,
1353 5131, 5142, 5153, 5163, 5174, 5184, 5195, 5205, 5215, 5225, 5235, 5245, 5255, 5264, 5274, 5283,
1354 5293, 5302, 5311, 5320, 5329, 5338, 5347, 5355, 5364, 5372, 5381, 5389, 5397, 5406, 5414, 5422,
1355 5430, 5438, 5446, 5453, 5461, 5469, 5476, 5484, 5491, 5499, 5506, 5513, 5520, 5527, 5535, 5542],
1356 [5549, 5562, 5576, 5589, 5603, 5615, 5628, 5641, 5653, 5666, 5678, 5690, 5701, 5713, 5725, 5736,
1357 5747, 5758, 5769, 5780, 5790, 5801, 5811, 5822, 5832, 5842, 5852, 5862, 5871, 5881, 5890, 5900,
1358 5909, 5918, 5928, 5937, 5946, 5954, 5963, 5972, 5980, 5989, 5997, 6006, 6014, 6022, 6030, 6038,
1359 6046, 6054, 6062, 6070, 6078, 6085, 6093, 6100, 6108, 6115, 6122, 6130, 6137, 6144, 6151, 6158],
1360 [6165, 6179, 6192, 6206, 6219, 6232, 6245, 6257, 6270, 6282, 6294, 6306, 6318, 6330, 6341, 6352,
1361 6364, 6375, 6386, 6396, 6407, 6417, 6428, 6438, 6448, 6458, 6468, 6478, 6488, 6497, 6507, 6516,
1362 6526, 6535, 6544, 6553, 6562, 6571, 6580, 6588, 6597, 6605, 6614, 6622, 6630, 6639, 6647, 6655,
1363 6663, 6671, 6679, 6686, 6694, 6702, 6709, 6717, 6724, 6732, 6739, 6746, 6753, 6761, 6768, 6775],
1364 [6782, 6795, 6809, 6822, 6836, 6849, 6861, 6874, 6886, 6899, 6911, 6923, 6934, 6946, 6958, 6969,
1365 6980, 6991, 7002, 7013, 7023, 7034, 7044, 7055, 7065, 7075, 7085, 7095, 7104, 7114, 7124, 7133,
1366 7142, 7151, 7161, 7170, 7179, 7187, 7196, 7205, 7213, 7222, 7230, 7239, 7247, 7255, 7263, 7271,
1367 7279, 7287, 7295, 7303, 7311, 7318, 7326, 7333, 7341, 7348, 7355, 7363, 7370, 7377, 7384, 7391],
1368 [7398, 7412, 7425, 7439, 7452, 7465, 7478, 7490, 7503, 7515, 7527, 7539, 7551, 7563, 7574, 7585,
1369 7597, 7608, 7619, 7629, 7640, 7651, 7661, 7671, 7681, 7691, 7701, 7711, 7721, 7731, 7740, 7749,
1370 7759, 7768, 7777, 7786, 7795, 7804, 7813, 7821, 7830, 7838, 7847, 7855, 7864, 7872, 7880, 7888,
1371 7896, 7904, 7912, 7919, 7927, 7935, 7942, 7950, 7957, 7965, 7972, 7979, 7986, 7994, 8001, 8008],
1372 [8015, 8028, 8042, 8055, 8069, 8082, 8094, 8107, 8119, 8132, 8144, 8156, 8167, 8179, 8191, 8202,
1373 8213, 8224, 8235, 8246, 8256, 8267, 8277, 8288, 8298, 8308, 8318, 8328, 8337, 8347, 8357, 8366,
1374 8375, 8384, 8394, 8403, 8412, 8420, 8429, 8438, 8446, 8455, 8463, 8472, 8480, 8488, 8496, 8504,
1375 8512, 8520, 8528, 8536, 8544, 8551, 8559, 8566, 8574, 8581, 8588, 8596, 8603, 8610, 8617, 8624],
1376 [8631, 8645, 8659, 8672, 8685, 8698, 8711, 8723, 8736, 8748, 8760, 8772, 8784, 8796, 8807, 8818,
1377 8830, 8841, 8852, 8862, 8873, 8884, 8894, 8904, 8914, 8924, 8934, 8944, 8954, 8964, 8973, 8982,
1378 8992, 9001, 9010, 9019, 9028, 9037, 9046, 9054, 9063, 9071, 9080, 9088, 9097, 9105, 9113, 9121,
1379 9129, 9137, 9145, 9152, 9160, 9168, 9175, 9183, 9190, 9198, 9205, 9212, 9219, 9227, 9234, 9241],
1380 [9248, 9261, 9275, 9288, 9302, 9315, 9327, 9340, 9352, 9365, 9377, 9389, 9400, 9412, 9424, 9435,
1381 9446, 9457, 9468, 9479, 9490, 9500, 9510, 9521, 9531, 9541, 9551, 9561, 9570, 9580, 9590, 9599,
1382 9608, 9617, 9627, 9636, 9645, 9653, 9662, 9671, 9679, 9688, 9696, 9705, 9713, 9721, 9729, 9737,
1383 9745, 9753, 9761, 9769, 9777, 9784, 9792, 9799, 9807, 9814, 9821, 9829, 9836, 9843, 9850, 9857],
1384 [9864, 9878, 9892, 9905, 9918, 9931, 9944, 9956, 9969, 9981, 9993, 10005, 10017, 10029, 10040, 10051,
1385 10063, 10074, 10085, 10095, 10106, 10117, 10127, 10137, 10147, 10157, 10167, 10177, 10187, 10197, 10206, 10215,
1386 10225, 10234, 10243, 10252, 10261, 10270, 10279, 10287, 10296, 10304, 10313, 10321, 10330, 10338, 10346, 10354,
1387 10362, 10370, 10378, 10385, 10393, 10401, 10408, 10416, 10423, 10431, 10438, 10445, 10452, 10460, 10467, 10474],
1388 [10481, 10494, 10508, 10521, 10535, 10548, 10560, 10573, 10585, 10598, 10610, 10622, 10634, 10645, 10657, 10668,
1389 10679, 10690, 10701, 10712, 10723, 10733, 10743, 10754, 10764, 10774, 10784, 10794, 10803, 10813, 10823, 10832,
1390 10841, 10851, 10860, 10869, 10878, 10886, 10895, 10904, 10912, 10921, 10929, 10938, 10946, 10954, 10962, 10970,
1391 10978, 10986, 10994, 11002, 11010, 11017, 11025, 11032, 11040, 11047, 11054, 11062, 11069, 11076, 11083, 11090],
1392 [11097, 11111, 11125, 11138, 11151, 11164, 11177, 11189, 11202, 11214, 11226, 11238, 11250, 11262, 11273, 11284,
1393 11296, 11307, 11318, 11328, 11339, 11350, 11360, 11370, 11380, 11390, 11400, 11410, 11420, 11430, 11439, 11448,
1394 11458, 11467, 11476, 11485, 11494, 11503, 11512, 11520, 11529, 11538, 11546, 11554, 11563, 11571, 11579, 11587,
1395 11595, 11603, 11611, 11618, 11626, 11634, 11641, 11649, 11656, 11664, 11671, 11678, 11685, 11693, 11700, 11707],
1396 [11714, 11727, 11741, 11754, 11768, 11781, 11793, 11806, 11818, 11831, 11843, 11855, 11867, 11878, 11890, 11901,
1397 11912, 11923, 11934, 11945, 11956, 11966, 11976, 11987, 11997, 12007, 12017, 12027, 12036, 12046, 12056, 12065,
1398 12074, 12084, 12093, 12102, 12111, 12119, 12128, 12137, 12146, 12154, 12162, 12171, 12179, 12187, 12195, 12203,
1399 12211, 12219, 12227, 12235, 12243, 12250, 12258, 12265, 12273, 12280, 12287, 12295, 12302, 12309, 12316, 12323],
1400 [12330, 12344, 12358, 12371, 12384, 12397, 12410, 12423, 12435, 12447, 12459, 12471, 12483, 12495, 12506, 12517,
1401 12529, 12540, 12551, 12561, 12572, 12583, 12593, 12603, 12613, 12623, 12633, 12643, 12653, 12663, 12672, 12682,
1402 12691, 12700, 12709, 12718, 12727, 12736, 12745, 12753, 12762, 12771, 12779, 12787, 12796, 12804, 12812, 12820,
1403 12828, 12836, 12844, 12851, 12859, 12867, 12874, 12882, 12889, 12897, 12904, 12911, 12918, 12926, 12933, 12940],
1404 [12947, 12960, 12974, 12987, 13001, 13014, 13026, 13039, 13051, 13064, 13076, 13088, 13100, 13111, 13123, 13134,
1405 13145, 13156, 13167, 13178, 13189, 13199, 13209, 13220, 13230, 13240, 13250, 13260, 13269, 13279, 13289, 13298,
1406 13307, 13317, 13326, 13335, 13344, 13352, 13361, 13370, 13379, 13387, 13395, 13404, 13412, 13420, 13428, 13436,
1407 13444, 13452, 13460, 13468, 13476, 13483, 13491, 13498, 13506, 13513, 13521, 13528, 13535, 13542, 13549, 13556],
1408 [13563, 13577, 13591, 13604, 13617, 13630, 13643, 13656, 13668, 13680, 13692, 13704, 13716, 13728, 13739, 13750,
1409 13762, 13773, 13784, 13794, 13805, 13816, 13826, 13836, 13846, 13857, 13866, 13876, 13886, 13896, 13905, 13915,
1410 13924, 13933, 13942, 13951, 13960, 13969, 13978, 13986, 13995, 14004, 14012, 14020, 14029, 14037, 14045, 14053,
1411 14061, 14069, 14077, 14084, 14092, 14100, 14107, 14115, 14122, 14130, 14137, 14144, 14151, 14159, 14166, 14173],
1412 [14180, 14194, 14207, 14220, 14234, 14247, 14259, 14272, 14284, 14297, 14309, 14321, 14333, 14344, 14356, 14367,
1413 14378, 14389, 14400, 14411, 14422, 14432, 14443, 14453, 14463, 14473, 14483, 14493, 14502, 14512, 14522, 14531,
1414 14540, 14550, 14559, 14568, 14577, 14586, 14594, 14603, 14612, 14620, 14628, 14637, 14645, 14653, 14661, 14669,
1415 14677, 14685, 14693, 14701, 14709, 14716, 14724, 14731, 14739, 14746, 14754, 14761, 14768, 14775, 14782, 14789],
1416 [14796, 14810, 14824, 14837, 14850, 14863, 14876, 14889, 14901, 14913, 14925, 14937, 14949, 14961, 14972, 14984,
1417 14995, 15006, 15017, 15027, 15038, 15049, 15059, 15069, 15079, 15090, 15099, 15109, 15119, 15129, 15138, 15148,
1418 15157, 15166, 15175, 15184, 15193, 15202, 15211, 15219, 15228, 15237, 15245, 15253, 15262, 15270, 15278, 15286,
1419 15294, 15302, 15310, 15317, 15325, 15333, 15340, 15348, 15355, 15363, 15370, 15377, 15384, 15392, 15399, 15406],
1420 [15413, 15427, 15440, 15453, 15467, 15480, 15492, 15505, 15517, 15530, 15542, 15554, 15566, 15577, 15589, 15600,
1421 15611, 15622, 15633, 15644, 15655, 15665, 15676, 15686, 15696, 15706, 15716, 15726, 15736, 15745, 15755, 15764,
1422 15773, 15783, 15792, 15801, 15810, 15819, 15827, 15836, 15845, 15853, 15862, 15870, 15878, 15886, 15894, 15903,
1423 15910, 15918, 15926, 15934, 15942, 15949, 15957, 15964, 15972, 15979, 15987, 15994, 16001, 16008, 16015, 16022],
1424 [16029, 16043, 16057, 16070, 16083, 16096, 16109, 16122, 16134, 16146, 16158, 16170, 16182, 16194, 16205, 16217,
1425 16228, 16239, 16250, 16260, 16271, 16282, 16292, 16302, 16312, 16323, 16332, 16342, 16352, 16362, 16371, 16381,
1426 16390, 16399, 16408, 16417, 16426, 16435, 16444, 16452, 16461, 16470, 16478, 16486, 16495, 16503, 16511, 16519,
1427 16527, 16535, 16543, 16550, 16558, 16566, 16573, 16581, 16588, 16596, 16603, 16610, 16618, 16625, 16632, 16639],
1428 [16646, 16660, 16673, 16686, 16700, 16713, 16725, 16738, 16751, 16763, 16775, 16787, 16799, 16810, 16822, 16833,
1429 16844, 16855, 16866, 16877, 16888, 16898, 16909, 16919, 16929, 16939, 16949, 16959, 16969, 16978, 16988, 16997,
1430 17006, 17016, 17025, 17034, 17043, 17052, 17060, 17069, 17078, 17086, 17095, 17103, 17111, 17119, 17127, 17136,
1431 17143, 17151, 17159, 17167, 17175, 17182, 17190, 17197, 17205, 17212, 17220, 17227, 17234, 17241, 17248, 17255],
1432 [17262, 17276, 17290, 17303, 17316, 17329, 17342, 17355, 17367, 17379, 17391, 17403, 17415, 17427, 17438, 17450,
1433 17461, 17472, 17483, 17493, 17504, 17515, 17525, 17535, 17546, 17556, 17565, 17575, 17585, 17595, 17604, 17614,
1434 17623, 17632, 17641, 17650, 17659, 17668, 17677, 17685, 17694, 17703, 17711, 17719, 17728, 17736, 17744, 17752,
1435 17760, 17768, 17776, 17784, 17791, 17799, 17806, 17814, 17821, 17829, 17836, 17843, 17851, 17858, 17865, 17872],
1436 [17879, 17893, 17906, 17920, 17933, 17946, 17958, 17971, 17984, 17996, 18008, 18020, 18032, 18043, 18055, 18066,
1437 18077, 18088, 18099, 18110, 18121, 18131, 18142, 18152, 18162, 18172, 18182, 18192, 18202, 18211, 18221, 18230,
1438 18239, 18249, 18258, 18267, 18276, 18285, 18293, 18302, 18311, 18319, 18328, 18336, 18344, 18352, 18360, 18369,
1439 18377, 18384, 18392, 18400, 18408, 18415, 18423, 18430, 18438, 18445, 18453, 18460, 18467, 18474, 18481, 18488],
1440 [18495, 18509, 18523, 18536, 18549, 18562, 18575, 18588, 18600, 18612, 18624, 18636, 18648, 18660, 18671, 18683,
1441 18694, 18705, 18716, 18726, 18737, 18748, 18758, 18768, 18779, 18789, 18799, 18808, 18818, 18828, 18837, 18847,
1442 18856, 18865, 18874, 18883, 18892, 18901, 18910, 18919, 18927, 18936, 18944, 18952, 18961, 18969, 18977, 18985,
1443 18993, 19001, 19009, 19017, 19024, 19032, 19039, 19047, 19054, 19062, 19069, 19076, 19084, 19091, 19098, 19105],
1444 [19112, 19126, 19139, 19153, 19166, 19179, 19191, 19204, 19217, 19229, 19241, 19253, 19265, 19276, 19288, 19299,
1445 19310, 19321, 19332, 19343, 19354, 19364, 19375, 19385, 19395, 19405, 19415, 19425, 19435, 19444, 19454, 19463,
1446 19472, 19482, 19491, 19500, 19509, 19518, 19526, 19535, 19544, 19552, 19561, 19569, 19577, 19585, 19594, 19602,
1447 19610, 19617, 19625, 19633, 19641, 19648, 19656, 19663, 19671, 19678, 19686, 19693, 19700, 19707, 19714, 19721],
1448 [19728, 19742, 19756, 19769, 19782, 19795, 19808, 19821, 19833, 19845, 19857, 19869, 19881, 19893, 19904, 19916,
1449 19927, 19938, 19949, 19960, 19970, 19981, 19991, 20001, 20012, 20022, 20032, 20041, 20051, 20061, 20070, 20080,
1450 20089, 20098, 20107, 20116, 20125, 20134, 20143, 20152, 20160, 20169, 20177, 20185, 20194, 20202, 20210, 20218,
1451 20226, 20234, 20242, 20250, 20257, 20265, 20272, 20280, 20287, 20295, 20302, 20309, 20317, 20324, 20331, 20338],
1452 [20345, 20359, 20372, 20386, 20399, 20412, 20425, 20437, 20450, 20462, 20474, 20486, 20498, 20509, 20521, 20532,
1453 20543, 20554, 20565, 20576, 20587, 20597, 20608, 20618, 20628, 20638, 20648, 20658, 20668, 20677, 20687, 20696,
1454 20705, 20715, 20724, 20733, 20742, 20751, 20759, 20768, 20777, 20785, 20794, 20802, 20810, 20818, 20827, 20835,
1455 20843, 20850, 20858, 20866, 20874, 20881, 20889, 20896, 20904, 20911, 20919, 20926, 20933, 20940, 20947, 20954],
1456 [20961, 20975, 20989, 21002, 21015, 21028, 21041, 21054, 21066, 21078, 21090, 21102, 21114, 21126, 21137, 21149,
1457 21160, 21171, 21182, 21193, 21203, 21214, 21224, 21234, 21245, 21255, 21265, 21274, 21284, 21294, 21303, 21313,
1458 21322, 21331, 21340, 21349, 21358, 21367, 21376, 21385, 21393, 21402, 21410, 21418, 21427, 21435, 21443, 21451,
1459 21459, 21467, 21475, 21483, 21490, 21498, 21505, 21513, 21520, 21528, 21535, 21542, 21550, 21557, 21564, 21571],
1460 [21578, 21592, 21605, 21619, 21632, 21645, 21658, 21670, 21683, 21695, 21707, 21719, 21731, 21742, 21754, 21765,
1461 21776, 21787, 21798, 21809, 21820, 21830, 21841, 21851, 21861, 21871, 21881, 21891, 21901, 21910, 21920, 21929,
1462 21938, 21948, 21957, 21966, 21975, 21984, 21992, 22001, 22010, 22018, 22027, 22035, 22043, 22051, 22060, 22068,
1463 22076, 22083, 22091, 22099, 22107, 22114, 22122, 22129, 22137, 22144, 22152, 22159, 22166, 22173, 22180, 22187],
1464 [22194, 22208, 22222, 22235, 22248, 22261, 22274, 22287, 22299, 22311, 22323, 22335, 22347, 22359, 22370, 22382,
1465 22393, 22404, 22415, 22426, 22436, 22447, 22457, 22467, 22478, 22488, 22498, 22507, 22517, 22527, 22536, 22546,
1466 22555, 22564, 22573, 22582, 22591, 22600, 22609, 22618, 22626, 22635, 22643, 22651, 22660, 22668, 22676, 22684,
1467 22692, 22700, 22708, 22716, 22723, 22731, 22738, 22746, 22753, 22761, 22768, 22775, 22783, 22790, 22797, 22804],
1468 [22811, 22825, 22838, 22852, 22865, 22878, 22891, 22903, 22916, 22928, 22940, 22952, 22964, 22975, 22987, 22998,
1469 23009, 23020, 23031, 23042, 23053, 23063, 23074, 23084, 23094, 23104, 23114, 23124, 23134, 23143, 23153, 23162,
1470 23171, 23181, 23190, 23199, 23208, 23217, 23225, 23234, 23243, 23251, 23260, 23268, 23276, 23284, 23293, 23301,
1471 23309, 23316, 23324, 23332, 23340, 23347, 23355, 23363, 23370, 23377, 23385, 23392, 23399, 23406, 23413, 23420],
1472 [23427, 23441, 23455, 23468, 23481, 23494, 23507, 23520, 23532, 23544, 23556, 23568, 23580, 23592, 23603, 23615,
1473 23626, 23637, 23648, 23659, 23669, 23680, 23690, 23700, 23711, 23721, 23731, 23740, 23750, 23760, 23769, 23779,
1474 23788, 23797, 23806, 23815, 23824, 23833, 23842, 23851, 23859, 23868, 23876, 23884, 23893, 23901, 23909, 23917,
1475 23925, 23933, 23941, 23949, 23956, 23964, 23972, 23979, 23986, 23994, 24001, 24008, 24016, 24023, 24030, 24037],
1476 [24044, 24058, 24071, 24085, 24098, 24111, 24124, 24136, 24149, 24161, 24173, 24185, 24197, 24208, 24220, 24231,
1477 24242, 24253, 24264, 24275, 24286, 24296, 24307, 24317, 24327, 24337, 24347, 24357, 24367, 24376, 24386, 24395,
1478 24405, 24414, 24423, 24432, 24441, 24450, 24458, 24467, 24476, 24484, 24493, 24501, 24509, 24517, 24526, 24534,
1479 24542, 24550, 24557, 24565, 24573, 24580, 24588, 24596, 24603, 24610, 24618, 24625, 24632, 24639, 24646, 24653],
1480 [24660, 24674, 24688, 24701, 24714, 24727, 24740, 24753, 24765, 24777, 24790, 24801, 24813, 24825, 24836, 24848,
1481 24859, 24870, 24881, 24892, 24902, 24913, 24923, 24933, 24944, 24954, 24964, 24973, 24983, 24993, 25002, 25012,
1482 25021, 25030, 25039, 25048, 25057, 25066, 25075, 25084, 25092, 25101, 25109, 25117, 25126, 25134, 25142, 25150,
1483 25158, 25166, 25174, 25182, 25189, 25197, 25205, 25212, 25219, 25227, 25234, 25241, 25249, 25256, 25263, 25270],
1484 [25277, 25291, 25304, 25318, 25331, 25344, 25357, 25369, 25382, 25394, 25406, 25418, 25430, 25441, 25453, 25464,
1485 25475, 25486, 25497, 25508, 25519, 25529, 25540, 25550, 25560, 25570, 25580, 25590, 25600, 25609, 25619, 25628,
1486 25638, 25647, 25656, 25665, 25674, 25683, 25691, 25700, 25709, 25717, 25726, 25734, 25742, 25750, 25759, 25767,
1487 25775, 25783, 25790, 25798, 25806, 25813, 25821, 25829, 25836, 25843, 25851, 25858, 25865, 25872, 25879, 25886],
1488 [25893, 25907, 25921, 25934, 25947, 25960, 25973, 25986, 25998, 26010, 26023, 26034, 26046, 26058, 26069, 26081,
1489 26092, 26103, 26114, 26125, 26135, 26146, 26156, 26166, 26177, 26187, 26197, 26206, 26216, 26226, 26235, 26245,
1490 26254, 26263, 26272, 26281, 26290, 26299, 26308, 26317, 26325, 26334, 26342, 26351, 26359, 26367, 26375, 26383,
1491 26391, 26399, 26407, 26415, 26422, 26430, 26438, 26445, 26453, 26460, 26467, 26474, 26482, 26489, 26496, 26503],
1492 [26510, 26524, 26537, 26551, 26564, 26577, 26590, 26602, 26615, 26627, 26639, 26651, 26663, 26674, 26686, 26697,
1493 26708, 26719, 26730, 26741, 26752, 26762, 26773, 26783, 26793, 26803, 26813, 26823, 26833, 26842, 26852, 26861,
1494 26871, 26880, 26889, 26898, 26907, 26916, 26924, 26933, 26942, 26950, 26959, 26967, 26975, 26983, 26992, 27000,
1495 27008, 27016, 27023, 27031, 27039, 27046, 27054, 27062, 27069, 27076, 27084, 27091, 27098, 27105, 27112, 27119],
1496 [27126, 27140, 27154, 27167, 27180, 27193, 27206, 27219, 27231, 27243, 27256, 27267, 27279, 27291, 27302, 27314,
1497 27325, 27336, 27347, 27358, 27368, 27379, 27389, 27399, 27410, 27420, 27430, 27439, 27449, 27459, 27468, 27478,
1498 27487, 27496, 27505, 27514, 27523, 27532, 27541, 27550, 27558, 27567, 27575, 27584, 27592, 27600, 27608, 27616,
1499 27624, 27632, 27640, 27648, 27655, 27663, 27671, 27678, 27686, 27693, 27700, 27707, 27715, 27722, 27729, 27736],
1500 [27743, 27757, 27770, 27784, 27797, 27810, 27823, 27835, 27848, 27860, 27872, 27884, 27896, 27907, 27919, 27930,
1501 27941, 27952, 27963, 27974, 27985, 27995, 28006, 28016, 28026, 28036, 28046, 28056, 28066, 28075, 28085, 28094,
1502 28104, 28113, 28122, 28131, 28140, 28149, 28157, 28166, 28175, 28183, 28192, 28200, 28208, 28217, 28225, 28233,
1503 28241, 28249, 28256, 28264, 28272, 28280, 28287, 28295, 28302, 28309, 28317, 28324, 28331, 28338, 28345, 28352],
1504 [28359, 28373, 28387, 28400, 28413, 28426, 28439, 28452, 28464, 28476, 28489, 28501, 28512, 28524, 28535, 28547,
1505 28558, 28569, 28580, 28591, 28601, 28612, 28622, 28633, 28643, 28653, 28663, 28672, 28682, 28692, 28701, 28711,
1506 28720, 28729, 28738, 28747, 28756, 28765, 28774, 28783, 28791, 28800, 28808, 28817, 28825, 28833, 28841, 28849,
1507 28857, 28865, 28873, 28881, 28888, 28896, 28904, 28911, 28919, 28926, 28933, 28941, 28948, 28955, 28962, 28969],
1508 [28976, 28990, 29003, 29017, 29030, 29043, 29056, 29068, 29081, 29093, 29105, 29117, 29129, 29140, 29152, 29163,
1509 29174, 29185, 29196, 29207, 29218, 29228, 29239, 29249, 29259, 29269, 29279, 29289, 29299, 29308, 29318, 29327,
1510 29337, 29346, 29355, 29364, 29373, 29382, 29390, 29399, 29408, 29416, 29425, 29433, 29441, 29450, 29458, 29466,
1511 29474, 29482, 29489, 29497, 29505, 29513, 29520, 29528, 29535, 29542, 29550, 29557, 29564, 29571, 29578, 29585],
1512 [29592, 29606, 29620, 29633, 29646, 29659, 29672, 29685, 29697, 29709, 29722, 29734, 29745, 29757, 29768, 29780,
1513 29791, 29802, 29813, 29824, 29834, 29845, 29855, 29866, 29876, 29886, 29896, 29906, 29915, 29925, 29934, 29944,
1514 29953, 29962, 29971, 29980, 29989, 29998, 30007, 30016, 30024, 30033, 30041, 30050, 30058, 30066, 30074, 30082,
1515 30090, 30098, 30106, 30114, 30121, 30129, 30137, 30144, 30152, 30159, 30166, 30174, 30181, 30188, 30195, 30202],
1516 [30209, 30223, 30236, 30250, 30263, 30276, 30289, 30301, 30314, 30326, 30338, 30350, 30362, 30373, 30385, 30396,
1517 30407, 30418, 30429, 30440, 30451, 30461, 30472, 30482, 30492, 30502, 30512, 30522, 30532, 30541, 30551, 30560,
1518 30570, 30579, 30588, 30597, 30606, 30615, 30624, 30632, 30641, 30649, 30658, 30666, 30674, 30683, 30691, 30699,
1519 30707, 30715, 30722, 30730, 30738, 30746, 30753, 30761, 30768, 30775, 30783, 30790, 30797, 30804, 30811, 30818],
1520 [30825, 30839, 30853, 30866, 30879, 30892, 30905, 30918, 30930, 30943, 30955, 30967, 30978, 30990, 31001, 31013,
1521 31024, 31035, 31046, 31057, 31067, 31078, 31088, 31099, 31109, 31119, 31129, 31139, 31148, 31158, 31167, 31177,
1522 31186, 31195, 31204, 31213, 31222, 31231, 31240, 31249, 31257, 31266, 31274, 31283, 31291, 31299, 31307, 31315,
1523 31323, 31331, 31339, 31347, 31354, 31362, 31370, 31377, 31385, 31392, 31399, 31407, 31414, 31421, 31428, 31435],
1524 [31442, 31456, 31469, 31483, 31496, 31509, 31522, 31534, 31547, 31559, 31571, 31583, 31595, 31606, 31618, 31629,
1525 31640, 31652, 31662, 31673, 31684, 31694, 31705, 31715, 31725, 31735, 31745, 31755, 31765, 31774, 31784, 31793,
1526 31803, 31812, 31821, 31830, 31839, 31848, 31857, 31865, 31874, 31882, 31891, 31899, 31907, 31916, 31924, 31932,
1527 31940, 31948, 31955, 31963, 31971, 31979, 31986, 31994, 32001, 32008, 32016, 32023, 32030, 32037, 32044, 32052],
1528 [32058, 32072, 32086, 32099, 32112, 32125, 32138, 32151, 32163, 32176, 32188, 32200, 32211, 32223, 32234, 32246,
1529 32257, 32268, 32279, 32290, 32300, 32311, 32321, 32332, 32342, 32352, 32362, 32372, 32381, 32391, 32400, 32410,
1530 32419, 32428, 32437, 32446, 32455, 32464, 32473, 32482, 32490, 32499, 32507, 32516, 32524, 32532, 32540, 32548,
1531 32556, 32564, 32572, 32580, 32587, 32595, 32603, 32610, 32618, 32625, 32632, 32640, 32647, 32654, 32661, 32668],
1532 [32675, 32689, 32702, 32716, 32729, 32742, 32755, 32767, 32780, 32792, 32804, 32816, 32828, 32839, 32851, 32862,
1533 32873, 32885, 32895, 32906, 32917, 32927, 32938, 32948, 32958, 32968, 32978, 32988, 32998, 33007, 33017, 33026,
1534 33036, 33045, 33054, 33063, 33072, 33081, 33090, 33098, 33107, 33115, 33124, 33132, 33140, 33149, 33157, 33165,
1535 33173, 33181, 33188, 33196, 33204, 33212, 33219, 33227, 33234, 33241, 33249, 33256, 33263, 33270, 33278, 33285],
1536 [33292, 33305, 33319, 33332, 33345, 33358, 33371, 33384, 33396, 33409, 33421, 33433, 33444, 33456, 33467, 33479,
1537 33490, 33501, 33512, 33523, 33533, 33544, 33554, 33565, 33575, 33585, 33595, 33605, 33614, 33624, 33633, 33643,
1538 33652, 33661, 33670, 33680, 33688, 33697, 33706, 33715, 33723, 33732, 33740, 33749, 33757, 33765, 33773, 33781,
1539 33789, 33797, 33805, 33813, 33820, 33828, 33836, 33843, 33851, 33858, 33865, 33873, 33880, 33887, 33894, 33901],
1540 [33908, 33922, 33935, 33949, 33962, 33975, 33988, 34000, 34013, 34025, 34037, 34049, 34061, 34072, 34084, 34095,
1541 34106, 34118, 34128, 34139, 34150, 34160, 34171, 34181, 34191, 34201, 34211, 34221, 34231, 34240, 34250, 34259,
1542 34269, 34278, 34287, 34296, 34305, 34314, 34323, 34331, 34340, 34348, 34357, 34365, 34373, 34382, 34390, 34398,
1543 34406, 34414, 34422, 34429, 34437, 34445, 34452, 34460, 34467, 34475, 34482, 34489, 34496, 34503, 34511, 34518],
1544 [34525, 34538, 34552, 34565, 34578, 34591, 34604, 34617, 34629, 34642, 34654, 34666, 34677, 34689, 34700, 34712,
1545 34723, 34734, 34745, 34756, 34766, 34777, 34787, 34798, 34808, 34818, 34828, 34838, 34847, 34857, 34866, 34876,
1546 34885, 34894, 34904, 34913, 34921, 34930, 34939, 34948, 34956, 34965, 34973, 34982, 34990, 34998, 35006, 35014,
1547 35022, 35030, 35038, 35046, 35053, 35061, 35069, 35076, 35084, 35091, 35098, 35106, 35113, 35120, 35127, 35134],
1548 [35141, 35155, 35168, 35182, 35195, 35208, 35221, 35233, 35246, 35258, 35270, 35282, 35294, 35306, 35317, 35328,
1549 35340, 35351, 35361, 35372, 35383, 35393, 35404, 35414, 35424, 35434, 35444, 35454, 35464, 35473, 35483, 35492,
1550 35502, 35511, 35520, 35529, 35538, 35547, 35556, 35564, 35573, 35581, 35590, 35598, 35606, 35615, 35623, 35631,
1551 35639, 35647, 35655, 35662, 35670, 35678, 35685, 35693, 35700, 35708, 35715, 35722, 35729, 35736, 35744, 35751],
1552 [35758, 35771, 35785, 35798, 35811, 35824, 35837, 35850, 35862, 35875, 35887, 35899, 35910, 35922, 35934, 35945,
1553 35956, 35967, 35978, 35989, 35999, 36010, 36020, 36031, 36041, 36051, 36061, 36071, 36080, 36090, 36099, 36109,
1554 36118, 36127, 36137, 36146, 36154, 36163, 36172, 36181, 36189, 36198, 36206, 36215, 36223, 36231, 36239, 36247,
1555 36255, 36263, 36271, 36279, 36287, 36294, 36302, 36309, 36317, 36324, 36331, 36339, 36346, 36353, 36360, 36367],
1556 [36374, 36388, 36401, 36415, 36428, 36441, 36454, 36466, 36479, 36491, 36503, 36515, 36527, 36539, 36550, 36561,
1557 36573, 36584, 36594, 36605, 36616, 36626, 36637, 36647, 36657, 36667, 36677, 36687, 36697, 36706, 36716, 36725,
1558 36735, 36744, 36753, 36762, 36771, 36780, 36789, 36797, 36806, 36814, 36823, 36831, 36839, 36848, 36856, 36864,
1559 36872, 36880, 36888, 36895, 36903, 36911, 36918, 36926, 36933, 36941, 36948, 36955, 36962, 36969, 36977, 36984],
1560 [36991, 37004, 37018, 37031, 37044, 37057, 37070, 37083, 37095, 37108, 37120, 37132, 37143, 37155, 37167, 37178,
1561 37189, 37200, 37211, 37222, 37232, 37243, 37253, 37264, 37274, 37284, 37294, 37304, 37313, 37323, 37332, 37342,
1562 37351, 37360, 37370, 37379, 37388, 37396, 37405, 37414, 37422, 37431, 37439, 37448, 37456, 37464, 37472, 37480,
1563 37488, 37496, 37504, 37512, 37520, 37527, 37535, 37542, 37550, 37557, 37564, 37572, 37579, 37586, 37593, 37600],
1564 [37607, 37621, 37634, 37648, 37661, 37674, 37687, 37699, 37712, 37724, 37736, 37748, 37760, 37772, 37783, 37794,
1565 37806, 37817, 37828, 37838, 37849, 37859, 37870, 37880, 37890, 37900, 37910, 37920, 37930, 37939, 37949, 37958,
1566 37968, 37977, 37986, 37995, 38004, 38013, 38022, 38030, 38039, 38047, 38056, 38064, 38072, 38081, 38089, 38097,
1567 38105, 38113, 38121, 38128, 38136, 38144, 38151, 38159, 38166, 38174, 38181, 38188, 38195, 38202, 38210, 38217],
1568 [38224, 38237, 38251, 38264, 38278, 38290, 38303, 38316, 38328, 38341, 38353, 38365, 38376, 38388, 38400, 38411,
1569 38422, 38433, 38444, 38455, 38465, 38476, 38486, 38497, 38507, 38517, 38527, 38537, 38546, 38556, 38565, 38575,
1570 38584, 38593, 38603, 38612, 38621, 38629, 38638, 38647, 38655, 38664, 38672, 38681, 38689, 38697, 38705, 38713,
1571 38721, 38729, 38737, 38745, 38753, 38760, 38768, 38775, 38783, 38790, 38797, 38805, 38812, 38819, 38826, 38833],
1572 [38840, 38854, 38867, 38881, 38894, 38907, 38920, 38932, 38945, 38957, 38969, 38981, 38993, 39005, 39016, 39027,
1573 39039, 39050, 39061, 39071, 39082, 39092, 39103, 39113, 39123, 39133, 39143, 39153, 39163, 39172, 39182, 39191,
1574 39201, 39210, 39219, 39228, 39237, 39246, 39255, 39263, 39272, 39280, 39289, 39297, 39305, 39314, 39322, 39330,
1575 39338, 39346, 39354, 39361, 39369, 39377, 39384, 39392, 39399, 39407, 39414, 39421, 39428, 39436, 39443, 39450],
1578 /// Approximate `log10(numerator / denominator) * 2048` using a look-up table.
1580 pub fn negative_log10_times_2048(numerator: u64, denominator: u64) -> u64 {
1581 // Multiply the -1 through to avoid needing to use signed numbers.
1582 (log10_times_2048(denominator) - log10_times_2048(numerator)) as u64
1586 fn log10_times_2048(x: u64) -> u16 {
1587 debug_assert_ne!(x, 0);
1588 let most_significant_bit = HIGHEST_BIT - x.leading_zeros();
1589 let lower_bits = (x >> most_significant_bit.saturating_sub(LOWER_BITS)) & LOWER_BITMASK;
1590 LOG10_TIMES_2048[most_significant_bit as usize][lower_bits as usize]
1598 fn prints_negative_log10_times_2048_lookup_table() {
1599 for msb in 0..BITS {
1600 for i in 0..LOWER_BITS_BOUND {
1601 let x = ((LOWER_BITS_BOUND + i) << (HIGHEST_BIT - LOWER_BITS)) >> (HIGHEST_BIT - msb);
1602 let log10_times_2048 = ((x as f64).log10() * 2048.0).round() as u16;
1603 assert_eq!(log10_times_2048, LOG10_TIMES_2048[msb as usize][i as usize]);
1605 if i % LOWER_BITS_BOUND == 0 {
1606 print!("\t\t[{}, ", log10_times_2048);
1607 } else if i % LOWER_BITS_BOUND == LOWER_BITS_BOUND - 1 {
1608 println!("{}],", log10_times_2048);
1609 } else if i % (LOWER_BITS_BOUND/4) == LOWER_BITS_BOUND/4 - 1 {
1610 print!("{},\n\t\t\t", log10_times_2048);
1612 print!("{}, ", log10_times_2048);
1620 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Writeable for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1622 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
1623 write_tlv_fields!(w, {
1624 (0, self.channel_liquidities, required),
1630 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time>
1631 ReadableArgs<(ProbabilisticScoringParameters, G, L)> for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1634 r: &mut R, args: (ProbabilisticScoringParameters, G, L)
1635 ) -> Result<Self, DecodeError> {
1636 let (params, network_graph, logger) = args;
1637 let mut channel_liquidities = HashMap::new();
1638 read_tlv_fields!(r, {
1639 (0, channel_liquidities, required),
1645 channel_liquidities,
1650 impl<T: Time> Writeable for ChannelLiquidity<T> {
1652 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
1653 let duration_since_epoch = T::duration_since_epoch() - self.last_updated.elapsed();
1654 write_tlv_fields!(w, {
1655 (0, self.min_liquidity_offset_msat, required),
1656 (1, Some(self.min_liquidity_offset_history), option),
1657 (2, self.max_liquidity_offset_msat, required),
1658 (3, Some(self.max_liquidity_offset_history), option),
1659 (4, duration_since_epoch, required),
1665 impl<T: Time> Readable for ChannelLiquidity<T> {
1667 fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
1668 let mut min_liquidity_offset_msat = 0;
1669 let mut max_liquidity_offset_msat = 0;
1670 let mut min_liquidity_offset_history = Some(HistoricalBucketRangeTracker::new());
1671 let mut max_liquidity_offset_history = Some(HistoricalBucketRangeTracker::new());
1672 let mut duration_since_epoch = Duration::from_secs(0);
1673 read_tlv_fields!(r, {
1674 (0, min_liquidity_offset_msat, required),
1675 (1, min_liquidity_offset_history, option),
1676 (2, max_liquidity_offset_msat, required),
1677 (3, max_liquidity_offset_history, option),
1678 (4, duration_since_epoch, required),
1680 // On rust prior to 1.60 `Instant::duration_since` will panic if time goes backwards.
1681 // We write `last_updated` as wallclock time even though its ultimately an `Instant` (which
1682 // is a time from a monotonic clock usually represented as an offset against boot time).
1683 // Thus, we have to construct an `Instant` by subtracting the difference in wallclock time
1684 // from the one that was written. However, because `Instant` can panic if we construct one
1685 // in the future, we must handle wallclock time jumping backwards, which we do by simply
1686 // using `Instant::now()` in that case.
1687 let wall_clock_now = T::duration_since_epoch();
1689 let last_updated = if wall_clock_now > duration_since_epoch {
1690 now - (wall_clock_now - duration_since_epoch)
1693 min_liquidity_offset_msat,
1694 max_liquidity_offset_msat,
1695 min_liquidity_offset_history: min_liquidity_offset_history.unwrap(),
1696 max_liquidity_offset_history: max_liquidity_offset_history.unwrap(),
1704 use super::{ChannelLiquidity, HistoricalBucketRangeTracker, ProbabilisticScoringParameters, ProbabilisticScorerUsingTime};
1705 use crate::util::config::UserConfig;
1706 use crate::util::time::Time;
1707 use crate::util::time::tests::SinceEpoch;
1709 use crate::ln::channelmanager;
1710 use crate::ln::msgs::{ChannelAnnouncement, ChannelUpdate, UnsignedChannelAnnouncement, UnsignedChannelUpdate};
1711 use crate::routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId};
1712 use crate::routing::router::RouteHop;
1713 use crate::routing::scoring::{ChannelUsage, Score};
1714 use crate::util::ser::{ReadableArgs, Writeable};
1715 use crate::util::test_utils::TestLogger;
1717 use bitcoin::blockdata::constants::genesis_block;
1718 use bitcoin::hashes::Hash;
1719 use bitcoin::hashes::sha256d::Hash as Sha256dHash;
1720 use bitcoin::network::constants::Network;
1721 use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey};
1722 use core::time::Duration;
1725 fn source_privkey() -> SecretKey {
1726 SecretKey::from_slice(&[42; 32]).unwrap()
1729 fn target_privkey() -> SecretKey {
1730 SecretKey::from_slice(&[43; 32]).unwrap()
1733 fn source_pubkey() -> PublicKey {
1734 let secp_ctx = Secp256k1::new();
1735 PublicKey::from_secret_key(&secp_ctx, &source_privkey())
1738 fn target_pubkey() -> PublicKey {
1739 let secp_ctx = Secp256k1::new();
1740 PublicKey::from_secret_key(&secp_ctx, &target_privkey())
1743 fn source_node_id() -> NodeId {
1744 NodeId::from_pubkey(&source_pubkey())
1747 fn target_node_id() -> NodeId {
1748 NodeId::from_pubkey(&target_pubkey())
1751 // `ProbabilisticScorer` tests
1753 /// A probabilistic scorer for testing with time that can be manually advanced.
1754 type ProbabilisticScorer<'a> = ProbabilisticScorerUsingTime::<&'a NetworkGraph<&'a TestLogger>, &'a TestLogger, SinceEpoch>;
1756 fn sender_privkey() -> SecretKey {
1757 SecretKey::from_slice(&[41; 32]).unwrap()
1760 fn recipient_privkey() -> SecretKey {
1761 SecretKey::from_slice(&[45; 32]).unwrap()
1764 fn sender_pubkey() -> PublicKey {
1765 let secp_ctx = Secp256k1::new();
1766 PublicKey::from_secret_key(&secp_ctx, &sender_privkey())
1769 fn recipient_pubkey() -> PublicKey {
1770 let secp_ctx = Secp256k1::new();
1771 PublicKey::from_secret_key(&secp_ctx, &recipient_privkey())
1774 fn sender_node_id() -> NodeId {
1775 NodeId::from_pubkey(&sender_pubkey())
1778 fn recipient_node_id() -> NodeId {
1779 NodeId::from_pubkey(&recipient_pubkey())
1782 fn network_graph(logger: &TestLogger) -> NetworkGraph<&TestLogger> {
1783 let mut network_graph = NetworkGraph::new(Network::Testnet, logger);
1784 add_channel(&mut network_graph, 42, source_privkey(), target_privkey());
1785 add_channel(&mut network_graph, 43, target_privkey(), recipient_privkey());
1791 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_1_key: SecretKey,
1792 node_2_key: SecretKey
1794 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1795 let node_1_secret = &SecretKey::from_slice(&[39; 32]).unwrap();
1796 let node_2_secret = &SecretKey::from_slice(&[40; 32]).unwrap();
1797 let secp_ctx = Secp256k1::new();
1798 let unsigned_announcement = UnsignedChannelAnnouncement {
1799 features: channelmanager::provided_channel_features(&UserConfig::default()),
1800 chain_hash: genesis_hash,
1802 node_id_1: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_1_key)),
1803 node_id_2: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_2_key)),
1804 bitcoin_key_1: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_1_secret)),
1805 bitcoin_key_2: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_2_secret)),
1806 excess_data: Vec::new(),
1808 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
1809 let signed_announcement = ChannelAnnouncement {
1810 node_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_key),
1811 node_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_key),
1812 bitcoin_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_secret),
1813 bitcoin_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_secret),
1814 contents: unsigned_announcement,
1816 let chain_source: Option<&crate::util::test_utils::TestChainSource> = None;
1817 network_graph.update_channel_from_announcement(
1818 &signed_announcement, &chain_source).unwrap();
1819 update_channel(network_graph, short_channel_id, node_1_key, 0, 1_000);
1820 update_channel(network_graph, short_channel_id, node_2_key, 1, 0);
1824 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_key: SecretKey,
1825 flags: u8, htlc_maximum_msat: u64
1827 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1828 let secp_ctx = Secp256k1::new();
1829 let unsigned_update = UnsignedChannelUpdate {
1830 chain_hash: genesis_hash,
1834 cltv_expiry_delta: 18,
1835 htlc_minimum_msat: 0,
1838 fee_proportional_millionths: 0,
1839 excess_data: Vec::new(),
1841 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_update.encode()[..])[..]);
1842 let signed_update = ChannelUpdate {
1843 signature: secp_ctx.sign_ecdsa(&msghash, &node_key),
1844 contents: unsigned_update,
1846 network_graph.update_channel(&signed_update).unwrap();
1849 fn path_hop(pubkey: PublicKey, short_channel_id: u64, fee_msat: u64) -> RouteHop {
1850 let config = UserConfig::default();
1853 node_features: channelmanager::provided_node_features(&config),
1855 channel_features: channelmanager::provided_channel_features(&config),
1857 cltv_expiry_delta: 18,
1861 fn payment_path_for_amount(amount_msat: u64) -> Vec<RouteHop> {
1863 path_hop(source_pubkey(), 41, 1),
1864 path_hop(target_pubkey(), 42, 2),
1865 path_hop(recipient_pubkey(), 43, amount_msat),
1870 fn liquidity_bounds_directed_from_lowest_node_id() {
1871 let logger = TestLogger::new();
1872 let last_updated = SinceEpoch::now();
1873 let network_graph = network_graph(&logger);
1874 let params = ProbabilisticScoringParameters::default();
1875 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1878 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated,
1879 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1880 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1884 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated,
1885 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1886 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1888 let source = source_node_id();
1889 let target = target_node_id();
1890 let recipient = recipient_node_id();
1891 assert!(source > target);
1892 assert!(target < recipient);
1894 // Update minimum liquidity.
1896 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1897 .as_directed(&source, &target, 0, 1_000, &scorer.params);
1898 assert_eq!(liquidity.min_liquidity_msat(), 100);
1899 assert_eq!(liquidity.max_liquidity_msat(), 300);
1901 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1902 .as_directed(&target, &source, 0, 1_000, &scorer.params);
1903 assert_eq!(liquidity.min_liquidity_msat(), 700);
1904 assert_eq!(liquidity.max_liquidity_msat(), 900);
1906 scorer.channel_liquidities.get_mut(&42).unwrap()
1907 .as_directed_mut(&source, &target, 0, 1_000, &scorer.params)
1908 .set_min_liquidity_msat(200);
1910 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1911 .as_directed(&source, &target, 0, 1_000, &scorer.params);
1912 assert_eq!(liquidity.min_liquidity_msat(), 200);
1913 assert_eq!(liquidity.max_liquidity_msat(), 300);
1915 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1916 .as_directed(&target, &source, 0, 1_000, &scorer.params);
1917 assert_eq!(liquidity.min_liquidity_msat(), 700);
1918 assert_eq!(liquidity.max_liquidity_msat(), 800);
1920 // Update maximum liquidity.
1922 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1923 .as_directed(&target, &recipient, 0, 1_000, &scorer.params);
1924 assert_eq!(liquidity.min_liquidity_msat(), 700);
1925 assert_eq!(liquidity.max_liquidity_msat(), 900);
1927 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1928 .as_directed(&recipient, &target, 0, 1_000, &scorer.params);
1929 assert_eq!(liquidity.min_liquidity_msat(), 100);
1930 assert_eq!(liquidity.max_liquidity_msat(), 300);
1932 scorer.channel_liquidities.get_mut(&43).unwrap()
1933 .as_directed_mut(&target, &recipient, 0, 1_000, &scorer.params)
1934 .set_max_liquidity_msat(200);
1936 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1937 .as_directed(&target, &recipient, 0, 1_000, &scorer.params);
1938 assert_eq!(liquidity.min_liquidity_msat(), 0);
1939 assert_eq!(liquidity.max_liquidity_msat(), 200);
1941 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1942 .as_directed(&recipient, &target, 0, 1_000, &scorer.params);
1943 assert_eq!(liquidity.min_liquidity_msat(), 800);
1944 assert_eq!(liquidity.max_liquidity_msat(), 1000);
1948 fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() {
1949 let logger = TestLogger::new();
1950 let last_updated = SinceEpoch::now();
1951 let network_graph = network_graph(&logger);
1952 let params = ProbabilisticScoringParameters::default();
1953 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1956 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated,
1957 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1958 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1960 let source = source_node_id();
1961 let target = target_node_id();
1962 assert!(source > target);
1964 // Check initial bounds.
1965 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1966 .as_directed(&source, &target, 0, 1_000, &scorer.params);
1967 assert_eq!(liquidity.min_liquidity_msat(), 400);
1968 assert_eq!(liquidity.max_liquidity_msat(), 800);
1970 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1971 .as_directed(&target, &source, 0, 1_000, &scorer.params);
1972 assert_eq!(liquidity.min_liquidity_msat(), 200);
1973 assert_eq!(liquidity.max_liquidity_msat(), 600);
1975 // Reset from source to target.
1976 scorer.channel_liquidities.get_mut(&42).unwrap()
1977 .as_directed_mut(&source, &target, 0, 1_000, &scorer.params)
1978 .set_min_liquidity_msat(900);
1980 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1981 .as_directed(&source, &target, 0, 1_000, &scorer.params);
1982 assert_eq!(liquidity.min_liquidity_msat(), 900);
1983 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1985 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1986 .as_directed(&target, &source, 0, 1_000, &scorer.params);
1987 assert_eq!(liquidity.min_liquidity_msat(), 0);
1988 assert_eq!(liquidity.max_liquidity_msat(), 100);
1990 // Reset from target to source.
1991 scorer.channel_liquidities.get_mut(&42).unwrap()
1992 .as_directed_mut(&target, &source, 0, 1_000, &scorer.params)
1993 .set_min_liquidity_msat(400);
1995 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1996 .as_directed(&source, &target, 0, 1_000, &scorer.params);
1997 assert_eq!(liquidity.min_liquidity_msat(), 0);
1998 assert_eq!(liquidity.max_liquidity_msat(), 600);
2000 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2001 .as_directed(&target, &source, 0, 1_000, &scorer.params);
2002 assert_eq!(liquidity.min_liquidity_msat(), 400);
2003 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2007 fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() {
2008 let logger = TestLogger::new();
2009 let last_updated = SinceEpoch::now();
2010 let network_graph = network_graph(&logger);
2011 let params = ProbabilisticScoringParameters::default();
2012 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
2015 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated,
2016 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2017 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2019 let source = source_node_id();
2020 let target = target_node_id();
2021 assert!(source > target);
2023 // Check initial bounds.
2024 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2025 .as_directed(&source, &target, 0, 1_000, &scorer.params);
2026 assert_eq!(liquidity.min_liquidity_msat(), 400);
2027 assert_eq!(liquidity.max_liquidity_msat(), 800);
2029 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2030 .as_directed(&target, &source, 0, 1_000, &scorer.params);
2031 assert_eq!(liquidity.min_liquidity_msat(), 200);
2032 assert_eq!(liquidity.max_liquidity_msat(), 600);
2034 // Reset from source to target.
2035 scorer.channel_liquidities.get_mut(&42).unwrap()
2036 .as_directed_mut(&source, &target, 0, 1_000, &scorer.params)
2037 .set_max_liquidity_msat(300);
2039 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2040 .as_directed(&source, &target, 0, 1_000, &scorer.params);
2041 assert_eq!(liquidity.min_liquidity_msat(), 0);
2042 assert_eq!(liquidity.max_liquidity_msat(), 300);
2044 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2045 .as_directed(&target, &source, 0, 1_000, &scorer.params);
2046 assert_eq!(liquidity.min_liquidity_msat(), 700);
2047 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2049 // Reset from target to source.
2050 scorer.channel_liquidities.get_mut(&42).unwrap()
2051 .as_directed_mut(&target, &source, 0, 1_000, &scorer.params)
2052 .set_max_liquidity_msat(600);
2054 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2055 .as_directed(&source, &target, 0, 1_000, &scorer.params);
2056 assert_eq!(liquidity.min_liquidity_msat(), 400);
2057 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2059 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2060 .as_directed(&target, &source, 0, 1_000, &scorer.params);
2061 assert_eq!(liquidity.min_liquidity_msat(), 0);
2062 assert_eq!(liquidity.max_liquidity_msat(), 600);
2066 fn increased_penalty_nearing_liquidity_upper_bound() {
2067 let logger = TestLogger::new();
2068 let network_graph = network_graph(&logger);
2069 let params = ProbabilisticScoringParameters {
2070 liquidity_penalty_multiplier_msat: 1_000,
2071 ..ProbabilisticScoringParameters::zero_penalty()
2073 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2074 let source = source_node_id();
2075 let target = target_node_id();
2077 let usage = ChannelUsage {
2079 inflight_htlc_msat: 0,
2080 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
2082 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2083 let usage = ChannelUsage { amount_msat: 10_240, ..usage };
2084 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2085 let usage = ChannelUsage { amount_msat: 102_400, ..usage };
2086 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 47);
2087 let usage = ChannelUsage { amount_msat: 1_023_999, ..usage };
2088 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
2090 let usage = ChannelUsage {
2092 inflight_htlc_msat: 0,
2093 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2095 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 58);
2096 let usage = ChannelUsage { amount_msat: 256, ..usage };
2097 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
2098 let usage = ChannelUsage { amount_msat: 374, ..usage };
2099 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 198);
2100 let usage = ChannelUsage { amount_msat: 512, ..usage };
2101 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2102 let usage = ChannelUsage { amount_msat: 640, ..usage };
2103 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 425);
2104 let usage = ChannelUsage { amount_msat: 768, ..usage };
2105 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 602);
2106 let usage = ChannelUsage { amount_msat: 896, ..usage };
2107 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 902);
2111 fn constant_penalty_outside_liquidity_bounds() {
2112 let logger = TestLogger::new();
2113 let last_updated = SinceEpoch::now();
2114 let network_graph = network_graph(&logger);
2115 let params = ProbabilisticScoringParameters {
2116 liquidity_penalty_multiplier_msat: 1_000,
2117 considered_impossible_penalty_msat: u64::max_value(),
2118 ..ProbabilisticScoringParameters::zero_penalty()
2120 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
2123 min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40, last_updated,
2124 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2125 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
2127 let source = source_node_id();
2128 let target = target_node_id();
2130 let usage = ChannelUsage {
2132 inflight_htlc_msat: 0,
2133 effective_capacity: EffectiveCapacity::Total { capacity_msat: 100, htlc_maximum_msat: 1_000 },
2135 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2136 let usage = ChannelUsage { amount_msat: 50, ..usage };
2137 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2138 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2139 let usage = ChannelUsage { amount_msat: 61, ..usage };
2140 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2144 fn does_not_further_penalize_own_channel() {
2145 let logger = TestLogger::new();
2146 let network_graph = network_graph(&logger);
2147 let params = ProbabilisticScoringParameters {
2148 liquidity_penalty_multiplier_msat: 1_000,
2149 ..ProbabilisticScoringParameters::zero_penalty()
2151 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2152 let sender = sender_node_id();
2153 let source = source_node_id();
2154 let usage = ChannelUsage {
2156 inflight_htlc_msat: 0,
2157 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2159 let failed_path = payment_path_for_amount(500);
2160 let successful_path = payment_path_for_amount(200);
2162 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 301);
2164 scorer.payment_path_failed(&failed_path.iter().collect::<Vec<_>>(), 41);
2165 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 301);
2167 scorer.payment_path_successful(&successful_path.iter().collect::<Vec<_>>());
2168 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 301);
2172 fn sets_liquidity_lower_bound_on_downstream_failure() {
2173 let logger = TestLogger::new();
2174 let network_graph = network_graph(&logger);
2175 let params = ProbabilisticScoringParameters {
2176 liquidity_penalty_multiplier_msat: 1_000,
2177 ..ProbabilisticScoringParameters::zero_penalty()
2179 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2180 let source = source_node_id();
2181 let target = target_node_id();
2182 let path = payment_path_for_amount(500);
2184 let usage = ChannelUsage {
2186 inflight_htlc_msat: 0,
2187 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2189 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 128);
2190 let usage = ChannelUsage { amount_msat: 500, ..usage };
2191 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 301);
2192 let usage = ChannelUsage { amount_msat: 750, ..usage };
2193 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 602);
2195 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 43);
2197 let usage = ChannelUsage { amount_msat: 250, ..usage };
2198 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2199 let usage = ChannelUsage { amount_msat: 500, ..usage };
2200 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2201 let usage = ChannelUsage { amount_msat: 750, ..usage };
2202 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2206 fn sets_liquidity_upper_bound_on_failure() {
2207 let logger = TestLogger::new();
2208 let network_graph = network_graph(&logger);
2209 let params = ProbabilisticScoringParameters {
2210 liquidity_penalty_multiplier_msat: 1_000,
2211 considered_impossible_penalty_msat: u64::max_value(),
2212 ..ProbabilisticScoringParameters::zero_penalty()
2214 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2215 let source = source_node_id();
2216 let target = target_node_id();
2217 let path = payment_path_for_amount(500);
2219 let usage = ChannelUsage {
2221 inflight_htlc_msat: 0,
2222 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2224 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 128);
2225 let usage = ChannelUsage { amount_msat: 500, ..usage };
2226 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 301);
2227 let usage = ChannelUsage { amount_msat: 750, ..usage };
2228 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 602);
2230 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 42);
2232 let usage = ChannelUsage { amount_msat: 250, ..usage };
2233 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2234 let usage = ChannelUsage { amount_msat: 500, ..usage };
2235 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2236 let usage = ChannelUsage { amount_msat: 750, ..usage };
2237 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2241 fn ignores_channels_after_removed_failed_channel() {
2242 // Previously, if we'd tried to send over a channel which was removed from the network
2243 // graph before we call `payment_path_failed` (which is the default if the we get a "no
2244 // such channel" error in the `InvoicePayer`), we would call `failed_downstream` on all
2245 // channels in the route, even ones which they payment never reached. This tests to ensure
2246 // we do not score such channels.
2247 let secp_ctx = Secp256k1::new();
2248 let logger = TestLogger::new();
2249 let mut network_graph = NetworkGraph::new(Network::Testnet, &logger);
2250 let secret_a = SecretKey::from_slice(&[42; 32]).unwrap();
2251 let secret_b = SecretKey::from_slice(&[43; 32]).unwrap();
2252 let secret_c = SecretKey::from_slice(&[44; 32]).unwrap();
2253 let secret_d = SecretKey::from_slice(&[45; 32]).unwrap();
2254 add_channel(&mut network_graph, 42, secret_a, secret_b);
2255 // Don't add the channel from B -> C.
2256 add_channel(&mut network_graph, 44, secret_c, secret_d);
2258 let pub_a = PublicKey::from_secret_key(&secp_ctx, &secret_a);
2259 let pub_b = PublicKey::from_secret_key(&secp_ctx, &secret_b);
2260 let pub_c = PublicKey::from_secret_key(&secp_ctx, &secret_c);
2261 let pub_d = PublicKey::from_secret_key(&secp_ctx, &secret_d);
2264 path_hop(pub_b, 42, 1),
2265 path_hop(pub_c, 43, 2),
2266 path_hop(pub_d, 44, 100),
2269 let node_a = NodeId::from_pubkey(&pub_a);
2270 let node_b = NodeId::from_pubkey(&pub_b);
2271 let node_c = NodeId::from_pubkey(&pub_c);
2272 let node_d = NodeId::from_pubkey(&pub_d);
2274 let params = ProbabilisticScoringParameters {
2275 liquidity_penalty_multiplier_msat: 1_000,
2276 ..ProbabilisticScoringParameters::zero_penalty()
2278 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2280 let usage = ChannelUsage {
2282 inflight_htlc_msat: 0,
2283 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2285 assert_eq!(scorer.channel_penalty_msat(42, &node_a, &node_b, usage), 128);
2286 // Note that a default liquidity bound is used for B -> C as no channel exists
2287 assert_eq!(scorer.channel_penalty_msat(43, &node_b, &node_c, usage), 128);
2288 assert_eq!(scorer.channel_penalty_msat(44, &node_c, &node_d, usage), 128);
2290 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 43);
2292 assert_eq!(scorer.channel_penalty_msat(42, &node_a, &node_b, usage), 80);
2293 // Note that a default liquidity bound is used for B -> C as no channel exists
2294 assert_eq!(scorer.channel_penalty_msat(43, &node_b, &node_c, usage), 128);
2295 assert_eq!(scorer.channel_penalty_msat(44, &node_c, &node_d, usage), 128);
2299 fn reduces_liquidity_upper_bound_along_path_on_success() {
2300 let logger = TestLogger::new();
2301 let network_graph = network_graph(&logger);
2302 let params = ProbabilisticScoringParameters {
2303 liquidity_penalty_multiplier_msat: 1_000,
2304 ..ProbabilisticScoringParameters::zero_penalty()
2306 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2307 let sender = sender_node_id();
2308 let source = source_node_id();
2309 let target = target_node_id();
2310 let recipient = recipient_node_id();
2311 let usage = ChannelUsage {
2313 inflight_htlc_msat: 0,
2314 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2316 let path = payment_path_for_amount(500);
2318 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 128);
2319 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 128);
2320 assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage), 128);
2322 scorer.payment_path_successful(&path.iter().collect::<Vec<_>>());
2324 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 128);
2325 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2326 assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage), 300);
2330 fn decays_liquidity_bounds_over_time() {
2331 let logger = TestLogger::new();
2332 let network_graph = network_graph(&logger);
2333 let params = ProbabilisticScoringParameters {
2334 liquidity_penalty_multiplier_msat: 1_000,
2335 liquidity_offset_half_life: Duration::from_secs(10),
2336 considered_impossible_penalty_msat: u64::max_value(),
2337 ..ProbabilisticScoringParameters::zero_penalty()
2339 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2340 let source = source_node_id();
2341 let target = target_node_id();
2343 let usage = ChannelUsage {
2345 inflight_htlc_msat: 0,
2346 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
2348 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2349 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
2350 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
2352 scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::<Vec<_>>(), 42);
2353 scorer.payment_path_failed(&payment_path_for_amount(128).iter().collect::<Vec<_>>(), 43);
2355 let usage = ChannelUsage { amount_msat: 128, ..usage };
2356 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2357 let usage = ChannelUsage { amount_msat: 256, ..usage };
2358 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 93);
2359 let usage = ChannelUsage { amount_msat: 768, ..usage };
2360 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1_479);
2361 let usage = ChannelUsage { amount_msat: 896, ..usage };
2362 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2364 SinceEpoch::advance(Duration::from_secs(9));
2365 let usage = ChannelUsage { amount_msat: 128, ..usage };
2366 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2367 let usage = ChannelUsage { amount_msat: 256, ..usage };
2368 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 93);
2369 let usage = ChannelUsage { amount_msat: 768, ..usage };
2370 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1_479);
2371 let usage = ChannelUsage { amount_msat: 896, ..usage };
2372 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2374 SinceEpoch::advance(Duration::from_secs(1));
2375 let usage = ChannelUsage { amount_msat: 64, ..usage };
2376 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2377 let usage = ChannelUsage { amount_msat: 128, ..usage };
2378 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 34);
2379 let usage = ChannelUsage { amount_msat: 896, ..usage };
2380 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1_970);
2381 let usage = ChannelUsage { amount_msat: 960, ..usage };
2382 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2384 // Fully decay liquidity lower bound.
2385 SinceEpoch::advance(Duration::from_secs(10 * 7));
2386 let usage = ChannelUsage { amount_msat: 0, ..usage };
2387 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2388 let usage = ChannelUsage { amount_msat: 1, ..usage };
2389 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2390 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
2391 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
2392 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2393 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2395 // Fully decay liquidity upper bound.
2396 SinceEpoch::advance(Duration::from_secs(10));
2397 let usage = ChannelUsage { amount_msat: 0, ..usage };
2398 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2399 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2400 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2402 SinceEpoch::advance(Duration::from_secs(10));
2403 let usage = ChannelUsage { amount_msat: 0, ..usage };
2404 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2405 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2406 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2410 fn decays_liquidity_bounds_without_shift_overflow() {
2411 let logger = TestLogger::new();
2412 let network_graph = network_graph(&logger);
2413 let params = ProbabilisticScoringParameters {
2414 liquidity_penalty_multiplier_msat: 1_000,
2415 liquidity_offset_half_life: Duration::from_secs(10),
2416 ..ProbabilisticScoringParameters::zero_penalty()
2418 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2419 let source = source_node_id();
2420 let target = target_node_id();
2421 let usage = ChannelUsage {
2423 inflight_htlc_msat: 0,
2424 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2426 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
2428 scorer.payment_path_failed(&payment_path_for_amount(512).iter().collect::<Vec<_>>(), 42);
2429 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 281);
2431 // An unchecked right shift 64 bits or more in DirectedChannelLiquidity::decayed_offset_msat
2432 // would cause an overflow.
2433 SinceEpoch::advance(Duration::from_secs(10 * 64));
2434 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
2436 SinceEpoch::advance(Duration::from_secs(10));
2437 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
2441 fn restricts_liquidity_bounds_after_decay() {
2442 let logger = TestLogger::new();
2443 let network_graph = network_graph(&logger);
2444 let params = ProbabilisticScoringParameters {
2445 liquidity_penalty_multiplier_msat: 1_000,
2446 liquidity_offset_half_life: Duration::from_secs(10),
2447 ..ProbabilisticScoringParameters::zero_penalty()
2449 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2450 let source = source_node_id();
2451 let target = target_node_id();
2452 let usage = ChannelUsage {
2454 inflight_htlc_msat: 0,
2455 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2458 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2460 // More knowledge gives higher confidence (256, 768), meaning a lower penalty.
2461 scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::<Vec<_>>(), 42);
2462 scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::<Vec<_>>(), 43);
2463 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 281);
2465 // Decaying knowledge gives less confidence (128, 896), meaning a higher penalty.
2466 SinceEpoch::advance(Duration::from_secs(10));
2467 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 291);
2469 // Reducing the upper bound gives more confidence (128, 832) that the payment amount (512)
2470 // is closer to the upper bound, meaning a higher penalty.
2471 scorer.payment_path_successful(&payment_path_for_amount(64).iter().collect::<Vec<_>>());
2472 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 331);
2474 // Increasing the lower bound gives more confidence (256, 832) that the payment amount (512)
2475 // is closer to the lower bound, meaning a lower penalty.
2476 scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::<Vec<_>>(), 43);
2477 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 245);
2479 // Further decaying affects the lower bound more than the upper bound (128, 928).
2480 SinceEpoch::advance(Duration::from_secs(10));
2481 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 280);
2485 fn restores_persisted_liquidity_bounds() {
2486 let logger = TestLogger::new();
2487 let network_graph = network_graph(&logger);
2488 let params = ProbabilisticScoringParameters {
2489 liquidity_penalty_multiplier_msat: 1_000,
2490 liquidity_offset_half_life: Duration::from_secs(10),
2491 considered_impossible_penalty_msat: u64::max_value(),
2492 ..ProbabilisticScoringParameters::zero_penalty()
2494 let mut scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger);
2495 let source = source_node_id();
2496 let target = target_node_id();
2497 let usage = ChannelUsage {
2499 inflight_htlc_msat: 0,
2500 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2503 scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
2504 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2506 SinceEpoch::advance(Duration::from_secs(10));
2507 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 473);
2509 scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::<Vec<_>>(), 43);
2510 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2512 let mut serialized_scorer = Vec::new();
2513 scorer.write(&mut serialized_scorer).unwrap();
2515 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
2516 let deserialized_scorer =
2517 <ProbabilisticScorer>::read(&mut serialized_scorer, (params, &network_graph, &logger)).unwrap();
2518 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2522 fn decays_persisted_liquidity_bounds() {
2523 let logger = TestLogger::new();
2524 let network_graph = network_graph(&logger);
2525 let params = ProbabilisticScoringParameters {
2526 liquidity_penalty_multiplier_msat: 1_000,
2527 liquidity_offset_half_life: Duration::from_secs(10),
2528 considered_impossible_penalty_msat: u64::max_value(),
2529 ..ProbabilisticScoringParameters::zero_penalty()
2531 let mut scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger);
2532 let source = source_node_id();
2533 let target = target_node_id();
2534 let usage = ChannelUsage {
2536 inflight_htlc_msat: 0,
2537 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2540 scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
2541 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2543 let mut serialized_scorer = Vec::new();
2544 scorer.write(&mut serialized_scorer).unwrap();
2546 SinceEpoch::advance(Duration::from_secs(10));
2548 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
2549 let deserialized_scorer =
2550 <ProbabilisticScorer>::read(&mut serialized_scorer, (params, &network_graph, &logger)).unwrap();
2551 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage), 473);
2553 scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::<Vec<_>>(), 43);
2554 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2556 SinceEpoch::advance(Duration::from_secs(10));
2557 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage), 365);
2561 fn scores_realistic_payments() {
2562 // Shows the scores of "realistic" sends of 100k sats over channels of 1-10m sats (with a
2563 // 50k sat reserve).
2564 let logger = TestLogger::new();
2565 let network_graph = network_graph(&logger);
2566 let params = ProbabilisticScoringParameters::default();
2567 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2568 let source = source_node_id();
2569 let target = target_node_id();
2571 let usage = ChannelUsage {
2572 amount_msat: 100_000_000,
2573 inflight_htlc_msat: 0,
2574 effective_capacity: EffectiveCapacity::Total { capacity_msat: 950_000_000, htlc_maximum_msat: 1_000 },
2576 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 4375);
2577 let usage = ChannelUsage {
2578 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2580 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2739);
2581 let usage = ChannelUsage {
2582 effective_capacity: EffectiveCapacity::Total { capacity_msat: 2_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2584 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2236);
2585 let usage = ChannelUsage {
2586 effective_capacity: EffectiveCapacity::Total { capacity_msat: 3_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2588 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1983);
2589 let usage = ChannelUsage {
2590 effective_capacity: EffectiveCapacity::Total { capacity_msat: 4_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2592 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1637);
2593 let usage = ChannelUsage {
2594 effective_capacity: EffectiveCapacity::Total { capacity_msat: 5_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2596 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1606);
2597 let usage = ChannelUsage {
2598 effective_capacity: EffectiveCapacity::Total { capacity_msat: 6_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2600 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1331);
2601 let usage = ChannelUsage {
2602 effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_450_000_000, htlc_maximum_msat: 1_000 }, ..usage
2604 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1387);
2605 let usage = ChannelUsage {
2606 effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2608 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1379);
2609 let usage = ChannelUsage {
2610 effective_capacity: EffectiveCapacity::Total { capacity_msat: 8_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2612 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1363);
2613 let usage = ChannelUsage {
2614 effective_capacity: EffectiveCapacity::Total { capacity_msat: 9_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
2616 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1355);
2620 fn adds_base_penalty_to_liquidity_penalty() {
2621 let logger = TestLogger::new();
2622 let network_graph = network_graph(&logger);
2623 let source = source_node_id();
2624 let target = target_node_id();
2625 let usage = ChannelUsage {
2627 inflight_htlc_msat: 0,
2628 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2631 let params = ProbabilisticScoringParameters {
2632 liquidity_penalty_multiplier_msat: 1_000,
2633 ..ProbabilisticScoringParameters::zero_penalty()
2635 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2636 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 58);
2638 let params = ProbabilisticScoringParameters {
2639 base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000,
2640 anti_probing_penalty_msat: 0, ..ProbabilisticScoringParameters::zero_penalty()
2642 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2643 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 558);
2645 let params = ProbabilisticScoringParameters {
2646 base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000,
2647 base_penalty_amount_multiplier_msat: (1 << 30),
2648 anti_probing_penalty_msat: 0, ..ProbabilisticScoringParameters::zero_penalty()
2651 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2652 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 558 + 128);
2656 fn adds_amount_penalty_to_liquidity_penalty() {
2657 let logger = TestLogger::new();
2658 let network_graph = network_graph(&logger);
2659 let source = source_node_id();
2660 let target = target_node_id();
2661 let usage = ChannelUsage {
2662 amount_msat: 512_000,
2663 inflight_htlc_msat: 0,
2664 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
2667 let params = ProbabilisticScoringParameters {
2668 liquidity_penalty_multiplier_msat: 1_000,
2669 liquidity_penalty_amount_multiplier_msat: 0,
2670 ..ProbabilisticScoringParameters::zero_penalty()
2672 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2673 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2675 let params = ProbabilisticScoringParameters {
2676 liquidity_penalty_multiplier_msat: 1_000,
2677 liquidity_penalty_amount_multiplier_msat: 256,
2678 ..ProbabilisticScoringParameters::zero_penalty()
2680 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2681 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 337);
2685 fn calculates_log10_without_overflowing_u64_max_value() {
2686 let logger = TestLogger::new();
2687 let network_graph = network_graph(&logger);
2688 let source = source_node_id();
2689 let target = target_node_id();
2690 let usage = ChannelUsage {
2691 amount_msat: u64::max_value(),
2692 inflight_htlc_msat: 0,
2693 effective_capacity: EffectiveCapacity::Infinite,
2696 let params = ProbabilisticScoringParameters {
2697 liquidity_penalty_multiplier_msat: 40_000,
2698 ..ProbabilisticScoringParameters::zero_penalty()
2700 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2701 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 80_000);
2705 fn accounts_for_inflight_htlc_usage() {
2706 let logger = TestLogger::new();
2707 let network_graph = network_graph(&logger);
2708 let params = ProbabilisticScoringParameters {
2709 considered_impossible_penalty_msat: u64::max_value(),
2710 ..ProbabilisticScoringParameters::zero_penalty()
2712 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2713 let source = source_node_id();
2714 let target = target_node_id();
2716 let usage = ChannelUsage {
2718 inflight_htlc_msat: 0,
2719 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2721 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2723 let usage = ChannelUsage { inflight_htlc_msat: 251, ..usage };
2724 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2728 fn removes_uncertainity_when_exact_liquidity_known() {
2729 let logger = TestLogger::new();
2730 let network_graph = network_graph(&logger);
2731 let params = ProbabilisticScoringParameters::default();
2732 let scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger);
2733 let source = source_node_id();
2734 let target = target_node_id();
2736 let base_penalty_msat = params.base_penalty_msat;
2737 let usage = ChannelUsage {
2739 inflight_htlc_msat: 0,
2740 effective_capacity: EffectiveCapacity::ExactLiquidity { liquidity_msat: 1_000 },
2742 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), base_penalty_msat);
2744 let usage = ChannelUsage { amount_msat: 1_000, ..usage };
2745 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), base_penalty_msat);
2747 let usage = ChannelUsage { amount_msat: 1_001, ..usage };
2748 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2752 fn remembers_historical_failures() {
2753 let logger = TestLogger::new();
2754 let network_graph = network_graph(&logger);
2755 let params = ProbabilisticScoringParameters {
2756 liquidity_offset_half_life: Duration::from_secs(60 * 60),
2757 historical_liquidity_penalty_multiplier_msat: 1024,
2758 historical_liquidity_penalty_amount_multiplier_msat: 1024,
2759 historical_no_updates_half_life: Duration::from_secs(10),
2760 ..ProbabilisticScoringParameters::zero_penalty()
2762 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2763 let source = source_node_id();
2764 let target = target_node_id();
2766 let usage = ChannelUsage {
2768 inflight_htlc_msat: 0,
2769 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
2771 // With no historical data the normal liquidity penalty calculation is used.
2772 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 47);
2773 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
2776 scorer.payment_path_failed(&payment_path_for_amount(1).iter().collect::<Vec<_>>(), 42);
2777 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2048);
2778 // The "it failed" increment is 32, where the probability should lie fully in the first
2780 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
2781 Some(([32, 0, 0, 0, 0, 0, 0, 0], [32, 0, 0, 0, 0, 0, 0, 0])));
2783 // Even after we tell the scorer we definitely have enough available liquidity, it will
2784 // still remember that there was some failure in the past, and assign a non-0 penalty.
2785 scorer.payment_path_failed(&payment_path_for_amount(1000).iter().collect::<Vec<_>>(), 43);
2786 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 198);
2787 // The first octile should be decayed just slightly and the last octile has a new point.
2788 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
2789 Some(([31, 0, 0, 0, 0, 0, 0, 32], [31, 0, 0, 0, 0, 0, 0, 32])));
2791 // Advance the time forward 16 half-lives (which the docs claim will ensure all data is
2792 // gone), and check that we're back to where we started.
2793 SinceEpoch::advance(Duration::from_secs(10 * 16));
2794 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 47);
2795 // Once fully decayed we still have data, but its all-0s. In the future we may remove the
2796 // data entirely instead.
2797 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
2798 Some(([0; 8], [0; 8])));
2800 let usage = ChannelUsage {
2802 inflight_htlc_msat: 1024,
2803 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
2805 scorer.payment_path_failed(&payment_path_for_amount(1).iter().collect::<Vec<_>>(), 42);
2806 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 409);
2808 let usage = ChannelUsage {
2810 inflight_htlc_msat: 0,
2811 effective_capacity: EffectiveCapacity::MaximumHTLC { amount_msat: 0 },
2813 assert_eq!(scorer.channel_penalty_msat(42, &target, &source, usage), 2048);
2815 // Advance to decay all liquidity offsets to zero.
2816 SinceEpoch::advance(Duration::from_secs(60 * 60 * 10));
2818 // Use a path in the opposite direction, which have zero for htlc_maximum_msat. This will
2819 // ensure that the effective capacity is zero to test division-by-zero edge cases.
2821 path_hop(target_pubkey(), 43, 2),
2822 path_hop(source_pubkey(), 42, 1),
2823 path_hop(sender_pubkey(), 41, 0),
2825 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 42);
2829 fn adds_anti_probing_penalty() {
2830 let logger = TestLogger::new();
2831 let network_graph = network_graph(&logger);
2832 let source = source_node_id();
2833 let target = target_node_id();
2834 let params = ProbabilisticScoringParameters {
2835 anti_probing_penalty_msat: 500,
2836 ..ProbabilisticScoringParameters::zero_penalty()
2838 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2840 // Check we receive no penalty for a low htlc_maximum_msat.
2841 let usage = ChannelUsage {
2842 amount_msat: 512_000,
2843 inflight_htlc_msat: 0,
2844 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
2846 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2848 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity.
2849 let usage = ChannelUsage {
2850 amount_msat: 512_000,
2851 inflight_htlc_msat: 0,
2852 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_024_000 },
2854 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500);
2856 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity/2.
2857 let usage = ChannelUsage {
2858 amount_msat: 512_000,
2859 inflight_htlc_msat: 0,
2860 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 512_000 },
2862 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500);
2864 // Check we receive no anti-probing penalty for htlc_maximum_msat == channel_capacity/2 - 1.
2865 let usage = ChannelUsage {
2866 amount_msat: 512_000,
2867 inflight_htlc_msat: 0,
2868 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 511_999 },
2870 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);