//! # impl Logger for FakeLogger {
//! # fn log(&self, record: &Record) { unimplemented!() }
//! # }
-//! # fn find_scored_route(payer: PublicKey, route_params: RouteParameters, network_graph: NetworkGraph) {
+//! # fn find_scored_route(payer: PublicKey, route_params: RouteParameters, network_graph: NetworkGraph<&FakeLogger>) {
//! # let logger = FakeLogger {};
//! #
//! // Use the default channel penalties.
//! let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
//! # let random_seed_bytes = [42u8; 32];
//!
-//! let route = find_route(&payer, &route_params, &network_graph, None, &logger, &scorer, &random_seed_bytes);
+//! let route = find_route(&payer, &route_params, &network_graph.read_only(), None, &logger, &scorer, &random_seed_bytes);
//! # }
//! ```
//!
use prelude::*;
use core::fmt;
-use core::cell::{RefCell, RefMut};
+#[cfg(not(c_bindings))]
+use core::cell::RefCell;
+use core::cell::RefMut;
use core::ops::{Deref, DerefMut};
use core::time::Duration;
use io::{self, Read};
///
/// We need this trait to be able to pass in a scorer to `lightning-background-processor` that will enable us to
/// use the Persister to persist it.
+#[cfg(not(c_bindings))] // This doesn't make sense in bindings as all `Score`s are `Writeable`.
pub trait WriteableScore<'a>: LockableScore<'a> + Writeable {}
+#[cfg(not(c_bindings))] // This doesn't make sense in bindings as all `Score`s are `Writeable`.
impl<'a, T> WriteableScore<'a> for T where T: LockableScore<'a> + Writeable {}
-/// (C-not exported)
+#[cfg(not(c_bindings))]
impl<'a, T: 'a + Score> LockableScore<'a> for Mutex<T> {
type Locked = MutexGuard<'a, T>;
}
}
+#[cfg(not(c_bindings))]
impl<'a, T: 'a + Score> LockableScore<'a> for RefCell<T> {
type Locked = RefMut<'a, T>;
}
#[cfg(c_bindings)]
/// (C-not exported)
-impl<'a, T: Score + 'a> LockableScore<'a> for MultiThreadedLockableScore<T> {
- type Locked = MutexGuard<'a, T>;
+impl<'a, S: Score + 'a> LockableScore<'a> for MultiThreadedLockableScore<S> {
+ type Locked = MutexGuard<'a, S>;
- fn lock(&'a self) -> MutexGuard<'a, T> {
+ fn lock(&'a self) -> MutexGuard<'a, S> {
Mutex::lock(&self.score).unwrap()
}
}
+#[cfg(c_bindings)]
+impl<S: Score> Writeable for MultiThreadedLockableScore<S> {
+ fn write<W: Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
+ S::write(&*self.lock(), writer)
+ }
+}
+
#[cfg(c_bindings)]
impl<T: Score> MultiThreadedLockableScore<T> {
/// Creates a new [`MultiThreadedLockableScore`] given an underlying [`Score`].
}
#[cfg(not(feature = "no-std"))]
-type ConfiguredTime = std::time::Instant;
-#[cfg(feature = "no-std")]
-use util::time::Eternity;
+/// [`Score`] implementation using channel success probability distributions.
+///
+/// Based on *Optimally Reliable & Cheap Payment Flows on the Lightning Network* by Rene Pickhardt
+/// and Stefan Richter [[1]]. Given the uncertainty of channel liquidity balances, probability
+/// distributions are defined based on knowledge learned from successful and unsuccessful attempts.
+/// Then the negative `log10` of the success probability is used to determine the cost of routing a
+/// specific HTLC amount through a channel.
+///
+/// Knowledge about channel liquidity balances takes the form of upper and lower bounds on the
+/// possible liquidity. Certainty of the bounds is decreased over time using a decay function. See
+/// [`ProbabilisticScoringParameters`] for details.
+///
+/// Since the scorer aims to learn the current channel liquidity balances, it works best for nodes
+/// with high payment volume or that actively probe the [`NetworkGraph`]. Nodes with low payment
+/// volume are more likely to experience failed payment paths, which would need to be retried.
+///
+/// # Note
+///
+/// Mixing the `no-std` feature between serialization and deserialization results in undefined
+/// behavior.
+///
+/// [1]: https://arxiv.org/abs/2107.05322
+pub type ProbabilisticScorer<G, L> = ProbabilisticScorerUsingTime::<G, L, std::time::Instant>;
#[cfg(feature = "no-std")]
-type ConfiguredTime = Eternity;
-
/// [`Score`] implementation using channel success probability distributions.
///
/// Based on *Optimally Reliable & Cheap Payment Flows on the Lightning Network* by Rene Pickhardt
/// behavior.
///
/// [1]: https://arxiv.org/abs/2107.05322
-pub type ProbabilisticScorer<G, L> = ProbabilisticScorerUsingTime::<G, L, ConfiguredTime>;
+pub type ProbabilisticScorer<G, L> = ProbabilisticScorerUsingTime::<G, L, util::time::Eternity>;
/// Probabilistic [`Score`] implementation.
///
/// (C-not exported) generally all users should use the [`ProbabilisticScorer`] type alias.
-pub struct ProbabilisticScorerUsingTime<G: Deref<Target = NetworkGraph>, L: Deref, T: Time> where L::Target: Logger {
+pub struct ProbabilisticScorerUsingTime<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time>
+where L::Target: Logger {
params: ProbabilisticScoringParameters,
network_graph: G,
logger: L,
half_life: Duration,
}
-impl<G: Deref<Target = NetworkGraph>, L: Deref, T: Time> ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
+impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
/// Creates a new scorer using the given scoring parameters for sending payments from a node
/// through a network graph.
pub fn new(params: ProbabilisticScoringParameters, network_graph: G, logger: L) -> Self {
}
}
-impl<G: Deref<Target = NetworkGraph>, L: Deref, T: Time> Score for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
+impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Score for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
fn channel_penalty_msat(
&self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage
) -> u64 {
}
}
-impl<G: Deref<Target = NetworkGraph>, L: Deref, T: Time> Writeable for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
+impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time> Writeable for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
#[inline]
fn write<W: Writer>(&self, w: &mut W) -> Result<(), io::Error> {
write_tlv_fields!(w, {
}
}
-impl<G: Deref<Target = NetworkGraph>, L: Deref, T: Time>
+impl<G: Deref<Target = NetworkGraph<L>>, L: Deref, T: Time>
ReadableArgs<(ProbabilisticScoringParameters, G, L)> for ProbabilisticScorerUsingTime<G, L, T> where L::Target: Logger {
#[inline]
fn read<R: Read>(
// `ProbabilisticScorer` tests
/// A probabilistic scorer for testing with time that can be manually advanced.
- type ProbabilisticScorer<'a> = ProbabilisticScorerUsingTime::<&'a NetworkGraph, &'a TestLogger, SinceEpoch>;
+ type ProbabilisticScorer<'a> = ProbabilisticScorerUsingTime::<&'a NetworkGraph<&'a TestLogger>, &'a TestLogger, SinceEpoch>;
fn sender_privkey() -> SecretKey {
SecretKey::from_slice(&[41; 32]).unwrap()
NodeId::from_pubkey(&recipient_pubkey())
}
- fn network_graph() -> NetworkGraph {
+ fn network_graph(logger: &TestLogger) -> NetworkGraph<&TestLogger> {
let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
- let mut network_graph = NetworkGraph::new(genesis_hash);
+ let mut network_graph = NetworkGraph::new(genesis_hash, logger);
add_channel(&mut network_graph, 42, source_privkey(), target_privkey());
add_channel(&mut network_graph, 43, target_privkey(), recipient_privkey());
}
fn add_channel(
- network_graph: &mut NetworkGraph, short_channel_id: u64, node_1_key: SecretKey,
+ network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_1_key: SecretKey,
node_2_key: SecretKey
) {
let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
}
fn update_channel(
- network_graph: &mut NetworkGraph, short_channel_id: u64, node_key: SecretKey, flags: u8
+ network_graph: &mut NetworkGraph<&TestLogger>, short_channel_id: u64, node_key: SecretKey,
+ flags: u8
) {
let genesis_hash = genesis_block(Network::Testnet).header.block_hash();
let secp_ctx = Secp256k1::new();
fn liquidity_bounds_directed_from_lowest_node_id() {
let logger = TestLogger::new();
let last_updated = SinceEpoch::now();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let params = ProbabilisticScoringParameters::default();
let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
.with_channel(42,
fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() {
let logger = TestLogger::new();
let last_updated = SinceEpoch::now();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let params = ProbabilisticScoringParameters::default();
let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
.with_channel(42,
fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() {
let logger = TestLogger::new();
let last_updated = SinceEpoch::now();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let params = ProbabilisticScoringParameters::default();
let mut scorer = ProbabilisticScorer::new(params, &network_graph, &logger)
.with_channel(42,
#[test]
fn increased_penalty_nearing_liquidity_upper_bound() {
let logger = TestLogger::new();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let params = ProbabilisticScoringParameters {
liquidity_penalty_multiplier_msat: 1_000,
..ProbabilisticScoringParameters::zero_penalty()
fn constant_penalty_outside_liquidity_bounds() {
let logger = TestLogger::new();
let last_updated = SinceEpoch::now();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let params = ProbabilisticScoringParameters {
liquidity_penalty_multiplier_msat: 1_000,
..ProbabilisticScoringParameters::zero_penalty()
#[test]
fn does_not_further_penalize_own_channel() {
let logger = TestLogger::new();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let params = ProbabilisticScoringParameters {
liquidity_penalty_multiplier_msat: 1_000,
..ProbabilisticScoringParameters::zero_penalty()
#[test]
fn sets_liquidity_lower_bound_on_downstream_failure() {
let logger = TestLogger::new();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let params = ProbabilisticScoringParameters {
liquidity_penalty_multiplier_msat: 1_000,
..ProbabilisticScoringParameters::zero_penalty()
#[test]
fn sets_liquidity_upper_bound_on_failure() {
let logger = TestLogger::new();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let params = ProbabilisticScoringParameters {
liquidity_penalty_multiplier_msat: 1_000,
..ProbabilisticScoringParameters::zero_penalty()
#[test]
fn reduces_liquidity_upper_bound_along_path_on_success() {
let logger = TestLogger::new();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let params = ProbabilisticScoringParameters {
liquidity_penalty_multiplier_msat: 1_000,
..ProbabilisticScoringParameters::zero_penalty()
#[test]
fn decays_liquidity_bounds_over_time() {
let logger = TestLogger::new();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let params = ProbabilisticScoringParameters {
liquidity_penalty_multiplier_msat: 1_000,
liquidity_offset_half_life: Duration::from_secs(10),
#[test]
fn decays_liquidity_bounds_without_shift_overflow() {
let logger = TestLogger::new();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let params = ProbabilisticScoringParameters {
liquidity_penalty_multiplier_msat: 1_000,
liquidity_offset_half_life: Duration::from_secs(10),
#[test]
fn restricts_liquidity_bounds_after_decay() {
let logger = TestLogger::new();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let params = ProbabilisticScoringParameters {
liquidity_penalty_multiplier_msat: 1_000,
liquidity_offset_half_life: Duration::from_secs(10),
#[test]
fn restores_persisted_liquidity_bounds() {
let logger = TestLogger::new();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let params = ProbabilisticScoringParameters {
liquidity_penalty_multiplier_msat: 1_000,
liquidity_offset_half_life: Duration::from_secs(10),
#[test]
fn decays_persisted_liquidity_bounds() {
let logger = TestLogger::new();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let params = ProbabilisticScoringParameters {
liquidity_penalty_multiplier_msat: 1_000,
liquidity_offset_half_life: Duration::from_secs(10),
// Shows the scores of "realistic" sends of 100k sats over channels of 1-10m sats (with a
// 50k sat reserve).
let logger = TestLogger::new();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let params = ProbabilisticScoringParameters::default();
let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
let source = source_node_id();
#[test]
fn adds_base_penalty_to_liquidity_penalty() {
let logger = TestLogger::new();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let source = source_node_id();
let target = target_node_id();
let usage = ChannelUsage {
#[test]
fn adds_amount_penalty_to_liquidity_penalty() {
let logger = TestLogger::new();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let source = source_node_id();
let target = target_node_id();
let usage = ChannelUsage {
#[test]
fn calculates_log10_without_overflowing_u64_max_value() {
let logger = TestLogger::new();
- let network_graph = network_graph();
+ let network_graph = network_graph(&logger);
let source = source_node_id();
let target = target_node_id();
let usage = ChannelUsage {
#[test]
fn accounts_for_inflight_htlc_usage() {
- let network_graph = network_graph();
let logger = TestLogger::new();
+ let network_graph = network_graph(&logger);
let params = ProbabilisticScoringParameters::default();
let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
let source = source_node_id();
#[test]
fn removes_uncertainity_when_exact_liquidity_known() {
- let network_graph = network_graph();
let logger = TestLogger::new();
+ let network_graph = network_graph(&logger);
let params = ProbabilisticScoringParameters::default();
let scorer = ProbabilisticScorer::new(params, &network_graph, &logger);
let source = source_node_id();
projects / rust-lightning / blobdiff