+
+ #[test]
+ fn exact_fee_liquidity_limit() {
+ // Test that if, while walking the graph, we find a hop that has exactly enough liquidity
+ // for us, including later hop fees, we take it. In the first version of our MPP algorithm
+ // we calculated fees on a higher value, resulting in us ignoring such paths.
+ let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph();
+ let (our_privkey, our_id, _, nodes) = get_nodes(&secp_ctx);
+ let scorer = test_utils::TestScorer::with_penalty(0);
+ let payment_params = PaymentParameters::from_node_id(nodes[2]);
+
+ // We modify the graph to set the htlc_maximum of channel 2 to below the value we wish to
+ // send.
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 2,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(85_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 12,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: (4 << 4) | 1,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(270_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 1000000,
+ excess_data: Vec::new()
+ });
+
+ {
+ // Now, attempt to route 90 sats, which is exactly 90 sats at the last hop, plus the
+ // 200% fee charged channel 13 in the 1-to-2 direction.
+ let route = get_route(&our_id, &payment_params, &network_graph, None, 90_000, 42, Arc::clone(&logger), &scorer).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ assert_eq!(route.paths[0].len(), 2);
+
+ assert_eq!(route.paths[0][0].pubkey, nodes[7]);
+ assert_eq!(route.paths[0][0].short_channel_id, 12);
+ assert_eq!(route.paths[0][0].fee_msat, 90_000*2);
+ assert_eq!(route.paths[0][0].cltv_expiry_delta, (13 << 4) | 1);
+ assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(8));
+ assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(12));
+
+ assert_eq!(route.paths[0][1].pubkey, nodes[2]);
+ assert_eq!(route.paths[0][1].short_channel_id, 13);
+ assert_eq!(route.paths[0][1].fee_msat, 90_000);
+ assert_eq!(route.paths[0][1].cltv_expiry_delta, 42);
+ assert_eq!(route.paths[0][1].node_features.le_flags(), &id_to_feature_flags(3));
+ assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(13));
+ }
+ }
+
+ #[test]
+ fn htlc_max_reduction_below_min() {
+ // Test that if, while walking the graph, we reduce the value being sent to meet an
+ // htlc_maximum_msat, we don't end up undershooting a later htlc_minimum_msat. In the
+ // initial version of MPP we'd accept such routes but reject them while recalculating fees,
+ // resulting in us thinking there is no possible path, even if other paths exist.
+ let (secp_ctx, network_graph, net_graph_msg_handler, _, logger) = build_graph();
+ let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
+ let scorer = test_utils::TestScorer::with_penalty(0);
+ let payment_params = PaymentParameters::from_node_id(nodes[2]).with_features(InvoiceFeatures::known());
+
+ // We modify the graph to set the htlc_minimum of channel 2 and 4 as needed - channel 2
+ // gets an htlc_maximum_msat of 80_000 and channel 4 an htlc_minimum_msat of 90_000. We
+ // then try to send 90_000.
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 2,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(80_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[1], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 4,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: (4 << 4) | 1,
+ htlc_minimum_msat: 90_000,
+ htlc_maximum_msat: OptionalField::Absent,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ {
+ // Now, attempt to route 90 sats, hitting the htlc_minimum on channel 4, but
+ // overshooting the htlc_maximum on channel 2. Thus, we should pick the (absurdly
+ // expensive) channels 12-13 path.
+ let route = get_route(&our_id, &payment_params, &network_graph, None, 90_000, 42, Arc::clone(&logger), &scorer).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ assert_eq!(route.paths[0].len(), 2);
+
+ assert_eq!(route.paths[0][0].pubkey, nodes[7]);
+ assert_eq!(route.paths[0][0].short_channel_id, 12);
+ assert_eq!(route.paths[0][0].fee_msat, 90_000*2);
+ assert_eq!(route.paths[0][0].cltv_expiry_delta, (13 << 4) | 1);
+ assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(8));
+ assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(12));
+
+ assert_eq!(route.paths[0][1].pubkey, nodes[2]);
+ assert_eq!(route.paths[0][1].short_channel_id, 13);
+ assert_eq!(route.paths[0][1].fee_msat, 90_000);
+ assert_eq!(route.paths[0][1].cltv_expiry_delta, 42);
+ assert_eq!(route.paths[0][1].node_features.le_flags(), InvoiceFeatures::known().le_flags());
+ assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(13));
+ }
+ }
+
+ #[test]
+ fn multiple_direct_first_hops() {
+ // Previously we'd only ever considered one first hop path per counterparty.
+ // However, as we don't restrict users to one channel per peer, we really need to support
+ // looking at all first hop paths.
+ // Here we test that we do not ignore all-but-the-last first hop paths per counterparty (as
+ // we used to do by overwriting the `first_hop_targets` hashmap entry) and that we can MPP
+ // route over multiple channels with the same first hop.
+ let secp_ctx = Secp256k1::new();
+ let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
+ let logger = Arc::new(test_utils::TestLogger::new());
+ let network_graph = NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash());
+ let scorer = test_utils::TestScorer::with_penalty(0);
+ let payment_params = PaymentParameters::from_node_id(nodes[0]).with_features(InvoiceFeatures::known());
+
+ {
+ let route = get_route(&our_id, &payment_params, &network_graph, Some(&[
+ &get_channel_details(Some(3), nodes[0], InitFeatures::known(), 200_000),
+ &get_channel_details(Some(2), nodes[0], InitFeatures::known(), 10_000),
+ ]), 100_000, 42, Arc::clone(&logger), &scorer).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ assert_eq!(route.paths[0].len(), 1);
+
+ assert_eq!(route.paths[0][0].pubkey, nodes[0]);
+ assert_eq!(route.paths[0][0].short_channel_id, 3);
+ assert_eq!(route.paths[0][0].fee_msat, 100_000);
+ }
+ {
+ let route = get_route(&our_id, &payment_params, &network_graph, Some(&[
+ &get_channel_details(Some(3), nodes[0], InitFeatures::known(), 50_000),
+ &get_channel_details(Some(2), nodes[0], InitFeatures::known(), 50_000),
+ ]), 100_000, 42, Arc::clone(&logger), &scorer).unwrap();
+ assert_eq!(route.paths.len(), 2);
+ assert_eq!(route.paths[0].len(), 1);
+ assert_eq!(route.paths[1].len(), 1);
+
+ assert_eq!(route.paths[0][0].pubkey, nodes[0]);
+ assert_eq!(route.paths[0][0].short_channel_id, 3);
+ assert_eq!(route.paths[0][0].fee_msat, 50_000);
+
+ assert_eq!(route.paths[1][0].pubkey, nodes[0]);
+ assert_eq!(route.paths[1][0].short_channel_id, 2);
+ assert_eq!(route.paths[1][0].fee_msat, 50_000);
+ }
+ }
+
+ #[test]
+ fn prefers_shorter_route_with_higher_fees() {
+ let (secp_ctx, network_graph, _, _, logger) = build_graph();
+ let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
+ let payment_params = PaymentParameters::from_node_id(nodes[6]).with_route_hints(last_hops(&nodes));
+
+ // Without penalizing each hop 100 msats, a longer path with lower fees is chosen.
+ let scorer = test_utils::TestScorer::with_penalty(0);
+ let route = get_route(
+ &our_id, &payment_params, &network_graph, None, 100, 42,
+ Arc::clone(&logger), &scorer
+ ).unwrap();
+ let path = route.paths[0].iter().map(|hop| hop.short_channel_id).collect::<Vec<_>>();
+
+ assert_eq!(route.get_total_fees(), 100);
+ assert_eq!(route.get_total_amount(), 100);
+ assert_eq!(path, vec![2, 4, 6, 11, 8]);
+
+ // Applying a 100 msat penalty to each hop results in taking channels 7 and 10 to nodes[6]
+ // from nodes[2] rather than channel 6, 11, and 8, even though the longer path is cheaper.
+ let scorer = test_utils::TestScorer::with_penalty(100);
+ let route = get_route(
+ &our_id, &payment_params, &network_graph, None, 100, 42,
+ Arc::clone(&logger), &scorer
+ ).unwrap();
+ let path = route.paths[0].iter().map(|hop| hop.short_channel_id).collect::<Vec<_>>();
+
+ assert_eq!(route.get_total_fees(), 300);
+ assert_eq!(route.get_total_amount(), 100);
+ assert_eq!(path, vec![2, 4, 7, 10]);
+ }
+
+ struct BadChannelScorer {
+ short_channel_id: u64,
+ }
+
+ #[cfg(c_bindings)]
+ impl Writeable for BadChannelScorer {
+ fn write<W: Writer>(&self, _w: &mut W) -> Result<(), ::io::Error> { unimplemented!() }
+ }
+ impl Score for BadChannelScorer {
+ fn channel_penalty_msat(&self, short_channel_id: u64, _send_amt: u64, _capacity_msat: u64, _source: &NodeId, _target: &NodeId) -> u64 {
+ if short_channel_id == self.short_channel_id { u64::max_value() } else { 0 }
+ }
+
+ fn payment_path_failed(&mut self, _path: &[&RouteHop], _short_channel_id: u64) {}
+ fn payment_path_successful(&mut self, _path: &[&RouteHop]) {}
+ }
+
+ struct BadNodeScorer {
+ node_id: NodeId,
+ }
+
+ #[cfg(c_bindings)]
+ impl Writeable for BadNodeScorer {
+ fn write<W: Writer>(&self, _w: &mut W) -> Result<(), ::io::Error> { unimplemented!() }
+ }
+
+ impl Score for BadNodeScorer {
+ fn channel_penalty_msat(&self, _short_channel_id: u64, _send_amt: u64, _capacity_msat: u64, _source: &NodeId, target: &NodeId) -> u64 {
+ if *target == self.node_id { u64::max_value() } else { 0 }
+ }
+
+ fn payment_path_failed(&mut self, _path: &[&RouteHop], _short_channel_id: u64) {}
+ fn payment_path_successful(&mut self, _path: &[&RouteHop]) {}
+ }
+
+ #[test]
+ fn avoids_routing_through_bad_channels_and_nodes() {
+ let (secp_ctx, network_graph, _, _, logger) = build_graph();
+ let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
+ let payment_params = PaymentParameters::from_node_id(nodes[6]).with_route_hints(last_hops(&nodes));
+
+ // A path to nodes[6] exists when no penalties are applied to any channel.
+ let scorer = test_utils::TestScorer::with_penalty(0);
+ let route = get_route(
+ &our_id, &payment_params, &network_graph, None, 100, 42,
+ Arc::clone(&logger), &scorer
+ ).unwrap();
+ let path = route.paths[0].iter().map(|hop| hop.short_channel_id).collect::<Vec<_>>();
+
+ assert_eq!(route.get_total_fees(), 100);
+ assert_eq!(route.get_total_amount(), 100);
+ assert_eq!(path, vec![2, 4, 6, 11, 8]);
+
+ // A different path to nodes[6] exists if channel 6 cannot be routed over.
+ let scorer = BadChannelScorer { short_channel_id: 6 };
+ let route = get_route(
+ &our_id, &payment_params, &network_graph, None, 100, 42,
+ Arc::clone(&logger), &scorer
+ ).unwrap();
+ let path = route.paths[0].iter().map(|hop| hop.short_channel_id).collect::<Vec<_>>();
+
+ assert_eq!(route.get_total_fees(), 300);
+ assert_eq!(route.get_total_amount(), 100);
+ assert_eq!(path, vec![2, 4, 7, 10]);
+
+ // A path to nodes[6] does not exist if nodes[2] cannot be routed through.
+ let scorer = BadNodeScorer { node_id: NodeId::from_pubkey(&nodes[2]) };
+ match get_route(
+ &our_id, &payment_params, &network_graph, None, 100, 42,
+ Arc::clone(&logger), &scorer
+ ) {
+ Err(LightningError { err, .. } ) => {
+ assert_eq!(err, "Failed to find a path to the given destination");
+ },
+ Ok(_) => panic!("Expected error"),
+ }
+ }
+
+ #[test]
+ fn total_fees_single_path() {
+ let route = Route {
+ paths: vec![vec![
+ RouteHop {
+ pubkey: PublicKey::from_slice(&hex::decode("02eec7245d6b7d2ccb30380bfbe2a3648cd7a942653f5aa340edcea1f283686619").unwrap()[..]).unwrap(),
+ channel_features: ChannelFeatures::empty(), node_features: NodeFeatures::empty(),
+ short_channel_id: 0, fee_msat: 100, cltv_expiry_delta: 0
+ },
+ RouteHop {
+ pubkey: PublicKey::from_slice(&hex::decode("0324653eac434488002cc06bbfb7f10fe18991e35f9fe4302dbea6d2353dc0ab1c").unwrap()[..]).unwrap(),
+ channel_features: ChannelFeatures::empty(), node_features: NodeFeatures::empty(),
+ short_channel_id: 0, fee_msat: 150, cltv_expiry_delta: 0
+ },
+ RouteHop {
+ pubkey: PublicKey::from_slice(&hex::decode("027f31ebc5462c1fdce1b737ecff52d37d75dea43ce11c74d25aa297165faa2007").unwrap()[..]).unwrap(),
+ channel_features: ChannelFeatures::empty(), node_features: NodeFeatures::empty(),
+ short_channel_id: 0, fee_msat: 225, cltv_expiry_delta: 0
+ },
+ ]],
+ payment_params: None,
+ };
+
+ assert_eq!(route.get_total_fees(), 250);
+ assert_eq!(route.get_total_amount(), 225);
+ }
+
+ #[test]
+ fn total_fees_multi_path() {
+ let route = Route {
+ paths: vec![vec![
+ RouteHop {
+ pubkey: PublicKey::from_slice(&hex::decode("02eec7245d6b7d2ccb30380bfbe2a3648cd7a942653f5aa340edcea1f283686619").unwrap()[..]).unwrap(),
+ channel_features: ChannelFeatures::empty(), node_features: NodeFeatures::empty(),
+ short_channel_id: 0, fee_msat: 100, cltv_expiry_delta: 0
+ },
+ RouteHop {
+ pubkey: PublicKey::from_slice(&hex::decode("0324653eac434488002cc06bbfb7f10fe18991e35f9fe4302dbea6d2353dc0ab1c").unwrap()[..]).unwrap(),
+ channel_features: ChannelFeatures::empty(), node_features: NodeFeatures::empty(),
+ short_channel_id: 0, fee_msat: 150, cltv_expiry_delta: 0
+ },
+ ],vec![
+ RouteHop {
+ pubkey: PublicKey::from_slice(&hex::decode("02eec7245d6b7d2ccb30380bfbe2a3648cd7a942653f5aa340edcea1f283686619").unwrap()[..]).unwrap(),
+ channel_features: ChannelFeatures::empty(), node_features: NodeFeatures::empty(),
+ short_channel_id: 0, fee_msat: 100, cltv_expiry_delta: 0
+ },
+ RouteHop {
+ pubkey: PublicKey::from_slice(&hex::decode("0324653eac434488002cc06bbfb7f10fe18991e35f9fe4302dbea6d2353dc0ab1c").unwrap()[..]).unwrap(),
+ channel_features: ChannelFeatures::empty(), node_features: NodeFeatures::empty(),
+ short_channel_id: 0, fee_msat: 150, cltv_expiry_delta: 0
+ },
+ ]],
+ payment_params: None,
+ };
+
+ assert_eq!(route.get_total_fees(), 200);
+ assert_eq!(route.get_total_amount(), 300);
+ }
+
+ #[test]
+ fn total_empty_route_no_panic() {
+ // In an earlier version of `Route::get_total_fees` and `Route::get_total_amount`, they
+ // would both panic if the route was completely empty. We test to ensure they return 0
+ // here, even though its somewhat nonsensical as a route.
+ let route = Route { paths: Vec::new(), payment_params: None };
+
+ assert_eq!(route.get_total_fees(), 0);
+ assert_eq!(route.get_total_amount(), 0);
+ }
+
+ #[test]
+ fn limits_total_cltv_delta() {
+ let (secp_ctx, network_graph, _, _, logger) = build_graph();
+ let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
+
+ let scorer = test_utils::TestScorer::with_penalty(0);
+
+ // Make sure that generally there is at least one route available
+ let feasible_max_total_cltv_delta = 1008;
+ let feasible_payment_params = PaymentParameters::from_node_id(nodes[6]).with_route_hints(last_hops(&nodes))
+ .with_max_total_cltv_expiry_delta(feasible_max_total_cltv_delta);
+ let route = get_route(&our_id, &feasible_payment_params, &network_graph, None, 100, 42, Arc::clone(&logger), &scorer).unwrap();
+ let path = route.paths[0].iter().map(|hop| hop.short_channel_id).collect::<Vec<_>>();
+ assert_ne!(path.len(), 0);
+
+ // But not if we exclude all paths on the basis of their accumulated CLTV delta
+ let fail_max_total_cltv_delta = 23;
+ let fail_payment_params = PaymentParameters::from_node_id(nodes[6]).with_route_hints(last_hops(&nodes))
+ .with_max_total_cltv_expiry_delta(fail_max_total_cltv_delta);
+ match get_route(&our_id, &fail_payment_params, &network_graph, None, 100, 42, Arc::clone(&logger), &scorer)
+ {
+ Err(LightningError { err, .. } ) => {
+ assert_eq!(err, "Failed to find a path to the given destination");
+ },
+ Ok(_) => panic!("Expected error"),
+ }
+ }
+
+ #[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};
+ let seed = std::collections::hash_map::RandomState::new().build_hasher().finish();
+ 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,
+ Err(e) => {
+ eprintln!("{}", e);
+ return;
+ },
+ };