penalty_msat: u64,
}
-impl_writeable_tlv_based!(FixedPenaltyScorer, {
- (0, penalty_msat, required),
-});
-
impl FixedPenaltyScorer {
/// Creates a new scorer using `penalty_msat`.
pub fn with_penalty(penalty_msat: u64) -> Self {
fn payment_path_successful(&mut self, _path: &[&RouteHop]) {}
}
+impl Writeable for FixedPenaltyScorer {
+ #[inline]
+ fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
+ write_tlv_fields!(w, {});
+ Ok(())
+ }
+}
+
+impl ReadableArgs<u64> for FixedPenaltyScorer {
+ #[inline]
+ fn read<R: Read>(r: &mut R, penalty_msat: u64) -> Result<Self, DecodeError> {
+ read_tlv_fields!(r, {});
+ Ok(Self { penalty_msat })
+ }
+}
+
/// [`Score`] implementation that provides reasonable default behavior.
///
/// Used to apply a fixed penalty to each channel, thus avoiding long paths when shorter paths with
}
/// Parameters for configuring [`ProbabilisticScorer`].
+///
+/// Used to configure base, liquidity, and amount penalties, the sum of which comprises the channel
+/// penalty (i.e., the amount in msats willing to be paid to avoid routing through the channel).
#[derive(Clone, Copy)]
pub struct ProbabilisticScoringParameters {
- /// A multiplier used to determine the amount in msats willing to be paid to avoid routing
- /// through a channel, as per multiplying by the negative `log10` of the channel's success
- /// probability for a payment.
+ /// A fixed penalty in msats to apply to each channel.
+ ///
+ /// Default value: 500 msat
+ pub base_penalty_msat: u64,
+
+ /// A multiplier used in conjunction with the negative `log10` of the channel's success
+ /// probability for a payment to determine the liquidity penalty.
///
- /// The success probability is determined by the effective channel capacity, the payment amount,
- /// and knowledge learned from prior successful and unsuccessful payments. The lower bound of
- /// the success probability is 0.01, effectively limiting the penalty to the range
- /// `0..=2*liquidity_penalty_multiplier_msat`. The knowledge learned is decayed over time based
- /// on [`liquidity_offset_half_life`].
+ /// The penalty is based in part on the knowledge learned from prior successful and unsuccessful
+ /// payments. This knowledge is decayed over time based on [`liquidity_offset_half_life`]. The
+ /// penalty is effectively limited to `2 * liquidity_penalty_multiplier_msat` (corresponding to
+ /// lower bounding the success probability to `0.01`) when the amount falls within the
+ /// uncertainty bounds of the channel liquidity balance. Amounts above the upper bound will
+ /// result in a `u64::max_value` penalty, however.
///
- /// Default value: 10,000 msat
+ /// Default value: 40,000 msat
///
/// [`liquidity_offset_half_life`]: Self::liquidity_offset_half_life
pub liquidity_penalty_multiplier_msat: u64,
/// When built with the `no-std` feature, time will never elapse. Therefore, the channel
/// liquidity knowledge will never decay except when the bounds cross.
pub liquidity_offset_half_life: Duration,
-}
-impl_writeable_tlv_based!(ProbabilisticScoringParameters, {
- (0, liquidity_penalty_multiplier_msat, required),
- (2, liquidity_offset_half_life, required),
-});
+ /// A multiplier used in conjunction with a payment amount and the negative `log10` of the
+ /// channel's success probability for the payment to determine the amount penalty.
+ ///
+ /// The purpose of the amount penalty is to avoid having fees dominate the channel cost (i.e.,
+ /// fees plus penalty) for large payments. The penalty is computed as the product of this
+ /// multiplier and `2^20`ths of the payment amount, weighted by the negative `log10` of the
+ /// success probability.
+ ///
+ /// `-log10(success_probability) * amount_penalty_multiplier_msat * amount_msat / 2^20`
+ ///
+ /// In practice, this means for 0.1 success probability (`-log10(0.1) == 1`) each `2^20`th of
+ /// the amount will result in a penalty of the multiplier. And, as the success probability
+ /// decreases, the negative `log10` weighting will increase dramatically. For higher success
+ /// probabilities, the multiplier will have a decreasing effect as the negative `log10` will
+ /// fall below `1`.
+ ///
+ /// Default value: 256 msat
+ pub amount_penalty_multiplier_msat: u64,
+}
/// Accounting for channel liquidity balance uncertainty.
///
}
}
+impl ProbabilisticScoringParameters {
+ #[cfg(test)]
+ fn zero_penalty() -> Self {
+ Self {
+ base_penalty_msat: 0,
+ liquidity_penalty_multiplier_msat: 0,
+ liquidity_offset_half_life: Duration::from_secs(3600),
+ amount_penalty_multiplier_msat: 0,
+ }
+ }
+}
+
impl Default for ProbabilisticScoringParameters {
fn default() -> Self {
Self {
- liquidity_penalty_multiplier_msat: 10_000,
+ base_penalty_msat: 500,
+ liquidity_penalty_multiplier_msat: 40_000,
liquidity_offset_half_life: Duration::from_secs(3600),
+ amount_penalty_multiplier_msat: 256,
}
}
}
}
}
+/// Bounds `-log10` to avoid excessive liquidity penalties for payments with low success
+/// probabilities.
+const NEGATIVE_LOG10_UPPER_BOUND: u64 = 2;
+
+/// The divisor used when computing the amount penalty.
+const AMOUNT_PENALTY_DIVISOR: u64 = 1 << 20;
+
impl<L: Deref<Target = u64>, T: Time, U: Deref<Target = T>> DirectedChannelLiquidity<L, T, U> {
/// Returns a penalty for routing the given HTLC `amount_msat` through the channel in this
/// direction.
- fn penalty_msat(&self, amount_msat: u64, liquidity_penalty_multiplier_msat: u64) -> u64 {
+ fn penalty_msat(&self, amount_msat: u64, params: ProbabilisticScoringParameters) -> u64 {
let max_liquidity_msat = self.max_liquidity_msat();
let min_liquidity_msat = core::cmp::min(self.min_liquidity_msat(), max_liquidity_msat);
- if amount_msat > max_liquidity_msat {
- u64::max_value()
- } else if amount_msat <= min_liquidity_msat {
+ if amount_msat <= min_liquidity_msat {
0
+ } else if amount_msat >= max_liquidity_msat {
+ if amount_msat > max_liquidity_msat {
+ u64::max_value()
+ } else if max_liquidity_msat != self.capacity_msat {
+ // Avoid using the failed channel on retry.
+ u64::max_value()
+ } else {
+ // Equivalent to hitting the else clause below with the amount equal to the
+ // effective capacity and without any certainty on the liquidity upper bound.
+ let negative_log10_times_1024 = NEGATIVE_LOG10_UPPER_BOUND * 1024;
+ self.combined_penalty_msat(amount_msat, negative_log10_times_1024, params)
+ }
} else {
- let numerator = max_liquidity_msat + 1 - amount_msat;
- let denominator = max_liquidity_msat + 1 - min_liquidity_msat;
- approx::negative_log10_times_1024(numerator, denominator)
- .saturating_mul(liquidity_penalty_multiplier_msat) / 1024
+ let numerator = (max_liquidity_msat - amount_msat).saturating_add(1);
+ let denominator = (max_liquidity_msat - min_liquidity_msat).saturating_add(1);
+ let negative_log10_times_1024 =
+ approx::negative_log10_times_1024(numerator, denominator);
+ self.combined_penalty_msat(amount_msat, negative_log10_times_1024, params)
}
- // Upper bound the penalty to ensure some channel is selected.
- .min(2 * liquidity_penalty_multiplier_msat)
+ }
+
+ /// Computes the liquidity and amount penalties and adds them to the base penalty.
+ #[inline(always)]
+ fn combined_penalty_msat(
+ &self, amount_msat: u64, negative_log10_times_1024: u64,
+ params: ProbabilisticScoringParameters
+ ) -> u64 {
+ let liquidity_penalty_msat = {
+ // Upper bound the liquidity penalty to ensure some channel is selected.
+ let multiplier_msat = params.liquidity_penalty_multiplier_msat;
+ let max_penalty_msat = multiplier_msat.saturating_mul(NEGATIVE_LOG10_UPPER_BOUND);
+ (negative_log10_times_1024.saturating_mul(multiplier_msat) / 1024).min(max_penalty_msat)
+ };
+ let amount_penalty_msat = negative_log10_times_1024
+ .saturating_mul(params.amount_penalty_multiplier_msat)
+ .saturating_mul(amount_msat) / 1024 / AMOUNT_PENALTY_DIVISOR;
+
+ params.base_penalty_msat
+ .saturating_add(liquidity_penalty_msat)
+ .saturating_add(amount_penalty_msat)
}
/// Returns the lower bound of the channel liquidity balance in this direction.
&self, short_channel_id: u64, amount_msat: u64, capacity_msat: u64, source: &NodeId,
target: &NodeId
) -> u64 {
- let liquidity_penalty_multiplier_msat = self.params.liquidity_penalty_multiplier_msat;
let liquidity_offset_half_life = self.params.liquidity_offset_half_life;
self.channel_liquidities
.get(&short_channel_id)
.unwrap_or(&ChannelLiquidity::new())
.as_directed(source, target, capacity_msat, liquidity_offset_half_life)
- .penalty_msat(amount_msat, liquidity_penalty_multiplier_msat)
+ .penalty_msat(amount_msat, self.params)
}
fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
}
}
-impl<G, T> ReadableArgs<(ProbabilisticScoringParameters, G)> for ProbabilisticScorerUsingTime<G, T>
-where
- G: Deref<Target = NetworkGraph>,
- T: Time,
-{
+impl<G: Deref<Target = NetworkGraph>, T: Time>
+ReadableArgs<(ProbabilisticScoringParameters, G)> for ProbabilisticScorerUsingTime<G, T> {
#[inline]
fn read<R: Read>(
r: &mut R, args: (ProbabilisticScoringParameters, G)
fn increased_penalty_nearing_liquidity_upper_bound() {
let network_graph = network_graph();
let params = ProbabilisticScoringParameters {
- liquidity_penalty_multiplier_msat: 1_000, ..Default::default()
+ liquidity_penalty_multiplier_msat: 1_000,
+ ..ProbabilisticScoringParameters::zero_penalty()
};
let scorer = ProbabilisticScorer::new(params, &network_graph);
let source = source_node_id();
let last_updated = SinceEpoch::now();
let network_graph = network_graph();
let params = ProbabilisticScoringParameters {
- liquidity_penalty_multiplier_msat: 1_000, ..Default::default()
+ liquidity_penalty_multiplier_msat: 1_000,
+ ..ProbabilisticScoringParameters::zero_penalty()
};
let scorer = ProbabilisticScorer::new(params, &network_graph)
.with_channel(42,
assert_eq!(scorer.channel_penalty_msat(42, 39, 100, &source, &target), 0);
assert_ne!(scorer.channel_penalty_msat(42, 50, 100, &source, &target), 0);
- assert_ne!(scorer.channel_penalty_msat(42, 50, 100, &source, &target), 2_000);
- assert_eq!(scorer.channel_penalty_msat(42, 61, 100, &source, &target), 2_000);
+ assert_ne!(scorer.channel_penalty_msat(42, 50, 100, &source, &target), u64::max_value());
+ assert_eq!(scorer.channel_penalty_msat(42, 61, 100, &source, &target), u64::max_value());
}
#[test]
fn does_not_further_penalize_own_channel() {
let network_graph = network_graph();
let params = ProbabilisticScoringParameters {
- liquidity_penalty_multiplier_msat: 1_000, ..Default::default()
+ liquidity_penalty_multiplier_msat: 1_000,
+ ..ProbabilisticScoringParameters::zero_penalty()
};
let mut scorer = ProbabilisticScorer::new(params, &network_graph);
let sender = sender_node_id();
fn sets_liquidity_lower_bound_on_downstream_failure() {
let network_graph = network_graph();
let params = ProbabilisticScoringParameters {
- liquidity_penalty_multiplier_msat: 1_000, ..Default::default()
+ liquidity_penalty_multiplier_msat: 1_000,
+ ..ProbabilisticScoringParameters::zero_penalty()
};
let mut scorer = ProbabilisticScorer::new(params, &network_graph);
let source = source_node_id();
fn sets_liquidity_upper_bound_on_failure() {
let network_graph = network_graph();
let params = ProbabilisticScoringParameters {
- liquidity_penalty_multiplier_msat: 1_000, ..Default::default()
+ liquidity_penalty_multiplier_msat: 1_000,
+ ..ProbabilisticScoringParameters::zero_penalty()
};
let mut scorer = ProbabilisticScorer::new(params, &network_graph);
let source = source_node_id();
scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 42);
assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 300);
- assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 2_000);
- assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 2_000);
+ assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), u64::max_value());
+ assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), u64::max_value());
}
#[test]
fn reduces_liquidity_upper_bound_along_path_on_success() {
let network_graph = network_graph();
let params = ProbabilisticScoringParameters {
- liquidity_penalty_multiplier_msat: 1_000, ..Default::default()
+ liquidity_penalty_multiplier_msat: 1_000,
+ ..ProbabilisticScoringParameters::zero_penalty()
};
let mut scorer = ProbabilisticScorer::new(params, &network_graph);
let sender = sender_node_id();
let params = ProbabilisticScoringParameters {
liquidity_penalty_multiplier_msat: 1_000,
liquidity_offset_half_life: Duration::from_secs(10),
+ ..ProbabilisticScoringParameters::zero_penalty()
};
let mut scorer = ProbabilisticScorer::new(params, &network_graph);
let source = source_node_id();
assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 0);
assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 97);
assert_eq!(scorer.channel_penalty_msat(42, 768, 1_024, &source, &target), 1_409);
- assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), 2_000);
+ assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), u64::max_value());
SinceEpoch::advance(Duration::from_secs(9));
assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 0);
assert_eq!(scorer.channel_penalty_msat(42, 256, 1_024, &source, &target), 97);
assert_eq!(scorer.channel_penalty_msat(42, 768, 1_024, &source, &target), 1_409);
- assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), 2_000);
+ assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), u64::max_value());
SinceEpoch::advance(Duration::from_secs(1));
assert_eq!(scorer.channel_penalty_msat(42, 64, 1_024, &source, &target), 0);
assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 34);
assert_eq!(scorer.channel_penalty_msat(42, 896, 1_024, &source, &target), 1_773);
- assert_eq!(scorer.channel_penalty_msat(42, 960, 1_024, &source, &target), 2_000);
+ assert_eq!(scorer.channel_penalty_msat(42, 960, 1_024, &source, &target), u64::max_value());
// Fully decay liquidity lower bound.
SinceEpoch::advance(Duration::from_secs(10 * 7));
let params = ProbabilisticScoringParameters {
liquidity_penalty_multiplier_msat: 1_000,
liquidity_offset_half_life: Duration::from_secs(10),
+ ..ProbabilisticScoringParameters::zero_penalty()
};
let mut scorer = ProbabilisticScorer::new(params, &network_graph);
let source = source_node_id();
let params = ProbabilisticScoringParameters {
liquidity_penalty_multiplier_msat: 1_000,
liquidity_offset_half_life: Duration::from_secs(10),
+ ..ProbabilisticScoringParameters::zero_penalty()
};
let mut scorer = ProbabilisticScorer::new(params, &network_graph);
let source = source_node_id();
let params = ProbabilisticScoringParameters {
liquidity_penalty_multiplier_msat: 1_000,
liquidity_offset_half_life: Duration::from_secs(10),
+ ..ProbabilisticScoringParameters::zero_penalty()
};
let mut scorer = ProbabilisticScorer::new(params, &network_graph);
let source = source_node_id();
let target = target_node_id();
scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
- assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 2_000);
+ assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), u64::max_value());
SinceEpoch::advance(Duration::from_secs(10));
assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 472);
let params = ProbabilisticScoringParameters {
liquidity_penalty_multiplier_msat: 1_000,
liquidity_offset_half_life: Duration::from_secs(10),
+ ..ProbabilisticScoringParameters::zero_penalty()
};
let mut scorer = ProbabilisticScorer::new(params, &network_graph);
let source = source_node_id();
let target = target_node_id();
scorer.payment_path_failed(&payment_path_for_amount(500).iter().collect::<Vec<_>>(), 42);
- assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 2_000);
+ assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), u64::max_value());
let mut serialized_scorer = Vec::new();
scorer.write(&mut serialized_scorer).unwrap();
SinceEpoch::advance(Duration::from_secs(10));
assert_eq!(deserialized_scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 371);
}
+
+ #[test]
+ fn scores_realistic_payments() {
+ // Shows the scores of "realistic" sends of 100k sats over channels of 1-10m sats (with a
+ // 50k sat reserve).
+ let network_graph = network_graph();
+ let params = ProbabilisticScoringParameters::default();
+ let scorer = ProbabilisticScorer::new(params, &network_graph);
+ let source = source_node_id();
+ let target = target_node_id();
+
+ assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 950_000_000, &source, &target), 3645);
+ assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 1_950_000_000, &source, &target), 2512);
+ assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 2_950_000_000, &source, &target), 500);
+ assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 3_950_000_000, &source, &target), 1442);
+ assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 4_950_000_000, &source, &target), 500);
+ assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 5_950_000_000, &source, &target), 1820);
+ assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 6_950_000_000, &source, &target), 500);
+ assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 7_450_000_000, &source, &target), 500);
+ assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 7_950_000_000, &source, &target), 500);
+ assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 8_950_000_000, &source, &target), 500);
+ assert_eq!(scorer.channel_penalty_msat(42, 100_000_000, 9_950_000_000, &source, &target), 500);
+ }
+
+ #[test]
+ fn adds_base_penalty_to_liquidity_penalty() {
+ let network_graph = network_graph();
+ let source = source_node_id();
+ let target = target_node_id();
+
+ let params = ProbabilisticScoringParameters {
+ liquidity_penalty_multiplier_msat: 1_000,
+ ..ProbabilisticScoringParameters::zero_penalty()
+ };
+ let scorer = ProbabilisticScorer::new(params, &network_graph);
+ assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 58);
+
+ let params = ProbabilisticScoringParameters {
+ base_penalty_msat: 500, liquidity_penalty_multiplier_msat: 1_000, ..Default::default()
+ };
+ let scorer = ProbabilisticScorer::new(params, &network_graph);
+ assert_eq!(scorer.channel_penalty_msat(42, 128, 1_024, &source, &target), 558);
+ }
+
+ #[test]
+ fn adds_amount_penalty_to_liquidity_penalty() {
+ let network_graph = network_graph();
+ let source = source_node_id();
+ let target = target_node_id();
+
+ let params = ProbabilisticScoringParameters {
+ liquidity_penalty_multiplier_msat: 1_000,
+ amount_penalty_multiplier_msat: 0,
+ ..ProbabilisticScoringParameters::zero_penalty()
+ };
+ let scorer = ProbabilisticScorer::new(params, &network_graph);
+ assert_eq!(scorer.channel_penalty_msat(42, 512_000, 1_024_000, &source, &target), 300);
+
+ let params = ProbabilisticScoringParameters {
+ liquidity_penalty_multiplier_msat: 1_000,
+ amount_penalty_multiplier_msat: 256,
+ ..ProbabilisticScoringParameters::zero_penalty()
+ };
+ let scorer = ProbabilisticScorer::new(params, &network_graph);
+ assert_eq!(scorer.channel_penalty_msat(42, 512_000, 1_024_000, &source, &target), 337);
+ }
+
+ #[test]
+ fn calculates_log10_without_overflowing_u64_max_value() {
+ let network_graph = network_graph();
+ let source = source_node_id();
+ let target = target_node_id();
+
+ let params = ProbabilisticScoringParameters {
+ liquidity_penalty_multiplier_msat: 40_000,
+ ..ProbabilisticScoringParameters::zero_penalty()
+ };
+ let scorer = ProbabilisticScorer::new(params, &network_graph);
+ assert_eq!(
+ scorer.channel_penalty_msat(42, u64::max_value(), u64::max_value(), &source, &target),
+ 80_000,
+ );
+ }
}