X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=8d326b7d7f4f24cfb373f7caa9c146174760f6fd;hb=87c9684c53cadb9d1452ca35460e14ce11fafe48;hp=6584eb5fb55472aad318e4449cd965a6434ebda4;hpb=0a0f87c00f3c5e30965751fb46502ebc1f110333;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index 6584eb5f..8d326b7d 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -12,7 +12,7 @@ //! You probably want to create a NetGraphMsgHandler and use that as your RoutingMessageHandler and then //! interrogate it to get routes for your own payments. -use bitcoin::secp256k1::key::PublicKey; +use bitcoin::secp256k1::PublicKey; use ln::channelmanager::ChannelDetails; use ln::features::{ChannelFeatures, InvoiceFeatures, NodeFeatures}; @@ -65,11 +65,10 @@ impl_writeable_tlv_based!(RouteHop, { #[derive(Clone, Hash, PartialEq, Eq)] pub struct Route { /// The list of routes taken for a single (potentially-)multi-part payment. The pubkey of the - /// last RouteHop in each path must be the same. - /// Each entry represents a list of hops, NOT INCLUDING our own, where the last hop is the - /// destination. Thus, this must always be at least length one. While the maximum length of any - /// given path is variable, keeping the length of any path to less than 20 should currently - /// ensure it is viable. + /// last RouteHop in each path must be the same. Each entry represents a list of hops, NOT + /// INCLUDING our own, where the last hop is the destination. Thus, this must always be at + /// least length one. While the maximum length of any given path is variable, keeping the length + /// of any path less or equal to 19 should currently ensure it is viable. pub paths: Vec>, /// The `payment_params` parameter passed to [`find_route`]. /// This is used by `ChannelManager` to track information which may be required for retries, @@ -177,9 +176,23 @@ 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; -/// The median hop CLTV expiry delta currently seen in the network. +// The median hop CLTV expiry delta currently seen in the network. const MEDIAN_HOP_CLTV_EXPIRY_DELTA: u32 = 40; +// During routing, we only consider paths shorter than our maximum length estimate. +// In the legacy onion format, the maximum number of hops used to be a fixed value of 20. +// However, in the TLV onion format, there is no fixed maximum length, but the `hop_payloads` +// field is always 1300 bytes. As the `tlv_payload` for each hop may vary in length, we have to +// estimate how many hops the route may have so that it actually fits the `hop_payloads` field. +// +// We estimate 3+32 (payload length and HMAC) + 2+8 (amt_to_forward) + 2+4 (outgoing_cltv_value) + +// 2+8 (short_channel_id) = 61 bytes for each intermediate hop and 3+32 +// (payload length and HMAC) + 2+8 (amt_to_forward) + 2+4 (outgoing_cltv_value) + 2+32+8 +// (payment_secret and total_msat) = 93 bytes for the final hop. +// Since the length of the potentially included `payment_metadata` is unknown to us, we round +// down from (1300-93) / 61 = 19.78... to arrive at a conservative estimate of 19. +const MAX_PATH_LENGTH_ESTIMATE: u8 = 19; + /// The recipient of a payment. #[derive(Clone, Debug, Hash, PartialEq, Eq)] pub struct PaymentParameters { @@ -327,6 +340,8 @@ struct RouteGraphNode { /// All penalties incurred from this hop on the way to the destination, as calculated using /// channel scoring. path_penalty_msat: u64, + /// The number of hops walked up to this node. + path_length_to_node: u8, } impl cmp::Ord for RouteGraphNode { @@ -412,7 +427,7 @@ impl<'a> CandidateRouteHop<'a> { fn effective_capacity(&self) -> EffectiveCapacity { match self { CandidateRouteHop::FirstHop { details } => EffectiveCapacity::ExactLiquidity { - liquidity_msat: details.outbound_capacity_msat, + liquidity_msat: details.next_outbound_htlc_limit_msat, }, CandidateRouteHop::PublicHop { info, .. } => info.effective_capacity(), CandidateRouteHop::PrivateHop { .. } => EffectiveCapacity::Infinite, @@ -602,6 +617,17 @@ fn compute_fees(amount_msat: u64, channel_fees: RoutingFees) -> Option { } } +/// The default `features` we assume for a node in a route, when no `features` are known about that +/// specific node. +/// +/// Default features are: +/// * variable_length_onion_optional +fn default_node_features() -> NodeFeatures { + let mut features = NodeFeatures::empty(); + features.set_variable_length_onion_optional(); + features +} + /// Finds a route from us (payer) to the given target node (payee). /// /// If the payee provided features in their invoice, they should be provided via `params.payee`. @@ -785,11 +811,11 @@ where L::Target: Logger { // The main heap containing all candidate next-hops sorted by their score (max(A* 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. - let mut targets = BinaryHeap::new(); + let mut targets: BinaryHeap = BinaryHeap::new(); // Map from node_id to information about the best current path to that node, including feerate // information. - let mut dist = HashMap::with_capacity(network_nodes.len()); + let mut dist: HashMap = HashMap::with_capacity(network_nodes.len()); // 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 @@ -807,7 +833,8 @@ where L::Target: Logger { // We don't want multiple paths (as per MPP) share liquidity of the same channels. // This map allows paths to be aware of the channel use by other paths in the same call. // This would help to make a better path finding decisions and not "overbook" channels. - // It is unaware of the directions (except for `outbound_capacity_msat` in `first_hops`). + // It is unaware of the directions (except for `next_outbound_htlc_limit_msat` in + // `first_hops`). let mut bookkept_channels_liquidity_available_msat = HashMap::with_capacity(network_nodes.len()); // Keeping track of how much value we already collected across other paths. Helps to decide: @@ -830,12 +857,12 @@ where L::Target: Logger { // sort channels above `recommended_value_msat` in ascending order, preferring channels // which have enough, but not too much, capacity for the payment. channels.sort_unstable_by(|chan_a, chan_b| { - if chan_b.outbound_capacity_msat < recommended_value_msat || chan_a.outbound_capacity_msat < recommended_value_msat { + if chan_b.next_outbound_htlc_limit_msat < recommended_value_msat || chan_a.next_outbound_htlc_limit_msat < recommended_value_msat { // Sort in descending order - chan_b.outbound_capacity_msat.cmp(&chan_a.outbound_capacity_msat) + chan_b.next_outbound_htlc_limit_msat.cmp(&chan_a.next_outbound_htlc_limit_msat) } else { // Sort in ascending order - chan_a.outbound_capacity_msat.cmp(&chan_b.outbound_capacity_msat) + chan_a.next_outbound_htlc_limit_msat.cmp(&chan_b.next_outbound_htlc_limit_msat) } }); } @@ -848,8 +875,8 @@ where L::Target: Logger { // since that value has to be transferred over this channel. // Returns whether this channel caused an update to `targets`. ( $candidate: expr, $src_node_id: expr, $dest_node_id: expr, $next_hops_fee_msat: expr, - $next_hops_value_contribution: expr, $next_hops_path_htlc_minimum_msat: expr, - $next_hops_path_penalty_msat: expr, $next_hops_cltv_delta: expr ) => { { + $next_hops_value_contribution: expr, $next_hops_path_htlc_minimum_msat: expr, + $next_hops_path_penalty_msat: expr, $next_hops_cltv_delta: expr, $next_hops_path_length: expr ) => { { // We "return" whether we updated the path at the end, via this: let mut did_add_update_path_to_src_node = false; // Channels to self should not be used. This is more of belt-and-suspenders, because in @@ -893,6 +920,9 @@ where L::Target: Logger { }; // 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. + let path_length_to_node = $next_hops_path_length + 1; + let doesnt_exceed_max_path_length = path_length_to_node <= MAX_PATH_LENGTH_ESTIMATE; // Do not consider candidates that exceed the maximum total cltv expiry limit. // In order to already account for some of the privacy enhancing random CLTV @@ -927,9 +957,11 @@ where L::Target: Logger { // bother considering this channel. If retrying with recommended_value_msat may // allow us to hit the HTLC minimum limit, set htlc_minimum_limit so that we go // around again with a higher amount. - if contributes_sufficient_value && doesnt_exceed_cltv_delta_limit && may_overpay_to_meet_path_minimum_msat { + if contributes_sufficient_value && doesnt_exceed_max_path_length && + doesnt_exceed_cltv_delta_limit && may_overpay_to_meet_path_minimum_msat { hit_minimum_limit = true; - } else if contributes_sufficient_value && doesnt_exceed_cltv_delta_limit && over_path_minimum_msat { + } else if contributes_sufficient_value && doesnt_exceed_max_path_length && + doesnt_exceed_cltv_delta_limit && over_path_minimum_msat { // Note that low contribution here (limited by available_liquidity_msat) // might violate htlc_minimum_msat on the hops which are next along the // payment path (upstream to the payee). To avoid that, we recompute @@ -1026,6 +1058,7 @@ where L::Target: Logger { value_contribution_msat: value_contribution_msat, path_htlc_minimum_msat, path_penalty_msat, + path_length_to_node, }; // Update the way of reaching $src_node_id with the given short_channel_id (from $dest_node_id), @@ -1101,14 +1134,17 @@ where L::Target: Logger { } } } - let empty_node_features = NodeFeatures::empty(); + let default_node_features = default_node_features(); + // Find ways (channels with destination) to reach a given node and store them // in the corresponding data structures (routing graph etc). // $fee_to_target_msat represents how much it costs to reach to this node from the payee, // meaning how much will be paid in fees after this node (to the best of our knowledge). // This data can later be helpful to optimize routing (pay lower fees). macro_rules! add_entries_to_cheapest_to_target_node { - ( $node: expr, $node_id: expr, $fee_to_target_msat: expr, $next_hops_value_contribution: expr, $next_hops_path_htlc_minimum_msat: expr, $next_hops_path_penalty_msat: expr, $next_hops_cltv_delta: expr ) => { + ( $node: expr, $node_id: expr, $fee_to_target_msat: expr, $next_hops_value_contribution: expr, + $next_hops_path_htlc_minimum_msat: expr, $next_hops_path_penalty_msat: expr, + $next_hops_cltv_delta: expr, $next_hops_path_length: expr ) => { let skip_node = if let Some(elem) = dist.get_mut(&$node_id) { let was_processed = elem.was_processed; elem.was_processed = true; @@ -1125,14 +1161,17 @@ where L::Target: Logger { if let Some(first_channels) = first_hop_targets.get(&$node_id) { for details in first_channels { let candidate = CandidateRouteHop::FirstHop { details }; - add_entry!(candidate, our_node_id, $node_id, $fee_to_target_msat, $next_hops_value_contribution, $next_hops_path_htlc_minimum_msat, $next_hops_path_penalty_msat, $next_hops_cltv_delta); + add_entry!(candidate, our_node_id, $node_id, $fee_to_target_msat, + $next_hops_value_contribution, + $next_hops_path_htlc_minimum_msat, $next_hops_path_penalty_msat, + $next_hops_cltv_delta, $next_hops_path_length); } } let features = if let Some(node_info) = $node.announcement_info.as_ref() { &node_info.features } else { - &empty_node_features + &default_node_features }; if !features.requires_unknown_bits() { @@ -1148,7 +1187,12 @@ where L::Target: Logger { info: directed_channel.with_update().unwrap(), short_channel_id: *chan_id, }; - add_entry!(candidate, *source, $node_id, $fee_to_target_msat, $next_hops_value_contribution, $next_hops_path_htlc_minimum_msat, $next_hops_path_penalty_msat, $next_hops_cltv_delta); + add_entry!(candidate, *source, $node_id, + $fee_to_target_msat, + $next_hops_value_contribution, + $next_hops_path_htlc_minimum_msat, + $next_hops_path_penalty_msat, + $next_hops_cltv_delta, $next_hops_path_length); } } } @@ -1175,8 +1219,10 @@ where L::Target: Logger { if let Some(first_channels) = first_hop_targets.get(&payee_node_id) { for details in first_channels { let candidate = CandidateRouteHop::FirstHop { details }; - let added = add_entry!(candidate, our_node_id, payee_node_id, 0, path_value_msat, 0, 0u64, 0); - log_trace!(logger, "{} direct route to payee via SCID {}", if added { "Added" } else { "Skipped" }, candidate.short_channel_id()); + let added = add_entry!(candidate, our_node_id, payee_node_id, 0, path_value_msat, + 0, 0u64, 0, 0); + log_trace!(logger, "{} direct route to payee via SCID {}", + if added { "Added" } else { "Skipped" }, candidate.short_channel_id()); } } @@ -1189,7 +1235,7 @@ where L::Target: Logger { // If not, targets.pop() will not even let us enter the loop in step 2. None => {}, Some(node) => { - add_entries_to_cheapest_to_target_node!(node, payee_node_id, 0, path_value_msat, 0, 0u64, 0); + add_entries_to_cheapest_to_target_node!(node, payee_node_id, 0, path_value_msat, 0, 0u64, 0, 0); }, } @@ -1216,6 +1262,7 @@ where L::Target: Logger { let mut aggregate_next_hops_path_htlc_minimum_msat: u64 = 0; let mut aggregate_next_hops_path_penalty_msat: u64 = 0; let mut aggregate_next_hops_cltv_delta: u32 = 0; + let mut aggregate_next_hops_path_length: u8 = 0; for (idx, (hop, prev_hop_id)) in hop_iter.zip(prev_hop_iter).enumerate() { let source = NodeId::from_pubkey(&hop.src_node_id); @@ -1231,15 +1278,22 @@ where L::Target: Logger { .unwrap_or_else(|| CandidateRouteHop::PrivateHop { hint: hop }); let capacity_msat = candidate.effective_capacity().as_msat(); aggregate_next_hops_path_penalty_msat = aggregate_next_hops_path_penalty_msat - .saturating_add(scorer.channel_penalty_msat(hop.short_channel_id, final_value_msat, capacity_msat, &source, &target)); + .saturating_add(scorer.channel_penalty_msat(hop.short_channel_id, + final_value_msat, capacity_msat, &source, &target)); aggregate_next_hops_cltv_delta = aggregate_next_hops_cltv_delta .saturating_add(hop.cltv_expiry_delta as u32); - if !add_entry!(candidate, source, target, aggregate_next_hops_fee_msat, path_value_msat, aggregate_next_hops_path_htlc_minimum_msat, aggregate_next_hops_path_penalty_msat, aggregate_next_hops_cltv_delta) { - // If this hop was not used then there is no use checking the preceding hops - // in the RouteHint. We can break by just searching for a direct channel between - // last checked hop and first_hop_targets + aggregate_next_hops_path_length = aggregate_next_hops_path_length + .saturating_add(1); + + if !add_entry!(candidate, source, target, aggregate_next_hops_fee_msat, + path_value_msat, aggregate_next_hops_path_htlc_minimum_msat, + aggregate_next_hops_path_penalty_msat, + aggregate_next_hops_cltv_delta, aggregate_next_hops_path_length) { + // If this hop was not used then there is no use checking the preceding + // hops in the RouteHint. We can break by just searching for a direct + // channel between last checked hop and first_hop_targets. hop_used = false; } @@ -1247,7 +1301,11 @@ where L::Target: Logger { if let Some(first_channels) = first_hop_targets.get(&NodeId::from_pubkey(&prev_hop_id)) { for details in first_channels { let candidate = CandidateRouteHop::FirstHop { details }; - add_entry!(candidate, our_node_id, NodeId::from_pubkey(&prev_hop_id), aggregate_next_hops_fee_msat, path_value_msat, aggregate_next_hops_path_htlc_minimum_msat, aggregate_next_hops_path_penalty_msat, aggregate_next_hops_cltv_delta); + add_entry!(candidate, our_node_id, NodeId::from_pubkey(&prev_hop_id), + aggregate_next_hops_fee_msat, path_value_msat, + aggregate_next_hops_path_htlc_minimum_msat, + aggregate_next_hops_path_penalty_msat, aggregate_next_hops_cltv_delta, + aggregate_next_hops_path_length); } } @@ -1258,7 +1316,7 @@ where L::Target: Logger { // In the next values of the iterator, the aggregate fees already reflects // the sum of value sent from payer (final_value_msat) and routing fees // for the last node in the RouteHint. We need to just add the fees to - // route through the current node so that the preceeding node (next iteration) + // route through the current node so that the preceding node (next iteration) // can use it. let hops_fee = compute_fees(aggregate_next_hops_fee_msat + final_value_msat, hop.fees) .map_or(None, |inc| inc.checked_add(aggregate_next_hops_fee_msat)); @@ -1283,7 +1341,13 @@ where L::Target: Logger { if let Some(first_channels) = first_hop_targets.get(&NodeId::from_pubkey(&hop.src_node_id)) { for details in first_channels { let candidate = CandidateRouteHop::FirstHop { details }; - add_entry!(candidate, our_node_id, NodeId::from_pubkey(&hop.src_node_id), aggregate_next_hops_fee_msat, path_value_msat, aggregate_next_hops_path_htlc_minimum_msat, aggregate_next_hops_path_penalty_msat, aggregate_next_hops_cltv_delta); + add_entry!(candidate, our_node_id, + NodeId::from_pubkey(&hop.src_node_id), + aggregate_next_hops_fee_msat, path_value_msat, + aggregate_next_hops_path_htlc_minimum_msat, + aggregate_next_hops_path_penalty_msat, + aggregate_next_hops_cltv_delta, + aggregate_next_hops_path_length); } } } @@ -1306,13 +1370,13 @@ where L::Target: Logger { // Both these cases (and other cases except reaching recommended_value_msat) mean that // paths_collection will be stopped because found_new_path==false. // This is not necessarily a routing failure. - 'path_construction: while let Some(RouteGraphNode { node_id, lowest_fee_to_node, total_cltv_delta, value_contribution_msat, path_htlc_minimum_msat, path_penalty_msat, .. }) = targets.pop() { + 'path_construction: while let Some(RouteGraphNode { node_id, lowest_fee_to_node, total_cltv_delta, value_contribution_msat, path_htlc_minimum_msat, path_penalty_msat, path_length_to_node, .. }) = targets.pop() { // 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 ordered_hops = vec!((new_entry.clone(), NodeFeatures::empty())); + let mut ordered_hops: Vec<(PathBuildingHop, NodeFeatures)> = vec!((new_entry.clone(), default_node_features.clone())); 'path_walk: loop { let mut features_set = false; @@ -1330,7 +1394,7 @@ where L::Target: Logger { if let Some(node_info) = node.announcement_info.as_ref() { ordered_hops.last_mut().unwrap().1 = node_info.features.clone(); } else { - ordered_hops.last_mut().unwrap().1 = NodeFeatures::empty(); + ordered_hops.last_mut().unwrap().1 = default_node_features.clone(); } } else { // We can fill in features for everything except hops which were @@ -1357,7 +1421,7 @@ where L::Target: Logger { // so that fees paid for a HTLC forwarding on the current channel are // associated with the previous channel (where they will be subtracted). ordered_hops.last_mut().unwrap().0.fee_msat = new_entry.hop_use_fee_msat; - ordered_hops.push((new_entry.clone(), NodeFeatures::empty())); + ordered_hops.push((new_entry.clone(), default_node_features.clone())); } ordered_hops.last_mut().unwrap().0.fee_msat = value_contribution_msat; ordered_hops.last_mut().unwrap().0.hop_use_fee_msat = 0; @@ -1428,7 +1492,9 @@ where L::Target: Logger { match network_nodes.get(&node_id) { None => {}, Some(node) => { - add_entries_to_cheapest_to_target_node!(node, node_id, lowest_fee_to_node, value_contribution_msat, path_htlc_minimum_msat, path_penalty_msat, total_cltv_delta); + add_entries_to_cheapest_to_target_node!(node, node_id, lowest_fee_to_node, + value_contribution_msat, path_htlc_minimum_msat, path_penalty_msat, + total_cltv_delta, path_length_to_node); }, } } @@ -1684,13 +1750,15 @@ fn add_random_cltv_offset(route: &mut Route, payment_params: &PaymentParameters, #[cfg(test)] mod tests { use routing::network_graph::{NetworkGraph, NetGraphMsgHandler, NodeId}; - use routing::router::{get_route, add_random_cltv_offset, PaymentParameters, Route, RouteHint, RouteHintHop, RouteHop, RoutingFees, DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA}; + use routing::router::{get_route, add_random_cltv_offset, default_node_features, + PaymentParameters, Route, RouteHint, RouteHintHop, RouteHop, RoutingFees, + DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA, MAX_PATH_LENGTH_ESTIMATE}; use routing::scoring::Score; use chain::transaction::OutPoint; use chain::keysinterface::KeysInterface; use ln::features::{ChannelFeatures, InitFeatures, InvoiceFeatures, NodeFeatures}; use ln::msgs::{ErrorAction, LightningError, OptionalField, UnsignedChannelAnnouncement, ChannelAnnouncement, RoutingMessageHandler, - NodeAnnouncement, UnsignedNodeAnnouncement, ChannelUpdate, UnsignedChannelUpdate}; + NodeAnnouncement, UnsignedNodeAnnouncement, ChannelUpdate, UnsignedChannelUpdate}; use ln::channelmanager; use util::test_utils; use util::chacha20::ChaCha20; @@ -1708,7 +1776,7 @@ mod tests { use hex; - use bitcoin::secp256k1::key::{PublicKey,SecretKey}; + use bitcoin::secp256k1::{PublicKey,SecretKey}; use bitcoin::secp256k1::{Secp256k1, All}; use prelude::*; @@ -1723,6 +1791,8 @@ mod tests { node_id, unspendable_punishment_reserve: 0, forwarding_info: None, + outbound_htlc_minimum_msat: None, + outbound_htlc_maximum_msat: None, }, funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }), channel_type: None, @@ -1732,12 +1802,15 @@ mod tests { user_channel_id: 0, balance_msat: 0, outbound_capacity_msat, + next_outbound_htlc_limit_msat: outbound_capacity_msat, inbound_capacity_msat: 42, unspendable_punishment_reserve: None, confirmations_required: None, force_close_spend_delay: None, is_outbound: true, is_funding_locked: true, is_usable: true, is_public: true, + inbound_htlc_minimum_msat: None, + inbound_htlc_maximum_msat: None, } } @@ -1762,10 +1835,10 @@ mod tests { let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]); let valid_announcement = ChannelAnnouncement { - node_signature_1: secp_ctx.sign(&msghash, node_1_privkey), - node_signature_2: secp_ctx.sign(&msghash, node_2_privkey), - bitcoin_signature_1: secp_ctx.sign(&msghash, node_1_privkey), - bitcoin_signature_2: secp_ctx.sign(&msghash, node_2_privkey), + node_signature_1: secp_ctx.sign_ecdsa(&msghash, node_1_privkey), + node_signature_2: secp_ctx.sign_ecdsa(&msghash, node_2_privkey), + bitcoin_signature_1: secp_ctx.sign_ecdsa(&msghash, node_1_privkey), + bitcoin_signature_2: secp_ctx.sign_ecdsa(&msghash, node_2_privkey), contents: unsigned_announcement.clone(), }; match net_graph_msg_handler.handle_channel_announcement(&valid_announcement) { @@ -1780,7 +1853,7 @@ mod tests { ) { let msghash = hash_to_message!(&Sha256dHash::hash(&update.encode()[..])[..]); let valid_channel_update = ChannelUpdate { - signature: secp_ctx.sign(&msghash, node_privkey), + signature: secp_ctx.sign_ecdsa(&msghash, node_privkey), contents: update.clone() }; @@ -1807,7 +1880,7 @@ mod tests { }; let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]); let valid_announcement = NodeAnnouncement { - signature: secp_ctx.sign(&msghash, node_privkey), + signature: secp_ctx.sign_ecdsa(&msghash, node_privkey), contents: unsigned_announcement.clone() }; @@ -1818,7 +1891,7 @@ mod tests { } fn get_nodes(secp_ctx: &Secp256k1) -> (SecretKey, PublicKey, Vec, Vec) { - let privkeys: Vec = (2..10).map(|i| { + let privkeys: Vec = (2..22).map(|i| { SecretKey::from_slice(&hex::decode(format!("{:02x}", i).repeat(32)).unwrap()[..]).unwrap() }).collect(); @@ -1845,6 +1918,57 @@ mod tests { } } + fn build_line_graph() -> ( + Secp256k1, sync::Arc, NetGraphMsgHandler, + 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 net_graph_msg_handler = NetGraphMsgHandler::new(Arc::clone(&network_graph), None, Arc::clone(&logger)); + + // Build network from our_id to node 19: + // our_id -1(1)2- node0 -1(2)2- node1 - ... - node19 + let (our_privkey, _, privkeys, _) = get_nodes(&secp_ctx); + + for (idx, (cur_privkey, next_privkey)) in core::iter::once(&our_privkey) + .chain(privkeys.iter()).zip(privkeys.iter()).enumerate() { + let cur_short_channel_id = (idx as u64) + 1; + add_channel(&net_graph_msg_handler, &secp_ctx, &cur_privkey, &next_privkey, + ChannelFeatures::from_le_bytes(id_to_feature_flags(1)), cur_short_channel_id); + update_channel(&net_graph_msg_handler, &secp_ctx, &cur_privkey, UnsignedChannelUpdate { + chain_hash: genesis_block(Network::Testnet).header.block_hash(), + short_channel_id: cur_short_channel_id, + timestamp: idx as u32, + flags: 0, + 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, &next_privkey, UnsignedChannelUpdate { + chain_hash: genesis_block(Network::Testnet).header.block_hash(), + short_channel_id: cur_short_channel_id, + timestamp: (idx as u32)+1, + flags: 1, + 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() + }); + add_or_update_node(&net_graph_msg_handler, &secp_ctx, next_privkey, + NodeFeatures::from_le_bytes(id_to_feature_flags(1)), 0); + } + + (secp_ctx, network_graph, net_graph_msg_handler, chain_monitor, logger) + } + fn build_graph() -> ( Secp256k1, sync::Arc, @@ -2785,7 +2909,7 @@ mod tests { assert_eq!(route.paths[0][4].short_channel_id, 8); assert_eq!(route.paths[0][4].fee_msat, 100); assert_eq!(route.paths[0][4].cltv_expiry_delta, 42); - assert_eq!(route.paths[0][4].node_features.le_flags(), &Vec::::new()); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][4].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly } @@ -2861,7 +2985,7 @@ mod tests { assert_eq!(route.paths[0][4].short_channel_id, 8); assert_eq!(route.paths[0][4].fee_msat, 100); assert_eq!(route.paths[0][4].cltv_expiry_delta, 42); - assert_eq!(route.paths[0][4].node_features.le_flags(), &Vec::::new()); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][4].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly } @@ -2958,7 +3082,7 @@ mod tests { 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].node_features.le_flags(), default_node_features().le_flags()); // 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 } @@ -3023,14 +3147,14 @@ mod tests { 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].node_features.le_flags(), default_node_features().le_flags()); // 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 + assert_eq!(route.paths[0][3].node_features.le_flags(), default_node_features().le_flags()); // 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 } @@ -3121,7 +3245,7 @@ mod tests { assert_eq!(route.paths[0][4].short_channel_id, 8); assert_eq!(route.paths[0][4].fee_msat, 100); assert_eq!(route.paths[0][4].cltv_expiry_delta, 42); - assert_eq!(route.paths[0][4].node_features.le_flags(), &Vec::::new()); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][4].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly } @@ -3151,7 +3275,7 @@ mod tests { assert_eq!(route.paths[0][1].short_channel_id, 8); assert_eq!(route.paths[0][1].fee_msat, 100); assert_eq!(route.paths[0][1].cltv_expiry_delta, 42); - assert_eq!(route.paths[0][1].node_features.le_flags(), &Vec::::new()); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][1].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet assert_eq!(route.paths[0][1].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly last_hops[0].0[0].fees.base_msat = 1000; @@ -3188,7 +3312,7 @@ mod tests { assert_eq!(route.paths[0][3].short_channel_id, 10); 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].node_features.le_flags(), default_node_features().le_flags()); // 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 // ...but still use 8 for larger payments as 6 has a variable feerate @@ -3229,7 +3353,7 @@ mod tests { assert_eq!(route.paths[0][4].short_channel_id, 8); assert_eq!(route.paths[0][4].fee_msat, 2000); assert_eq!(route.paths[0][4].cltv_expiry_delta, 42); - assert_eq!(route.paths[0][4].node_features.le_flags(), &Vec::::new()); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][4].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::::new()); // We can't learn any flags from invoices, sadly } @@ -3281,7 +3405,7 @@ mod tests { assert_eq!(route.paths[0][1].short_channel_id, 8); assert_eq!(route.paths[0][1].fee_msat, 1000000); assert_eq!(route.paths[0][1].cltv_expiry_delta, 42); - assert_eq!(route.paths[0][1].node_features.le_flags(), &[0; 0]); // We dont pass flags in from invoices yet + assert_eq!(route.paths[0][1].node_features.le_flags(), default_node_features().le_flags()); // We dont pass flags in from invoices yet assert_eq!(route.paths[0][1].channel_features.le_flags(), &[0; 0]); // We can't learn any flags from invoices, sadly } @@ -3391,7 +3515,7 @@ mod tests { assert_eq!(path.last().unwrap().fee_msat, 250_000_000); } - // Check that setting outbound_capacity_msat in first_hops limits the channels. + // Check that setting next_outbound_htlc_limit_msat in first_hops limits the channels. // Disable channel #1 and use another first hop. update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate { chain_hash: genesis_block(Network::Testnet).header.block_hash(), @@ -3406,7 +3530,7 @@ mod tests { excess_data: Vec::new() }); - // Now, limit the first_hop by the outbound_capacity_msat of 200_000 sats. + // Now, limit the first_hop by the next_outbound_htlc_limit_msat of 200_000 sats. let our_chans = vec![get_channel_details(Some(42), nodes[0].clone(), InitFeatures::from_le_bytes(vec![0b11]), 200_000_000)]; { @@ -5195,6 +5319,35 @@ mod tests { } } + #[test] + fn limits_path_length() { + let (secp_ctx, network, _, _, logger) = build_line_graph(); + let (_, our_id, _, nodes) = get_nodes(&secp_ctx); + let network_graph = network.read_only(); + + 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(); + + // First check we can actually create a long route on this graph. + let feasible_payment_params = PaymentParameters::from_node_id(nodes[18]); + let route = get_route(&our_id, &feasible_payment_params, &network_graph, None, 100, 0, + Arc::clone(&logger), &scorer, &random_seed_bytes).unwrap(); + let path = route.paths[0].iter().map(|hop| hop.short_channel_id).collect::>(); + assert!(path.len() == MAX_PATH_LENGTH_ESTIMATE.into()); + + // But we can't create a path surpassing the MAX_PATH_LENGTH_ESTIMATE limit. + let fail_payment_params = PaymentParameters::from_node_id(nodes[19]); + match get_route(&our_id, &fail_payment_params, &network_graph, None, 100, 0, + Arc::clone(&logger), &scorer, &random_seed_bytes) + { + Err(LightningError { err, .. } ) => { + assert_eq!(err, "Failed to find a path to the given destination"); + }, + Ok(_) => panic!("Expected error"), + } + } + #[test] fn adds_and_limits_cltv_offset() { let (secp_ctx, network_graph, _, _, logger) = build_graph(); @@ -5334,8 +5487,9 @@ mod tests { let payment_params = PaymentParameters::from_node_id(dst); let amt = seed as u64 % 200_000_000; let params = ProbabilisticScoringParameters::default(); - let scorer = ProbabilisticScorer::new(params, &graph); - if get_route(src, &payment_params, &graph.read_only(), None, amt, 42, &test_utils::TestLogger::new(), &scorer, &random_seed_bytes).is_ok() { + 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; } } @@ -5370,8 +5524,9 @@ 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 scorer = ProbabilisticScorer::new(params, &graph); - if get_route(src, &payment_params, &graph.read_only(), None, amt, 42, &test_utils::TestLogger::new(), &scorer, &random_seed_bytes).is_ok() { + 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; } } @@ -5417,6 +5572,7 @@ mod benches { use ln::features::{InitFeatures, InvoiceFeatures}; use routing::scoring::{FixedPenaltyScorer, ProbabilisticScorer, ProbabilisticScoringParameters, Scorer}; use util::logger::{Logger, Record}; + use util::test_utils::TestLogger; use test::Bencher; @@ -5444,6 +5600,8 @@ mod benches { node_id, unspendable_punishment_reserve: 0, forwarding_info: None, + outbound_htlc_minimum_msat: None, + outbound_htlc_maximum_msat: None, }, funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 @@ -5455,6 +5613,7 @@ mod benches { user_channel_id: 0, balance_msat: 10_000_000, outbound_capacity_msat: 10_000_000, + next_outbound_htlc_limit_msat: 10_000_000, inbound_capacity_msat: 0, unspendable_punishment_reserve: None, confirmations_required: None, @@ -5463,6 +5622,8 @@ mod benches { is_funding_locked: true, is_usable: true, is_public: true, + inbound_htlc_minimum_msat: None, + inbound_htlc_maximum_msat: None, } } @@ -5496,17 +5657,19 @@ mod benches { #[bench] fn generate_routes_with_probabilistic_scorer(bench: &mut Bencher) { + let logger = TestLogger::new(); let network_graph = read_network_graph(); let params = ProbabilisticScoringParameters::default(); - let scorer = ProbabilisticScorer::new(params, &network_graph); + let scorer = ProbabilisticScorer::new(params, &network_graph, &logger); generate_routes(bench, &network_graph, scorer, InvoiceFeatures::empty()); } #[bench] fn generate_mpp_routes_with_probabilistic_scorer(bench: &mut Bencher) { + let logger = TestLogger::new(); let network_graph = read_network_graph(); let params = ProbabilisticScoringParameters::default(); - let scorer = ProbabilisticScorer::new(params, &network_graph); + let scorer = ProbabilisticScorer::new(params, &network_graph, &logger); generate_routes(bench, &network_graph, scorer, InvoiceFeatures::known()); }