X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Fscoring.rs;h=1c13771b1b7224432b1e79db5c2ceec6a97d752a;hb=9d3324968c175661ae2d11c5c754688978f2fb7f;hp=d1195dc8d674b343fcb769f9490724e4a4c14d21;hpb=559ed20f92cb86b02094421fa51ad243dbf800b6;p=rust-lightning diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index d1195dc8..1c13771b 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -54,21 +54,21 @@ //! //! [`find_route`]: crate::routing::router::find_route -use ln::msgs::DecodeError; -use routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId}; -use routing::router::RouteHop; -use util::ser::{Readable, ReadableArgs, Writeable, Writer}; -use util::logger::Logger; -use util::time::Time; - -use prelude::*; +use crate::ln::msgs::DecodeError; +use crate::routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId}; +use crate::routing::router::RouteHop; +use crate::util::ser::{Readable, ReadableArgs, Writeable, Writer}; +use crate::util::logger::Logger; +use crate::util::time::Time; + +use crate::prelude::*; use core::{cmp, fmt}; use core::cell::{RefCell, RefMut}; use core::convert::TryInto; use core::ops::{Deref, DerefMut}; use core::time::Duration; -use io::{self, Read}; -use sync::{Mutex, MutexGuard}; +use crate::io::{self, Read}; +use crate::sync::{Mutex, MutexGuard}; /// We define Score ever-so-slightly differently based on whether we are being built for C bindings /// or not. For users, `LockableScore` must somehow be writeable to disk. For Rust users, this is @@ -225,6 +225,16 @@ impl<'a, T: Score + 'a> LockableScore<'a> for MultiThreadedLockableScore { } } +#[cfg(c_bindings)] +impl Writeable for MultiThreadedLockableScore { + fn write(&self, writer: &mut W) -> Result<(), io::Error> { + self.lock().write(writer) + } +} + +#[cfg(c_bindings)] +impl<'a, T: Score + 'a> WriteableScore<'a> for MultiThreadedLockableScore {} + #[cfg(c_bindings)] impl MultiThreadedLockableScore { /// Creates a new [`MultiThreadedLockableScore`] given an underlying [`Score`]. @@ -309,25 +319,34 @@ impl ReadableArgs for FixedPenaltyScorer { #[cfg(not(feature = "no-std"))] type ConfiguredTime = std::time::Instant; #[cfg(feature = "no-std")] -use util::time::Eternity; +use crate::util::time::Eternity; #[cfg(feature = "no-std")] type ConfiguredTime = Eternity; /// [`Score`] implementation using channel success probability distributions. /// -/// Based on *Optimally Reliable & Cheap Payment Flows on the Lightning Network* by Rene Pickhardt -/// and Stefan Richter [[1]]. Given the uncertainty of channel liquidity balances, probability -/// distributions are defined based on knowledge learned from successful and unsuccessful attempts. -/// Then the negative `log10` of the success probability is used to determine the cost of routing a -/// specific HTLC amount through a channel. +/// 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. /// -/// Knowledge about channel liquidity balances takes the form of upper and lower bounds on the -/// possible liquidity. Certainty of the bounds is decreased over time using a decay function. See -/// [`ProbabilisticScoringParameters`] for details. +/// The liquidity bounds are decayed by halving them every [`liquidity_offset_half_life`]. /// -/// Since the scorer aims to learn the current channel liquidity balances, it works best for nodes -/// with high payment volume or that actively probe the [`NetworkGraph`]. Nodes with low payment -/// volume are more likely to experience failed payment paths, which would need to be retried. +/// 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 /// @@ -335,6 +354,11 @@ type ConfiguredTime = Eternity; /// 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::; /// Probabilistic [`Score`] implementation. @@ -388,19 +412,27 @@ pub struct ProbabilisticScoringParameters { /// uncertainty bounds of the channel liquidity balance. Amounts above the upper bound will /// result in a `u64::max_value` penalty, however. /// + /// `-log10(success_probability) * liquidity_penalty_multiplier_msat` + /// /// Default value: 30,000 msat /// /// [`liquidity_offset_half_life`]: Self::liquidity_offset_half_life pub liquidity_penalty_multiplier_msat: u64, - /// The time required to elapse before any knowledge learned about channel liquidity balances is - /// cut in half. + /// Whenever this amount of time elapses since the last update to a channel's liquidity bounds, + /// the distance from the bounds to "zero" is cut in half. In other words, the lower-bound on + /// the available liquidity is halved and the upper-bound moves half-way to the channel's total + /// capacity. + /// + /// Because halving the liquidity bounds grows the uncertainty on the channel's liquidity, + /// the penalty for an amount within the new bounds may change. See the [`ProbabilisticScorer`] + /// struct documentation for more info on the way the liquidity bounds are used. /// - /// The bounds are defined in terms of offsets and are initially zero. Increasing the offsets - /// gives tighter bounds on the channel liquidity balance. Thus, halving the offsets decreases - /// the certainty of the channel liquidity balance. + /// For example, if the channel's capacity is 1 million sats, and the current upper and lower + /// liquidity bounds are 200,000 sats and 600,000 sats, after this amount of time the upper + /// and lower liquidity bounds will be decayed to 100,000 and 800,000 sats. /// - /// Default value: 1 hour + /// Default value: 6 hours /// /// # Note /// @@ -758,7 +790,7 @@ impl ProbabilisticScoringParameters { base_penalty_msat: 0, base_penalty_amount_multiplier_msat: 0, liquidity_penalty_multiplier_msat: 0, - liquidity_offset_half_life: Duration::from_secs(3600), + liquidity_offset_half_life: Duration::from_secs(6 * 60 * 60), liquidity_penalty_amount_multiplier_msat: 0, historical_liquidity_penalty_multiplier_msat: 0, historical_liquidity_penalty_amount_multiplier_msat: 0, @@ -784,7 +816,7 @@ impl Default for ProbabilisticScoringParameters { base_penalty_msat: 500, base_penalty_amount_multiplier_msat: 8192, liquidity_penalty_multiplier_msat: 30_000, - liquidity_offset_half_life: Duration::from_secs(3600), + liquidity_offset_half_life: Duration::from_secs(6 * 60 * 60), liquidity_penalty_amount_multiplier_msat: 192, historical_liquidity_penalty_multiplier_msat: 10_000, historical_liquidity_penalty_amount_multiplier_msat: 64, @@ -1569,16 +1601,16 @@ impl Readable for ChannelLiquidity { #[cfg(test)] mod tests { use super::{ChannelLiquidity, HistoricalBucketRangeTracker, ProbabilisticScoringParameters, ProbabilisticScorerUsingTime}; - use util::time::Time; - use util::time::tests::SinceEpoch; + use crate::util::time::Time; + use crate::util::time::tests::SinceEpoch; - use ln::channelmanager; - use ln::msgs::{ChannelAnnouncement, ChannelUpdate, UnsignedChannelAnnouncement, UnsignedChannelUpdate}; - use routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId}; - use routing::router::RouteHop; - use routing::scoring::{ChannelUsage, Score}; - use util::ser::{ReadableArgs, Writeable}; - use util::test_utils::TestLogger; + use crate::ln::channelmanager; + use crate::ln::msgs::{ChannelAnnouncement, ChannelUpdate, UnsignedChannelAnnouncement, UnsignedChannelUpdate}; + use crate::routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId}; + use crate::routing::router::RouteHop; + use crate::routing::scoring::{ChannelUsage, Score}; + use crate::util::ser::{ReadableArgs, Writeable}; + use crate::util::test_utils::TestLogger; use bitcoin::blockdata::constants::genesis_block; use bitcoin::hashes::Hash; @@ -1586,7 +1618,7 @@ mod tests { use bitcoin::network::constants::Network; use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey}; use core::time::Duration; - use io; + use crate::io; fn source_privkey() -> SecretKey { SecretKey::from_slice(&[42; 32]).unwrap() @@ -1680,7 +1712,7 @@ mod tests { bitcoin_signature_2: secp_ctx.sign_ecdsa(&msghash, &node_2_secret), contents: unsigned_announcement, }; - let chain_source: Option<&::util::test_utils::TestChainSource> = None; + let chain_source: Option<&crate::util::test_utils::TestChainSource> = None; network_graph.update_channel_from_announcement( &signed_announcement, &chain_source).unwrap(); update_channel(network_graph, short_channel_id, node_1_key, 0);