+
+ #[test]
+ fn unannounced_path_test() {
+ // We should be able to send a payment to a destination without any help of a routing graph
+ // if we have a channel with a common counterparty that appears in the first and last hop
+ // hints.
+ let source_node_id = PublicKey::from_secret_key(&Secp256k1::new(), &SecretKey::from_slice(&hex::decode(format!("{:02}", 41).repeat(32)).unwrap()[..]).unwrap());
+ let middle_node_id = PublicKey::from_secret_key(&Secp256k1::new(), &SecretKey::from_slice(&hex::decode(format!("{:02}", 42).repeat(32)).unwrap()[..]).unwrap());
+ let target_node_id = PublicKey::from_secret_key(&Secp256k1::new(), &SecretKey::from_slice(&hex::decode(format!("{:02}", 43).repeat(32)).unwrap()[..]).unwrap());
+
+ // If we specify a channel to a middle hop, that overrides our local channel view and that gets used
+ let last_hops = vec![RouteHintHop {
+ src_node_id: middle_node_id,
+ short_channel_id: 8,
+ fees: RoutingFees {
+ base_msat: 1000,
+ proportional_millionths: 0,
+ },
+ cltv_expiry_delta: (8 << 8) | 1,
+ htlc_minimum_msat: None,
+ htlc_maximum_msat: None,
+ }];
+ let our_chans = vec![channelmanager::ChannelDetails {
+ channel_id: [0; 32],
+ 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: 100000,
+ inbound_capacity_msat: 100000,
+ is_live: true,
+ counterparty_forwarding_info: None,
+ }];
+ let route = get_route(&source_node_id, &NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash()), &target_node_id, None, Some(&our_chans.iter().collect::<Vec<_>>()), &last_hops.iter().collect::<Vec<_>>(), 100, 42, Arc::new(test_utils::TestLogger::new())).unwrap();
+
+ assert_eq!(route.paths[0].len(), 2);
+
+ assert_eq!(route.paths[0][0].pubkey, middle_node_id);
+ assert_eq!(route.paths[0][0].short_channel_id, 42);
+ assert_eq!(route.paths[0][0].fee_msat, 1000);
+ assert_eq!(route.paths[0][0].cltv_expiry_delta, (8 << 8) | 1);
+ assert_eq!(route.paths[0][0].node_features.le_flags(), &[0b11]);
+ assert_eq!(route.paths[0][0].channel_features.le_flags(), &[0; 0]); // We can't learn any flags from invoices, sadly
+
+ assert_eq!(route.paths[0][1].pubkey, target_node_id);
+ 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(), &[0; 0]); // 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
+ }
+
+ #[test]
+ fn available_amount_while_routing_test() {
+ // Tests whether we choose the correct available channel amount while routing.
+
+ let (secp_ctx, mut net_graph_msg_handler, chain_monitor, logger) = build_graph();
+ let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
+
+ // We will use a simple single-path route from
+ // our node to node2 via node0: channels {1, 3}.
+
+ // First disable all other paths.
+ 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: 2,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_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: 2,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Make the first channel (#1) very permissive,
+ // and we will be testing all limits on the second channel.
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 1,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(1_000_000_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // First, let's see if routing works if we have absolutely no idea about the available amount.
+ // In this case, it should be set to 250_000 sats.
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 3,
+ timestamp: 2,
+ 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()
+ });
+
+ {
+ // Attempt to route more than available results in a failure.
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 250_000_001, 42, Arc::clone(&logger)) {
+ assert_eq!(err, "Failed to find a sufficient route to the given destination");
+ } else { panic!(); }
+ }
+
+ {
+ // Now, attempt to route an exact amount we have should be fine.
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 250_000_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ let path = route.paths.last().unwrap();
+ assert_eq!(path.len(), 2);
+ assert_eq!(path.last().unwrap().pubkey, nodes[2]);
+ assert_eq!(path.last().unwrap().fee_msat, 250_000_000);
+ }
+
+ // Check that setting outbound_capacity_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(),
+ short_channel_id: 1,
+ timestamp: 3,
+ flags: 2,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(1_000_000_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::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],
+ 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_live: true,
+ counterparty_forwarding_info: None,
+ }];
+
+ {
+ // Attempt to route more than available results in a failure.
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 200_000_001, 42, Arc::clone(&logger)) {
+ assert_eq!(err, "Failed to find a sufficient route to the given destination");
+ } else { panic!(); }
+ }
+
+ {
+ // Now, attempt to route an exact amount we have should be fine.
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 200_000_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ let path = route.paths.last().unwrap();
+ assert_eq!(path.len(), 2);
+ assert_eq!(path.last().unwrap().pubkey, nodes[2]);
+ assert_eq!(path.last().unwrap().fee_msat, 200_000_000);
+ }
+
+ // Enable channel #1 back.
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 1,
+ timestamp: 4,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(1_000_000_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+
+ // Now let's see if routing works if we know only htlc_maximum_msat.
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 3,
+ timestamp: 3,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(15_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ {
+ // Attempt to route more than available results in a failure.
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 15_001, 42, Arc::clone(&logger)) {
+ assert_eq!(err, "Failed to find a sufficient route to the given destination");
+ } else { panic!(); }
+ }
+
+ {
+ // Now, attempt to route an exact amount we have should be fine.
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 15_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ let path = route.paths.last().unwrap();
+ assert_eq!(path.len(), 2);
+ assert_eq!(path.last().unwrap().pubkey, nodes[2]);
+ assert_eq!(path.last().unwrap().fee_msat, 15_000);
+ }
+
+ // Now let's see if routing works if we know only capacity from the UTXO.
+
+ // We can't change UTXO capacity on the fly, so we'll disable
+ // the existing channel and add another one with the capacity we need.
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 3,
+ timestamp: 4,
+ flags: 2,
+ 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()
+ });
+
+ let good_script = Builder::new().push_opcode(opcodes::all::OP_PUSHNUM_2)
+ .push_slice(&PublicKey::from_secret_key(&secp_ctx, &privkeys[0]).serialize())
+ .push_slice(&PublicKey::from_secret_key(&secp_ctx, &privkeys[2]).serialize())
+ .push_opcode(opcodes::all::OP_PUSHNUM_2)
+ .push_opcode(opcodes::all::OP_CHECKMULTISIG).into_script().to_v0_p2wsh();
+
+ *chain_monitor.utxo_ret.lock().unwrap() = Ok(TxOut { value: 15, script_pubkey: good_script.clone() });
+ net_graph_msg_handler.add_chain_access(Some(chain_monitor));
+
+ add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], &privkeys[2], ChannelFeatures::from_le_bytes(id_to_feature_flags(3)), 333);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 333,
+ timestamp: 1,
+ flags: 0,
+ cltv_expiry_delta: (3 << 8) | 1,
+ 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, &privkeys[2], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 333,
+ timestamp: 1,
+ flags: 1,
+ cltv_expiry_delta: (3 << 8) | 2,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Absent,
+ fee_base_msat: 100,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ {
+ // Attempt to route more than available results in a failure.
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 15_001, 42, Arc::clone(&logger)) {
+ assert_eq!(err, "Failed to find a sufficient route to the given destination");
+ } else { panic!(); }
+ }
+
+ {
+ // Now, attempt to route an exact amount we have should be fine.
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 15_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ let path = route.paths.last().unwrap();
+ assert_eq!(path.len(), 2);
+ assert_eq!(path.last().unwrap().pubkey, nodes[2]);
+ assert_eq!(path.last().unwrap().fee_msat, 15_000);
+ }
+
+ // Now let's see if routing chooses htlc_maximum_msat over UTXO capacity.
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 333,
+ timestamp: 6,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(10_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ {
+ // Attempt to route more than available results in a failure.
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 10_001, 42, Arc::clone(&logger)) {
+ assert_eq!(err, "Failed to find a sufficient route to the given destination");
+ } else { panic!(); }
+ }
+
+ {
+ // Now, attempt to route an exact amount we have should be fine.
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 10_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ let path = route.paths.last().unwrap();
+ assert_eq!(path.len(), 2);
+ assert_eq!(path.last().unwrap().pubkey, nodes[2]);
+ assert_eq!(path.last().unwrap().fee_msat, 10_000);
+ }
+ }
+
+ #[test]
+ fn available_liquidity_last_hop_test() {
+ // Check that available liquidity properly limits the path even when only
+ // one of the latter hops is limited.
+ let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
+ let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
+
+ // Path via {node7, node2, node4} is channels {12, 13, 6, 11}.
+ // {12, 13, 11} have the capacities of 100, {6} has a capacity of 50.
+ // Total capacity: 50 sats.
+
+ // Disable other potential paths.
+ 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: 2,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 7,
+ timestamp: 2,
+ flags: 2,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Limit capacities
+
+ 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: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 13,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 6,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(50_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 11,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ {
+ // Attempt to route more than available results in a failure.
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 60_000, 42, Arc::clone(&logger)) {
+ assert_eq!(err, "Failed to find a sufficient route to the given destination");
+ } else { panic!(); }
+ }
+
+ {
+ // Now, attempt to route 49 sats (just a bit below the capacity).
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 49_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ let mut total_amount_paid_msat = 0;
+ for path in &route.paths {
+ assert_eq!(path.len(), 4);
+ assert_eq!(path.last().unwrap().pubkey, nodes[3]);
+ total_amount_paid_msat += path.last().unwrap().fee_msat;
+ }
+ assert_eq!(total_amount_paid_msat, 49_000);
+ }
+
+ {
+ // Attempt to route an exact amount is also fine
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 50_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ let mut total_amount_paid_msat = 0;
+ for path in &route.paths {
+ assert_eq!(path.len(), 4);
+ assert_eq!(path.last().unwrap().pubkey, nodes[3]);
+ total_amount_paid_msat += path.last().unwrap().fee_msat;
+ }
+ assert_eq!(total_amount_paid_msat, 50_000);
+ }
+ }
+
+ #[test]
+ fn ignore_fee_first_hop_test() {
+ let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
+ let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
+
+ // Path via node0 is channels {1, 3}. Limit them to 100 and 50 sats (total limit 50).
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 1,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 1_000_000,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 3,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(50_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ {
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 50_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ let mut total_amount_paid_msat = 0;
+ for path in &route.paths {
+ assert_eq!(path.len(), 2);
+ assert_eq!(path.last().unwrap().pubkey, nodes[2]);
+ total_amount_paid_msat += path.last().unwrap().fee_msat;
+ }
+ assert_eq!(total_amount_paid_msat, 50_000);
+ }
+ }
+
+ #[test]
+ fn simple_mpp_route_test() {
+ let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
+ let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
+
+ // We need a route consisting of 3 paths:
+ // From our node to node2 via node0, node7, node1 (three paths one hop each).
+ // To achieve this, the amount being transferred should be around
+ // the total capacity of these 3 paths.
+
+ // First, we set limits on these (previously unlimited) channels.
+ // Their aggregate capacity will be 50 + 60 + 180 = 290 sats.
+
+ // Path via node0 is channels {1, 3}. Limit them to 100 and 50 sats (total limit 50).
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 1,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 3,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(50_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Path via node7 is channels {12, 13}. Limit them to 60 and 60 sats
+ // (total limit 60).
+ 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: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(60_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 13,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(60_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Path via node1 is channels {2, 4}. Limit them to 200 and 180 sats
+ // (total capacity 180 sats).
+ 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(200_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: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(180_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ {
+ // Attempt to route more than available results in a failure.
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(),
+ &nodes[2], Some(InvoiceFeatures::known()), None, &Vec::new(), 300_000, 42, Arc::clone(&logger)) {
+ assert_eq!(err, "Failed to find a sufficient route to the given destination");
+ } else { panic!(); }
+ }
+
+ {
+ // Now, attempt to route 250 sats (just a bit below the capacity).
+ // Our algorithm should provide us with these 3 paths.
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 250_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 3);
+ let mut total_amount_paid_msat = 0;
+ for path in &route.paths {
+ assert_eq!(path.len(), 2);
+ assert_eq!(path.last().unwrap().pubkey, nodes[2]);
+ total_amount_paid_msat += path.last().unwrap().fee_msat;
+ }
+ assert_eq!(total_amount_paid_msat, 250_000);
+ }
+
+ {
+ // Attempt to route an exact amount is also fine
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 290_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 3);
+ let mut total_amount_paid_msat = 0;
+ for path in &route.paths {
+ assert_eq!(path.len(), 2);
+ assert_eq!(path.last().unwrap().pubkey, nodes[2]);
+ total_amount_paid_msat += path.last().unwrap().fee_msat;
+ }
+ assert_eq!(total_amount_paid_msat, 290_000);
+ }
+ }
+
+ #[test]
+ fn long_mpp_route_test() {
+ let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
+ let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
+
+ // We need a route consisting of 3 paths:
+ // From our node to node3 via {node0, node2}, {node7, node2, node4} and {node7, node2}.
+ // Note that these paths overlap (channels 5, 12, 13).
+ // We will route 300 sats.
+ // Each path will have 100 sats capacity, those channels which
+ // are used twice will have 200 sats capacity.
+
+ // Disable other potential paths.
+ 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: 2,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 7,
+ timestamp: 2,
+ flags: 2,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Path via {node0, node2} is channels {1, 3, 5}.
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 1,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 3,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Capacity of 200 sats because this channel will be used by 3rd path as well.
+ add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], &privkeys[3], ChannelFeatures::from_le_bytes(id_to_feature_flags(5)), 5);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 5,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(200_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Path via {node7, node2, node4} is channels {12, 13, 6, 11}.
+ // Add 100 sats to the capacities of {12, 13}, because these channels
+ // are also used for 3rd path. 100 sats for the rest. Total capacity: 100 sats.
+ 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: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(200_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 13,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(200_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 6,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 11,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Path via {node7, node2} is channels {12, 13, 5}.
+ // We already limited them to 200 sats (they are used twice for 100 sats).
+ // Nothing to do here.
+
+ {
+ // Attempt to route more than available results in a failure.
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 350_000, 42, Arc::clone(&logger)) {
+ assert_eq!(err, "Failed to find a sufficient route to the given destination");
+ } else { panic!(); }
+ }
+
+ {
+ // Now, attempt to route 300 sats (exact amount we can route).
+ // Our algorithm should provide us with these 3 paths, 100 sats each.
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 300_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 3);
+
+ let mut total_amount_paid_msat = 0;
+ for path in &route.paths {
+ assert_eq!(path.last().unwrap().pubkey, nodes[3]);
+ total_amount_paid_msat += path.last().unwrap().fee_msat;
+ }
+ assert_eq!(total_amount_paid_msat, 300_000);
+ }
+
+ }
+
+ #[test]
+ fn mpp_cheaper_route_test() {
+ let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
+ let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
+
+ // This test checks that if we have two cheaper paths and one more expensive path,
+ // so that liquidity-wise any 2 of 3 combination is sufficient,
+ // two cheaper paths will be taken.
+ // These paths have equal available liquidity.
+
+ // We need a combination of 3 paths:
+ // From our node to node3 via {node0, node2}, {node7, node2, node4} and {node7, node2}.
+ // Note that these paths overlap (channels 5, 12, 13).
+ // Each path will have 100 sats capacity, those channels which
+ // are used twice will have 200 sats capacity.
+
+ // Disable other potential paths.
+ 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: 2,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 7,
+ timestamp: 2,
+ flags: 2,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Path via {node0, node2} is channels {1, 3, 5}.
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 1,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 3,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Capacity of 200 sats because this channel will be used by 3rd path as well.
+ add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], &privkeys[3], ChannelFeatures::from_le_bytes(id_to_feature_flags(5)), 5);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 5,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(200_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Path via {node7, node2, node4} is channels {12, 13, 6, 11}.
+ // Add 100 sats to the capacities of {12, 13}, because these channels
+ // are also used for 3rd path. 100 sats for the rest. Total capacity: 100 sats.
+ 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: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(200_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 13,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(200_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 6,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 1_000,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 11,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Path via {node7, node2} is channels {12, 13, 5}.
+ // We already limited them to 200 sats (they are used twice for 100 sats).
+ // Nothing to do here.
+
+ {
+ // Now, attempt to route 180 sats.
+ // Our algorithm should provide us with these 2 paths.
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 180_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 2);
+
+ let mut total_value_transferred_msat = 0;
+ let mut total_paid_msat = 0;
+ for path in &route.paths {
+ assert_eq!(path.last().unwrap().pubkey, nodes[3]);
+ total_value_transferred_msat += path.last().unwrap().fee_msat;
+ for hop in path {
+ total_paid_msat += hop.fee_msat;
+ }
+ }
+ // If we paid fee, this would be higher.
+ assert_eq!(total_value_transferred_msat, 180_000);
+ let total_fees_paid = total_paid_msat - total_value_transferred_msat;
+ assert_eq!(total_fees_paid, 0);
+ }
+ }
+
+ #[test]
+ fn fees_on_mpp_route_test() {
+ // This test makes sure that MPP algorithm properly takes into account
+ // fees charged on the channels, by making the fees impactful:
+ // if the fee is not properly accounted for, the behavior is different.
+ let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
+ let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
+
+ // We need a route consisting of 2 paths:
+ // From our node to node3 via {node0, node2} and {node7, node2, node4}.
+ // We will route 200 sats, Each path will have 100 sats capacity.
+
+ // This test is not particularly stable: e.g.,
+ // there's a way to route via {node0, node2, node4}.
+ // It works while pathfinding is deterministic, but can be broken otherwise.
+ // It's fine to ignore this concern for now.
+
+ // Disable other potential paths.
+ 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: 2,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 7,
+ timestamp: 2,
+ flags: 2,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Path via {node0, node2} is channels {1, 3, 5}.
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 1,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 3,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], &privkeys[3], ChannelFeatures::from_le_bytes(id_to_feature_flags(5)), 5);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 5,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Path via {node7, node2, node4} is channels {12, 13, 6, 11}.
+ // All channels should be 100 sats capacity. But for the fee experiment,
+ // we'll add absolute fee of 150 sats paid for the use channel 6 (paid to node2 on channel 13).
+ // Since channel 12 allows to deliver only 250 sats to channel 13, channel 13 can transfer only
+ // 100 sats (and pay 150 sats in fees for the use of channel 6),
+ // so no matter how large are other channels,
+ // the whole path will be limited by 100 sats with just these 2 conditions:
+ // - channel 12 capacity is 250 sats
+ // - fee for channel 6 is 150 sats
+ // Let's test this by enforcing these 2 conditions and removing other limits.
+ 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: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(250_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 13,
+ timestamp: 2,
+ 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, &privkeys[2], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 6,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Absent,
+ fee_base_msat: 150_000,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 11,
+ timestamp: 2,
+ 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()
+ });
+
+ {
+ // Attempt to route more than available results in a failure.
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 210_000, 42, Arc::clone(&logger)) {
+ assert_eq!(err, "Failed to find a sufficient route to the given destination");
+ } else { panic!(); }
+ }
+
+ {
+ // Now, attempt to route 200 sats (exact amount we can route).
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 200_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 2);
+
+ let mut total_amount_paid_msat = 0;
+ for path in &route.paths {
+ assert_eq!(path.last().unwrap().pubkey, nodes[3]);
+ total_amount_paid_msat += path.last().unwrap().fee_msat;
+ }
+ assert_eq!(total_amount_paid_msat, 200_000);
+ }
+
+ }
+
+ #[test]
+ fn drop_lowest_channel_mpp_route_test() {
+ // This test checks that low-capacity channel is dropped when after
+ // path finding we realize that we found more capacity than we need.
+ let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
+ let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
+
+ // We need a route consisting of 3 paths:
+ // From our node to node2 via node0, node7, node1 (three paths one hop each).
+
+ // The first and the second paths should be sufficient, but the third should be
+ // cheaper, so that we select it but drop later.
+
+ // First, we set limits on these (previously unlimited) channels.
+ // Their aggregate capacity will be 50 + 60 + 20 = 130 sats.
+
+ // Path via node0 is channels {1, 3}. Limit them to 100 and 50 sats (total limit 50);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 1,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(100_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 3,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(50_000),
+ fee_base_msat: 100,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Path via node7 is channels {12, 13}. Limit them to 60 and 60 sats (total limit 60);
+ 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: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(60_000),
+ fee_base_msat: 100,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 13,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(60_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ // Path via node1 is channels {2, 4}. Limit them to 20 and 20 sats (total capacity 20 sats).
+ 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(20_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: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(20_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ {
+ // Attempt to route more than available results in a failure.
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 150_000, 42, Arc::clone(&logger)) {
+ assert_eq!(err, "Failed to find a sufficient route to the given destination");
+ } else { panic!(); }
+ }
+
+ {
+ // Now, attempt to route 125 sats (just a bit below the capacity of 3 channels).
+ // Our algorithm should provide us with these 3 paths.
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 125_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 3);
+ let mut total_amount_paid_msat = 0;
+ for path in &route.paths {
+ assert_eq!(path.len(), 2);
+ assert_eq!(path.last().unwrap().pubkey, nodes[2]);
+ total_amount_paid_msat += path.last().unwrap().fee_msat;
+ }
+ assert_eq!(total_amount_paid_msat, 125_000);
+ }
+
+ {
+ // Attempt to route without the last small cheap channel
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2],
+ Some(InvoiceFeatures::known()), None, &Vec::new(), 90_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 2);
+ let mut total_amount_paid_msat = 0;
+ for path in &route.paths {
+ assert_eq!(path.len(), 2);
+ assert_eq!(path.last().unwrap().pubkey, nodes[2]);
+ total_amount_paid_msat += path.last().unwrap().fee_msat;
+ }
+ assert_eq!(total_amount_paid_msat, 90_000);
+ }
+ }
+
+ #[test]
+ fn min_criteria_consistency() {
+ // Test that we don't use an inconsistent metric between updating and walking nodes during
+ // our Dijkstra's pass. In the initial version of MPP, the "best source" for a given node
+ // was updated with a different criterion from the heap sorting, resulting in loops in
+ // calculated paths. We test for that specific case here.
+
+ // We construct a network that looks like this:
+ //
+ // node2 -1(3)2- node3
+ // 2 2
+ // (2) (4)
+ // 1 1
+ // node1 -1(5)2- node4 -1(1)2- node6
+ // 2
+ // (6)
+ // 1
+ // our_node
+ //
+ // We create a loop on the side of our real path - our destination is node 6, with a
+ // previous hop of node 4. From 4, the cheapest previous path is channel 2 from node 2,
+ // followed by node 3 over channel 3. Thereafter, the cheapest next-hop is back to node 4
+ // (this time over channel 4). Channel 4 has 0 htlc_minimum_msat whereas channel 1 (the
+ // other channel with a previous-hop of node 4) has a high (but irrelevant to the overall
+ // 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 logger = Arc::new(test_utils::TestLogger::new());
+ let net_graph_msg_handler = NetGraphMsgHandler::new(genesis_block(Network::Testnet).header.block_hash(), None, Arc::clone(&logger));
+ let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
+
+ add_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, &privkeys[1], ChannelFeatures::from_le_bytes(id_to_feature_flags(6)), 6);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 6,
+ timestamp: 1,
+ flags: 0,
+ cltv_expiry_delta: (6 << 8) | 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, &privkeys[1], NodeFeatures::from_le_bytes(id_to_feature_flags(1)), 0);
+
+ add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[1], &privkeys[4], ChannelFeatures::from_le_bytes(id_to_feature_flags(5)), 5);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[1], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 5,
+ timestamp: 1,
+ flags: 0,
+ cltv_expiry_delta: (5 << 8) | 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Absent,
+ fee_base_msat: 100,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[4], NodeFeatures::from_le_bytes(id_to_feature_flags(4)), 0);
+
+ add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], &privkeys[3], ChannelFeatures::from_le_bytes(id_to_feature_flags(4)), 4);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 4,
+ timestamp: 1,
+ flags: 0,
+ cltv_expiry_delta: (4 << 8) | 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, &privkeys[3], NodeFeatures::from_le_bytes(id_to_feature_flags(3)), 0);
+
+ add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[3], &privkeys[2], ChannelFeatures::from_le_bytes(id_to_feature_flags(3)), 3);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[3], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 3,
+ timestamp: 1,
+ flags: 0,
+ cltv_expiry_delta: (3 << 8) | 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, &privkeys[2], NodeFeatures::from_le_bytes(id_to_feature_flags(2)), 0);
+
+ add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], &privkeys[4], ChannelFeatures::from_le_bytes(id_to_feature_flags(2)), 2);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 2,
+ timestamp: 1,
+ flags: 0,
+ cltv_expiry_delta: (2 << 8) | 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Absent,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], &privkeys[6], ChannelFeatures::from_le_bytes(id_to_feature_flags(1)), 1);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 1,
+ timestamp: 1,
+ flags: 0,
+ cltv_expiry_delta: (1 << 8) | 0,
+ htlc_minimum_msat: 100,
+ 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, &privkeys[6], NodeFeatures::from_le_bytes(id_to_feature_flags(6)), 0);
+
+ {
+ // Now ensure the route flows simply over nodes 1 and 4 to 6.
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, None, &Vec::new(), 10_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ assert_eq!(route.paths[0].len(), 3);
+
+ assert_eq!(route.paths[0][0].pubkey, nodes[1]);
+ assert_eq!(route.paths[0][0].short_channel_id, 6);
+ assert_eq!(route.paths[0][0].fee_msat, 100);
+ assert_eq!(route.paths[0][0].cltv_expiry_delta, (5 << 8) | 0);
+ assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(1));
+ assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(6));
+
+ assert_eq!(route.paths[0][1].pubkey, nodes[4]);
+ assert_eq!(route.paths[0][1].short_channel_id, 5);
+ assert_eq!(route.paths[0][1].fee_msat, 0);
+ assert_eq!(route.paths[0][1].cltv_expiry_delta, (1 << 8) | 0);
+ assert_eq!(route.paths[0][1].node_features.le_flags(), &id_to_feature_flags(4));
+ assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(5));
+
+ assert_eq!(route.paths[0][2].pubkey, nodes[6]);
+ assert_eq!(route.paths[0][2].short_channel_id, 1);
+ assert_eq!(route.paths[0][2].fee_msat, 10_000);
+ assert_eq!(route.paths[0][2].cltv_expiry_delta, 42);
+ assert_eq!(route.paths[0][2].node_features.le_flags(), &id_to_feature_flags(6));
+ assert_eq!(route.paths[0][2].channel_features.le_flags(), &id_to_feature_flags(1));
+ }
+ }
+
+
+ #[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, net_graph_msg_handler, _, logger) = build_graph();
+ let (our_privkey, our_id, _, nodes) = get_nodes(&secp_ctx);
+
+ // 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 << 8) | 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, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 90_000, 42, Arc::clone(&logger)).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 << 8) | 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, net_graph_msg_handler, _, logger) = build_graph();
+ let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
+
+ // 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 << 8) | 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, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(InvoiceFeatures::known()), None, &Vec::new(), 90_000, 42, Arc::clone(&logger)).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 << 8) | 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));
+ }
+ }
+
+ use std::fs::File;
+ use util::ser::Readable;
+ /// Tries to open a network graph file, or panics with a URL to fetch it.
+ pub(super) fn get_route_file() -> Result<std::fs::File, std::io::Error> {
+ let res = File::open("net_graph-2021-02-12.bin") // By default we're run in RL/lightning
+ .or_else(|_| File::open("lightning/net_graph-2021-02-12.bin")) // We may be run manually in RL/
+ .or_else(|_| { // Fall back to guessing based on the binary location
+ // path is likely something like .../rust-lightning/target/debug/deps/lightning-...
+ let mut path = std::env::current_exe().unwrap();
+ path.pop(); // lightning-...
+ path.pop(); // deps
+ path.pop(); // debug
+ path.pop(); // target
+ path.push("lightning");
+ path.push("net_graph-2021-02-12.bin");
+ eprintln!("{}", path.to_str().unwrap());
+ File::open(path)
+ });
+ #[cfg(require_route_graph_test)]
+ return Ok(res.expect("Didn't have route graph and was configured to require it"));
+ #[cfg(not(require_route_graph_test))]
+ return res;
+ }
+
+ 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 std::hash::{BuildHasher, Hasher};
+ let seed = std::collections::hash_map::RandomState::new().build_hasher().finish();
+ println!("Using seed of {}", seed);
+ seed
+ }
+
+ #[test]
+ fn generate_routes() {
+ let mut d = match get_route_file() {
+ Ok(f) => f,
+ Err(_) => {
+ eprintln!("Please fetch https://bitcoin.ninja/ldk-net_graph-879e309c128-2020-02-12.bin and place it at lightning/net_graph-2021-02-12.bin");
+ return;
+ },
+ };
+ let graph = NetworkGraph::read(&mut d).unwrap();
+
+ // First, get 100 (source, destination) pairs for which route-getting actually succeeds...
+ let mut seed = random_init_seed() as usize;
+ 'load_endpoints: for _ in 0..10 {
+ loop {
+ seed = seed.overflowing_mul(0xdeadbeef).0;
+ let src = graph.get_nodes().keys().skip(seed % graph.get_nodes().len()).next().unwrap();
+ seed = seed.overflowing_mul(0xdeadbeef).0;
+ let dst = graph.get_nodes().keys().skip(seed % graph.get_nodes().len()).next().unwrap();
+ let amt = seed as u64 % 200_000_000;
+ if get_route(src, &graph, dst, None, None, &[], amt, 42, &test_utils::TestLogger::new()).is_ok() {
+ continue 'load_endpoints;
+ }
+ }
+ }
+ }
+
+ #[test]
+ fn generate_routes_mpp() {
+ let mut d = match get_route_file() {
+ Ok(f) => f,
+ Err(_) => {
+ eprintln!("Please fetch https://bitcoin.ninja/ldk-net_graph-879e309c128-2020-02-12.bin and place it at lightning/net_graph-2021-02-12.bin");
+ return;
+ },
+ };
+ let graph = NetworkGraph::read(&mut d).unwrap();
+
+ // First, get 100 (source, destination) pairs for which route-getting actually succeeds...
+ let mut seed = random_init_seed() as usize;
+ 'load_endpoints: for _ in 0..10 {
+ loop {
+ seed = seed.overflowing_mul(0xdeadbeef).0;
+ let src = graph.get_nodes().keys().skip(seed % graph.get_nodes().len()).next().unwrap();
+ seed = seed.overflowing_mul(0xdeadbeef).0;
+ let dst = graph.get_nodes().keys().skip(seed % graph.get_nodes().len()).next().unwrap();
+ let amt = seed as u64 % 200_000_000;
+ if get_route(src, &graph, dst, Some(InvoiceFeatures::known()), None, &[], amt, 42, &test_utils::TestLogger::new()).is_ok() {
+ continue 'load_endpoints;
+ }
+ }
+ }
+ }
+}
+
+#[cfg(all(test, feature = "unstable"))]
+mod benches {
+ use super::*;
+ use util::logger::{Logger, Record};
+
+ use test::Bencher;
+
+ struct DummyLogger {}
+ impl Logger for DummyLogger {
+ fn log(&self, _record: &Record) {}
+ }
+
+ #[bench]
+ fn generate_routes(bench: &mut Bencher) {
+ let mut d = tests::get_route_file()
+ .expect("Please fetch https://bitcoin.ninja/ldk-net_graph-879e309c128-2020-02-12.bin and place it at lightning/net_graph-2021-02-12.bin");
+ let graph = NetworkGraph::read(&mut d).unwrap();
+
+ // First, get 100 (source, destination) pairs for which route-getting actually succeeds...
+ let mut path_endpoints = Vec::new();
+ let mut seed: usize = 0xdeadbeef;
+ 'load_endpoints: for _ in 0..100 {
+ loop {
+ seed *= 0xdeadbeef;
+ let src = graph.get_nodes().keys().skip(seed % graph.get_nodes().len()).next().unwrap();
+ seed *= 0xdeadbeef;
+ let dst = graph.get_nodes().keys().skip(seed % graph.get_nodes().len()).next().unwrap();
+ let amt = seed as u64 % 1_000_000;
+ if get_route(src, &graph, dst, None, None, &[], amt, 42, &DummyLogger{}).is_ok() {
+ path_endpoints.push((src, dst, amt));
+ continue 'load_endpoints;
+ }
+ }
+ }
+
+ // ...then benchmark finding paths between the nodes we learned.
+ let mut idx = 0;
+ bench.iter(|| {
+ let (src, dst, amt) = path_endpoints[idx % path_endpoints.len()];
+ assert!(get_route(src, &graph, dst, None, None, &[], amt, 42, &DummyLogger{}).is_ok());
+ idx += 1;
+ });
+ }
+
+ #[bench]
+ fn generate_mpp_routes(bench: &mut Bencher) {
+ let mut d = tests::get_route_file()
+ .expect("Please fetch https://bitcoin.ninja/ldk-net_graph-879e309c128-2020-02-12.bin and place it at lightning/net_graph-2021-02-12.bin");
+ let graph = NetworkGraph::read(&mut d).unwrap();
+
+ // First, get 100 (source, destination) pairs for which route-getting actually succeeds...
+ let mut path_endpoints = Vec::new();
+ let mut seed: usize = 0xdeadbeef;
+ 'load_endpoints: for _ in 0..100 {
+ loop {
+ seed *= 0xdeadbeef;
+ let src = graph.get_nodes().keys().skip(seed % graph.get_nodes().len()).next().unwrap();
+ seed *= 0xdeadbeef;
+ let dst = graph.get_nodes().keys().skip(seed % graph.get_nodes().len()).next().unwrap();
+ let amt = seed as u64 % 1_000_000;
+ if get_route(src, &graph, dst, Some(InvoiceFeatures::known()), None, &[], amt, 42, &DummyLogger{}).is_ok() {
+ path_endpoints.push((src, dst, amt));
+ continue 'load_endpoints;
+ }
+ }
+ }
+
+ // ...then benchmark finding paths between the nodes we learned.
+ let mut idx = 0;
+ bench.iter(|| {
+ let (src, dst, amt) = path_endpoints[idx % path_endpoints.len()];
+ assert!(get_route(src, &graph, dst, Some(InvoiceFeatures::known()), None, &[], amt, 42, &DummyLogger{}).is_ok());
+ idx += 1;
+ });
+ }