X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=0910985418ed8b23a958efa5f9056bef8414c3e7;hb=b5827f77ad539ce047e513401f6cabb08576e204;hp=b4e2b138433648d9218ce0e8977cb85f4d9197a8;hpb=d0b8f455fe86d3e55231d35d35dd96693abe2049;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index b4e2b138..09109854 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -13,13 +13,15 @@ use bitcoin::secp256k1::PublicKey; use bitcoin::hashes::Hash; use bitcoin::hashes::sha256::Hash as Sha256; +use crate::blinded_path::BlindedPath; use crate::ln::PaymentHash; use crate::ln::channelmanager::{ChannelDetails, PaymentId}; use crate::ln::features::{ChannelFeatures, InvoiceFeatures, NodeFeatures}; use crate::ln::msgs::{DecodeError, ErrorAction, LightningError, MAX_VALUE_MSAT}; +use crate::offers::invoice::BlindedPayInfo; use crate::routing::gossip::{DirectedChannelInfo, EffectiveCapacity, ReadOnlyNetworkGraph, NetworkGraph, NodeId, RoutingFees}; use crate::routing::scoring::{ChannelUsage, LockableScore, Score}; -use crate::util::ser::{Writeable, Readable, Writer}; +use crate::util::ser::{Writeable, Readable, ReadableArgs, Writer}; use crate::util::logger::{Level, Logger}; use crate::util::chacha20::ChaCha20; @@ -210,7 +212,8 @@ impl Readable for InFlightHtlcs { } } -/// A hop in a route +/// A hop in a route, and additional metadata about it. "Hop" is defined as a node and the channel +/// that leads to it. #[derive(Clone, Debug, Hash, PartialEq, Eq)] pub struct RouteHop { /// The node_id of the node at this hop. @@ -224,11 +227,10 @@ pub struct RouteHop { /// to reach this node. pub channel_features: ChannelFeatures, /// The fee taken on this hop (for paying for the use of the *next* channel in the path). - /// For the last hop, this should be the full value of the payment (might be more than - /// requested if we had to match htlc_minimum_msat). + /// For the last hop, this should be the full value of this path's part of the payment. pub fee_msat: u64, - /// The CLTV delta added for this hop. For the last hop, this should be the full CLTV value - /// expected at the destination, in excess of the current block height. + /// The CLTV delta added for this hop. For the last hop, this is the CLTV delta expected at the + /// destination. pub cltv_expiry_delta: u32, } @@ -245,17 +247,17 @@ impl_writeable_tlv_based!(RouteHop, { /// it can take multiple paths. Each path is composed of one or more hops through the network. #[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 less or equal to 19 should currently ensure it is viable. + /// The list of paths 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, 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, /// provided back to you via [`Event::PaymentPathFailed`]. /// - /// [`Event::PaymentPathFailed`]: crate::util::events::Event::PaymentPathFailed + /// [`Event::PaymentPathFailed`]: crate::events::Event::PaymentPathFailed pub payment_params: Option, } @@ -281,7 +283,8 @@ impl Route { self.paths.iter().map(|path| path.get_path_fees()).sum() } - /// Returns the total amount paid on this [`Route`], excluding the fees. + /// Returns the total amount paid on this [`Route`], excluding the fees. Might be more than + /// requested if we had to reach htlc_minimum_msat. pub fn get_total_amount(&self) -> u64 { return self.paths.iter() .map(|path| path.split_last().map(|(hop, _)| hop.fee_msat).unwrap_or(0)) @@ -313,18 +316,23 @@ impl Readable for Route { fn read(reader: &mut R) -> Result { let _ver = read_ver_prefix!(reader, SERIALIZATION_VERSION); let path_count: u64 = Readable::read(reader)?; + if path_count == 0 { return Err(DecodeError::InvalidValue); } let mut paths = Vec::with_capacity(cmp::min(path_count, 128) as usize); + let mut min_final_cltv_expiry_delta = u32::max_value(); for _ in 0..path_count { let hop_count: u8 = Readable::read(reader)?; - let mut hops = Vec::with_capacity(hop_count as usize); + let mut hops: Vec = Vec::with_capacity(hop_count as usize); for _ in 0..hop_count { hops.push(Readable::read(reader)?); } + if hops.is_empty() { return Err(DecodeError::InvalidValue); } + min_final_cltv_expiry_delta = + cmp::min(min_final_cltv_expiry_delta, hops.last().unwrap().cltv_expiry_delta); paths.push(hops); } let mut payment_params = None; read_tlv_fields!(reader, { - (1, payment_params, option), + (1, payment_params, (option: ReadableArgs, min_final_cltv_expiry_delta)), }); Ok(Route { paths, payment_params }) } @@ -335,7 +343,7 @@ impl Readable for Route { /// Passed to [`find_route`] and [`build_route_from_hops`], but also provided in /// [`Event::PaymentPathFailed`]. /// -/// [`Event::PaymentPathFailed`]: crate::util::events::Event::PaymentPathFailed +/// [`Event::PaymentPathFailed`]: crate::events::Event::PaymentPathFailed #[derive(Clone, Debug, PartialEq, Eq)] pub struct RouteParameters { /// The parameters of the failed payment path. @@ -343,19 +351,38 @@ pub struct RouteParameters { /// The amount in msats sent on the failed payment path. pub final_value_msat: u64, +} - /// The CLTV on the final hop of the failed payment path. - /// - /// This field is deprecated, [`PaymentParameters::final_cltv_expiry_delta`] should be used - /// instead, if available. - pub final_cltv_expiry_delta: u32, +impl Writeable for RouteParameters { + fn write(&self, writer: &mut W) -> Result<(), io::Error> { + write_tlv_fields!(writer, { + (0, self.payment_params, required), + (2, self.final_value_msat, required), + // LDK versions prior to 0.0.114 had the `final_cltv_expiry_delta` parameter in + // `RouteParameters` directly. For compatibility, we write it here. + (4, self.payment_params.final_cltv_expiry_delta, required), + }); + Ok(()) + } } -impl_writeable_tlv_based!(RouteParameters, { - (0, payment_params, required), - (2, final_value_msat, required), - (4, final_cltv_expiry_delta, required), -}); +impl Readable for RouteParameters { + fn read(reader: &mut R) -> Result { + _init_and_read_tlv_fields!(reader, { + (0, payment_params, (required: ReadableArgs, 0)), + (2, final_value_msat, required), + (4, final_cltv_expiry_delta, required), + }); + let mut payment_params: PaymentParameters = payment_params.0.unwrap(); + if payment_params.final_cltv_expiry_delta == 0 { + payment_params.final_cltv_expiry_delta = final_cltv_expiry_delta.0.unwrap(); + } + Ok(Self { + payment_params, + final_value_msat: final_value_msat.0.unwrap(), + }) + } +} /// Maximum total CTLV difference we allow for a full payment path. pub const DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA: u32 = 1008; @@ -396,7 +423,7 @@ pub struct PaymentParameters { pub features: Option, /// Hints for routing to the payee, containing channels connecting the payee to public nodes. - pub route_hints: Vec, + pub route_hints: Hints, /// Expiration of a payment to the payee, in seconds relative to the UNIX epoch. pub expiry_time: Option, @@ -429,23 +456,70 @@ pub struct PaymentParameters { /// these SCIDs. pub previously_failed_channels: Vec, - /// The minimum CLTV delta at the end of the route. - /// - /// This field should always be set to `Some` and may be required in a future release. - pub final_cltv_expiry_delta: Option, + /// The minimum CLTV delta at the end of the route. This value must not be zero. + pub final_cltv_expiry_delta: u32, +} + +impl Writeable for PaymentParameters { + fn write(&self, writer: &mut W) -> Result<(), io::Error> { + let mut clear_hints = &vec![]; + let mut blinded_hints = &vec![]; + match &self.route_hints { + Hints::Clear(hints) => clear_hints = hints, + Hints::Blinded(hints) => blinded_hints = hints, + } + write_tlv_fields!(writer, { + (0, self.payee_pubkey, required), + (1, self.max_total_cltv_expiry_delta, required), + (2, self.features, option), + (3, self.max_path_count, required), + (4, *clear_hints, vec_type), + (5, self.max_channel_saturation_power_of_half, required), + (6, self.expiry_time, option), + (7, self.previously_failed_channels, vec_type), + (8, *blinded_hints, optional_vec), + (9, self.final_cltv_expiry_delta, required), + }); + Ok(()) + } +} + +impl ReadableArgs for PaymentParameters { + fn read(reader: &mut R, default_final_cltv_expiry_delta: u32) -> Result { + _init_and_read_tlv_fields!(reader, { + (0, payee_pubkey, required), + (1, max_total_cltv_expiry_delta, (default_value, DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA)), + (2, features, option), + (3, max_path_count, (default_value, DEFAULT_MAX_PATH_COUNT)), + (4, route_hints, vec_type), + (5, max_channel_saturation_power_of_half, (default_value, 2)), + (6, expiry_time, option), + (7, previously_failed_channels, vec_type), + (8, blinded_route_hints, optional_vec), + (9, final_cltv_expiry_delta, (default_value, default_final_cltv_expiry_delta)), + }); + let clear_route_hints = route_hints.unwrap_or(vec![]); + let blinded_route_hints = blinded_route_hints.unwrap_or(vec![]); + let route_hints = if blinded_route_hints.len() != 0 { + if clear_route_hints.len() != 0 { return Err(DecodeError::InvalidValue) } + Hints::Blinded(blinded_route_hints) + } else { + Hints::Clear(clear_route_hints) + }; + Ok(Self { + payee_pubkey: _init_tlv_based_struct_field!(payee_pubkey, required), + max_total_cltv_expiry_delta: _init_tlv_based_struct_field!(max_total_cltv_expiry_delta, (default_value, unused)), + features, + max_path_count: _init_tlv_based_struct_field!(max_path_count, (default_value, unused)), + route_hints, + max_channel_saturation_power_of_half: _init_tlv_based_struct_field!(max_channel_saturation_power_of_half, (default_value, unused)), + expiry_time, + previously_failed_channels: previously_failed_channels.unwrap_or(Vec::new()), + final_cltv_expiry_delta: _init_tlv_based_struct_field!(final_cltv_expiry_delta, (default_value, unused)), + }) + } } -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_path_count, (default_value, DEFAULT_MAX_PATH_COUNT)), - (4, route_hints, vec_type), - (5, max_channel_saturation_power_of_half, (default_value, 2)), - (6, expiry_time, option), - (7, previously_failed_channels, vec_type), - (9, final_cltv_expiry_delta, option), -}); impl PaymentParameters { /// Creates a payee with the node id of the given `pubkey`. @@ -456,13 +530,13 @@ impl PaymentParameters { Self { payee_pubkey, features: None, - route_hints: vec![], + route_hints: Hints::Clear(vec![]), expiry_time: None, max_total_cltv_expiry_delta: DEFAULT_MAX_TOTAL_CLTV_EXPIRY_DELTA, max_path_count: DEFAULT_MAX_PATH_COUNT, max_channel_saturation_power_of_half: 2, previously_failed_channels: Vec::new(), - final_cltv_expiry_delta: Some(final_cltv_expiry_delta), + final_cltv_expiry_delta, } } @@ -476,47 +550,57 @@ impl PaymentParameters { /// Includes the payee's features. /// - /// (C-not exported) since bindings don't support move semantics + /// This is not exported to bindings users since bindings don't support move semantics pub fn with_features(self, features: InvoiceFeatures) -> Self { Self { features: Some(features), ..self } } /// Includes hints for routing to the payee. /// - /// (C-not exported) since bindings don't support move semantics + /// This is not exported to bindings users since bindings don't support move semantics pub fn with_route_hints(self, route_hints: Vec) -> Self { - Self { route_hints, ..self } + Self { route_hints: Hints::Clear(route_hints), ..self } } /// Includes a payment expiration in seconds relative to the UNIX epoch. /// - /// (C-not exported) since bindings don't support move semantics + /// This is not exported to bindings users since bindings don't support move semantics pub fn with_expiry_time(self, expiry_time: u64) -> Self { Self { expiry_time: Some(expiry_time), ..self } } /// Includes a limit for the total CLTV expiry delta which is considered during routing /// - /// (C-not exported) since bindings don't support move semantics + /// This is not exported to bindings users since bindings don't support move semantics 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. /// - /// (C-not exported) since bindings don't support move semantics + /// This is not exported to bindings users since bindings don't support move semantics pub fn with_max_path_count(self, max_path_count: u8) -> Self { Self { max_path_count, ..self } } /// Includes a limit for the maximum number of payment paths that may be used. /// - /// (C-not exported) since bindings don't support move semantics + /// This is not exported to bindings users since bindings don't support move semantics pub fn with_max_channel_saturation_power_of_half(self, max_channel_saturation_power_of_half: u8) -> Self { Self { max_channel_saturation_power_of_half, ..self } } } +/// Routing hints for the tail of the route. +#[derive(Clone, Debug, Hash, PartialEq, Eq)] +pub enum Hints { + /// The recipient provided blinded paths and payinfo to reach them. The blinded paths themselves + /// will be included in the final [`Route`]. + Blinded(Vec<(BlindedPayInfo, BlindedPath)>), + /// The recipient included these route hints in their BOLT11 invoice. + Clear(Vec), +} + /// A list of hops along a payment path terminating with a channel to the recipient. #[derive(Clone, Debug, Hash, Eq, PartialEq)] pub struct RouteHint(pub Vec); @@ -928,7 +1012,7 @@ fn default_node_features() -> NodeFeatures { /// [`ChannelManager::list_usable_channels`] will never include such channels. /// /// [`ChannelManager::list_usable_channels`]: crate::ln::channelmanager::ChannelManager::list_usable_channels -/// [`Event::PaymentPathFailed`]: crate::util::events::Event::PaymentPathFailed +/// [`Event::PaymentPathFailed`]: crate::events::Event::PaymentPathFailed /// [`NetworkGraph`]: crate::routing::gossip::NetworkGraph pub fn find_route( our_node_pubkey: &PublicKey, route_params: &RouteParameters, @@ -937,9 +1021,7 @@ pub fn find_route( ) -> Result where L::Target: Logger, GL::Target: Logger { let graph_lock = network_graph.read_only(); - let final_cltv_expiry_delta = - if let Some(delta) = route_params.payment_params.final_cltv_expiry_delta { delta } - else { route_params.final_cltv_expiry_delta }; + let final_cltv_expiry_delta = route_params.payment_params.final_cltv_expiry_delta; let mut route = get_route(our_node_pubkey, &route_params.payment_params, &graph_lock, first_hops, route_params.final_value_msat, final_cltv_expiry_delta, logger, scorer, random_seed_bytes)?; @@ -968,19 +1050,25 @@ where L::Target: Logger { return Err(LightningError{err: "Cannot send a payment of 0 msat".to_owned(), action: ErrorAction::IgnoreError}); } - for route in payment_params.route_hints.iter() { - for hop in &route.0 { - if hop.src_node_id == payment_params.payee_pubkey { - return Err(LightningError{err: "Route hint cannot have the payee as the source.".to_owned(), action: ErrorAction::IgnoreError}); + match &payment_params.route_hints { + Hints::Clear(hints) => { + for route in hints.iter() { + for hop in &route.0 { + if hop.src_node_id == payment_params.payee_pubkey { + return Err(LightningError{err: "Route hint cannot have the payee as the source.".to_owned(), action: ErrorAction::IgnoreError}); + } + } } - } + }, + _ => return Err(LightningError{err: "Routing to blinded paths isn't supported yet".to_owned(), action: ErrorAction::IgnoreError}), + } if payment_params.max_total_cltv_expiry_delta <= final_cltv_expiry_delta { return Err(LightningError{err: "Can't find a route where the maximum total CLTV expiry delta is below the final CLTV expiry.".to_owned(), action: ErrorAction::IgnoreError}); } - if let Some(delta) = payment_params.final_cltv_expiry_delta { - debug_assert_eq!(delta, final_cltv_expiry_delta); - } + + // TODO: Remove the explicit final_cltv_expiry_delta parameter + debug_assert_eq!(final_cltv_expiry_delta, payment_params.final_cltv_expiry_delta); // The general routing idea is the following: // 1. Fill first/last hops communicated by the caller. @@ -1498,7 +1586,11 @@ where L::Target: Logger { // If a caller provided us with last hops, add them to routing targets. Since this happens // earlier than general path finding, they will be somewhat prioritized, although currently // it matters only if the fees are exactly the same. - for route in payment_params.route_hints.iter().filter(|route| !route.0.is_empty()) { + let route_hints = match &payment_params.route_hints { + Hints::Clear(hints) => hints, + _ => return Err(LightningError{err: "Routing to blinded paths isn't supported yet".to_owned(), action: ErrorAction::IgnoreError}), + }; + for route in route_hints.iter().filter(|route| !route.0.is_empty()) { let first_hop_in_route = &(route.0)[0]; let have_hop_src_in_graph = // Only add the hops in this route to our candidate set if either @@ -2019,7 +2111,8 @@ where L::Target: Logger, GL::Target: Logger { let graph_lock = network_graph.read_only(); let mut route = build_route_from_hops_internal( our_node_pubkey, hops, &route_params.payment_params, &graph_lock, - route_params.final_value_msat, route_params.final_cltv_expiry_delta, logger, random_seed_bytes)?; + route_params.final_value_msat, route_params.payment_params.final_cltv_expiry_delta, + logger, random_seed_bytes)?; add_random_cltv_offset(&mut route, &route_params.payment_params, &graph_lock, random_seed_bytes); Ok(route) } @@ -2154,6 +2247,7 @@ mod tests { inbound_htlc_minimum_msat: None, inbound_htlc_maximum_msat: None, config: None, + feerate_sat_per_1000_weight: None } } @@ -3256,9 +3350,8 @@ mod tests { let scorer = ln_test_utils::TestScorer::new(); let keys_manager = ln_test_utils::TestKeysInterface::new(&[0u8; 32], Network::Testnet); let random_seed_bytes = keys_manager.get_secure_random_bytes(); - let genesis_hash = genesis_block(Network::Testnet).header.block_hash(); let logger = ln_test_utils::TestLogger::new(); - let network_graph = NetworkGraph::new(genesis_hash, &logger); + let network_graph = NetworkGraph::new(Network::Testnet, &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 @@ -4690,9 +4783,8 @@ 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(ln_test_utils::TestLogger::new()); - let network = Arc::new(NetworkGraph::new(genesis_hash, Arc::clone(&logger))); + let network = Arc::new(NetworkGraph::new(Network::Testnet, 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 = ln_test_utils::TestScorer::new(); @@ -4958,9 +5050,8 @@ 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(ln_test_utils::TestLogger::new()); - let network_graph = NetworkGraph::new(genesis_hash, Arc::clone(&logger)); + let network_graph = NetworkGraph::new(Network::Testnet, Arc::clone(&logger)); let scorer = ln_test_utils::TestScorer::new(); let config = UserConfig::default(); let payment_params = PaymentParameters::from_node_id(nodes[0], 42).with_features(channelmanager::provided_invoice_features(&config)); @@ -5686,6 +5777,7 @@ mod benches { inbound_htlc_minimum_msat: None, inbound_htlc_maximum_msat: None, config: None, + feerate_sat_per_1000_weight: None, } }