+
+ #[test]
+ fn overflow_unannounced_path_test_liquidity_underflow() {
+ // Previously, when we had a last-hop hint connected directly to a first-hop channel, where
+ // the last-hop had a fee which overflowed a u64, we'd panic.
+ // This was due to us adding the first-hop from us unconditionally, causing us to think
+ // we'd built a path (as our node is in the "best candidate" set), when we had not.
+ // In this test, we previously hit a subtraction underflow due to having less available
+ // liquidity at the last hop than 0.
+ assert!(do_unannounced_path_test(Some(21_000_000_0000_0000_000), 0, 21_000_000_0000_0000_000, 21_000_000_0000_0000_000).is_err());
+ }
+
+ #[test]
+ fn overflow_unannounced_path_test_feerate_overflow() {
+ // This tests for the same case as above, except instead of hitting a subtraction
+ // underflow, we hit a case where the fee charged at a hop overflowed.
+ assert!(do_unannounced_path_test(Some(21_000_000_0000_0000_000), 50000, 21_000_000_0000_0000_000, 21_000_000_0000_0000_000).is_err());
+ }
+
+ #[test]
+ fn available_amount_while_routing_test() {
+ // Tests whether we choose the correct available channel amount while routing.
+
+ let (secp_ctx, network_graph, mut net_graph_msg_handler, chain_monitor, 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 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, &payment_params, &network_graph, None, 250_000_001, 42, Arc::clone(&logger), &scorer) {
+ 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, &payment_params, &network_graph, None, 250_000_000, 42, Arc::clone(&logger), &scorer).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![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.
+ if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(
+ &our_id, &payment_params, &network_graph, Some(&our_chans.iter().collect::<Vec<_>>()), 200_000_001, 42, Arc::clone(&logger), &scorer) {
+ 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, &payment_params, &network_graph, Some(&our_chans.iter().collect::<Vec<_>>()), 200_000_000, 42, Arc::clone(&logger), &scorer).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, &payment_params, &network_graph, None, 15_001, 42, Arc::clone(&logger), &scorer) {
+ 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, &payment_params, &network_graph, None, 15_000, 42, Arc::clone(&logger), &scorer).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 << 4) | 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 << 4) | 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, &payment_params, &network_graph, None, 15_001, 42, Arc::clone(&logger), &scorer) {
+ 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, &payment_params, &network_graph, None, 15_000, 42, Arc::clone(&logger), &scorer).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, &payment_params, &network_graph, None, 10_001, 42, Arc::clone(&logger), &scorer) {
+ 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, &payment_params, &network_graph, None, 10_000, 42, Arc::clone(&logger), &scorer).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, 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[3]).with_features(InvoiceFeatures::known());
+
+ // 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, &payment_params, &network_graph, None, 60_000, 42, Arc::clone(&logger), &scorer) {
+ 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, &payment_params, &network_graph, None, 49_000, 42, Arc::clone(&logger), &scorer).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, &payment_params, &network_graph, None, 50_000, 42, Arc::clone(&logger), &scorer).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, 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]);
+
+ // 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, &payment_params, &network_graph, None, 50_000, 42, Arc::clone(&logger), &scorer).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, 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 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, &payment_params, &network_graph, None, 300_000, 42, Arc::clone(&logger), &scorer) {
+ 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, &payment_params, &network_graph, None, 250_000, 42, Arc::clone(&logger), &scorer).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, &payment_params, &network_graph, None, 290_000, 42, Arc::clone(&logger), &scorer).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, 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[3]).with_features(InvoiceFeatures::known());
+
+ // 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, &payment_params, &network_graph, None, 350_000, 42, Arc::clone(&logger), &scorer) {
+ 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, &payment_params, &network_graph, None, 300_000, 42, Arc::clone(&logger), &scorer).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, 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[3]).with_features(InvoiceFeatures::known());
+
+ // 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, &payment_params, &network_graph, None, 180_000, 42, Arc::clone(&logger), &scorer).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, 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[3]).with_features(InvoiceFeatures::known());
+
+ // 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, &payment_params, &network_graph, None, 210_000, 42, Arc::clone(&logger), &scorer) {
+ 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, &payment_params, &network_graph, None, 200_000, 42, Arc::clone(&logger), &scorer).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);
+ assert_eq!(route.get_total_fees(), 150_000);
+ }
+ }
+
+ #[test]
+ fn mpp_with_last_hops() {
+ // Previously, if we tried to send an MPP payment to a destination which was only reachable
+ // via a single last-hop route hint, we'd fail to route if we first collected routes
+ // totaling close but not quite enough to fund the full payment.
+ //
+ // This was because we considered last-hop hints to have exactly the sought payment amount
+ // instead of the amount we were trying to collect, needlessly limiting our path searching
+ // at the very first hop.
+ //
+ // Specifically, this interacted with our "all paths must fund at least 5% of total target"
+ // criterion to cause us to refuse all routes at the last hop hint which would be considered
+ // to only have the remaining to-collect amount in available liquidity.
+ //
+ // This bug appeared in production in some specific channel configurations.
+ 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(PublicKey::from_slice(&[02; 33]).unwrap()).with_features(InvoiceFeatures::known())
+ .with_route_hints(vec![RouteHint(vec![RouteHintHop {
+ src_node_id: nodes[2],
+ short_channel_id: 42,
+ fees: RoutingFees { base_msat: 0, proportional_millionths: 0 },
+ cltv_expiry_delta: 42,
+ htlc_minimum_msat: None,
+ htlc_maximum_msat: None,
+ }])]);
+
+ // Keep only two paths from us to nodes[2], both with a 99sat HTLC maximum, with one with
+ // no fee and one with a 1msat fee. Previously, trying to route 100 sats to nodes[2] here
+ // would first use the no-fee route and then fail to find a path along the second route as
+ // we think we can only send up to 1 additional sat over the last-hop but refuse to as its
+ // under 5% of our payment amount.
+ 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: (5 << 4) | 5,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(99_000),
+ fee_base_msat: u32::max_value(),
+ fee_proportional_millionths: u32::max_value(),
+ 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: 2,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: (5 << 4) | 3,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(99_000),
+ fee_base_msat: u32::max_value(),
+ fee_proportional_millionths: u32::max_value(),
+ 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: 0,
+ htlc_maximum_msat: OptionalField::Absent,
+ fee_base_msat: 1,
+ 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|2, // Channel disabled
+ cltv_expiry_delta: (13 << 4) | 1,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Absent,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 2000000,
+ excess_data: Vec::new()
+ });
+
+ // Get a route for 100 sats and check that we found the MPP route no problem and didn't
+ // overpay at all.
+ let route = get_route(&our_id, &payment_params, &network_graph, None, 100_000, 42, Arc::clone(&logger), &scorer).unwrap();
+ assert_eq!(route.paths.len(), 2);
+ // Paths are somewhat randomly ordered, but:
+ // * the first is channel 2 (1 msat fee) -> channel 4 -> channel 42
+ // * the second is channel 1 (0 fee, but 99 sat maximum) -> channel 3 -> channel 42
+ assert_eq!(route.paths[0][0].short_channel_id, 2);
+ assert_eq!(route.paths[0][0].fee_msat, 1);
+ assert_eq!(route.paths[0][2].fee_msat, 1_000);
+ assert_eq!(route.paths[1][0].short_channel_id, 1);
+ assert_eq!(route.paths[1][0].fee_msat, 0);
+ assert_eq!(route.paths[1][2].fee_msat, 99_000);
+ assert_eq!(route.get_total_fees(), 1);
+ assert_eq!(route.get_total_amount(), 100_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, 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 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, &payment_params, &network_graph, None, 150_000, 42, Arc::clone(&logger), &scorer) {
+ 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, &payment_params, &network_graph, None, 125_000, 42, Arc::clone(&logger), &scorer).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, &payment_params, &network_graph, None, 90_000, 42, Arc::clone(&logger), &scorer).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 network_graph = Arc::new(NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash()));
+ let net_graph_msg_handler = NetGraphMsgHandler::new(Arc::clone(&network_graph), None, Arc::clone(&logger));
+ 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[6]);
+
+ 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 << 4) | 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 << 4) | 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 << 4) | 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 << 4) | 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 << 4) | 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 << 4) | 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, &payment_params, &network_graph, None, 10_000, 42, Arc::clone(&logger), &scorer).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 << 4) | 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 << 4) | 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, 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;
+ },
+ };
+ 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;
+ let nodes = graph.read_only().nodes().clone();
+ 'load_endpoints: for _ in 0..10 {
+ loop {
+ seed = seed.overflowing_mul(0xdeadbeef).0;
+ let src = &PublicKey::from_slice(nodes.keys().skip(seed % nodes.len()).next().unwrap().as_slice()).unwrap();
+ seed = seed.overflowing_mul(0xdeadbeef).0;
+ let dst = PublicKey::from_slice(nodes.keys().skip(seed % nodes.len()).next().unwrap().as_slice()).unwrap();
+ let payment_params = PaymentParameters::from_node_id(dst);
+ let amt = seed as u64 % 200_000_000;
+ let params = ProbabilisticScoringParameters::default();
+ let scorer = ProbabilisticScorer::new(params, &graph);
+ if get_route(src, &payment_params, &graph, None, amt, 42, &test_utils::TestLogger::new(), &scorer).is_ok() {
+ continue 'load_endpoints;
+ }
+ }
+ }
+ }
+
+ #[test]
+ #[cfg(not(feature = "no-std"))]
+ fn generate_routes_mpp() {
+ let mut d = match super::test_utils::get_route_file() {
+ Ok(f) => f,
+ Err(e) => {
+ eprintln!("{}", e);
+ 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;
+ let nodes = graph.read_only().nodes().clone();
+ 'load_endpoints: for _ in 0..10 {
+ loop {
+ seed = seed.overflowing_mul(0xdeadbeef).0;
+ let src = &PublicKey::from_slice(nodes.keys().skip(seed % nodes.len()).next().unwrap().as_slice()).unwrap();
+ seed = seed.overflowing_mul(0xdeadbeef).0;
+ let dst = PublicKey::from_slice(nodes.keys().skip(seed % nodes.len()).next().unwrap().as_slice()).unwrap();
+ let payment_params = PaymentParameters::from_node_id(dst).with_features(InvoiceFeatures::known());
+ let amt = seed as u64 % 200_000_000;
+ let params = ProbabilisticScoringParameters::default();
+ let scorer = ProbabilisticScorer::new(params, &graph);
+ if get_route(src, &payment_params, &graph, None, amt, 42, &test_utils::TestLogger::new(), &scorer).is_ok() {
+ continue 'load_endpoints;
+ }
+ }
+ }
+ }
+}
+
+#[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.
+ pub(crate) fn get_route_file() -> Result<std::fs::File, &'static str> {
+ let res = File::open("net_graph-2021-05-31.bin") // By default we're run in RL/lightning
+ .or_else(|_| File::open("lightning/net_graph-2021-05-31.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-05-31.bin");
+ eprintln!("{}", path.to_str().unwrap());
+ File::open(path)
+ })
+ .map_err(|_| "Please fetch https://bitcoin.ninja/ldk-net_graph-v0.0.15-2021-05-31.bin and place it at lightning/net_graph-2021-05-31.bin");
+ #[cfg(require_route_graph_test)]
+ return Ok(res.unwrap());
+ #[cfg(not(require_route_graph_test))]
+ return res;
+ }
+}
+
+#[cfg(all(test, feature = "_bench_unstable", not(feature = "no-std")))]
+mod benches {
+ use super::*;
+ use bitcoin::hashes::Hash;
+ use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey};
+ use chain::transaction::OutPoint;
+ use ln::channelmanager::{ChannelCounterparty, ChannelDetails};
+ use ln::features::{InitFeatures, InvoiceFeatures};
+ use routing::scoring::{FixedPenaltyScorer, ProbabilisticScorer, ProbabilisticScoringParameters, Scorer};
+ use util::logger::{Logger, Record};
+
+ use test::Bencher;
+
+ struct DummyLogger {}
+ impl Logger for DummyLogger {
+ fn log(&self, _record: &Record) {}
+ }
+
+ fn read_network_graph() -> NetworkGraph {
+ let mut d = test_utils::get_route_file().unwrap();
+ NetworkGraph::read(&mut d).unwrap()
+ }
+
+ fn payer_pubkey() -> PublicKey {
+ let secp_ctx = Secp256k1::new();
+ PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&[42; 32]).unwrap())
+ }
+
+ #[inline]
+ fn first_hop(node_id: PublicKey) -> ChannelDetails {
+ ChannelDetails {
+ channel_id: [0; 32],
+ counterparty: ChannelCounterparty {
+ features: InitFeatures::known(),
+ 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: Some(1),
+ channel_value_satoshis: 10_000_000,
+ user_channel_id: 0,
+ balance_msat: 10_000_000,
+ outbound_capacity_msat: 10_000_000,
+ inbound_capacity_msat: 0,
+ 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,
+ }
+ }
+
+ #[bench]
+ fn generate_routes_with_zero_penalty_scorer(bench: &mut Bencher) {
+ let network_graph = read_network_graph();
+ let scorer = FixedPenaltyScorer::with_penalty(0);
+ generate_routes(bench, &network_graph, scorer, InvoiceFeatures::empty());
+ }
+
+ #[bench]
+ fn generate_mpp_routes_with_zero_penalty_scorer(bench: &mut Bencher) {
+ let network_graph = read_network_graph();
+ let scorer = FixedPenaltyScorer::with_penalty(0);
+ generate_routes(bench, &network_graph, scorer, InvoiceFeatures::known());
+ }
+
+ #[bench]
+ fn generate_routes_with_default_scorer(bench: &mut Bencher) {
+ let network_graph = read_network_graph();
+ let scorer = Scorer::default();
+ generate_routes(bench, &network_graph, scorer, InvoiceFeatures::empty());
+ }
+
+ #[bench]
+ fn generate_mpp_routes_with_default_scorer(bench: &mut Bencher) {
+ let network_graph = read_network_graph();
+ let scorer = Scorer::default();
+ generate_routes(bench, &network_graph, scorer, InvoiceFeatures::known());
+ }
+
+ #[bench]
+ fn generate_routes_with_probabilistic_scorer(bench: &mut Bencher) {
+ let network_graph = read_network_graph();
+ let params = ProbabilisticScoringParameters::default();
+ let scorer = ProbabilisticScorer::new(params, &network_graph);
+ generate_routes(bench, &network_graph, scorer, InvoiceFeatures::empty());
+ }
+
+ #[bench]
+ fn generate_mpp_routes_with_probabilistic_scorer(bench: &mut Bencher) {
+ let network_graph = read_network_graph();
+ let params = ProbabilisticScoringParameters::default();
+ let scorer = ProbabilisticScorer::new(params, &network_graph);
+ generate_routes(bench, &network_graph, scorer, InvoiceFeatures::known());
+ }
+
+ fn generate_routes<S: Score>(
+ bench: &mut Bencher, graph: &NetworkGraph, mut scorer: S, features: InvoiceFeatures
+ ) {
+ let nodes = graph.read_only().nodes().clone();
+ let payer = payer_pubkey();
+
+ // First, get 100 (source, destination) pairs for which route-getting actually succeeds...
+ let mut routes = Vec::new();
+ let mut route_endpoints = Vec::new();
+ let mut seed: usize = 0xdeadbeef;
+ 'load_endpoints: for _ in 0..100 {
+ loop {
+ seed *= 0xdeadbeef;
+ let src = PublicKey::from_slice(nodes.keys().skip(seed % nodes.len()).next().unwrap().as_slice()).unwrap();
+ seed *= 0xdeadbeef;
+ let dst = PublicKey::from_slice(nodes.keys().skip(seed % nodes.len()).next().unwrap().as_slice()).unwrap();
+ let params = PaymentParameters::from_node_id(dst).with_features(features.clone());
+ let first_hop = first_hop(src);
+ let amt = seed as u64 % 1_000_000;
+ if let Ok(route) = get_route(&payer, ¶ms, &graph, Some(&[&first_hop]), amt, 42, &DummyLogger{}, &scorer) {
+ routes.push(route);
+ route_endpoints.push((first_hop, params, amt));
+ continue 'load_endpoints;
+ }
+ }
+ }
+
+ // ...and seed the scorer with success and failure data...
+ for route in routes {
+ let amount = route.get_total_amount();
+ if amount < 250_000 {
+ for path in route.paths {
+ scorer.payment_path_successful(&path.iter().collect::<Vec<_>>());
+ }
+ } else if amount > 750_000 {
+ for path in route.paths {
+ let short_channel_id = path[path.len() / 2].short_channel_id;
+ scorer.payment_path_failed(&path.iter().collect::<Vec<_>>(), short_channel_id);
+ }
+ }
+ }
+
+ // ...then benchmark finding paths between the nodes we learned.
+ let mut idx = 0;
+ bench.iter(|| {
+ let (first_hop, params, amt) = &route_endpoints[idx % route_endpoints.len()];
+ assert!(get_route(&payer, params, &graph, Some(&[first_hop]), *amt, 42, &DummyLogger{}, &scorer).is_ok());
+ idx += 1;
+ });
+ }