//! Utilities for scoring payment channels.
//!
-//! [`Scorer`] may be given to [`find_route`] to score payment channels during path finding when a
-//! custom [`Score`] implementation is not needed.
+//! [`ProbabilisticScorer`] may be given to [`find_route`] to score payment channels during path
+//! finding when a custom [`Score`] implementation is not needed.
//!
//! # Example
//!
//! #
//! # use lightning::routing::network_graph::NetworkGraph;
//! # use lightning::routing::router::{RouteParameters, find_route};
-//! # use lightning::routing::scoring::{Scorer, ScoringParameters};
+//! # use lightning::routing::scoring::{ProbabilisticScorer, ProbabilisticScoringParameters, Scorer, ScoringParameters};
//! # use lightning::util::logger::{Logger, Record};
//! # use secp256k1::key::PublicKey;
//! #
//! # impl Logger for FakeLogger {
//! # fn log(&self, record: &Record) { unimplemented!() }
//! # }
-//! # fn find_scored_route(payer: PublicKey, params: RouteParameters, network_graph: NetworkGraph) {
+//! # fn find_scored_route(payer: PublicKey, route_params: RouteParameters, network_graph: NetworkGraph) {
//! # let logger = FakeLogger {};
//! #
//! // Use the default channel penalties.
-//! let scorer = Scorer::default();
+//! let params = ProbabilisticScoringParameters::default();
+//! let scorer = ProbabilisticScorer::new(params, &payer, &network_graph);
//!
//! // Or use custom channel penalties.
-//! let scorer = Scorer::new(ScoringParameters {
-//! base_penalty_msat: 1000,
-//! failure_penalty_msat: 2 * 1024 * 1000,
-//! ..ScoringParameters::default()
-//! });
+//! let params = ProbabilisticScoringParameters {
+//! liquidity_penalty_multiplier_msat: 2 * 1000,
+//! ..ProbabilisticScoringParameters::default()
+//! };
+//! let scorer = ProbabilisticScorer::new(params, &payer, &network_graph);
//!
-//! let route = find_route(&payer, ¶ms, &network_graph, None, &logger, &scorer);
+//! let route = find_route(&payer, &route_params, &network_graph, None, &logger, &scorer);
//! # }
//! ```
//!
///
/// [1]: https://arxiv.org/abs/2107.05322
pub struct ProbabilisticScorer<G: Deref<Target = NetworkGraph>> {
- _params: ProbabilisticScoringParameters,
+ params: ProbabilisticScoringParameters,
node_id: NodeId,
network_graph: G,
// TODO: Remove entries of closed channels.
}
/// Parameters for configuring [`ProbabilisticScorer`].
-pub struct ProbabilisticScoringParameters;
+pub struct ProbabilisticScoringParameters {
+ /// A penalty applied after multiplying by the negative log of channel's success probability for
+ /// a payment.
+ ///
+ /// The success probability is determined by the effective channel capacity, the payment amount,
+ /// and knowledge learned from prior successful and unsuccessful payments.
+ ///
+ /// Default value: 1,000 msat
+ pub liquidity_penalty_multiplier_msat: u64,
+}
impl_writeable_tlv_based!(ProbabilisticScoringParameters, {
+ (0, liquidity_penalty_multiplier_msat, required),
});
/// Accounting for channel liquidity balance uncertainty.
capacity_msat: u64,
}
-/// The likelihood of an event occurring.
-enum Probability {
- Zero,
- One,
- Ratio { numerator: u64, denominator: u64 },
-}
-
impl<G: Deref<Target = NetworkGraph>> ProbabilisticScorer<G> {
/// Creates a new scorer using the given scoring parameters for sending payments from a node
/// through a network graph.
pub fn new(
- _params: ProbabilisticScoringParameters, node_pubkey: PublicKey, network_graph: G
+ params: ProbabilisticScoringParameters, node_pubkey: &PublicKey, network_graph: G
) -> Self {
Self {
- _params,
- node_id: NodeId::from_pubkey(&node_pubkey),
+ params,
+ node_id: NodeId::from_pubkey(node_pubkey),
network_graph,
channel_liquidities: HashMap::new(),
}
impl Default for ProbabilisticScoringParameters {
fn default() -> Self {
- Self
+ Self {
+ liquidity_penalty_multiplier_msat: 1000,
+ }
}
}
impl<L: Deref<Target = u64>> DirectedChannelLiquidity<L> {
/// Returns the success probability of routing the given HTLC `amount_msat` through the channel
/// in this direction.
- fn success_probability(&self, amount_msat: u64) -> Probability {
+ fn success_probability(&self, amount_msat: u64) -> f64 {
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 {
- Probability::Zero
- } else if amount_msat < min_liquidity_msat {
- Probability::One
+ 0.0
+ } else if amount_msat <= min_liquidity_msat {
+ 1.0
} else {
let numerator = max_liquidity_msat + 1 - amount_msat;
let denominator = max_liquidity_msat + 1 - min_liquidity_msat;
- if numerator == denominator {
- Probability::One
- } else {
- Probability::Ratio { numerator, denominator }
- }
+ numerator as f64 / denominator as f64
}
}
return 0;
}
+ let liquidity_penalty_multiplier_msat = self.params.liquidity_penalty_multiplier_msat;
let success_probability = self.channel_liquidities
.get(&short_channel_id)
.unwrap_or(&ChannelLiquidity::new())
.as_directed(source, target, capacity_msat)
.success_probability(amount_msat);
- match success_probability {
- Probability::Zero => u64::max_value(),
- Probability::One => 0,
- Probability::Ratio { numerator, denominator } => {
- let success_probability = numerator as f64 / denominator as f64;
- (-(success_probability.log10()) * amount_msat as f64) as u64
- },
+ if success_probability == 0.0 {
+ u64::max_value()
+ } else if success_probability == 1.0 {
+ 0
+ } else {
+ (-(success_probability.log10()) * liquidity_penalty_multiplier_msat as f64) as u64
}
}
impl<G: Deref<Target = NetworkGraph>> Writeable for ProbabilisticScorer<G> {
#[inline]
fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
- self._params.write(w)?;
- self.node_id.write(w)?;
+ self.params.write(w)?;
self.channel_liquidities.write(w)?;
write_tlv_fields!(w, {});
Ok(())
}
}
-impl<G: Deref<Target = NetworkGraph>> ReadableArgs<G> for ProbabilisticScorer<G> {
+impl<G: Deref<Target = NetworkGraph>> ReadableArgs<(&PublicKey, G)> for ProbabilisticScorer<G> {
#[inline]
- fn read<R: Read>(r: &mut R, args: G) -> Result<Self, DecodeError> {
+ fn read<R: Read>(r: &mut R, args: (&PublicKey, G)) -> Result<Self, DecodeError> {
+ let (node_pubkey, network_graph) = args;
let res = Ok(Self {
- _params: Readable::read(r)?,
- node_id: Readable::read(r)?,
- network_graph: args,
+ params: Readable::read(r)?,
+ node_id: NodeId::from_pubkey(node_pubkey),
+ network_graph,
channel_liquidities: Readable::read(r)?,
});
read_tlv_fields!(r, {});
network_graph.update_channel(&signed_update, &secp_ctx).unwrap();
}
- fn payment_path(amount_msat: u64) -> Vec<RouteHop> {
+ fn payment_path_for_amount(amount_msat: u64) -> Vec<RouteHop> {
vec![
RouteHop {
pubkey: source_pubkey(),
fn liquidity_bounds_directed_from_lowest_node_id() {
let network_graph = network_graph();
let params = ProbabilisticScoringParameters::default();
- let mut scorer = ProbabilisticScorer::new(params, sender_pubkey(), &network_graph)
+ let mut scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph)
.with_channel(42,
ChannelLiquidity {
min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100
assert_eq!(liquidity.as_directed(&recipient, &target, 1_000).max_liquidity_msat(), 1000);
}
+ #[test]
+ fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() {
+ let network_graph = network_graph();
+ let params = ProbabilisticScoringParameters::default();
+ let mut scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph)
+ .with_channel(42,
+ ChannelLiquidity {
+ min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400
+ });
+ let source = source_node_id();
+ let target = target_node_id();
+ assert!(source > target);
+
+ // Check initial bounds.
+ let liquidity = scorer.channel_liquidities.get(&42).unwrap()
+ .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);
+ 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)
+ .set_min_liquidity_msat(900);
+
+ let liquidity = scorer.channel_liquidities.get(&42).unwrap()
+ .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);
+ 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)
+ .set_min_liquidity_msat(400);
+
+ let liquidity = scorer.channel_liquidities.get(&42).unwrap()
+ .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);
+ assert_eq!(liquidity.min_liquidity_msat(), 400);
+ assert_eq!(liquidity.max_liquidity_msat(), 1_000);
+ }
+
+ #[test]
+ fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() {
+ let network_graph = network_graph();
+ let params = ProbabilisticScoringParameters::default();
+ let mut scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph)
+ .with_channel(42,
+ ChannelLiquidity {
+ min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400
+ });
+ let source = source_node_id();
+ let target = target_node_id();
+ assert!(source > target);
+
+ // Check initial bounds.
+ let liquidity = scorer.channel_liquidities.get(&42).unwrap()
+ .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);
+ 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)
+ .set_max_liquidity_msat(300);
+
+ let liquidity = scorer.channel_liquidities.get(&42).unwrap()
+ .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);
+ 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)
+ .set_max_liquidity_msat(600);
+
+ let liquidity = scorer.channel_liquidities.get(&42).unwrap()
+ .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);
+ assert_eq!(liquidity.min_liquidity_msat(), 0);
+ assert_eq!(liquidity.max_liquidity_msat(), 600);
+ }
+
#[test]
fn increased_penalty_nearing_liquidity_upper_bound() {
let network_graph = network_graph();
let params = ProbabilisticScoringParameters::default();
- let scorer = ProbabilisticScorer::new(params, sender_pubkey(), &network_graph);
+ let scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph);
let source = source_node_id();
let target = target_node_id();
assert_eq!(scorer.channel_penalty_msat(42, 100, 100_000, &source, &target), 0);
assert_eq!(scorer.channel_penalty_msat(42, 1_000, 100_000, &source, &target), 4);
- assert_eq!(scorer.channel_penalty_msat(42, 10_000, 100_000, &source, &target), 457);
- assert_eq!(scorer.channel_penalty_msat(42, 100_000, 100_000, &source, &target), 500_000);
+ assert_eq!(scorer.channel_penalty_msat(42, 10_000, 100_000, &source, &target), 45);
+ assert_eq!(scorer.channel_penalty_msat(42, 100_000, 100_000, &source, &target), 5_000);
- assert_eq!(scorer.channel_penalty_msat(42, 125, 1_000, &source, &target), 7);
- assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 31);
- assert_eq!(scorer.channel_penalty_msat(42, 375, 1_000, &source, &target), 76);
- assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 150);
- assert_eq!(scorer.channel_penalty_msat(42, 625, 1_000, &source, &target), 265);
- assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 450);
- assert_eq!(scorer.channel_penalty_msat(42, 875, 1_000, &source, &target), 787);
+ assert_eq!(scorer.channel_penalty_msat(42, 125, 1_000, &source, &target), 57);
+ assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 124);
+ assert_eq!(scorer.channel_penalty_msat(42, 375, 1_000, &source, &target), 203);
+ assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300);
+ assert_eq!(scorer.channel_penalty_msat(42, 625, 1_000, &source, &target), 425);
+ assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 600);
+ assert_eq!(scorer.channel_penalty_msat(42, 875, 1_000, &source, &target), 900);
}
#[test]
fn constant_penalty_outside_liquidity_bounds() {
let network_graph = network_graph();
let params = ProbabilisticScoringParameters::default();
- let scorer = ProbabilisticScorer::new(params, sender_pubkey(), &network_graph)
+ let scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph)
.with_channel(42,
ChannelLiquidity { min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40 });
let source = source_node_id();
}
#[test]
- fn reduces_liquidity_upper_bound_on_success() {
+ fn does_not_penalize_own_channel() {
let network_graph = network_graph();
let params = ProbabilisticScoringParameters::default();
- let mut scorer = ProbabilisticScorer::new(params, sender_pubkey(), &network_graph)
- .with_channel(42,
- ChannelLiquidity { min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 0 })
- .with_channel(43,
- ChannelLiquidity { min_liquidity_offset_msat: 0, max_liquidity_offset_msat: 400 });
+ let mut scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph);
+ let sender = sender_node_id();
+ let source = source_node_id();
+ let failed_path = payment_path_for_amount(500);
+ let successful_path = payment_path_for_amount(200);
+
+ assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 0);
+
+ scorer.payment_path_failed(&failed_path.iter().collect::<Vec<_>>(), 41);
+ assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 0);
+
+ scorer.payment_path_successful(&successful_path.iter().collect::<Vec<_>>());
+ assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 0);
+ }
+
+ #[test]
+ fn sets_liquidity_lower_bound_on_downstream_failure() {
+ let network_graph = network_graph();
+ let params = ProbabilisticScoringParameters::default();
+ let mut scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph);
+ let source = source_node_id();
+ let target = target_node_id();
+ let path = payment_path_for_amount(500);
+
+ assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 124);
+ assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300);
+ assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 600);
+
+ scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), 43);
+
+ assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 0);
+ assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 0);
+ assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 300);
+ }
+
+ #[test]
+ fn sets_liquidity_upper_bound_on_failure() {
+ let network_graph = network_graph();
+ let params = ProbabilisticScoringParameters::default();
+ let mut scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph);
+ let source = source_node_id();
+ let target = target_node_id();
+ let path = payment_path_for_amount(500);
+
+ assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 124);
+ assert_eq!(scorer.channel_penalty_msat(42, 500, 1_000, &source, &target), 300);
+ assert_eq!(scorer.channel_penalty_msat(42, 750, 1_000, &source, &target), 600);
+
+ 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), 2699);
+ 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::default();
+ let mut scorer = ProbabilisticScorer::new(params, &sender_pubkey(), &network_graph);
let sender = sender_node_id();
let source = source_node_id();
let target = target_node_id();
let recipient = recipient_node_id();
- let path = payment_path(200);
+ let path = payment_path_for_amount(500);
- assert_eq!(scorer.channel_penalty_msat(41, 200, 1_000, &sender, &source), 0);
- assert_eq!(scorer.channel_penalty_msat(42, 200, 1_000, &source, &target), 94);
- assert_eq!(scorer.channel_penalty_msat(43, 200, 1_000, &target, &recipient), 35);
+ assert_eq!(scorer.channel_penalty_msat(41, 250, 1_000, &sender, &source), 0);
+ assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 124);
+ assert_eq!(scorer.channel_penalty_msat(43, 250, 1_000, &target, &recipient), 124);
scorer.payment_path_successful(&path.iter().collect::<Vec<_>>());
- assert_eq!(scorer.channel_penalty_msat(41, 200, 1_000, &sender, &source), 0);
- assert_eq!(scorer.channel_penalty_msat(42, 200, 1_000, &source, &target), u64::max_value());
- assert_eq!(scorer.channel_penalty_msat(43, 200, 1_000, &target, &recipient), 59);
+ assert_eq!(scorer.channel_penalty_msat(41, 250, 1_000, &sender, &source), 0);
+ assert_eq!(scorer.channel_penalty_msat(42, 250, 1_000, &source, &target), 300);
+ assert_eq!(scorer.channel_penalty_msat(43, 250, 1_000, &target, &recipient), 300);
}
-
- // TODO: Add more test coverage
}
projects / rust-lightning / blobdiff