X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;fp=lightning%2Fsrc%2Frouting%2Frouter.rs;h=7c78a7bad896e33b5777baf3efac84ecda088415;hb=7da08a77ba5b6d4bfb3c09b885703518966c00de;hp=3454172e3d204921230c214dd351839cc3f3f872;hpb=87170e9f452774a297ee82d1ff3334af22bfefd8;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index 3454172e..7c78a7ba 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -1131,6 +1131,12 @@ pub struct CandidateFirstHop<'a> { pub details: &'a ChannelDetails, /// The node id of the payer, which is also the source side of this candidate route hop. pub payer_node_id: &'a NodeId, + /// A unique ID which describes the payer. It will not conlict with any + /// [`NodeInfo::node_counter`]s, but may be equal to one if the payer is a public node. + payer_node_counter: u32, + /// A unique ID which describes the first hop counterparty. It will not conlict with any + /// [`NodeInfo::node_counter`]s, but may be equal to one if the counterparty is a public node. + target_node_counter: u32, } /// A [`CandidateRouteHop::PublicHop`] entry. @@ -1150,7 +1156,16 @@ pub struct CandidatePrivateHop<'a> { /// Information about the private hop communicated via BOLT 11. pub hint: &'a RouteHintHop, /// Node id of the next hop in BOLT 11 route hint. - pub target_node_id: &'a NodeId + pub target_node_id: &'a NodeId, + /// A unique ID which describes the source node of the hop (further from the payment target). + /// It will not conlict with any [`NodeInfo::node_counter`]s, but may be equal to one if the + /// node is a public node. + source_node_counter: u32, + /// A unique ID which describes the destination node of the hop (towards the payment target). + /// It will not conlict with any [`NodeInfo::node_counter`]s, but may be equal to one if the + /// node is a public node. + target_node_counter: u32, + } /// A [`CandidateRouteHop::Blinded`] entry. @@ -1164,6 +1179,10 @@ pub struct CandidateBlindedPath<'a> { /// This is used to cheaply uniquely identify this blinded path, even though we don't have /// a short channel ID for this hop. hint_idx: usize, + /// A unique ID which describes the introduction point of the blinded path. + /// It will not conlict with any [`NodeInfo::node_counter`]s, but will generally be equal to + /// one from the public network graph (assuming the introduction point is a public node). + source_node_counter: u32, } /// A [`CandidateRouteHop::OneHopBlinded`] entry. @@ -1179,6 +1198,10 @@ pub struct CandidateOneHopBlindedPath<'a> { /// This is used to cheaply uniquely identify this blinded path, even though we don't have /// a short channel ID for this hop. hint_idx: usize, + /// A unique ID which describes the introduction point of the blinded path. + /// It will not conlict with any [`NodeInfo::node_counter`]s, but will generally be equal to + /// one from the public network graph (assuming the introduction point is a public node). + source_node_counter: u32, } /// A wrapper around the various hop representations. @@ -1301,6 +1324,28 @@ impl<'a> CandidateRouteHop<'a> { } } + #[inline] + fn src_node_counter(&self) -> u32 { + match self { + CandidateRouteHop::FirstHop { payer_node_counter, .. } => *payer_node_counter, + CandidateRouteHop::PublicHop { info, .. } => info.source_counter(), + CandidateRouteHop::PrivateHop { source_node_counter, .. } => *source_node_counter, + CandidateRouteHop::Blinded { source_node_counter, .. } => *source_node_counter, + CandidateRouteHop::OneHopBlinded { source_node_counter, .. } => *source_node_counter, + } + } + + #[inline] + fn target_node_counter(&self) -> Option { + match self { + CandidateRouteHop::FirstHop { target_node_counter, .. } => Some(*target_node_counter), + CandidateRouteHop::PublicHop { info, .. } => Some(info.target_counter()), + CandidateRouteHop::PrivateHop { target_node_counter, .. } => Some(*target_node_counter), + CandidateRouteHop::Blinded { .. } => None, + CandidateRouteHop::OneHopBlinded { .. } => None, + } + } + /// Returns the fees that must be paid to route an HTLC over this channel. #[inline] pub fn fees(&self) -> RoutingFees { @@ -1449,6 +1494,7 @@ fn iter_equal(mut iter_a: I1, mut iter_b: I2) #[repr(C)] // Force fields to appear in the order we define them. struct PathBuildingHop<'a> { candidate: CandidateRouteHop<'a>, + target_node_counter: Option, /// If we've already processed a node as the best node, we shouldn't process it again. Normally /// we'd just ignore it if we did as all channels would have a higher new fee, but because we /// may decrease the amounts in use as we walk the graph, the actual calculated fee may @@ -1504,12 +1550,13 @@ impl<'a> core::fmt::Debug for PathBuildingHop<'a> { fn fmt(&self, f: &mut core::fmt::Formatter) -> Result<(), core::fmt::Error> { let mut debug_struct = f.debug_struct("PathBuildingHop"); debug_struct - .field("node_id", &self.candidate.target()) + .field("source_node_id", &self.candidate.source()) + .field("target_node_id", &self.candidate.target()) .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("total_fee_msat - (next_hops_fee_msat + hop_use_fee_msat)", &(&self.total_fee_msat.saturating_sub(self.next_hops_fee_msat).saturating_sub(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()); @@ -1930,11 +1977,42 @@ where L::Target: Logger { first_hops.map(|hops| hops.len()).unwrap_or(0), if first_hops.is_some() { "" } else { "not " }, max_total_routing_fee_msat); + let private_hop_targets_node_counter_offset = network_graph.max_node_counter() + 2; + let mut private_node_id_to_node_counter = HashMap::new(); + + let mut private_hop_key_cache = HashMap::with_capacity( + payment_params.payee.unblinded_route_hints().iter().map(|path| path.0.len()).sum() + ); + + // Because we store references to private hop node_ids in `dist`, below, we need them to exist + // (as `NodeId`, not `PublicKey`) for the lifetime of `dist`. Thus, we calculate all the keys + // we'll need here and simply fetch them when routing. + let payee_node_counter = payee_node_id_opt + .and_then(|payee| network_nodes.get(&payee)) + .map(|node| node.node_counter) + .unwrap_or(private_hop_targets_node_counter_offset); + private_node_id_to_node_counter.insert(maybe_dummy_payee_node_id, payee_node_counter); + private_hop_key_cache.insert(maybe_dummy_payee_pk, (NodeId::from_pubkey(&maybe_dummy_payee_pk), payee_node_counter)); + + for route in payment_params.payee.unblinded_route_hints().iter() { + for hop in route.0.iter() { + let hop_node_id = NodeId::from_pubkey(&hop.src_node_id); + let node_counter = if let Some(node) = network_nodes.get(&hop_node_id) { + node.node_counter + } else { + let next_node_counter = private_hop_targets_node_counter_offset + private_node_id_to_node_counter.len() as u32; + *private_node_id_to_node_counter.entry(hop_node_id) + .or_insert(next_node_counter) + }; + private_hop_key_cache.insert(hop.src_node_id, (hop_node_id, node_counter)); + } + } + // Step (1). // Prepare the data we'll use for payee-to-payer search by // inserting first hops suggested by the caller as targets. // Our search will then attempt to reach them while traversing from the payee node. - let mut first_hop_targets: HashMap<_, Vec<&ChannelDetails>> = + let mut first_hop_targets: HashMap<_, (Vec<&ChannelDetails>, u32)> = HashMap::with_capacity(if first_hops.is_some() { first_hops.as_ref().unwrap().len() } else { 0 }); if let Some(hops) = first_hops { for chan in hops { @@ -1944,30 +2022,26 @@ where L::Target: Logger { if chan.counterparty.node_id == *our_node_pubkey { return Err(LightningError{err: "First hop cannot have our_node_pubkey as a destination.".to_owned(), action: ErrorAction::IgnoreError}); } + let counterparty_node_id = NodeId::from_pubkey(&chan.counterparty.node_id); first_hop_targets - .entry(NodeId::from_pubkey(&chan.counterparty.node_id)) - .or_insert(Vec::new()) - .push(chan); + .entry(counterparty_node_id) + .or_insert_with(|| { + let node_counter = if let Some(node) = network_nodes.get(&counterparty_node_id) { + node.node_counter + } else { + let next_node_counter = private_hop_targets_node_counter_offset + private_node_id_to_node_counter.len() as u32; + *private_node_id_to_node_counter.entry(counterparty_node_id) + .or_insert(next_node_counter) + }; + (Vec::new(), node_counter) + }) + .0.push(chan); } if first_hop_targets.is_empty() { return Err(LightningError{err: "Cannot route when there are no outbound routes away from us".to_owned(), action: ErrorAction::IgnoreError}); } } - let mut private_hop_key_cache = HashMap::with_capacity( - payment_params.payee.unblinded_route_hints().iter().map(|path| path.0.len()).sum() - ); - - // Because we store references to private hop node_ids in `dist`, below, we need them to exist - // (as `NodeId`, not `PublicKey`) for the lifetime of `dist`. Thus, we calculate all the keys - // we'll need here and simply fetch them when routing. - private_hop_key_cache.insert(maybe_dummy_payee_pk, NodeId::from_pubkey(&maybe_dummy_payee_pk)); - for route in payment_params.payee.unblinded_route_hints().iter() { - for hop in route.0.iter() { - private_hop_key_cache.insert(hop.src_node_id, NodeId::from_pubkey(&hop.src_node_id)); - } - } - // The main heap containing all candidate next-hops sorted by their score (max(fee, // htlc_minimum)). Ideally this would be a heap which allowed cheap score reduction instead of // adding duplicate entries when we find a better path to a given node. @@ -1975,7 +2049,15 @@ where L::Target: Logger { // Map from node_id to information about the best current path to that node, including feerate // information. - let mut dist: HashMap = HashMap::with_capacity(network_nodes.len()); + let dist_len = private_hop_targets_node_counter_offset + private_hop_key_cache.len() as u32 + 1; + let mut dist: Vec> = vec![None; dist_len as usize]; + let payer_node_counter = network_nodes + .get(&our_node_id) + .map(|node| node.node_counter) + .or_else(|| { + private_node_id_to_node_counter.get(&our_node_id).map(|counter| *counter) + }) + .unwrap_or(network_graph.max_node_counter() + 1); // During routing, if we ignore a path due to an htlc_minimum_msat limit, we set this, // indicating that we may wish to try again with a higher value, potentially paying to meet an @@ -2022,7 +2104,7 @@ where L::Target: Logger { // when we want to stop looking for new paths. let mut already_collected_value_msat = 0; - for (_, channels) in first_hop_targets.iter_mut() { + for (_, (channels, _)) in first_hop_targets.iter_mut() { sort_first_hop_channels(channels, &used_liquidities, recommended_value_msat, our_node_pubkey); } @@ -2186,15 +2268,19 @@ where L::Target: Logger { ); let path_htlc_minimum_msat = compute_fees_saturating(curr_min, $candidate.fees()) .saturating_add(curr_min); - let hm_entry = dist.entry(src_node_id); - let old_entry = hm_entry.or_insert_with(|| { + + let dist_entry = &mut dist[$candidate.src_node_counter() as usize]; + let mut old_entry = if let Some(hop) = dist_entry { + hop + } else { // If there was previously no known way to access the source node // (recall it goes payee-to-payer) of short_channel_id, first add a // 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 $candidate.target() node. - PathBuildingHop { + *dist_entry = Some(PathBuildingHop { candidate: $candidate.clone(), + target_node_counter: None, fee_msat: 0, next_hops_fee_msat: u64::max_value(), hop_use_fee_msat: u64::max_value(), @@ -2204,8 +2290,9 @@ where L::Target: Logger { was_processed: false, #[cfg(all(not(ldk_bench), any(test, fuzzing)))] value_contribution_msat, - } - }); + }); + dist_entry.as_mut().unwrap() + }; #[allow(unused_mut)] // We only use the mut in cfg(test) let mut should_process = !old_entry.was_processed; @@ -2287,6 +2374,7 @@ where L::Target: Logger { path_length_to_node, }; targets.push(new_graph_node); + old_entry.target_node_counter = $candidate.target_node_counter(); old_entry.next_hops_fee_msat = $next_hops_fee_msat; old_entry.hop_use_fee_msat = hop_use_fee_msat; old_entry.total_fee_msat = total_fee_msat; @@ -2364,7 +2452,7 @@ where L::Target: Logger { let fee_to_target_msat; let next_hops_path_htlc_minimum_msat; let next_hops_path_penalty_msat; - let skip_node = if let Some(elem) = dist.get_mut(&$node_id) { + let skip_node = if let Some(elem) = &mut dist[$node.node_counter as usize] { let was_processed = elem.was_processed; elem.was_processed = true; fee_to_target_msat = elem.total_fee_msat; @@ -2376,6 +2464,7 @@ where L::Target: Logger { // Because there are no channels from payee, it will not have a dist entry at this point. // If we're processing any other node, it is always be the result of a channel from it. debug_assert_eq!($node_id, maybe_dummy_payee_node_id); + fee_to_target_msat = 0; next_hops_path_htlc_minimum_msat = 0; next_hops_path_penalty_msat = 0; @@ -2383,10 +2472,12 @@ where L::Target: Logger { }; if !skip_node { - if let Some(first_channels) = first_hop_targets.get(&$node_id) { + if let Some((first_channels, peer_node_counter)) = first_hop_targets.get(&$node_id) { for details in first_channels { + debug_assert_eq!(*peer_node_counter, $node.node_counter); let candidate = CandidateRouteHop::FirstHop(CandidateFirstHop { - details, payer_node_id: &our_node_id, + details, payer_node_id: &our_node_id, payer_node_counter, + target_node_counter: $node.node_counter, }); add_entry!(&candidate, fee_to_target_msat, $next_hops_value_contribution, @@ -2435,15 +2526,19 @@ where L::Target: Logger { // For every new path, start from scratch, except for used_liquidities, which // helps to avoid reusing previously selected paths in future iterations. targets.clear(); - dist.clear(); + for e in dist.iter_mut() { + *e = None; + } hit_minimum_limit = false; // If first hop is a private channel and the only way to reach the payee, this is the only // place where it could be added. - payee_node_id_opt.map(|payee| first_hop_targets.get(&payee).map(|first_channels| { + payee_node_id_opt.map(|payee| first_hop_targets.get(&payee).map(|(first_channels, peer_node_counter)| { + debug_assert_eq!(*peer_node_counter, payee_node_counter); for details in first_channels { let candidate = CandidateRouteHop::FirstHop(CandidateFirstHop { - details, payer_node_id: &our_node_id, + details, payer_node_id: &our_node_id, payer_node_counter, + target_node_counter: payee_node_counter, }); let added = add_entry!(&candidate, 0, path_value_msat, 0, 0u64, 0, 0).is_some(); @@ -2471,28 +2566,41 @@ where L::Target: Logger { // it matters only if the fees are exactly the same. for (hint_idx, hint) in payment_params.payee.blinded_route_hints().iter().enumerate() { let intro_node_id = NodeId::from_pubkey(&hint.1.introduction_node_id); - let have_intro_node_in_graph = + let intro_node_counter_opt = // Only add the hops in this route to our candidate set if either // we have a direct channel to the first hop or the first hop is // in the regular network graph. - first_hop_targets.get(&intro_node_id).is_some() || - network_nodes.get(&intro_node_id).is_some(); - if !have_intro_node_in_graph || our_node_id == intro_node_id { continue } + network_nodes.get(&intro_node_id).map(|node| node.node_counter) + .or( + first_hop_targets.get(&intro_node_id).map(|(_, node_counter)| *node_counter) + ); + if intro_node_counter_opt.is_none() || our_node_id == intro_node_id { continue } let candidate = if hint.1.blinded_hops.len() == 1 { - CandidateRouteHop::OneHopBlinded(CandidateOneHopBlindedPath { hint, hint_idx }) - } else { CandidateRouteHop::Blinded(CandidateBlindedPath { hint, hint_idx }) }; + CandidateRouteHop::OneHopBlinded(CandidateOneHopBlindedPath { + hint, + hint_idx, + source_node_counter: intro_node_counter_opt.unwrap(), + }) + } else { + CandidateRouteHop::Blinded(CandidateBlindedPath { + hint, + hint_idx, + source_node_counter: intro_node_counter_opt.unwrap(), + }) + }; let mut path_contribution_msat = path_value_msat; if let Some(hop_used_msat) = add_entry!(&candidate, 0, path_contribution_msat, 0, 0_u64, 0, 0) { path_contribution_msat = hop_used_msat; } else { continue } - if let Some(first_channels) = first_hop_targets.get_mut(&NodeId::from_pubkey(&hint.1.introduction_node_id)) { + if let Some((first_channels, peer_node_counter)) = first_hop_targets.get_mut(&NodeId::from_pubkey(&hint.1.introduction_node_id)) { sort_first_hop_channels(first_channels, &used_liquidities, recommended_value_msat, our_node_pubkey); for details in first_channels { let first_hop_candidate = CandidateRouteHop::FirstHop(CandidateFirstHop { - details, payer_node_id: &our_node_id, + details, payer_node_id: &our_node_id, payer_node_counter, + target_node_counter: *peer_node_counter, }); let blinded_path_fee = match compute_fees(path_contribution_msat, candidate.fees()) { Some(fee) => fee, @@ -2532,9 +2640,10 @@ where L::Target: Logger { let mut aggregate_path_contribution_msat = path_value_msat; for (idx, (hop, prev_hop_id)) in hop_iter.zip(prev_hop_iter).enumerate() { - let target = private_hop_key_cache.get(&prev_hop_id).unwrap(); + let (target, private_target_node_counter) = private_hop_key_cache.get(&prev_hop_id).unwrap(); + let (_src_id, private_source_node_counter) = private_hop_key_cache.get(&hop.src_node_id).unwrap(); - if let Some(first_channels) = first_hop_targets.get(&target) { + if let Some((first_channels, _)) = first_hop_targets.get(&target) { if first_channels.iter().any(|d| d.outbound_scid_alias == Some(hop.short_channel_id)) { log_trace!(logger, "Ignoring route hint with SCID {} (and any previous) due to it being a direct channel of ours.", hop.short_channel_id); @@ -2548,8 +2657,12 @@ where L::Target: Logger { .map(|(info, _)| CandidateRouteHop::PublicHop(CandidatePublicHop { info, short_channel_id: hop.short_channel_id, - })) - .unwrap_or_else(|| CandidateRouteHop::PrivateHop(CandidatePrivateHop { hint: hop, target_node_id: target })); + }) + .unwrap_or_else(|| CandidateRouteHop::PrivateHop(CandidatePrivateHop { + hint: hop, target_node_id: target, + source_node_counter: *private_source_node_counter, + target_node_counter: *private_target_node_counter, + })); if let Some(hop_used_msat) = add_entry!(&candidate, aggregate_next_hops_fee_msat, aggregate_path_contribution_msat, @@ -2585,12 +2698,13 @@ where L::Target: Logger { .saturating_add(1); // Searching for a direct channel between last checked hop and first_hop_targets - if let Some(first_channels) = first_hop_targets.get_mut(&target) { + if let Some((first_channels, peer_node_counter)) = first_hop_targets.get_mut(&target) { sort_first_hop_channels(first_channels, &used_liquidities, recommended_value_msat, our_node_pubkey); for details in first_channels { let first_hop_candidate = CandidateRouteHop::FirstHop(CandidateFirstHop { - details, payer_node_id: &our_node_id, + details, payer_node_id: &our_node_id, payer_node_counter, + target_node_counter: *peer_node_counter, }); add_entry!(&first_hop_candidate, aggregate_next_hops_fee_msat, aggregate_path_contribution_msat, @@ -2632,12 +2746,13 @@ where L::Target: Logger { // Note that we *must* check if the last hop was added as `add_entry` // always assumes that the third argument is a node to which we have a // path. - if let Some(first_channels) = first_hop_targets.get_mut(&NodeId::from_pubkey(&hop.src_node_id)) { + if let Some((first_channels, peer_node_counter)) = first_hop_targets.get_mut(&NodeId::from_pubkey(&hop.src_node_id)) { sort_first_hop_channels(first_channels, &used_liquidities, recommended_value_msat, our_node_pubkey); for details in first_channels { let first_hop_candidate = CandidateRouteHop::FirstHop(CandidateFirstHop { - details, payer_node_id: &our_node_id, + details, payer_node_id: &our_node_id, payer_node_counter, + target_node_counter: *peer_node_counter, }); add_entry!(&first_hop_candidate, aggregate_next_hops_fee_msat, @@ -2673,13 +2788,15 @@ where L::Target: Logger { // Since we're going payee-to-payer, hitting our node as a target means we should stop // traversing the graph and arrange the path out of what we found. if node_id == our_node_id { - let mut new_entry = dist.remove(&our_node_id).unwrap(); + let mut new_entry = dist[payer_node_counter as usize].take().unwrap(); let mut ordered_hops: Vec<(PathBuildingHop, NodeFeatures)> = vec!((new_entry.clone(), default_node_features.clone())); 'path_walk: loop { let mut features_set = false; - let target = ordered_hops.last().unwrap().0.candidate.target().unwrap_or(maybe_dummy_payee_node_id); - if let Some(first_channels) = first_hop_targets.get(&target) { + let candidate = &ordered_hops.last().unwrap().0.candidate; + let target = candidate.target().unwrap_or(maybe_dummy_payee_node_id); + let target_node_counter = candidate.target_node_counter(); + if let Some((first_channels, _)) = first_hop_targets.get(&target) { for details in first_channels { if let CandidateRouteHop::FirstHop(CandidateFirstHop { details: last_hop_details, .. }) = ordered_hops.last().unwrap().0.candidate @@ -2710,11 +2827,12 @@ where L::Target: Logger { // save this path for the payment route. Also, update the liquidity // remaining on the used hops, so that we take them into account // while looking for more paths. - if target == maybe_dummy_payee_node_id { + if target_node_counter.is_none() { break 'path_walk; } + if target_node_counter == Some(payee_node_counter) { break 'path_walk; } - new_entry = match dist.remove(&target) { + new_entry = match dist[target_node_counter.unwrap() as usize].take() { Some(payment_hop) => payment_hop, // We can't arrive at None because, if we ever add an entry to targets, // we also fill in the entry in dist (see add_entry!).