From 969e23019155409b5beefe3f48994047dfad692c Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Tue, 1 Mar 2022 03:47:28 +0000 Subject: [PATCH] Simplify type aliasing somewhat around times .. as the current C bindings generator isn't capable of handling type aliases in generics in type alias definition currently. --- lightning/src/routing/scoring.rs | 44 +++++++++++++++++++++++++++----- 1 file changed, 38 insertions(+), 6 deletions(-) diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index e60e4879b..f3a508ab6 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -316,12 +316,44 @@ impl ReadableArgs for FixedPenaltyScorer { } #[cfg(not(feature = "no-std"))] -type ConfiguredTime = std::time::Instant; -#[cfg(feature = "no-std")] -use crate::util::time::Eternity; +/// [`Score`] implementation using channel success probability distributions. +/// +/// Channels are tracked with upper and lower liquidity bounds - when an HTLC fails at a channel, +/// we learn that the upper-bound on the available liquidity is lower than the amount of the HTLC. +/// When a payment is forwarded through a channel (but fails later in the route), we learn the +/// lower-bound on the channel's available liquidity must be at least the value of the HTLC. +/// +/// These bounds are then used to determine a success probability using the formula from +/// *Optimally Reliable & Cheap Payment Flows on the Lightning Network* by Rene Pickhardt +/// and Stefan Richter [[1]] (i.e. `(upper_bound - payment_amount) / (upper_bound - lower_bound)`). +/// +/// This probability is combined with the [`liquidity_penalty_multiplier_msat`] and +/// [`liquidity_penalty_amount_multiplier_msat`] parameters to calculate a concrete penalty in +/// milli-satoshis. The penalties, when added across all hops, have the property of being linear in +/// terms of the entire path's success probability. This allows the router to directly compare +/// penalties for different paths. See the documentation of those parameters for the exact formulas. +/// +/// The liquidity bounds are decayed by halving them every [`liquidity_offset_half_life`]. +/// +/// Further, we track the history of our upper and lower liquidity bounds for each channel, +/// allowing us to assign a second penalty (using [`historical_liquidity_penalty_multiplier_msat`] +/// and [`historical_liquidity_penalty_amount_multiplier_msat`]) based on the same probability +/// formula, but using the history of a channel rather than our latest estimates for the liquidity +/// bounds. +/// +/// # Note +/// +/// Mixing the `no-std` feature between serialization and deserialization results in undefined +/// behavior. +/// +/// [1]: https://arxiv.org/abs/2107.05322 +/// [`liquidity_penalty_multiplier_msat`]: ProbabilisticScoringParameters::liquidity_penalty_multiplier_msat +/// [`liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringParameters::liquidity_penalty_amount_multiplier_msat +/// [`liquidity_offset_half_life`]: ProbabilisticScoringParameters::liquidity_offset_half_life +/// [`historical_liquidity_penalty_multiplier_msat`]: ProbabilisticScoringParameters::historical_liquidity_penalty_multiplier_msat +/// [`historical_liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringParameters::historical_liquidity_penalty_amount_multiplier_msat +pub type ProbabilisticScorer = ProbabilisticScorerUsingTime::; #[cfg(feature = "no-std")] -type ConfiguredTime = Eternity; - /// [`Score`] implementation using channel success probability distributions. /// /// Channels are tracked with upper and lower liquidity bounds - when an HTLC fails at a channel, @@ -358,7 +390,7 @@ type ConfiguredTime = Eternity; /// [`liquidity_offset_half_life`]: ProbabilisticScoringParameters::liquidity_offset_half_life /// [`historical_liquidity_penalty_multiplier_msat`]: ProbabilisticScoringParameters::historical_liquidity_penalty_multiplier_msat /// [`historical_liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringParameters::historical_liquidity_penalty_amount_multiplier_msat -pub type ProbabilisticScorer = ProbabilisticScorerUsingTime::; +pub type ProbabilisticScorer = ProbabilisticScorerUsingTime::; /// Probabilistic [`Score`] implementation. /// -- 2.39.5