//! Utilities for scoring payment channels.
//!
//! [`ProbabilisticScorer`] may be given to [`find_route`] to score payment channels during path
-//! finding when a custom [`Score`] implementation is not needed.
+//! finding when a custom [`ScoreLookUp`] implementation is not needed.
//!
//! # Example
//!
use crate::prelude::*;
use core::{cmp, fmt};
-use core::cell::{RefCell, RefMut};
+use core::cell::{RefCell, RefMut, Ref};
use core::convert::TryInto;
use core::ops::{Deref, DerefMut};
use core::time::Duration;
use crate::io::{self, Read};
-use crate::sync::{Mutex, MutexGuard};
+use crate::sync::{Mutex, MutexGuard, RwLock, RwLockReadGuard, RwLockWriteGuard};
/// 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
macro_rules! define_score { ($($supertrait: path)*) => {
/// An interface used to score payment channels for path finding.
///
-/// Scoring is in terms of fees willing to be paid in order to avoid routing through a channel.
-pub trait Score $(: $supertrait)* {
+/// `ScoreLookUp` is used to determine the penalty for a given channel.
+///
+/// Scoring is in terms of fees willing to be paid in order to avoid routing through a channel.
+pub trait ScoreLookUp $(: $supertrait)* {
/// A configurable type which should contain various passed-in parameters for configuring the scorer,
/// on a per-routefinding-call basis through to the scorer methods,
/// which are used to determine the parameters for the suitability of channels for use.
fn channel_penalty_msat(
&self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage, score_params: &Self::ScoreParams
) -> u64;
+}
+/// `ScoreUpdate` is used to update the scorer's internal state after a payment attempt.
+pub trait ScoreUpdate $(: $supertrait)* {
/// Handles updating channel penalties after failing to route through a channel.
fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64);
fn probe_successful(&mut self, path: &Path);
}
-impl<S: Score, T: DerefMut<Target=S> $(+ $supertrait)*> Score for T {
- type ScoreParams = S::ScoreParams;
+impl<SP: Sized, S: ScoreLookUp<ScoreParams = SP>, T: Deref<Target=S> $(+ $supertrait)*> ScoreLookUp for T {
+ type ScoreParams = SP;
fn channel_penalty_msat(
&self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage, score_params: &Self::ScoreParams
) -> u64 {
self.deref().channel_penalty_msat(short_channel_id, source, target, usage, score_params)
}
+}
+impl<S: ScoreUpdate, T: DerefMut<Target=S> $(+ $supertrait)*> ScoreUpdate for T {
fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64) {
self.deref_mut().payment_path_failed(path, short_channel_id)
}
#[cfg(c_bindings)]
define_score!(Writeable);
+
#[cfg(not(c_bindings))]
define_score!();
/// A scorer that is accessed under a lock.
///
-/// Needed so that calls to [`Score::channel_penalty_msat`] in [`find_route`] can be made while
-/// having shared ownership of a scorer but without requiring internal locking in [`Score`]
+/// Needed so that calls to [`ScoreLookUp::channel_penalty_msat`] in [`find_route`] can be made while
+/// having shared ownership of a scorer but without requiring internal locking in [`ScoreUpdate`]
/// implementations. Internal locking would be detrimental to route finding performance and could
-/// result in [`Score::channel_penalty_msat`] returning a different value for the same channel.
+/// result in [`ScoreLookUp::channel_penalty_msat`] returning a different value for the same channel.
///
/// [`find_route`]: crate::routing::router::find_route
pub trait LockableScore<'a> {
- /// The locked [`Score`] type.
- type Locked: 'a + Score;
+ /// The [`ScoreUpdate`] type.
+ type ScoreUpdate: 'a + ScoreUpdate;
+ /// The [`ScoreLookUp`] type.
+ type ScoreLookUp: 'a + ScoreLookUp;
+
+ /// The write locked [`ScoreUpdate`] type.
+ type WriteLocked: DerefMut<Target = Self::ScoreUpdate> + Sized;
- /// Returns the locked scorer.
- fn lock(&'a self) -> Self::Locked;
+ /// The read locked [`ScoreLookUp`] type.
+ type ReadLocked: Deref<Target = Self::ScoreLookUp> + Sized;
+
+ /// Returns read locked scorer.
+ fn read_lock(&'a self) -> Self::ReadLocked;
+
+ /// Returns write locked scorer.
+ fn write_lock(&'a self) -> Self::WriteLocked;
}
/// Refers to a scorer that is accessible under lock and also writeable to disk
#[cfg(not(c_bindings))]
impl<'a, T> WriteableScore<'a> for T where T: LockableScore<'a> + Writeable {}
-/// This is not exported to bindings users
-impl<'a, T: 'a + Score> LockableScore<'a> for Mutex<T> {
- type Locked = MutexGuard<'a, T>;
+#[cfg(not(c_bindings))]
+impl<'a, T: 'a + ScoreLookUp + ScoreUpdate> LockableScore<'a> for Mutex<T> {
+ type ScoreUpdate = T;
+ type ScoreLookUp = T;
+
+ type WriteLocked = MutexGuard<'a, Self::ScoreUpdate>;
+ type ReadLocked = MutexGuard<'a, Self::ScoreLookUp>;
- fn lock(&'a self) -> MutexGuard<'a, T> {
+ fn read_lock(&'a self) -> Self::ReadLocked {
+ Mutex::lock(self).unwrap()
+ }
+
+ fn write_lock(&'a self) -> Self::WriteLocked {
Mutex::lock(self).unwrap()
}
}
-impl<'a, T: 'a + Score> LockableScore<'a> for RefCell<T> {
- type Locked = RefMut<'a, T>;
+#[cfg(not(c_bindings))]
+impl<'a, T: 'a + ScoreUpdate + ScoreLookUp> LockableScore<'a> for RefCell<T> {
+ type ScoreUpdate = T;
+ type ScoreLookUp = T;
+
+ type WriteLocked = RefMut<'a, Self::ScoreUpdate>;
+ type ReadLocked = Ref<'a, Self::ScoreLookUp>;
- fn lock(&'a self) -> RefMut<'a, T> {
+ fn write_lock(&'a self) -> Self::WriteLocked {
self.borrow_mut()
}
+
+ fn read_lock(&'a self) -> Self::ReadLocked {
+ self.borrow()
+ }
+}
+
+#[cfg(not(c_bindings))]
+impl<'a, SP:Sized, T: 'a + ScoreUpdate + ScoreLookUp<ScoreParams = SP>> LockableScore<'a> for RwLock<T> {
+ type ScoreUpdate = T;
+ type ScoreLookUp = T;
+
+ type WriteLocked = RwLockWriteGuard<'a, Self::ScoreLookUp>;
+ type ReadLocked = RwLockReadGuard<'a, Self::ScoreUpdate>;
+
+ fn read_lock(&'a self) -> Self::ReadLocked {
+ RwLock::read(self).unwrap()
+ }
+
+ fn write_lock(&'a self) -> Self::WriteLocked {
+ RwLock::write(self).unwrap()
+ }
}
#[cfg(c_bindings)]
/// A concrete implementation of [`LockableScore`] which supports multi-threading.
-pub struct MultiThreadedLockableScore<S: Score> {
- score: Mutex<S>,
+pub struct MultiThreadedLockableScore<T: ScoreLookUp + ScoreUpdate> {
+ score: RwLock<T>,
}
+
#[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 = <T as Score>::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)
+impl<'a, SP:Sized, T: 'a + ScoreLookUp<ScoreParams = SP> + ScoreUpdate> LockableScore<'a> for MultiThreadedLockableScore<T> {
+ type ScoreUpdate = T;
+ type ScoreLookUp = T;
+ type WriteLocked = MultiThreadedScoreLockWrite<'a, Self::ScoreUpdate>;
+ type ReadLocked = MultiThreadedScoreLockRead<'a, Self::ScoreLookUp>;
+
+ fn read_lock(&'a self) -> Self::ReadLocked {
+ MultiThreadedScoreLockRead(self.score.read().unwrap())
}
- fn probe_successful(&mut self, path: &Path) {
- self.0.probe_successful(path)
+
+ fn write_lock(&'a self) -> Self::WriteLocked {
+ MultiThreadedScoreLockWrite(self.score.write().unwrap())
}
}
+
#[cfg(c_bindings)]
-impl<'a, T: Score + 'a> Writeable for MultiThreadedScoreLock<'a, T> {
+impl<T: ScoreUpdate + ScoreLookUp> Writeable for MultiThreadedLockableScore<T> {
fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
- self.0.write(writer)
+ self.score.read().unwrap().write(writer)
}
}
#[cfg(c_bindings)]
-impl<'a, T: Score + 'a> LockableScore<'a> for MultiThreadedLockableScore<T> {
- type Locked = MultiThreadedScoreLock<'a, T>;
+impl<'a, T: 'a + ScoreUpdate + ScoreLookUp> WriteableScore<'a> for MultiThreadedLockableScore<T> {}
- fn lock(&'a self) -> MultiThreadedScoreLock<'a, T> {
- MultiThreadedScoreLock(Mutex::lock(&self.score).unwrap())
+#[cfg(c_bindings)]
+impl<T: ScoreLookUp + ScoreUpdate> MultiThreadedLockableScore<T> {
+ /// Creates a new [`MultiThreadedLockableScore`] given an underlying [`Score`].
+ pub fn new(score: T) -> Self {
+ MultiThreadedLockableScore { score: RwLock::new(score) }
}
}
#[cfg(c_bindings)]
-impl<T: Score> Writeable for MultiThreadedLockableScore<T> {
- fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
- self.lock().write(writer)
- }
-}
+/// A locked `MultiThreadedLockableScore`.
+pub struct MultiThreadedScoreLockRead<'a, T: ScoreLookUp>(RwLockReadGuard<'a, T>);
#[cfg(c_bindings)]
-impl<'a, T: Score + 'a> WriteableScore<'a> for MultiThreadedLockableScore<T> {}
+/// A locked `MultiThreadedLockableScore`.
+pub struct MultiThreadedScoreLockWrite<'a, T: ScoreUpdate>(RwLockWriteGuard<'a, T>);
#[cfg(c_bindings)]
-impl<T: Score> MultiThreadedLockableScore<T> {
- /// Creates a new [`MultiThreadedLockableScore`] given an underlying [`Score`].
- pub fn new(score: T) -> Self {
- MultiThreadedLockableScore { score: Mutex::new(score) }
+impl<'a, T: 'a + ScoreLookUp> Deref for MultiThreadedScoreLockRead<'a, T> {
+ type Target = T;
+
+ fn deref(&self) -> &Self::Target {
+ self.0.deref()
}
}
#[cfg(c_bindings)]
-/// This is not exported to bindings users
-impl<'a, T: Writeable> Writeable for RefMut<'a, T> {
+impl<'a, T: 'a + ScoreUpdate> Writeable for MultiThreadedScoreLockWrite<'a, T> {
fn write<W: Writer>(&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<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
- S::write(&**self, writer)
+impl<'a, T: 'a + ScoreUpdate> Deref for MultiThreadedScoreLockWrite<'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`].
+#[cfg(c_bindings)]
+impl<'a, T: 'a + ScoreUpdate> DerefMut for MultiThreadedScoreLockWrite<'a, T> {
+ fn deref_mut(&mut self) -> &mut Self::Target {
+ self.0.deref_mut()
+ }
+}
+
+
+/// Proposed use of a channel passed as a parameter to [`ScoreLookUp::channel_penalty_msat`].
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct ChannelUsage {
/// The amount to send through the channel, denominated in millisatoshis.
}
#[derive(Clone)]
-/// [`Score`] implementation that uses a fixed penalty.
+/// [`ScoreLookUp`] implementation that uses a fixed penalty.
pub struct FixedPenaltyScorer {
penalty_msat: u64,
}
}
}
-impl Score for FixedPenaltyScorer {
+impl ScoreLookUp for FixedPenaltyScorer {
type ScoreParams = ();
fn channel_penalty_msat(&self, _: u64, _: &NodeId, _: &NodeId, _: ChannelUsage, _score_params: &Self::ScoreParams) -> u64 {
self.penalty_msat
}
+}
+impl ScoreUpdate for FixedPenaltyScorer {
fn payment_path_failed(&mut self, _path: &Path, _short_channel_id: u64) {}
fn payment_path_successful(&mut self, _path: &Path) {}
}
#[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")]
type ConfiguredTime = Eternity;
-/// [`Score`] implementation using channel success probability distributions.
+/// [`ScoreLookUp`] 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.
/// [`historical_liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringFeeParameters::historical_liquidity_penalty_amount_multiplier_msat
pub type ProbabilisticScorer<G, L> = ProbabilisticScorerUsingTime::<G, L, ConfiguredTime>;
-/// Probabilistic [`Score`] implementation.
+/// Probabilistic [`ScoreLookUp`] implementation.
///
/// This is not exported to bindings users generally all users should use the [`ProbabilisticScorer`] type alias.
pub struct ProbabilisticScorerUsingTime<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time>
pub manual_node_penalties: HashMap<NodeId, u64>,
/// 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.
}
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
+ }
}
}
}
}
-impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Score for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
+impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> ScoreLookUp for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
type ScoreParams = ProbabilisticScoringFeeParameters;
fn channel_penalty_msat(
&self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage, score_params: &ProbabilisticScoringFeeParameters
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;
.saturating_add(anti_probing_penalty_msat)
.saturating_add(base_penalty_msat)
}
+}
+impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> ScoreUpdate for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64) {
let amount_msat = path.final_value_msat();
log_trace!(self.logger, "Scoring path through to SCID {} as having failed at {} msat", short_channel_id, amount_msat);
use crate::ln::msgs::{ChannelAnnouncement, ChannelUpdate, UnsignedChannelAnnouncement, UnsignedChannelUpdate};
use crate::routing::gossip::{EffectiveCapacity, NetworkGraph, NodeId};
use crate::routing::router::{BlindedTail, Path, RouteHop};
- use crate::routing::scoring::{ChannelUsage, Score};
+ use crate::routing::scoring::{ChannelUsage, ScoreLookUp, ScoreUpdate};
use crate::util::ser::{ReadableArgs, Writeable};
use crate::util::test_utils::{self, TestLogger};
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 };
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 };
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 };
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);