impl cmp::Ord for RouteGraphNode {
fn cmp(&self, other: &RouteGraphNode) -> cmp::Ordering {
- other.lowest_fee_to_peer_through_node.cmp(&self.lowest_fee_to_peer_through_node)
- .then_with(|| other.pubkey.serialize().cmp(&self.pubkey.serialize()))
+ let other_score = cmp::max(other.lowest_fee_to_peer_through_node, other.path_htlc_minimum_msat);
+ let self_score = cmp::max(self.lowest_fee_to_peer_through_node, self.path_htlc_minimum_msat);
+ other_score.cmp(&self_score).then_with(|| other.pubkey.serialize().cmp(&self.pubkey.serialize()))
}
}
/// we don't fall below the minimum. Should not be updated manually and
/// generally should not be accessed.
htlc_minimum_msat: u64,
+ /// A mirror of the same field in RouteGraphNode. Note that this is only used during the graph
+ /// walk and may be invalid thereafter.
+ path_htlc_minimum_msat: u64,
}
// Instantiated with a list of hops with correct data in them collected during path finding,
hop_use_fee_msat: u64::max_value(),
total_fee_msat: u64::max_value(),
htlc_minimum_msat: $directional_info.htlc_minimum_msat,
+ path_htlc_minimum_msat,
}
});
// 1 BTC. Now, since the latter is more expensive, we gonna try to cut it
// by 0.5 BTC, but then match htlc_minimum_msat by paying a fee of 0.5 BTC
// to this channel.
- // TODO: this scoring could be smarter (e.g. 0.5*htlc_minimum_msat here).
- let mut old_cost = old_entry.total_fee_msat;
- if let Some(increased_old_cost) = old_cost.checked_add(old_entry.htlc_minimum_msat) {
- old_cost = increased_old_cost;
- } else {
- old_cost = u64::max_value();
- }
-
- let mut new_cost = total_fee_msat;
- if let Some(increased_new_cost) = new_cost.checked_add($directional_info.htlc_minimum_msat) {
- new_cost = increased_new_cost;
- } else {
- new_cost = u64::max_value();
- }
+ // Ideally the scoring could be smarter (e.g. 0.5*htlc_minimum_msat here),
+ // but it may require additional tracking - we don't want to double-count
+ // the fees included in $next_hops_path_htlc_minimum_msat, but also
+ // can't use something that may decrease on future hops.
+ let old_cost = cmp::max(old_entry.total_fee_msat, old_entry.path_htlc_minimum_msat);
+ let new_cost = cmp::max(total_fee_msat, path_htlc_minimum_msat);
if new_cost < old_cost {
targets.push(new_graph_node);
cltv_expiry_delta: $directional_info.cltv_expiry_delta as u32,
};
old_entry.channel_fees = $directional_info.fees;
- // It's probably fine to replace the old entry, because the new one
- // passed the htlc_minimum-related checks above.
old_entry.htlc_minimum_msat = $directional_info.htlc_minimum_msat;
+ old_entry.path_htlc_minimum_msat = path_htlc_minimum_msat;
}
}
}
// on some channels we already passed (assuming dest->source direction). Here, we
// recompute the fees again, so that if that's the case, we match the currently
// underpaid htlc_minimum_msat with fees.
- payment_path.update_value_and_recompute_fees(value_contribution_msat);
+ payment_path.update_value_and_recompute_fees(cmp::min(value_contribution_msat, final_value_msat));
// Since a path allows to transfer as much value as
// the smallest channel it has ("bottleneck"), we should recompute
// might have been computed considering a larger value.
// Remember that we used these channels so that we don't rely
// on the same liquidity in future paths.
+ let mut prevented_redundant_path_selection = false;
for payment_hop in payment_path.hops.iter() {
let channel_liquidity_available_msat = bookkeeped_channels_liquidity_available_msat.get_mut(&payment_hop.route_hop.short_channel_id).unwrap();
let mut spent_on_hop_msat = value_contribution_msat;
// trying to avoid cases when a hop is not usable due to the fee situation.
break 'path_construction;
}
+ if spent_on_hop_msat == *channel_liquidity_available_msat {
+ // If this path used all of this channel's available liquidity, we know
+ // this path will not be selected again in the next loop iteration.
+ prevented_redundant_path_selection = true;
+ }
*channel_liquidity_available_msat -= spent_on_hop_msat;
}
+ if !prevented_redundant_path_selection {
+ // If we weren't capped by hitting a liquidity limit on a channel in the path,
+ // we'll probably end up picking the same path again on the next iteration.
+ // Decrease the available liquidity of a hop in the middle of the path.
+ let victim_liquidity = bookkeeped_channels_liquidity_available_msat.get_mut(
+ &payment_path.hops[(payment_path.hops.len() - 1) / 2].route_hop.short_channel_id).unwrap();
+ *victim_liquidity = 0;
+ }
+
// Track the total amount all our collected paths allow to send so that we:
// - know when to stop looking for more paths
// - know which of the hops are useless considering how much more sats we need
}
}
+ #[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
projects / rust-lightning / blobdiff