X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Fscoring.rs;h=fefdebfccd30f8b38966e58b7650e81ba06ec080;hb=e61f3a238a70cbac87209e223b7c396108a49b97;hp=73bbbe460e159378e00d12b6f41a3685bbefc1bb;hpb=c8fb859ad6889c67f675052140cf817052542872;p=rust-lightning diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index 73bbbe46..fefdebfc 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -163,6 +163,7 @@ pub trait LockableScore<'a> { /// use the Persister to persist it. pub trait WriteableScore<'a>: LockableScore<'a> + Writeable {} +#[cfg(not(c_bindings))] impl<'a, T> WriteableScore<'a> for T where T: LockableScore<'a> + Writeable {} /// (C-not exported) @@ -188,12 +189,39 @@ pub struct MultiThreadedLockableScore { score: Mutex, } #[cfg(c_bindings)] -/// (C-not exported) +/// A locked `MultiThreadedLockableScore`. +pub struct MultiThreadedScoreLock<'a, S: Score>(MutexGuard<'a, S>); +#[cfg(c_bindings)] +impl<'a, T: Score + 'a> Score for MultiThreadedScoreLock<'a, T> { + fn channel_penalty_msat(&self, scid: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage) -> u64 { + self.0.channel_penalty_msat(scid, source, target, usage) + } + fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) { + self.0.payment_path_failed(path, short_channel_id) + } + fn payment_path_successful(&mut self, path: &[&RouteHop]) { + self.0.payment_path_successful(path) + } + fn probe_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) { + self.0.probe_failed(path, short_channel_id) + } + fn probe_successful(&mut self, path: &[&RouteHop]) { + self.0.probe_successful(path) + } +} +#[cfg(c_bindings)] +impl<'a, T: Score + 'a> Writeable for MultiThreadedScoreLock<'a, T> { + fn write(&self, writer: &mut W) -> Result<(), io::Error> { + self.0.write(writer) + } +} + +#[cfg(c_bindings)] impl<'a, T: Score + 'a> LockableScore<'a> for MultiThreadedLockableScore { - type Locked = MutexGuard<'a, T>; + type Locked = MultiThreadedScoreLock<'a, T>; - fn lock(&'a self) -> MutexGuard<'a, T> { - Mutex::lock(&self.score).unwrap() + fn lock(&'a self) -> MultiThreadedScoreLock<'a, T> { + MultiThreadedScoreLock(Mutex::lock(&self.score).unwrap()) } } @@ -222,7 +250,7 @@ impl<'a, S: Writeable> Writeable for MutexGuard<'a, S> { } /// Proposed use of a channel passed as a parameter to [`Score::channel_penalty_msat`]. -#[derive(Clone, Copy)] +#[derive(Clone, Copy, Debug)] pub struct ChannelUsage { /// The amount to send through the channel, denominated in millisatoshis. pub amount_msat: u64, @@ -287,19 +315,28 @@ 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)`). /// -/// 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. +/// 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. /// -/// 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. +/// 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 /// @@ -307,6 +344,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. @@ -360,19 +402,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 /// @@ -730,7 +780,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, @@ -756,7 +806,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, @@ -957,21 +1007,25 @@ impl, BRT: Deref, impl, BRT: DerefMut, T: Time, U: DerefMut> DirectedChannelLiquidity<'_, L, BRT, T, U> { /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat`. fn failed_at_channel(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger { - if amount_msat < self.max_liquidity_msat() { - log_debug!(logger, "Setting max liquidity of {} to {}", chan_descr, amount_msat); + let existing_max_msat = self.max_liquidity_msat(); + if amount_msat < existing_max_msat { + log_debug!(logger, "Setting max liquidity of {} from {} to {}", chan_descr, existing_max_msat, amount_msat); self.set_max_liquidity_msat(amount_msat); } else { - log_trace!(logger, "Max liquidity of {} already more than {}", chan_descr, amount_msat); + log_trace!(logger, "Max liquidity of {} is {} (already less than or equal to {})", + chan_descr, existing_max_msat, amount_msat); } } /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat` downstream. fn failed_downstream(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger { - if amount_msat > self.min_liquidity_msat() { - log_debug!(logger, "Setting min liquidity of {} to {}", chan_descr, amount_msat); + let existing_min_msat = self.min_liquidity_msat(); + if amount_msat > existing_min_msat { + log_debug!(logger, "Setting min liquidity of {} from {} to {}", existing_min_msat, chan_descr, amount_msat); self.set_min_liquidity_msat(amount_msat); } else { - log_trace!(logger, "Min liquidity of {} already less than {}", chan_descr, amount_msat); + log_trace!(logger, "Min liquidity of {} is {} (already greater than or equal to {})", + chan_descr, existing_min_msat, amount_msat); } } @@ -1540,7 +1594,7 @@ mod tests { use util::time::Time; use util::time::tests::SinceEpoch; - use ln::features::{ChannelFeatures, NodeFeatures}; + use ln::channelmanager; use ln::msgs::{ChannelAnnouncement, ChannelUpdate, UnsignedChannelAnnouncement, UnsignedChannelUpdate}; use routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId}; use routing::router::RouteHop; @@ -1631,7 +1685,7 @@ mod tests { let node_2_secret = &SecretKey::from_slice(&[40; 32]).unwrap(); let secp_ctx = Secp256k1::new(); let unsigned_announcement = UnsignedChannelAnnouncement { - features: ChannelFeatures::known(), + features: channelmanager::provided_channel_features(), chain_hash: genesis_hash, short_channel_id, node_id_1: PublicKey::from_secret_key(&secp_ctx, &node_1_key), @@ -1685,25 +1739,25 @@ mod tests { vec![ RouteHop { pubkey: source_pubkey(), - node_features: NodeFeatures::known(), + node_features: channelmanager::provided_node_features(), short_channel_id: 41, - channel_features: ChannelFeatures::known(), + channel_features: channelmanager::provided_channel_features(), fee_msat: 1, cltv_expiry_delta: 18, }, RouteHop { pubkey: target_pubkey(), - node_features: NodeFeatures::known(), + node_features: channelmanager::provided_node_features(), short_channel_id: 42, - channel_features: ChannelFeatures::known(), + channel_features: channelmanager::provided_channel_features(), fee_msat: 2, cltv_expiry_delta: 18, }, RouteHop { pubkey: recipient_pubkey(), - node_features: NodeFeatures::known(), + node_features: channelmanager::provided_node_features(), short_channel_id: 43, - channel_features: ChannelFeatures::known(), + channel_features: channelmanager::provided_channel_features(), fee_msat: amount_msat, cltv_expiry_delta: 18, },