use prelude::*;
use alloc::collections::BinaryHeap;
use core::cmp;
-use std::collections::HashMap;
use core::ops::Deref;
/// A hop in a route
}
impl_writeable_tlv_based!(RouteHop, {
- (0, pubkey),
- (2, node_features),
- (4, short_channel_id),
- (6, channel_features),
- (8, fee_msat),
- (10, cltv_expiry_delta),
-}, {}, {});
+ (0, pubkey, required),
+ (2, node_features, required),
+ (4, short_channel_id, required),
+ (6, channel_features, required),
+ (8, fee_msat, required),
+ (10, cltv_expiry_delta, required),
+});
/// A route directs a payment from the sender (us) to the recipient. If the recipient supports MPP,
/// it can take multiple paths. Each path is composed of one or more hops through the network.
hop.write(writer)?;
}
}
- write_tlv_fields!(writer, {}, {});
+ write_tlv_fields!(writer, {});
Ok(())
}
}
}
paths.push(hops);
}
- read_tlv_fields!(reader, {}, {});
+ read_tlv_fields!(reader, {});
Ok(Route { paths })
}
}
/// 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)]
+#[derive(Clone, Debug)]
struct PathBuildingHop<'a> {
// The RouteHintHop fields which will eventually be used if this hop is used in a final Route.
// Note that node_features is calculated separately after our initial graph walk.
}
}
+/// Gets a keysend route from us (payer) to the given target node (payee). This is needed because
+/// keysend payments do not have an invoice from which to pull the payee's supported features, which
+/// makes it tricky to otherwise supply the `payee_features` parameter of `get_route`.
+pub fn get_keysend_route<L: Deref>(our_node_id: &PublicKey, network: &NetworkGraph, payee:
+ &PublicKey, first_hops: Option<&[&ChannelDetails]>, last_hops: &[&RouteHint],
+ final_value_msat: u64, final_cltv: u32, logger: L) -> Result<Route,
+ LightningError> where L::Target: Logger {
+ let invoice_features = InvoiceFeatures::for_keysend();
+ get_route(our_node_id, network, payee, Some(invoice_features), first_hops, last_hops,
+ final_value_msat, final_cltv, logger)
+}
+
/// Gets a route from us (payer) to the given target node (payee).
///
/// If the payee provided features in their invoice, they should be provided via payee_features.
if let Some(hops) = first_hops {
for chan in hops {
let short_channel_id = chan.short_channel_id.expect("first_hops should be filled in with usable channels, not pending ones");
- if chan.remote_network_id == *our_node_id {
+ if chan.counterparty.node_id == *our_node_id {
return Err(LightningError{err: "First hop cannot have our_node_id as a destination.".to_owned(), action: ErrorAction::IgnoreError});
}
- first_hop_targets.insert(chan.remote_network_id, (short_channel_id, chan.counterparty_features.to_context(), chan.outbound_capacity_msat, chan.counterparty_features.to_context()));
+ first_hop_targets.insert(chan.counterparty.node_id, (short_channel_id, chan.counterparty.features.to_context(), chan.outbound_capacity_msat, chan.counterparty.features.to_context()));
}
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});
// - when we want to stop looking for new paths.
let mut already_collected_value_msat = 0;
+ log_trace!(logger, "Building path from {} (payee) to {} (us/payer) for value {} msat.", payee, our_node_id, final_value_msat);
+
macro_rules! add_entry {
// Adds entry which goes from $src_node_id to $dest_node_id
// over the channel with id $chan_id with fees described in
htlc_maximum_msat: hop.htlc_maximum_msat,
fees: hop.fees,
};
- if add_entry!(hop.short_channel_id, hop.src_node_id, payee, directional_info, None::<u64>, &empty_channel_features, 0, path_value_msat, 0) {
+ // We assume that the recipient only included route hints for routes which had
+ // sufficient value to route `final_value_msat`. Note that in the case of "0-value"
+ // invoices where the invoice does not specify value this may not be the case, but
+ // better to include the hints than not.
+ if add_entry!(hop.short_channel_id, hop.src_node_id, payee, directional_info, Some((final_value_msat + 999) / 1000), &empty_channel_features, 0, path_value_msat, 0) {
// If this hop connects to a node with which we have a direct channel,
// ignore the network graph and, if the last hop was added, add our
// direct channel to the candidate set.
}
}
+ log_trace!(logger, "Starting main path collection loop with {} nodes pre-filled from first/last hops.", targets.len());
+
// At this point, targets are filled with the data from first and
// last hops communicated by the caller, and the payment receiver.
let mut found_new_path = false;
ordered_hops.last_mut().unwrap().0.hop_use_fee_msat = 0;
ordered_hops.last_mut().unwrap().0.cltv_expiry_delta = final_cltv;
+ 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);
+
let mut payment_path = PaymentPath {hops: ordered_hops};
// We could have possibly constructed a slightly inconsistent path: since we reduce
// If we weren't capped by hitting a liquidity limit on a channel in the path,
// we'll probably end up picking the same path again on the next iteration.
// Decrease the available liquidity of a hop in the middle of the path.
- let victim_liquidity = bookkeeped_channels_liquidity_available_msat.get_mut(
- &payment_path.hops[(payment_path.hops.len() - 1) / 2].0.short_channel_id).unwrap();
+ let victim_scid = payment_path.hops[(payment_path.hops.len() - 1) / 2].0.short_channel_id;
+ log_trace!(logger, "Disabling channel {} for future path building iterations to avoid duplicates.", victim_scid);
+ let victim_liquidity = bookkeeped_channels_liquidity_available_msat.get_mut(&victim_scid).unwrap();
*victim_liquidity = 0;
}
// In the latter case, making another path finding attempt won't help,
// because we deterministically terminated the search due to low liquidity.
if already_collected_value_msat >= recommended_value_msat || !found_new_path {
+ log_trace!(logger, "Have now collected {} msat (seeking {} msat) in paths. Last path loop {} a new path.",
+ already_collected_value_msat, recommended_value_msat, if found_new_path { "found" } else { "did not find" });
break 'paths_collection;
} else if found_new_path && already_collected_value_msat == final_value_msat && payment_paths.len() == 1 {
// Further, if this was our first walk of the graph, and we weren't limited by an
// potentially allowing us to pay fees to meet the htlc_minimum on the new path while
// still keeping a lower total fee than this path.
if !hit_minimum_limit {
+ log_trace!(logger, "Collected exactly our payment amount on the first pass, without hitting an htlc_minimum_msat limit, exiting.");
break 'paths_collection;
}
+ log_trace!(logger, "Collected our payment amount on the first pass, but running again to collect extra paths with a potentially higher limit.");
path_value_msat = recommended_value_msat;
}
}
}
let route = Route { paths: selected_paths };
- log_trace!(logger, "Got route: {}", log_route!(route));
+ log_info!(logger, "Got route to {}: {}", payee, log_route!(route));
Ok(route)
}
use bitcoin::secp256k1::{Secp256k1, All};
use prelude::*;
- use std::sync::Arc;
+ use sync::{self, Arc};
+
+ fn get_channel_details(short_channel_id: Option<u64>, node_id: PublicKey,
+ features: InitFeatures, outbound_capacity_msat: u64) -> channelmanager::ChannelDetails {
+ channelmanager::ChannelDetails {
+ channel_id: [0; 32],
+ counterparty: channelmanager::ChannelCounterparty {
+ features,
+ node_id,
+ unspendable_punishment_reserve: 0,
+ forwarding_info: None,
+ },
+ funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
+ short_channel_id,
+ channel_value_satoshis: 0,
+ user_id: 0,
+ 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,
+ }
+ }
// Using the same keys for LN and BTC ids
fn add_channel(net_graph_msg_handler: &NetGraphMsgHandler<Arc<test_utils::TestChainSource>, Arc<test_utils::TestLogger>>, secp_ctx: &Secp256k1<All>, node_1_privkey: &SecretKey,
}
}
- fn build_graph() -> (Secp256k1<All>, NetGraphMsgHandler<std::sync::Arc<test_utils::TestChainSource>, std::sync::Arc<crate::util::test_utils::TestLogger>>, std::sync::Arc<test_utils::TestChainSource>, std::sync::Arc<test_utils::TestLogger>) {
+ fn build_graph() -> (Secp256k1<All>, NetGraphMsgHandler<sync::Arc<test_utils::TestChainSource>, sync::Arc<crate::util::test_utils::TestLogger>>, sync::Arc<test_utils::TestChainSource>, sync::Arc<test_utils::TestLogger>) {
let secp_ctx = Secp256k1::new();
let logger = Arc::new(test_utils::TestLogger::new());
let chain_monitor = Arc::new(test_utils::TestChainSource::new(Network::Testnet));
// Simple route to 2 via 1
- let our_chans = vec![channelmanager::ChannelDetails {
- channel_id: [0; 32],
- funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
- short_channel_id: Some(2),
- remote_network_id: our_id,
- counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
- channel_value_satoshis: 100000,
- user_id: 0,
- outbound_capacity_msat: 100000,
- inbound_capacity_msat: 100000,
- is_outbound: true, is_funding_locked: true,
- is_usable: true, is_public: true,
- counterparty_forwarding_info: None,
- }];
+ let our_chans = vec![get_channel_details(Some(2), our_id, InitFeatures::from_le_bytes(vec![0b11]), 100000)];
if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)) {
assert_eq!(err, "First hop cannot have our_node_id as a destination.");
} else { panic!(); }
// If we specify a channel to node7, that overrides our local channel view and that gets used
- let our_chans = vec![channelmanager::ChannelDetails {
- channel_id: [0; 32],
- funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
- short_channel_id: Some(42),
- remote_network_id: nodes[7].clone(),
- counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
- channel_value_satoshis: 0,
- user_id: 0,
- outbound_capacity_msat: 250_000_000,
- inbound_capacity_msat: 0,
- is_outbound: true, is_funding_locked: true,
- is_usable: true, is_public: true,
- counterparty_forwarding_info: None,
- }];
+ let our_chans = vec![get_channel_details(Some(42), nodes[7].clone(), InitFeatures::from_le_bytes(vec![0b11]), 250_000_000)];
let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths[0].len(), 2);
let (_, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
// Disable nodes 1, 2, and 8 by requiring unknown feature bits
- let mut unknown_features = NodeFeatures::known();
- unknown_features.set_required_unknown_bits();
+ let unknown_features = NodeFeatures::known().set_unknown_feature_required();
add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[0], unknown_features.clone(), 1);
add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[1], unknown_features.clone(), 1);
add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[7], unknown_features.clone(), 1);
} else { panic!(); }
// If we specify a channel to node7, that overrides our local channel view and that gets used
- let our_chans = vec![channelmanager::ChannelDetails {
- channel_id: [0; 32],
- funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
- short_channel_id: Some(42),
- remote_network_id: nodes[7].clone(),
- counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
- channel_value_satoshis: 0,
- user_id: 0,
- outbound_capacity_msat: 250_000_000,
- inbound_capacity_msat: 0,
- is_outbound: true, is_funding_locked: true,
- is_usable: true, is_public: true,
- counterparty_forwarding_info: None,
- }];
+ let our_chans = vec![get_channel_details(Some(42), nodes[7].clone(), InitFeatures::from_le_bytes(vec![0b11]), 250_000_000)];
let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths[0].len(), 2);
assert_eq!(route.paths[0][2].channel_features.le_flags(), &id_to_feature_flags(3));
// If we specify a channel to node7, that overrides our local channel view and that gets used
- let our_chans = vec![channelmanager::ChannelDetails {
- channel_id: [0; 32],
- funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
- short_channel_id: Some(42),
- remote_network_id: nodes[7].clone(),
- counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
- channel_value_satoshis: 0,
- user_id: 0,
- outbound_capacity_msat: 250_000_000,
- inbound_capacity_msat: 0,
- is_outbound: true, is_funding_locked: true,
- is_usable: true, is_public: true,
- counterparty_forwarding_info: None,
- }];
+ let our_chans = vec![get_channel_details(Some(42), nodes[7].clone(), InitFeatures::from_le_bytes(vec![0b11]), 250_000_000)];
let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths[0].len(), 2);
let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
// Simple test with outbound channel to 4 to test that last_hops and first_hops connect
- let our_chans = vec![channelmanager::ChannelDetails {
- channel_id: [0; 32],
- funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
- short_channel_id: Some(42),
- remote_network_id: nodes[3].clone(),
- counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
- channel_value_satoshis: 0,
- user_id: 0,
- outbound_capacity_msat: 250_000_000,
- inbound_capacity_msat: 0,
- is_outbound: true, is_funding_locked: true,
- is_usable: true, is_public: true,
- counterparty_forwarding_info: None,
- }];
+ let our_chans = vec![get_channel_details(Some(42), nodes[3].clone(), InitFeatures::from_le_bytes(vec![0b11]), 250_000_000)];
let mut last_hops = last_hops(&nodes);
let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, Some(&our_chans.iter().collect::<Vec<_>>()), &last_hops.iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths[0].len(), 2);
htlc_minimum_msat: None,
htlc_maximum_msat: last_hop_htlc_max,
}]);
- let our_chans = vec![channelmanager::ChannelDetails {
- channel_id: [0; 32],
- funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
- short_channel_id: Some(42),
- remote_network_id: middle_node_id,
- counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
- channel_value_satoshis: 100000,
- user_id: 0,
- outbound_capacity_msat: outbound_capacity_msat,
- inbound_capacity_msat: 100000,
- is_outbound: true, is_funding_locked: true,
- is_usable: true, is_public: true,
- counterparty_forwarding_info: None,
- }];
+ let our_chans = vec![get_channel_details(Some(42), middle_node_id, InitFeatures::from_le_bytes(vec![0b11]), outbound_capacity_msat)];
get_route(&source_node_id, &NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash()), &target_node_id, None, Some(&our_chans.iter().collect::<Vec<_>>()), &vec![&last_hops], route_val, 42, Arc::new(test_utils::TestLogger::new()))
}
});
// Now, limit the first_hop by the outbound_capacity_msat of 200_000 sats.
- let our_chans = vec![channelmanager::ChannelDetails {
- channel_id: [0; 32],
- funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
- short_channel_id: Some(42),
- remote_network_id: nodes[0].clone(),
- counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
- channel_value_satoshis: 0,
- user_id: 0,
- outbound_capacity_msat: 200_000_000,
- inbound_capacity_msat: 0,
- is_outbound: true, is_funding_locked: true,
- is_usable: true, is_public: true,
- counterparty_forwarding_info: None,
- }];
+ let our_chans = vec![get_channel_details(Some(42), nodes[0].clone(), InitFeatures::from_le_bytes(vec![0b11]), 200_000_000)];
{
// Attempt to route more than available results in a failure.
}
}
+ #[cfg(not(feature = "no_std"))]
pub(super) fn random_init_seed() -> u64 {
// Because the default HashMap in std pulls OS randomness, we can use it as a (bad) RNG.
use core::hash::{BuildHasher, Hasher};
println!("Using seed of {}", seed);
seed
}
+ #[cfg(not(feature = "no_std"))]
use util::ser::Readable;
#[test]
+ #[cfg(not(feature = "no_std"))]
fn generate_routes() {
let mut d = match super::test_utils::get_route_file() {
Ok(f) => f,
}
#[test]
+ #[cfg(not(feature = "no_std"))]
fn generate_routes_mpp() {
let mut d = match super::test_utils::get_route_file() {
Ok(f) => f,
}
}
-#[cfg(test)]
+#[cfg(all(test, not(feature = "no_std")))]
pub(crate) mod test_utils {
use std::fs::File;
/// Tries to open a network graph file, or panics with a URL to fetch it.
}
}
-#[cfg(all(test, feature = "unstable"))]
+#[cfg(all(test, feature = "unstable", not(feature = "no_std")))]
mod benches {
use super::*;
use util::logger::{Logger, Record};
projects / rust-lightning / blobdiff