X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=0a09ca81e3ffc6c13feca2c34391cac981128d62;hb=5824e226cad67e32d5e8be71ebbb6f91a3fc2116;hp=cffd9ddb0a581ea2e26a53ee3f305a8c7f81bbf7;hpb=8d93dba37031208878a6046110dc3f6e56796b65;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index cffd9ddb..0a09ca81 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -13,45 +13,210 @@ //! interrogate it to get routes for your own payments. use bitcoin::secp256k1::PublicKey; +use bitcoin::hashes::Hash; +use bitcoin::hashes::sha256::Hash as Sha256; -use crate::ln::channelmanager::ChannelDetails; +use crate::ln::PaymentHash; +use crate::ln::channelmanager::{ChannelDetails, PaymentId}; use crate::ln::features::{ChannelFeatures, InvoiceFeatures, NodeFeatures}; use crate::ln::msgs::{DecodeError, ErrorAction, LightningError, MAX_VALUE_MSAT}; use crate::routing::gossip::{DirectedChannelInfo, EffectiveCapacity, ReadOnlyNetworkGraph, NetworkGraph, NodeId, RoutingFees}; -use crate::routing::scoring::{ChannelUsage, Score}; +use crate::routing::scoring::{ChannelUsage, LockableScore, Score}; use crate::util::ser::{Writeable, Readable, Writer}; use crate::util::logger::{Level, Logger}; use crate::util::chacha20::ChaCha20; use crate::io; use crate::prelude::*; +use crate::sync::Mutex; use alloc::collections::BinaryHeap; use core::cmp; use core::ops::Deref; +/// A [`Router`] implemented using [`find_route`]. +pub struct DefaultRouter>, L: Deref, S: Deref> where + L::Target: Logger, + S::Target: for <'a> LockableScore<'a>, +{ + network_graph: G, + logger: L, + random_seed_bytes: Mutex<[u8; 32]>, + scorer: S +} + +impl>, L: Deref, S: Deref> DefaultRouter where + L::Target: Logger, + S::Target: for <'a> LockableScore<'a>, +{ + /// Creates a new router. + pub fn new(network_graph: G, logger: L, random_seed_bytes: [u8; 32], scorer: S) -> Self { + let random_seed_bytes = Mutex::new(random_seed_bytes); + Self { network_graph, logger, random_seed_bytes, scorer } + } +} + +impl>, L: Deref, S: Deref> Router for DefaultRouter where + L::Target: Logger, + S::Target: for <'a> LockableScore<'a>, +{ + fn find_route( + &self, payer: &PublicKey, params: &RouteParameters, first_hops: Option<&[&ChannelDetails]>, + inflight_htlcs: &InFlightHtlcs + ) -> Result { + let random_seed_bytes = { + let mut locked_random_seed_bytes = self.random_seed_bytes.lock().unwrap(); + *locked_random_seed_bytes = Sha256::hash(&*locked_random_seed_bytes).into_inner(); + *locked_random_seed_bytes + }; + + find_route( + payer, params, &self.network_graph, first_hops, &*self.logger, + &ScorerAccountingForInFlightHtlcs::new(self.scorer.lock(), inflight_htlcs), + &random_seed_bytes + ) + } + + fn notify_payment_path_failed(&self, path: &[&RouteHop], short_channel_id: u64) { + self.scorer.lock().payment_path_failed(path, short_channel_id); + } + + fn notify_payment_path_successful(&self, path: &[&RouteHop]) { + self.scorer.lock().payment_path_successful(path); + } + + fn notify_payment_probe_successful(&self, path: &[&RouteHop]) { + self.scorer.lock().probe_successful(path); + } + + fn notify_payment_probe_failed(&self, path: &[&RouteHop], short_channel_id: u64) { + self.scorer.lock().probe_failed(path, short_channel_id); + } +} + /// A trait defining behavior for routing a payment. pub trait Router { /// Finds a [`Route`] between `payer` and `payee` for a payment with the given values. fn find_route( &self, payer: &PublicKey, route_params: &RouteParameters, - first_hops: Option<&[&ChannelDetails]>, inflight_htlcs: InFlightHtlcs + first_hops: Option<&[&ChannelDetails]>, inflight_htlcs: &InFlightHtlcs ) -> Result; + /// Finds a [`Route`] between `payer` and `payee` for a payment with the given values. Includes + /// `PaymentHash` and `PaymentId` to be able to correlate the request with a specific payment. + fn find_route_with_id( + &self, payer: &PublicKey, route_params: &RouteParameters, + first_hops: Option<&[&ChannelDetails]>, inflight_htlcs: &InFlightHtlcs, + _payment_hash: PaymentHash, _payment_id: PaymentId + ) -> Result { + self.find_route(payer, route_params, first_hops, inflight_htlcs) + } + /// Lets the router know that payment through a specific path has failed. + fn notify_payment_path_failed(&self, path: &[&RouteHop], short_channel_id: u64); + /// Lets the router know that payment through a specific path was successful. + fn notify_payment_path_successful(&self, path: &[&RouteHop]); + /// Lets the router know that a payment probe was successful. + fn notify_payment_probe_successful(&self, path: &[&RouteHop]); + /// Lets the router know that a payment probe failed. + fn notify_payment_probe_failed(&self, path: &[&RouteHop], short_channel_id: u64); +} + +/// [`Score`] implementation that factors in in-flight HTLC liquidity. +/// +/// Useful for custom [`Router`] implementations to wrap their [`Score`] on-the-fly when calling +/// [`find_route`]. +/// +/// [`Score`]: crate::routing::scoring::Score +pub struct ScorerAccountingForInFlightHtlcs<'a, S: Score> { + scorer: S, + // Maps a channel's short channel id and its direction to the liquidity used up. + inflight_htlcs: &'a InFlightHtlcs, +} + +impl<'a, S: Score> ScorerAccountingForInFlightHtlcs<'a, S> { + /// Initialize a new `ScorerAccountingForInFlightHtlcs`. + pub fn new(scorer: S, inflight_htlcs: &'a InFlightHtlcs) -> Self { + ScorerAccountingForInFlightHtlcs { + scorer, + inflight_htlcs + } + } +} + +#[cfg(c_bindings)] +impl<'a, S: Score> Writeable for ScorerAccountingForInFlightHtlcs<'a, S> { + fn write(&self, writer: &mut W) -> Result<(), io::Error> { self.scorer.write(writer) } +} + +impl<'a, S: Score> Score for ScorerAccountingForInFlightHtlcs<'a, S> { + fn channel_penalty_msat(&self, short_channel_id: u64, source: &NodeId, target: &NodeId, usage: ChannelUsage) -> u64 { + if let Some(used_liquidity) = self.inflight_htlcs.used_liquidity_msat( + source, target, short_channel_id + ) { + let usage = ChannelUsage { + inflight_htlc_msat: usage.inflight_htlc_msat + used_liquidity, + ..usage + }; + + self.scorer.channel_penalty_msat(short_channel_id, source, target, usage) + } else { + self.scorer.channel_penalty_msat(short_channel_id, source, target, usage) + } + } + + fn payment_path_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) { + self.scorer.payment_path_failed(path, short_channel_id) + } + + fn payment_path_successful(&mut self, path: &[&RouteHop]) { + self.scorer.payment_path_successful(path) + } + + fn probe_failed(&mut self, path: &[&RouteHop], short_channel_id: u64) { + self.scorer.probe_failed(path, short_channel_id) + } + + fn probe_successful(&mut self, path: &[&RouteHop]) { + self.scorer.probe_successful(path) + } } -/// A map with liquidity value (in msat) keyed by a short channel id and the direction the HTLC -/// is traveling in. The direction boolean is determined by checking if the HTLC source's public -/// key is less than its destination. See [`InFlightHtlcs::used_liquidity_msat`] for more -/// details. -#[cfg(not(any(test, feature = "_test_utils")))] -pub struct InFlightHtlcs(HashMap<(u64, bool), u64>); -#[cfg(any(test, feature = "_test_utils"))] -pub struct InFlightHtlcs(pub HashMap<(u64, bool), u64>); +/// A data structure for tracking in-flight HTLCs. May be used during pathfinding to account for +/// in-use channel liquidity. +#[derive(Clone)] +pub struct InFlightHtlcs( + // A map with liquidity value (in msat) keyed by a short channel id and the direction the HTLC + // is traveling in. The direction boolean is determined by checking if the HTLC source's public + // key is less than its destination. See `InFlightHtlcs::used_liquidity_msat` for more + // details. + HashMap<(u64, bool), u64> +); impl InFlightHtlcs { - /// Create a new `InFlightHtlcs` via a mapping from: - /// (short_channel_id, source_pubkey < target_pubkey) -> used_liquidity_msat - pub fn new(inflight_map: HashMap<(u64, bool), u64>) -> Self { - InFlightHtlcs(inflight_map) + /// Constructs an empty `InFlightHtlcs`. + pub fn new() -> Self { InFlightHtlcs(HashMap::new()) } + + /// Takes in a path with payer's node id and adds the path's details to `InFlightHtlcs`. + pub fn process_path(&mut self, path: &[RouteHop], payer_node_id: PublicKey) { + if path.is_empty() { return }; + // total_inflight_map needs to be direction-sensitive when keeping track of the HTLC value + // that is held up. However, the `hops` array, which is a path returned by `find_route` in + // the router excludes the payer node. In the following lines, the payer's information is + // hardcoded with an inflight value of 0 so that we can correctly represent the first hop + // in our sliding window of two. + let reversed_hops_with_payer = path.iter().rev().skip(1) + .map(|hop| hop.pubkey) + .chain(core::iter::once(payer_node_id)); + let mut cumulative_msat = 0; + + // Taking the reversed vector from above, we zip it with just the reversed hops list to + // work "backwards" of the given path, since the last hop's `fee_msat` actually represents + // the total amount sent. + for (next_hop, prev_hop) in path.iter().rev().zip(reversed_hops_with_payer) { + cumulative_msat += next_hop.fee_msat; + self.0 + .entry((next_hop.short_channel_id, NodeId::from_pubkey(&prev_hop) < NodeId::from_pubkey(&next_hop.pubkey))) + .and_modify(|used_liquidity_msat| *used_liquidity_msat += cumulative_msat) + .or_insert(cumulative_msat); + } } /// Returns liquidity in msat given the public key of the HTLC source, target, and short channel @@ -1974,7 +2139,7 @@ mod tests { use crate::routing::scoring::{ChannelUsage, Score, ProbabilisticScorer, ProbabilisticScoringParameters}; use crate::routing::test_utils::{add_channel, add_or_update_node, build_graph, build_line_graph, id_to_feature_flags, get_nodes, update_channel}; use crate::chain::transaction::OutPoint; - use crate::chain::keysinterface::KeysInterface; + use crate::chain::keysinterface::EntropySource; use crate::ln::features::{ChannelFeatures, InitFeatures, NodeFeatures}; use crate::ln::msgs::{ErrorAction, LightningError, UnsignedChannelUpdate, MAX_VALUE_MSAT}; use crate::ln::channelmanager; @@ -2025,6 +2190,7 @@ mod tests { inbound_capacity_msat: 42, unspendable_punishment_reserve: None, confirmations_required: None, + confirmations: None, force_close_spend_delay: None, is_outbound: true, is_channel_ready: true, is_usable: true, is_public: true, @@ -5487,7 +5653,7 @@ mod benches { use bitcoin::hashes::Hash; use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey}; use crate::chain::transaction::OutPoint; - use crate::chain::keysinterface::{KeysManager,KeysInterface}; + use crate::chain::keysinterface::{EntropySource, KeysManager}; use crate::ln::channelmanager::{self, ChannelCounterparty, ChannelDetails}; use crate::ln::features::InvoiceFeatures; use crate::routing::gossip::NetworkGraph; @@ -5539,6 +5705,7 @@ mod benches { inbound_capacity_msat: 0, unspendable_punishment_reserve: None, confirmations_required: None, + confirmations: None, force_close_spend_delay: None, is_outbound: true, is_channel_ready: true,