X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=add1726623541d11f328635b56ab3e6622ef76e4;hb=5c38e09b2616ee78ccaa257dc4502f2f373c4a9e;hp=682302481b653f47b1a5485d50dcbd015050f1ec;hpb=c896461319b71ef3356ab72d9e886437d09cf79b;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index 68230248..add17266 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -372,8 +372,43 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // 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. @@ -391,13 +426,18 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye 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 @@ -521,8 +561,9 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // 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 amount_to_transfer_over_msat < $directional_info.htlc_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 @@ -709,12 +750,13 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // 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); } } @@ -727,7 +769,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // 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); }, } @@ -746,7 +788,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye // 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); true } else { // In any other case, only add the hop if the source is in the regular network @@ -766,7 +808,7 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye htlc_maximum_msat: hop.htlc_maximum_msat, fees: hop.fees, }; - add_entry!(hop.short_channel_id, hop.src_node_id, payee, directional_info, None::, ChannelFeatures::empty(), 0, recommended_value_msat); + add_entry!(hop.short_channel_id, hop.src_node_id, payee, directional_info, None::, ChannelFeatures::empty(), 0, path_value_msat); } } @@ -891,12 +933,22 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye } // 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; } } @@ -1473,6 +1525,7 @@ mod tests { 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::new(), 100, 42, Arc::clone(&logger)) { @@ -1790,6 +1843,7 @@ mod tests { 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::new(), 100, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths[0].len(), 2); @@ -1837,6 +1891,7 @@ mod tests { 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::new(), 100, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths[0].len(), 2); @@ -1901,6 +1956,7 @@ mod tests { 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::new(), 100, 42, Arc::clone(&logger)).unwrap(); assert_eq!(route.paths[0].len(), 2); @@ -2037,6 +2093,7 @@ mod tests { 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::>()), &last_hops.iter().collect::>(), 100, 42, Arc::clone(&logger)).unwrap(); @@ -2165,6 +2222,7 @@ mod tests { 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::>()), &last_hops.iter().collect::>(), 100, 42, Arc::new(test_utils::TestLogger::new())).unwrap(); @@ -2296,6 +2354,7 @@ mod tests { outbound_capacity_msat: 200_000_000, inbound_capacity_msat: 0, is_live: true, + counterparty_forwarding_info: None, }]; { @@ -3393,6 +3452,65 @@ mod tests { assert_eq!(total_amount_paid_msat, 90_000); } } + + #[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)); + } + } } #[cfg(all(test, feature = "unstable"))]