/// Handles updating channel penalties after a probe over the given path succeeded.
fn probe_successful(&mut self, path: &Path, duration_since_epoch: Duration);
- /// Scorers may wich to reduce their certainty of channel liquidity information over time.
+ /// Scorers may wish to reduce their certainty of channel liquidity information over time.
/// Thus, this method is provided to allow scorers to observe the passage of time - the holder
/// of this object should call this method regularly (generally via the
/// `lightning-background-processor` crate).
decay_params: ProbabilisticScoringDecayParameters,
network_graph: G,
logger: L,
- // TODO: Remove entries of closed channels.
- channel_liquidities: HashMap<u64, ChannelLiquidity<T>>,
+ channel_liquidities: HashMap<u64, ChannelLiquidity>,
+ _unused_time: core::marker::PhantomData<T>,
}
/// Parameters for configuring [`ProbabilisticScorer`].
/// Direction is defined in terms of [`NodeId`] partial ordering, where the source node is the
/// first node in the ordering of the channel's counterparties. Thus, swapping the two liquidity
/// offset fields gives the opposite direction.
-struct ChannelLiquidity<T: Time> {
+struct ChannelLiquidity {
/// Lower channel liquidity bound in terms of an offset from zero.
min_liquidity_offset_msat: u64,
/// Upper channel liquidity bound in terms of an offset from the effective capacity.
max_liquidity_offset_msat: u64,
- /// Time when the liquidity bounds were last modified.
- last_updated: T,
-
min_liquidity_offset_history: HistoricalBucketRangeTracker,
max_liquidity_offset_history: HistoricalBucketRangeTracker,
+
+ /// Time when the liquidity bounds were last modified as an offset since the unix epoch.
+ last_updated: Duration,
+
+ /// Time when the historical liquidity bounds were last modified as an offset against the unix
+ /// epoch.
+ offset_history_last_updated: Duration,
}
/// A snapshot of [`ChannelLiquidity`] in one direction assuming a certain channel capacity and
/// decayed with a given half life.
-struct DirectedChannelLiquidity<L: Deref<Target = u64>, BRT: Deref<Target = HistoricalBucketRangeTracker>, T: Time, U: Deref<Target = T>> {
+struct DirectedChannelLiquidity<L: Deref<Target = u64>, BRT: Deref<Target = HistoricalBucketRangeTracker>, T: Deref<Target = Duration>> {
min_liquidity_offset_msat: L,
max_liquidity_offset_msat: L,
liquidity_history: HistoricalMinMaxBuckets<BRT>,
capacity_msat: u64,
- last_updated: U,
- now: T,
+ last_updated: T,
+ offset_history_last_updated: T,
decay_params: ProbabilisticScoringDecayParameters,
}
network_graph,
logger,
channel_liquidities: HashMap::new(),
+ _unused_time: core::marker::PhantomData,
}
}
#[cfg(test)]
- fn with_channel(mut self, short_channel_id: u64, liquidity: ChannelLiquidity<T>) -> Self {
+ fn with_channel(mut self, short_channel_id: u64, liquidity: ChannelLiquidity) -> Self {
assert!(self.channel_liquidities.insert(short_channel_id, liquidity).is_none());
self
}
/// Note that this writes roughly one line per channel for which we have a liquidity estimate,
/// which may be a substantial amount of log output.
pub fn debug_log_liquidity_stats(&self) {
- let now = T::now();
-
let graph = self.network_graph.read_only();
for (scid, liq) in self.channel_liquidities.iter() {
if let Some(chan_debug) = graph.channels().get(scid) {
let amt = directed_info.effective_capacity().as_msat();
let dir_liq = liq.as_directed(source, target, amt, self.decay_params);
- let (min_buckets, max_buckets) = dir_liq.liquidity_history
- .get_decayed_buckets(now, *dir_liq.last_updated,
- self.decay_params.historical_no_updates_half_life)
- .unwrap_or(([0; 32], [0; 32]));
+ let min_buckets = &dir_liq.liquidity_history.min_liquidity_offset_history.buckets;
+ let max_buckets = &dir_liq.liquidity_history.max_liquidity_offset_history.buckets;
log_debug!(self.logger, core::concat!(
"Liquidity from {} to {} via {} is in the range ({}, {}).\n",
/// in the top and bottom bucket, and roughly with similar (recent) frequency.
///
/// Because the datapoints are decayed slowly over time, values will eventually return to
- /// `Some(([1; 32], [1; 32]))` and then to `None` once no datapoints remain.
+ /// `Some(([0; 32], [0; 32]))` or `None` if no data remains for a channel.
///
/// In order to fetch a single success probability from the buckets provided here, as used in
/// the scoring model, see [`Self::historical_estimated_payment_success_probability`].
let amt = directed_info.effective_capacity().as_msat();
let dir_liq = liq.as_directed(source, target, amt, self.decay_params);
- let (min_buckets, mut max_buckets) =
- dir_liq.liquidity_history.get_decayed_buckets(
- dir_liq.now, *dir_liq.last_updated,
- self.decay_params.historical_no_updates_half_life
- )?;
+ let min_buckets = dir_liq.liquidity_history.min_liquidity_offset_history.buckets;
+ let mut max_buckets = dir_liq.liquidity_history.max_liquidity_offset_history.buckets;
// Note that the liquidity buckets are an offset from the edge, so we inverse
// the max order to get the probabilities from zero.
let dir_liq = liq.as_directed(source, target, capacity_msat, self.decay_params);
return dir_liq.liquidity_history.calculate_success_probability_times_billion(
- dir_liq.now, *dir_liq.last_updated,
- self.decay_params.historical_no_updates_half_life, ¶ms, amount_msat,
- capacity_msat
+ ¶ms, amount_msat, capacity_msat
).map(|p| p as f64 / (1024 * 1024 * 1024) as f64);
}
}
}
}
-impl<T: Time> ChannelLiquidity<T> {
- #[inline]
- fn new() -> Self {
+impl ChannelLiquidity {
+ fn new(last_updated: Duration) -> Self {
Self {
min_liquidity_offset_msat: 0,
max_liquidity_offset_msat: 0,
min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
- last_updated: T::now(),
+ last_updated,
+ offset_history_last_updated: last_updated,
}
}
/// `capacity_msat`.
fn as_directed(
&self, source: &NodeId, target: &NodeId, capacity_msat: u64, decay_params: ProbabilisticScoringDecayParameters
- ) -> DirectedChannelLiquidity<&u64, &HistoricalBucketRangeTracker, T, &T> {
+ ) -> DirectedChannelLiquidity<&u64, &HistoricalBucketRangeTracker, &Duration> {
let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) =
if source < target {
(&self.min_liquidity_offset_msat, &self.max_liquidity_offset_msat,
},
capacity_msat,
last_updated: &self.last_updated,
- now: T::now(),
+ offset_history_last_updated: &self.offset_history_last_updated,
decay_params: decay_params,
}
}
/// `capacity_msat`.
fn as_directed_mut(
&mut self, source: &NodeId, target: &NodeId, capacity_msat: u64, decay_params: ProbabilisticScoringDecayParameters
- ) -> DirectedChannelLiquidity<&mut u64, &mut HistoricalBucketRangeTracker, T, &mut T> {
+ ) -> DirectedChannelLiquidity<&mut u64, &mut HistoricalBucketRangeTracker, &mut Duration> {
let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) =
if source < target {
(&mut self.min_liquidity_offset_msat, &mut self.max_liquidity_offset_msat,
},
capacity_msat,
last_updated: &mut self.last_updated,
- now: T::now(),
+ offset_history_last_updated: &mut self.offset_history_last_updated,
decay_params: decay_params,
}
}
+
+ fn decayed_offset(&self, offset: u64, duration_since_epoch: Duration,
+ decay_params: ProbabilisticScoringDecayParameters
+ ) -> u64 {
+ let half_life = decay_params.liquidity_offset_half_life.as_secs_f64();
+ if half_life != 0.0 {
+ let elapsed_time = duration_since_epoch.saturating_sub(self.last_updated).as_secs_f64();
+ ((offset as f64) * powf64(0.5, elapsed_time / half_life)) as u64
+ } else {
+ 0
+ }
+ }
}
/// Bounds `-log10` to avoid excessive liquidity penalties for payments with low success
(numerator, denominator)
}
-impl<L: Deref<Target = u64>, BRT: Deref<Target = HistoricalBucketRangeTracker>, T: Time, U: Deref<Target = T>> DirectedChannelLiquidity< L, BRT, T, U> {
+impl<L: Deref<Target = u64>, BRT: Deref<Target = HistoricalBucketRangeTracker>, T: Deref<Target = Duration>>
+DirectedChannelLiquidity< L, BRT, T> {
/// Returns a liquidity penalty for routing the given HTLC `amount_msat` through the channel in
/// this direction.
fn penalty_msat(&self, amount_msat: u64, score_params: &ProbabilisticScoringFeeParameters) -> u64 {
if score_params.historical_liquidity_penalty_multiplier_msat != 0 ||
score_params.historical_liquidity_penalty_amount_multiplier_msat != 0 {
if let Some(cumulative_success_prob_times_billion) = self.liquidity_history
- .calculate_success_probability_times_billion(self.now, *self.last_updated,
- self.decay_params.historical_no_updates_half_life, score_params, amount_msat,
- self.capacity_msat)
+ .calculate_success_probability_times_billion(
+ score_params, amount_msat, self.capacity_msat)
{
let historical_negative_log10_times_2048 = approx::negative_log10_times_2048(cumulative_success_prob_times_billion + 1, 1024 * 1024 * 1024);
res = res.saturating_add(Self::combined_penalty_msat(amount_msat,
}
fn decayed_offset_msat(&self, offset_msat: u64) -> u64 {
- 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
- }
+ offset_msat
}
}
-impl<L: DerefMut<Target = u64>, BRT: DerefMut<Target = HistoricalBucketRangeTracker>, T: Time, U: DerefMut<Target = T>> DirectedChannelLiquidity<L, BRT, T, U> {
+impl<L: DerefMut<Target = u64>, BRT: DerefMut<Target = HistoricalBucketRangeTracker>, T: DerefMut<Target = Duration>>
+DirectedChannelLiquidity<L, BRT, T> {
/// Adjusts the channel liquidity balance bounds when failing to route `amount_msat`.
- fn failed_at_channel<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
+ fn failed_at_channel<Log: Deref>(
+ &mut self, amount_msat: u64, duration_since_epoch: Duration, chan_descr: fmt::Arguments, logger: &Log
+ ) where Log::Target: Logger {
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);
+ self.set_max_liquidity_msat(amount_msat, duration_since_epoch);
} else {
log_trace!(logger, "Max liquidity of {} is {} (already less than or equal to {})",
chan_descr, existing_max_msat, amount_msat);
}
- self.update_history_buckets(0);
+ self.update_history_buckets(0, duration_since_epoch);
}
/// Adjusts the channel liquidity balance bounds when failing to route `amount_msat` downstream.
- fn failed_downstream<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
+ fn failed_downstream<Log: Deref>(
+ &mut self, amount_msat: u64, duration_since_epoch: Duration, chan_descr: fmt::Arguments, logger: &Log
+ ) where Log::Target: Logger {
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);
+ self.set_min_liquidity_msat(amount_msat, duration_since_epoch);
} else {
log_trace!(logger, "Min liquidity of {} is {} (already greater than or equal to {})",
chan_descr, existing_min_msat, amount_msat);
}
- self.update_history_buckets(0);
+ self.update_history_buckets(0, duration_since_epoch);
}
/// Adjusts the channel liquidity balance bounds when successfully routing `amount_msat`.
- fn successful<Log: Deref>(&mut self, amount_msat: u64, chan_descr: fmt::Arguments, logger: &Log) where Log::Target: Logger {
+ fn successful<Log: Deref>(&mut self,
+ amount_msat: u64, duration_since_epoch: Duration, chan_descr: fmt::Arguments, logger: &Log
+ ) where Log::Target: Logger {
let max_liquidity_msat = self.max_liquidity_msat().checked_sub(amount_msat).unwrap_or(0);
log_debug!(logger, "Subtracting {} from max liquidity of {} (setting it to {})", amount_msat, chan_descr, max_liquidity_msat);
- self.set_max_liquidity_msat(max_liquidity_msat);
- self.update_history_buckets(amount_msat);
+ self.set_max_liquidity_msat(max_liquidity_msat, duration_since_epoch);
+ self.update_history_buckets(amount_msat, duration_since_epoch);
}
/// Updates the history buckets for this channel. Because the history buckets track what we now
/// know about the channel's state *prior to our payment* (i.e. what we assume is "steady
/// state"), we allow the caller to set an offset applied to our liquidity bounds which
/// represents the amount of the successful payment we just made.
- fn update_history_buckets(&mut self, bucket_offset_msat: u64) {
- let half_lives = self.now.duration_since(*self.last_updated).as_secs()
+ fn update_history_buckets(&mut self, bucket_offset_msat: u64, duration_since_epoch: Duration) {
+ let half_lives =
+ duration_since_epoch.checked_sub(*self.offset_history_last_updated)
+ .unwrap_or(Duration::ZERO).as_secs()
.checked_div(self.decay_params.historical_no_updates_half_life.as_secs())
.map(|v| v.try_into().unwrap_or(u32::max_value())).unwrap_or(u32::max_value());
self.liquidity_history.min_liquidity_offset_history.time_decay_data(half_lives);
self.liquidity_history.max_liquidity_offset_history.track_datapoint(
max_liquidity_offset_msat.saturating_sub(bucket_offset_msat), self.capacity_msat
);
+ *self.offset_history_last_updated = duration_since_epoch;
}
/// Adjusts the lower bound of the channel liquidity balance in this direction.
- fn set_min_liquidity_msat(&mut self, amount_msat: u64) {
+ fn set_min_liquidity_msat(&mut self, amount_msat: u64, duration_since_epoch: Duration) {
*self.min_liquidity_offset_msat = amount_msat;
- *self.max_liquidity_offset_msat = if amount_msat > self.max_liquidity_msat() {
- 0
- } else {
- self.decayed_offset_msat(*self.max_liquidity_offset_msat)
- };
- *self.last_updated = self.now;
+ if amount_msat > self.max_liquidity_msat() {
+ *self.max_liquidity_offset_msat = 0;
+ }
+ *self.last_updated = duration_since_epoch;
}
/// Adjusts the upper bound of the channel liquidity balance in this direction.
- fn set_max_liquidity_msat(&mut self, amount_msat: u64) {
+ fn set_max_liquidity_msat(&mut self, amount_msat: u64, duration_since_epoch: Duration) {
*self.max_liquidity_offset_msat = self.capacity_msat.checked_sub(amount_msat).unwrap_or(0);
- *self.min_liquidity_offset_msat = if amount_msat < self.min_liquidity_msat() {
- 0
- } else {
- self.decayed_offset_msat(*self.min_liquidity_offset_msat)
- };
- *self.last_updated = self.now;
+ if amount_msat < *self.min_liquidity_offset_msat {
+ *self.min_liquidity_offset_msat = 0;
+ }
+ *self.last_updated = duration_since_epoch;
}
}
let capacity_msat = usage.effective_capacity.as_msat();
self.channel_liquidities
.get(&scid)
- .unwrap_or(&ChannelLiquidity::new())
+ .unwrap_or(&ChannelLiquidity::new(Duration::ZERO))
.as_directed(&source, &target, capacity_msat, self.decay_params)
.penalty_msat(amount_msat, score_params)
.saturating_add(anti_probing_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, _duration_since_epoch: Duration) {
+ fn payment_path_failed(&mut self, path: &Path, short_channel_id: u64, duration_since_epoch: Duration) {
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);
let network_graph = self.network_graph.read_only();
if at_failed_channel {
self.channel_liquidities
.entry(hop.short_channel_id)
- .or_insert_with(ChannelLiquidity::new)
+ .or_insert_with(|| ChannelLiquidity::new(duration_since_epoch))
.as_directed_mut(source, &target, capacity_msat, self.decay_params)
- .failed_at_channel(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
+ .failed_at_channel(amount_msat, duration_since_epoch,
+ format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
} else {
self.channel_liquidities
.entry(hop.short_channel_id)
- .or_insert_with(ChannelLiquidity::new)
+ .or_insert_with(|| ChannelLiquidity::new(duration_since_epoch))
.as_directed_mut(source, &target, capacity_msat, self.decay_params)
- .failed_downstream(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
+ .failed_downstream(amount_msat, duration_since_epoch,
+ format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
}
} else {
log_debug!(self.logger, "Not able to penalize channel with SCID {} as we do not have graph info for it (likely a route-hint last-hop).",
}
}
- fn payment_path_successful(&mut self, path: &Path, _duration_since_epoch: Duration) {
+ fn payment_path_successful(&mut self, path: &Path, duration_since_epoch: Duration) {
let amount_msat = path.final_value_msat();
log_trace!(self.logger, "Scoring path through SCID {} as having succeeded at {} msat.",
path.hops.split_last().map(|(hop, _)| hop.short_channel_id).unwrap_or(0), amount_msat);
let capacity_msat = channel.effective_capacity().as_msat();
self.channel_liquidities
.entry(hop.short_channel_id)
- .or_insert_with(ChannelLiquidity::new)
+ .or_insert_with(|| ChannelLiquidity::new(duration_since_epoch))
.as_directed_mut(source, &target, capacity_msat, self.decay_params)
- .successful(amount_msat, format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
+ .successful(amount_msat, duration_since_epoch,
+ format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
} else {
log_debug!(self.logger, "Not able to learn for channel with SCID {} as we do not have graph info for it (likely a route-hint last-hop).",
hop.short_channel_id);
self.payment_path_failed(path, u64::max_value(), duration_since_epoch)
}
- fn decay_liquidity_certainty(&mut self, _duration_since_epoch: Duration) {}
+ fn decay_liquidity_certainty(&mut self, duration_since_epoch: Duration) {
+ let decay_params = self.decay_params;
+ self.channel_liquidities.retain(|_scid, liquidity| {
+ liquidity.min_liquidity_offset_msat =
+ liquidity.decayed_offset(liquidity.min_liquidity_offset_msat, duration_since_epoch, decay_params);
+ liquidity.max_liquidity_offset_msat =
+ liquidity.decayed_offset(liquidity.max_liquidity_offset_msat, duration_since_epoch, decay_params);
+ liquidity.last_updated = duration_since_epoch;
+
+ let elapsed_time =
+ duration_since_epoch.saturating_sub(liquidity.offset_history_last_updated);
+ if elapsed_time > decay_params.historical_no_updates_half_life {
+ let half_life = decay_params.historical_no_updates_half_life.as_secs_f64();
+ if half_life != 0.0 {
+ let divisor = powf64(2048.0, elapsed_time.as_secs_f64() / half_life) as u64;
+ for bucket in liquidity.min_liquidity_offset_history.buckets.iter_mut() {
+ *bucket = ((*bucket as u64) * 1024 / divisor) as u16;
+ }
+ for bucket in liquidity.max_liquidity_offset_history.buckets.iter_mut() {
+ *bucket = ((*bucket as u64) * 1024 / divisor) as u16;
+ }
+ liquidity.offset_history_last_updated = duration_since_epoch;
+ }
+ }
+ liquidity.min_liquidity_offset_msat != 0 || liquidity.max_liquidity_offset_msat != 0 ||
+ liquidity.min_liquidity_offset_history.buckets != [0; 32] ||
+ liquidity.max_liquidity_offset_history.buckets != [0; 32]
+ });
+ }
}
#[cfg(c_bindings)]
/// in each of 32 buckets.
#[derive(Clone, Copy)]
pub(super) struct HistoricalBucketRangeTracker {
- buckets: [u16; 32],
+ pub(super) buckets: [u16; 32],
}
/// Buckets are stored in fixed point numbers with a 5 bit fractional part. Thus, the value
}
impl<D: Deref<Target = HistoricalBucketRangeTracker>> HistoricalMinMaxBuckets<D> {
- pub(super) fn get_decayed_buckets<T: Time>(&self, now: T, last_updated: T, half_life: Duration)
- -> Option<([u16; 32], [u16; 32])> {
- let (_, required_decays) = self.get_total_valid_points(now, last_updated, half_life)?;
-
- let mut min_buckets = *self.min_liquidity_offset_history;
- min_buckets.time_decay_data(required_decays);
- let mut max_buckets = *self.max_liquidity_offset_history;
- max_buckets.time_decay_data(required_decays);
- Some((min_buckets.buckets, max_buckets.buckets))
- }
#[inline]
- pub(super) fn get_total_valid_points<T: Time>(&self, now: T, last_updated: T, half_life: Duration)
- -> Option<(u64, u32)> {
- let required_decays = now.duration_since(last_updated).as_secs()
- .checked_div(half_life.as_secs())
- .map_or(u32::max_value(), |decays| cmp::min(decays, u32::max_value() as u64) as u32);
+ pub(super) fn calculate_success_probability_times_billion(
+ &self, params: &ProbabilisticScoringFeeParameters, amount_msat: u64,
+ capacity_msat: u64
+ ) -> Option<u64> {
+ // If historical penalties are enabled, we try to calculate a probability of success
+ // given our historical distribution of min- and max-liquidity bounds in a channel.
+ // To do so, we walk the set of historical liquidity bucket (min, max) combinations
+ // (where min_idx < max_idx, as having a minimum above our maximum is an invalid
+ // state). For each pair, we calculate the probability as if the bucket's corresponding
+ // min- and max- liquidity bounds were our current liquidity bounds and then multiply
+ // that probability by the weight of the selected buckets.
+ let payment_pos = amount_to_pos(amount_msat, capacity_msat);
+ if payment_pos >= POSITION_TICKS { return None; }
let mut total_valid_points_tracked = 0;
for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate() {
// If the total valid points is smaller than 1.0 (i.e. 32 in our fixed-point scheme),
// treat it as if we were fully decayed.
const FULLY_DECAYED: u16 = BUCKET_FIXED_POINT_ONE * BUCKET_FIXED_POINT_ONE;
- if total_valid_points_tracked.checked_shr(required_decays).unwrap_or(0) < FULLY_DECAYED.into() {
+ if total_valid_points_tracked < FULLY_DECAYED.into() {
return None;
}
- Some((total_valid_points_tracked, required_decays))
- }
-
- #[inline]
- pub(super) fn calculate_success_probability_times_billion<T: Time>(
- &self, now: T, last_updated: T, half_life: Duration,
- params: &ProbabilisticScoringFeeParameters, amount_msat: u64, capacity_msat: u64
- ) -> Option<u64> {
- // If historical penalties are enabled, we try to calculate a probability of success
- // given our historical distribution of min- and max-liquidity bounds in a channel.
- // To do so, we walk the set of historical liquidity bucket (min, max) combinations
- // (where min_idx < max_idx, as having a minimum above our maximum is an invalid
- // state). For each pair, we calculate the probability as if the bucket's corresponding
- // min- and max- liquidity bounds were our current liquidity bounds and then multiply
- // that probability by the weight of the selected buckets.
- let payment_pos = amount_to_pos(amount_msat, capacity_msat);
- if payment_pos >= POSITION_TICKS { return None; }
-
- // Check if all our buckets are zero, once decayed and treat it as if we had no data. We
- // don't actually use the decayed buckets, though, as that would lose precision.
- let (total_valid_points_tracked, _)
- = self.get_total_valid_points(now, last_updated, half_life)?;
-
let mut cumulative_success_prob_times_billion = 0;
// Special-case the 0th min bucket - it generally means we failed a payment, so only
// consider the highest (i.e. largest-offset-from-max-capacity) max bucket for all
network_graph,
logger,
channel_liquidities,
+ _unused_time: core::marker::PhantomData,
})
}
}
-impl<T: Time> Writeable for ChannelLiquidity<T> {
+impl Writeable for ChannelLiquidity {
#[inline]
fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
- let duration_since_epoch = T::duration_since_epoch() - self.last_updated.elapsed();
write_tlv_fields!(w, {
(0, self.min_liquidity_offset_msat, required),
// 1 was the min_liquidity_offset_history in octile form
(2, self.max_liquidity_offset_msat, required),
// 3 was the max_liquidity_offset_history in octile form
- (4, duration_since_epoch, required),
+ (4, self.last_updated, required),
(5, Some(self.min_liquidity_offset_history), option),
(7, Some(self.max_liquidity_offset_history), option),
+ (9, self.offset_history_last_updated, required),
});
Ok(())
}
}
-impl<T: Time> Readable for ChannelLiquidity<T> {
+impl Readable for ChannelLiquidity {
#[inline]
fn read<R: Read>(r: &mut R) -> Result<Self, DecodeError> {
let mut min_liquidity_offset_msat = 0;
let mut legacy_max_liq_offset_history: Option<LegacyHistoricalBucketRangeTracker> = None;
let mut min_liquidity_offset_history: Option<HistoricalBucketRangeTracker> = None;
let mut max_liquidity_offset_history: Option<HistoricalBucketRangeTracker> = None;
- let mut duration_since_epoch = Duration::from_secs(0);
+ let mut last_updated = Duration::from_secs(0);
+ let mut offset_history_last_updated = None;
read_tlv_fields!(r, {
(0, min_liquidity_offset_msat, required),
(1, legacy_min_liq_offset_history, option),
(2, max_liquidity_offset_msat, required),
(3, legacy_max_liq_offset_history, option),
- (4, duration_since_epoch, required),
+ (4, last_updated, required),
(5, min_liquidity_offset_history, option),
(7, max_liquidity_offset_history, option),
+ (9, offset_history_last_updated, option),
});
- // On rust prior to 1.60 `Instant::duration_since` will panic if time goes backwards.
- // We write `last_updated` as wallclock time even though its ultimately an `Instant` (which
- // is a time from a monotonic clock usually represented as an offset against boot time).
- // Thus, we have to construct an `Instant` by subtracting the difference in wallclock time
- // from the one that was written. However, because `Instant` can panic if we construct one
- // in the future, we must handle wallclock time jumping backwards, which we do by simply
- // using `Instant::now()` in that case.
- let wall_clock_now = T::duration_since_epoch();
- let now = T::now();
- let last_updated = if wall_clock_now > duration_since_epoch {
- now - (wall_clock_now - duration_since_epoch)
- } else { now };
+
if min_liquidity_offset_history.is_none() {
if let Some(legacy_buckets) = legacy_min_liq_offset_history {
min_liquidity_offset_history = Some(legacy_buckets.into_current());
min_liquidity_offset_history: min_liquidity_offset_history.unwrap(),
max_liquidity_offset_history: max_liquidity_offset_history.unwrap(),
last_updated,
+ offset_history_last_updated: offset_history_last_updated.unwrap_or(last_updated),
})
}
}
use super::{ChannelLiquidity, HistoricalBucketRangeTracker, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters, ProbabilisticScorerUsingTime};
use crate::blinded_path::{BlindedHop, BlindedPath};
use crate::util::config::UserConfig;
- use crate::util::time::Time;
use crate::util::time::tests::SinceEpoch;
use crate::ln::channelmanager;
#[test]
fn liquidity_bounds_directed_from_lowest_node_id() {
let logger = TestLogger::new();
- let last_updated = SinceEpoch::now();
+ let last_updated = Duration::ZERO;
+ let offset_history_last_updated = Duration::ZERO;
let network_graph = network_graph(&logger);
let decay_params = ProbabilisticScoringDecayParameters::default();
let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
.with_channel(42,
ChannelLiquidity {
- min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated,
+ min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100,
+ last_updated, offset_history_last_updated,
min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
})
.with_channel(43,
ChannelLiquidity {
- min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated,
+ min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100,
+ last_updated, offset_history_last_updated,
min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
});
scorer.channel_liquidities.get_mut(&42).unwrap()
.as_directed_mut(&source, &target, 1_000, decay_params)
- .set_min_liquidity_msat(200);
+ .set_min_liquidity_msat(200, Duration::ZERO);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
.as_directed(&source, &target, 1_000, decay_params);
scorer.channel_liquidities.get_mut(&43).unwrap()
.as_directed_mut(&target, &recipient, 1_000, decay_params)
- .set_max_liquidity_msat(200);
+ .set_max_liquidity_msat(200, Duration::ZERO);
let liquidity = scorer.channel_liquidities.get(&43).unwrap()
.as_directed(&target, &recipient, 1_000, decay_params);
#[test]
fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() {
let logger = TestLogger::new();
- let last_updated = SinceEpoch::now();
+ let last_updated = Duration::ZERO;
+ let offset_history_last_updated = Duration::ZERO;
let network_graph = network_graph(&logger);
let decay_params = ProbabilisticScoringDecayParameters::default();
let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
.with_channel(42,
ChannelLiquidity {
- min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated,
+ min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400,
+ last_updated, offset_history_last_updated,
min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
});
// Reset from source to target.
scorer.channel_liquidities.get_mut(&42).unwrap()
.as_directed_mut(&source, &target, 1_000, decay_params)
- .set_min_liquidity_msat(900);
+ .set_min_liquidity_msat(900, Duration::ZERO);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
.as_directed(&source, &target, 1_000, decay_params);
// Reset from target to source.
scorer.channel_liquidities.get_mut(&42).unwrap()
.as_directed_mut(&target, &source, 1_000, decay_params)
- .set_min_liquidity_msat(400);
+ .set_min_liquidity_msat(400, Duration::ZERO);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
.as_directed(&source, &target, 1_000, decay_params);
#[test]
fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() {
let logger = TestLogger::new();
- let last_updated = SinceEpoch::now();
+ let last_updated = Duration::ZERO;
+ let offset_history_last_updated = Duration::ZERO;
let network_graph = network_graph(&logger);
let decay_params = ProbabilisticScoringDecayParameters::default();
let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
.with_channel(42,
ChannelLiquidity {
- min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated,
+ min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400,
+ last_updated, offset_history_last_updated,
min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
});
// Reset from source to target.
scorer.channel_liquidities.get_mut(&42).unwrap()
.as_directed_mut(&source, &target, 1_000, decay_params)
- .set_max_liquidity_msat(300);
+ .set_max_liquidity_msat(300, Duration::ZERO);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
.as_directed(&source, &target, 1_000, decay_params);
// Reset from target to source.
scorer.channel_liquidities.get_mut(&42).unwrap()
.as_directed_mut(&target, &source, 1_000, decay_params)
- .set_max_liquidity_msat(600);
+ .set_max_liquidity_msat(600, Duration::ZERO);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
.as_directed(&source, &target, 1_000, decay_params);
#[test]
fn constant_penalty_outside_liquidity_bounds() {
let logger = TestLogger::new();
- let last_updated = SinceEpoch::now();
+ let last_updated = Duration::ZERO;
+ let offset_history_last_updated = Duration::ZERO;
let network_graph = network_graph(&logger);
let params = ProbabilisticScoringFeeParameters {
liquidity_penalty_multiplier_msat: 1_000,
let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger)
.with_channel(42,
ChannelLiquidity {
- min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40, last_updated,
+ min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40,
+ last_updated, offset_history_last_updated,
min_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
max_liquidity_offset_history: HistoricalBucketRangeTracker::new(),
});
let usage = ChannelUsage { amount_msat: 896, ..usage };
assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
- // No decay
- SinceEpoch::advance(Duration::from_secs(4));
- let usage = ChannelUsage { amount_msat: 128, ..usage };
- assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
- let usage = ChannelUsage { amount_msat: 256, ..usage };
- assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 93);
- let usage = ChannelUsage { amount_msat: 768, ..usage };
- assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 1_479);
- let usage = ChannelUsage { amount_msat: 896, ..usage };
- assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
-
// Half decay (i.e., three-quarter life)
- SinceEpoch::advance(Duration::from_secs(1));
+ SinceEpoch::advance(Duration::from_secs(5));
+ scorer.decay_liquidity_certainty(Duration::from_secs(5));
let usage = ChannelUsage { amount_msat: 128, ..usage };
assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 22);
let usage = ChannelUsage { amount_msat: 256, ..usage };
// One decay (i.e., half life)
SinceEpoch::advance(Duration::from_secs(5));
+ scorer.decay_liquidity_certainty(Duration::from_secs(10));
let usage = ChannelUsage { amount_msat: 64, ..usage };
assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
let usage = ChannelUsage { amount_msat: 128, ..usage };
// Fully decay liquidity lower bound.
SinceEpoch::advance(Duration::from_secs(10 * 7));
+ scorer.decay_liquidity_certainty(Duration::from_secs(10 * 8));
let usage = ChannelUsage { amount_msat: 0, ..usage };
assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
let usage = ChannelUsage { amount_msat: 1, ..usage };
// Fully decay liquidity upper bound.
SinceEpoch::advance(Duration::from_secs(10));
+ scorer.decay_liquidity_certainty(Duration::from_secs(10 * 9));
let usage = ChannelUsage { amount_msat: 0, ..usage };
assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
let usage = ChannelUsage { amount_msat: 1_024, ..usage };
assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
SinceEpoch::advance(Duration::from_secs(10));
+ scorer.decay_liquidity_certainty(Duration::from_secs(10 * 10));
let usage = ChannelUsage { amount_msat: 0, ..usage };
assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 0);
let usage = ChannelUsage { amount_msat: 1_024, ..usage };
// An unchecked right shift 64 bits or more in DirectedChannelLiquidity::decayed_offset_msat
// would cause an overflow.
SinceEpoch::advance(Duration::from_secs(10 * 64));
+ scorer.decay_liquidity_certainty(Duration::from_secs(10 * 64));
assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 125);
SinceEpoch::advance(Duration::from_secs(10));
+ scorer.decay_liquidity_certainty(Duration::from_secs(10 * 65));
assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 125);
}
// Decaying knowledge gives less confidence (128, 896), meaning a higher penalty.
SinceEpoch::advance(Duration::from_secs(10));
+ scorer.decay_liquidity_certainty(Duration::from_secs(10));
assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 291);
// Reducing the upper bound gives more confidence (128, 832) that the payment amount (512)
// Further decaying affects the lower bound more than the upper bound (128, 928).
SinceEpoch::advance(Duration::from_secs(10));
+ scorer.decay_liquidity_certainty(Duration::from_secs(20));
assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 280);
}
assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
SinceEpoch::advance(Duration::from_secs(10));
+ scorer.decay_liquidity_certainty(Duration::from_secs(10));
assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 473);
scorer.payment_path_failed(&payment_path_for_amount(250), 43, Duration::from_secs(10));
assert_eq!(deserialized_scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300);
}
- #[test]
- fn decays_persisted_liquidity_bounds() {
+ fn do_decays_persisted_liquidity_bounds(decay_before_reload: bool) {
let logger = TestLogger::new();
let network_graph = network_graph(&logger);
let params = ProbabilisticScoringFeeParameters {
};
assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), u64::max_value());
+ if decay_before_reload {
+ SinceEpoch::advance(Duration::from_secs(10));
+ scorer.decay_liquidity_certainty(Duration::from_secs(10));
+ }
+
let mut serialized_scorer = Vec::new();
scorer.write(&mut serialized_scorer).unwrap();
- SinceEpoch::advance(Duration::from_secs(10));
-
let mut serialized_scorer = io::Cursor::new(&serialized_scorer);
- let deserialized_scorer =
+ let mut deserialized_scorer =
<ProbabilisticScorer>::read(&mut serialized_scorer, (decay_params, &network_graph, &logger)).unwrap();
+ if !decay_before_reload {
+ SinceEpoch::advance(Duration::from_secs(10));
+ scorer.decay_liquidity_certainty(Duration::from_secs(10));
+ deserialized_scorer.decay_liquidity_certainty(Duration::from_secs(10));
+ }
assert_eq!(deserialized_scorer.channel_penalty_msat(&candidate, usage, ¶ms), 473);
scorer.payment_path_failed(&payment_path_for_amount(250), 43, Duration::from_secs(10));
assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 300);
SinceEpoch::advance(Duration::from_secs(10));
+ deserialized_scorer.decay_liquidity_certainty(Duration::from_secs(20));
assert_eq!(deserialized_scorer.channel_penalty_msat(&candidate, usage, ¶ms), 370);
}
+ #[test]
+ fn decays_persisted_liquidity_bounds() {
+ do_decays_persisted_liquidity_bounds(false);
+ do_decays_persisted_liquidity_bounds(true);
+ }
+
#[test]
fn scores_realistic_payments() {
// Shows the scores of "realistic" sends of 100k sats over channels of 1-10m sats (with a
// Advance the time forward 16 half-lives (which the docs claim will ensure all data is
// gone), and check that we're back to where we started.
SinceEpoch::advance(Duration::from_secs(10 * 16));
+ scorer.decay_liquidity_certainty(Duration::from_secs(10 * 16));
{
let network_graph = network_graph.read_only();
let channel = network_graph.channel(42).unwrap();
// Once fully decayed we still have data, but its all-0s. In the future we may remove the
// data entirely instead.
assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
- None);
+ Some(([0; 32], [0; 32])));
assert_eq!(scorer.historical_estimated_payment_success_probability(42, &target, 1, ¶ms), None);
let mut usage = ChannelUsage {
};
assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 2050);
- usage.inflight_htlc_msat = 0;
- assert_eq!(scorer.channel_penalty_msat(&candidate, usage, ¶ms), 866);
let usage = ChannelUsage {
amount_msat: 1,
// Advance to decay all liquidity offsets to zero.
SinceEpoch::advance(Duration::from_secs(60 * 60 * 10));
+ scorer.decay_liquidity_certainty(Duration::from_secs(10 * (16 + 60 * 60)));
+
+ // Once even the bounds have decayed information about the channel should be removed
+ // entirely.
+ assert_eq!(scorer.historical_estimated_channel_liquidity_probabilities(42, &target),
+ None);
// Use a path in the opposite direction, which have zero for htlc_maximum_msat. This will
// ensure that the effective capacity is zero to test division-by-zero edge cases.
projects / rust-lightning / blobdiff