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