X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Fscoring.rs;h=75dae72248b13f0100a8b350459580a2957109e5;hb=861e0eee9e2461fbb2c21454da746f5def5d39a5;hp=9298a17b6c58d860dac29e6188867d70e817f884;hpb=21b0818be7c3f4b3fce24c2bd3ac0c156549f8bc;p=rust-lightning diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index 9298a17b..75dae722 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -157,8 +157,11 @@ define_score!(); /// /// [`find_route`]: crate::routing::router::find_route pub trait LockableScore<'a> { + /// The [`Score`] type. + type Score: 'a + Score; + /// The locked [`Score`] type. - type Locked: 'a + Score; + type Locked: DerefMut + Sized; /// Returns the locked scorer. fn lock(&'a self) -> Self::Locked; @@ -172,62 +175,38 @@ pub trait WriteableScore<'a>: LockableScore<'a> + Writeable {} #[cfg(not(c_bindings))] impl<'a, T> WriteableScore<'a> for T where T: LockableScore<'a> + Writeable {} -/// This is not exported to bindings users +#[cfg(not(c_bindings))] impl<'a, T: 'a + Score> LockableScore<'a> for Mutex { + type Score = T; type Locked = MutexGuard<'a, T>; - fn lock(&'a self) -> MutexGuard<'a, T> { + fn lock(&'a self) -> Self::Locked { Mutex::lock(self).unwrap() } } +#[cfg(not(c_bindings))] impl<'a, T: 'a + Score> LockableScore<'a> for RefCell { + type Score = T; type Locked = RefMut<'a, T>; - fn lock(&'a self) -> RefMut<'a, T> { + fn lock(&'a self) -> Self::Locked { self.borrow_mut() } } #[cfg(c_bindings)] /// A concrete implementation of [`LockableScore`] which supports multi-threading. -pub struct MultiThreadedLockableScore { - score: Mutex, -} -#[cfg(c_bindings)] -/// 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> { - type ScoreParams = ::ScoreParams; - fn channel_penalty_msat(&self, scid: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage, score_params: &Self::ScoreParams) -> u64 { - self.0.channel_penalty_msat(scid, source, target, usage, score_params) - } - fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64) { - self.0.payment_path_failed(path, short_channel_id) - } - fn payment_path_successful(&mut self, path: &Path) { - self.0.payment_path_successful(path) - } - fn probe_failed(&mut self, path: &Path, short_channel_id: u64) { - self.0.probe_failed(path, short_channel_id) - } - fn probe_successful(&mut self, path: &Path) { - 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) - } +pub struct MultiThreadedLockableScore { + score: Mutex, } #[cfg(c_bindings)] -impl<'a, T: Score + 'a> LockableScore<'a> for MultiThreadedLockableScore { +impl<'a, T: 'a + Score> LockableScore<'a> for MultiThreadedLockableScore { + type Score = T; type Locked = MultiThreadedScoreLock<'a, T>; - fn lock(&'a self) -> MultiThreadedScoreLock<'a, T> { + fn lock(&'a self) -> Self::Locked { MultiThreadedScoreLock(Mutex::lock(&self.score).unwrap()) } } @@ -240,7 +219,7 @@ impl Writeable for MultiThreadedLockableScore { } #[cfg(c_bindings)] -impl<'a, T: Score + 'a> WriteableScore<'a> for MultiThreadedLockableScore {} +impl<'a, T: 'a + Score> WriteableScore<'a> for MultiThreadedLockableScore {} #[cfg(c_bindings)] impl MultiThreadedLockableScore { @@ -251,21 +230,34 @@ impl MultiThreadedLockableScore { } #[cfg(c_bindings)] -/// This is not exported to bindings users -impl<'a, T: Writeable> Writeable for RefMut<'a, T> { +/// A locked `MultiThreadedLockableScore`. +pub struct MultiThreadedScoreLock<'a, T: Score>(MutexGuard<'a, T>); + +#[cfg(c_bindings)] +impl<'a, T: 'a + Score> Writeable for MultiThreadedScoreLock<'a, T> { fn write(&self, writer: &mut W) -> Result<(), io::Error> { - T::write(&**self, writer) + self.0.write(writer) } } #[cfg(c_bindings)] -/// This is not exported to bindings users -impl<'a, S: Writeable> Writeable for MutexGuard<'a, S> { - fn write(&self, writer: &mut W) -> Result<(), io::Error> { - S::write(&**self, writer) - } +impl<'a, T: 'a + Score> DerefMut for MultiThreadedScoreLock<'a, T> { + fn deref_mut(&mut self) -> &mut Self::Target { + self.0.deref_mut() + } +} + +#[cfg(c_bindings)] +impl<'a, T: 'a + Score> Deref for MultiThreadedScoreLock<'a, T> { + type Target = T; + + fn deref(&self) -> &Self::Target { + self.0.deref() + } } + + /// Proposed use of a channel passed as a parameter to [`Score::channel_penalty_msat`]. #[derive(Clone, Copy, Debug, PartialEq)] pub struct ChannelUsage { @@ -325,7 +317,7 @@ impl ReadableArgs for FixedPenaltyScorer { } #[cfg(not(feature = "no-std"))] -type ConfiguredTime = std::time::Instant; +type ConfiguredTime = crate::util::time::MonotonicTime; #[cfg(feature = "no-std")] use crate::util::time::Eternity; #[cfg(feature = "no-std")] @@ -491,7 +483,7 @@ pub struct ProbabilisticScoringFeeParameters { pub manual_node_penalties: HashMap, /// This penalty is applied when `htlc_maximum_msat` is equal to or larger than half of the - /// channel's capacity, (ie. htlc_maximum_msat ≥ 0.5 * channel_capacity) which makes us + /// channel's capacity, (ie. htlc_maximum_msat >= 0.5 * channel_capacity) which makes us /// prefer nodes with a smaller `htlc_maximum_msat`. We treat such nodes preferentially /// as this makes balance discovery attacks harder to execute, thereby creating an incentive /// to restrict `htlc_maximum_msat` and improve privacy. @@ -519,6 +511,75 @@ pub struct ProbabilisticScoringFeeParameters { pub considered_impossible_penalty_msat: u64, } +impl Default for ProbabilisticScoringFeeParameters { + fn default() -> Self { + Self { + base_penalty_msat: 500, + base_penalty_amount_multiplier_msat: 8192, + liquidity_penalty_multiplier_msat: 30_000, + liquidity_penalty_amount_multiplier_msat: 192, + manual_node_penalties: HashMap::new(), + anti_probing_penalty_msat: 250, + considered_impossible_penalty_msat: 1_0000_0000_000, + historical_liquidity_penalty_multiplier_msat: 10_000, + historical_liquidity_penalty_amount_multiplier_msat: 64, + } + } +} + +impl ProbabilisticScoringFeeParameters { + /// Marks the node with the given `node_id` as banned, + /// i.e it will be avoided during path finding. + pub fn add_banned(&mut self, node_id: &NodeId) { + self.manual_node_penalties.insert(*node_id, u64::max_value()); + } + + /// Marks all nodes in the given list as banned, i.e., + /// they will be avoided during path finding. + pub fn add_banned_from_list(&mut self, node_ids: Vec) { + for id in node_ids { + self.manual_node_penalties.insert(id, u64::max_value()); + } + } + + /// Removes the node with the given `node_id` from the list of nodes to avoid. + pub fn remove_banned(&mut self, node_id: &NodeId) { + self.manual_node_penalties.remove(node_id); + } + + /// Sets a manual penalty for the given node. + pub fn set_manual_penalty(&mut self, node_id: &NodeId, penalty: u64) { + self.manual_node_penalties.insert(*node_id, penalty); + } + + /// Removes the node with the given `node_id` from the list of manual penalties. + pub fn remove_manual_penalty(&mut self, node_id: &NodeId) { + self.manual_node_penalties.remove(node_id); + } + + /// Clears the list of manual penalties that are applied during path finding. + pub fn clear_manual_penalties(&mut self) { + self.manual_node_penalties = HashMap::new(); + } +} + +#[cfg(test)] +impl ProbabilisticScoringFeeParameters { + fn zero_penalty() -> Self { + Self { + base_penalty_msat: 0, + base_penalty_amount_multiplier_msat: 0, + liquidity_penalty_multiplier_msat: 0, + liquidity_penalty_amount_multiplier_msat: 0, + historical_liquidity_penalty_multiplier_msat: 0, + historical_liquidity_penalty_amount_multiplier_msat: 0, + manual_node_penalties: HashMap::new(), + anti_probing_penalty_msat: 0, + considered_impossible_penalty_msat: 0, + } + } +} + /// Parameters for configuring [`ProbabilisticScorer`]. /// /// Used to configure decay parameters that are static throughout the lifetime of the scorer. @@ -561,9 +622,8 @@ pub struct ProbabilisticScoringDecayParameters { pub liquidity_offset_half_life: Duration, } -#[cfg(test)] -impl ProbabilisticScoringDecayParameters { - fn zero_penalty() -> Self { +impl Default for ProbabilisticScoringDecayParameters { + fn default() -> Self { Self { liquidity_offset_half_life: Duration::from_secs(6 * 60 * 60), historical_no_updates_half_life: Duration::from_secs(60 * 60 * 24 * 14), @@ -571,14 +631,16 @@ impl ProbabilisticScoringDecayParameters { } } -impl Default for ProbabilisticScoringDecayParameters { - fn default() -> Self { +#[cfg(test)] +impl ProbabilisticScoringDecayParameters { + fn zero_penalty() -> Self { Self { liquidity_offset_half_life: Duration::from_secs(6 * 60 * 60), historical_no_updates_half_life: Duration::from_secs(60 * 60 * 24 * 14), } } } + /// Tracks the historical state of a distribution as a weighted average of how much time was spent /// in each of 8 buckets. #[derive(Clone, Copy)] @@ -882,73 +944,6 @@ impl>, L: Deref, T: Time> ProbabilisticScorerU } } -impl ProbabilisticScoringFeeParameters { - #[cfg(test)] - fn zero_penalty() -> Self { - Self { - base_penalty_msat: 0, - base_penalty_amount_multiplier_msat: 0, - liquidity_penalty_multiplier_msat: 0, - liquidity_penalty_amount_multiplier_msat: 0, - historical_liquidity_penalty_multiplier_msat: 0, - historical_liquidity_penalty_amount_multiplier_msat: 0, - manual_node_penalties: HashMap::new(), - anti_probing_penalty_msat: 0, - considered_impossible_penalty_msat: 0, - } - } - - /// Marks the node with the given `node_id` as banned, i.e., - /// it will be avoided during path finding. - pub fn add_banned(&mut self, node_id: &NodeId) { - self.manual_node_penalties.insert(*node_id, u64::max_value()); - } - - /// Marks all nodes in the given list as banned, i.e., - /// they will be avoided during path finding. - pub fn add_banned_from_list(&mut self, node_ids: Vec) { - for id in node_ids { - self.manual_node_penalties.insert(id, u64::max_value()); - } - } - - /// Removes the node with the given `node_id` from the list of nodes to avoid. - pub fn remove_banned(&mut self, node_id: &NodeId) { - self.manual_node_penalties.remove(node_id); - } - - /// Sets a manual penalty for the given node. - pub fn set_manual_penalty(&mut self, node_id: &NodeId, penalty: u64) { - self.manual_node_penalties.insert(*node_id, penalty); - } - - /// Removes the node with the given `node_id` from the list of manual penalties. - pub fn remove_manual_penalty(&mut self, node_id: &NodeId) { - self.manual_node_penalties.remove(node_id); - } - - /// Clears the list of manual penalties that are applied during path finding. - pub fn clear_manual_penalties(&mut self) { - self.manual_node_penalties = HashMap::new(); - } -} - -impl Default for ProbabilisticScoringFeeParameters { - fn default() -> Self { - Self { - base_penalty_msat: 500, - base_penalty_amount_multiplier_msat: 8192, - liquidity_penalty_multiplier_msat: 30_000, - liquidity_penalty_amount_multiplier_msat: 192, - manual_node_penalties: HashMap::new(), - anti_probing_penalty_msat: 250, - considered_impossible_penalty_msat: 1_0000_0000_000, - historical_liquidity_penalty_multiplier_msat: 10_000, - historical_liquidity_penalty_amount_multiplier_msat: 64, - } - } -} - impl ChannelLiquidity { #[inline] fn new() -> Self { @@ -1143,10 +1138,25 @@ impl, BRT: Deref, } fn decayed_offset_msat(&self, offset_msat: u64) -> u64 { - self.now.duration_since(*self.last_updated).as_secs() - .checked_div(self.decay_params.liquidity_offset_half_life.as_secs()) - .and_then(|decays| offset_msat.checked_shr(decays as u32)) - .unwrap_or(0) + let half_life = self.decay_params.liquidity_offset_half_life.as_secs(); + if half_life != 0 { + // Decay the offset by the appropriate number of half lives. If half of the next half + // life has passed, approximate an additional three-quarter life to help smooth out the + // decay. + let elapsed_time = self.now.duration_since(*self.last_updated).as_secs(); + let half_decays = elapsed_time / (half_life / 2); + let decays = half_decays / 2; + let decayed_offset_msat = offset_msat.checked_shr(decays as u32).unwrap_or(0); + if half_decays % 2 == 0 { + decayed_offset_msat + } else { + // 11_585 / 16_384 ~= core::f64::consts::FRAC_1_SQRT_2 + // 16_384 == 2^14 + (decayed_offset_msat as u128 * 11_585 / 16_384) as u64 + } + } else { + 0 + } } } @@ -1240,8 +1250,10 @@ impl>, L: Deref, T: Time> Score for Probabilis let mut anti_probing_penalty_msat = 0; match usage.effective_capacity { - EffectiveCapacity::ExactLiquidity { liquidity_msat } => { - if usage.amount_msat > liquidity_msat { + EffectiveCapacity::ExactLiquidity { liquidity_msat: amount_msat } | + EffectiveCapacity::HintMaxHTLC { amount_msat } => + { + if usage.amount_msat > amount_msat { return u64::max_value(); } else { return base_penalty_msat; @@ -2395,6 +2407,7 @@ mod tests { scorer.payment_path_failed(&payment_path_for_amount(768), 42); scorer.payment_path_failed(&payment_path_for_amount(128), 43); + // Initial penalties let usage = ChannelUsage { amount_msat: 128, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); let usage = ChannelUsage { amount_msat: 256, ..usage }; @@ -2404,7 +2417,8 @@ mod tests { let usage = ChannelUsage { amount_msat: 896, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); - SinceEpoch::advance(Duration::from_secs(9)); + // No decay + SinceEpoch::advance(Duration::from_secs(4)); let usage = ChannelUsage { amount_msat: 128, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); let usage = ChannelUsage { amount_msat: 256, ..usage }; @@ -2414,7 +2428,19 @@ mod tests { let usage = ChannelUsage { amount_msat: 896, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); + // Half decay (i.e., three-quarter life) SinceEpoch::advance(Duration::from_secs(1)); + let usage = ChannelUsage { amount_msat: 128, ..usage }; + assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 22); + let usage = ChannelUsage { amount_msat: 256, ..usage }; + assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 106); + let usage = ChannelUsage { amount_msat: 768, ..usage }; + assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 916); + let usage = ChannelUsage { amount_msat: 896, ..usage }; + assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), u64::max_value()); + + // One decay (i.e., half life) + SinceEpoch::advance(Duration::from_secs(5)); let usage = ChannelUsage { amount_msat: 64, ..usage }; assert_eq!(scorer.channel_penalty_msat(42, &source, &target, usage, ¶ms), 0); let usage = ChannelUsage { amount_msat: 128, ..usage }; @@ -2866,7 +2892,7 @@ mod tests { let usage = ChannelUsage { amount_msat: 1, inflight_htlc_msat: 0, - effective_capacity: EffectiveCapacity::MaximumHTLC { amount_msat: 0 }, + effective_capacity: EffectiveCapacity::AdvertisedMaxHTLC { amount_msat: 0 }, }; assert_eq!(scorer.channel_penalty_msat(42, &target, &source, usage, ¶ms), 2048);