X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=1360aa3ddf475b4791dfafffa503fcd56a46b209;hb=d70292d6c8db9ee4ddc7889ddc4682b9cfc6be72;hp=f31bfd2ea4eef2a1e2cc6a31cdb94abdfebf71a3;hpb=28faf89df3027b7fea21c0717967ffbc721e1262;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index f31bfd2e..1360aa3d 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -423,7 +423,7 @@ impl<'a> CandidateRouteHop<'a> { /// so that we can choose cheaper paths (as per Dijkstra's algorithm). /// Fee values should be updated only in the context of the whole path, see update_value_and_recompute_fees. /// These fee values are useful to choose hops as we traverse the graph "payee-to-payer". -#[derive(Clone, Debug)] +#[derive(Clone)] struct PathBuildingHop<'a> { // Note that this should be dropped in favor of loading it from CandidateRouteHop, but doing so // is a larger refactor and will require careful performance analysis. @@ -455,7 +455,7 @@ struct PathBuildingHop<'a> { /// decrease as well. Thus, we have to explicitly track which nodes have been processed and /// avoid processing them again. was_processed: bool, - #[cfg(any(test, feature = "fuzztarget"))] + #[cfg(all(not(feature = "_bench_unstable"), any(test, fuzzing)))] // In tests, we apply further sanity checks on cases where we skip nodes we already processed // to ensure it is specifically in cases where the fee has gone down because of a decrease in // value_contribution_msat, which requires tracking it here. See comments below where it is @@ -463,6 +463,22 @@ struct PathBuildingHop<'a> { value_contribution_msat: u64, } +impl<'a> core::fmt::Debug for PathBuildingHop<'a> { + fn fmt(&self, f: &mut core::fmt::Formatter) -> Result<(), core::fmt::Error> { + f.debug_struct("PathBuildingHop") + .field("node_id", &self.node_id) + .field("short_channel_id", &self.candidate.short_channel_id()) + .field("total_fee_msat", &self.total_fee_msat) + .field("next_hops_fee_msat", &self.next_hops_fee_msat) + .field("hop_use_fee_msat", &self.hop_use_fee_msat) + .field("total_fee_msat - (next_hops_fee_msat + hop_use_fee_msat)", &(&self.total_fee_msat - (&self.next_hops_fee_msat + &self.hop_use_fee_msat))) + .field("path_penalty_msat", &self.path_penalty_msat) + .field("path_htlc_minimum_msat", &self.path_htlc_minimum_msat) + .field("cltv_expiry_delta", &self.candidate.cltv_expiry_delta()) + .finish() + } +} + // Instantiated with a list of hops with correct data in them collected during path finding, // an instance of this struct should be further modified only via given methods. #[derive(Clone)] @@ -719,8 +735,9 @@ where L::Target: Logger { node_info.features.supports_basic_mpp() } else { false } } else { false }; - log_trace!(logger, "Searching for a route from payer {} to payee {} {} MPP", our_node_pubkey, - payment_params.payee_pubkey, if allow_mpp { "with" } else { "without" }); + 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 " }); // Step (1). // Prepare the data we'll use for payee-to-payer search by @@ -876,8 +893,8 @@ where L::Target: Logger { // semi-dummy record just to compute the fees to reach the source node. // This will affect our decision on selecting short_channel_id // as a way to reach the $dest_node_id. - let mut fee_base_msat = u32::max_value(); - let mut fee_proportional_millionths = u32::max_value(); + let mut fee_base_msat = 0; + let mut fee_proportional_millionths = 0; if let Some(Some(fees)) = network_nodes.get(&$src_node_id).map(|node| node.lowest_inbound_channel_fees) { fee_base_msat = fees.base_msat; fee_proportional_millionths = fees.proportional_millionths; @@ -896,14 +913,14 @@ where L::Target: Logger { path_htlc_minimum_msat, path_penalty_msat: u64::max_value(), was_processed: false, - #[cfg(any(test, feature = "fuzztarget"))] + #[cfg(all(not(feature = "_bench_unstable"), any(test, fuzzing)))] value_contribution_msat, } }); #[allow(unused_mut)] // We only use the mut in cfg(test) let mut should_process = !old_entry.was_processed; - #[cfg(any(test, feature = "fuzztarget"))] + #[cfg(all(not(feature = "_bench_unstable"), any(test, fuzzing)))] { // In test/fuzzing builds, we do extra checks to make sure the skipping // of already-seen nodes only happens in cases we expect (see below). @@ -992,13 +1009,13 @@ where L::Target: Logger { old_entry.fee_msat = 0; // This value will be later filled with hop_use_fee_msat of the following channel old_entry.path_htlc_minimum_msat = path_htlc_minimum_msat; old_entry.path_penalty_msat = path_penalty_msat; - #[cfg(any(test, feature = "fuzztarget"))] + #[cfg(all(not(feature = "_bench_unstable"), any(test, fuzzing)))] { old_entry.value_contribution_msat = value_contribution_msat; } did_add_update_path_to_src_node = true; } else if old_entry.was_processed && new_cost < old_cost { - #[cfg(any(test, feature = "fuzztarget"))] + #[cfg(all(not(feature = "_bench_unstable"), any(test, fuzzing)))] { // If we're skipping processing a node which was previously // processed even though we found another path to it with a @@ -1268,11 +1285,9 @@ where L::Target: Logger { ordered_hops.last_mut().unwrap().1 = NodeFeatures::empty(); } } else { - // We should be able to fill in features for everything except the last - // hop, if the last hop was provided via a BOLT 11 invoice (though we - // should be able to extend it further as BOLT 11 does have feature - // flags for the last hop node itself). - assert!(ordered_hops.last().unwrap().0.node_id == payee_node_id); + // We can fill in features for everything except hops which were + // provided via the invoice we're paying. We could guess based on the + // recipient's features but for now we simply avoid guessing at all. } } @@ -1299,8 +1314,8 @@ where L::Target: Logger { ordered_hops.last_mut().unwrap().0.fee_msat = value_contribution_msat; ordered_hops.last_mut().unwrap().0.hop_use_fee_msat = 0; - log_trace!(logger, "Found a path back to us from the target with {} hops contributing up to {} msat: {:?}", - ordered_hops.len(), value_contribution_msat, ordered_hops); + log_trace!(logger, "Found a path back to us from the target with {} hops contributing up to {} msat: \n {:#?}", + ordered_hops.len(), value_contribution_msat, ordered_hops.iter().map(|h| &(h.0)).collect::>()); let mut payment_path = PaymentPath {hops: ordered_hops}; @@ -1522,9 +1537,9 @@ where L::Target: Logger { #[cfg(test)] mod tests { - use routing::scoring::{ProbabilisticScorer, ProbabilisticScoringParameters, Score}; use routing::network_graph::{NetworkGraph, NetGraphMsgHandler, NodeId}; use routing::router::{get_route, PaymentParameters, Route, RouteHint, RouteHintHop, RouteHop, RoutingFees}; + use routing::scoring::Score; use chain::transaction::OutPoint; use ln::features::{ChannelFeatures, InitFeatures, InvoiceFeatures, NodeFeatures}; use ln::msgs::{ErrorAction, LightningError, OptionalField, UnsignedChannelAnnouncement, ChannelAnnouncement, RoutingMessageHandler, @@ -1654,7 +1669,7 @@ mod tests { fn get_nodes(secp_ctx: &Secp256k1) -> (SecretKey, PublicKey, Vec, Vec) { let privkeys: Vec = (2..10).map(|i| { - SecretKey::from_slice(&hex::decode(format!("{:02}", i).repeat(32)).unwrap()[..]).unwrap() + SecretKey::from_slice(&hex::decode(format!("{:02x}", i).repeat(32)).unwrap()[..]).unwrap() }).collect(); let pubkeys = privkeys.iter().map(|secret| PublicKey::from_secret_key(&secp_ctx, secret)).collect(); @@ -2680,14 +2695,16 @@ mod tests { assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly } - fn multi_hint_last_hops(nodes: &Vec) -> Vec { + /// Builds a trivial last-hop hint that passes through the two nodes given, with channel 0xff00 + /// and 0xff01. + fn multi_hop_last_hops_hint(hint_hops: [PublicKey; 2]) -> Vec { let zero_fees = RoutingFees { base_msat: 0, proportional_millionths: 0, }; vec![RouteHint(vec![RouteHintHop { - src_node_id: nodes[2], - short_channel_id: 5, + src_node_id: hint_hops[0], + short_channel_id: 0xff00, fees: RoutingFees { base_msat: 100, proportional_millionths: 0, @@ -2696,19 +2713,12 @@ mod tests { htlc_minimum_msat: None, htlc_maximum_msat: None, }, RouteHintHop { - src_node_id: nodes[3], - short_channel_id: 8, + src_node_id: hint_hops[1], + short_channel_id: 0xff01, fees: zero_fees, cltv_expiry_delta: (8 << 4) | 1, htlc_minimum_msat: None, htlc_maximum_msat: None, - }]), RouteHint(vec![RouteHintHop { - src_node_id: nodes[5], - short_channel_id: 10, - fees: zero_fees, - cltv_expiry_delta: (10 << 4) | 1, - htlc_minimum_msat: None, - htlc_maximum_msat: None, }])] } @@ -2716,9 +2726,10 @@ mod tests { fn multi_hint_last_hops_test() { let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph(); let (_, our_id, privkeys, nodes) = get_nodes(&secp_ctx); - let payment_params = PaymentParameters::from_node_id(nodes[6]).with_route_hints(multi_hint_last_hops(&nodes)); + let last_hops = multi_hop_last_hops_hint([nodes[2], nodes[3]]); + let payment_params = PaymentParameters::from_node_id(nodes[6]).with_route_hints(last_hops.clone()); let scorer = test_utils::TestScorer::with_penalty(0); - // Test through channels 2, 3, 5, 8. + // Test through channels 2, 3, 0xff00, 0xff01. // Test shows that multiple hop hints are considered. // Disabling channels 6 & 7 by flags=2 @@ -2765,14 +2776,86 @@ mod tests { assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(4)); assert_eq!(route.paths[0][2].pubkey, nodes[3]); - assert_eq!(route.paths[0][2].short_channel_id, 5); + assert_eq!(route.paths[0][2].short_channel_id, last_hops[0].0[0].short_channel_id); assert_eq!(route.paths[0][2].fee_msat, 0); assert_eq!(route.paths[0][2].cltv_expiry_delta, 129); assert_eq!(route.paths[0][2].node_features.le_flags(), &id_to_feature_flags(4)); - assert_eq!(route.paths[0][2].channel_features.le_flags(), &Vec::::new()); + assert_eq!(route.paths[0][2].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly assert_eq!(route.paths[0][3].pubkey, nodes[6]); - assert_eq!(route.paths[0][3].short_channel_id, 8); + assert_eq!(route.paths[0][3].short_channel_id, last_hops[0].0[1].short_channel_id); + assert_eq!(route.paths[0][3].fee_msat, 100); + assert_eq!(route.paths[0][3].cltv_expiry_delta, 42); + assert_eq!(route.paths[0][3].node_features.le_flags(), &Vec::::new()); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][3].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly + } + + #[test] + fn private_multi_hint_last_hops_test() { + let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph(); + let (_, our_id, privkeys, nodes) = get_nodes(&secp_ctx); + + let non_announced_privkey = SecretKey::from_slice(&hex::decode(format!("{:02x}", 0xf0).repeat(32)).unwrap()[..]).unwrap(); + let non_announced_pubkey = PublicKey::from_secret_key(&secp_ctx, &non_announced_privkey); + + let last_hops = multi_hop_last_hops_hint([nodes[2], non_announced_pubkey]); + let payment_params = PaymentParameters::from_node_id(nodes[6]).with_route_hints(last_hops.clone()); + let scorer = test_utils::TestScorer::with_penalty(0); + // Test through channels 2, 3, 0xff00, 0xff01. + // Test shows that multiple hop hints are considered. + + // Disabling channels 6 & 7 by flags=2 + update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate { + chain_hash: genesis_block(Network::Testnet).header.block_hash(), + short_channel_id: 6, + timestamp: 2, + flags: 2, // to disable + cltv_expiry_delta: 0, + htlc_minimum_msat: 0, + htlc_maximum_msat: OptionalField::Absent, + fee_base_msat: 0, + fee_proportional_millionths: 0, + excess_data: Vec::new() + }); + update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate { + chain_hash: genesis_block(Network::Testnet).header.block_hash(), + short_channel_id: 7, + timestamp: 2, + flags: 2, // to disable + cltv_expiry_delta: 0, + htlc_minimum_msat: 0, + htlc_maximum_msat: OptionalField::Absent, + fee_base_msat: 0, + fee_proportional_millionths: 0, + excess_data: Vec::new() + }); + + let route = get_route(&our_id, &payment_params, &network_graph, None, 100, 42, Arc::clone(&logger), &scorer).unwrap(); + assert_eq!(route.paths[0].len(), 4); + + assert_eq!(route.paths[0][0].pubkey, nodes[1]); + assert_eq!(route.paths[0][0].short_channel_id, 2); + assert_eq!(route.paths[0][0].fee_msat, 200); + assert_eq!(route.paths[0][0].cltv_expiry_delta, 65); + assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(2)); + assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(2)); + + assert_eq!(route.paths[0][1].pubkey, nodes[2]); + assert_eq!(route.paths[0][1].short_channel_id, 4); + assert_eq!(route.paths[0][1].fee_msat, 100); + assert_eq!(route.paths[0][1].cltv_expiry_delta, 81); + assert_eq!(route.paths[0][1].node_features.le_flags(), &id_to_feature_flags(3)); + assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(4)); + + assert_eq!(route.paths[0][2].pubkey, non_announced_pubkey); + assert_eq!(route.paths[0][2].short_channel_id, last_hops[0].0[0].short_channel_id); + assert_eq!(route.paths[0][2].fee_msat, 0); + assert_eq!(route.paths[0][2].cltv_expiry_delta, 129); + assert_eq!(route.paths[0][2].node_features.le_flags(), &Vec::::new()); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][2].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly + + assert_eq!(route.paths[0][3].pubkey, nodes[6]); + assert_eq!(route.paths[0][3].short_channel_id, last_hops[0].0[1].short_channel_id); assert_eq!(route.paths[0][3].fee_msat, 100); assert_eq!(route.paths[0][3].cltv_expiry_delta, 42); assert_eq!(route.paths[0][3].node_features.le_flags(), &Vec::::new()); // We dont pass flags in from invoices yet @@ -4887,6 +4970,8 @@ mod tests { #[test] #[cfg(not(feature = "no-std"))] fn generate_routes() { + use routing::scoring::{ProbabilisticScorer, ProbabilisticScoringParameters}; + let mut d = match super::test_utils::get_route_file() { Ok(f) => f, Err(e) => { @@ -4919,6 +5004,8 @@ mod tests { #[test] #[cfg(not(feature = "no-std"))] fn generate_routes_mpp() { + use routing::scoring::{ProbabilisticScorer, ProbabilisticScoringParameters}; + let mut d = match super::test_utils::get_route_file() { Ok(f) => f, Err(e) => { @@ -4976,7 +5063,7 @@ pub(crate) mod test_utils { } } -#[cfg(all(test, feature = "unstable", not(feature = "no-std")))] +#[cfg(all(test, feature = "_bench_unstable", not(feature = "no-std")))] mod benches { use super::*; use bitcoin::hashes::Hash; @@ -4984,7 +5071,7 @@ mod benches { use chain::transaction::OutPoint; use ln::channelmanager::{ChannelCounterparty, ChannelDetails}; use ln::features::{InitFeatures, InvoiceFeatures}; - use routing::scoring::{FixedPenaltyScorer, Scorer}; + use routing::scoring::{FixedPenaltyScorer, ProbabilisticScorer, ProbabilisticScoringParameters, Scorer}; use util::logger::{Logger, Record}; use test::Bencher; @@ -5061,6 +5148,22 @@ mod benches { generate_routes(bench, &network_graph, scorer, InvoiceFeatures::known()); } + #[bench] + fn generate_routes_with_probabilistic_scorer(bench: &mut Bencher) { + let network_graph = read_network_graph(); + let params = ProbabilisticScoringParameters::default(); + let scorer = ProbabilisticScorer::new(params, &network_graph); + generate_routes(bench, &network_graph, scorer, InvoiceFeatures::empty()); + } + + #[bench] + fn generate_mpp_routes_with_probabilistic_scorer(bench: &mut Bencher) { + let network_graph = read_network_graph(); + let params = ProbabilisticScoringParameters::default(); + let scorer = ProbabilisticScorer::new(params, &network_graph); + generate_routes(bench, &network_graph, scorer, InvoiceFeatures::known()); + } + fn generate_routes( bench: &mut Bencher, graph: &NetworkGraph, mut scorer: S, features: InvoiceFeatures ) {