/// formula, but using the history of a channel rather than our latest estimates for the liquidity
/// bounds.
///
-/// # Note
-///
-/// Mixing the `no-std` feature between serialization and deserialization results in undefined
-/// behavior.
-///
/// [1]: https://arxiv.org/abs/2107.05322
/// [`liquidity_penalty_multiplier_msat`]: ProbabilisticScoringFeeParameters::liquidity_penalty_multiplier_msat
/// [`liquidity_penalty_amount_multiplier_msat`]: ProbabilisticScoringFeeParameters::liquidity_penalty_amount_multiplier_msat
capacity_msat: u64,
last_updated: T,
offset_history_last_updated: T,
- decay_params: ProbabilisticScoringDecayParameters,
}
impl<G: Deref<Target = NetworkGraph<L>>, L: Deref> ProbabilisticScorer<G, L> where L::Target: Logger {
let log_direction = |source, target| {
if let Some((directed_info, _)) = chan_debug.as_directed_to(target) {
let amt = directed_info.effective_capacity().as_msat();
- let dir_liq = liq.as_directed(source, target, amt, self.decay_params);
+ let dir_liq = liq.as_directed(source, target, amt);
let min_buckets = &dir_liq.liquidity_history.min_liquidity_offset_history.buckets;
let max_buckets = &dir_liq.liquidity_history.max_liquidity_offset_history.buckets;
if let Some(liq) = self.channel_liquidities.get(&scid) {
if let Some((directed_info, source)) = chan.as_directed_to(target) {
let amt = directed_info.effective_capacity().as_msat();
- let dir_liq = liq.as_directed(source, target, amt, self.decay_params);
+ let dir_liq = liq.as_directed(source, target, amt);
return Some((dir_liq.min_liquidity_msat(), dir_liq.max_liquidity_msat()));
}
}
if let Some(liq) = self.channel_liquidities.get(&scid) {
if let Some((directed_info, source)) = chan.as_directed_to(target) {
let amt = directed_info.effective_capacity().as_msat();
- let dir_liq = liq.as_directed(source, target, amt, self.decay_params);
+ let dir_liq = liq.as_directed(source, target, amt);
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;
if let Some(liq) = self.channel_liquidities.get(&scid) {
if let Some((directed_info, source)) = chan.as_directed_to(target) {
let capacity_msat = directed_info.effective_capacity().as_msat();
- let dir_liq = liq.as_directed(source, target, capacity_msat, self.decay_params);
+ let dir_liq = liq.as_directed(source, target, capacity_msat);
return dir_liq.liquidity_history.calculate_success_probability_times_billion(
¶ms, amount_msat, capacity_msat
/// Returns a view of the channel liquidity directed from `source` to `target` assuming
/// `capacity_msat`.
fn as_directed(
- &self, source: &NodeId, target: &NodeId, capacity_msat: u64, decay_params: ProbabilisticScoringDecayParameters
+ &self, source: &NodeId, target: &NodeId, capacity_msat: u64,
) -> DirectedChannelLiquidity<&u64, &HistoricalBucketRangeTracker, &Duration> {
let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) =
if source < target {
capacity_msat,
last_updated: &self.last_updated,
offset_history_last_updated: &self.offset_history_last_updated,
- decay_params: decay_params,
}
}
/// Returns a mutable view of the channel liquidity directed from `source` to `target` assuming
/// `capacity_msat`.
fn as_directed_mut(
- &mut self, source: &NodeId, target: &NodeId, capacity_msat: u64, decay_params: ProbabilisticScoringDecayParameters
+ &mut self, source: &NodeId, target: &NodeId, capacity_msat: u64,
) -> 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 {
capacity_msat,
last_updated: &mut self.last_updated,
offset_history_last_updated: &mut self.offset_history_last_updated,
- decay_params: decay_params,
}
}
/// Returns the lower bound of the channel liquidity balance in this direction.
#[inline(always)]
fn min_liquidity_msat(&self) -> u64 {
- self.decayed_offset_msat(*self.min_liquidity_offset_msat)
+ *self.min_liquidity_offset_msat
}
/// Returns the upper bound of the channel liquidity balance in this direction.
#[inline(always)]
fn max_liquidity_msat(&self) -> u64 {
self.capacity_msat
- .saturating_sub(self.decayed_offset_msat(*self.max_liquidity_offset_msat))
- }
-
- fn decayed_offset_msat(&self, offset_msat: u64) -> u64 {
- offset_msat
+ .saturating_sub(*self.max_liquidity_offset_msat)
}
}
/// 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, 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.time_decay_data(half_lives);
-
- let min_liquidity_offset_msat = self.decayed_offset_msat(*self.min_liquidity_offset_msat);
self.liquidity_history.min_liquidity_offset_history.track_datapoint(
- min_liquidity_offset_msat + bucket_offset_msat, self.capacity_msat
+ *self.min_liquidity_offset_msat + bucket_offset_msat, self.capacity_msat
);
- let max_liquidity_offset_msat = self.decayed_offset_msat(*self.max_liquidity_offset_msat);
self.liquidity_history.max_liquidity_offset_history.track_datapoint(
- max_liquidity_offset_msat.saturating_sub(bucket_offset_msat), self.capacity_msat
+ self.max_liquidity_offset_msat.saturating_sub(bucket_offset_msat), self.capacity_msat
);
*self.offset_history_last_updated = duration_since_epoch;
}
self.channel_liquidities
.get(&scid)
.unwrap_or(&ChannelLiquidity::new(Duration::ZERO))
- .as_directed(&source, &target, capacity_msat, self.decay_params)
+ .as_directed(&source, &target, capacity_msat)
.penalty_msat(amount_msat, score_params)
.saturating_add(anti_probing_penalty_msat)
.saturating_add(base_penalty_msat)
self.channel_liquidities
.entry(hop.short_channel_id)
.or_insert_with(|| ChannelLiquidity::new(duration_since_epoch))
- .as_directed_mut(source, &target, capacity_msat, self.decay_params)
+ .as_directed_mut(source, &target, capacity_msat)
.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(duration_since_epoch))
- .as_directed_mut(source, &target, capacity_msat, self.decay_params)
+ .as_directed_mut(source, &target, capacity_msat)
.failed_downstream(amount_msat, duration_since_epoch,
format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
}
self.channel_liquidities
.entry(hop.short_channel_id)
.or_insert_with(|| ChannelLiquidity::new(duration_since_epoch))
- .as_directed_mut(source, &target, capacity_msat, self.decay_params)
+ .as_directed_mut(source, &target, capacity_msat)
.successful(amount_msat, duration_since_epoch,
format_args!("SCID {}, towards {:?}", hop.short_channel_id, target), &self.logger);
} else {
self.buckets[bucket] = self.buckets[bucket].saturating_add(BUCKET_FIXED_POINT_ONE);
}
}
- /// Decay all buckets by the given number of half-lives. Used to more aggressively remove old
- /// datapoints as we receive newer information.
- #[inline]
- pub(super) fn time_decay_data(&mut self, half_lives: u32) {
- for e in self.buckets.iter_mut() {
- *e = e.checked_shr(half_lives).unwrap_or(0);
- }
- }
}
impl_writeable_tlv_based!(HistoricalBucketRangeTracker, { (0, buckets, required) });
// Update minimum liquidity.
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
- .as_directed(&source, &target, 1_000, decay_params);
+ .as_directed(&source, &target, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 100);
assert_eq!(liquidity.max_liquidity_msat(), 300);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
- .as_directed(&target, &source, 1_000, decay_params);
+ .as_directed(&target, &source, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 700);
assert_eq!(liquidity.max_liquidity_msat(), 900);
scorer.channel_liquidities.get_mut(&42).unwrap()
- .as_directed_mut(&source, &target, 1_000, decay_params)
+ .as_directed_mut(&source, &target, 1_000)
.set_min_liquidity_msat(200, Duration::ZERO);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
- .as_directed(&source, &target, 1_000, decay_params);
+ .as_directed(&source, &target, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 200);
assert_eq!(liquidity.max_liquidity_msat(), 300);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
- .as_directed(&target, &source, 1_000, decay_params);
+ .as_directed(&target, &source, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 700);
assert_eq!(liquidity.max_liquidity_msat(), 800);
// Update maximum liquidity.
let liquidity = scorer.channel_liquidities.get(&43).unwrap()
- .as_directed(&target, &recipient, 1_000, decay_params);
+ .as_directed(&target, &recipient, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 700);
assert_eq!(liquidity.max_liquidity_msat(), 900);
let liquidity = scorer.channel_liquidities.get(&43).unwrap()
- .as_directed(&recipient, &target, 1_000, decay_params);
+ .as_directed(&recipient, &target, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 100);
assert_eq!(liquidity.max_liquidity_msat(), 300);
scorer.channel_liquidities.get_mut(&43).unwrap()
- .as_directed_mut(&target, &recipient, 1_000, decay_params)
+ .as_directed_mut(&target, &recipient, 1_000)
.set_max_liquidity_msat(200, Duration::ZERO);
let liquidity = scorer.channel_liquidities.get(&43).unwrap()
- .as_directed(&target, &recipient, 1_000, decay_params);
+ .as_directed(&target, &recipient, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 0);
assert_eq!(liquidity.max_liquidity_msat(), 200);
let liquidity = scorer.channel_liquidities.get(&43).unwrap()
- .as_directed(&recipient, &target, 1_000, decay_params);
+ .as_directed(&recipient, &target, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 800);
assert_eq!(liquidity.max_liquidity_msat(), 1000);
}
// Check initial bounds.
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
- .as_directed(&source, &target, 1_000, decay_params);
+ .as_directed(&source, &target, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 400);
assert_eq!(liquidity.max_liquidity_msat(), 800);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
- .as_directed(&target, &source, 1_000, decay_params);
+ .as_directed(&target, &source, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 200);
assert_eq!(liquidity.max_liquidity_msat(), 600);
// Reset from source to target.
scorer.channel_liquidities.get_mut(&42).unwrap()
- .as_directed_mut(&source, &target, 1_000, decay_params)
+ .as_directed_mut(&source, &target, 1_000)
.set_min_liquidity_msat(900, Duration::ZERO);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
- .as_directed(&source, &target, 1_000, decay_params);
+ .as_directed(&source, &target, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 900);
assert_eq!(liquidity.max_liquidity_msat(), 1_000);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
- .as_directed(&target, &source, 1_000, decay_params);
+ .as_directed(&target, &source, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 0);
assert_eq!(liquidity.max_liquidity_msat(), 100);
// Reset from target to source.
scorer.channel_liquidities.get_mut(&42).unwrap()
- .as_directed_mut(&target, &source, 1_000, decay_params)
+ .as_directed_mut(&target, &source, 1_000)
.set_min_liquidity_msat(400, Duration::ZERO);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
- .as_directed(&source, &target, 1_000, decay_params);
+ .as_directed(&source, &target, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 0);
assert_eq!(liquidity.max_liquidity_msat(), 600);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
- .as_directed(&target, &source, 1_000, decay_params);
+ .as_directed(&target, &source, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 400);
assert_eq!(liquidity.max_liquidity_msat(), 1_000);
}
// Check initial bounds.
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
- .as_directed(&source, &target, 1_000, decay_params);
+ .as_directed(&source, &target, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 400);
assert_eq!(liquidity.max_liquidity_msat(), 800);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
- .as_directed(&target, &source, 1_000, decay_params);
+ .as_directed(&target, &source, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 200);
assert_eq!(liquidity.max_liquidity_msat(), 600);
// Reset from source to target.
scorer.channel_liquidities.get_mut(&42).unwrap()
- .as_directed_mut(&source, &target, 1_000, decay_params)
+ .as_directed_mut(&source, &target, 1_000)
.set_max_liquidity_msat(300, Duration::ZERO);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
- .as_directed(&source, &target, 1_000, decay_params);
+ .as_directed(&source, &target, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 0);
assert_eq!(liquidity.max_liquidity_msat(), 300);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
- .as_directed(&target, &source, 1_000, decay_params);
+ .as_directed(&target, &source, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 700);
assert_eq!(liquidity.max_liquidity_msat(), 1_000);
// Reset from target to source.
scorer.channel_liquidities.get_mut(&42).unwrap()
- .as_directed_mut(&target, &source, 1_000, decay_params)
+ .as_directed_mut(&target, &source, 1_000)
.set_max_liquidity_msat(600, Duration::ZERO);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
- .as_directed(&source, &target, 1_000, decay_params);
+ .as_directed(&source, &target, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 400);
assert_eq!(liquidity.max_liquidity_msat(), 1_000);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
- .as_directed(&target, &source, 1_000, decay_params);
+ .as_directed(&target, &source, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 0);
assert_eq!(liquidity.max_liquidity_msat(), 600);
}
scorer.payment_path_failed(&path, 43, Duration::ZERO);
let liquidity = scorer.channel_liquidities.get(&42).unwrap()
- .as_directed(&source, &target, 1_000, decay_params);
+ .as_directed(&source, &target, 1_000);
assert_eq!(liquidity.min_liquidity_msat(), 256);
assert_eq!(liquidity.max_liquidity_msat(), 768);
}
Some(0.0));
}
}
+
+#[cfg(ldk_bench)]
+pub mod benches {
+ use super::*;
+ use criterion::Criterion;
+ use crate::routing::router::{bench_utils, RouteHop};
+ use crate::util::test_utils::TestLogger;
+ use crate::ln::features::{ChannelFeatures, NodeFeatures};
+
+ pub fn decay_100k_channel_bounds(bench: &mut Criterion) {
+ let logger = TestLogger::new();
+ let network_graph = bench_utils::read_network_graph(&logger).unwrap();
+ let mut scorer = ProbabilisticScorer::new(Default::default(), &network_graph, &logger);
+ // Score a number of random channels
+ let mut seed: u64 = 0xdeadbeef;
+ for _ in 0..100_000 {
+ seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0;
+ let (victim, victim_dst, amt) = {
+ let rong = network_graph.read_only();
+ let channels = rong.channels();
+ let chan = channels.unordered_iter()
+ .skip((seed as usize) % channels.len())
+ .next().unwrap();
+ seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0;
+ let amt = seed % chan.1.capacity_sats.map(|c| c * 1000)
+ .or(chan.1.one_to_two.as_ref().map(|info| info.htlc_maximum_msat))
+ .or(chan.1.two_to_one.as_ref().map(|info| info.htlc_maximum_msat))
+ .unwrap_or(1_000_000_000).saturating_add(1);
+ (*chan.0, chan.1.node_two, amt)
+ };
+ let path = Path {
+ hops: vec![RouteHop {
+ pubkey: victim_dst.as_pubkey().unwrap(),
+ node_features: NodeFeatures::empty(),
+ short_channel_id: victim,
+ channel_features: ChannelFeatures::empty(),
+ fee_msat: amt,
+ cltv_expiry_delta: 42,
+ maybe_announced_channel: true,
+ }],
+ blinded_tail: None
+ };
+ seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0;
+ if seed % 1 == 0 {
+ scorer.probe_failed(&path, victim, Duration::ZERO);
+ } else {
+ scorer.probe_successful(&path, Duration::ZERO);
+ }
+ }
+ let mut cur_time = Duration::ZERO;
+ cur_time += Duration::from_millis(1);
+ scorer.decay_liquidity_certainty(cur_time);
+ bench.bench_function("decay_100k_channel_bounds", |b| b.iter(|| {
+ cur_time += Duration::from_millis(1);
+ scorer.decay_liquidity_certainty(cur_time);
+ }));
+ }
+}