// - how much is needed for a path being constructed
// - how much value can channels following this node (up to the destination) can contribute,
// considering their capacity and fees
- value_contribution_msat: u64
+ value_contribution_msat: u64,
+ /// The effective htlc_minimum_msat at this hop. If a later hop on the path had a higher HTLC
+ /// minimum, we use it, plus the fees required at each earlier hop to meet it.
+ path_htlc_minimum_msat: u64,
}
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,
// 8. Choose the best route by the lowest total fee.
// As for the actual search algorithm,
- // we do a payee-to-payer Dijkstra's sorting by each node's distance from the payee
- // plus the minimum per-HTLC fee to get from it to another node (aka "shitty A*").
+ // we do a payee-to-payer pseudo-Dijkstra's sorting by each node's distance from the payee
+ // plus the minimum per-HTLC fee to get from it to another node (aka "shitty pseudo-A*").
+ //
+ // We are not a faithful Dijkstra's implementation because we can change values which impact
+ // earlier nodes while processing later nodes. Specifically, if we reach a channel with a lower
+ // liquidity limit (via htlc_maximum_msat, on-chain capacity or assumed liquidity limits) then
+ // the value we are currently attempting to send over a path, we simply reduce the value being
+ // sent along the path for any hops after that channel. This may imply that later fees (which
+ // we've already tabulated) are lower because a smaller value is passing through the channels
+ // (and the proportional fee is thus lower). There isn't a trivial way to recalculate the
+ // channels which were selected earlier (and which may still be used for other paths without a
+ // lower liquidity limit), so we simply accept that some liquidity-limited paths may be
+ // de-preferenced.
+ //
+ // One potentially problematic case for this algorithm would be if there are many
+ // liquidity-limited paths which are liquidity-limited near the destination (ie early in our
+ // graph walking), we may never find a path which is not liquidity-limited and has lower
+ // proportional fee (and only lower absolute fee when considering the ultimate value sent).
+ // Because we only consider paths with at least 5% of the total value being sent, the damage
+ // from such a case should be limited, however this could be further reduced in the future by
+ // calculating fees on the amount we wish to route over a path, ie ignoring the liquidity
+ // limits for the purposes of fee calculation.
+ //
+ // Alternatively, we could store more detailed path information in the heap (targets, below)
+ // and index the best-path map (dist, below) by node *and* HTLC limits, however that would blow
+ // up the runtime significantly both algorithmically (as we'd traverse nodes multiple times)
+ // and practically (as we would need to store dynamically-allocated path information in heap
+ // objects, increasing malloc traffic and indirect memory access significantly). Further, the
+ // results of such an algorithm would likely be biased towards lower-value paths.
+ //
+ // Further, we could return to a faithful Dijkstra's algorithm by rejecting paths with limits
+ // outside of our current search value, running a path search more times to gather candidate
+ // paths at different values. While this may be acceptable, further path searches may increase
+ // runtime for little gain. Specifically, the current algorithm rather efficiently explores the
+ // graph for candidate paths, calculating the maximum value which can realistically be sent at
+ // the same time, remaining generic across different payment values.
+ //
// TODO: There are a few tweaks we could do, including possibly pre-calculating more stuff
// to use as the A* heuristic beyond just the cost to get one node further than the current
// one.
let mut targets = BinaryHeap::new(); //TODO: Do we care about switching to eg Fibbonaci heap?
let mut dist = HashMap::with_capacity(network.get_nodes().len());
+ // During routing, if we ignore a path due to an htlc_minimum_msat limit, we set this,
+ // indicating that we may wish to try again with a higher value, potentially paying to meet an
+ // htlc_minimum with extra fees while still finding a cheaper path.
+ let mut hit_minimum_limit;
+
// When arranging a route, we select multiple paths so that we can make a multi-path payment.
- // Don't stop searching for paths when we think they're
- // sufficient to transfer a given value aggregately.
- // Search for higher value, so that we collect many more paths,
- // and then select the best combination among them.
+ // We start with a path_value of the exact amount we want, and if that generates a route we may
+ // return it immediately. Otherwise, we don't stop searching for paths until we have 3x the
+ // amount we want in total across paths, selecting the best subset at the end.
const ROUTE_CAPACITY_PROVISION_FACTOR: u64 = 3;
let recommended_value_msat = final_value_msat * ROUTE_CAPACITY_PROVISION_FACTOR as u64;
+ let mut path_value_msat = final_value_msat;
// Allow MPP only if we have a features set from somewhere that indicates the payee supports
// it. If the payee supports it they're supposed to include it in the invoice, so that should
// $next_hops_fee_msat represents the fees paid for using all the channel *after* this one,
// since that value has to be transferred over this channel.
( $chan_id: expr, $src_node_id: expr, $dest_node_id: expr, $directional_info: expr, $capacity_sats: expr, $chan_features: expr, $next_hops_fee_msat: expr,
- $next_hops_value_contribution: expr ) => {
+ $next_hops_value_contribution: expr, $next_hops_path_htlc_minimum_msat: expr ) => {
// Channels to self should not be used. This is more of belt-and-suspenders, because in
// practice these cases should be caught earlier:
// - for regular channels at channel announcement (TODO)
// Can't overflow due to how the values were computed right above.
None => unreachable!(),
};
+ #[allow(unused_comparisons)] // $next_hops_path_htlc_minimum_msat is 0 in some calls so rustc complains
+ let over_path_minimum_msat = amount_to_transfer_over_msat >= $directional_info.htlc_minimum_msat &&
+ amount_to_transfer_over_msat >= $next_hops_path_htlc_minimum_msat;
// If HTLC minimum is larger than the amount we're going to transfer, we shouldn't
// bother considering this channel.
// Since we're choosing amount_to_transfer_over_msat as maximum possible, it can
// be only reduced later (not increased), so this channel should just be skipped
// as not sufficient.
- // TODO: Explore simply adding fee to hit htlc_minimum_msat
- if contributes_sufficient_value && amount_to_transfer_over_msat >= $directional_info.htlc_minimum_msat {
+ if !over_path_minimum_msat {
+ hit_minimum_limit = true;
+ } else if contributes_sufficient_value {
// Note that low contribution here (limited by available_liquidity_msat)
// might violate htlc_minimum_msat on the hops which are next along the
// payment path (upstream to the payee). To avoid that, we recompute path
// path fees knowing the final path contribution after constructing it.
+ let path_htlc_minimum_msat = match compute_fees($next_hops_path_htlc_minimum_msat, $directional_info.fees)
+ .map(|fee_msat| fee_msat.checked_add($next_hops_path_htlc_minimum_msat)) {
+ Some(Some(value_msat)) => cmp::max(value_msat, $directional_info.htlc_minimum_msat),
+ _ => u64::max_value()
+ };
let hm_entry = dist.entry(&$src_node_id);
let old_entry = hm_entry.or_insert_with(|| {
// If there was previously no known way to access
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,
}
});
lowest_fee_to_peer_through_node: total_fee_msat,
lowest_fee_to_node: $next_hops_fee_msat as u64 + hop_use_fee_msat,
value_contribution_msat: value_contribution_msat,
+ path_htlc_minimum_msat,
};
// Update the way of reaching $src_node_id with the given $chan_id (from $dest_node_id),
// 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;
}
}
}
// meaning how much will be paid in fees after this node (to the best of our knowledge).
// This data can later be helpful to optimize routing (pay lower fees).
macro_rules! add_entries_to_cheapest_to_target_node {
- ( $node: expr, $node_id: expr, $fee_to_target_msat: expr, $next_hops_value_contribution: expr ) => {
+ ( $node: expr, $node_id: expr, $fee_to_target_msat: expr, $next_hops_value_contribution: expr, $next_hops_path_htlc_minimum_msat: expr ) => {
if first_hops.is_some() {
if let Some(&(ref first_hop, ref features, ref outbound_capacity_msat)) = first_hop_targets.get(&$node_id) {
- add_entry!(first_hop, *our_node_id, $node_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), $fee_to_target_msat, $next_hops_value_contribution);
+ add_entry!(first_hop, *our_node_id, $node_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), $fee_to_target_msat, $next_hops_value_contribution, $next_hops_path_htlc_minimum_msat);
}
}
if first_hops.is_none() || chan.node_two != *our_node_id {
if let Some(two_to_one) = chan.two_to_one.as_ref() {
if two_to_one.enabled {
- add_entry!(chan_id, chan.node_two, chan.node_one, two_to_one, chan.capacity_sats, chan.features, $fee_to_target_msat, $next_hops_value_contribution);
+ add_entry!(chan_id, chan.node_two, chan.node_one, two_to_one, chan.capacity_sats, chan.features, $fee_to_target_msat, $next_hops_value_contribution, $next_hops_path_htlc_minimum_msat);
}
}
}
if first_hops.is_none() || chan.node_one != *our_node_id {
if let Some(one_to_two) = chan.one_to_two.as_ref() {
if one_to_two.enabled {
- add_entry!(chan_id, chan.node_one, chan.node_two, one_to_two, chan.capacity_sats, chan.features, $fee_to_target_msat, $next_hops_value_contribution);
+ add_entry!(chan_id, chan.node_one, chan.node_two, one_to_two, chan.capacity_sats, chan.features, $fee_to_target_msat, $next_hops_value_contribution, $next_hops_path_htlc_minimum_msat);
}
}
// the further iterations of path finding. Also don't erase first_hop_targets.
targets.clear();
dist.clear();
+ hit_minimum_limit = false;
// If first hop is a private channel and the only way to reach the payee, this is the only
// place where it could be added.
if first_hops.is_some() {
if let Some(&(ref first_hop, ref features, ref outbound_capacity_msat)) = first_hop_targets.get(&payee) {
- add_entry!(first_hop, *our_node_id, payee, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, recommended_value_msat);
+ add_entry!(first_hop, *our_node_id, payee, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, path_value_msat, 0);
}
}
// If not, targets.pop() will not even let us enter the loop in step 2.
None => {},
Some(node) => {
- add_entries_to_cheapest_to_target_node!(node, payee, 0, recommended_value_msat);
+ add_entries_to_cheapest_to_target_node!(node, payee, 0, path_value_msat, 0);
},
}
// bit lazy here. In the future, we should pull them out via our
// ChannelManager, but there's no reason to waste the space until we
// need them.
- add_entry!(first_hop, *our_node_id , hop.src_node_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, recommended_value_msat);
+ add_entry!(first_hop, *our_node_id , hop.src_node_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, path_value_msat, 0);
true
} else {
// In any other case, only add the hop if the source is in the regular network
htlc_maximum_msat: hop.htlc_maximum_msat,
fees: hop.fees,
};
- add_entry!(hop.short_channel_id, hop.src_node_id, payee, directional_info, None::<u64>, ChannelFeatures::empty(), 0, recommended_value_msat);
+ add_entry!(hop.short_channel_id, hop.src_node_id, payee, directional_info, None::<u64>, ChannelFeatures::empty(), 0, path_value_msat, 0);
}
}
// Both these cases (and other cases except reaching recommended_value_msat) mean that
// paths_collection will be stopped because found_new_path==false.
// This is not necessarily a routing failure.
- 'path_construction: while let Some(RouteGraphNode { pubkey, lowest_fee_to_node, value_contribution_msat, .. }) = targets.pop() {
+ 'path_construction: while let Some(RouteGraphNode { pubkey, lowest_fee_to_node, value_contribution_msat, path_htlc_minimum_msat, .. }) = targets.pop() {
// Since we're going payee-to-payer, hitting our node as a target means we should stop
// traversing the graph and arrange the path out of what we found.
// 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
match network.get_nodes().get(&pubkey) {
None => {},
Some(node) => {
- add_entries_to_cheapest_to_target_node!(node, &pubkey, lowest_fee_to_node, value_contribution_msat);
+ add_entries_to_cheapest_to_target_node!(node, &pubkey, lowest_fee_to_node, value_contribution_msat, path_htlc_minimum_msat);
},
}
}
}
// Step (3).
- // Stop either when recommended value is reached,
- // or if during last iteration no new path was found.
- // In the latter case, making another path finding attempt could not help,
- // because we deterministically terminate the search due to low liquidity.
+ // Stop either when the recommended value is reached or if no new path was found in this
+ // iteration.
+ // In the latter case, making another path finding attempt won't help,
+ // because we deterministically terminated the search due to low liquidity.
if already_collected_value_msat >= recommended_value_msat || !found_new_path {
break 'paths_collection;
+ } else if found_new_path && already_collected_value_msat == final_value_msat && payment_paths.len() == 1 {
+ // Further, if this was our first walk of the graph, and we weren't limited by an
+ // htlc_minimum_msat, return immediately because this path should suffice. If we were
+ // limited by an htlc_minimum_msat value, find another path with a higher value,
+ // potentially allowing us to pay fees to meet the htlc_minimum on the new path while
+ // still keeping a lower total fee than this path.
+ if !hit_minimum_limit {
+ break 'paths_collection;
+ }
+ path_value_msat = recommended_value_msat;
}
}
outbound_capacity_msat: 100000,
inbound_capacity_msat: 100000,
is_live: true,
+ counterparty_forwarding_info: None,
}];
if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)) {
outbound_capacity_msat: 250_000_000,
inbound_capacity_msat: 0,
is_live: true,
+ counterparty_forwarding_info: None,
}];
let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths[0].len(), 2);
outbound_capacity_msat: 250_000_000,
inbound_capacity_msat: 0,
is_live: true,
+ counterparty_forwarding_info: None,
}];
let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths[0].len(), 2);
outbound_capacity_msat: 250_000_000,
inbound_capacity_msat: 0,
is_live: true,
+ counterparty_forwarding_info: None,
}];
let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
assert_eq!(route.paths[0].len(), 2);
outbound_capacity_msat: 250_000_000,
inbound_capacity_msat: 0,
is_live: true,
+ counterparty_forwarding_info: None,
}];
let mut last_hops = last_hops(&nodes);
let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, Some(&our_chans.iter().collect::<Vec<_>>()), &last_hops.iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)).unwrap();
outbound_capacity_msat: 100000,
inbound_capacity_msat: 100000,
is_live: true,
+ counterparty_forwarding_info: None,
}];
let route = get_route(&source_node_id, &NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash()), &target_node_id, None, Some(&our_chans.iter().collect::<Vec<_>>()), &last_hops.iter().collect::<Vec<_>>(), 100, 42, Arc::new(test_utils::TestLogger::new())).unwrap();
outbound_capacity_msat: 200_000_000,
inbound_capacity_msat: 0,
is_live: true,
+ counterparty_forwarding_info: None,
}];
{
assert_eq!(total_amount_paid_msat, 90_000);
}
}
+
+ #[test]
+ fn min_criteria_consistency() {
+ // Test that we don't use an inconsistent metric between updating and walking nodes during
+ // our Dijkstra's pass. In the initial version of MPP, the "best source" for a given node
+ // was updated with a different criterion from the heap sorting, resulting in loops in
+ // calculated paths. We test for that specific case here.
+
+ // We construct a network that looks like this:
+ //
+ // node2 -1(3)2- node3
+ // 2 2
+ // (2) (4)
+ // 1 1
+ // node1 -1(5)2- node4 -1(1)2- node6
+ // 2
+ // (6)
+ // 1
+ // our_node
+ //
+ // We create a loop on the side of our real path - our destination is node 6, with a
+ // previous hop of node 4. From 4, the cheapest previous path is channel 2 from node 2,
+ // followed by node 3 over channel 3. Thereafter, the cheapest next-hop is back to node 4
+ // (this time over channel 4). Channel 4 has 0 htlc_minimum_msat whereas channel 1 (the
+ // other channel with a previous-hop of node 4) has a high (but irrelevant to the overall
+ // payment) htlc_minimum_msat. In the original algorithm, this resulted in node4's
+ // "previous hop" being set to node 3, creating a loop in the path.
+ let secp_ctx = Secp256k1::new();
+ let logger = Arc::new(test_utils::TestLogger::new());
+ let net_graph_msg_handler = NetGraphMsgHandler::new(genesis_block(Network::Testnet).header.block_hash(), None, Arc::clone(&logger));
+ let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
+
+ add_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, &privkeys[1], ChannelFeatures::from_le_bytes(id_to_feature_flags(6)), 6);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 6,
+ timestamp: 1,
+ flags: 0,
+ cltv_expiry_delta: (6 << 8) | 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Absent,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[1], NodeFeatures::from_le_bytes(id_to_feature_flags(1)), 0);
+
+ add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[1], &privkeys[4], ChannelFeatures::from_le_bytes(id_to_feature_flags(5)), 5);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[1], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 5,
+ timestamp: 1,
+ flags: 0,
+ cltv_expiry_delta: (5 << 8) | 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Absent,
+ fee_base_msat: 100,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[4], NodeFeatures::from_le_bytes(id_to_feature_flags(4)), 0);
+
+ add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], &privkeys[3], ChannelFeatures::from_le_bytes(id_to_feature_flags(4)), 4);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 4,
+ timestamp: 1,
+ flags: 0,
+ cltv_expiry_delta: (4 << 8) | 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Absent,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[3], NodeFeatures::from_le_bytes(id_to_feature_flags(3)), 0);
+
+ add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[3], &privkeys[2], ChannelFeatures::from_le_bytes(id_to_feature_flags(3)), 3);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[3], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 3,
+ timestamp: 1,
+ flags: 0,
+ cltv_expiry_delta: (3 << 8) | 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Absent,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[2], NodeFeatures::from_le_bytes(id_to_feature_flags(2)), 0);
+
+ add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], &privkeys[4], ChannelFeatures::from_le_bytes(id_to_feature_flags(2)), 2);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 2,
+ timestamp: 1,
+ flags: 0,
+ cltv_expiry_delta: (2 << 8) | 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Absent,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], &privkeys[6], ChannelFeatures::from_le_bytes(id_to_feature_flags(1)), 1);
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 1,
+ timestamp: 1,
+ flags: 0,
+ cltv_expiry_delta: (1 << 8) | 0,
+ htlc_minimum_msat: 100,
+ htlc_maximum_msat: OptionalField::Absent,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[6], NodeFeatures::from_le_bytes(id_to_feature_flags(6)), 0);
+
+ {
+ // Now ensure the route flows simply over nodes 1 and 4 to 6.
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, None, &Vec::new(), 10_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ assert_eq!(route.paths[0].len(), 3);
+
+ assert_eq!(route.paths[0][0].pubkey, nodes[1]);
+ assert_eq!(route.paths[0][0].short_channel_id, 6);
+ assert_eq!(route.paths[0][0].fee_msat, 100);
+ assert_eq!(route.paths[0][0].cltv_expiry_delta, (5 << 8) | 0);
+ assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(1));
+ assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(6));
+
+ assert_eq!(route.paths[0][1].pubkey, nodes[4]);
+ assert_eq!(route.paths[0][1].short_channel_id, 5);
+ assert_eq!(route.paths[0][1].fee_msat, 0);
+ assert_eq!(route.paths[0][1].cltv_expiry_delta, (1 << 8) | 0);
+ assert_eq!(route.paths[0][1].node_features.le_flags(), &id_to_feature_flags(4));
+ assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(5));
+
+ assert_eq!(route.paths[0][2].pubkey, nodes[6]);
+ assert_eq!(route.paths[0][2].short_channel_id, 1);
+ assert_eq!(route.paths[0][2].fee_msat, 10_000);
+ assert_eq!(route.paths[0][2].cltv_expiry_delta, 42);
+ assert_eq!(route.paths[0][2].node_features.le_flags(), &id_to_feature_flags(6));
+ assert_eq!(route.paths[0][2].channel_features.le_flags(), &id_to_feature_flags(1));
+ }
+ }
+
+
+ #[test]
+ fn exact_fee_liquidity_limit() {
+ // Test that if, while walking the graph, we find a hop that has exactly enough liquidity
+ // for us, including later hop fees, we take it. In the first version of our MPP algorithm
+ // we calculated fees on a higher value, resulting in us ignoring such paths.
+ let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
+ let (our_privkey, our_id, _, nodes) = get_nodes(&secp_ctx);
+
+ // We modify the graph to set the htlc_maximum of channel 2 to below the value we wish to
+ // send.
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 2,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(85_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 12,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: (4 << 8) | 1,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(270_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 1000000,
+ excess_data: Vec::new()
+ });
+
+ {
+ // Now, attempt to route 90 sats, which is exactly 90 sats at the last hop, plus the
+ // 200% fee charged channel 13 in the 1-to-2 direction.
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, None, &Vec::new(), 90_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ assert_eq!(route.paths[0].len(), 2);
+
+ assert_eq!(route.paths[0][0].pubkey, nodes[7]);
+ assert_eq!(route.paths[0][0].short_channel_id, 12);
+ assert_eq!(route.paths[0][0].fee_msat, 90_000*2);
+ assert_eq!(route.paths[0][0].cltv_expiry_delta, (13 << 8) | 1);
+ assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(8));
+ assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(12));
+
+ assert_eq!(route.paths[0][1].pubkey, nodes[2]);
+ assert_eq!(route.paths[0][1].short_channel_id, 13);
+ assert_eq!(route.paths[0][1].fee_msat, 90_000);
+ assert_eq!(route.paths[0][1].cltv_expiry_delta, 42);
+ assert_eq!(route.paths[0][1].node_features.le_flags(), &id_to_feature_flags(3));
+ assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(13));
+ }
+ }
+
+ #[test]
+ fn htlc_max_reduction_below_min() {
+ // Test that if, while walking the graph, we reduce the value being sent to meet an
+ // htlc_maximum_msat, we don't end up undershooting a later htlc_minimum_msat. In the
+ // initial version of MPP we'd accept such routes but reject them while recalculating fees,
+ // resulting in us thinking there is no possible path, even if other paths exist.
+ let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
+ let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
+
+ // We modify the graph to set the htlc_minimum of channel 2 and 4 as needed - channel 2
+ // gets an htlc_maximum_msat of 80_000 and channel 4 an htlc_minimum_msat of 90_000. We
+ // then try to send 90_000.
+ update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 2,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: 0,
+ htlc_minimum_msat: 0,
+ htlc_maximum_msat: OptionalField::Present(80_000),
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+ update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[1], UnsignedChannelUpdate {
+ chain_hash: genesis_block(Network::Testnet).header.block_hash(),
+ short_channel_id: 4,
+ timestamp: 2,
+ flags: 0,
+ cltv_expiry_delta: (4 << 8) | 1,
+ htlc_minimum_msat: 90_000,
+ htlc_maximum_msat: OptionalField::Absent,
+ fee_base_msat: 0,
+ fee_proportional_millionths: 0,
+ excess_data: Vec::new()
+ });
+
+ {
+ // Now, attempt to route 90 sats, hitting the htlc_minimum on channel 4, but
+ // overshooting the htlc_maximum on channel 2. Thus, we should pick the (absurdly
+ // expensive) channels 12-13 path.
+ let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(InvoiceFeatures::known()), None, &Vec::new(), 90_000, 42, Arc::clone(&logger)).unwrap();
+ assert_eq!(route.paths.len(), 1);
+ assert_eq!(route.paths[0].len(), 2);
+
+ assert_eq!(route.paths[0][0].pubkey, nodes[7]);
+ assert_eq!(route.paths[0][0].short_channel_id, 12);
+ assert_eq!(route.paths[0][0].fee_msat, 90_000*2);
+ assert_eq!(route.paths[0][0].cltv_expiry_delta, (13 << 8) | 1);
+ assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(8));
+ assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(12));
+
+ assert_eq!(route.paths[0][1].pubkey, nodes[2]);
+ assert_eq!(route.paths[0][1].short_channel_id, 13);
+ assert_eq!(route.paths[0][1].fee_msat, 90_000);
+ assert_eq!(route.paths[0][1].cltv_expiry_delta, 42);
+ assert_eq!(route.paths[0][1].node_features.le_flags(), InvoiceFeatures::known().le_flags());
+ assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(13));
+ }
+ }
}
#[cfg(all(test, feature = "unstable"))]
projects / rust-lightning / blobdiff