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<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,
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.liquidity_offset_half_life);
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.liquidity_offset_half_life);
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, half_life: Duration
696 ) -> DirectedChannelLiquidity<&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
721 &mut self, source: &NodeId, target: &NodeId, capacity_msat: u64, half_life: Duration
722 ) -> DirectedChannelLiquidity<&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.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 liquidity_offset_half_life = self.params.liquidity_offset_half_life;
999 let amount_msat = usage.amount_msat;
1000 let capacity_msat = usage.effective_capacity.as_msat()
1001 .saturating_sub(usage.inflight_htlc_msat);
1002 self.channel_liquidities
1003 .get(&short_channel_id)
1004 .unwrap_or(&ChannelLiquidity::new())
1005 .as_directed(source, target, capacity_msat, liquidity_offset_half_life)
1006 .penalty_msat(amount_msat, &self.params)
1007 .saturating_add(anti_probing_penalty_msat)
1008 .saturating_add(base_penalty_msat)
1011 fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
1012 let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
1013 let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
1014 log_trace!(self.logger, "Scoring path through to SCID {} as having failed at {} msat", short_channel_id, amount_msat);
1015 let network_graph = self.network_graph.read_only();
1016 for (hop_idx, hop) in path.iter().enumerate() {
1017 let target = NodeId::from_pubkey(&hop.pubkey);
1018 let channel_directed_from_source = network_graph.channels()
1019 .get(&hop.short_channel_id)
1020 .and_then(|channel| channel.as_directed_to(&target));
1022 if hop.short_channel_id == short_channel_id && hop_idx == 0 {
1023 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);
1026 // Only score announced channels.
1027 if let Some((channel, source)) = channel_directed_from_source {
1028 let capacity_msat = channel.effective_capacity().as_msat();
1029 if hop.short_channel_id == short_channel_id {
1030 self.channel_liquidities
1031 .entry(hop.short_channel_id)
1032 .or_insert_with(ChannelLiquidity::new)
1033 .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life)
1034 .failed_at_channel(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1038 self.channel_liquidities
1039 .entry(hop.short_channel_id)
1040 .or_insert_with(ChannelLiquidity::new)
1041 .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life)
1042 .failed_downstream(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1044 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).",
1045 hop.short_channel_id);
1050 fn payment_path_successful(&mut self, path: &[&RouteHop]) {
1051 let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
1052 let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
1053 log_trace!(self.logger, "Scoring path through SCID {} as having succeeded at {} msat.",
1054 path.split_last().map(|(hop, _)| hop.short_channel_id).unwrap_or(0), amount_msat);
1055 let network_graph = self.network_graph.read_only();
1057 let target = NodeId::from_pubkey(&hop.pubkey);
1058 let channel_directed_from_source = network_graph.channels()
1059 .get(&hop.short_channel_id)
1060 .and_then(|channel| channel.as_directed_to(&target));
1062 // Only score announced channels.
1063 if let Some((channel, source)) = channel_directed_from_source {
1064 let capacity_msat = channel.effective_capacity().as_msat();
1065 self.channel_liquidities
1066 .entry(hop.short_channel_id)
1067 .or_insert_with(ChannelLiquidity::new)
1068 .as_directed_mut(source, &target, capacity_msat, liquidity_offset_half_life)
1069 .successful(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1071 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).",
1072 hop.short_channel_id);
1077 fn probe_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
1078 self.payment_path_failed(path, short_channel_id)
1081 fn probe_successful(&mut self, path: &[&RouteHop]) {
1082 self.payment_path_failed(path, u64::max_value())
1087 const BITS: u32 = 64;
1088 const HIGHEST_BIT: u32 = BITS - 1;
1089 const LOWER_BITS: u32 = 6;
1090 pub(super) const LOWER_BITS_BOUND: u64 = 1 << LOWER_BITS;
1091 const LOWER_BITMASK: u64 = (1 << LOWER_BITS) - 1;
1093 /// Look-up table for `log10(x) * 2048` where row `i` is used for each `x` having `i` as the
1094 /// most significant bit. The next 4 bits of `x`, if applicable, are used for the second index.
1095 const LOG10_TIMES_2048: [[u16; (LOWER_BITS_BOUND) as usize]; BITS as usize] = [
1096 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1097 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1098 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1099 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
1100 [617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
1101 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617, 617,
1102 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977,
1103 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977, 977],
1104 [1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233, 1233,
1105 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431, 1431,
1106 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594,
1107 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731, 1731],
1108 [1850, 1850, 1850, 1850, 1850, 1850, 1850, 1850, 1954, 1954, 1954, 1954, 1954, 1954, 1954, 1954,
1109 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2048, 2133, 2133, 2133, 2133, 2133, 2133, 2133, 2133,
1110 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2210, 2281, 2281, 2281, 2281, 2281, 2281, 2281, 2281,
1111 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2347, 2409, 2409, 2409, 2409, 2409, 2409, 2409, 2409],
1112 [2466, 2466, 2466, 2466, 2520, 2520, 2520, 2520, 2571, 2571, 2571, 2571, 2619, 2619, 2619, 2619,
1113 2665, 2665, 2665, 2665, 2708, 2708, 2708, 2708, 2749, 2749, 2749, 2749, 2789, 2789, 2789, 2789,
1114 2827, 2827, 2827, 2827, 2863, 2863, 2863, 2863, 2898, 2898, 2898, 2898, 2931, 2931, 2931, 2931,
1115 2964, 2964, 2964, 2964, 2995, 2995, 2995, 2995, 3025, 3025, 3025, 3025, 3054, 3054, 3054, 3054],
1116 [3083, 3083, 3110, 3110, 3136, 3136, 3162, 3162, 3187, 3187, 3212, 3212, 3235, 3235, 3259, 3259,
1117 3281, 3281, 3303, 3303, 3324, 3324, 3345, 3345, 3366, 3366, 3386, 3386, 3405, 3405, 3424, 3424,
1118 3443, 3443, 3462, 3462, 3479, 3479, 3497, 3497, 3514, 3514, 3531, 3531, 3548, 3548, 3564, 3564,
1119 3580, 3580, 3596, 3596, 3612, 3612, 3627, 3627, 3642, 3642, 3656, 3656, 3671, 3671, 3685, 3685],
1120 [3699, 3713, 3726, 3740, 3753, 3766, 3779, 3791, 3804, 3816, 3828, 3840, 3852, 3864, 3875, 3886,
1121 3898, 3909, 3919, 3930, 3941, 3951, 3962, 3972, 3982, 3992, 4002, 4012, 4022, 4031, 4041, 4050,
1122 4060, 4069, 4078, 4087, 4096, 4105, 4114, 4122, 4131, 4139, 4148, 4156, 4164, 4173, 4181, 4189,
1123 4197, 4205, 4213, 4220, 4228, 4236, 4243, 4251, 4258, 4266, 4273, 4280, 4287, 4294, 4302, 4309],
1124 [4316, 4329, 4343, 4356, 4369, 4382, 4395, 4408, 4420, 4433, 4445, 4457, 4468, 4480, 4492, 4503,
1125 4514, 4525, 4536, 4547, 4557, 4568, 4578, 4589, 4599, 4609, 4619, 4629, 4638, 4648, 4657, 4667,
1126 4676, 4685, 4695, 4704, 4713, 4721, 4730, 4739, 4747, 4756, 4764, 4773, 4781, 4789, 4797, 4805,
1127 4813, 4821, 4829, 4837, 4845, 4852, 4860, 4867, 4875, 4882, 4889, 4897, 4904, 4911, 4918, 4925],
1128 [4932, 4946, 4959, 4973, 4986, 4999, 5012, 5024, 5037, 5049, 5061, 5073, 5085, 5097, 5108, 5119,
1129 5131, 5142, 5153, 5163, 5174, 5184, 5195, 5205, 5215, 5225, 5235, 5245, 5255, 5264, 5274, 5283,
1130 5293, 5302, 5311, 5320, 5329, 5338, 5347, 5355, 5364, 5372, 5381, 5389, 5397, 5406, 5414, 5422,
1131 5430, 5438, 5446, 5453, 5461, 5469, 5476, 5484, 5491, 5499, 5506, 5513, 5520, 5527, 5535, 5542],
1132 [5549, 5562, 5576, 5589, 5603, 5615, 5628, 5641, 5653, 5666, 5678, 5690, 5701, 5713, 5725, 5736,
1133 5747, 5758, 5769, 5780, 5790, 5801, 5811, 5822, 5832, 5842, 5852, 5862, 5871, 5881, 5890, 5900,
1134 5909, 5918, 5928, 5937, 5946, 5954, 5963, 5972, 5980, 5989, 5997, 6006, 6014, 6022, 6030, 6038,
1135 6046, 6054, 6062, 6070, 6078, 6085, 6093, 6100, 6108, 6115, 6122, 6130, 6137, 6144, 6151, 6158],
1136 [6165, 6179, 6192, 6206, 6219, 6232, 6245, 6257, 6270, 6282, 6294, 6306, 6318, 6330, 6341, 6352,
1137 6364, 6375, 6386, 6396, 6407, 6417, 6428, 6438, 6448, 6458, 6468, 6478, 6488, 6497, 6507, 6516,
1138 6526, 6535, 6544, 6553, 6562, 6571, 6580, 6588, 6597, 6605, 6614, 6622, 6630, 6639, 6647, 6655,
1139 6663, 6671, 6679, 6686, 6694, 6702, 6709, 6717, 6724, 6732, 6739, 6746, 6753, 6761, 6768, 6775],
1140 [6782, 6795, 6809, 6822, 6836, 6849, 6861, 6874, 6886, 6899, 6911, 6923, 6934, 6946, 6958, 6969,
1141 6980, 6991, 7002, 7013, 7023, 7034, 7044, 7055, 7065, 7075, 7085, 7095, 7104, 7114, 7124, 7133,
1142 7142, 7151, 7161, 7170, 7179, 7187, 7196, 7205, 7213, 7222, 7230, 7239, 7247, 7255, 7263, 7271,
1143 7279, 7287, 7295, 7303, 7311, 7318, 7326, 7333, 7341, 7348, 7355, 7363, 7370, 7377, 7384, 7391],
1144 [7398, 7412, 7425, 7439, 7452, 7465, 7478, 7490, 7503, 7515, 7527, 7539, 7551, 7563, 7574, 7585,
1145 7597, 7608, 7619, 7629, 7640, 7651, 7661, 7671, 7681, 7691, 7701, 7711, 7721, 7731, 7740, 7749,
1146 7759, 7768, 7777, 7786, 7795, 7804, 7813, 7821, 7830, 7838, 7847, 7855, 7864, 7872, 7880, 7888,
1147 7896, 7904, 7912, 7919, 7927, 7935, 7942, 7950, 7957, 7965, 7972, 7979, 7986, 7994, 8001, 8008],
1148 [8015, 8028, 8042, 8055, 8069, 8082, 8094, 8107, 8119, 8132, 8144, 8156, 8167, 8179, 8191, 8202,
1149 8213, 8224, 8235, 8246, 8256, 8267, 8277, 8288, 8298, 8308, 8318, 8328, 8337, 8347, 8357, 8366,
1150 8375, 8384, 8394, 8403, 8412, 8420, 8429, 8438, 8446, 8455, 8463, 8472, 8480, 8488, 8496, 8504,
1151 8512, 8520, 8528, 8536, 8544, 8551, 8559, 8566, 8574, 8581, 8588, 8596, 8603, 8610, 8617, 8624],
1152 [8631, 8645, 8659, 8672, 8685, 8698, 8711, 8723, 8736, 8748, 8760, 8772, 8784, 8796, 8807, 8818,
1153 8830, 8841, 8852, 8862, 8873, 8884, 8894, 8904, 8914, 8924, 8934, 8944, 8954, 8964, 8973, 8982,
1154 8992, 9001, 9010, 9019, 9028, 9037, 9046, 9054, 9063, 9071, 9080, 9088, 9097, 9105, 9113, 9121,
1155 9129, 9137, 9145, 9152, 9160, 9168, 9175, 9183, 9190, 9198, 9205, 9212, 9219, 9227, 9234, 9241],
1156 [9248, 9261, 9275, 9288, 9302, 9315, 9327, 9340, 9352, 9365, 9377, 9389, 9400, 9412, 9424, 9435,
1157 9446, 9457, 9468, 9479, 9490, 9500, 9510, 9521, 9531, 9541, 9551, 9561, 9570, 9580, 9590, 9599,
1158 9608, 9617, 9627, 9636, 9645, 9653, 9662, 9671, 9679, 9688, 9696, 9705, 9713, 9721, 9729, 9737,
1159 9745, 9753, 9761, 9769, 9777, 9784, 9792, 9799, 9807, 9814, 9821, 9829, 9836, 9843, 9850, 9857],
1160 [9864, 9878, 9892, 9905, 9918, 9931, 9944, 9956, 9969, 9981, 9993, 10005, 10017, 10029, 10040, 10051,
1161 10063, 10074, 10085, 10095, 10106, 10117, 10127, 10137, 10147, 10157, 10167, 10177, 10187, 10197, 10206, 10215,
1162 10225, 10234, 10243, 10252, 10261, 10270, 10279, 10287, 10296, 10304, 10313, 10321, 10330, 10338, 10346, 10354,
1163 10362, 10370, 10378, 10385, 10393, 10401, 10408, 10416, 10423, 10431, 10438, 10445, 10452, 10460, 10467, 10474],
1164 [10481, 10494, 10508, 10521, 10535, 10548, 10560, 10573, 10585, 10598, 10610, 10622, 10634, 10645, 10657, 10668,
1165 10679, 10690, 10701, 10712, 10723, 10733, 10743, 10754, 10764, 10774, 10784, 10794, 10803, 10813, 10823, 10832,
1166 10841, 10851, 10860, 10869, 10878, 10886, 10895, 10904, 10912, 10921, 10929, 10938, 10946, 10954, 10962, 10970,
1167 10978, 10986, 10994, 11002, 11010, 11017, 11025, 11032, 11040, 11047, 11054, 11062, 11069, 11076, 11083, 11090],
1168 [11097, 11111, 11125, 11138, 11151, 11164, 11177, 11189, 11202, 11214, 11226, 11238, 11250, 11262, 11273, 11284,
1169 11296, 11307, 11318, 11328, 11339, 11350, 11360, 11370, 11380, 11390, 11400, 11410, 11420, 11430, 11439, 11448,
1170 11458, 11467, 11476, 11485, 11494, 11503, 11512, 11520, 11529, 11538, 11546, 11554, 11563, 11571, 11579, 11587,
1171 11595, 11603, 11611, 11618, 11626, 11634, 11641, 11649, 11656, 11664, 11671, 11678, 11685, 11693, 11700, 11707],
1172 [11714, 11727, 11741, 11754, 11768, 11781, 11793, 11806, 11818, 11831, 11843, 11855, 11867, 11878, 11890, 11901,
1173 11912, 11923, 11934, 11945, 11956, 11966, 11976, 11987, 11997, 12007, 12017, 12027, 12036, 12046, 12056, 12065,
1174 12074, 12084, 12093, 12102, 12111, 12119, 12128, 12137, 12146, 12154, 12162, 12171, 12179, 12187, 12195, 12203,
1175 12211, 12219, 12227, 12235, 12243, 12250, 12258, 12265, 12273, 12280, 12287, 12295, 12302, 12309, 12316, 12323],
1176 [12330, 12344, 12358, 12371, 12384, 12397, 12410, 12423, 12435, 12447, 12459, 12471, 12483, 12495, 12506, 12517,
1177 12529, 12540, 12551, 12561, 12572, 12583, 12593, 12603, 12613, 12623, 12633, 12643, 12653, 12663, 12672, 12682,
1178 12691, 12700, 12709, 12718, 12727, 12736, 12745, 12753, 12762, 12771, 12779, 12787, 12796, 12804, 12812, 12820,
1179 12828, 12836, 12844, 12851, 12859, 12867, 12874, 12882, 12889, 12897, 12904, 12911, 12918, 12926, 12933, 12940],
1180 [12947, 12960, 12974, 12987, 13001, 13014, 13026, 13039, 13051, 13064, 13076, 13088, 13100, 13111, 13123, 13134,
1181 13145, 13156, 13167, 13178, 13189, 13199, 13209, 13220, 13230, 13240, 13250, 13260, 13269, 13279, 13289, 13298,
1182 13307, 13317, 13326, 13335, 13344, 13352, 13361, 13370, 13379, 13387, 13395, 13404, 13412, 13420, 13428, 13436,
1183 13444, 13452, 13460, 13468, 13476, 13483, 13491, 13498, 13506, 13513, 13521, 13528, 13535, 13542, 13549, 13556],
1184 [13563, 13577, 13591, 13604, 13617, 13630, 13643, 13656, 13668, 13680, 13692, 13704, 13716, 13728, 13739, 13750,
1185 13762, 13773, 13784, 13794, 13805, 13816, 13826, 13836, 13846, 13857, 13866, 13876, 13886, 13896, 13905, 13915,
1186 13924, 13933, 13942, 13951, 13960, 13969, 13978, 13986, 13995, 14004, 14012, 14020, 14029, 14037, 14045, 14053,
1187 14061, 14069, 14077, 14084, 14092, 14100, 14107, 14115, 14122, 14130, 14137, 14144, 14151, 14159, 14166, 14173],
1188 [14180, 14194, 14207, 14220, 14234, 14247, 14259, 14272, 14284, 14297, 14309, 14321, 14333, 14344, 14356, 14367,
1189 14378, 14389, 14400, 14411, 14422, 14432, 14443, 14453, 14463, 14473, 14483, 14493, 14502, 14512, 14522, 14531,
1190 14540, 14550, 14559, 14568, 14577, 14586, 14594, 14603, 14612, 14620, 14628, 14637, 14645, 14653, 14661, 14669,
1191 14677, 14685, 14693, 14701, 14709, 14716, 14724, 14731, 14739, 14746, 14754, 14761, 14768, 14775, 14782, 14789],
1192 [14796, 14810, 14824, 14837, 14850, 14863, 14876, 14889, 14901, 14913, 14925, 14937, 14949, 14961, 14972, 14984,
1193 14995, 15006, 15017, 15027, 15038, 15049, 15059, 15069, 15079, 15090, 15099, 15109, 15119, 15129, 15138, 15148,
1194 15157, 15166, 15175, 15184, 15193, 15202, 15211, 15219, 15228, 15237, 15245, 15253, 15262, 15270, 15278, 15286,
1195 15294, 15302, 15310, 15317, 15325, 15333, 15340, 15348, 15355, 15363, 15370, 15377, 15384, 15392, 15399, 15406],
1196 [15413, 15427, 15440, 15453, 15467, 15480, 15492, 15505, 15517, 15530, 15542, 15554, 15566, 15577, 15589, 15600,
1197 15611, 15622, 15633, 15644, 15655, 15665, 15676, 15686, 15696, 15706, 15716, 15726, 15736, 15745, 15755, 15764,
1198 15773, 15783, 15792, 15801, 15810, 15819, 15827, 15836, 15845, 15853, 15862, 15870, 15878, 15886, 15894, 15903,
1199 15910, 15918, 15926, 15934, 15942, 15949, 15957, 15964, 15972, 15979, 15987, 15994, 16001, 16008, 16015, 16022],
1200 [16029, 16043, 16057, 16070, 16083, 16096, 16109, 16122, 16134, 16146, 16158, 16170, 16182, 16194, 16205, 16217,
1201 16228, 16239, 16250, 16260, 16271, 16282, 16292, 16302, 16312, 16323, 16332, 16342, 16352, 16362, 16371, 16381,
1202 16390, 16399, 16408, 16417, 16426, 16435, 16444, 16452, 16461, 16470, 16478, 16486, 16495, 16503, 16511, 16519,
1203 16527, 16535, 16543, 16550, 16558, 16566, 16573, 16581, 16588, 16596, 16603, 16610, 16618, 16625, 16632, 16639],
1204 [16646, 16660, 16673, 16686, 16700, 16713, 16725, 16738, 16751, 16763, 16775, 16787, 16799, 16810, 16822, 16833,
1205 16844, 16855, 16866, 16877, 16888, 16898, 16909, 16919, 16929, 16939, 16949, 16959, 16969, 16978, 16988, 16997,
1206 17006, 17016, 17025, 17034, 17043, 17052, 17060, 17069, 17078, 17086, 17095, 17103, 17111, 17119, 17127, 17136,
1207 17143, 17151, 17159, 17167, 17175, 17182, 17190, 17197, 17205, 17212, 17220, 17227, 17234, 17241, 17248, 17255],
1208 [17262, 17276, 17290, 17303, 17316, 17329, 17342, 17355, 17367, 17379, 17391, 17403, 17415, 17427, 17438, 17450,
1209 17461, 17472, 17483, 17493, 17504, 17515, 17525, 17535, 17546, 17556, 17565, 17575, 17585, 17595, 17604, 17614,
1210 17623, 17632, 17641, 17650, 17659, 17668, 17677, 17685, 17694, 17703, 17711, 17719, 17728, 17736, 17744, 17752,
1211 17760, 17768, 17776, 17784, 17791, 17799, 17806, 17814, 17821, 17829, 17836, 17843, 17851, 17858, 17865, 17872],
1212 [17879, 17893, 17906, 17920, 17933, 17946, 17958, 17971, 17984, 17996, 18008, 18020, 18032, 18043, 18055, 18066,
1213 18077, 18088, 18099, 18110, 18121, 18131, 18142, 18152, 18162, 18172, 18182, 18192, 18202, 18211, 18221, 18230,
1214 18239, 18249, 18258, 18267, 18276, 18285, 18293, 18302, 18311, 18319, 18328, 18336, 18344, 18352, 18360, 18369,
1215 18377, 18384, 18392, 18400, 18408, 18415, 18423, 18430, 18438, 18445, 18453, 18460, 18467, 18474, 18481, 18488],
1216 [18495, 18509, 18523, 18536, 18549, 18562, 18575, 18588, 18600, 18612, 18624, 18636, 18648, 18660, 18671, 18683,
1217 18694, 18705, 18716, 18726, 18737, 18748, 18758, 18768, 18779, 18789, 18799, 18808, 18818, 18828, 18837, 18847,
1218 18856, 18865, 18874, 18883, 18892, 18901, 18910, 18919, 18927, 18936, 18944, 18952, 18961, 18969, 18977, 18985,
1219 18993, 19001, 19009, 19017, 19024, 19032, 19039, 19047, 19054, 19062, 19069, 19076, 19084, 19091, 19098, 19105],
1220 [19112, 19126, 19139, 19153, 19166, 19179, 19191, 19204, 19217, 19229, 19241, 19253, 19265, 19276, 19288, 19299,
1221 19310, 19321, 19332, 19343, 19354, 19364, 19375, 19385, 19395, 19405, 19415, 19425, 19435, 19444, 19454, 19463,
1222 19472, 19482, 19491, 19500, 19509, 19518, 19526, 19535, 19544, 19552, 19561, 19569, 19577, 19585, 19594, 19602,
1223 19610, 19617, 19625, 19633, 19641, 19648, 19656, 19663, 19671, 19678, 19686, 19693, 19700, 19707, 19714, 19721],
1224 [19728, 19742, 19756, 19769, 19782, 19795, 19808, 19821, 19833, 19845, 19857, 19869, 19881, 19893, 19904, 19916,
1225 19927, 19938, 19949, 19960, 19970, 19981, 19991, 20001, 20012, 20022, 20032, 20041, 20051, 20061, 20070, 20080,
1226 20089, 20098, 20107, 20116, 20125, 20134, 20143, 20152, 20160, 20169, 20177, 20185, 20194, 20202, 20210, 20218,
1227 20226, 20234, 20242, 20250, 20257, 20265, 20272, 20280, 20287, 20295, 20302, 20309, 20317, 20324, 20331, 20338],
1228 [20345, 20359, 20372, 20386, 20399, 20412, 20425, 20437, 20450, 20462, 20474, 20486, 20498, 20509, 20521, 20532,
1229 20543, 20554, 20565, 20576, 20587, 20597, 20608, 20618, 20628, 20638, 20648, 20658, 20668, 20677, 20687, 20696,
1230 20705, 20715, 20724, 20733, 20742, 20751, 20759, 20768, 20777, 20785, 20794, 20802, 20810, 20818, 20827, 20835,
1231 20843, 20850, 20858, 20866, 20874, 20881, 20889, 20896, 20904, 20911, 20919, 20926, 20933, 20940, 20947, 20954],
1232 [20961, 20975, 20989, 21002, 21015, 21028, 21041, 21054, 21066, 21078, 21090, 21102, 21114, 21126, 21137, 21149,
1233 21160, 21171, 21182, 21193, 21203, 21214, 21224, 21234, 21245, 21255, 21265, 21274, 21284, 21294, 21303, 21313,
1234 21322, 21331, 21340, 21349, 21358, 21367, 21376, 21385, 21393, 21402, 21410, 21418, 21427, 21435, 21443, 21451,
1235 21459, 21467, 21475, 21483, 21490, 21498, 21505, 21513, 21520, 21528, 21535, 21542, 21550, 21557, 21564, 21571],
1236 [21578, 21592, 21605, 21619, 21632, 21645, 21658, 21670, 21683, 21695, 21707, 21719, 21731, 21742, 21754, 21765,
1237 21776, 21787, 21798, 21809, 21820, 21830, 21841, 21851, 21861, 21871, 21881, 21891, 21901, 21910, 21920, 21929,
1238 21938, 21948, 21957, 21966, 21975, 21984, 21992, 22001, 22010, 22018, 22027, 22035, 22043, 22051, 22060, 22068,
1239 22076, 22083, 22091, 22099, 22107, 22114, 22122, 22129, 22137, 22144, 22152, 22159, 22166, 22173, 22180, 22187],
1240 [22194, 22208, 22222, 22235, 22248, 22261, 22274, 22287, 22299, 22311, 22323, 22335, 22347, 22359, 22370, 22382,
1241 22393, 22404, 22415, 22426, 22436, 22447, 22457, 22467, 22478, 22488, 22498, 22507, 22517, 22527, 22536, 22546,
1242 22555, 22564, 22573, 22582, 22591, 22600, 22609, 22618, 22626, 22635, 22643, 22651, 22660, 22668, 22676, 22684,
1243 22692, 22700, 22708, 22716, 22723, 22731, 22738, 22746, 22753, 22761, 22768, 22775, 22783, 22790, 22797, 22804],
1244 [22811, 22825, 22838, 22852, 22865, 22878, 22891, 22903, 22916, 22928, 22940, 22952, 22964, 22975, 22987, 22998,
1245 23009, 23020, 23031, 23042, 23053, 23063, 23074, 23084, 23094, 23104, 23114, 23124, 23134, 23143, 23153, 23162,
1246 23171, 23181, 23190, 23199, 23208, 23217, 23225, 23234, 23243, 23251, 23260, 23268, 23276, 23284, 23293, 23301,
1247 23309, 23316, 23324, 23332, 23340, 23347, 23355, 23363, 23370, 23377, 23385, 23392, 23399, 23406, 23413, 23420],
1248 [23427, 23441, 23455, 23468, 23481, 23494, 23507, 23520, 23532, 23544, 23556, 23568, 23580, 23592, 23603, 23615,
1249 23626, 23637, 23648, 23659, 23669, 23680, 23690, 23700, 23711, 23721, 23731, 23740, 23750, 23760, 23769, 23779,
1250 23788, 23797, 23806, 23815, 23824, 23833, 23842, 23851, 23859, 23868, 23876, 23884, 23893, 23901, 23909, 23917,
1251 23925, 23933, 23941, 23949, 23956, 23964, 23972, 23979, 23986, 23994, 24001, 24008, 24016, 24023, 24030, 24037],
1252 [24044, 24058, 24071, 24085, 24098, 24111, 24124, 24136, 24149, 24161, 24173, 24185, 24197, 24208, 24220, 24231,
1253 24242, 24253, 24264, 24275, 24286, 24296, 24307, 24317, 24327, 24337, 24347, 24357, 24367, 24376, 24386, 24395,
1254 24405, 24414, 24423, 24432, 24441, 24450, 24458, 24467, 24476, 24484, 24493, 24501, 24509, 24517, 24526, 24534,
1255 24542, 24550, 24557, 24565, 24573, 24580, 24588, 24596, 24603, 24610, 24618, 24625, 24632, 24639, 24646, 24653],
1256 [24660, 24674, 24688, 24701, 24714, 24727, 24740, 24753, 24765, 24777, 24790, 24801, 24813, 24825, 24836, 24848,
1257 24859, 24870, 24881, 24892, 24902, 24913, 24923, 24933, 24944, 24954, 24964, 24973, 24983, 24993, 25002, 25012,
1258 25021, 25030, 25039, 25048, 25057, 25066, 25075, 25084, 25092, 25101, 25109, 25117, 25126, 25134, 25142, 25150,
1259 25158, 25166, 25174, 25182, 25189, 25197, 25205, 25212, 25219, 25227, 25234, 25241, 25249, 25256, 25263, 25270],
1260 [25277, 25291, 25304, 25318, 25331, 25344, 25357, 25369, 25382, 25394, 25406, 25418, 25430, 25441, 25453, 25464,
1261 25475, 25486, 25497, 25508, 25519, 25529, 25540, 25550, 25560, 25570, 25580, 25590, 25600, 25609, 25619, 25628,
1262 25638, 25647, 25656, 25665, 25674, 25683, 25691, 25700, 25709, 25717, 25726, 25734, 25742, 25750, 25759, 25767,
1263 25775, 25783, 25790, 25798, 25806, 25813, 25821, 25829, 25836, 25843, 25851, 25858, 25865, 25872, 25879, 25886],
1264 [25893, 25907, 25921, 25934, 25947, 25960, 25973, 25986, 25998, 26010, 26023, 26034, 26046, 26058, 26069, 26081,
1265 26092, 26103, 26114, 26125, 26135, 26146, 26156, 26166, 26177, 26187, 26197, 26206, 26216, 26226, 26235, 26245,
1266 26254, 26263, 26272, 26281, 26290, 26299, 26308, 26317, 26325, 26334, 26342, 26351, 26359, 26367, 26375, 26383,
1267 26391, 26399, 26407, 26415, 26422, 26430, 26438, 26445, 26453, 26460, 26467, 26474, 26482, 26489, 26496, 26503],
1268 [26510, 26524, 26537, 26551, 26564, 26577, 26590, 26602, 26615, 26627, 26639, 26651, 26663, 26674, 26686, 26697,
1269 26708, 26719, 26730, 26741, 26752, 26762, 26773, 26783, 26793, 26803, 26813, 26823, 26833, 26842, 26852, 26861,
1270 26871, 26880, 26889, 26898, 26907, 26916, 26924, 26933, 26942, 26950, 26959, 26967, 26975, 26983, 26992, 27000,
1271 27008, 27016, 27023, 27031, 27039, 27046, 27054, 27062, 27069, 27076, 27084, 27091, 27098, 27105, 27112, 27119],
1272 [27126, 27140, 27154, 27167, 27180, 27193, 27206, 27219, 27231, 27243, 27256, 27267, 27279, 27291, 27302, 27314,
1273 27325, 27336, 27347, 27358, 27368, 27379, 27389, 27399, 27410, 27420, 27430, 27439, 27449, 27459, 27468, 27478,
1274 27487, 27496, 27505, 27514, 27523, 27532, 27541, 27550, 27558, 27567, 27575, 27584, 27592, 27600, 27608, 27616,
1275 27624, 27632, 27640, 27648, 27655, 27663, 27671, 27678, 27686, 27693, 27700, 27707, 27715, 27722, 27729, 27736],
1276 [27743, 27757, 27770, 27784, 27797, 27810, 27823, 27835, 27848, 27860, 27872, 27884, 27896, 27907, 27919, 27930,
1277 27941, 27952, 27963, 27974, 27985, 27995, 28006, 28016, 28026, 28036, 28046, 28056, 28066, 28075, 28085, 28094,
1278 28104, 28113, 28122, 28131, 28140, 28149, 28157, 28166, 28175, 28183, 28192, 28200, 28208, 28217, 28225, 28233,
1279 28241, 28249, 28256, 28264, 28272, 28280, 28287, 28295, 28302, 28309, 28317, 28324, 28331, 28338, 28345, 28352],
1280 [28359, 28373, 28387, 28400, 28413, 28426, 28439, 28452, 28464, 28476, 28489, 28501, 28512, 28524, 28535, 28547,
1281 28558, 28569, 28580, 28591, 28601, 28612, 28622, 28633, 28643, 28653, 28663, 28672, 28682, 28692, 28701, 28711,
1282 28720, 28729, 28738, 28747, 28756, 28765, 28774, 28783, 28791, 28800, 28808, 28817, 28825, 28833, 28841, 28849,
1283 28857, 28865, 28873, 28881, 28888, 28896, 28904, 28911, 28919, 28926, 28933, 28941, 28948, 28955, 28962, 28969],
1284 [28976, 28990, 29003, 29017, 29030, 29043, 29056, 29068, 29081, 29093, 29105, 29117, 29129, 29140, 29152, 29163,
1285 29174, 29185, 29196, 29207, 29218, 29228, 29239, 29249, 29259, 29269, 29279, 29289, 29299, 29308, 29318, 29327,
1286 29337, 29346, 29355, 29364, 29373, 29382, 29390, 29399, 29408, 29416, 29425, 29433, 29441, 29450, 29458, 29466,
1287 29474, 29482, 29489, 29497, 29505, 29513, 29520, 29528, 29535, 29542, 29550, 29557, 29564, 29571, 29578, 29585],
1288 [29592, 29606, 29620, 29633, 29646, 29659, 29672, 29685, 29697, 29709, 29722, 29734, 29745, 29757, 29768, 29780,
1289 29791, 29802, 29813, 29824, 29834, 29845, 29855, 29866, 29876, 29886, 29896, 29906, 29915, 29925, 29934, 29944,
1290 29953, 29962, 29971, 29980, 29989, 29998, 30007, 30016, 30024, 30033, 30041, 30050, 30058, 30066, 30074, 30082,
1291 30090, 30098, 30106, 30114, 30121, 30129, 30137, 30144, 30152, 30159, 30166, 30174, 30181, 30188, 30195, 30202],
1292 [30209, 30223, 30236, 30250, 30263, 30276, 30289, 30301, 30314, 30326, 30338, 30350, 30362, 30373, 30385, 30396,
1293 30407, 30418, 30429, 30440, 30451, 30461, 30472, 30482, 30492, 30502, 30512, 30522, 30532, 30541, 30551, 30560,
1294 30570, 30579, 30588, 30597, 30606, 30615, 30624, 30632, 30641, 30649, 30658, 30666, 30674, 30683, 30691, 30699,
1295 30707, 30715, 30722, 30730, 30738, 30746, 30753, 30761, 30768, 30775, 30783, 30790, 30797, 30804, 30811, 30818],
1296 [30825, 30839, 30853, 30866, 30879, 30892, 30905, 30918, 30930, 30943, 30955, 30967, 30978, 30990, 31001, 31013,
1297 31024, 31035, 31046, 31057, 31067, 31078, 31088, 31099, 31109, 31119, 31129, 31139, 31148, 31158, 31167, 31177,
1298 31186, 31195, 31204, 31213, 31222, 31231, 31240, 31249, 31257, 31266, 31274, 31283, 31291, 31299, 31307, 31315,
1299 31323, 31331, 31339, 31347, 31354, 31362, 31370, 31377, 31385, 31392, 31399, 31407, 31414, 31421, 31428, 31435],
1300 [31442, 31456, 31469, 31483, 31496, 31509, 31522, 31534, 31547, 31559, 31571, 31583, 31595, 31606, 31618, 31629,
1301 31640, 31652, 31662, 31673, 31684, 31694, 31705, 31715, 31725, 31735, 31745, 31755, 31765, 31774, 31784, 31793,
1302 31803, 31812, 31821, 31830, 31839, 31848, 31857, 31865, 31874, 31882, 31891, 31899, 31907, 31916, 31924, 31932,
1303 31940, 31948, 31955, 31963, 31971, 31979, 31986, 31994, 32001, 32008, 32016, 32023, 32030, 32037, 32044, 32052],
1304 [32058, 32072, 32086, 32099, 32112, 32125, 32138, 32151, 32163, 32176, 32188, 32200, 32211, 32223, 32234, 32246,
1305 32257, 32268, 32279, 32290, 32300, 32311, 32321, 32332, 32342, 32352, 32362, 32372, 32381, 32391, 32400, 32410,
1306 32419, 32428, 32437, 32446, 32455, 32464, 32473, 32482, 32490, 32499, 32507, 32516, 32524, 32532, 32540, 32548,
1307 32556, 32564, 32572, 32580, 32587, 32595, 32603, 32610, 32618, 32625, 32632, 32640, 32647, 32654, 32661, 32668],
1308 [32675, 32689, 32702, 32716, 32729, 32742, 32755, 32767, 32780, 32792, 32804, 32816, 32828, 32839, 32851, 32862,
1309 32873, 32885, 32895, 32906, 32917, 32927, 32938, 32948, 32958, 32968, 32978, 32988, 32998, 33007, 33017, 33026,
1310 33036, 33045, 33054, 33063, 33072, 33081, 33090, 33098, 33107, 33115, 33124, 33132, 33140, 33149, 33157, 33165,
1311 33173, 33181, 33188, 33196, 33204, 33212, 33219, 33227, 33234, 33241, 33249, 33256, 33263, 33270, 33278, 33285],
1312 [33292, 33305, 33319, 33332, 33345, 33358, 33371, 33384, 33396, 33409, 33421, 33433, 33444, 33456, 33467, 33479,
1313 33490, 33501, 33512, 33523, 33533, 33544, 33554, 33565, 33575, 33585, 33595, 33605, 33614, 33624, 33633, 33643,
1314 33652, 33661, 33670, 33680, 33688, 33697, 33706, 33715, 33723, 33732, 33740, 33749, 33757, 33765, 33773, 33781,
1315 33789, 33797, 33805, 33813, 33820, 33828, 33836, 33843, 33851, 33858, 33865, 33873, 33880, 33887, 33894, 33901],
1316 [33908, 33922, 33935, 33949, 33962, 33975, 33988, 34000, 34013, 34025, 34037, 34049, 34061, 34072, 34084, 34095,
1317 34106, 34118, 34128, 34139, 34150, 34160, 34171, 34181, 34191, 34201, 34211, 34221, 34231, 34240, 34250, 34259,
1318 34269, 34278, 34287, 34296, 34305, 34314, 34323, 34331, 34340, 34348, 34357, 34365, 34373, 34382, 34390, 34398,
1319 34406, 34414, 34422, 34429, 34437, 34445, 34452, 34460, 34467, 34475, 34482, 34489, 34496, 34503, 34511, 34518],
1320 [34525, 34538, 34552, 34565, 34578, 34591, 34604, 34617, 34629, 34642, 34654, 34666, 34677, 34689, 34700, 34712,
1321 34723, 34734, 34745, 34756, 34766, 34777, 34787, 34798, 34808, 34818, 34828, 34838, 34847, 34857, 34866, 34876,
1322 34885, 34894, 34904, 34913, 34921, 34930, 34939, 34948, 34956, 34965, 34973, 34982, 34990, 34998, 35006, 35014,
1323 35022, 35030, 35038, 35046, 35053, 35061, 35069, 35076, 35084, 35091, 35098, 35106, 35113, 35120, 35127, 35134],
1324 [35141, 35155, 35168, 35182, 35195, 35208, 35221, 35233, 35246, 35258, 35270, 35282, 35294, 35306, 35317, 35328,
1325 35340, 35351, 35361, 35372, 35383, 35393, 35404, 35414, 35424, 35434, 35444, 35454, 35464, 35473, 35483, 35492,
1326 35502, 35511, 35520, 35529, 35538, 35547, 35556, 35564, 35573, 35581, 35590, 35598, 35606, 35615, 35623, 35631,
1327 35639, 35647, 35655, 35662, 35670, 35678, 35685, 35693, 35700, 35708, 35715, 35722, 35729, 35736, 35744, 35751],
1328 [35758, 35771, 35785, 35798, 35811, 35824, 35837, 35850, 35862, 35875, 35887, 35899, 35910, 35922, 35934, 35945,
1329 35956, 35967, 35978, 35989, 35999, 36010, 36020, 36031, 36041, 36051, 36061, 36071, 36080, 36090, 36099, 36109,
1330 36118, 36127, 36137, 36146, 36154, 36163, 36172, 36181, 36189, 36198, 36206, 36215, 36223, 36231, 36239, 36247,
1331 36255, 36263, 36271, 36279, 36287, 36294, 36302, 36309, 36317, 36324, 36331, 36339, 36346, 36353, 36360, 36367],
1332 [36374, 36388, 36401, 36415, 36428, 36441, 36454, 36466, 36479, 36491, 36503, 36515, 36527, 36539, 36550, 36561,
1333 36573, 36584, 36594, 36605, 36616, 36626, 36637, 36647, 36657, 36667, 36677, 36687, 36697, 36706, 36716, 36725,
1334 36735, 36744, 36753, 36762, 36771, 36780, 36789, 36797, 36806, 36814, 36823, 36831, 36839, 36848, 36856, 36864,
1335 36872, 36880, 36888, 36895, 36903, 36911, 36918, 36926, 36933, 36941, 36948, 36955, 36962, 36969, 36977, 36984],
1336 [36991, 37004, 37018, 37031, 37044, 37057, 37070, 37083, 37095, 37108, 37120, 37132, 37143, 37155, 37167, 37178,
1337 37189, 37200, 37211, 37222, 37232, 37243, 37253, 37264, 37274, 37284, 37294, 37304, 37313, 37323, 37332, 37342,
1338 37351, 37360, 37370, 37379, 37388, 37396, 37405, 37414, 37422, 37431, 37439, 37448, 37456, 37464, 37472, 37480,
1339 37488, 37496, 37504, 37512, 37520, 37527, 37535, 37542, 37550, 37557, 37564, 37572, 37579, 37586, 37593, 37600],
1340 [37607, 37621, 37634, 37648, 37661, 37674, 37687, 37699, 37712, 37724, 37736, 37748, 37760, 37772, 37783, 37794,
1341 37806, 37817, 37828, 37838, 37849, 37859, 37870, 37880, 37890, 37900, 37910, 37920, 37930, 37939, 37949, 37958,
1342 37968, 37977, 37986, 37995, 38004, 38013, 38022, 38030, 38039, 38047, 38056, 38064, 38072, 38081, 38089, 38097,
1343 38105, 38113, 38121, 38128, 38136, 38144, 38151, 38159, 38166, 38174, 38181, 38188, 38195, 38202, 38210, 38217],
1344 [38224, 38237, 38251, 38264, 38278, 38290, 38303, 38316, 38328, 38341, 38353, 38365, 38376, 38388, 38400, 38411,
1345 38422, 38433, 38444, 38455, 38465, 38476, 38486, 38497, 38507, 38517, 38527, 38537, 38546, 38556, 38565, 38575,
1346 38584, 38593, 38603, 38612, 38621, 38629, 38638, 38647, 38655, 38664, 38672, 38681, 38689, 38697, 38705, 38713,
1347 38721, 38729, 38737, 38745, 38753, 38760, 38768, 38775, 38783, 38790, 38797, 38805, 38812, 38819, 38826, 38833],
1348 [38840, 38854, 38867, 38881, 38894, 38907, 38920, 38932, 38945, 38957, 38969, 38981, 38993, 39005, 39016, 39027,
1349 39039, 39050, 39061, 39071, 39082, 39092, 39103, 39113, 39123, 39133, 39143, 39153, 39163, 39172, 39182, 39191,
1350 39201, 39210, 39219, 39228, 39237, 39246, 39255, 39263, 39272, 39280, 39289, 39297, 39305, 39314, 39322, 39330,
1351 39338, 39346, 39354, 39361, 39369, 39377, 39384, 39392, 39399, 39407, 39414, 39421, 39428, 39436, 39443, 39450],
1354 /// Approximate `log10(numerator / denominator) * 2048` using a look-up table.
1356 pub fn negative_log10_times_2048(numerator: u64, denominator: u64) -> u64 {
1357 // Multiply the -1 through to avoid needing to use signed numbers.
1358 (log10_times_2048(denominator) - log10_times_2048(numerator)) as u64
1362 fn log10_times_2048(x: u64) -> u16 {
1363 debug_assert_ne!(x, 0);
1364 let most_significant_bit = HIGHEST_BIT - x.leading_zeros();
1365 let lower_bits = (x >> most_significant_bit.saturating_sub(LOWER_BITS)) & LOWER_BITMASK;
1366 LOG10_TIMES_2048[most_significant_bit as usize][lower_bits as usize]
1374 fn prints_negative_log10_times_2048_lookup_table() {
1375 for msb in 0..BITS {
1376 for i in 0..LOWER_BITS_BOUND {
1377 let x = ((LOWER_BITS_BOUND + i) << (HIGHEST_BIT - LOWER_BITS)) >> (HIGHEST_BIT - msb);
1378 let log10_times_2048 = ((x as f64).log10() * 2048.0).round() as u16;
1379 assert_eq!(log10_times_2048, LOG10_TIMES_2048[msb as usize][i as usize]);
1381 if i % LOWER_BITS_BOUND == 0 {
1382 print!("\t\t[{}, ", log10_times_2048);
1383 } else if i % LOWER_BITS_BOUND == LOWER_BITS_BOUND - 1 {
1384 println!("{}],", log10_times_2048);
1385 } else if i % (LOWER_BITS_BOUND/4) == LOWER_BITS_BOUND/4 - 1 {
1386 print!("{},\n\t\t\t", log10_times_2048);
1388 print!("{}, ", log10_times_2048);
1396 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Writeable for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1398 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
1399 write_tlv_fields!(w, {
1400 (0, self.channel_liquidities, required),
1406 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time>
1407 ReadableArgs<(ProbabilisticScoringParameters, G, L)> for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
1410 r: &mut R, args: (ProbabilisticScoringParameters, G, L)
1411 ) -> Result<Self, DecodeError> {
1412 let (params, network_graph, logger) = args;
1413 let mut channel_liquidities = HashMap::new();
1414 read_tlv_fields!(r, {
1415 (0, channel_liquidities, required),
1421 channel_liquidities,
1426 impl<T: Time> Writeable for ChannelLiquidity<T> {
1428 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
1429 let duration_since_epoch = T::duration_since_epoch() - self.last_updated.elapsed();
1430 write_tlv_fields!(w, {
1431 (0, self.min_liquidity_offset_msat, required),
1432 (1, Some(self.min_liquidity_offset_history), option),
1433 (2, self.max_liquidity_offset_msat, required),
1434 (3, Some(self.max_liquidity_offset_history), option),
1435 (4, duration_since_epoch, required),
1441 impl<T: Time> Readable for ChannelLiquidity<T> {
1443 fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
1444 let mut min_liquidity_offset_msat = 0;
1445 let mut max_liquidity_offset_msat = 0;
1446 let mut min_liquidity_offset_history = Some(HistoricalBucketRangeTracker::new());
1447 let mut max_liquidity_offset_history = Some(HistoricalBucketRangeTracker::new());
1448 let mut duration_since_epoch = Duration::from_secs(0);
1449 read_tlv_fields!(r, {
1450 (0, min_liquidity_offset_msat, required),
1451 (1, min_liquidity_offset_history, option),
1452 (2, max_liquidity_offset_msat, required),
1453 (3, max_liquidity_offset_history, option),
1454 (4, duration_since_epoch, required),
1456 // On rust prior to 1.60 `Instant::duration_since` will panic if time goes backwards.
1457 // We write `last_updated` as wallclock time even though its ultimately an `Instant` (which
1458 // is a time from a monotonic clock usually represented as an offset against boot time).
1459 // Thus, we have to construct an `Instant` by subtracting the difference in wallclock time
1460 // from the one that was written. However, because `Instant` can panic if we construct one
1461 // in the future, we must handle wallclock time jumping backwards, which we do by simply
1462 // using `Instant::now()` in that case.
1463 let wall_clock_now = T::duration_since_epoch();
1465 let last_updated = if wall_clock_now > duration_since_epoch {
1466 now - (wall_clock_now - duration_since_epoch)
1469 min_liquidity_offset_msat,
1470 max_liquidity_offset_msat,
1471 min_liquidity_offset_history: min_liquidity_offset_history.unwrap(),
1472 max_liquidity_offset_history: max_liquidity_offset_history.unwrap(),
1480 use super::{ChannelLiquidity, HistoricalBucketRangeTracker, ProbabilisticScoringParameters, ProbabilisticScorerUsingTime};
1481 use util::time::Time;
1482 use util::time::tests::SinceEpoch;
1484 use ln::features::{ChannelFeatures, NodeFeatures};
1485 use ln::msgs::{ChannelAnnouncement, ChannelUpdate, UnsignedChannelAnnouncement, UnsignedChannelUpdate};
1486 use routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId};
1487 use routing::router::RouteHop;
1488 use routing::scoring::{ChannelUsage, Score};
1489 use util::ser::{ReadableArgs, Writeable};
1490 use util::test_utils::TestLogger;
1492 use bitcoin::blockdata::constants::genesis_block;
1493 use bitcoin::hashes::Hash;
1494 use bitcoin::hashes::sha256d::Hash as Sha256dHash;
1495 use bitcoin::network::constants::Network;
1496 use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey};
1497 use core::time::Duration;
1500 fn source_privkey() -> SecretKey {
1501 SecretKey::from_slice(&[42; 32]).unwrap()
1504 fn target_privkey() -> SecretKey {
1505 SecretKey::from_slice(&[43; 32]).unwrap()
1508 fn source_pubkey() -> PublicKey {
1509 let secp_ctx = Secp256k1::new();
1510 PublicKey::from_secret_key(&secp_ctx, &source_privkey())
1513 fn target_pubkey() -> PublicKey {
1514 let secp_ctx = Secp256k1::new();
1515 PublicKey::from_secret_key(&secp_ctx, &target_privkey())
1518 fn source_node_id() -> NodeId {
1519 NodeId::from_pubkey(&source_pubkey())
1522 fn target_node_id() -> NodeId {
1523 NodeId::from_pubkey(&target_pubkey())
1526 // `ProbabilisticScorer` tests
1528 /// A probabilistic scorer for testing with time that can be manually advanced.
1529 type ProbabilisticScorer<'a> = ProbabilisticScorerUsingTime::<&'a NetworkGraph<&'a TestLogger>, &'a TestLogger, SinceEpoch>;
1531 fn sender_privkey() -> SecretKey {
1532 SecretKey::from_slice(&[41; 32]).unwrap()
1535 fn recipient_privkey() -> SecretKey {
1536 SecretKey::from_slice(&[45; 32]).unwrap()
1539 fn sender_pubkey() -> PublicKey {
1540 let secp_ctx = Secp256k1::new();
1541 PublicKey::from_secret_key(&secp_ctx, &sender_privkey())
1544 fn recipient_pubkey() -> PublicKey {
1545 let secp_ctx = Secp256k1::new();
1546 PublicKey::from_secret_key(&secp_ctx, &recipient_privkey())
1549 fn sender_node_id() -> NodeId {
1550 NodeId::from_pubkey(&sender_pubkey())
1553 fn recipient_node_id() -> NodeId {
1554 NodeId::from_pubkey(&recipient_pubkey())
1557 fn network_graph(logger: &TestLogger) -> NetworkGraph<&TestLogger> {
1558 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1559 let mut network_graph = NetworkGraph::new(genesis_hash, logger);
1560 add_channel(&mut network_graph, 42, source_privkey(), target_privkey());
1561 add_channel(&mut network_graph, 43, target_privkey(), recipient_privkey());
1567 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_1_key: SecretKey,
1568 node_2_key: SecretKey
1570 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1571 let node_1_secret = &SecretKey::from_slice(&[39; 32]).unwrap();
1572 let node_2_secret = &SecretKey::from_slice(&[40; 32]).unwrap();
1573 let secp_ctx = Secp256k1::new();
1574 let unsigned_announcement = UnsignedChannelAnnouncement {
1575 features: ChannelFeatures::known(),
1576 chain_hash: genesis_hash,
1578 node_id_1: PublicKey::from_secret_key(&secp_ctx, &node_1_key),
1579 node_id_2: PublicKey::from_secret_key(&secp_ctx, &node_2_key),
1580 bitcoin_key_1: PublicKey::from_secret_key(&secp_ctx, &node_1_secret),
1581 bitcoin_key_2: PublicKey::from_secret_key(&secp_ctx, &node_2_secret),
1582 excess_data: Vec::new(),
1584 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
1585 let signed_announcement = ChannelAnnouncement {
1586 node_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_key),
1587 node_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_key),
1588 bitcoin_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_secret),
1589 bitcoin_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_secret),
1590 contents: unsigned_announcement,
1592 let chain_source: Option<&::util::test_utils::TestChainSource> = None;
1593 network_graph.update_channel_from_announcement(
1594 &signed_announcement, &chain_source).unwrap();
1595 update_channel(network_graph, short_channel_id, node_1_key, 0);
1596 update_channel(network_graph, short_channel_id, node_2_key, 1);
1600 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_key: SecretKey,
1603 let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
1604 let secp_ctx = Secp256k1::new();
1605 let unsigned_update = UnsignedChannelUpdate {
1606 chain_hash: genesis_hash,
1610 cltv_expiry_delta: 18,
1611 htlc_minimum_msat: 0,
1612 htlc_maximum_msat: 1_000,
1614 fee_proportional_millionths: 0,
1615 excess_data: Vec::new(),
1617 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_update.encode()[..])[..]);
1618 let signed_update = ChannelUpdate {
1619 signature: secp_ctx.sign_ecdsa(&msghash, &node_key),
1620 contents: unsigned_update,
1622 network_graph.update_channel(&signed_update).unwrap();
1625 fn payment_path_for_amount(amount_msat: u64) -> Vec<RouteHop> {
1628 pubkey: source_pubkey(),
1629 node_features: NodeFeatures::known(),
1630 short_channel_id: 41,
1631 channel_features: ChannelFeatures::known(),
1633 cltv_expiry_delta: 18,
1636 pubkey: target_pubkey(),
1637 node_features: NodeFeatures::known(),
1638 short_channel_id: 42,
1639 channel_features: ChannelFeatures::known(),
1641 cltv_expiry_delta: 18,
1644 pubkey: recipient_pubkey(),
1645 node_features: NodeFeatures::known(),
1646 short_channel_id: 43,
1647 channel_features: ChannelFeatures::known(),
1648 fee_msat: amount_msat,
1649 cltv_expiry_delta: 18,
1655 fn liquidity_bounds_directed_from_lowest_node_id() {
1656 let logger = TestLogger::new();
1657 let last_updated = SinceEpoch::now();
1658 let network_graph = network_graph(&logger);
1659 let params = ProbabilisticScoringParameters::default();
1660 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1663 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated,
1664 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1665 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1669 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated,
1670 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1671 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1673 let source = source_node_id();
1674 let target = target_node_id();
1675 let recipient = recipient_node_id();
1676 assert!(source > target);
1677 assert!(target < recipient);
1679 // Update minimum liquidity.
1681 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
1682 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1683 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1684 assert_eq!(liquidity.min_liquidity_msat(), 100);
1685 assert_eq!(liquidity.max_liquidity_msat(), 300);
1687 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1688 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1689 assert_eq!(liquidity.min_liquidity_msat(), 700);
1690 assert_eq!(liquidity.max_liquidity_msat(), 900);
1692 scorer.channel_liquidities.get_mut(&42).unwrap()
1693 .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
1694 .set_min_liquidity_msat(200);
1696 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1697 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1698 assert_eq!(liquidity.min_liquidity_msat(), 200);
1699 assert_eq!(liquidity.max_liquidity_msat(), 300);
1701 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1702 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1703 assert_eq!(liquidity.min_liquidity_msat(), 700);
1704 assert_eq!(liquidity.max_liquidity_msat(), 800);
1706 // Update maximum liquidity.
1708 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1709 .as_directed(&target, &recipient, 1_000, liquidity_offset_half_life);
1710 assert_eq!(liquidity.min_liquidity_msat(), 700);
1711 assert_eq!(liquidity.max_liquidity_msat(), 900);
1713 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1714 .as_directed(&recipient, &target, 1_000, liquidity_offset_half_life);
1715 assert_eq!(liquidity.min_liquidity_msat(), 100);
1716 assert_eq!(liquidity.max_liquidity_msat(), 300);
1718 scorer.channel_liquidities.get_mut(&43).unwrap()
1719 .as_directed_mut(&target, &recipient, 1_000, liquidity_offset_half_life)
1720 .set_max_liquidity_msat(200);
1722 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1723 .as_directed(&target, &recipient, 1_000, liquidity_offset_half_life);
1724 assert_eq!(liquidity.min_liquidity_msat(), 0);
1725 assert_eq!(liquidity.max_liquidity_msat(), 200);
1727 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
1728 .as_directed(&recipient, &target, 1_000, liquidity_offset_half_life);
1729 assert_eq!(liquidity.min_liquidity_msat(), 800);
1730 assert_eq!(liquidity.max_liquidity_msat(), 1000);
1734 fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() {
1735 let logger = TestLogger::new();
1736 let last_updated = SinceEpoch::now();
1737 let network_graph = network_graph(&logger);
1738 let params = ProbabilisticScoringParameters::default();
1739 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1742 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated,
1743 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1744 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1746 let source = source_node_id();
1747 let target = target_node_id();
1748 assert!(source > target);
1750 // Check initial bounds.
1751 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
1752 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1753 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1754 assert_eq!(liquidity.min_liquidity_msat(), 400);
1755 assert_eq!(liquidity.max_liquidity_msat(), 800);
1757 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1758 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1759 assert_eq!(liquidity.min_liquidity_msat(), 200);
1760 assert_eq!(liquidity.max_liquidity_msat(), 600);
1762 // Reset from source to target.
1763 scorer.channel_liquidities.get_mut(&42).unwrap()
1764 .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
1765 .set_min_liquidity_msat(900);
1767 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1768 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1769 assert_eq!(liquidity.min_liquidity_msat(), 900);
1770 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1772 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1773 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1774 assert_eq!(liquidity.min_liquidity_msat(), 0);
1775 assert_eq!(liquidity.max_liquidity_msat(), 100);
1777 // Reset from target to source.
1778 scorer.channel_liquidities.get_mut(&42).unwrap()
1779 .as_directed_mut(&target, &source, 1_000, liquidity_offset_half_life)
1780 .set_min_liquidity_msat(400);
1782 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1783 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1784 assert_eq!(liquidity.min_liquidity_msat(), 0);
1785 assert_eq!(liquidity.max_liquidity_msat(), 600);
1787 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1788 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1789 assert_eq!(liquidity.min_liquidity_msat(), 400);
1790 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1794 fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() {
1795 let logger = TestLogger::new();
1796 let last_updated = SinceEpoch::now();
1797 let network_graph = network_graph(&logger);
1798 let params = ProbabilisticScoringParameters::default();
1799 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1802 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated,
1803 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1804 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1806 let source = source_node_id();
1807 let target = target_node_id();
1808 assert!(source > target);
1810 // Check initial bounds.
1811 let liquidity_offset_half_life = scorer.params.liquidity_offset_half_life;
1812 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1813 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1814 assert_eq!(liquidity.min_liquidity_msat(), 400);
1815 assert_eq!(liquidity.max_liquidity_msat(), 800);
1817 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1818 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1819 assert_eq!(liquidity.min_liquidity_msat(), 200);
1820 assert_eq!(liquidity.max_liquidity_msat(), 600);
1822 // Reset from source to target.
1823 scorer.channel_liquidities.get_mut(&42).unwrap()
1824 .as_directed_mut(&source, &target, 1_000, liquidity_offset_half_life)
1825 .set_max_liquidity_msat(300);
1827 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1828 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1829 assert_eq!(liquidity.min_liquidity_msat(), 0);
1830 assert_eq!(liquidity.max_liquidity_msat(), 300);
1832 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1833 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1834 assert_eq!(liquidity.min_liquidity_msat(), 700);
1835 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1837 // Reset from target to source.
1838 scorer.channel_liquidities.get_mut(&42).unwrap()
1839 .as_directed_mut(&target, &source, 1_000, liquidity_offset_half_life)
1840 .set_max_liquidity_msat(600);
1842 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1843 .as_directed(&source, &target, 1_000, liquidity_offset_half_life);
1844 assert_eq!(liquidity.min_liquidity_msat(), 400);
1845 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
1847 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
1848 .as_directed(&target, &source, 1_000, liquidity_offset_half_life);
1849 assert_eq!(liquidity.min_liquidity_msat(), 0);
1850 assert_eq!(liquidity.max_liquidity_msat(), 600);
1854 fn increased_penalty_nearing_liquidity_upper_bound() {
1855 let logger = TestLogger::new();
1856 let network_graph = network_graph(&logger);
1857 let params = ProbabilisticScoringParameters {
1858 liquidity_penalty_multiplier_msat: 1_000,
1859 ..ProbabilisticScoringParameters::zero_penalty()
1861 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1862 let source = source_node_id();
1863 let target = target_node_id();
1865 let usage = ChannelUsage {
1867 inflight_htlc_msat: 0,
1868 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(1_000) },
1870 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1871 let usage = ChannelUsage { amount_msat: 10_240, ..usage };
1872 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1873 let usage = ChannelUsage { amount_msat: 102_400, ..usage };
1874 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 47);
1875 let usage = ChannelUsage { amount_msat: 1_023_999, ..usage };
1876 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
1878 let usage = ChannelUsage {
1880 inflight_htlc_msat: 0,
1881 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_000) },
1883 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 58);
1884 let usage = ChannelUsage { amount_msat: 256, ..usage };
1885 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
1886 let usage = ChannelUsage { amount_msat: 374, ..usage };
1887 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 198);
1888 let usage = ChannelUsage { amount_msat: 512, ..usage };
1889 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1890 let usage = ChannelUsage { amount_msat: 640, ..usage };
1891 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 425);
1892 let usage = ChannelUsage { amount_msat: 768, ..usage };
1893 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 602);
1894 let usage = ChannelUsage { amount_msat: 896, ..usage };
1895 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 902);
1899 fn constant_penalty_outside_liquidity_bounds() {
1900 let logger = TestLogger::new();
1901 let last_updated = SinceEpoch::now();
1902 let network_graph = network_graph(&logger);
1903 let params = ProbabilisticScoringParameters {
1904 liquidity_penalty_multiplier_msat: 1_000,
1905 considered_impossible_penalty_msat: u64::max_value(),
1906 ..ProbabilisticScoringParameters::zero_penalty()
1908 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
1911 min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40, last_updated,
1912 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1913 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1915 let source = source_node_id();
1916 let target = target_node_id();
1918 let usage = ChannelUsage {
1920 inflight_htlc_msat: 0,
1921 effective_capacity: EffectiveCapacity::Total { capacity_msat: 100, htlc_maximum_msat: Some(1_000) },
1923 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1924 let usage = ChannelUsage { amount_msat: 50, ..usage };
1925 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1926 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1927 let usage = ChannelUsage { amount_msat: 61, ..usage };
1928 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
1932 fn does_not_further_penalize_own_channel() {
1933 let logger = TestLogger::new();
1934 let network_graph = network_graph(&logger);
1935 let params = ProbabilisticScoringParameters {
1936 liquidity_penalty_multiplier_msat: 1_000,
1937 ..ProbabilisticScoringParameters::zero_penalty()
1939 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1940 let sender = sender_node_id();
1941 let source = source_node_id();
1942 let usage = ChannelUsage {
1944 inflight_htlc_msat: 0,
1945 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
1947 let failed_path = payment_path_for_amount(500);
1948 let successful_path = payment_path_for_amount(200);
1950 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 301);
1952 scorer.payment_path_failed(&failed_path.iter().collect::<Vec<_>>(), 41);
1953 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 301);
1955 scorer.payment_path_successful(&successful_path.iter().collect::<Vec<_>>());
1956 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 301);
1960 fn sets_liquidity_lower_bound_on_downstream_failure() {
1961 let logger = TestLogger::new();
1962 let network_graph = network_graph(&logger);
1963 let params = ProbabilisticScoringParameters {
1964 liquidity_penalty_multiplier_msat: 1_000,
1965 ..ProbabilisticScoringParameters::zero_penalty()
1967 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
1968 let source = source_node_id();
1969 let target = target_node_id();
1970 let path = payment_path_for_amount(500);
1972 let usage = ChannelUsage {
1974 inflight_htlc_msat: 0,
1975 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
1977 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 128);
1978 let usage = ChannelUsage { amount_msat: 500, ..usage };
1979 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 301);
1980 let usage = ChannelUsage { amount_msat: 750, ..usage };
1981 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 602);
1983 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 43);
1985 let usage = ChannelUsage { amount_msat: 250, ..usage };
1986 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1987 let usage = ChannelUsage { amount_msat: 500, ..usage };
1988 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
1989 let usage = ChannelUsage { amount_msat: 750, ..usage };
1990 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
1994 fn sets_liquidity_upper_bound_on_failure() {
1995 let logger = TestLogger::new();
1996 let network_graph = network_graph(&logger);
1997 let params = ProbabilisticScoringParameters {
1998 liquidity_penalty_multiplier_msat: 1_000,
1999 considered_impossible_penalty_msat: u64::max_value(),
2000 ..ProbabilisticScoringParameters::zero_penalty()
2002 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2003 let source = source_node_id();
2004 let target = target_node_id();
2005 let path = payment_path_for_amount(500);
2007 let usage = ChannelUsage {
2009 inflight_htlc_msat: 0,
2010 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
2012 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 128);
2013 let usage = ChannelUsage { amount_msat: 500, ..usage };
2014 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 301);
2015 let usage = ChannelUsage { amount_msat: 750, ..usage };
2016 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 602);
2018 scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 42);
2020 let usage = ChannelUsage { amount_msat: 250, ..usage };
2021 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2022 let usage = ChannelUsage { amount_msat: 500, ..usage };
2023 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2024 let usage = ChannelUsage { amount_msat: 750, ..usage };
2025 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2029 fn reduces_liquidity_upper_bound_along_path_on_success() {
2030 let logger = TestLogger::new();
2031 let network_graph = network_graph(&logger);
2032 let params = ProbabilisticScoringParameters {
2033 liquidity_penalty_multiplier_msat: 1_000,
2034 ..ProbabilisticScoringParameters::zero_penalty()
2036 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2037 let sender = sender_node_id();
2038 let source = source_node_id();
2039 let target = target_node_id();
2040 let recipient = recipient_node_id();
2041 let usage = ChannelUsage {
2043 inflight_htlc_msat: 0,
2044 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
2046 let path = payment_path_for_amount(500);
2048 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 128);
2049 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 128);
2050 assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage), 128);
2052 scorer.payment_path_successful(&path.iter().collect::<Vec<_>>());
2054 assert_eq!(scorer.channel_penalty_msat(41, &sender, &source, usage), 128);
2055 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2056 assert_eq!(scorer.channel_penalty_msat(43, &target, &recipient, usage), 300);
2060 fn decays_liquidity_bounds_over_time() {
2061 let logger = TestLogger::new();
2062 let network_graph = network_graph(&logger);
2063 let params = ProbabilisticScoringParameters {
2064 liquidity_penalty_multiplier_msat: 1_000,
2065 liquidity_offset_half_life: Duration::from_secs(10),
2066 considered_impossible_penalty_msat: u64::max_value(),
2067 ..ProbabilisticScoringParameters::zero_penalty()
2069 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2070 let source = source_node_id();
2071 let target = target_node_id();
2073 let usage = ChannelUsage {
2075 inflight_htlc_msat: 0,
2076 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_024) },
2078 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2079 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
2080 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
2082 scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::<Vec<_>>(), 42);
2083 scorer.payment_path_failed(&payment_path_for_amount(128).iter().collect::<Vec<_>>(), 43);
2085 let usage = ChannelUsage { amount_msat: 128, ..usage };
2086 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2087 let usage = ChannelUsage { amount_msat: 256, ..usage };
2088 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 93);
2089 let usage = ChannelUsage { amount_msat: 768, ..usage };
2090 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1_479);
2091 let usage = ChannelUsage { amount_msat: 896, ..usage };
2092 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2094 SinceEpoch::advance(Duration::from_secs(9));
2095 let usage = ChannelUsage { amount_msat: 128, ..usage };
2096 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2097 let usage = ChannelUsage { amount_msat: 256, ..usage };
2098 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 93);
2099 let usage = ChannelUsage { amount_msat: 768, ..usage };
2100 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1_479);
2101 let usage = ChannelUsage { amount_msat: 896, ..usage };
2102 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2104 SinceEpoch::advance(Duration::from_secs(1));
2105 let usage = ChannelUsage { amount_msat: 64, ..usage };
2106 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2107 let usage = ChannelUsage { amount_msat: 128, ..usage };
2108 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 34);
2109 let usage = ChannelUsage { amount_msat: 896, ..usage };
2110 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1_970);
2111 let usage = ChannelUsage { amount_msat: 960, ..usage };
2112 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2114 // Fully decay liquidity lower bound.
2115 SinceEpoch::advance(Duration::from_secs(10 * 7));
2116 let usage = ChannelUsage { amount_msat: 0, ..usage };
2117 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2118 let usage = ChannelUsage { amount_msat: 1, ..usage };
2119 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2120 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
2121 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2_000);
2122 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2123 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2125 // Fully decay liquidity upper bound.
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());
2132 SinceEpoch::advance(Duration::from_secs(10));
2133 let usage = ChannelUsage { amount_msat: 0, ..usage };
2134 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2135 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2136 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2140 fn decays_liquidity_bounds_without_shift_overflow() {
2141 let logger = TestLogger::new();
2142 let network_graph = network_graph(&logger);
2143 let params = ProbabilisticScoringParameters {
2144 liquidity_penalty_multiplier_msat: 1_000,
2145 liquidity_offset_half_life: Duration::from_secs(10),
2146 ..ProbabilisticScoringParameters::zero_penalty()
2148 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2149 let source = source_node_id();
2150 let target = target_node_id();
2151 let usage = ChannelUsage {
2153 inflight_htlc_msat: 0,
2154 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_000) },
2156 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
2158 scorer.payment_path_failed(&payment_path_for_amount(512).iter().collect::<Vec<_>>(), 42);
2159 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 281);
2161 // An unchecked right shift 64 bits or more in DirectedChannelLiquidity::decayed_offset_msat
2162 // would cause an overflow.
2163 SinceEpoch::advance(Duration::from_secs(10 * 64));
2164 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
2166 SinceEpoch::advance(Duration::from_secs(10));
2167 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 125);
2171 fn restricts_liquidity_bounds_after_decay() {
2172 let logger = TestLogger::new();
2173 let network_graph = network_graph(&logger);
2174 let params = ProbabilisticScoringParameters {
2175 liquidity_penalty_multiplier_msat: 1_000,
2176 liquidity_offset_half_life: Duration::from_secs(10),
2177 ..ProbabilisticScoringParameters::zero_penalty()
2179 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2180 let source = source_node_id();
2181 let target = target_node_id();
2182 let usage = ChannelUsage {
2184 inflight_htlc_msat: 0,
2185 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_000) },
2188 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2190 // More knowledge gives higher confidence (256, 768), meaning a lower penalty.
2191 scorer.payment_path_failed(&payment_path_for_amount(768).iter().collect::<Vec<_>>(), 42);
2192 scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::<Vec<_>>(), 43);
2193 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 281);
2195 // Decaying knowledge gives less confidence (128, 896), meaning a higher penalty.
2196 SinceEpoch::advance(Duration::from_secs(10));
2197 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 291);
2199 // Reducing the upper bound gives more confidence (128, 832) that the payment amount (512)
2200 // is closer to the upper bound, meaning a higher penalty.
2201 scorer.payment_path_successful(&payment_path_for_amount(64).iter().collect::<Vec<_>>());
2202 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 331);
2204 // Increasing the lower bound gives more confidence (256, 832) that the payment amount (512)
2205 // is closer to the lower bound, meaning a lower penalty.
2206 scorer.payment_path_failed(&payment_path_for_amount(256).iter().collect::<Vec<_>>(), 43);
2207 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 245);
2209 // Further decaying affects the lower bound more than the upper bound (128, 928).
2210 SinceEpoch::advance(Duration::from_secs(10));
2211 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 280);
2215 fn restores_persisted_liquidity_bounds() {
2216 let logger = TestLogger::new();
2217 let network_graph = network_graph(&logger);
2218 let params = ProbabilisticScoringParameters {
2219 liquidity_penalty_multiplier_msat: 1_000,
2220 liquidity_offset_half_life: Duration::from_secs(10),
2221 considered_impossible_penalty_msat: u64::max_value(),
2222 ..ProbabilisticScoringParameters::zero_penalty()
2224 let mut scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger);
2225 let source = source_node_id();
2226 let target = target_node_id();
2227 let usage = ChannelUsage {
2229 inflight_htlc_msat: 0,
2230 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
2233 scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
2234 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2236 SinceEpoch::advance(Duration::from_secs(10));
2237 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 473);
2239 scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::<Vec<_>>(), 43);
2240 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2242 let mut serialized_scorer = Vec::new();
2243 scorer.write(&mut serialized_scorer).unwrap();
2245 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
2246 let deserialized_scorer =
2247 <ProbabilisticScorer>::read(&mut serialized_scorer, (params, &network_graph, &logger)).unwrap();
2248 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2252 fn decays_persisted_liquidity_bounds() {
2253 let logger = TestLogger::new();
2254 let network_graph = network_graph(&logger);
2255 let params = ProbabilisticScoringParameters {
2256 liquidity_penalty_multiplier_msat: 1_000,
2257 liquidity_offset_half_life: Duration::from_secs(10),
2258 considered_impossible_penalty_msat: u64::max_value(),
2259 ..ProbabilisticScoringParameters::zero_penalty()
2261 let mut scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger);
2262 let source = source_node_id();
2263 let target = target_node_id();
2264 let usage = ChannelUsage {
2266 inflight_htlc_msat: 0,
2267 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
2270 scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
2271 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2273 let mut serialized_scorer = Vec::new();
2274 scorer.write(&mut serialized_scorer).unwrap();
2276 SinceEpoch::advance(Duration::from_secs(10));
2278 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
2279 let deserialized_scorer =
2280 <ProbabilisticScorer>::read(&mut serialized_scorer, (params, &network_graph, &logger)).unwrap();
2281 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage), 473);
2283 scorer.payment_path_failed(&payment_path_for_amount(250).iter().collect::<Vec<_>>(), 43);
2284 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2286 SinceEpoch::advance(Duration::from_secs(10));
2287 assert_eq!(deserialized_scorer.channel_penalty_msat(42, &source, &target, usage), 365);
2291 fn scores_realistic_payments() {
2292 // Shows the scores of "realistic" sends of 100k sats over channels of 1-10m sats (with a
2293 // 50k sat reserve).
2294 let logger = TestLogger::new();
2295 let network_graph = network_graph(&logger);
2296 let params = ProbabilisticScoringParameters::default();
2297 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2298 let source = source_node_id();
2299 let target = target_node_id();
2301 let usage = ChannelUsage {
2302 amount_msat: 100_000_000,
2303 inflight_htlc_msat: 0,
2304 effective_capacity: EffectiveCapacity::Total { capacity_msat: 950_000_000, htlc_maximum_msat: Some(1_000) },
2306 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 4375);
2307 let usage = ChannelUsage {
2308 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2310 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2739);
2311 let usage = ChannelUsage {
2312 effective_capacity: EffectiveCapacity::Total { capacity_msat: 2_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2314 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2236);
2315 let usage = ChannelUsage {
2316 effective_capacity: EffectiveCapacity::Total { capacity_msat: 3_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2318 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1983);
2319 let usage = ChannelUsage {
2320 effective_capacity: EffectiveCapacity::Total { capacity_msat: 4_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2322 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1637);
2323 let usage = ChannelUsage {
2324 effective_capacity: EffectiveCapacity::Total { capacity_msat: 5_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2326 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1606);
2327 let usage = ChannelUsage {
2328 effective_capacity: EffectiveCapacity::Total { capacity_msat: 6_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2330 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1331);
2331 let usage = ChannelUsage {
2332 effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_450_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2334 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1387);
2335 let usage = ChannelUsage {
2336 effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2338 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1379);
2339 let usage = ChannelUsage {
2340 effective_capacity: EffectiveCapacity::Total { capacity_msat: 8_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2342 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1363);
2343 let usage = ChannelUsage {
2344 effective_capacity: EffectiveCapacity::Total { capacity_msat: 9_950_000_000, htlc_maximum_msat: Some(1_000) }, ..usage
2346 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 1355);
2350 fn adds_base_penalty_to_liquidity_penalty() {
2351 let logger = TestLogger::new();
2352 let network_graph = network_graph(&logger);
2353 let source = source_node_id();
2354 let target = target_node_id();
2355 let usage = ChannelUsage {
2357 inflight_htlc_msat: 0,
2358 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_000) },
2361 let params = ProbabilisticScoringParameters {
2362 liquidity_penalty_multiplier_msat: 1_000,
2363 ..ProbabilisticScoringParameters::zero_penalty()
2365 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2366 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 58);
2368 let params = ProbabilisticScoringParameters {
2369 base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000,
2370 anti_probing_penalty_msat: 0, ..ProbabilisticScoringParameters::zero_penalty()
2372 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2373 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 558);
2375 let params = ProbabilisticScoringParameters {
2376 base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000,
2377 base_penalty_amount_multiplier_msat: (1 << 30),
2378 anti_probing_penalty_msat: 0, ..ProbabilisticScoringParameters::zero_penalty()
2381 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2382 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 558 + 128);
2386 fn adds_amount_penalty_to_liquidity_penalty() {
2387 let logger = TestLogger::new();
2388 let network_graph = network_graph(&logger);
2389 let source = source_node_id();
2390 let target = target_node_id();
2391 let usage = ChannelUsage {
2392 amount_msat: 512_000,
2393 inflight_htlc_msat: 0,
2394 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(1_000) },
2397 let params = ProbabilisticScoringParameters {
2398 liquidity_penalty_multiplier_msat: 1_000,
2399 liquidity_penalty_amount_multiplier_msat: 0,
2400 ..ProbabilisticScoringParameters::zero_penalty()
2402 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2403 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 300);
2405 let params = ProbabilisticScoringParameters {
2406 liquidity_penalty_multiplier_msat: 1_000,
2407 liquidity_penalty_amount_multiplier_msat: 256,
2408 ..ProbabilisticScoringParameters::zero_penalty()
2410 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2411 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 337);
2415 fn calculates_log10_without_overflowing_u64_max_value() {
2416 let logger = TestLogger::new();
2417 let network_graph = network_graph(&logger);
2418 let source = source_node_id();
2419 let target = target_node_id();
2420 let usage = ChannelUsage {
2421 amount_msat: u64::max_value(),
2422 inflight_htlc_msat: 0,
2423 effective_capacity: EffectiveCapacity::Infinite,
2426 let params = ProbabilisticScoringParameters {
2427 liquidity_penalty_multiplier_msat: 40_000,
2428 ..ProbabilisticScoringParameters::zero_penalty()
2430 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2431 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 80_000);
2435 fn accounts_for_inflight_htlc_usage() {
2436 let logger = TestLogger::new();
2437 let network_graph = network_graph(&logger);
2438 let params = ProbabilisticScoringParameters {
2439 considered_impossible_penalty_msat: u64::max_value(),
2440 ..ProbabilisticScoringParameters::zero_penalty()
2442 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2443 let source = source_node_id();
2444 let target = target_node_id();
2446 let usage = ChannelUsage {
2448 inflight_htlc_msat: 0,
2449 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: Some(1_000) },
2451 assert_ne!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2453 let usage = ChannelUsage { inflight_htlc_msat: 251, ..usage };
2454 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2458 fn removes_uncertainity_when_exact_liquidity_known() {
2459 let logger = TestLogger::new();
2460 let network_graph = network_graph(&logger);
2461 let params = ProbabilisticScoringParameters::default();
2462 let scorer = ProbabilisticScorer::new(params.clone(), &network_graph, &logger);
2463 let source = source_node_id();
2464 let target = target_node_id();
2466 let base_penalty_msat = params.base_penalty_msat;
2467 let usage = ChannelUsage {
2469 inflight_htlc_msat: 0,
2470 effective_capacity: EffectiveCapacity::ExactLiquidity { liquidity_msat: 1_000 },
2472 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), base_penalty_msat);
2474 let usage = ChannelUsage { amount_msat: 1_000, ..usage };
2475 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), base_penalty_msat);
2477 let usage = ChannelUsage { amount_msat: 1_001, ..usage };
2478 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), u64::max_value());
2482 fn remembers_historical_failures() {
2483 let logger = TestLogger::new();
2484 let network_graph = network_graph(&logger);
2485 let params = ProbabilisticScoringParameters {
2486 historical_liquidity_penalty_multiplier_msat: 1024,
2487 historical_liquidity_penalty_amount_multiplier_msat: 1024,
2488 ..ProbabilisticScoringParameters::zero_penalty()
2490 let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2491 let source = source_node_id();
2492 let target = target_node_id();
2494 let usage = ChannelUsage {
2496 inflight_htlc_msat: 0,
2497 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: Some(1_024) },
2499 // With no historical data the normal liquidity penalty calculation is used.
2500 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 47);
2502 scorer.payment_path_failed(&payment_path_for_amount(1).iter().collect::<Vec<_>>(), 42);
2503 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 2048);
2505 // Even after we tell the scorer we definitely have enough available liquidity, it will
2506 // still remember that there was some failure in the past, and assign a non-0 penalty.
2507 scorer.payment_path_failed(&payment_path_for_amount(1000).iter().collect::<Vec<_>>(), 43);
2508 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 198);
2512 fn adds_anti_probing_penalty() {
2513 let logger = TestLogger::new();
2514 let network_graph = network_graph(&logger);
2515 let source = source_node_id();
2516 let target = target_node_id();
2517 let params = ProbabilisticScoringParameters {
2518 anti_probing_penalty_msat: 500,
2519 ..ProbabilisticScoringParameters::zero_penalty()
2521 let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
2523 // Check we receive no penalty for a low htlc_maximum_msat.
2524 let usage = ChannelUsage {
2525 amount_msat: 512_000,
2526 inflight_htlc_msat: 0,
2527 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(1_000) },
2529 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);
2531 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity.
2532 let usage = ChannelUsage {
2533 amount_msat: 512_000,
2534 inflight_htlc_msat: 0,
2535 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(1_024_000) },
2537 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500);
2539 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity/2.
2540 let usage = ChannelUsage {
2541 amount_msat: 512_000,
2542 inflight_htlc_msat: 0,
2543 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(512_000) },
2545 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 500);
2547 // Check we receive no anti-probing penalty for htlc_maximum_msat == channel_capacity/2 - 1.
2548 let usage = ChannelUsage {
2549 amount_msat: 512_000,
2550 inflight_htlc_msat: 0,
2551 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: Some(511_999) },
2553 assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage), 0);