X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=048a434508e80bd88e5f6c62060fc852f09185db;hb=13b7cd503bd27981b249fabcaa4f2a12601f648b;hp=301ae76ddbb315e4aa02cec072e394f0bf87924f;hpb=574870e9f8faf44244dbfec2d146eb69e245d660;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index 301ae76d..048a4345 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -17,7 +17,7 @@ use bitcoin::secp256k1::PublicKey; use ln::channelmanager::ChannelDetails; use ln::features::{ChannelFeatures, InvoiceFeatures, NodeFeatures}; use ln::msgs::{DecodeError, ErrorAction, LightningError, MAX_VALUE_MSAT}; -use routing::gossip::{DirectedChannelInfoWithUpdate, EffectiveCapacity, NetworkGraph, ReadOnlyNetworkGraph, NodeId, RoutingFees}; +use routing::gossip::{DirectedChannelInfoWithUpdate, EffectiveCapacity, ReadOnlyNetworkGraph, NodeId, RoutingFees}; use routing::scoring::{ChannelUsage, Score}; use util::ser::{Writeable, Readable, Writer}; use util::logger::{Level, Logger}; @@ -176,6 +176,11 @@ impl_writeable_tlv_based!(RouteParameters, { /// Maximum total CTLV difference we allow for a full payment path. pub const DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA: u32 = 1008; +/// Maximum number of paths we allow an MPP payment to have. +// The default limit is currently set rather arbitrary - there aren't any real fundamental path-count +// limits, but for now more than 10 paths likely carries too much one-path failure. +pub const DEFAULT_MAX_MPP_PATH_COUNT: u8 = 10; + // The median hop CLTV expiry delta currently seen in the network. const MEDIAN_HOP_CLTV_EXPIRY_DELTA: u32 = 40; @@ -214,13 +219,19 @@ pub struct PaymentParameters { pub expiry_time: Option, /// The maximum total CLTV delta we accept for the route. + /// Defaults to [`DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA`]. pub max_total_cltv_expiry_delta: u32, + + /// The maximum number of paths that may be used by MPP payments. + /// Defaults to [`DEFAULT_MAX_MPP_PATH_COUNT`]. + pub max_mpp_path_count: u8, } impl_writeable_tlv_based!(PaymentParameters, { (0, payee_pubkey, required), (1, max_total_cltv_expiry_delta, (default_value, DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA)), (2, features, option), + (3, max_mpp_path_count, (default_value, DEFAULT_MAX_MPP_PATH_COUNT)), (4, route_hints, vec_type), (6, expiry_time, option), }); @@ -234,6 +245,7 @@ impl PaymentParameters { route_hints: vec![], expiry_time: None, max_total_cltv_expiry_delta: DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA, + max_mpp_path_count: DEFAULT_MAX_MPP_PATH_COUNT, } } @@ -269,6 +281,13 @@ impl PaymentParameters { pub fn with_max_total_cltv_expiry_delta(self, max_total_cltv_expiry_delta: u32) -> Self { Self { max_total_cltv_expiry_delta, ..self } } + + /// Includes a limit for the maximum number of payment paths that may be used by MPP. + /// + /// (C-not exported) since bindings don't support move semantics + pub fn with_max_mpp_path_count(self, max_mpp_path_count: u8) -> Self { + Self { max_mpp_path_count, ..self } + } } /// A list of hops along a payment path terminating with a channel to the recipient. @@ -369,7 +388,7 @@ enum CandidateRouteHop<'a> { FirstHop { details: &'a ChannelDetails, }, - /// A hop found in the [`NetworkGraph`], where the channel capacity may or may not be known. + /// A hop found in the [`ReadOnlyNetworkGraph`], where the channel capacity may be unknown. PublicHop { info: DirectedChannelInfoWithUpdate<'a>, short_channel_id: u64, @@ -650,8 +669,8 @@ fn default_node_features() -> NodeFeatures { /// Private routing paths between a public node and the target may be included in `params.payee`. /// /// If some channels aren't announced, it may be useful to fill in `first_hops` with the results -/// from [`ChannelManager::list_usable_channels`]. If it is filled in, the view of our local -/// channels from [`NetworkGraph`] will be ignored, and only those in `first_hops` will be used. +/// from [`ChannelManager::list_usable_channels`]. If it is filled in, the view of these channels +/// from `network_graph` will be ignored, and only those in `first_hops` will be used. /// /// The fees on channels from us to the next hop are ignored as they are assumed to all be equal. /// However, the enabled/disabled bit on such channels as well as the `htlc_minimum_msat` / @@ -670,16 +689,17 @@ fn default_node_features() -> NodeFeatures { /// /// [`ChannelManager::list_usable_channels`]: crate::ln::channelmanager::ChannelManager::list_usable_channels /// [`Event::PaymentPathFailed`]: crate::util::events::Event::PaymentPathFailed +/// [`NetworkGraph`]: crate::routing::gossip::NetworkGraph pub fn find_route( - our_node_pubkey: &PublicKey, route_params: &RouteParameters, network: &NetworkGraph, - first_hops: Option<&[&ChannelDetails]>, logger: L, scorer: &S, random_seed_bytes: &[u8; 32] + our_node_pubkey: &PublicKey, route_params: &RouteParameters, + network_graph: &ReadOnlyNetworkGraph, first_hops: Option<&[&ChannelDetails]>, logger: L, + scorer: &S, random_seed_bytes: &[u8; 32] ) -> Result where L::Target: Logger { - let network_graph = network.read_only(); - let mut route = get_route(our_node_pubkey, &route_params.payment_params, &network_graph, first_hops, + let mut route = get_route(our_node_pubkey, &route_params.payment_params, network_graph, first_hops, route_params.final_value_msat, route_params.final_cltv_expiry_delta, logger, scorer, random_seed_bytes)?; - add_random_cltv_offset(&mut route, &route_params.payment_params, &network_graph, random_seed_bytes); + add_random_cltv_offset(&mut route, &route_params.payment_params, network_graph, random_seed_bytes); Ok(route) } @@ -789,6 +809,11 @@ where L::Target: Logger { node_info.features.supports_basic_mpp() } else { false } } else { false }; + + if allow_mpp && payment_params.max_mpp_path_count == 0 { + return Err(LightningError{err: "Can't find an MPP route with no paths allowed.".to_owned(), action: ErrorAction::IgnoreError}); + } + log_trace!(logger, "Searching for a route from payer {} to payee {} {} MPP and {} first hops {}overriding the network graph", our_node_pubkey, payment_params.payee_pubkey, if allow_mpp { "with" } else { "without" }, first_hops.map(|hops| hops.len()).unwrap_or(0), if first_hops.is_some() { "" } else { "not " }); @@ -839,6 +864,21 @@ where L::Target: Logger { let recommended_value_msat = final_value_msat * ROUTE_CAPACITY_PROVISION_FACTOR as u64; let mut path_value_msat = final_value_msat; + // Routing Fragmentation Mitigation heuristic: + // + // Routing fragmentation across many payment paths increases the overall routing + // fees as you have irreducible routing fees per-link used (`fee_base_msat`). + // Taking too many smaller paths also increases the chance of payment failure. + // Thus to avoid this effect, we require from our collected links to provide + // at least a minimal contribution to the recommended value yet-to-be-fulfilled. + // This requirement is currently set to be 1/max_mpp_path_count of the payment + // value to ensure we only ever return routes that do not violate this limit. + let minimal_value_contribution_msat: u64 = if allow_mpp { + (final_value_msat + (payment_params.max_mpp_path_count as u64 - 1)) / payment_params.max_mpp_path_count as u64 + } else { + final_value_msat + }; + // Keep track of how much liquidity has been used in selected channels. Used to determine // if the channel can be used by additional MPP paths or to inform path finding decisions. It is // aware of direction *only* to ensure that the correct htlc_maximum_msat value is used. Hence, @@ -846,11 +886,8 @@ where L::Target: Logger { let mut used_channel_liquidities: HashMap<(u64, bool), u64> = HashMap::with_capacity(network_nodes.len()); - // Keeping track of how much value we already collected across other paths. Helps to decide: - // - how much a new path should be transferring (upper bound); - // - whether a channel should be disregarded because - // it's available liquidity is too small comparing to how much more we need to collect; - // - when we want to stop looking for new paths. + // Keeping track of how much value we already collected across other paths. Helps to decide + // when we want to stop looking for new paths. let mut already_collected_value_msat = 0; for (_, channels) in first_hop_targets.iter_mut() { @@ -912,26 +949,6 @@ where L::Target: Logger { *used_liquidity_msat }); - // Routing Fragmentation Mitigation heuristic: - // - // Routing fragmentation across many payment paths increases the overall routing - // fees as you have irreducible routing fees per-link used (`fee_base_msat`). - // Taking too many smaller paths also increases the chance of payment failure. - // Thus to avoid this effect, we require from our collected links to provide - // at least a minimal contribution to the recommended value yet-to-be-fulfilled. - // - // This requirement is currently 5% of the remaining-to-be-collected value. - // This means as we successfully advance in our collection, - // the absolute liquidity contribution is lowered, - // thus increasing the number of potential channels to be selected. - - // Derive the minimal liquidity contribution with a ratio of 20 (5%, rounded up) - // or 100% if we're not allowed to do multipath payments. - let minimal_value_contribution_msat: u64 = if allow_mpp { - (recommended_value_msat - already_collected_value_msat + 19) / 20 - } else { - final_value_msat - }; // Verify the liquidity offered by this channel complies to the minimal contribution. let contributes_sufficient_value = available_value_contribution_msat >= minimal_value_contribution_msat; // Do not consider candidate hops that would exceed the maximum path length. @@ -1503,10 +1520,8 @@ where L::Target: Logger { *used_channel_liquidities.entry((victim_scid, true)).or_default() = exhausted; } - // Track the total amount all our collected paths allow to send so that we: - // - know when to stop looking for more paths - // - know which of the hops are useless considering how much more sats we need - // (contributes_sufficient_value) + // Track the total amount all our collected paths allow to send so that we know + // when to stop looking for more paths already_collected_value_msat += value_contribution_msat; payment_paths.push(payment_path); @@ -1677,6 +1692,8 @@ where L::Target: Logger { }); selected_paths.push(path); } + // Make sure we would never create a route with more paths than we allow. + debug_assert!(selected_paths.len() <= payment_params.max_mpp_path_count.into()); if let Some(features) = &payment_params.features { for path in selected_paths.iter_mut() { @@ -1787,11 +1804,10 @@ fn add_random_cltv_offset(route: &mut Route, payment_params: &PaymentParameters, /// /// Re-uses logic from `find_route`, so the restrictions described there also apply here. pub fn build_route_from_hops( - our_node_pubkey: &PublicKey, hops: &[PublicKey], route_params: &RouteParameters, network: &NetworkGraph, - logger: L, random_seed_bytes: &[u8; 32] + our_node_pubkey: &PublicKey, hops: &[PublicKey], route_params: &RouteParameters, + network_graph: &ReadOnlyNetworkGraph, logger: L, random_seed_bytes: &[u8; 32] ) -> Result where L::Target: Logger { - let network_graph = network.read_only(); let mut route = build_route_from_hops_internal( our_node_pubkey, hops, &route_params.payment_params, &network_graph, route_params.final_value_msat, route_params.final_cltv_expiry_delta, logger, random_seed_bytes)?; @@ -1926,7 +1942,7 @@ mod tests { // Using the same keys for LN and BTC ids fn add_channel( - gossip_sync: &P2PGossipSync, Arc, Arc>, + gossip_sync: &P2PGossipSync>>, Arc, Arc>, secp_ctx: &Secp256k1, node_1_privkey: &SecretKey, node_2_privkey: &SecretKey, features: ChannelFeatures, short_channel_id: u64 ) { let node_id_1 = PublicKey::from_secret_key(&secp_ctx, node_1_privkey); @@ -1958,7 +1974,7 @@ mod tests { } fn update_channel( - gossip_sync: &P2PGossipSync, Arc, Arc>, + gossip_sync: &P2PGossipSync>>, Arc, Arc>, secp_ctx: &Secp256k1, node_privkey: &SecretKey, update: UnsignedChannelUpdate ) { let msghash = hash_to_message!(&Sha256dHash::hash(&update.encode()[..])[..]); @@ -1974,7 +1990,7 @@ mod tests { } fn add_or_update_node( - gossip_sync: &P2PGossipSync, Arc, Arc>, + gossip_sync: &P2PGossipSync>>, Arc, Arc>, secp_ctx: &Secp256k1, node_privkey: &SecretKey, features: NodeFeatures, timestamp: u32 ) { let node_id = PublicKey::from_secret_key(&secp_ctx, node_privkey); @@ -2029,14 +2045,15 @@ mod tests { } fn build_line_graph() -> ( - Secp256k1, sync::Arc, P2PGossipSync, - sync::Arc, sync::Arc>, + Secp256k1, sync::Arc>>, + P2PGossipSync>>, sync::Arc, sync::Arc>, sync::Arc, sync::Arc, ) { let secp_ctx = Secp256k1::new(); let logger = Arc::new(test_utils::TestLogger::new()); let chain_monitor = Arc::new(test_utils::TestChainSource::new(Network::Testnet)); - let network_graph = Arc::new(NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash())); + let genesis_hash = genesis_block(Network::Testnet).header.block_hash(); + let network_graph = Arc::new(NetworkGraph::new(genesis_hash, Arc::clone(&logger))); let gossip_sync = P2PGossipSync::new(Arc::clone(&network_graph), None, Arc::clone(&logger)); // Build network from our_id to node 19: @@ -2081,15 +2098,16 @@ mod tests { fn build_graph() -> ( Secp256k1, - sync::Arc, - P2PGossipSync, sync::Arc, sync::Arc>, + sync::Arc>>, + P2PGossipSync>>, sync::Arc, sync::Arc>, sync::Arc, sync::Arc, ) { let secp_ctx = Secp256k1::new(); let logger = Arc::new(test_utils::TestLogger::new()); let chain_monitor = Arc::new(test_utils::TestChainSource::new(Network::Testnet)); - let network_graph = Arc::new(NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash())); + let genesis_hash = genesis_block(Network::Testnet).header.block_hash(); + let network_graph = Arc::new(NetworkGraph::new(genesis_hash, Arc::clone(&logger))); let gossip_sync = P2PGossipSync::new(Arc::clone(&network_graph), None, Arc::clone(&logger)); // Build network from our_id to node6: // @@ -3489,8 +3507,12 @@ mod tests { let scorer = test_utils::TestScorer::with_penalty(0); let keys_manager = test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet); let random_seed_bytes = keys_manager.get_secure_random_bytes(); - get_route(&source_node_id, &payment_params, &NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash()).read_only(), - Some(&our_chans.iter().collect::>()), route_val, 42, &test_utils::TestLogger::new(), &scorer, &random_seed_bytes) + let genesis_hash = genesis_block(Network::Testnet).header.block_hash(); + let logger = test_utils::TestLogger::new(); + let network_graph = NetworkGraph::new(genesis_hash, &logger); + let route = get_route(&source_node_id, &payment_params, &network_graph.read_only(), + Some(&our_chans.iter().collect::>()), route_val, 42, &logger, &scorer, &random_seed_bytes); + route } #[test] @@ -4882,8 +4904,9 @@ mod tests { // payment) htlc_minimum_msat. In the original algorithm, this resulted in node4's // "previous hop" being set to node 3, creating a loop in the path. let secp_ctx = Secp256k1::new(); + let genesis_hash = genesis_block(Network::Testnet).header.block_hash(); let logger = Arc::new(test_utils::TestLogger::new()); - let network = Arc::new(NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash())); + let network = Arc::new(NetworkGraph::new(genesis_hash, Arc::clone(&logger))); let gossip_sync = P2PGossipSync::new(Arc::clone(&network), None, Arc::clone(&logger)); let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx); let scorer = test_utils::TestScorer::with_penalty(0); @@ -5148,8 +5171,9 @@ mod tests { // route over multiple channels with the same first hop. let secp_ctx = Secp256k1::new(); let (_, our_id, _, nodes) = get_nodes(&secp_ctx); + let genesis_hash = genesis_block(Network::Testnet).header.block_hash(); let logger = Arc::new(test_utils::TestLogger::new()); - let network_graph = NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash()); + let network_graph = NetworkGraph::new(genesis_hash, Arc::clone(&logger)); let scorer = test_utils::TestScorer::with_penalty(0); let payment_params = PaymentParameters::from_node_id(nodes[0]).with_features(InvoiceFeatures::known()); let keys_manager = test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet); @@ -5587,7 +5611,7 @@ mod tests { seed } #[cfg(not(feature = "no-std"))] - use util::ser::Readable; + use util::ser::ReadableArgs; #[test] #[cfg(not(feature = "no-std"))] @@ -5601,7 +5625,8 @@ mod tests { return; }, }; - let graph = NetworkGraph::read(&mut d).unwrap(); + let logger = test_utils::TestLogger::new(); + let graph = NetworkGraph::read(&mut d, &logger).unwrap(); let keys_manager = test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet); let random_seed_bytes = keys_manager.get_secure_random_bytes(); @@ -5617,7 +5642,6 @@ mod tests { let payment_params = PaymentParameters::from_node_id(dst); let amt = seed as u64 % 200_000_000; let params = ProbabilisticScoringParameters::default(); - let logger = test_utils::TestLogger::new(); let scorer = ProbabilisticScorer::new(params, &graph, &logger); if get_route(src, &payment_params, &graph.read_only(), None, amt, 42, &logger, &scorer, &random_seed_bytes).is_ok() { continue 'load_endpoints; @@ -5638,7 +5662,8 @@ mod tests { return; }, }; - let graph = NetworkGraph::read(&mut d).unwrap(); + let logger = test_utils::TestLogger::new(); + let graph = NetworkGraph::read(&mut d, &logger).unwrap(); let keys_manager = test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet); let random_seed_bytes = keys_manager.get_secure_random_bytes(); @@ -5654,7 +5679,6 @@ mod tests { let payment_params = PaymentParameters::from_node_id(dst).with_features(InvoiceFeatures::known()); let amt = seed as u64 % 200_000_000; let params = ProbabilisticScoringParameters::default(); - let logger = test_utils::TestLogger::new(); let scorer = ProbabilisticScorer::new(params, &graph, &logger); if get_route(src, &payment_params, &graph.read_only(), None, amt, 42, &logger, &scorer, &random_seed_bytes).is_ok() { continue 'load_endpoints; @@ -5700,9 +5724,10 @@ mod benches { use chain::keysinterface::{KeysManager,KeysInterface}; use ln::channelmanager::{ChannelCounterparty, ChannelDetails}; use ln::features::{InitFeatures, InvoiceFeatures}; + use routing::gossip::NetworkGraph; use routing::scoring::{FixedPenaltyScorer, ProbabilisticScorer, ProbabilisticScoringParameters}; use util::logger::{Logger, Record}; - use util::test_utils::TestLogger; + use util::ser::ReadableArgs; use test::Bencher; @@ -5711,9 +5736,9 @@ mod benches { fn log(&self, _record: &Record) {} } - fn read_network_graph() -> NetworkGraph { + fn read_network_graph(logger: &DummyLogger) -> NetworkGraph<&DummyLogger> { let mut d = test_utils::get_route_file().unwrap(); - NetworkGraph::read(&mut d).unwrap() + NetworkGraph::read(&mut d, logger).unwrap() } fn payer_pubkey() -> PublicKey { @@ -5760,22 +5785,24 @@ mod benches { #[bench] fn generate_routes_with_zero_penalty_scorer(bench: &mut Bencher) { - let network_graph = read_network_graph(); + let logger = DummyLogger {}; + let network_graph = read_network_graph(&logger); let scorer = FixedPenaltyScorer::with_penalty(0); generate_routes(bench, &network_graph, scorer, InvoiceFeatures::empty()); } #[bench] fn generate_mpp_routes_with_zero_penalty_scorer(bench: &mut Bencher) { - let network_graph = read_network_graph(); + let logger = DummyLogger {}; + let network_graph = read_network_graph(&logger); let scorer = FixedPenaltyScorer::with_penalty(0); generate_routes(bench, &network_graph, scorer, InvoiceFeatures::known()); } #[bench] fn generate_routes_with_probabilistic_scorer(bench: &mut Bencher) { - let logger = TestLogger::new(); - let network_graph = read_network_graph(); + let logger = DummyLogger {}; + let network_graph = read_network_graph(&logger); let params = ProbabilisticScoringParameters::default(); let scorer = ProbabilisticScorer::new(params, &network_graph, &logger); generate_routes(bench, &network_graph, scorer, InvoiceFeatures::empty()); @@ -5783,15 +5810,16 @@ mod benches { #[bench] fn generate_mpp_routes_with_probabilistic_scorer(bench: &mut Bencher) { - let logger = TestLogger::new(); - let network_graph = read_network_graph(); + let logger = DummyLogger {}; + let network_graph = read_network_graph(&logger); let params = ProbabilisticScoringParameters::default(); let scorer = ProbabilisticScorer::new(params, &network_graph, &logger); generate_routes(bench, &network_graph, scorer, InvoiceFeatures::known()); } fn generate_routes( - bench: &mut Bencher, graph: &NetworkGraph, mut scorer: S, features: InvoiceFeatures + bench: &mut Bencher, graph: &NetworkGraph<&DummyLogger>, mut scorer: S, + features: InvoiceFeatures ) { let nodes = graph.read_only().nodes().clone(); let payer = payer_pubkey();