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 [`ScoreLookUp`] 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, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters};
23 //! # use lightning::sign::KeysManager;
24 //! # use lightning::util::logger::{Logger, Record};
25 //! # use bitcoin::secp256k1::PublicKey;
27 //! # struct FakeLogger {};
28 //! # impl Logger for FakeLogger {
29 //! # fn log(&self, record: Record) { unimplemented!() }
31 //! # fn find_scored_route(payer: PublicKey, route_params: RouteParameters, network_graph: NetworkGraph<&FakeLogger>) {
32 //! # let logger = FakeLogger {};
34 //! // Use the default channel penalties.
35 //! let params = ProbabilisticScoringFeeParameters::default();
36 //! let decay_params = ProbabilisticScoringDecayParameters::default();
37 //! let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
39 //! // Or use custom channel penalties.
40 //! let params = ProbabilisticScoringFeeParameters {
41 //! liquidity_penalty_multiplier_msat: 2 * 1000,
42 //! ..ProbabilisticScoringFeeParameters::default()
44 //! let decay_params = ProbabilisticScoringDecayParameters::default();
45 //! let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
46 //! # let random_seed_bytes = [42u8; 32];
48 //! let route = find_route(&payer, &route_params, &network_graph, None, &logger, &scorer, ¶ms, &random_seed_bytes);
54 //! Persisting when built with feature `no-std` and restoring without it, or vice versa, uses
55 //! different types and thus is undefined.
57 //! [`find_route`]: crate::routing::router::find_route
59 use crate::ln::msgs::DecodeError;
60 use crate::routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId};
61 use crate::routing::router::{Path, CandidateRouteHop};
62 use crate::routing::log_approx;
63 use crate::util::ser::{Readable, ReadableArgs, Writeable, Writer};
64 use crate::util::logger::Logger;
65 use crate::util::simd_f32::FourF32;
67 use crate::prelude::*;
69 use core::cell::{RefCell, RefMut, Ref};
70 use core::convert::TryInto;
71 use core::ops::{Deref, DerefMut};
72 use core::time::Duration;
73 use crate::io::{self, Read};
74 use crate::sync::{Mutex, MutexGuard, RwLock, RwLockReadGuard, RwLockWriteGuard};
76 /// We define Score ever-so-slightly differently based on whether we are being built for C bindings
77 /// or not. For users, `LockableScore` must somehow be writeable to disk. For Rust users, this is
78 /// no problem - you move a `Score` that implements `Writeable` into a `Mutex`, lock it, and now
79 /// you have the original, concrete, `Score` type, which presumably implements `Writeable`.
81 /// For C users, once you've moved the `Score` into a `LockableScore` all you have after locking it
82 /// is an opaque trait object with an opaque pointer with no type info. Users could take the unsafe
83 /// approach of blindly casting that opaque pointer to a concrete type and calling `Writeable` from
84 /// there, but other languages downstream of the C bindings (e.g. Java) can't even do that.
85 /// Instead, we really want `Score` and `LockableScore` to implement `Writeable` directly, which we
86 /// do here by defining `Score` differently for `cfg(c_bindings)`.
87 macro_rules! define_score { ($($supertrait: path)*) => {
88 /// An interface used to score payment channels for path finding.
90 /// `ScoreLookUp` is used to determine the penalty for a given channel.
92 /// Scoring is in terms of fees willing to be paid in order to avoid routing through a channel.
93 pub trait ScoreLookUp {
94 /// A configurable type which should contain various passed-in parameters for configuring the scorer,
95 /// on a per-routefinding-call basis through to the scorer methods,
96 /// which are used to determine the parameters for the suitability of channels for use.
98 /// Returns the fee in msats willing to be paid to avoid routing `send_amt_msat` through the
99 /// given channel in the direction from `source` to `target`.
101 /// The channel's capacity (less any other MPP parts that are also being considered for use in
102 /// the same payment) is given by `capacity_msat`. It may be determined from various sources
103 /// such as a chain data, network gossip, or invoice hints. For invoice hints, a capacity near
104 /// [`u64::max_value`] is given to indicate sufficient capacity for the invoice's full amount.
105 /// Thus, implementations should be overflow-safe.
106 fn channel_penalty_msat(
107 &self, candidate: &CandidateRouteHop, usage: ChannelUsage, score_params: &Self::ScoreParams
111 /// `ScoreUpdate` is used to update the scorer's internal state after a payment attempt.
112 pub trait ScoreUpdate {
113 /// Handles updating channel penalties after failing to route through a channel.
114 fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration);
116 /// Handles updating channel penalties after successfully routing along a path.
117 fn payment_path_successful(&mut self, path: &Path, duration_since_epoch: Duration);
119 /// Handles updating channel penalties after a probe over the given path failed.
120 fn probe_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration);
122 /// Handles updating channel penalties after a probe over the given path succeeded.
123 fn probe_successful(&mut self, path: &Path, duration_since_epoch: Duration);
125 /// Scorers may wish to reduce their certainty of channel liquidity information over time.
126 /// Thus, this method is provided to allow scorers to observe the passage of time - the holder
127 /// of this object should call this method regularly (generally via the
128 /// `lightning-background-processor` crate).
129 fn decay_liquidity_certainty(&mut self, duration_since_epoch: Duration);
132 /// A trait which can both lookup and update routing channel penalty scores.
134 /// This is used in places where both bounds are required and implemented for all types which
135 /// implement [`ScoreLookUp`] and [`ScoreUpdate`].
137 /// Bindings users may need to manually implement this for their custom scoring implementations.
138 pub trait Score : ScoreLookUp + ScoreUpdate $(+ $supertrait)* {}
140 #[cfg(not(c_bindings))]
141 impl<T: ScoreLookUp + ScoreUpdate $(+ $supertrait)*> Score for T {}
143 #[cfg(not(c_bindings))]
144 impl<S: ScoreLookUp, T: Deref<Target=S>> ScoreLookUp for T {
145 type ScoreParams = S::ScoreParams;
146 fn channel_penalty_msat(
147 &self, candidate: &CandidateRouteHop, usage: ChannelUsage, score_params: &Self::ScoreParams
149 self.deref().channel_penalty_msat(candidate, usage, score_params)
153 #[cfg(not(c_bindings))]
154 impl<S: ScoreUpdate, T: DerefMut<Target=S>> ScoreUpdate for T {
155 fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) {
156 self.deref_mut().payment_path_failed(path, short_channel_id, duration_since_epoch)
159 fn payment_path_successful(&mut self, path: &Path, duration_since_epoch: Duration) {
160 self.deref_mut().payment_path_successful(path, duration_since_epoch)
163 fn probe_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) {
164 self.deref_mut().probe_failed(path, short_channel_id, duration_since_epoch)
167 fn probe_successful(&mut self, path: &Path, duration_since_epoch: Duration) {
168 self.deref_mut().probe_successful(path, duration_since_epoch)
171 fn decay_liquidity_certainty(&mut self, duration_since_epoch: Duration) {
172 self.deref_mut().decay_liquidity_certainty(duration_since_epoch)
178 define_score!(Writeable);
180 #[cfg(not(c_bindings))]
183 /// A scorer that is accessed under a lock.
185 /// Needed so that calls to [`ScoreLookUp::channel_penalty_msat`] in [`find_route`] can be made while
186 /// having shared ownership of a scorer but without requiring internal locking in [`ScoreUpdate`]
187 /// implementations. Internal locking would be detrimental to route finding performance and could
188 /// result in [`ScoreLookUp::channel_penalty_msat`] returning a different value for the same channel.
190 /// [`find_route`]: crate::routing::router::find_route
191 pub trait LockableScore<'a> {
192 /// The [`ScoreUpdate`] type.
193 type ScoreUpdate: 'a + ScoreUpdate;
194 /// The [`ScoreLookUp`] type.
195 type ScoreLookUp: 'a + ScoreLookUp;
197 /// The write locked [`ScoreUpdate`] type.
198 type WriteLocked: DerefMut<Target = Self::ScoreUpdate> + Sized;
200 /// The read locked [`ScoreLookUp`] type.
201 type ReadLocked: Deref<Target = Self::ScoreLookUp> + Sized;
203 /// Returns read locked scorer.
204 fn read_lock(&'a self) -> Self::ReadLocked;
206 /// Returns write locked scorer.
207 fn write_lock(&'a self) -> Self::WriteLocked;
210 /// Refers to a scorer that is accessible under lock and also writeable to disk
212 /// We need this trait to be able to pass in a scorer to `lightning-background-processor` that will enable us to
213 /// use the Persister to persist it.
214 pub trait WriteableScore<'a>: LockableScore<'a> + Writeable {}
216 #[cfg(not(c_bindings))]
217 impl<'a, T> WriteableScore<'a> for T where T: LockableScore<'a> + Writeable {}
218 #[cfg(not(c_bindings))]
219 impl<'a, T: Score + 'a> LockableScore<'a> for Mutex<T> {
220 type ScoreUpdate = T;
221 type ScoreLookUp = T;
223 type WriteLocked = MutexGuard<'a, Self::ScoreUpdate>;
224 type ReadLocked = MutexGuard<'a, Self::ScoreLookUp>;
226 fn read_lock(&'a self) -> Self::ReadLocked {
227 Mutex::lock(self).unwrap()
230 fn write_lock(&'a self) -> Self::WriteLocked {
231 Mutex::lock(self).unwrap()
235 #[cfg(not(c_bindings))]
236 impl<'a, T: Score + 'a> LockableScore<'a> for RefCell<T> {
237 type ScoreUpdate = T;
238 type ScoreLookUp = T;
240 type WriteLocked = RefMut<'a, Self::ScoreUpdate>;
241 type ReadLocked = Ref<'a, Self::ScoreLookUp>;
243 fn write_lock(&'a self) -> Self::WriteLocked {
247 fn read_lock(&'a self) -> Self::ReadLocked {
252 #[cfg(not(c_bindings))]
253 impl<'a, T: Score + 'a> LockableScore<'a> for RwLock<T> {
254 type ScoreUpdate = T;
255 type ScoreLookUp = T;
257 type WriteLocked = RwLockWriteGuard<'a, Self::ScoreLookUp>;
258 type ReadLocked = RwLockReadGuard<'a, Self::ScoreUpdate>;
260 fn read_lock(&'a self) -> Self::ReadLocked {
261 RwLock::read(self).unwrap()
264 fn write_lock(&'a self) -> Self::WriteLocked {
265 RwLock::write(self).unwrap()
270 /// A concrete implementation of [`LockableScore`] which supports multi-threading.
271 pub struct MultiThreadedLockableScore<T: Score> {
276 impl<'a, T: Score + 'a> LockableScore<'a> for MultiThreadedLockableScore<T> {
277 type ScoreUpdate = T;
278 type ScoreLookUp = T;
279 type WriteLocked = MultiThreadedScoreLockWrite<'a, Self::ScoreUpdate>;
280 type ReadLocked = MultiThreadedScoreLockRead<'a, Self::ScoreLookUp>;
282 fn read_lock(&'a self) -> Self::ReadLocked {
283 MultiThreadedScoreLockRead(self.score.read().unwrap())
286 fn write_lock(&'a self) -> Self::WriteLocked {
287 MultiThreadedScoreLockWrite(self.score.write().unwrap())
292 impl<T: Score> Writeable for MultiThreadedLockableScore<T> {
293 fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
294 self.score.read().unwrap().write(writer)
299 impl<'a, T: Score + 'a> WriteableScore<'a> for MultiThreadedLockableScore<T> {}
302 impl<T: Score> MultiThreadedLockableScore<T> {
303 /// Creates a new [`MultiThreadedLockableScore`] given an underlying [`Score`].
304 pub fn new(score: T) -> Self {
305 MultiThreadedLockableScore { score: RwLock::new(score) }
310 /// A locked `MultiThreadedLockableScore`.
311 pub struct MultiThreadedScoreLockRead<'a, T: Score>(RwLockReadGuard<'a, T>);
314 /// A locked `MultiThreadedLockableScore`.
315 pub struct MultiThreadedScoreLockWrite<'a, T: Score>(RwLockWriteGuard<'a, T>);
318 impl<'a, T: 'a + Score> Deref for MultiThreadedScoreLockRead<'a, T> {
321 fn deref(&self) -> &Self::Target {
327 impl<'a, T: Score> ScoreLookUp for MultiThreadedScoreLockRead<'a, T> {
328 type ScoreParams = T::ScoreParams;
329 fn channel_penalty_msat(&self, candidate:&CandidateRouteHop, usage: ChannelUsage, score_params: &Self::ScoreParams
331 self.0.channel_penalty_msat(candidate, usage, score_params)
336 impl<'a, T: Score> Writeable for MultiThreadedScoreLockWrite<'a, T> {
337 fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
343 impl<'a, T: 'a + Score> Deref for MultiThreadedScoreLockWrite<'a, T> {
346 fn deref(&self) -> &Self::Target {
352 impl<'a, T: 'a + Score> DerefMut for MultiThreadedScoreLockWrite<'a, T> {
353 fn deref_mut(&mut self) -> &mut Self::Target {
359 impl<'a, T: Score> ScoreUpdate for MultiThreadedScoreLockWrite<'a, T> {
360 fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) {
361 self.0.payment_path_failed(path, short_channel_id, duration_since_epoch)
364 fn payment_path_successful(&mut self, path: &Path, duration_since_epoch: Duration) {
365 self.0.payment_path_successful(path, duration_since_epoch)
368 fn probe_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) {
369 self.0.probe_failed(path, short_channel_id, duration_since_epoch)
372 fn probe_successful(&mut self, path: &Path, duration_since_epoch: Duration) {
373 self.0.probe_successful(path, duration_since_epoch)
376 fn decay_liquidity_certainty(&mut self, duration_since_epoch: Duration) {
377 self.0.decay_liquidity_certainty(duration_since_epoch)
382 /// Proposed use of a channel passed as a parameter to [`ScoreLookUp::channel_penalty_msat`].
383 #[derive(Clone, Copy, Debug, PartialEq)]
384 pub struct ChannelUsage {
385 /// The amount to send through the channel, denominated in millisatoshis.
386 pub amount_msat: u64,
388 /// Total amount, denominated in millisatoshis, already allocated to send through the channel
389 /// as part of a multi-path payment.
390 pub inflight_htlc_msat: u64,
392 /// The effective capacity of the channel.
393 pub effective_capacity: EffectiveCapacity,
397 /// [`ScoreLookUp`] implementation that uses a fixed penalty.
398 pub struct FixedPenaltyScorer {
402 impl FixedPenaltyScorer {
403 /// Creates a new scorer using `penalty_msat`.
404 pub fn with_penalty(penalty_msat: u64) -> Self {
405 Self { penalty_msat }
409 impl ScoreLookUp for FixedPenaltyScorer {
410 type ScoreParams = ();
411 fn channel_penalty_msat(&self, _: &CandidateRouteHop, _: ChannelUsage, _score_params: &Self::ScoreParams) -> u64 {
416 impl ScoreUpdate for FixedPenaltyScorer {
417 fn payment_path_failed(&mut self, _path: &Path, _short_channel_id: u64, _duration_since_epoch: Duration) {}
419 fn payment_path_successful(&mut self, _path: &Path, _duration_since_epoch: Duration) {}
421 fn probe_failed(&mut self, _path: &Path, _short_channel_id: u64, _duration_since_epoch: Duration) {}
423 fn probe_successful(&mut self, _path: &Path, _duration_since_epoch: Duration) {}
425 fn decay_liquidity_certainty(&mut self, _duration_since_epoch: Duration) {}
428 impl Writeable for FixedPenaltyScorer {
430 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
431 write_tlv_fields!(w, {});
436 impl ReadableArgs<u64> for FixedPenaltyScorer {
438 fn read<R: Read>(r: &mut R, penalty_msat: u64) -> Result<Self, DecodeError> {
439 read_tlv_fields!(r, {});
440 Ok(Self { penalty_msat })
444 /// [`ScoreLookUp`] implementation using channel success probability distributions.
446 /// Channels are tracked with upper and lower liquidity bounds - when an HTLC fails at a channel,
447 /// we learn that the upper-bound on the available liquidity is lower than the amount of the HTLC.
448 /// When a payment is forwarded through a channel (but fails later in the route), we learn the
449 /// lower-bound on the channel's available liquidity must be at least the value of the HTLC.
451 /// These bounds are then used to determine a success probability using the formula from
452 /// *Optimally Reliable & Cheap Payment Flows on the Lightning Network* by Rene Pickhardt
453 /// and Stefan Richter [[1]] (i.e. `(upper_bound - payment_amount) / (upper_bound - lower_bound)`).
455 /// This probability is combined with the [`liquidity_penalty_multiplier_msat`] and
456 /// [`liquidity_penalty_amount_multiplier_msat`] parameters to calculate a concrete penalty in
457 /// milli-satoshis. The penalties, when added across all hops, have the property of being linear in
458 /// terms of the entire path's success probability. This allows the router to directly compare
459 /// penalties for different paths. See the documentation of those parameters for the exact formulas.
461 /// The liquidity bounds are decayed by halving them every [`liquidity_offset_half_life`].
463 /// Further, we track the history of our upper and lower liquidity bounds for each channel,
464 /// allowing us to assign a second penalty (using [`historical_liquidity_penalty_multiplier_msat`]
465 /// and [`historical_liquidity_penalty_amount_multiplier_msat`]) based on the same probability
466 /// formula, but using the history of a channel rather than our latest estimates for the liquidity
469 /// [1]: https://arxiv.org/abs/2107.05322
470 /// [`liquidity_penalty_multiplier_msat`]: ProbabilisticScoringFeeParameters::liquidity_penalty_multiplier_msat
471 /// [`liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringFeeParameters::liquidity_penalty_amount_multiplier_msat
472 /// [`liquidity_offset_half_life`]: ProbabilisticScoringDecayParameters::liquidity_offset_half_life
473 /// [`historical_liquidity_penalty_multiplier_msat`]: ProbabilisticScoringFeeParameters::historical_liquidity_penalty_multiplier_msat
474 /// [`historical_liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringFeeParameters::historical_liquidity_penalty_amount_multiplier_msat
475 pub struct ProbabilisticScorer<G: Deref<Target = NetworkGraph<L>>, L: Deref>
476 where L::Target: Logger {
477 decay_params: ProbabilisticScoringDecayParameters,
480 channel_liquidities: HashMap<u64, ChannelLiquidity>,
483 /// Parameters for configuring [`ProbabilisticScorer`].
485 /// Used to configure base, liquidity, and amount penalties, the sum of which comprises the channel
486 /// penalty (i.e., the amount in msats willing to be paid to avoid routing through the channel).
488 /// The penalty applied to any channel by the [`ProbabilisticScorer`] is the sum of each of the
491 pub struct ProbabilisticScoringFeeParameters {
492 /// A fixed penalty in msats to apply to each channel.
494 /// Default value: 500 msat
495 pub base_penalty_msat: u64,
497 /// A multiplier used with the total amount flowing over a channel to calculate a fixed penalty
498 /// applied to each channel, in excess of the [`base_penalty_msat`].
500 /// The purpose of the amount penalty is to avoid having fees dominate the channel cost (i.e.,
501 /// fees plus penalty) for large payments. The penalty is computed as the product of this
502 /// multiplier and `2^30`ths of the total amount flowing over a channel (i.e. the payment
503 /// amount plus the amount of any other HTLCs flowing we sent over the same channel).
505 /// ie `base_penalty_amount_multiplier_msat * amount_msat / 2^30`
507 /// Default value: 8,192 msat
509 /// [`base_penalty_msat`]: Self::base_penalty_msat
510 pub base_penalty_amount_multiplier_msat: u64,
512 /// A multiplier used in conjunction with the negative `log10` of the channel's success
513 /// probability for a payment, as determined by our latest estimates of the channel's
514 /// liquidity, to determine the liquidity penalty.
516 /// The penalty is based in part on the knowledge learned from prior successful and unsuccessful
517 /// payments. This knowledge is decayed over time based on [`liquidity_offset_half_life`]. The
518 /// penalty is effectively limited to `2 * liquidity_penalty_multiplier_msat` (corresponding to
519 /// lower bounding the success probability to `0.01`) when the amount falls within the
520 /// uncertainty bounds of the channel liquidity balance. Amounts above the upper bound will
521 /// result in a `u64::max_value` penalty, however.
523 /// `-log10(success_probability) * liquidity_penalty_multiplier_msat`
525 /// Default value: 30,000 msat
527 /// [`liquidity_offset_half_life`]: ProbabilisticScoringDecayParameters::liquidity_offset_half_life
528 pub liquidity_penalty_multiplier_msat: u64,
530 /// A multiplier used in conjunction with the total amount flowing over a channel and the
531 /// negative `log10` of the channel's success probability for the payment, as determined by our
532 /// latest estimates of the channel's liquidity, to determine the amount penalty.
534 /// The purpose of the amount penalty is to avoid having fees dominate the channel cost (i.e.,
535 /// fees plus penalty) for large payments. The penalty is computed as the product of this
536 /// multiplier and `2^20`ths of the amount flowing over this channel, weighted by the negative
537 /// `log10` of the success probability.
539 /// `-log10(success_probability) * liquidity_penalty_amount_multiplier_msat * amount_msat / 2^20`
541 /// In practice, this means for 0.1 success probability (`-log10(0.1) == 1`) each `2^20`th of
542 /// the amount will result in a penalty of the multiplier. And, as the success probability
543 /// decreases, the negative `log10` weighting will increase dramatically. For higher success
544 /// probabilities, the multiplier will have a decreasing effect as the negative `log10` will
547 /// Default value: 192 msat
548 pub liquidity_penalty_amount_multiplier_msat: u64,
550 /// A multiplier used in conjunction with the negative `log10` of the channel's success
551 /// probability for the payment, as determined based on the history of our estimates of the
552 /// channel's available liquidity, to determine a penalty.
554 /// This penalty is similar to [`liquidity_penalty_multiplier_msat`], however, instead of using
555 /// only our latest estimate for the current liquidity available in the channel, it estimates
556 /// success probability based on the estimated liquidity available in the channel through
557 /// history. Specifically, every time we update our liquidity bounds on a given channel, we
558 /// track which of several buckets those bounds fall into, exponentially decaying the
559 /// probability of each bucket as new samples are added.
561 /// Default value: 10,000 msat
563 /// [`liquidity_penalty_multiplier_msat`]: Self::liquidity_penalty_multiplier_msat
564 pub historical_liquidity_penalty_multiplier_msat: u64,
566 /// A multiplier used in conjunction with the total amount flowing over a channel and the
567 /// negative `log10` of the channel's success probability for the payment, as determined based
568 /// on the history of our estimates of the channel's available liquidity, to determine a
571 /// The purpose of the amount penalty is to avoid having fees dominate the channel cost for
572 /// large payments. The penalty is computed as the product of this multiplier and `2^20`ths
573 /// of the amount flowing over this channel, weighted by the negative `log10` of the success
576 /// This penalty is similar to [`liquidity_penalty_amount_multiplier_msat`], however, instead
577 /// of using only our latest estimate for the current liquidity available in the channel, it
578 /// estimates success probability based on the estimated liquidity available in the channel
579 /// through history. Specifically, every time we update our liquidity bounds on a given
580 /// channel, we track which of several buckets those bounds fall into, exponentially decaying
581 /// the probability of each bucket as new samples are added.
583 /// Default value: 64 msat
585 /// [`liquidity_penalty_amount_multiplier_msat`]: Self::liquidity_penalty_amount_multiplier_msat
586 pub historical_liquidity_penalty_amount_multiplier_msat: u64,
588 /// Manual penalties used for the given nodes. Allows to set a particular penalty for a given
589 /// node. Note that a manual penalty of `u64::max_value()` means the node would not ever be
590 /// considered during path finding.
592 /// This is not exported to bindings users
593 pub manual_node_penalties: HashMap<NodeId, u64>,
595 /// This penalty is applied when `htlc_maximum_msat` is equal to or larger than half of the
596 /// channel's capacity, (ie. htlc_maximum_msat >= 0.5 * channel_capacity) which makes us
597 /// prefer nodes with a smaller `htlc_maximum_msat`. We treat such nodes preferentially
598 /// as this makes balance discovery attacks harder to execute, thereby creating an incentive
599 /// to restrict `htlc_maximum_msat` and improve privacy.
601 /// Default value: 250 msat
602 pub anti_probing_penalty_msat: u64,
604 /// This penalty is applied when the total amount flowing over a channel exceeds our current
605 /// estimate of the channel's available liquidity. The total amount is the amount of the
606 /// current HTLC plus any HTLCs which we've sent over the same channel.
608 /// Note that in this case all other penalties, including the
609 /// [`liquidity_penalty_multiplier_msat`] and [`liquidity_penalty_amount_multiplier_msat`]-based
610 /// penalties, as well as the [`base_penalty_msat`] and the [`anti_probing_penalty_msat`], if
611 /// applicable, are still included in the overall penalty.
613 /// If you wish to avoid creating paths with such channels entirely, setting this to a value of
614 /// `u64::max_value()` will guarantee that.
616 /// Default value: 1_0000_0000_000 msat (1 Bitcoin)
618 /// [`liquidity_penalty_multiplier_msat`]: Self::liquidity_penalty_multiplier_msat
619 /// [`liquidity_penalty_amount_multiplier_msat`]: Self::liquidity_penalty_amount_multiplier_msat
620 /// [`base_penalty_msat`]: Self::base_penalty_msat
621 /// [`anti_probing_penalty_msat`]: Self::anti_probing_penalty_msat
622 pub considered_impossible_penalty_msat: u64,
624 /// In order to calculate most of the scores above, we must first convert a lower and upper
625 /// bound on the available liquidity in a channel into the probability that we think a payment
626 /// will succeed. That probability is derived from a Probability Density Function for where we
627 /// think the liquidity in a channel likely lies, given such bounds.
629 /// If this flag is set, that PDF is simply a constant - we assume that the actual available
630 /// liquidity in a channel is just as likely to be at any point between our lower and upper
633 /// If this flag is *not* set, that PDF is `(x - 0.5*capacity) ^ 2`. That is, we use an
634 /// exponential curve which expects the liquidity of a channel to lie "at the edges". This
635 /// matches experimental results - most routing nodes do not aggressively rebalance their
636 /// channels and flows in the network are often unbalanced, leaving liquidity usually
639 /// Thus, for the "best" routes, leave this flag `false`. However, the flag does imply a number
640 /// of floating-point multiplications in the hottest routing code, which may lead to routing
641 /// performance degradation on some machines.
643 /// Default value: false
644 pub linear_success_probability: bool,
647 impl Default for ProbabilisticScoringFeeParameters {
648 fn default() -> Self {
650 base_penalty_msat: 500,
651 base_penalty_amount_multiplier_msat: 8192,
652 liquidity_penalty_multiplier_msat: 30_000,
653 liquidity_penalty_amount_multiplier_msat: 192,
654 manual_node_penalties: HashMap::new(),
655 anti_probing_penalty_msat: 250,
656 considered_impossible_penalty_msat: 1_0000_0000_000,
657 historical_liquidity_penalty_multiplier_msat: 10_000,
658 historical_liquidity_penalty_amount_multiplier_msat: 64,
659 linear_success_probability: false,
664 impl ProbabilisticScoringFeeParameters {
665 /// Marks the node with the given `node_id` as banned,
666 /// i.e it will be avoided during path finding.
667 pub fn add_banned(&mut self, node_id: &NodeId) {
668 self.manual_node_penalties.insert(*node_id, u64::max_value());
671 /// Marks all nodes in the given list as banned, i.e.,
672 /// they will be avoided during path finding.
673 pub fn add_banned_from_list(&mut self, node_ids: Vec<NodeId>) {
675 self.manual_node_penalties.insert(id, u64::max_value());
679 /// Removes the node with the given `node_id` from the list of nodes to avoid.
680 pub fn remove_banned(&mut self, node_id: &NodeId) {
681 self.manual_node_penalties.remove(node_id);
684 /// Sets a manual penalty for the given node.
685 pub fn set_manual_penalty(&mut self, node_id: &NodeId, penalty: u64) {
686 self.manual_node_penalties.insert(*node_id, penalty);
689 /// Removes the node with the given `node_id` from the list of manual penalties.
690 pub fn remove_manual_penalty(&mut self, node_id: &NodeId) {
691 self.manual_node_penalties.remove(node_id);
694 /// Clears the list of manual penalties that are applied during path finding.
695 pub fn clear_manual_penalties(&mut self) {
696 self.manual_node_penalties = HashMap::new();
701 impl ProbabilisticScoringFeeParameters {
702 fn zero_penalty() -> Self {
704 base_penalty_msat: 0,
705 base_penalty_amount_multiplier_msat: 0,
706 liquidity_penalty_multiplier_msat: 0,
707 liquidity_penalty_amount_multiplier_msat: 0,
708 historical_liquidity_penalty_multiplier_msat: 0,
709 historical_liquidity_penalty_amount_multiplier_msat: 0,
710 manual_node_penalties: HashMap::new(),
711 anti_probing_penalty_msat: 0,
712 considered_impossible_penalty_msat: 0,
713 linear_success_probability: true,
718 /// Parameters for configuring [`ProbabilisticScorer`].
720 /// Used to configure decay parameters that are static throughout the lifetime of the scorer.
721 /// these decay parameters affect the score of the channel penalty and are not changed on a
722 /// per-route penalty cost call.
723 #[derive(Copy, Clone)]
724 pub struct ProbabilisticScoringDecayParameters {
725 /// If we aren't learning any new datapoints for a channel, the historical liquidity bounds
726 /// tracking can simply live on with increasingly stale data. Instead, when a channel has not
727 /// seen a liquidity estimate update for this amount of time, the historical datapoints are
729 /// For an example of historical_no_updates_half_life being used see [`historical_estimated_channel_liquidity_probabilities`]
731 /// Note that after 16 or more half lives all historical data will be completely gone.
733 /// Default value: 14 days
735 /// [`historical_estimated_channel_liquidity_probabilities`]: ProbabilisticScorer::historical_estimated_channel_liquidity_probabilities
736 pub historical_no_updates_half_life: Duration,
738 /// Whenever this amount of time elapses since the last update to a channel's liquidity bounds,
739 /// the distance from the bounds to "zero" is cut in half. In other words, the lower-bound on
740 /// the available liquidity is halved and the upper-bound moves half-way to the channel's total
743 /// Because halving the liquidity bounds grows the uncertainty on the channel's liquidity,
744 /// the penalty for an amount within the new bounds may change. See the [`ProbabilisticScorer`]
745 /// struct documentation for more info on the way the liquidity bounds are used.
747 /// For example, if the channel's capacity is 1 million sats, and the current upper and lower
748 /// liquidity bounds are 200,000 sats and 600,000 sats, after this amount of time the upper
749 /// and lower liquidity bounds will be decayed to 100,000 and 800,000 sats.
751 /// Default value: 6 hours
755 /// When built with the `no-std` feature, time will never elapse. Therefore, the channel
756 /// liquidity knowledge will never decay except when the bounds cross.
757 pub liquidity_offset_half_life: Duration,
760 impl Default for ProbabilisticScoringDecayParameters {
761 fn default() -> Self {
763 liquidity_offset_half_life: Duration::from_secs(6 * 60 * 60),
764 historical_no_updates_half_life: Duration::from_secs(60 * 60 * 24 * 14),
770 impl ProbabilisticScoringDecayParameters {
771 fn zero_penalty() -> Self {
773 liquidity_offset_half_life: Duration::from_secs(6 * 60 * 60),
774 historical_no_updates_half_life: Duration::from_secs(60 * 60 * 24 * 14),
779 /// Accounting for channel liquidity balance uncertainty.
781 /// Direction is defined in terms of [`NodeId`] partial ordering, where the source node is the
782 /// first node in the ordering of the channel's counterparties. Thus, swapping the two liquidity
783 /// offset fields gives the opposite direction.
784 #[repr(C)] // Force the fields in memory to be in the order we specify
785 struct ChannelLiquidity {
786 /// Lower channel liquidity bound in terms of an offset from zero.
787 min_liquidity_offset_msat: u64,
789 /// Upper channel liquidity bound in terms of an offset from the effective capacity.
790 max_liquidity_offset_msat: u64,
792 liquidity_history: HistoricalLiquidityTracker,
794 /// Time when the liquidity bounds were last modified as an offset since the unix epoch.
795 last_updated: Duration,
797 /// Time when the historical liquidity bounds were last modified as an offset against the unix
799 offset_history_last_updated: Duration,
802 // Check that the liquidity HashMap's entries sit on round cache lines.
804 // Specifically, the first cache line will have the key, the liquidity offsets, and the total
805 // points tracked in the historical tracker.
807 // The next two cache lines will have the historical points, which we only access last during
808 // scoring, followed by the last_updated `Duration`s (which we do not need during scoring).
809 const _LIQUIDITY_MAP_SIZING_CHECK: usize = 192 - ::core::mem::size_of::<(u64, ChannelLiquidity)>();
810 const _LIQUIDITY_MAP_SIZING_CHECK_2: usize = ::core::mem::size_of::<(u64, ChannelLiquidity)>() - 192;
812 /// A snapshot of [`ChannelLiquidity`] in one direction assuming a certain channel capacity and
813 /// decayed with a given half life.
814 struct DirectedChannelLiquidity<L: Deref<Target = u64>, HT: Deref<Target = HistoricalLiquidityTracker>, T: Deref<Target = Duration>> {
815 min_liquidity_offset_msat: L,
816 max_liquidity_offset_msat: L,
817 liquidity_history: DirectedHistoricalLiquidityTracker<HT>,
820 offset_history_last_updated: T,
823 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref> ProbabilisticScorer<G, L> where L::Target: Logger {
824 /// Creates a new scorer using the given scoring parameters for sending payments from a node
825 /// through a network graph.
826 pub fn new(decay_params: ProbabilisticScoringDecayParameters, network_graph: G, logger: L) -> Self {
831 channel_liquidities: HashMap::new(),
836 fn with_channel(mut self, short_channel_id: u64, liquidity: ChannelLiquidity) -> Self {
837 assert!(self.channel_liquidities.insert(short_channel_id, liquidity).is_none());
841 /// Dump the contents of this scorer into the configured logger.
843 /// Note that this writes roughly one line per channel for which we have a liquidity estimate,
844 /// which may be a substantial amount of log output.
845 pub fn debug_log_liquidity_stats(&self) {
846 let graph = self.network_graph.read_only();
847 for (scid, liq) in self.channel_liquidities.iter() {
848 if let Some(chan_debug) = graph.channels().get(scid) {
849 let log_direction = |source, target| {
850 if let Some((directed_info, _)) = chan_debug.as_directed_to(target) {
851 let amt = directed_info.effective_capacity().as_msat();
852 let dir_liq = liq.as_directed(source, target, amt);
854 let min_buckets = &dir_liq.liquidity_history.min_liquidity_offset_history_buckets();
855 let max_buckets = &dir_liq.liquidity_history.max_liquidity_offset_history_buckets();
857 log_debug!(self.logger, core::concat!(
858 "Liquidity from {} to {} via {} is in the range ({}, {}).\n",
859 "\tHistorical min liquidity bucket relative probabilities:\n",
860 "\t\t{} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {}\n",
861 "\tHistorical max liquidity bucket relative probabilities:\n",
862 "\t\t{} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {} {}"),
863 source, target, scid, dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat(),
864 min_buckets[ 0], min_buckets[ 1], min_buckets[ 2], min_buckets[ 3],
865 min_buckets[ 4], min_buckets[ 5], min_buckets[ 6], min_buckets[ 7],
866 min_buckets[ 8], min_buckets[ 9], min_buckets[10], min_buckets[11],
867 min_buckets[12], min_buckets[13], min_buckets[14], min_buckets[15],
868 min_buckets[16], min_buckets[17], min_buckets[18], min_buckets[19],
869 min_buckets[20], min_buckets[21], min_buckets[22], min_buckets[23],
870 min_buckets[24], min_buckets[25], min_buckets[26], min_buckets[27],
871 min_buckets[28], min_buckets[29], min_buckets[30], min_buckets[31],
872 // Note that the liquidity buckets are an offset from the edge, so we
873 // inverse the max order to get the probabilities from zero.
874 max_buckets[31], max_buckets[30], max_buckets[29], max_buckets[28],
875 max_buckets[27], max_buckets[26], max_buckets[25], max_buckets[24],
876 max_buckets[23], max_buckets[22], max_buckets[21], max_buckets[20],
877 max_buckets[19], max_buckets[18], max_buckets[17], max_buckets[16],
878 max_buckets[15], max_buckets[14], max_buckets[13], max_buckets[12],
879 max_buckets[11], max_buckets[10], max_buckets[ 9], max_buckets[ 8],
880 max_buckets[ 7], max_buckets[ 6], max_buckets[ 5], max_buckets[ 4],
881 max_buckets[ 3], max_buckets[ 2], max_buckets[ 1], max_buckets[ 0]);
883 log_debug!(self.logger, "No amount known for SCID {} from {:?} to {:?}", scid, source, target);
887 log_direction(&chan_debug.node_one, &chan_debug.node_two);
888 log_direction(&chan_debug.node_two, &chan_debug.node_one);
890 log_debug!(self.logger, "No network graph entry for SCID {}", scid);
895 /// Query the estimated minimum and maximum liquidity available for sending a payment over the
896 /// channel with `scid` towards the given `target` node.
897 pub fn estimated_channel_liquidity_range(&self, scid: u64, target: &NodeId) -> Option<(u64, u64)> {
898 let graph = self.network_graph.read_only();
900 if let Some(chan) = graph.channels().get(&scid) {
901 if let Some(liq) = self.channel_liquidities.get(&scid) {
902 if let Some((directed_info, source)) = chan.as_directed_to(target) {
903 let amt = directed_info.effective_capacity().as_msat();
904 let dir_liq = liq.as_directed(source, target, amt);
905 return Some((dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat()));
912 /// Query the historical estimated minimum and maximum liquidity available for sending a
913 /// payment over the channel with `scid` towards the given `target` node.
915 /// Returns two sets of 32 buckets. The first set describes the lower-bound liquidity history,
916 /// the second set describes the upper-bound liquidity history. Each bucket describes the
917 /// relative frequency at which we've seen a liquidity bound in the bucket's range relative to
918 /// the channel's total capacity, on an arbitrary scale. Because the values are slowly decayed,
919 /// more recent data points are weighted more heavily than older datapoints.
921 /// Note that the range of each bucket varies by its location to provide more granular results
922 /// at the edges of a channel's capacity, where it is more likely to sit.
924 /// When scoring, the estimated probability that an upper-/lower-bound lies in a given bucket
925 /// is calculated by dividing that bucket's value with the total value of all buckets.
927 /// For example, using a lower bucket count for illustrative purposes, a value of
928 /// `[0, 0, 0, ..., 0, 32]` indicates that we believe the probability of a bound being very
929 /// close to the channel's capacity to be 100%, and have never (recently) seen it in any other
930 /// bucket. A value of `[31, 0, 0, ..., 0, 0, 32]` indicates we've seen the bound being both
931 /// in the top and bottom bucket, and roughly with similar (recent) frequency.
933 /// Because the datapoints are decayed slowly over time, values will eventually return to
934 /// `Some(([0; 32], [0; 32]))` or `None` if no data remains for a channel.
936 /// In order to fetch a single success probability from the buckets provided here, as used in
937 /// the scoring model, see [`Self::historical_estimated_payment_success_probability`].
938 pub fn historical_estimated_channel_liquidity_probabilities(&self, scid: u64, target: &NodeId)
939 -> Option<([u16; 32], [u16; 32])> {
940 let graph = self.network_graph.read_only();
942 if let Some(chan) = graph.channels().get(&scid) {
943 if let Some(liq) = self.channel_liquidities.get(&scid) {
944 if let Some((directed_info, source)) = chan.as_directed_to(target) {
945 let amt = directed_info.effective_capacity().as_msat();
946 let dir_liq = liq.as_directed(source, target, amt);
948 let min_buckets = *dir_liq.liquidity_history.min_liquidity_offset_history_buckets();
949 let mut max_buckets = *dir_liq.liquidity_history.max_liquidity_offset_history_buckets();
951 // Note that the liquidity buckets are an offset from the edge, so we inverse
952 // the max order to get the probabilities from zero.
953 max_buckets.reverse();
954 return Some((min_buckets, max_buckets));
961 /// Query the probability of payment success sending the given `amount_msat` over the channel
962 /// with `scid` towards the given `target` node, based on the historical estimated liquidity
965 /// These are the same bounds as returned by
966 /// [`Self::historical_estimated_channel_liquidity_probabilities`] (but not those returned by
967 /// [`Self::estimated_channel_liquidity_range`]).
968 pub fn historical_estimated_payment_success_probability(
969 &self, scid: u64, target: &NodeId, amount_msat: u64, params: &ProbabilisticScoringFeeParameters)
971 let graph = self.network_graph.read_only();
973 if let Some(chan) = graph.channels().get(&scid) {
974 if let Some(liq) = self.channel_liquidities.get(&scid) {
975 if let Some((directed_info, source)) = chan.as_directed_to(target) {
976 let capacity_msat = directed_info.effective_capacity().as_msat();
977 let dir_liq = liq.as_directed(source, target, capacity_msat);
979 return dir_liq.liquidity_history.calculate_success_probability_times_billion(
980 ¶ms, amount_msat, capacity_msat
981 ).map(|p| p as f64 / (1024 * 1024 * 1024) as f64);
989 impl ChannelLiquidity {
990 fn new(last_updated: Duration) -> Self {
992 min_liquidity_offset_msat: 0,
993 max_liquidity_offset_msat: 0,
994 liquidity_history: HistoricalLiquidityTracker::new(),
996 offset_history_last_updated: last_updated,
1000 /// Returns a view of the channel liquidity directed from `source` to `target` assuming
1001 /// `capacity_msat`.
1003 &self, source: &NodeId, target: &NodeId, capacity_msat: u64,
1004 ) -> DirectedChannelLiquidity<&u64, &HistoricalLiquidityTracker, &Duration> {
1005 let source_less_than_target = source < target;
1006 let (min_liquidity_offset_msat, max_liquidity_offset_msat) =
1007 if source_less_than_target {
1008 (&self.min_liquidity_offset_msat, &self.max_liquidity_offset_msat)
1010 (&self.max_liquidity_offset_msat, &self.min_liquidity_offset_msat)
1013 DirectedChannelLiquidity {
1014 min_liquidity_offset_msat,
1015 max_liquidity_offset_msat,
1016 liquidity_history: self.liquidity_history.as_directed(source_less_than_target),
1018 last_updated: &self.last_updated,
1019 offset_history_last_updated: &self.offset_history_last_updated,
1023 /// Returns a mutable view of the channel liquidity directed from `source` to `target` assuming
1024 /// `capacity_msat`.
1026 &mut self, source: &NodeId, target: &NodeId, capacity_msat: u64,
1027 ) -> DirectedChannelLiquidity<&mut u64, &mut HistoricalLiquidityTracker, &mut Duration> {
1028 let source_less_than_target = source < target;
1029 let (min_liquidity_offset_msat, max_liquidity_offset_msat) =
1030 if source_less_than_target {
1031 (&mut self.min_liquidity_offset_msat, &mut self.max_liquidity_offset_msat)
1033 (&mut self.max_liquidity_offset_msat, &mut self.min_liquidity_offset_msat)
1036 DirectedChannelLiquidity {
1037 min_liquidity_offset_msat,
1038 max_liquidity_offset_msat,
1039 liquidity_history: self.liquidity_history.as_directed_mut(source_less_than_target),
1041 last_updated: &mut self.last_updated,
1042 offset_history_last_updated: &mut self.offset_history_last_updated,
1046 fn decayed_offset(&self, offset: u64, duration_since_epoch: Duration,
1047 decay_params: ProbabilisticScoringDecayParameters
1049 let half_life = decay_params.liquidity_offset_half_life.as_secs_f64();
1050 if half_life != 0.0 {
1051 let elapsed_time = duration_since_epoch.saturating_sub(self.last_updated).as_secs_f64();
1052 ((offset as f64) * powf64(0.5, elapsed_time / half_life)) as u64
1059 /// Bounds `-log10` to avoid excessive liquidity penalties for payments with low success
1061 const NEGATIVE_LOG10_UPPER_BOUND: u64 = 2;
1063 /// The rough cutoff at which our precision falls off and we should stop bothering to try to log a
1064 /// ratio, as X in 1/X.
1065 const PRECISION_LOWER_BOUND_DENOMINATOR: u64 = log_approx::LOWER_BITS_BOUND;
1067 /// The divisor used when computing the amount penalty.
1068 const AMOUNT_PENALTY_DIVISOR: u64 = 1 << 20;
1069 const BASE_AMOUNT_PENALTY_DIVISOR: u64 = 1 << 30;
1071 /// Raises three `f32`s to the 3rd power, without `powi` because it requires `std` (dunno why).
1073 fn three_f32_pow_3(a: f32, b: f32, c: f32) -> (f32, f32, f32) {
1074 (a * a * a, b * b * b, c * c * c)
1078 fn linear_success_probability(
1079 amount_msat: u64, min_liquidity_msat: u64, max_liquidity_msat: u64,
1080 min_zero_implies_no_successes: bool,
1082 let (numerator, mut denominator) =
1083 (max_liquidity_msat - amount_msat,
1084 (max_liquidity_msat - min_liquidity_msat).saturating_add(1));
1086 if min_zero_implies_no_successes && min_liquidity_msat == 0 &&
1087 denominator < u64::max_value() / 21
1089 // If we have no knowledge of the channel, scale probability down by ~75%
1090 // Note that we prefer to increase the denominator rather than decrease the numerator as
1091 // the denominator is more likely to be larger and thus provide greater precision. This is
1092 // mostly an overoptimization but makes a large difference in tests.
1093 denominator = denominator * 21 / 16
1096 (numerator, denominator)
1100 fn nonlinear_success_probability_f(
1101 amount_msat: u16, min_liquidity_msat: u16, max_liquidity_msat: u16, capacity_msat: u16,
1102 min_zero_implies_no_successes: bool, value_numerator: u64, value_denominator: u64,
1104 debug_assert!(min_liquidity_msat <= amount_msat);
1105 debug_assert!(amount_msat < max_liquidity_msat);
1106 debug_assert!(max_liquidity_msat <= capacity_msat);
1108 let min_max_amt_max_msat = FourF32::from_ints(
1115 let capacity = capacity_msat as f32;
1116 let cap_cap_cap_cap = FourF32::new(capacity, capacity, capacity, capacity);
1118 let min_max_amt_max = min_max_amt_max_msat / cap_cap_cap_cap;
1120 let mhalf_mhalf_mhalf_mhalf = FourF32::new(-0.5f32, -0.5f32, -0.5f32, -0.5f32);
1121 let min_max_amt_max_offset = min_max_amt_max + mhalf_mhalf_mhalf_mhalf;
1123 let min_max_amt_max_sq = min_max_amt_max_offset * min_max_amt_max_offset;
1124 let min_max_amt_max_pow = min_max_amt_max_sq * min_max_amt_max_offset;
1126 let zero_zero_maxmin_maxamt = min_max_amt_max_pow.hsub();
1128 let mut zero_zero_den_num = zero_zero_maxmin_maxamt;
1129 if min_zero_implies_no_successes && min_liquidity_msat == 0 {
1130 let zero_zero_twentyone_sixteen = FourF32::new(0.0f32, 0.0f32, 21.0f32, 16.0f32);
1131 zero_zero_den_num = zero_zero_den_num * zero_zero_twentyone_sixteen;
1134 let zero_zero_vden_vnum = FourF32::new(0.0f32, 0.0f32, value_denominator as f32, value_numerator as f32);
1135 let zero_zero_rden_rnum = zero_zero_den_num * zero_zero_vden_vnum;
1137 let res = zero_zero_rden_rnum.dump();
1144 fn nonlinear_success_probability(
1145 amount_msat: u64, min_liquidity_msat: u64, max_liquidity_msat: u64, capacity_msat: u64,
1147 let capacity = capacity_msat as f32;
1148 let min = (min_liquidity_msat as f32) / capacity;
1149 let max = (max_liquidity_msat as f32) / capacity;
1150 let amount = (amount_msat as f32) / capacity;
1152 // Assume the channel has a probability density function of (x - 0.5)^2 for values from
1153 // 0 to 1 (where 1 is the channel's full capacity). The success probability given some
1154 // liquidity bounds is thus the integral under the curve from the amount to maximum
1155 // estimated liquidity, divided by the same integral from the minimum to the maximum
1156 // estimated liquidity bounds.
1158 // Because the integral from x to y is simply (y - 0.5)^3 - (x - 0.5)^3, we can
1159 // calculate the cumulative density function between the min/max bounds trivially. Note
1160 // that we don't bother to normalize the CDF to total to 1, as it will come out in the
1161 // division of num / den.
1162 let (max_pow, amt_pow, min_pow) = three_f32_pow_3(max - 0.5, amount - 0.5, min - 0.5);
1163 (max_pow - amt_pow, max_pow - min_pow)
1166 /// Given liquidity bounds, calculates the success probability (in the form of a numerator and
1167 /// denominator) of an HTLC. This is a key assumption in our scoring models.
1169 /// min_zero_implies_no_successes signals that a `min_liquidity_msat` of 0 means we've not
1170 /// (recently) seen an HTLC successfully complete over this channel.
1172 fn success_probability(
1173 amount_msat: u64, min_liquidity_msat: u64, max_liquidity_msat: u64, capacity_msat: u64,
1174 params: &ProbabilisticScoringFeeParameters, min_zero_implies_no_successes: bool,
1176 debug_assert!(min_liquidity_msat <= amount_msat);
1177 debug_assert!(amount_msat < max_liquidity_msat);
1178 debug_assert!(max_liquidity_msat <= capacity_msat);
1180 if params.linear_success_probability {
1181 return linear_success_probability(
1182 amount_msat, min_liquidity_msat, max_liquidity_msat, min_zero_implies_no_successes
1186 let (num, den) = nonlinear_success_probability(
1187 amount_msat, min_liquidity_msat, max_liquidity_msat, capacity_msat
1190 // Because our numerator and denominator max out at 0.5^3 we need to multiply them by
1191 // quite a large factor to get something useful (ideally in the 2^30 range).
1192 const BILLIONISH: f32 = 1024.0 * 1024.0 * 1024.0;
1193 let numerator = (num * BILLIONISH) as u64 + 1;
1194 let mut denominator = (den * BILLIONISH) as u64 + 1;
1195 debug_assert!(numerator <= 1 << 30, "Got large numerator ({}) from float {}.", numerator, num);
1196 debug_assert!(denominator <= 1 << 30, "Got large denominator ({}) from float {}.", denominator, den);
1198 if min_zero_implies_no_successes && min_liquidity_msat == 0 &&
1199 denominator < u64::max_value() / 21
1201 // If we have no knowledge of the channel, scale probability down by ~75%
1202 // Note that we prefer to increase the denominator rather than decrease the numerator as
1203 // the denominator is more likely to be larger and thus provide greater precision. This is
1204 // mostly an overoptimization but makes a large difference in tests.
1205 denominator = denominator * 21 / 16
1208 (numerator, denominator)
1211 /// Given liquidity bounds, calculates the success probability (times some value) of an HTLC. This
1212 /// is a key assumption in our scoring models.
1214 /// min_zero_implies_no_successes signals that a `min_liquidity_msat` of 0 means we've not
1215 /// (recently) seen an HTLC successfully complete over this channel.
1217 fn linear_success_probability_times_value_times_billion(
1218 amount_msat: u16, min_liquidity_msat: u16, max_liquidity_msat: u16, capacity_msat: u16,
1219 min_zero_implies_no_successes: bool, value_numerator: u64, value_denominator: u64,
1221 debug_assert!(min_liquidity_msat <= amount_msat);
1222 debug_assert!(amount_msat < max_liquidity_msat);
1223 debug_assert!(max_liquidity_msat <= capacity_msat);
1225 let (numerator, denominator) = linear_success_probability(
1226 amount_msat as u64, min_liquidity_msat as u64, max_liquidity_msat as u64, min_zero_implies_no_successes
1228 const BILLIONISH: u64 = 1024 * 1024 * 1024;
1229 return (value_numerator * BILLIONISH / value_denominator) * numerator / denominator;
1232 impl<L: Deref<Target = u64>, HT: Deref<Target = HistoricalLiquidityTracker>, T: Deref<Target = Duration>>
1233 DirectedChannelLiquidity< L, HT, T> {
1234 /// Returns a liquidity penalty for routing the given HTLC `amount_msat` through the channel in
1236 fn penalty_msat(&self, amount_msat: u64, score_params: &ProbabilisticScoringFeeParameters) -> u64 {
1237 let available_capacity = self.capacity_msat;
1238 let max_liquidity_msat = self.max_liquidity_msat();
1239 let min_liquidity_msat = core::cmp::min(self.min_liquidity_msat(), max_liquidity_msat);
1241 let mut res = if amount_msat <= min_liquidity_msat {
1243 } else if amount_msat >= max_liquidity_msat {
1244 // Equivalent to hitting the else clause below with the amount equal to the effective
1245 // capacity and without any certainty on the liquidity upper bound, plus the
1246 // impossibility penalty.
1247 let negative_log10_times_2048 = NEGATIVE_LOG10_UPPER_BOUND * 2048;
1248 Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
1249 score_params.liquidity_penalty_multiplier_msat,
1250 score_params.liquidity_penalty_amount_multiplier_msat)
1251 .saturating_add(score_params.considered_impossible_penalty_msat)
1253 let (numerator, denominator) = success_probability(amount_msat,
1254 min_liquidity_msat, max_liquidity_msat, available_capacity, score_params, false);
1255 if denominator - numerator < denominator / PRECISION_LOWER_BOUND_DENOMINATOR {
1256 // If the failure probability is < 1.5625% (as 1 - numerator/denominator < 1/64),
1257 // don't bother trying to use the log approximation as it gets too noisy to be
1258 // particularly helpful, instead just round down to 0.
1261 let negative_log10_times_2048 =
1262 log_approx::negative_log10_times_2048(numerator, denominator);
1263 Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
1264 score_params.liquidity_penalty_multiplier_msat,
1265 score_params.liquidity_penalty_amount_multiplier_msat)
1269 if amount_msat >= available_capacity {
1270 // We're trying to send more than the capacity, use a max penalty.
1271 res = res.saturating_add(Self::combined_penalty_msat(amount_msat,
1272 NEGATIVE_LOG10_UPPER_BOUND * 2048,
1273 score_params.historical_liquidity_penalty_multiplier_msat,
1274 score_params.historical_liquidity_penalty_amount_multiplier_msat));
1278 if score_params.historical_liquidity_penalty_multiplier_msat != 0 ||
1279 score_params.historical_liquidity_penalty_amount_multiplier_msat != 0 {
1280 if let Some(cumulative_success_prob_times_billion) = self.liquidity_history
1281 .calculate_success_probability_times_billion(
1282 score_params, amount_msat, self.capacity_msat)
1284 let historical_negative_log10_times_2048 =
1285 log_approx::negative_log10_times_2048(cumulative_success_prob_times_billion + 1, 1024 * 1024 * 1024);
1286 res = res.saturating_add(Self::combined_penalty_msat(amount_msat,
1287 historical_negative_log10_times_2048, score_params.historical_liquidity_penalty_multiplier_msat,
1288 score_params.historical_liquidity_penalty_amount_multiplier_msat));
1290 // If we don't have any valid points (or, once decayed, we have less than a full
1291 // point), redo the non-historical calculation with no liquidity bounds tracked and
1292 // the historical penalty multipliers.
1293 let (numerator, denominator) = success_probability(amount_msat, 0,
1294 available_capacity, available_capacity, score_params, true);
1295 let negative_log10_times_2048 =
1296 log_approx::negative_log10_times_2048(numerator, denominator);
1297 res = res.saturating_add(Self::combined_penalty_msat(amount_msat, negative_log10_times_2048,
1298 score_params.historical_liquidity_penalty_multiplier_msat,
1299 score_params.historical_liquidity_penalty_amount_multiplier_msat));
1306 /// Computes the liquidity penalty from the penalty multipliers.
1308 fn combined_penalty_msat(amount_msat: u64, mut negative_log10_times_2048: u64,
1309 liquidity_penalty_multiplier_msat: u64, liquidity_penalty_amount_multiplier_msat: u64,
1311 negative_log10_times_2048 =
1312 negative_log10_times_2048.min(NEGATIVE_LOG10_UPPER_BOUND * 2048);
1314 // Upper bound the liquidity penalty to ensure some channel is selected.
1315 let liquidity_penalty_msat = negative_log10_times_2048
1316 .saturating_mul(liquidity_penalty_multiplier_msat) / 2048;
1317 let amount_penalty_msat = negative_log10_times_2048
1318 .saturating_mul(liquidity_penalty_amount_multiplier_msat)
1319 .saturating_mul(amount_msat) / 2048 / AMOUNT_PENALTY_DIVISOR;
1321 liquidity_penalty_msat.saturating_add(amount_penalty_msat)
1324 /// Returns the lower bound of the channel liquidity balance in this direction.
1326 fn min_liquidity_msat(&self) -> u64 {
1327 *self.min_liquidity_offset_msat
1330 /// Returns the upper bound of the channel liquidity balance in this direction.
1332 fn max_liquidity_msat(&self) -> u64 {
1334 .saturating_sub(*self.max_liquidity_offset_msat)
1338 impl<L: DerefMut<Target = u64>, HT: DerefMut<Target = HistoricalLiquidityTracker>, T: DerefMut<Target = Duration>>
1339 DirectedChannelLiquidity<L, HT, T> {
1340 /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat`.
1341 fn failed_at_channel<Log: Deref>(
1342 &mut self, amount_msat: u64, duration_since_epoch: Duration, chan_descr: fmt::Arguments, logger: &Log
1343 ) where Log::Target: Logger {
1344 let existing_max_msat = self.max_liquidity_msat();
1345 if amount_msat < existing_max_msat {
1346 log_debug!(logger, "Setting max liquidity of {} from {} to {}", chan_descr, existing_max_msat, amount_msat);
1347 self.set_max_liquidity_msat(amount_msat, duration_since_epoch);
1349 log_trace!(logger, "Max liquidity of {} is {} (already less than or equal to {})",
1350 chan_descr, existing_max_msat, amount_msat);
1352 self.update_history_buckets(0, duration_since_epoch);
1355 /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat` downstream.
1356 fn failed_downstream<Log: Deref>(
1357 &mut self, amount_msat: u64, duration_since_epoch: Duration, chan_descr: fmt::Arguments, logger: &Log
1358 ) where Log::Target: Logger {
1359 let existing_min_msat = self.min_liquidity_msat();
1360 if amount_msat > existing_min_msat {
1361 log_debug!(logger, "Setting min liquidity of {} from {} to {}", existing_min_msat, chan_descr, amount_msat);
1362 self.set_min_liquidity_msat(amount_msat, duration_since_epoch);
1364 log_trace!(logger, "Min liquidity of {} is {} (already greater than or equal to {})",
1365 chan_descr, existing_min_msat, amount_msat);
1367 self.update_history_buckets(0, duration_since_epoch);
1370 /// Adjusts the channel liquidity balance bounds when successfully routing `amount_msat`.
1371 fn successful<Log: Deref>(&mut self,
1372 amount_msat: u64, duration_since_epoch: Duration, chan_descr: fmt::Arguments, logger: &Log
1373 ) where Log::Target: Logger {
1374 let max_liquidity_msat = self.max_liquidity_msat().checked_sub(amount_msat).unwrap_or(0);
1375 log_debug!(logger, "Subtracting {} from max liquidity of {} (setting it to {})", amount_msat, chan_descr, max_liquidity_msat);
1376 self.set_max_liquidity_msat(max_liquidity_msat, duration_since_epoch);
1377 self.update_history_buckets(amount_msat, duration_since_epoch);
1380 /// Updates the history buckets for this channel. Because the history buckets track what we now
1381 /// know about the channel's state *prior to our payment* (i.e. what we assume is "steady
1382 /// state"), we allow the caller to set an offset applied to our liquidity bounds which
1383 /// represents the amount of the successful payment we just made.
1384 fn update_history_buckets(&mut self, bucket_offset_msat: u64, duration_since_epoch: Duration) {
1385 self.liquidity_history.track_datapoint(
1386 *self.min_liquidity_offset_msat + bucket_offset_msat,
1387 self.max_liquidity_offset_msat.saturating_sub(bucket_offset_msat),
1390 *self.offset_history_last_updated = duration_since_epoch;
1393 /// Adjusts the lower bound of the channel liquidity balance in this direction.
1394 fn set_min_liquidity_msat(&mut self, amount_msat: u64, duration_since_epoch: Duration) {
1395 *self.min_liquidity_offset_msat = amount_msat;
1396 if amount_msat > self.max_liquidity_msat() {
1397 *self.max_liquidity_offset_msat = 0;
1399 *self.last_updated = duration_since_epoch;
1402 /// Adjusts the upper bound of the channel liquidity balance in this direction.
1403 fn set_max_liquidity_msat(&mut self, amount_msat: u64, duration_since_epoch: Duration) {
1404 *self.max_liquidity_offset_msat = self.capacity_msat.checked_sub(amount_msat).unwrap_or(0);
1405 if amount_msat < *self.min_liquidity_offset_msat {
1406 *self.min_liquidity_offset_msat = 0;
1408 *self.last_updated = duration_since_epoch;
1412 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref> ScoreLookUp for ProbabilisticScorer<G, L> where L::Target: Logger {
1413 type ScoreParams = ProbabilisticScoringFeeParameters;
1414 fn channel_penalty_msat(
1415 &self, candidate: &CandidateRouteHop, usage: ChannelUsage, score_params: &ProbabilisticScoringFeeParameters
1417 let (scid, target) = match candidate {
1418 CandidateRouteHop::PublicHop { info, short_channel_id } => {
1419 (short_channel_id, info.target())
1423 let source = candidate.source();
1424 if let Some(penalty) = score_params.manual_node_penalties.get(&target) {
1428 let base_penalty_msat = score_params.base_penalty_msat.saturating_add(
1429 score_params.base_penalty_amount_multiplier_msat
1430 .saturating_mul(usage.amount_msat) / BASE_AMOUNT_PENALTY_DIVISOR);
1432 let mut anti_probing_penalty_msat = 0;
1433 match usage.effective_capacity {
1434 EffectiveCapacity::ExactLiquidity { liquidity_msat: amount_msat } |
1435 EffectiveCapacity::HintMaxHTLC { amount_msat } =>
1437 if usage.amount_msat > amount_msat {
1438 return u64::max_value();
1440 return base_penalty_msat;
1443 EffectiveCapacity::Total { capacity_msat, htlc_maximum_msat } => {
1444 if htlc_maximum_msat >= capacity_msat/2 {
1445 anti_probing_penalty_msat = score_params.anti_probing_penalty_msat;
1451 let amount_msat = usage.amount_msat.saturating_add(usage.inflight_htlc_msat);
1452 let capacity_msat = usage.effective_capacity.as_msat();
1453 self.channel_liquidities
1455 .unwrap_or(&ChannelLiquidity::new(Duration::ZERO))
1456 .as_directed(&source, &target, capacity_msat)
1457 .penalty_msat(amount_msat, score_params)
1458 .saturating_add(anti_probing_penalty_msat)
1459 .saturating_add(base_penalty_msat)
1463 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref> ScoreUpdate for ProbabilisticScorer<G, L> where L::Target: Logger {
1464 fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) {
1465 let amount_msat = path.final_value_msat();
1466 log_trace!(self.logger, "Scoring path through to SCID {} as having failed at {} msat", short_channel_id, amount_msat);
1467 let network_graph = self.network_graph.read_only();
1468 for (hop_idx, hop) in path.hops.iter().enumerate() {
1469 let target = NodeId::from_pubkey(&hop.pubkey);
1470 let channel_directed_from_source = network_graph.channels()
1471 .get(&hop.short_channel_id)
1472 .and_then(|channel| channel.as_directed_to(&target));
1474 let at_failed_channel = hop.short_channel_id == short_channel_id;
1475 if at_failed_channel && hop_idx == 0 {
1476 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);
1479 // Only score announced channels.
1480 if let Some((channel, source)) = channel_directed_from_source {
1481 let capacity_msat = channel.effective_capacity().as_msat();
1482 if at_failed_channel {
1483 self.channel_liquidities
1484 .entry(hop.short_channel_id)
1485 .or_insert_with(|| ChannelLiquidity::new(duration_since_epoch))
1486 .as_directed_mut(source, &target, capacity_msat)
1487 .failed_at_channel(amount_msat, duration_since_epoch,
1488 format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1490 self.channel_liquidities
1491 .entry(hop.short_channel_id)
1492 .or_insert_with(|| ChannelLiquidity::new(duration_since_epoch))
1493 .as_directed_mut(source, &target, capacity_msat)
1494 .failed_downstream(amount_msat, duration_since_epoch,
1495 format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1498 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).",
1499 hop.short_channel_id);
1501 if at_failed_channel { break; }
1505 fn payment_path_successful(&mut self, path: &Path, duration_since_epoch: Duration) {
1506 let amount_msat = path.final_value_msat();
1507 log_trace!(self.logger, "Scoring path through SCID {} as having succeeded at {} msat.",
1508 path.hops.split_last().map(|(hop, _)| hop.short_channel_id).unwrap_or(0), amount_msat);
1509 let network_graph = self.network_graph.read_only();
1510 for hop in &path.hops {
1511 let target = NodeId::from_pubkey(&hop.pubkey);
1512 let channel_directed_from_source = network_graph.channels()
1513 .get(&hop.short_channel_id)
1514 .and_then(|channel| channel.as_directed_to(&target));
1516 // Only score announced channels.
1517 if let Some((channel, source)) = channel_directed_from_source {
1518 let capacity_msat = channel.effective_capacity().as_msat();
1519 self.channel_liquidities
1520 .entry(hop.short_channel_id)
1521 .or_insert_with(|| ChannelLiquidity::new(duration_since_epoch))
1522 .as_directed_mut(source, &target, capacity_msat)
1523 .successful(amount_msat, duration_since_epoch,
1524 format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
1526 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).",
1527 hop.short_channel_id);
1532 fn probe_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) {
1533 self.payment_path_failed(path, short_channel_id, duration_since_epoch)
1536 fn probe_successful(&mut self, path: &Path, duration_since_epoch: Duration) {
1537 self.payment_path_failed(path, u64::max_value(), duration_since_epoch)
1540 fn decay_liquidity_certainty(&mut self, duration_since_epoch: Duration) {
1541 let decay_params = self.decay_params;
1542 self.channel_liquidities.retain(|_scid, liquidity| {
1543 liquidity.min_liquidity_offset_msat =
1544 liquidity.decayed_offset(liquidity.min_liquidity_offset_msat, duration_since_epoch, decay_params);
1545 liquidity.max_liquidity_offset_msat =
1546 liquidity.decayed_offset(liquidity.max_liquidity_offset_msat, duration_since_epoch, decay_params);
1547 liquidity.last_updated = duration_since_epoch;
1550 duration_since_epoch.saturating_sub(liquidity.offset_history_last_updated);
1551 if elapsed_time > decay_params.historical_no_updates_half_life {
1552 let half_life = decay_params.historical_no_updates_half_life.as_secs_f64();
1553 if half_life != 0.0 {
1554 liquidity.liquidity_history.decay_buckets(elapsed_time.as_secs_f64() / half_life);
1555 liquidity.offset_history_last_updated = duration_since_epoch;
1558 liquidity.min_liquidity_offset_msat != 0 || liquidity.max_liquidity_offset_msat != 0 ||
1559 liquidity.liquidity_history.has_datapoints()
1565 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref> Score for ProbabilisticScorer<G, L>
1566 where L::Target: Logger {}
1568 #[cfg(feature = "std")]
1570 fn powf64(n: f64, exp: f64) -> f64 {
1573 #[cfg(not(feature = "std"))]
1574 fn powf64(n: f64, exp: f64) -> f64 {
1575 libm::powf(n as f32, exp as f32) as f64
1578 mod bucketed_history {
1581 // Because liquidity is often skewed heavily in one direction, we store historical state
1582 // distribution in buckets of different size. For backwards compatibility, buckets of size 1/8th
1583 // must fit evenly into the buckets here.
1585 // The smallest bucket is 2^-14th of the channel, for each of our 32 buckets here we define the
1586 // width of the bucket in 2^14'ths of the channel. This increases exponentially until we reach
1587 // a full 16th of the channel's capacity, which is reapeated a few times for backwards
1588 // compatibility. The four middle buckets represent full octiles of the channel's capacity.
1590 // For a 1 BTC channel, this let's us differentiate between failures in the bottom 6k sats, or
1591 // between the 12,000th sat and 24,000th sat, while only needing to store and operate on 32
1592 // buckets in total.
1594 // By default u16s may not be cache-aligned, but we'd rather not have to read a third cache
1595 // line just to access it
1597 struct BucketStartPos([u16; 33]);
1598 impl BucketStartPos {
1599 const fn new() -> Self {
1601 0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 3072, 4096, 6144, 8192, 10240, 12288,
1602 13312, 14336, 15360, 15872, 16128, 16256, 16320, 16352, 16368, 16376, 16380, 16382, 16383, 16384,
1606 impl core::ops::Index<usize> for BucketStartPos {
1609 fn index(&self, index: usize) -> &u16 { &self.0[index] }
1611 const BUCKET_START_POS: BucketStartPos = BucketStartPos::new();
1613 const LEGACY_TO_BUCKET_RANGE: [(u8, u8); 8] = [
1614 (0, 12), (12, 14), (14, 15), (15, 16), (16, 17), (17, 18), (18, 20), (20, 32)
1617 const POSITION_TICKS: u16 = 1 << 14;
1619 fn pos_to_bucket(pos: u16) -> usize {
1620 for bucket in 0..32 {
1621 if pos < BUCKET_START_POS[bucket + 1] {
1625 debug_assert!(false);
1631 fn check_bucket_maps() {
1632 const BUCKET_WIDTH_IN_16384S: [u16; 32] = [
1633 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 1024, 1024, 2048, 2048,
1634 2048, 2048, 1024, 1024, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 1];
1636 let mut min_size_iter = 0;
1637 let mut legacy_bucket_iter = 0;
1638 for (bucket, width) in BUCKET_WIDTH_IN_16384S.iter().enumerate() {
1639 assert_eq!(BUCKET_START_POS[bucket], min_size_iter);
1640 for i in 0..*width {
1641 assert_eq!(pos_to_bucket(min_size_iter + i) as usize, bucket);
1643 min_size_iter += *width;
1644 if min_size_iter % (POSITION_TICKS / 8) == 0 {
1645 assert_eq!(LEGACY_TO_BUCKET_RANGE[legacy_bucket_iter].1 as usize, bucket + 1);
1646 if legacy_bucket_iter + 1 < 8 {
1647 assert_eq!(LEGACY_TO_BUCKET_RANGE[legacy_bucket_iter + 1].0 as usize, bucket + 1);
1649 legacy_bucket_iter += 1;
1652 assert_eq!(BUCKET_START_POS[32], POSITION_TICKS);
1653 assert_eq!(min_size_iter, POSITION_TICKS);
1657 fn amount_to_pos(amount_msat: u64, capacity_msat: u64) -> u16 {
1658 let pos = if amount_msat < u64::max_value() / (POSITION_TICKS as u64) {
1659 (amount_msat * (POSITION_TICKS as u64) / capacity_msat.saturating_add(1))
1660 .try_into().unwrap_or(POSITION_TICKS)
1662 // Only use 128-bit arithmetic when multiplication will overflow to avoid 128-bit
1663 // division. This branch should only be hit in fuzz testing since the amount would
1664 // need to be over 2.88 million BTC in practice.
1665 ((amount_msat as u128) * (POSITION_TICKS as u128)
1666 / (capacity_msat as u128).saturating_add(1))
1667 .try_into().unwrap_or(POSITION_TICKS)
1669 // If we are running in a client that doesn't validate gossip, its possible for a channel's
1670 // capacity to change due to a `channel_update` message which, if received while a payment
1671 // is in-flight, could cause this to fail. Thus, we only assert in test.
1673 debug_assert!(pos < POSITION_TICKS);
1677 /// Prior to LDK 0.0.117 we used eight buckets which were split evenly across the either
1678 /// octiles. This was changed to use 32 buckets for accuracy reasons in 0.0.117, however we
1679 /// support reading the legacy values here for backwards compatibility.
1680 pub(super) struct LegacyHistoricalBucketRangeTracker {
1684 impl LegacyHistoricalBucketRangeTracker {
1685 pub(crate) fn into_current(&self) -> HistoricalBucketRangeTracker {
1686 let mut buckets = [0; 32];
1687 for (idx, legacy_bucket) in self.buckets.iter().enumerate() {
1688 let mut new_val = *legacy_bucket;
1689 let (start, end) = LEGACY_TO_BUCKET_RANGE[idx];
1690 new_val /= (end - start) as u16;
1691 for i in start..end {
1692 buckets[i as usize] = new_val;
1695 HistoricalBucketRangeTracker { buckets }
1699 /// Tracks the historical state of a distribution as a weighted average of how much time was spent
1700 /// in each of 32 buckets.
1701 #[derive(Clone, Copy)]
1702 pub(super) struct HistoricalBucketRangeTracker {
1706 /// Buckets are stored in fixed point numbers with a 5 bit fractional part. Thus, the value
1707 /// "one" is 32, or this constant.
1708 pub const BUCKET_FIXED_POINT_ONE: u16 = 32;
1710 impl HistoricalBucketRangeTracker {
1711 pub(super) fn new() -> Self { Self { buckets: [0; 32] } }
1712 fn track_datapoint(&mut self, liquidity_offset_msat: u64, capacity_msat: u64) {
1713 // We have 32 leaky buckets for min and max liquidity. Each bucket tracks the amount of time
1714 // we spend in each bucket as a 16-bit fixed-point number with a 5 bit fractional part.
1716 // Each time we update our liquidity estimate, we add 32 (1.0 in our fixed-point system) to
1717 // the buckets for the current min and max liquidity offset positions.
1719 // We then decay each bucket by multiplying by 2047/2048 (avoiding dividing by a
1720 // non-power-of-two). This ensures we can't actually overflow the u16 - when we get to
1721 // 63,457 adding 32 and decaying by 2047/2048 leaves us back at 63,457.
1723 // In total, this allows us to track data for the last 8,000 or so payments across a given
1726 // These constants are a balance - we try to fit in 2 bytes per bucket to reduce overhead,
1727 // and need to balance having more bits in the decimal part (to ensure decay isn't too
1728 // non-linear) with having too few bits in the mantissa, causing us to not store very many
1731 // The constants were picked experimentally, selecting a decay amount that restricts us
1732 // from overflowing buckets without having to cap them manually.
1734 let pos: u16 = amount_to_pos(liquidity_offset_msat, capacity_msat);
1735 if pos < POSITION_TICKS {
1736 for e in self.buckets.iter_mut() {
1737 *e = ((*e as u32) * 2047 / 2048) as u16;
1739 let bucket = pos_to_bucket(pos);
1740 self.buckets[bucket] = self.buckets[bucket].saturating_add(BUCKET_FIXED_POINT_ONE);
1745 impl_writeable_tlv_based!(HistoricalBucketRangeTracker, { (0, buckets, required) });
1746 impl_writeable_tlv_based!(LegacyHistoricalBucketRangeTracker, { (0, buckets, required) });
1748 #[derive(Clone, Copy)]
1749 #[repr(C)] // Force the fields in memory to be in the order we specify.
1750 pub(super) struct HistoricalLiquidityTracker {
1751 total_valid_points_tracked: u64,
1752 min_liquidity_offset_history: HistoricalBucketRangeTracker,
1753 max_liquidity_offset_history: HistoricalBucketRangeTracker,
1756 impl HistoricalLiquidityTracker {
1757 pub(super) fn new() -> HistoricalLiquidityTracker {
1758 HistoricalLiquidityTracker {
1759 min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1760 max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
1761 total_valid_points_tracked: 0,
1765 pub(super) fn from_min_max(
1766 min_liquidity_offset_history: HistoricalBucketRangeTracker,
1767 max_liquidity_offset_history: HistoricalBucketRangeTracker,
1768 ) -> HistoricalLiquidityTracker {
1769 let mut res = HistoricalLiquidityTracker {
1770 min_liquidity_offset_history,
1771 max_liquidity_offset_history,
1772 total_valid_points_tracked: 0,
1774 res.recalculate_valid_points();
1778 pub(super) fn has_datapoints(&self) -> bool {
1779 self.min_liquidity_offset_history.buckets != [0; 32] ||
1780 self.max_liquidity_offset_history.buckets != [0; 32]
1783 pub(super) fn decay_buckets(&mut self, half_lives: f64) {
1784 let divisor = powf64(2048.0, half_lives) as u64;
1785 for bucket in self.min_liquidity_offset_history.buckets.iter_mut() {
1786 *bucket = ((*bucket as u64) * 1024 / divisor) as u16;
1788 for bucket in self.max_liquidity_offset_history.buckets.iter_mut() {
1789 *bucket = ((*bucket as u64) * 1024 / divisor) as u16;
1791 self.recalculate_valid_points();
1794 fn recalculate_valid_points(&mut self) {
1795 self.total_valid_points_tracked = 0;
1796 for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate() {
1797 for max_bucket in self.max_liquidity_offset_history.buckets.iter().take(32 - min_idx) {
1798 self.total_valid_points_tracked += (*min_bucket as u64) * (*max_bucket as u64);
1803 pub(super) fn writeable_min_offset_history(&self) -> &HistoricalBucketRangeTracker {
1804 &self.min_liquidity_offset_history
1807 pub(super) fn writeable_max_offset_history(&self) -> &HistoricalBucketRangeTracker {
1808 &self.max_liquidity_offset_history
1811 pub(super) fn as_directed<'a>(&'a self, source_less_than_target: bool)
1812 -> DirectedHistoricalLiquidityTracker<&'a HistoricalLiquidityTracker> {
1813 DirectedHistoricalLiquidityTracker { source_less_than_target, tracker: self }
1816 pub(super) fn as_directed_mut<'a>(&'a mut self, source_less_than_target: bool)
1817 -> DirectedHistoricalLiquidityTracker<&'a mut HistoricalLiquidityTracker> {
1818 DirectedHistoricalLiquidityTracker { source_less_than_target, tracker: self }
1822 /// A set of buckets representing the history of where we've seen the minimum- and maximum-
1823 /// liquidity bounds for a given channel.
1824 pub(super) struct DirectedHistoricalLiquidityTracker<D: Deref<Target = HistoricalLiquidityTracker>> {
1825 source_less_than_target: bool,
1829 impl<D: DerefMut<Target = HistoricalLiquidityTracker>> DirectedHistoricalLiquidityTracker<D> {
1830 pub(super) fn track_datapoint(
1831 &mut self, min_offset_msat: u64, max_offset_msat: u64, capacity_msat: u64,
1833 if self.source_less_than_target {
1834 self.tracker.min_liquidity_offset_history.track_datapoint(min_offset_msat, capacity_msat);
1835 self.tracker.max_liquidity_offset_history.track_datapoint(max_offset_msat, capacity_msat);
1837 self.tracker.max_liquidity_offset_history.track_datapoint(min_offset_msat, capacity_msat);
1838 self.tracker.min_liquidity_offset_history.track_datapoint(max_offset_msat, capacity_msat);
1840 self.tracker.recalculate_valid_points();
1844 impl<D: Deref<Target = HistoricalLiquidityTracker>> DirectedHistoricalLiquidityTracker<D> {
1845 pub(super) fn min_liquidity_offset_history_buckets(&self) -> &[u16; 32] {
1846 if self.source_less_than_target {
1847 &self.tracker.min_liquidity_offset_history.buckets
1849 &self.tracker.max_liquidity_offset_history.buckets
1853 pub(super) fn max_liquidity_offset_history_buckets(&self) -> &[u16; 32] {
1854 if self.source_less_than_target {
1855 &self.tracker.max_liquidity_offset_history.buckets
1857 &self.tracker.min_liquidity_offset_history.buckets
1862 pub(super) fn calculate_success_probability_times_billion(
1863 &self, params: &ProbabilisticScoringFeeParameters, amount_msat: u64,
1866 // If historical penalties are enabled, we try to calculate a probability of success
1867 // given our historical distribution of min- and max-liquidity bounds in a channel.
1868 // To do so, we walk the set of historical liquidity bucket (min, max) combinations
1869 // (where min_idx < max_idx, as having a minimum above our maximum is an invalid
1870 // state). For each pair, we calculate the probability as if the bucket's corresponding
1871 // min- and max- liquidity bounds were our current liquidity bounds and then multiply
1872 // that probability by the weight of the selected buckets.
1873 let payment_pos = amount_to_pos(amount_msat, capacity_msat);
1874 if payment_pos >= POSITION_TICKS { return None; }
1876 let min_liquidity_offset_history_buckets =
1877 self.min_liquidity_offset_history_buckets();
1878 let max_liquidity_offset_history_buckets =
1879 self.max_liquidity_offset_history_buckets();
1881 let total_valid_points_tracked = self.tracker.total_valid_points_tracked;
1882 #[cfg(debug_assertions)] {
1883 let mut actual_valid_points_tracked = 0;
1884 for (min_idx, min_bucket) in min_liquidity_offset_history_buckets.iter().enumerate() {
1885 for max_bucket in max_liquidity_offset_history_buckets.iter().take(32 - min_idx) {
1886 actual_valid_points_tracked += (*min_bucket as u64) * (*max_bucket as u64);
1889 assert_eq!(total_valid_points_tracked, actual_valid_points_tracked);
1892 // If the total valid points is smaller than 1.0 (i.e. 32 in our fixed-point scheme),
1893 // treat it as if we were fully decayed.
1894 const FULLY_DECAYED: u16 = BUCKET_FIXED_POINT_ONE * BUCKET_FIXED_POINT_ONE;
1895 if total_valid_points_tracked < FULLY_DECAYED.into() {
1899 let mut cumulative_success_prob_times_billion = 0;
1900 let mut cumulative_float_success_prob = 0.0;
1901 macro_rules! zero_min_bucket { ($prob: ident, $accum: ident) => { {
1902 // Special-case the 0th min bucket - it generally means we failed a payment, so only
1903 // consider the highest (i.e. largest-offset-from-max-capacity) max bucket for all
1904 // points against the 0th min bucket. This avoids the case where we fail to route
1905 // increasingly lower values over a channel, but treat each failure as a separate
1906 // datapoint, many of which may have relatively high maximum-available-liquidity
1907 // values, which will result in us thinking we have some nontrivial probability of
1908 // routing up to that amount.
1909 if min_liquidity_offset_history_buckets[0] != 0 {
1910 let mut highest_max_bucket_with_points = 0; // The highest max-bucket with any data
1911 let mut total_max_points = 0; // Total points in max-buckets to consider
1912 for (max_idx, max_bucket) in max_liquidity_offset_history_buckets.iter().enumerate() {
1913 if *max_bucket >= BUCKET_FIXED_POINT_ONE {
1914 highest_max_bucket_with_points = cmp::max(highest_max_bucket_with_points, max_idx);
1916 total_max_points += *max_bucket as u64;
1918 let max_bucket_end_pos = BUCKET_START_POS[32 - highest_max_bucket_with_points] - 1;
1919 if payment_pos < max_bucket_end_pos {
1920 let bucket_points = (min_liquidity_offset_history_buckets[0] as u64) * total_max_points;
1922 payment_pos, 0, max_bucket_end_pos,
1923 POSITION_TICKS - 1, true,
1924 bucket_points, total_valid_points_tracked
1929 if params.linear_success_probability {
1930 zero_min_bucket!(linear_success_probability_times_value_times_billion, cumulative_success_prob_times_billion);
1932 zero_min_bucket!(nonlinear_success_probability_f, cumulative_float_success_prob);
1935 let total_points_float = total_valid_points_tracked as f32;
1936 let total_points_simd = FourF32::new(
1937 total_points_float, total_points_float, total_points_float, total_points_float,
1940 macro_rules! main_liq_loop { ($prob: ident, $accum: ident) => { {
1941 for (min_idx, min_bucket) in min_liquidity_offset_history_buckets.iter().enumerate().skip(1) {
1942 let min_bucket_start_pos = BUCKET_START_POS[min_idx];
1943 let max_max_idx = 31 - min_idx;
1944 let min_bucket_float = *min_bucket as f32;
1945 let min_bucket_simd = FourF32::new(
1946 min_bucket_float, min_bucket_float, min_bucket_float, min_bucket_float
1948 if payment_pos < min_bucket_start_pos {
1949 for (idx, chunk) in max_liquidity_offset_history_buckets.chunks(4).enumerate() {
1950 let (max_idx_a, max_idx_b, max_idx_c, max_idx_d) =
1951 (idx * 4, idx * 4 + 1, idx * 4 + 2, idx * 4 + 3);
1953 let max_bucket_a = chunk[0];
1954 let mut max_bucket_b = chunk[1];
1955 let mut max_bucket_c = chunk[2];
1956 let mut max_bucket_d = chunk[3];
1958 let max_bucket_end_pos_a = BUCKET_START_POS[32 - max_idx_a] - 1;
1959 if payment_pos >= max_bucket_end_pos_a || max_idx_a > max_max_idx {
1960 // Success probability 0, the payment amount may be above the max liquidity
1963 let max_bucket_end_pos_b = BUCKET_START_POS[32 - max_idx_b] - 1;
1964 if max_idx_b > max_max_idx || payment_pos >= max_bucket_end_pos_b { max_bucket_b = 0; }
1965 let max_bucket_end_pos_c = BUCKET_START_POS[32 - max_idx_c] - 1;
1966 if max_idx_c > max_max_idx || payment_pos >= max_bucket_end_pos_c { max_bucket_c = 0; }
1967 let max_bucket_end_pos_d = BUCKET_START_POS[32 - max_idx_d] - 1;
1968 if max_idx_d > max_max_idx || payment_pos >= max_bucket_end_pos_d { max_bucket_d = 0; }
1970 let buckets = FourF32::from_ints(max_bucket_a, max_bucket_b, max_bucket_c, max_bucket_d);
1972 let min_times_max = min_bucket_simd * buckets;
1973 let ratio = min_times_max / total_points_simd;
1974 cumulative_float_success_prob += ratio.consuming_sum();
1977 for (max_idx, max_bucket) in max_liquidity_offset_history_buckets.iter().enumerate().take(32 - min_idx) {
1978 let max_bucket_end_pos = BUCKET_START_POS[32 - max_idx] - 1;
1979 if payment_pos >= max_bucket_end_pos {
1980 // Success probability 0, the payment amount may be above the max liquidity
1983 // Note that this multiply can only barely not overflow - two 16 bit ints plus
1984 // 30 bits is 62 bits.
1985 let bucket_points = ((*min_bucket as u32) * (*max_bucket as u32)) as u64;
1987 payment_pos, min_bucket_start_pos,
1988 max_bucket_end_pos, POSITION_TICKS - 1, true,
1989 bucket_points, total_valid_points_tracked);
1994 if params.linear_success_probability {
1995 main_liq_loop!(linear_success_probability_times_value_times_billion, cumulative_success_prob_times_billion);
1997 main_liq_loop!(nonlinear_success_probability_f, cumulative_float_success_prob);
2000 const BILLIONISH: f32 = 1024.0 * 1024.0 * 1024.0;
2001 cumulative_success_prob_times_billion += (cumulative_float_success_prob * BILLIONISH) as u64;
2003 Some(cumulative_success_prob_times_billion)
2007 use bucketed_history::{LegacyHistoricalBucketRangeTracker, HistoricalBucketRangeTracker, DirectedHistoricalLiquidityTracker, HistoricalLiquidityTracker};
2009 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref> Writeable for ProbabilisticScorer<G, L> where L::Target: Logger {
2011 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
2012 write_tlv_fields!(w, {
2013 (0, self.channel_liquidities, required),
2019 impl<G: Deref<Target = NetworkGraph<L>>, L: Deref>
2020 ReadableArgs<(ProbabilisticScoringDecayParameters, G, L)> for ProbabilisticScorer<G, L> where L::Target: Logger {
2023 r: &mut R, args: (ProbabilisticScoringDecayParameters, G, L)
2024 ) -> Result<Self, DecodeError> {
2025 let (decay_params, network_graph, logger) = args;
2026 let mut channel_liquidities = HashMap::new();
2027 read_tlv_fields!(r, {
2028 (0, channel_liquidities, required),
2034 channel_liquidities,
2039 impl Writeable for ChannelLiquidity {
2041 fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
2042 write_tlv_fields!(w, {
2043 (0, self.min_liquidity_offset_msat, required),
2044 // 1 was the min_liquidity_offset_history in octile form
2045 (2, self.max_liquidity_offset_msat, required),
2046 // 3 was the max_liquidity_offset_history in octile form
2047 (4, self.last_updated, required),
2048 (5, self.liquidity_history.writeable_min_offset_history(), required),
2049 (7, self.liquidity_history.writeable_max_offset_history(), required),
2050 (9, self.offset_history_last_updated, required),
2056 impl Readable for ChannelLiquidity {
2058 fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
2059 let mut min_liquidity_offset_msat = 0;
2060 let mut max_liquidity_offset_msat = 0;
2061 let mut legacy_min_liq_offset_history: Option<LegacyHistoricalBucketRangeTracker> = None;
2062 let mut legacy_max_liq_offset_history: Option<LegacyHistoricalBucketRangeTracker> = None;
2063 let mut min_liquidity_offset_history: Option<HistoricalBucketRangeTracker> = None;
2064 let mut max_liquidity_offset_history: Option<HistoricalBucketRangeTracker> = None;
2065 let mut last_updated = Duration::from_secs(0);
2066 let mut offset_history_last_updated = None;
2067 read_tlv_fields!(r, {
2068 (0, min_liquidity_offset_msat, required),
2069 (1, legacy_min_liq_offset_history, option),
2070 (2, max_liquidity_offset_msat, required),
2071 (3, legacy_max_liq_offset_history, option),
2072 (4, last_updated, required),
2073 (5, min_liquidity_offset_history, option),
2074 (7, max_liquidity_offset_history, option),
2075 (9, offset_history_last_updated, option),
2078 if min_liquidity_offset_history.is_none() {
2079 if let Some(legacy_buckets) = legacy_min_liq_offset_history {
2080 min_liquidity_offset_history = Some(legacy_buckets.into_current());
2082 min_liquidity_offset_history = Some(HistoricalBucketRangeTracker::new());
2085 if max_liquidity_offset_history.is_none() {
2086 if let Some(legacy_buckets) = legacy_max_liq_offset_history {
2087 max_liquidity_offset_history = Some(legacy_buckets.into_current());
2089 max_liquidity_offset_history = Some(HistoricalBucketRangeTracker::new());
2093 min_liquidity_offset_msat,
2094 max_liquidity_offset_msat,
2095 liquidity_history: HistoricalLiquidityTracker::from_min_max(
2096 min_liquidity_offset_history.unwrap(), max_liquidity_offset_history.unwrap()
2099 offset_history_last_updated: offset_history_last_updated.unwrap_or(last_updated),
2106 use super::{ChannelLiquidity, HistoricalLiquidityTracker, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters, ProbabilisticScorer};
2107 use crate::blinded_path::{BlindedHop, BlindedPath};
2108 use crate::util::config::UserConfig;
2110 use crate::ln::channelmanager;
2111 use crate::ln::msgs::{ChannelAnnouncement, ChannelUpdate, UnsignedChannelAnnouncement, UnsignedChannelUpdate};
2112 use crate::routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId};
2113 use crate::routing::router::{BlindedTail, Path, RouteHop, CandidateRouteHop};
2114 use crate::routing::scoring::{ChannelUsage, ScoreLookUp, ScoreUpdate};
2115 use crate::util::ser::{ReadableArgs, Writeable};
2116 use crate::util::test_utils::{self, TestLogger};
2118 use bitcoin::blockdata::constants::ChainHash;
2119 use bitcoin::hashes::Hash;
2120 use bitcoin::hashes::sha256d::Hash as Sha256dHash;
2121 use bitcoin::network::constants::Network;
2122 use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey};
2123 use core::time::Duration;
2126 fn source_privkey() -> SecretKey {
2127 SecretKey::from_slice(&[42; 32]).unwrap()
2130 fn target_privkey() -> SecretKey {
2131 SecretKey::from_slice(&[43; 32]).unwrap()
2134 fn source_pubkey() -> PublicKey {
2135 let secp_ctx = Secp256k1::new();
2136 PublicKey::from_secret_key(&secp_ctx, &source_privkey())
2139 fn target_pubkey() -> PublicKey {
2140 let secp_ctx = Secp256k1::new();
2141 PublicKey::from_secret_key(&secp_ctx, &target_privkey())
2144 fn source_node_id() -> NodeId {
2145 NodeId::from_pubkey(&source_pubkey())
2148 fn target_node_id() -> NodeId {
2149 NodeId::from_pubkey(&target_pubkey())
2152 // `ProbabilisticScorer` tests
2154 fn sender_privkey() -> SecretKey {
2155 SecretKey::from_slice(&[41; 32]).unwrap()
2158 fn recipient_privkey() -> SecretKey {
2159 SecretKey::from_slice(&[45; 32]).unwrap()
2162 fn sender_pubkey() -> PublicKey {
2163 let secp_ctx = Secp256k1::new();
2164 PublicKey::from_secret_key(&secp_ctx, &sender_privkey())
2167 fn recipient_pubkey() -> PublicKey {
2168 let secp_ctx = Secp256k1::new();
2169 PublicKey::from_secret_key(&secp_ctx, &recipient_privkey())
2172 fn recipient_node_id() -> NodeId {
2173 NodeId::from_pubkey(&recipient_pubkey())
2176 fn network_graph(logger: &TestLogger) -> NetworkGraph<&TestLogger> {
2177 let mut network_graph = NetworkGraph::new(Network::Testnet, logger);
2178 add_channel(&mut network_graph, 42, source_privkey(), target_privkey());
2179 add_channel(&mut network_graph, 43, target_privkey(), recipient_privkey());
2185 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_1_key: SecretKey,
2186 node_2_key: SecretKey
2188 let genesis_hash = ChainHash::using_genesis_block(Network::Testnet);
2189 let node_1_secret = &SecretKey::from_slice(&[39; 32]).unwrap();
2190 let node_2_secret = &SecretKey::from_slice(&[40; 32]).unwrap();
2191 let secp_ctx = Secp256k1::new();
2192 let unsigned_announcement = UnsignedChannelAnnouncement {
2193 features: channelmanager::provided_channel_features(&UserConfig::default()),
2194 chain_hash: genesis_hash,
2196 node_id_1: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_1_key)),
2197 node_id_2: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_2_key)),
2198 bitcoin_key_1: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_1_secret)),
2199 bitcoin_key_2: NodeId::from_pubkey(&PublicKey::from_secret_key(&secp_ctx, &node_2_secret)),
2200 excess_data: Vec::new(),
2202 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
2203 let signed_announcement = ChannelAnnouncement {
2204 node_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_key),
2205 node_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_key),
2206 bitcoin_signature_1: secp_ctx.sign_ecdsa(&msghash, &node_1_secret),
2207 bitcoin_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_secret),
2208 contents: unsigned_announcement,
2210 let chain_source: Option<&crate::util::test_utils::TestChainSource> = None;
2211 network_graph.update_channel_from_announcement(
2212 &signed_announcement, &chain_source).unwrap();
2213 update_channel(network_graph, short_channel_id, node_1_key, 0, 1_000, 100);
2214 update_channel(network_graph, short_channel_id, node_2_key, 1, 0, 100);
2218 network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_key: SecretKey,
2219 flags: u8, htlc_maximum_msat: u64, timestamp: u32,
2221 let genesis_hash = ChainHash::using_genesis_block(Network::Testnet);
2222 let secp_ctx = Secp256k1::new();
2223 let unsigned_update = UnsignedChannelUpdate {
2224 chain_hash: genesis_hash,
2228 cltv_expiry_delta: 18,
2229 htlc_minimum_msat: 0,
2232 fee_proportional_millionths: 0,
2233 excess_data: Vec::new(),
2235 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_update.encode()[..])[..]);
2236 let signed_update = ChannelUpdate {
2237 signature: secp_ctx.sign_ecdsa(&msghash, &node_key),
2238 contents: unsigned_update,
2240 network_graph.update_channel(&signed_update).unwrap();
2243 fn path_hop(pubkey: PublicKey, short_channel_id: u64, fee_msat: u64) -> RouteHop {
2244 let config = UserConfig::default();
2247 node_features: channelmanager::provided_node_features(&config),
2249 channel_features: channelmanager::provided_channel_features(&config),
2251 cltv_expiry_delta: 18,
2252 maybe_announced_channel: true,
2256 fn payment_path_for_amount(amount_msat: u64) -> Path {
2259 path_hop(source_pubkey(), 41, 1),
2260 path_hop(target_pubkey(), 42, 2),
2261 path_hop(recipient_pubkey(), 43, amount_msat),
2262 ], blinded_tail: None,
2267 fn liquidity_bounds_directed_from_lowest_node_id() {
2268 let logger = TestLogger::new();
2269 let last_updated = Duration::ZERO;
2270 let offset_history_last_updated = Duration::ZERO;
2271 let network_graph = network_graph(&logger);
2272 let decay_params = ProbabilisticScoringDecayParameters::default();
2273 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2276 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100,
2277 last_updated, offset_history_last_updated,
2278 liquidity_history: HistoricalLiquidityTracker::new(),
2282 min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100,
2283 last_updated, offset_history_last_updated,
2284 liquidity_history: HistoricalLiquidityTracker::new(),
2286 let source = source_node_id();
2287 let target = target_node_id();
2288 let recipient = recipient_node_id();
2289 assert!(source > target);
2290 assert!(target < recipient);
2292 // Update minimum liquidity.
2294 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2295 .as_directed(&source, &target, 1_000);
2296 assert_eq!(liquidity.min_liquidity_msat(), 100);
2297 assert_eq!(liquidity.max_liquidity_msat(), 300);
2299 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2300 .as_directed(&target, &source, 1_000);
2301 assert_eq!(liquidity.min_liquidity_msat(), 700);
2302 assert_eq!(liquidity.max_liquidity_msat(), 900);
2304 scorer.channel_liquidities.get_mut(&42).unwrap()
2305 .as_directed_mut(&source, &target, 1_000)
2306 .set_min_liquidity_msat(200, Duration::ZERO);
2308 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2309 .as_directed(&source, &target, 1_000);
2310 assert_eq!(liquidity.min_liquidity_msat(), 200);
2311 assert_eq!(liquidity.max_liquidity_msat(), 300);
2313 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2314 .as_directed(&target, &source, 1_000);
2315 assert_eq!(liquidity.min_liquidity_msat(), 700);
2316 assert_eq!(liquidity.max_liquidity_msat(), 800);
2318 // Update maximum liquidity.
2320 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2321 .as_directed(&target, &recipient, 1_000);
2322 assert_eq!(liquidity.min_liquidity_msat(), 700);
2323 assert_eq!(liquidity.max_liquidity_msat(), 900);
2325 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2326 .as_directed(&recipient, &target, 1_000);
2327 assert_eq!(liquidity.min_liquidity_msat(), 100);
2328 assert_eq!(liquidity.max_liquidity_msat(), 300);
2330 scorer.channel_liquidities.get_mut(&43).unwrap()
2331 .as_directed_mut(&target, &recipient, 1_000)
2332 .set_max_liquidity_msat(200, Duration::ZERO);
2334 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2335 .as_directed(&target, &recipient, 1_000);
2336 assert_eq!(liquidity.min_liquidity_msat(), 0);
2337 assert_eq!(liquidity.max_liquidity_msat(), 200);
2339 let liquidity = scorer.channel_liquidities.get(&43).unwrap()
2340 .as_directed(&recipient, &target, 1_000);
2341 assert_eq!(liquidity.min_liquidity_msat(), 800);
2342 assert_eq!(liquidity.max_liquidity_msat(), 1000);
2346 fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() {
2347 let logger = TestLogger::new();
2348 let last_updated = Duration::ZERO;
2349 let offset_history_last_updated = Duration::ZERO;
2350 let network_graph = network_graph(&logger);
2351 let decay_params = ProbabilisticScoringDecayParameters::default();
2352 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2355 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400,
2356 last_updated, offset_history_last_updated,
2357 liquidity_history: HistoricalLiquidityTracker::new(),
2359 let source = source_node_id();
2360 let target = target_node_id();
2361 assert!(source > target);
2363 // Check initial bounds.
2364 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2365 .as_directed(&source, &target, 1_000);
2366 assert_eq!(liquidity.min_liquidity_msat(), 400);
2367 assert_eq!(liquidity.max_liquidity_msat(), 800);
2369 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2370 .as_directed(&target, &source, 1_000);
2371 assert_eq!(liquidity.min_liquidity_msat(), 200);
2372 assert_eq!(liquidity.max_liquidity_msat(), 600);
2374 // Reset from source to target.
2375 scorer.channel_liquidities.get_mut(&42).unwrap()
2376 .as_directed_mut(&source, &target, 1_000)
2377 .set_min_liquidity_msat(900, Duration::ZERO);
2379 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2380 .as_directed(&source, &target, 1_000);
2381 assert_eq!(liquidity.min_liquidity_msat(), 900);
2382 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2384 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2385 .as_directed(&target, &source, 1_000);
2386 assert_eq!(liquidity.min_liquidity_msat(), 0);
2387 assert_eq!(liquidity.max_liquidity_msat(), 100);
2389 // Reset from target to source.
2390 scorer.channel_liquidities.get_mut(&42).unwrap()
2391 .as_directed_mut(&target, &source, 1_000)
2392 .set_min_liquidity_msat(400, Duration::ZERO);
2394 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2395 .as_directed(&source, &target, 1_000);
2396 assert_eq!(liquidity.min_liquidity_msat(), 0);
2397 assert_eq!(liquidity.max_liquidity_msat(), 600);
2399 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2400 .as_directed(&target, &source, 1_000);
2401 assert_eq!(liquidity.min_liquidity_msat(), 400);
2402 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2406 fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() {
2407 let logger = TestLogger::new();
2408 let last_updated = Duration::ZERO;
2409 let offset_history_last_updated = Duration::ZERO;
2410 let network_graph = network_graph(&logger);
2411 let decay_params = ProbabilisticScoringDecayParameters::default();
2412 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2415 min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400,
2416 last_updated, offset_history_last_updated,
2417 liquidity_history: HistoricalLiquidityTracker::new(),
2419 let source = source_node_id();
2420 let target = target_node_id();
2421 assert!(source > target);
2423 // Check initial bounds.
2424 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2425 .as_directed(&source, &target, 1_000);
2426 assert_eq!(liquidity.min_liquidity_msat(), 400);
2427 assert_eq!(liquidity.max_liquidity_msat(), 800);
2429 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2430 .as_directed(&target, &source, 1_000);
2431 assert_eq!(liquidity.min_liquidity_msat(), 200);
2432 assert_eq!(liquidity.max_liquidity_msat(), 600);
2434 // Reset from source to target.
2435 scorer.channel_liquidities.get_mut(&42).unwrap()
2436 .as_directed_mut(&source, &target, 1_000)
2437 .set_max_liquidity_msat(300, Duration::ZERO);
2439 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2440 .as_directed(&source, &target, 1_000);
2441 assert_eq!(liquidity.min_liquidity_msat(), 0);
2442 assert_eq!(liquidity.max_liquidity_msat(), 300);
2444 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2445 .as_directed(&target, &source, 1_000);
2446 assert_eq!(liquidity.min_liquidity_msat(), 700);
2447 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2449 // Reset from target to source.
2450 scorer.channel_liquidities.get_mut(&42).unwrap()
2451 .as_directed_mut(&target, &source, 1_000)
2452 .set_max_liquidity_msat(600, Duration::ZERO);
2454 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2455 .as_directed(&source, &target, 1_000);
2456 assert_eq!(liquidity.min_liquidity_msat(), 400);
2457 assert_eq!(liquidity.max_liquidity_msat(), 1_000);
2459 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
2460 .as_directed(&target, &source, 1_000);
2461 assert_eq!(liquidity.min_liquidity_msat(), 0);
2462 assert_eq!(liquidity.max_liquidity_msat(), 600);
2466 fn increased_penalty_nearing_liquidity_upper_bound() {
2467 let logger = TestLogger::new();
2468 let network_graph = network_graph(&logger);
2469 let params = ProbabilisticScoringFeeParameters {
2470 liquidity_penalty_multiplier_msat: 1_000,
2471 ..ProbabilisticScoringFeeParameters::zero_penalty()
2473 let decay_params = ProbabilisticScoringDecayParameters::default();
2474 let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2475 let source = source_node_id();
2477 let usage = ChannelUsage {
2479 inflight_htlc_msat: 0,
2480 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
2482 let network_graph = network_graph.read_only();
2483 let channel = network_graph.channel(42).unwrap();
2484 let (info, _) = channel.as_directed_from(&source).unwrap();
2485 let candidate = CandidateRouteHop::PublicHop {
2487 short_channel_id: 42,
2489 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
2490 let usage = ChannelUsage { amount_msat: 10_240, ..usage };
2491 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
2492 let usage = ChannelUsage { amount_msat: 102_400, ..usage };
2493 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 47);
2494 let usage = ChannelUsage { amount_msat: 1_023_999, ..usage };
2495 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 2_000);
2497 let usage = ChannelUsage {
2499 inflight_htlc_msat: 0,
2500 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2502 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 58);
2503 let usage = ChannelUsage { amount_msat: 256, ..usage };
2504 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 125);
2505 let usage = ChannelUsage { amount_msat: 374, ..usage };
2506 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 198);
2507 let usage = ChannelUsage { amount_msat: 512, ..usage };
2508 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300);
2509 let usage = ChannelUsage { amount_msat: 640, ..usage };
2510 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 425);
2511 let usage = ChannelUsage { amount_msat: 768, ..usage };
2512 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 602);
2513 let usage = ChannelUsage { amount_msat: 896, ..usage };
2514 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 902);
2518 fn constant_penalty_outside_liquidity_bounds() {
2519 let logger = TestLogger::new();
2520 let last_updated = Duration::ZERO;
2521 let offset_history_last_updated = Duration::ZERO;
2522 let network_graph = network_graph(&logger);
2523 let params = ProbabilisticScoringFeeParameters {
2524 liquidity_penalty_multiplier_msat: 1_000,
2525 considered_impossible_penalty_msat: u64::max_value(),
2526 ..ProbabilisticScoringFeeParameters::zero_penalty()
2528 let decay_params = ProbabilisticScoringDecayParameters {
2529 ..ProbabilisticScoringDecayParameters::zero_penalty()
2531 let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
2534 min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40,
2535 last_updated, offset_history_last_updated,
2536 liquidity_history: HistoricalLiquidityTracker::new(),
2538 let source = source_node_id();
2540 let usage = ChannelUsage {
2542 inflight_htlc_msat: 0,
2543 effective_capacity: EffectiveCapacity::Total { capacity_msat: 100, htlc_maximum_msat: 1_000 },
2545 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2546 let (info, _) = channel.as_directed_from(&source).unwrap();
2547 let candidate = CandidateRouteHop::PublicHop {
2549 short_channel_id: 42,
2551 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
2552 let usage = ChannelUsage { amount_msat: 50, ..usage };
2553 assert_ne!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
2554 assert_ne!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
2555 let usage = ChannelUsage { amount_msat: 61, ..usage };
2556 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
2560 fn does_not_further_penalize_own_channel() {
2561 let logger = TestLogger::new();
2562 let network_graph = network_graph(&logger);
2563 let params = ProbabilisticScoringFeeParameters {
2564 liquidity_penalty_multiplier_msat: 1_000,
2565 ..ProbabilisticScoringFeeParameters::zero_penalty()
2567 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2568 let source = source_node_id();
2569 let usage = ChannelUsage {
2571 inflight_htlc_msat: 0,
2572 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2574 let failed_path = payment_path_for_amount(500);
2575 let successful_path = payment_path_for_amount(200);
2576 let channel = &network_graph.read_only().channel(42).unwrap().to_owned();
2577 let (info, _) = channel.as_directed_from(&source).unwrap();
2578 let candidate = CandidateRouteHop::PublicHop {
2580 short_channel_id: 41,
2583 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 301);
2585 scorer.payment_path_failed(&failed_path, 41, Duration::ZERO);
2586 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 301);
2588 scorer.payment_path_successful(&successful_path, Duration::ZERO);
2589 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 301);
2593 fn sets_liquidity_lower_bound_on_downstream_failure() {
2594 let logger = TestLogger::new();
2595 let network_graph = network_graph(&logger);
2596 let params = ProbabilisticScoringFeeParameters {
2597 liquidity_penalty_multiplier_msat: 1_000,
2598 ..ProbabilisticScoringFeeParameters::zero_penalty()
2600 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2601 let source = source_node_id();
2602 let path = payment_path_for_amount(500);
2604 let usage = ChannelUsage {
2606 inflight_htlc_msat: 0,
2607 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2609 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2610 let (info, _) = channel.as_directed_from(&source).unwrap();
2611 let candidate = CandidateRouteHop::PublicHop {
2613 short_channel_id: 42,
2615 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 128);
2616 let usage = ChannelUsage { amount_msat: 500, ..usage };
2617 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 301);
2618 let usage = ChannelUsage { amount_msat: 750, ..usage };
2619 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 602);
2621 scorer.payment_path_failed(&path, 43, Duration::ZERO);
2623 let usage = ChannelUsage { amount_msat: 250, ..usage };
2624 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
2625 let usage = ChannelUsage { amount_msat: 500, ..usage };
2626 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
2627 let usage = ChannelUsage { amount_msat: 750, ..usage };
2628 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300);
2632 fn sets_liquidity_upper_bound_on_failure() {
2633 let logger = TestLogger::new();
2634 let network_graph = network_graph(&logger);
2635 let params = ProbabilisticScoringFeeParameters {
2636 liquidity_penalty_multiplier_msat: 1_000,
2637 considered_impossible_penalty_msat: u64::max_value(),
2638 ..ProbabilisticScoringFeeParameters::zero_penalty()
2640 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2641 let source = source_node_id();
2642 let path = payment_path_for_amount(500);
2644 let usage = ChannelUsage {
2646 inflight_htlc_msat: 0,
2647 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2649 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2650 let (info, _) = channel.as_directed_from(&source).unwrap();
2651 let candidate = CandidateRouteHop::PublicHop {
2653 short_channel_id: 42,
2655 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 128);
2656 let usage = ChannelUsage { amount_msat: 500, ..usage };
2657 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 301);
2658 let usage = ChannelUsage { amount_msat: 750, ..usage };
2659 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 602);
2661 scorer.payment_path_failed(&path, 42, Duration::ZERO);
2663 let usage = ChannelUsage { amount_msat: 250, ..usage };
2664 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300);
2665 let usage = ChannelUsage { amount_msat: 500, ..usage };
2666 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
2667 let usage = ChannelUsage { amount_msat: 750, ..usage };
2668 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
2672 fn ignores_channels_after_removed_failed_channel() {
2673 // Previously, if we'd tried to send over a channel which was removed from the network
2674 // graph before we call `payment_path_failed` (which is the default if the we get a "no
2675 // such channel" error in the `InvoicePayer`), we would call `failed_downstream` on all
2676 // channels in the route, even ones which they payment never reached. This tests to ensure
2677 // we do not score such channels.
2678 let secp_ctx = Secp256k1::new();
2679 let logger = TestLogger::new();
2680 let mut network_graph = NetworkGraph::new(Network::Testnet, &logger);
2681 let secret_a = SecretKey::from_slice(&[42; 32]).unwrap();
2682 let secret_b = SecretKey::from_slice(&[43; 32]).unwrap();
2683 let secret_c = SecretKey::from_slice(&[44; 32]).unwrap();
2684 let secret_d = SecretKey::from_slice(&[45; 32]).unwrap();
2685 add_channel(&mut network_graph, 42, secret_a, secret_b);
2686 // Don't add the channel from B -> C.
2687 add_channel(&mut network_graph, 44, secret_c, secret_d);
2689 let pub_a = PublicKey::from_secret_key(&secp_ctx, &secret_a);
2690 let pub_b = PublicKey::from_secret_key(&secp_ctx, &secret_b);
2691 let pub_c = PublicKey::from_secret_key(&secp_ctx, &secret_c);
2692 let pub_d = PublicKey::from_secret_key(&secp_ctx, &secret_d);
2695 path_hop(pub_b, 42, 1),
2696 path_hop(pub_c, 43, 2),
2697 path_hop(pub_d, 44, 100),
2700 let node_a = NodeId::from_pubkey(&pub_a);
2701 let node_b = NodeId::from_pubkey(&pub_b);
2702 let node_c = NodeId::from_pubkey(&pub_c);
2704 let params = ProbabilisticScoringFeeParameters {
2705 liquidity_penalty_multiplier_msat: 1_000,
2706 ..ProbabilisticScoringFeeParameters::zero_penalty()
2708 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2710 let usage = ChannelUsage {
2712 inflight_htlc_msat: 0,
2713 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2715 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2716 let (info, _) = channel.as_directed_from(&node_a).unwrap();
2717 let candidate = CandidateRouteHop::PublicHop {
2719 short_channel_id: 42,
2721 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 128);
2722 // Note that a default liquidity bound is used for B -> C as no channel exists
2723 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2724 let (info, _) = channel.as_directed_from(&node_b).unwrap();
2725 let candidate = CandidateRouteHop::PublicHop {
2727 short_channel_id: 43,
2729 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 128);
2730 let channel = network_graph.read_only().channel(44).unwrap().to_owned();
2731 let (info, _) = channel.as_directed_from(&node_c).unwrap();
2732 let candidate = CandidateRouteHop::PublicHop {
2734 short_channel_id: 44,
2736 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 128);
2738 scorer.payment_path_failed(&Path { hops: path, blinded_tail: None }, 43, Duration::ZERO);
2740 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2741 let (info, _) = channel.as_directed_from(&node_a).unwrap();
2742 let candidate = CandidateRouteHop::PublicHop {
2744 short_channel_id: 42,
2746 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 80);
2747 // Note that a default liquidity bound is used for B -> C as no channel exists
2748 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2749 let (info, _) = channel.as_directed_from(&node_b).unwrap();
2750 let candidate = CandidateRouteHop::PublicHop {
2752 short_channel_id: 43,
2754 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 128);
2755 let channel = network_graph.read_only().channel(44).unwrap().to_owned();
2756 let (info, _) = channel.as_directed_from(&node_c).unwrap();
2757 let candidate = CandidateRouteHop::PublicHop {
2759 short_channel_id: 44,
2761 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 128);
2765 fn reduces_liquidity_upper_bound_along_path_on_success() {
2766 let logger = TestLogger::new();
2767 let network_graph = network_graph(&logger);
2768 let params = ProbabilisticScoringFeeParameters {
2769 liquidity_penalty_multiplier_msat: 1_000,
2770 ..ProbabilisticScoringFeeParameters::zero_penalty()
2772 let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
2773 let source = source_node_id();
2774 let usage = ChannelUsage {
2776 inflight_htlc_msat: 0,
2777 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2779 let network_graph = network_graph.read_only().channels().clone();
2780 let channel_42 = network_graph.get(&42).unwrap();
2781 let channel_43 = network_graph.get(&43).unwrap();
2782 let (info, _) = channel_42.as_directed_from(&source).unwrap();
2783 let candidate_41 = CandidateRouteHop::PublicHop {
2785 short_channel_id: 41,
2787 let (info, target) = channel_42.as_directed_from(&source).unwrap();
2788 let candidate_42 = CandidateRouteHop::PublicHop {
2790 short_channel_id: 42,
2792 let (info, _) = channel_43.as_directed_from(&target).unwrap();
2793 let candidate_43 = CandidateRouteHop::PublicHop {
2795 short_channel_id: 43,
2797 assert_eq!(scorer.channel_penalty_msat(&candidate_41, usage, ¶ms), 128);
2798 assert_eq!(scorer.channel_penalty_msat(&candidate_42, usage, ¶ms), 128);
2799 assert_eq!(scorer.channel_penalty_msat(&candidate_43, usage, ¶ms), 128);
2801 scorer.payment_path_successful(&payment_path_for_amount(500), Duration::ZERO);
2803 assert_eq!(scorer.channel_penalty_msat(&candidate_41, usage, ¶ms), 128);
2804 assert_eq!(scorer.channel_penalty_msat(&candidate_42, usage, ¶ms), 300);
2805 assert_eq!(scorer.channel_penalty_msat(&candidate_43, usage, ¶ms), 300);
2809 fn decays_liquidity_bounds_over_time() {
2810 let logger = TestLogger::new();
2811 let network_graph = network_graph(&logger);
2812 let params = ProbabilisticScoringFeeParameters {
2813 liquidity_penalty_multiplier_msat: 1_000,
2814 considered_impossible_penalty_msat: u64::max_value(),
2815 ..ProbabilisticScoringFeeParameters::zero_penalty()
2817 let decay_params = ProbabilisticScoringDecayParameters {
2818 liquidity_offset_half_life: Duration::from_secs(10),
2819 ..ProbabilisticScoringDecayParameters::zero_penalty()
2821 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2822 let source = source_node_id();
2824 let usage = ChannelUsage {
2826 inflight_htlc_msat: 0,
2827 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
2829 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2830 let (info, _) = channel.as_directed_from(&source).unwrap();
2831 let candidate = CandidateRouteHop::PublicHop {
2833 short_channel_id: 42,
2835 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
2836 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
2837 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 2_000);
2839 scorer.payment_path_failed(&payment_path_for_amount(768), 42, Duration::ZERO);
2840 scorer.payment_path_failed(&payment_path_for_amount(128), 43, Duration::ZERO);
2842 // Initial penalties
2843 let usage = ChannelUsage { amount_msat: 128, ..usage };
2844 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
2845 let usage = ChannelUsage { amount_msat: 256, ..usage };
2846 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 93);
2847 let usage = ChannelUsage { amount_msat: 768, ..usage };
2848 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 1_479);
2849 let usage = ChannelUsage { amount_msat: 896, ..usage };
2850 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
2852 // Half decay (i.e., three-quarter life)
2853 scorer.decay_liquidity_certainty(Duration::from_secs(5));
2854 let usage = ChannelUsage { amount_msat: 128, ..usage };
2855 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 22);
2856 let usage = ChannelUsage { amount_msat: 256, ..usage };
2857 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 106);
2858 let usage = ChannelUsage { amount_msat: 768, ..usage };
2859 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 921);
2860 let usage = ChannelUsage { amount_msat: 896, ..usage };
2861 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
2863 // One decay (i.e., half life)
2864 scorer.decay_liquidity_certainty(Duration::from_secs(10));
2865 let usage = ChannelUsage { amount_msat: 64, ..usage };
2866 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
2867 let usage = ChannelUsage { amount_msat: 128, ..usage };
2868 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 34);
2869 let usage = ChannelUsage { amount_msat: 896, ..usage };
2870 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 1_970);
2871 let usage = ChannelUsage { amount_msat: 960, ..usage };
2872 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
2874 // Fully decay liquidity lower bound.
2875 scorer.decay_liquidity_certainty(Duration::from_secs(10 * 8));
2876 let usage = ChannelUsage { amount_msat: 0, ..usage };
2877 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
2878 let usage = ChannelUsage { amount_msat: 1, ..usage };
2879 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
2880 let usage = ChannelUsage { amount_msat: 1_023, ..usage };
2881 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 2_000);
2882 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2883 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
2885 // Fully decay liquidity upper bound.
2886 scorer.decay_liquidity_certainty(Duration::from_secs(10 * 9));
2887 let usage = ChannelUsage { amount_msat: 0, ..usage };
2888 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
2889 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2890 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
2892 scorer.decay_liquidity_certainty(Duration::from_secs(10 * 10));
2893 let usage = ChannelUsage { amount_msat: 0, ..usage };
2894 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
2895 let usage = ChannelUsage { amount_msat: 1_024, ..usage };
2896 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
2900 fn restricts_liquidity_bounds_after_decay() {
2901 let logger = TestLogger::new();
2902 let network_graph = network_graph(&logger);
2903 let params = ProbabilisticScoringFeeParameters {
2904 liquidity_penalty_multiplier_msat: 1_000,
2905 ..ProbabilisticScoringFeeParameters::zero_penalty()
2907 let decay_params = ProbabilisticScoringDecayParameters {
2908 liquidity_offset_half_life: Duration::from_secs(10),
2909 ..ProbabilisticScoringDecayParameters::default()
2911 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2912 let source = source_node_id();
2913 let usage = ChannelUsage {
2915 inflight_htlc_msat: 0,
2916 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
2918 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2919 let (info, _) = channel.as_directed_from(&source).unwrap();
2920 let candidate = CandidateRouteHop::PublicHop {
2922 short_channel_id: 42,
2925 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300);
2927 // More knowledge gives higher confidence (256, 768), meaning a lower penalty.
2928 scorer.payment_path_failed(&payment_path_for_amount(768), 42, Duration::ZERO);
2929 scorer.payment_path_failed(&payment_path_for_amount(256), 43, Duration::ZERO);
2930 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 281);
2932 // Decaying knowledge gives less confidence (128, 896), meaning a higher penalty.
2933 scorer.decay_liquidity_certainty(Duration::from_secs(10));
2934 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 291);
2936 // Reducing the upper bound gives more confidence (128, 832) that the payment amount (512)
2937 // is closer to the upper bound, meaning a higher penalty.
2938 scorer.payment_path_successful(&payment_path_for_amount(64), Duration::from_secs(10));
2939 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 331);
2941 // Increasing the lower bound gives more confidence (256, 832) that the payment amount (512)
2942 // is closer to the lower bound, meaning a lower penalty.
2943 scorer.payment_path_failed(&payment_path_for_amount(256), 43, Duration::from_secs(10));
2944 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 245);
2946 // Further decaying affects the lower bound more than the upper bound (128, 928).
2947 scorer.decay_liquidity_certainty(Duration::from_secs(20));
2948 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 280);
2952 fn restores_persisted_liquidity_bounds() {
2953 let logger = TestLogger::new();
2954 let network_graph = network_graph(&logger);
2955 let params = ProbabilisticScoringFeeParameters {
2956 liquidity_penalty_multiplier_msat: 1_000,
2957 considered_impossible_penalty_msat: u64::max_value(),
2958 ..ProbabilisticScoringFeeParameters::zero_penalty()
2960 let decay_params = ProbabilisticScoringDecayParameters {
2961 liquidity_offset_half_life: Duration::from_secs(10),
2962 ..ProbabilisticScoringDecayParameters::default()
2964 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
2965 let source = source_node_id();
2966 let usage = ChannelUsage {
2968 inflight_htlc_msat: 0,
2969 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
2972 scorer.payment_path_failed(&payment_path_for_amount(500), 42, Duration::ZERO);
2973 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
2974 let (info, _) = channel.as_directed_from(&source).unwrap();
2975 let candidate = CandidateRouteHop::PublicHop {
2977 short_channel_id: 42,
2979 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
2981 scorer.decay_liquidity_certainty(Duration::from_secs(10));
2982 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 473);
2984 scorer.payment_path_failed(&payment_path_for_amount(250), 43, Duration::from_secs(10));
2985 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300);
2987 let mut serialized_scorer = Vec::new();
2988 scorer.write(&mut serialized_scorer).unwrap();
2990 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
2991 let deserialized_scorer =
2992 <ProbabilisticScorer<_, _>>::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap();
2993 assert_eq!(deserialized_scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300);
2996 fn do_decays_persisted_liquidity_bounds(decay_before_reload: bool) {
2997 let logger = TestLogger::new();
2998 let network_graph = network_graph(&logger);
2999 let params = ProbabilisticScoringFeeParameters {
3000 liquidity_penalty_multiplier_msat: 1_000,
3001 considered_impossible_penalty_msat: u64::max_value(),
3002 ..ProbabilisticScoringFeeParameters::zero_penalty()
3004 let decay_params = ProbabilisticScoringDecayParameters {
3005 liquidity_offset_half_life: Duration::from_secs(10),
3006 ..ProbabilisticScoringDecayParameters::zero_penalty()
3008 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3009 let source = source_node_id();
3010 let usage = ChannelUsage {
3012 inflight_htlc_msat: 0,
3013 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
3016 scorer.payment_path_failed(&payment_path_for_amount(500), 42, Duration::ZERO);
3017 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
3018 let (info, _) = channel.as_directed_from(&source).unwrap();
3019 let candidate = CandidateRouteHop::PublicHop {
3021 short_channel_id: 42,
3023 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
3025 if decay_before_reload {
3026 scorer.decay_liquidity_certainty(Duration::from_secs(10));
3029 let mut serialized_scorer = Vec::new();
3030 scorer.write(&mut serialized_scorer).unwrap();
3032 let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
3033 let mut deserialized_scorer =
3034 <ProbabilisticScorer<_, _>>::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap();
3035 if !decay_before_reload {
3036 scorer.decay_liquidity_certainty(Duration::from_secs(10));
3037 deserialized_scorer.decay_liquidity_certainty(Duration::from_secs(10));
3039 assert_eq!(deserialized_scorer.channel_penalty_msat(&candidate, usage, ¶ms), 473);
3041 scorer.payment_path_failed(&payment_path_for_amount(250), 43, Duration::from_secs(10));
3042 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300);
3044 deserialized_scorer.decay_liquidity_certainty(Duration::from_secs(20));
3045 assert_eq!(deserialized_scorer.channel_penalty_msat(&candidate, usage, ¶ms), 370);
3049 fn decays_persisted_liquidity_bounds() {
3050 do_decays_persisted_liquidity_bounds(false);
3051 do_decays_persisted_liquidity_bounds(true);
3055 fn scores_realistic_payments() {
3056 // Shows the scores of "realistic" sends of 100k sats over channels of 1-10m sats (with a
3057 // 50k sat reserve).
3058 let logger = TestLogger::new();
3059 let network_graph = network_graph(&logger);
3060 let params = ProbabilisticScoringFeeParameters::default();
3061 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3062 let source = source_node_id();
3064 let usage = ChannelUsage {
3065 amount_msat: 100_000_000,
3066 inflight_htlc_msat: 0,
3067 effective_capacity: EffectiveCapacity::Total { capacity_msat: 950_000_000, htlc_maximum_msat: 1_000 },
3069 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
3070 let (info, _) = channel.as_directed_from(&source).unwrap();
3071 let candidate = CandidateRouteHop::PublicHop {
3073 short_channel_id: 42,
3075 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 11497);
3076 let usage = ChannelUsage {
3077 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3079 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 7408);
3080 let usage = ChannelUsage {
3081 effective_capacity: EffectiveCapacity::Total { capacity_msat: 2_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3083 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 6151);
3084 let usage = ChannelUsage {
3085 effective_capacity: EffectiveCapacity::Total { capacity_msat: 3_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3087 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 5427);
3088 let usage = ChannelUsage {
3089 effective_capacity: EffectiveCapacity::Total { capacity_msat: 4_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3091 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 4955);
3092 let usage = ChannelUsage {
3093 effective_capacity: EffectiveCapacity::Total { capacity_msat: 5_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3095 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 4736);
3096 let usage = ChannelUsage {
3097 effective_capacity: EffectiveCapacity::Total { capacity_msat: 6_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3099 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 4484);
3100 let usage = ChannelUsage {
3101 effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_450_000_000, htlc_maximum_msat: 1_000 }, ..usage
3103 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 4484);
3104 let usage = ChannelUsage {
3105 effective_capacity: EffectiveCapacity::Total { capacity_msat: 7_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3107 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 4263);
3108 let usage = ChannelUsage {
3109 effective_capacity: EffectiveCapacity::Total { capacity_msat: 8_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3111 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 4263);
3112 let usage = ChannelUsage {
3113 effective_capacity: EffectiveCapacity::Total { capacity_msat: 9_950_000_000, htlc_maximum_msat: 1_000 }, ..usage
3115 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 4044);
3119 fn adds_base_penalty_to_liquidity_penalty() {
3120 let logger = TestLogger::new();
3121 let network_graph = network_graph(&logger);
3122 let source = source_node_id();
3123 let usage = ChannelUsage {
3125 inflight_htlc_msat: 0,
3126 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
3129 let params = ProbabilisticScoringFeeParameters {
3130 liquidity_penalty_multiplier_msat: 1_000,
3131 ..ProbabilisticScoringFeeParameters::zero_penalty()
3133 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3134 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
3135 let (info, _) = channel.as_directed_from(&source).unwrap();
3136 let candidate = CandidateRouteHop::PublicHop {
3138 short_channel_id: 42,
3140 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 58);
3142 let params = ProbabilisticScoringFeeParameters {
3143 base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000,
3144 anti_probing_penalty_msat: 0, ..ProbabilisticScoringFeeParameters::zero_penalty()
3146 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3147 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 558);
3149 let params = ProbabilisticScoringFeeParameters {
3150 base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000,
3151 base_penalty_amount_multiplier_msat: (1 << 30),
3152 anti_probing_penalty_msat: 0, ..ProbabilisticScoringFeeParameters::zero_penalty()
3155 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3156 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 558 + 128);
3160 fn adds_amount_penalty_to_liquidity_penalty() {
3161 let logger = TestLogger::new();
3162 let network_graph = network_graph(&logger);
3163 let source = source_node_id();
3164 let usage = ChannelUsage {
3165 amount_msat: 512_000,
3166 inflight_htlc_msat: 0,
3167 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
3170 let params = ProbabilisticScoringFeeParameters {
3171 liquidity_penalty_multiplier_msat: 1_000,
3172 liquidity_penalty_amount_multiplier_msat: 0,
3173 ..ProbabilisticScoringFeeParameters::zero_penalty()
3175 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3176 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
3177 let (info, _) = channel.as_directed_from(&source).unwrap();
3178 let candidate = CandidateRouteHop::PublicHop {
3180 short_channel_id: 42,
3182 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300);
3184 let params = ProbabilisticScoringFeeParameters {
3185 liquidity_penalty_multiplier_msat: 1_000,
3186 liquidity_penalty_amount_multiplier_msat: 256,
3187 ..ProbabilisticScoringFeeParameters::zero_penalty()
3189 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3190 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 337);
3194 fn calculates_log10_without_overflowing_u64_max_value() {
3195 let logger = TestLogger::new();
3196 let network_graph = network_graph(&logger);
3197 let source = source_node_id();
3198 let usage = ChannelUsage {
3199 amount_msat: u64::max_value(),
3200 inflight_htlc_msat: 0,
3201 effective_capacity: EffectiveCapacity::Infinite,
3203 let params = ProbabilisticScoringFeeParameters {
3204 liquidity_penalty_multiplier_msat: 40_000,
3205 ..ProbabilisticScoringFeeParameters::zero_penalty()
3207 let decay_params = ProbabilisticScoringDecayParameters::zero_penalty();
3208 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
3209 let (info, _) = channel.as_directed_from(&source).unwrap();
3210 let candidate = CandidateRouteHop::PublicHop {
3212 short_channel_id: 42,
3214 let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3215 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 80_000);
3219 fn accounts_for_inflight_htlc_usage() {
3220 let logger = TestLogger::new();
3221 let network_graph = network_graph(&logger);
3222 let params = ProbabilisticScoringFeeParameters {
3223 considered_impossible_penalty_msat: u64::max_value(),
3224 ..ProbabilisticScoringFeeParameters::zero_penalty()
3226 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3227 let source = source_node_id();
3229 let usage = ChannelUsage {
3231 inflight_htlc_msat: 0,
3232 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_000, htlc_maximum_msat: 1_000 },
3234 let network_graph = network_graph.read_only();
3235 let channel = network_graph.channel(42).unwrap();
3236 let (info, _) = channel.as_directed_from(&source).unwrap();
3237 let candidate = CandidateRouteHop::PublicHop {
3239 short_channel_id: 42,
3241 assert_ne!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
3243 let usage = ChannelUsage { inflight_htlc_msat: 251, ..usage };
3244 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
3248 fn removes_uncertainity_when_exact_liquidity_known() {
3249 let logger = TestLogger::new();
3250 let network_graph = network_graph(&logger);
3251 let params = ProbabilisticScoringFeeParameters::default();
3252 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3253 let source = source_node_id();
3255 let base_penalty_msat = params.base_penalty_msat;
3256 let usage = ChannelUsage {
3258 inflight_htlc_msat: 0,
3259 effective_capacity: EffectiveCapacity::ExactLiquidity { liquidity_msat: 1_000 },
3261 let network_graph = network_graph.read_only();
3262 let channel = network_graph.channel(42).unwrap();
3263 let (info, _) = channel.as_directed_from(&source).unwrap();
3264 let candidate = CandidateRouteHop::PublicHop {
3266 short_channel_id: 42,
3268 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), base_penalty_msat);
3270 let usage = ChannelUsage { amount_msat: 1_000, ..usage };
3271 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), base_penalty_msat);
3273 let usage = ChannelUsage { amount_msat: 1_001, ..usage };
3274 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
3278 fn remembers_historical_failures() {
3279 let logger = TestLogger::new();
3280 let network_graph = network_graph(&logger);
3281 let params = ProbabilisticScoringFeeParameters {
3282 historical_liquidity_penalty_multiplier_msat: 1024,
3283 historical_liquidity_penalty_amount_multiplier_msat: 1024,
3284 ..ProbabilisticScoringFeeParameters::zero_penalty()
3286 let decay_params = ProbabilisticScoringDecayParameters {
3287 liquidity_offset_half_life: Duration::from_secs(60 * 60),
3288 historical_no_updates_half_life: Duration::from_secs(10),
3290 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3291 let source = source_node_id();
3292 let target = target_node_id();
3294 let usage = ChannelUsage {
3296 inflight_htlc_msat: 0,
3297 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
3299 let usage_1 = ChannelUsage {
3301 inflight_htlc_msat: 0,
3302 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
3306 let network_graph = network_graph.read_only();
3307 let channel = network_graph.channel(42).unwrap();
3308 let (info, _) = channel.as_directed_from(&source).unwrap();
3309 let candidate = CandidateRouteHop::PublicHop {
3311 short_channel_id: 42,
3314 // With no historical data the normal liquidity penalty calculation is used.
3315 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 168);
3317 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3319 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 42, ¶ms),
3322 scorer.payment_path_failed(&payment_path_for_amount(1), 42, Duration::ZERO);
3324 let network_graph = network_graph.read_only();
3325 let channel = network_graph.channel(42).unwrap();
3326 let (info, _) = channel.as_directed_from(&source).unwrap();
3327 let candidate = CandidateRouteHop::PublicHop {
3329 short_channel_id: 42,
3332 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 2048);
3333 assert_eq!(scorer.channel_penalty_msat(&candidate, usage_1, ¶ms), 249);
3335 // The "it failed" increment is 32, where the probability should lie several buckets into
3336 // the first octile.
3337 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3338 Some(([32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
3339 [0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])));
3340 assert!(scorer.historical_estimated_payment_success_probability(42, &target, 1, ¶ms)
3342 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 500, ¶ms),
3345 // Even after we tell the scorer we definitely have enough available liquidity, it will
3346 // still remember that there was some failure in the past, and assign a non-0 penalty.
3347 scorer.payment_path_failed(&payment_path_for_amount(1000), 43, Duration::ZERO);
3349 let network_graph = network_graph.read_only();
3350 let channel = network_graph.channel(42).unwrap();
3351 let (info, _) = channel.as_directed_from(&source).unwrap();
3352 let candidate = CandidateRouteHop::PublicHop {
3354 short_channel_id: 42,
3357 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 105);
3359 // The first points should be decayed just slightly and the last bucket has a new point.
3360 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3361 Some(([31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0],
3362 [0, 0, 0, 0, 0, 0, 31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32])));
3364 // The exact success probability is a bit complicated and involves integer rounding, so we
3365 // simply check bounds here.
3366 let five_hundred_prob =
3367 scorer.historical_estimated_payment_success_probability(42, &target, 500, ¶ms).unwrap();
3368 assert!(five_hundred_prob > 0.59);
3369 assert!(five_hundred_prob < 0.60);
3371 scorer.historical_estimated_payment_success_probability(42, &target, 1, ¶ms).unwrap();
3372 assert!(one_prob < 0.85);
3373 assert!(one_prob > 0.84);
3375 // Advance the time forward 16 half-lives (which the docs claim will ensure all data is
3376 // gone), and check that we're back to where we started.
3377 scorer.decay_liquidity_certainty(Duration::from_secs(10 * 16));
3379 let network_graph = network_graph.read_only();
3380 let channel = network_graph.channel(42).unwrap();
3381 let (info, _) = channel.as_directed_from(&source).unwrap();
3382 let candidate = CandidateRouteHop::PublicHop {
3384 short_channel_id: 42,
3387 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 168);
3389 // Once fully decayed we still have data, but its all-0s. In the future we may remove the
3390 // data entirely instead.
3391 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3392 Some(([0; 32], [0; 32])));
3393 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 1, ¶ms), None);
3395 let mut usage = ChannelUsage {
3397 inflight_htlc_msat: 1024,
3398 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_024 },
3400 scorer.payment_path_failed(&payment_path_for_amount(1), 42, Duration::from_secs(10 * 16));
3402 let network_graph = network_graph.read_only();
3403 let channel = network_graph.channel(42).unwrap();
3404 let (info, _) = channel.as_directed_from(&source).unwrap();
3405 let candidate = CandidateRouteHop::PublicHop {
3407 short_channel_id: 42,
3410 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 2050);
3412 let usage = ChannelUsage {
3414 inflight_htlc_msat: 0,
3415 effective_capacity: EffectiveCapacity::AdvertisedMaxHTLC { amount_msat: 0 },
3417 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 2048);
3420 // Advance to decay all liquidity offsets to zero.
3421 scorer.decay_liquidity_certainty(Duration::from_secs(10 * (16 + 60 * 60)));
3423 // Once even the bounds have decayed information about the channel should be removed
3425 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3428 // Use a path in the opposite direction, which have zero for htlc_maximum_msat. This will
3429 // ensure that the effective capacity is zero to test division-by-zero edge cases.
3431 path_hop(target_pubkey(), 43, 2),
3432 path_hop(source_pubkey(), 42, 1),
3433 path_hop(sender_pubkey(), 41, 0),
3435 scorer.payment_path_failed(&Path { hops: path, blinded_tail: None }, 42, Duration::from_secs(10 * (16 + 60 * 60)));
3439 fn adds_anti_probing_penalty() {
3440 let logger = TestLogger::new();
3441 let network_graph = network_graph(&logger);
3442 let source = source_node_id();
3443 let params = ProbabilisticScoringFeeParameters {
3444 anti_probing_penalty_msat: 500,
3445 ..ProbabilisticScoringFeeParameters::zero_penalty()
3447 let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger);
3449 // Check we receive no penalty for a low htlc_maximum_msat.
3450 let usage = ChannelUsage {
3451 amount_msat: 512_000,
3452 inflight_htlc_msat: 0,
3453 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_000 },
3455 let network_graph = network_graph.read_only();
3456 let channel = network_graph.channel(42).unwrap();
3457 let (info, _) = channel.as_directed_from(&source).unwrap();
3458 let candidate = CandidateRouteHop::PublicHop {
3460 short_channel_id: 42,
3462 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
3464 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity.
3465 let usage = ChannelUsage {
3466 amount_msat: 512_000,
3467 inflight_htlc_msat: 0,
3468 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 1_024_000 },
3470 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 500);
3472 // Check we receive anti-probing penalty for htlc_maximum_msat == channel_capacity/2.
3473 let usage = ChannelUsage {
3474 amount_msat: 512_000,
3475 inflight_htlc_msat: 0,
3476 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 512_000 },
3478 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 500);
3480 // Check we receive no anti-probing penalty for htlc_maximum_msat == channel_capacity/2 - 1.
3481 let usage = ChannelUsage {
3482 amount_msat: 512_000,
3483 inflight_htlc_msat: 0,
3484 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024_000, htlc_maximum_msat: 511_999 },
3486 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
3490 fn scores_with_blinded_path() {
3491 // Make sure we'll account for a blinded path's final_value_msat in scoring
3492 let logger = TestLogger::new();
3493 let network_graph = network_graph(&logger);
3494 let params = ProbabilisticScoringFeeParameters {
3495 liquidity_penalty_multiplier_msat: 1_000,
3496 ..ProbabilisticScoringFeeParameters::zero_penalty()
3498 let decay_params = ProbabilisticScoringDecayParameters::default();
3499 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3500 let source = source_node_id();
3501 let usage = ChannelUsage {
3503 inflight_htlc_msat: 0,
3504 effective_capacity: EffectiveCapacity::Total { capacity_msat: 1_024, htlc_maximum_msat: 1_000 },
3506 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
3507 let (info, target) = channel.as_directed_from(&source).unwrap();
3508 let candidate = CandidateRouteHop::PublicHop {
3510 short_channel_id: 42,
3512 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300);
3514 let mut path = payment_path_for_amount(768);
3515 let recipient_hop = path.hops.pop().unwrap();
3516 let blinded_path = BlindedPath {
3517 introduction_node_id: path.hops.last().as_ref().unwrap().pubkey,
3518 blinding_point: test_utils::pubkey(42),
3520 BlindedHop { blinded_node_id: test_utils::pubkey(44), encrypted_payload: Vec::new() }
3523 path.blinded_tail = Some(BlindedTail {
3524 hops: blinded_path.blinded_hops,
3525 blinding_point: blinded_path.blinding_point,
3526 excess_final_cltv_expiry_delta: recipient_hop.cltv_expiry_delta,
3527 final_value_msat: recipient_hop.fee_msat,
3530 // Check the liquidity before and after scoring payment failures to ensure the blinded path's
3531 // final value is taken into account.
3532 assert!(scorer.channel_liquidities.get(&42).is_none());
3534 scorer.payment_path_failed(&path, 42, Duration::ZERO);
3535 path.blinded_tail.as_mut().unwrap().final_value_msat = 256;
3536 scorer.payment_path_failed(&path, 43, Duration::ZERO);
3538 let liquidity = scorer.channel_liquidities.get(&42).unwrap()
3539 .as_directed(&source, &target, 1_000);
3540 assert_eq!(liquidity.min_liquidity_msat(), 256);
3541 assert_eq!(liquidity.max_liquidity_msat(), 768);
3545 fn realistic_historical_failures() {
3546 // The motivation for the unequal sized buckets came largely from attempting to pay 10k
3547 // sats over a one bitcoin channel. This tests that case explicitly, ensuring that we score
3549 let logger = TestLogger::new();
3550 let mut network_graph = network_graph(&logger);
3551 let params = ProbabilisticScoringFeeParameters {
3552 historical_liquidity_penalty_multiplier_msat: 1024,
3553 historical_liquidity_penalty_amount_multiplier_msat: 1024,
3554 ..ProbabilisticScoringFeeParameters::zero_penalty()
3556 let decay_params = ProbabilisticScoringDecayParameters {
3557 liquidity_offset_half_life: Duration::from_secs(60 * 60),
3558 historical_no_updates_half_life: Duration::from_secs(10),
3559 ..ProbabilisticScoringDecayParameters::default()
3562 let capacity_msat = 100_000_000_000;
3563 update_channel(&mut network_graph, 42, source_privkey(), 0, capacity_msat, 200);
3564 update_channel(&mut network_graph, 42, target_privkey(), 1, capacity_msat, 200);
3566 let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger);
3567 let source = source_node_id();
3569 let mut amount_msat = 10_000_000;
3570 let usage = ChannelUsage {
3572 inflight_htlc_msat: 0,
3573 effective_capacity: EffectiveCapacity::Total { capacity_msat, htlc_maximum_msat: capacity_msat },
3575 let channel = network_graph.read_only().channel(42).unwrap().to_owned();
3576 let (info, target) = channel.as_directed_from(&source).unwrap();
3577 let candidate = CandidateRouteHop::PublicHop {
3579 short_channel_id: 42,
3581 // With no historical data the normal liquidity penalty calculation is used, which results
3582 // in a success probability of ~75%.
3583 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 1269);
3584 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3586 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 42, ¶ms),
3589 // Fail to pay once, and then check the buckets and penalty.
3590 scorer.payment_path_failed(&payment_path_for_amount(amount_msat), 42, Duration::ZERO);
3591 // The penalty should be the maximum penalty, as the payment we're scoring is now in the
3592 // same bucket which is the only maximum datapoint.
3593 assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms),
3594 2048 + 2048 * amount_msat / super::AMOUNT_PENALTY_DIVISOR);
3595 // The "it failed" increment is 32, which we should apply to the first upper-bound (between
3596 // 6k sats and 12k sats).
3597 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3598 Some(([32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
3599 [0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])));
3600 // The success probability estimate itself should be zero.
3601 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, amount_msat, ¶ms),
3604 // Now test again with the amount in the bottom bucket.
3606 // The new amount is entirely within the only minimum bucket with score, so the probability
3607 // we assign is 1/2.
3608 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, amount_msat, ¶ms),
3611 // ...but once we see a failure, we consider the payment to be substantially less likely,
3612 // even though not a probability of zero as we still look at the second max bucket which
3614 scorer.payment_path_failed(&payment_path_for_amount(amount_msat), 42, Duration::ZERO);
3615 assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
3616 Some(([63, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
3617 [32, 31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])));
3618 assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, amount_msat, ¶ms),
3626 use criterion::Criterion;
3627 use crate::routing::router::{bench_utils, RouteHop};
3628 use crate::util::test_utils::TestLogger;
3629 use crate::ln::features::{ChannelFeatures, NodeFeatures};
3631 pub fn decay_100k_channel_bounds(bench: &mut Criterion) {
3632 let logger = TestLogger::new();
3633 let (network_graph, mut scorer) = bench_utils::read_graph_scorer(&logger).unwrap();
3634 let mut cur_time = Duration::ZERO;
3635 cur_time += Duration::from_millis(1);
3636 scorer.decay_liquidity_certainty(cur_time);
3637 bench.bench_function("decay_100k_channel_bounds", |b| b.iter(|| {
3638 cur_time += Duration::from_millis(1);
3639 scorer.decay_liquidity_certainty(cur_time);