//! #
//! // Use the default channel penalties.
//! let params = ProbabilisticScoringParameters::default();
-//! let scorer = ProbabilisticScorer::new(params, &payer, &network_graph);
+//! let scorer = ProbabilisticScorer::new(params, &network_graph);
//!
//! // Or use custom channel penalties.
//! let params = ProbabilisticScoringParameters {
//! liquidity_penalty_multiplier_msat: 2 * 1000,
//! ..ProbabilisticScoringParameters::default()
//! };
-//! let scorer = ProbabilisticScorer::new(params, &payer, &network_graph);
+//! let scorer = ProbabilisticScorer::new(params, &network_graph);
//!
//! let route = find_route(&payer, &route_params, &network_graph, None, &logger, &scorer);
//! # }
//!
//! [`find_route`]: crate::routing::router::find_route
-use bitcoin::secp256k1::key::PublicKey;
-
use ln::msgs::DecodeError;
-use routing::network_graph::{EffectiveCapacity, NetworkGraph, NodeId};
+use routing::network_graph::{NetworkGraph, NodeId};
use routing::router::RouteHop;
use util::ser::{Readable, ReadableArgs, Writeable, Writer};
/// [1]: https://arxiv.org/abs/2107.05322
pub struct ProbabilisticScorer<G: Deref<Target = NetworkGraph>> {
params: ProbabilisticScoringParameters,
- node_id: NodeId,
network_graph: G,
// TODO: Remove entries of closed channels.
channel_liquidities: HashMap<u64, ChannelLiquidity>,
/// first node in the ordering of the channel's counterparties. Thus, swapping the two liquidity
/// offset fields gives the opposite direction.
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,
}
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
- ) -> Self {
+ pub fn new(params: ProbabilisticScoringParameters, network_graph: G) -> Self {
Self {
params,
- node_id: NodeId::from_pubkey(node_pubkey),
network_graph,
channel_liquidities: HashMap::new(),
}
}
impl<G: Deref<Target = NetworkGraph>> Score for ProbabilisticScorer<G> {
- #[allow(clippy::float_cmp)]
fn channel_penalty_msat(
&self, short_channel_id: u64, amount_msat: u64, capacity_msat: u64, source: &NodeId,
target: &NodeId
) -> u64 {
- if *source == self.node_id || *target == self.node_id {
- 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);
- 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
- }
+ // NOTE: If success_probability is ever changed to return 0.0, log10 is undefined so return
+ // u64::max_value instead.
+ debug_assert!(success_probability > core::f64::EPSILON);
+ (-(success_probability.log10()) * liquidity_penalty_multiplier_msat as f64) as u64
}
fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) {
let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
let network_graph = self.network_graph.read_only();
- let hop_sources = core::iter::once(self.node_id)
- .chain(path.iter().map(|hop| NodeId::from_pubkey(&hop.pubkey)));
- for (source, hop) in hop_sources.zip(path.iter()) {
+ for hop in path {
let target = NodeId::from_pubkey(&hop.pubkey);
- if source == self.node_id || target == self.node_id {
- continue;
- }
-
- let capacity_msat = network_graph.channels()
+ let channel_directed_from_source = network_graph.channels()
.get(&hop.short_channel_id)
- .and_then(|channel| channel.as_directed_to(&target).map(|(d, _)| d.effective_capacity()))
- .unwrap_or(EffectiveCapacity::Unknown)
- .as_msat();
+ .and_then(|channel| channel.as_directed_to(&target));
+
+ // Only score announced channels.
+ if let Some((channel, source)) = channel_directed_from_source {
+ let capacity_msat = channel.effective_capacity().as_msat();
+ if hop.short_channel_id == short_channel_id {
+ self.channel_liquidities
+ .entry(hop.short_channel_id)
+ .or_insert_with(ChannelLiquidity::new)
+ .as_directed_mut(source, &target, capacity_msat)
+ .failed_at_channel(amount_msat);
+ break;
+ }
- if hop.short_channel_id == short_channel_id {
self.channel_liquidities
.entry(hop.short_channel_id)
- .or_insert_with(|| ChannelLiquidity::new())
- .as_directed_mut(&source, &target, capacity_msat)
- .failed_at_channel(amount_msat);
- break;
+ .or_insert_with(ChannelLiquidity::new)
+ .as_directed_mut(source, &target, capacity_msat)
+ .failed_downstream(amount_msat);
}
-
- self.channel_liquidities
- .entry(hop.short_channel_id)
- .or_insert_with(|| ChannelLiquidity::new())
- .as_directed_mut(&source, &target, capacity_msat)
- .failed_downstream(amount_msat);
}
}
fn payment_path_successful(&mut self, path: &[&RouteHop]) {
let amount_msat = path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0);
let network_graph = self.network_graph.read_only();
- let hop_sources = core::iter::once(self.node_id)
- .chain(path.iter().map(|hop| NodeId::from_pubkey(&hop.pubkey)));
- for (source, hop) in hop_sources.zip(path.iter()) {
+ for hop in path {
let target = NodeId::from_pubkey(&hop.pubkey);
- if source == self.node_id || target == self.node_id {
- continue;
- }
-
- let capacity_msat = network_graph.channels()
+ let channel_directed_from_source = network_graph.channels()
.get(&hop.short_channel_id)
- .and_then(|channel| channel.as_directed_to(&target).map(|(d, _)| d.effective_capacity()))
- .unwrap_or(EffectiveCapacity::Unknown)
- .as_msat();
+ .and_then(|channel| channel.as_directed_to(&target));
- self.channel_liquidities
- .entry(hop.short_channel_id)
- .or_insert_with(|| ChannelLiquidity::new())
- .as_directed_mut(&source, &target, capacity_msat)
- .successful(amount_msat);
+ // Only score announced channels.
+ if let Some((channel, source)) = channel_directed_from_source {
+ let capacity_msat = channel.effective_capacity().as_msat();
+ self.channel_liquidities
+ .entry(hop.short_channel_id)
+ .or_insert_with(ChannelLiquidity::new)
+ .as_directed_mut(source, &target, capacity_msat)
+ .successful(amount_msat);
+ }
}
}
}
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.channel_liquidities.write(w)?;
- write_tlv_fields!(w, {});
+ write_tlv_fields!(w, {
+ (0, self.channel_liquidities, required)
+ });
Ok(())
}
}
-impl<G: Deref<Target = NetworkGraph>> ReadableArgs<(&PublicKey, G)> for ProbabilisticScorer<G> {
+impl<G: Deref<Target = NetworkGraph>> ReadableArgs<(ProbabilisticScoringParameters, G)>
+for ProbabilisticScorer<G> {
#[inline]
- 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: NodeId::from_pubkey(node_pubkey),
- network_graph,
- channel_liquidities: Readable::read(r)?,
+ fn read<R: Read>(
+ r: &mut R, args: (ProbabilisticScoringParameters, G)
+ ) -> Result<Self, DecodeError> {
+ let (params, network_graph) = args;
+ let mut channel_liquidities = HashMap::new();
+ read_tlv_fields!(r, {
+ (0, channel_liquidities, required)
});
- read_tlv_fields!(r, {});
- res
+ Ok(Self {
+ params,
+ network_graph,
+ channel_liquidities,
+ })
}
}
fn network_graph() -> NetworkGraph {
let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
let mut network_graph = NetworkGraph::new(genesis_hash);
- add_channel(&mut network_graph, 41, sender_privkey(), source_privkey());
add_channel(&mut network_graph, 42, source_privkey(), target_privkey());
add_channel(&mut network_graph, 43, target_privkey(), recipient_privkey());
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, &network_graph)
.with_channel(42,
ChannelLiquidity {
min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100
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)
+ let mut scorer = ProbabilisticScorer::new(params, &network_graph)
.with_channel(42,
ChannelLiquidity {
min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400
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)
+ let mut scorer = ProbabilisticScorer::new(params, &network_graph)
.with_channel(42,
ChannelLiquidity {
min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400
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, &network_graph);
let source = source_node_id();
let target = target_node_id();
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, &network_graph)
.with_channel(42,
ChannelLiquidity { min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40 });
let source = source_node_id();
}
#[test]
- fn does_not_penalize_own_channel() {
+ fn does_not_further_penalize_own_channel() {
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, &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);
+ assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 300);
scorer.payment_path_failed(&failed_path.iter().collect::<Vec<_>>(), 41);
- assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 0);
+ assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 300);
scorer.payment_path_successful(&successful_path.iter().collect::<Vec<_>>());
- assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 0);
+ assert_eq!(scorer.channel_penalty_msat(41, 500, 1_000, &sender, &source), 300);
}
#[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 mut scorer = ProbabilisticScorer::new(params, &network_graph);
let source = source_node_id();
let target = target_node_id();
let path = payment_path_for_amount(500);
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 mut scorer = ProbabilisticScorer::new(params, &network_graph);
let source = source_node_id();
let target = target_node_id();
let path = payment_path_for_amount(500);
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 mut scorer = ProbabilisticScorer::new(params, &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_for_amount(500);
- assert_eq!(scorer.channel_penalty_msat(41, 250, 1_000, &sender, &source), 0);
+ assert_eq!(scorer.channel_penalty_msat(41, 250, 1_000, &sender, &source), 124);
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, 250, 1_000, &sender, &source), 0);
+ assert_eq!(scorer.channel_penalty_msat(41, 250, 1_000, &sender, &source), 124);
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);
}