X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=e49844383bbceee091e9d42b7262416109b2d484;hb=565559005ec241d8f4f45a373652eb4ee4e13b9c;hp=974ae74e4960f0c636670f721106aa4cb8d87d53;hpb=55fc0a1c10b5c412cb83bac509f7072d239c62c9;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index 974ae74e..e4984438 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -17,7 +17,7 @@ use bitcoin::secp256k1::key::PublicKey; use ln::channelmanager::ChannelDetails; use ln::features::{ChannelFeatures, InvoiceFeatures, NodeFeatures}; use ln::msgs::{DecodeError, ErrorAction, LightningError, MAX_VALUE_MSAT}; -use routing; +use routing::scoring::Score; use routing::network_graph::{NetworkGraph, NodeId, RoutingFees}; use util::ser::{Writeable, Readable}; use util::logger::{Level, Logger}; @@ -529,7 +529,7 @@ fn compute_fees(amount_msat: u64, channel_fees: RoutingFees) -> Option { /// /// [`ChannelManager::list_usable_channels`]: crate::ln::channelmanager::ChannelManager::list_usable_channels /// [`Event::PaymentPathFailed`]: crate::util::events::Event::PaymentPathFailed -pub fn find_route( +pub fn find_route( our_node_pubkey: &PublicKey, params: &RouteParameters, network: &NetworkGraph, first_hops: Option<&[&ChannelDetails]>, logger: L, scorer: &S ) -> Result @@ -540,7 +540,7 @@ where L::Target: Logger { ) } -pub(crate) fn get_route( +pub(crate) fn get_route( our_node_pubkey: &PublicKey, payee: &Payee, network: &NetworkGraph, first_hops: Option<&[&ChannelDetails]>, final_value_msat: u64, final_cltv_expiry_delta: u32, logger: L, scorer: &S @@ -892,9 +892,9 @@ where L::Target: Logger { } } - let path_penalty_msat = $next_hops_path_penalty_msat - .checked_add(scorer.channel_penalty_msat($chan_id.clone(), &$src_node_id, &$dest_node_id)) - .unwrap_or_else(|| u64::max_value()); + let path_penalty_msat = $next_hops_path_penalty_msat.checked_add( + scorer.channel_penalty_msat($chan_id.clone(), amount_to_transfer_over_msat, Some(*available_liquidity_msat), + &$src_node_id, &$dest_node_id)).unwrap_or_else(|| u64::max_value()); let new_graph_node = RouteGraphNode { node_id: $src_node_id, lowest_fee_to_peer_through_node: total_fee_msat, @@ -1113,22 +1113,28 @@ where L::Target: Logger { fees: hop.fees, }; - let reqd_channel_cap = if let Some (val) = final_value_msat.checked_add(match idx { - 0 => 999, - _ => aggregate_next_hops_fee_msat.checked_add(999).unwrap_or(u64::max_value()) - }) { Some( val / 1000 ) } else { break; }; // converting from msat or breaking if max ~ infinity + // We want a value of final_value_msat * ROUTE_CAPACITY_PROVISION_FACTOR but we + // need it to increment at each hop by the fee charged at later hops. Further, + // we need to ensure we round up when we divide to get satoshis. + let channel_cap_msat = final_value_msat + .checked_mul(ROUTE_CAPACITY_PROVISION_FACTOR).and_then(|v| v.checked_add(aggregate_next_hops_fee_msat)) + .unwrap_or(u64::max_value()); + let channel_cap_sat = match channel_cap_msat.checked_add(999) { + None => break, // We overflowed above, just ignore this route hint + Some(val) => Some(val / 1000), + }; let src_node_id = NodeId::from_pubkey(&hop.src_node_id); let dest_node_id = NodeId::from_pubkey(&prev_hop_id); aggregate_next_hops_path_penalty_msat = aggregate_next_hops_path_penalty_msat - .checked_add(scorer.channel_penalty_msat(hop.short_channel_id, &src_node_id, &dest_node_id)) + .checked_add(scorer.channel_penalty_msat(hop.short_channel_id, final_value_msat, None, &src_node_id, &dest_node_id)) .unwrap_or_else(|| u64::max_value()); // We assume that the recipient only included route hints for routes which had // sufficient value to route `final_value_msat`. Note that in the case of "0-value" // invoices where the invoice does not specify value this may not be the case, but // better to include the hints than not. - if !add_entry!(hop.short_channel_id, src_node_id, dest_node_id, directional_info, reqd_channel_cap, &empty_channel_features, aggregate_next_hops_fee_msat, path_value_msat, aggregate_next_hops_path_htlc_minimum_msat, aggregate_next_hops_path_penalty_msat) { + if !add_entry!(hop.short_channel_id, src_node_id, dest_node_id, directional_info, channel_cap_sat, &empty_channel_features, aggregate_next_hops_fee_msat, path_value_msat, aggregate_next_hops_path_htlc_minimum_msat, aggregate_next_hops_path_penalty_msat) { // If this hop was not used then there is no use checking the preceding hops // in the RouteHint. We can break by just searching for a direct channel between // last checked hop and first_hop_targets @@ -1472,7 +1478,7 @@ where L::Target: Logger { #[cfg(test)] mod tests { - use routing; + use routing::scoring::Score; use routing::network_graph::{NetworkGraph, NetGraphMsgHandler, NodeId}; use routing::router::{get_route, Payee, Route, RouteHint, RouteHintHop, RouteHop, RoutingFees}; use chain::transaction::OutPoint; @@ -1482,6 +1488,8 @@ mod tests { use ln::channelmanager; use util::test_utils; use util::ser::Writeable; + #[cfg(c_bindings)] + use util::ser::Writer; use bitcoin::hashes::sha256d::Hash as Sha256dHash; use bitcoin::hashes::Hash; @@ -1513,6 +1521,7 @@ mod tests { short_channel_id, channel_value_satoshis: 0, user_channel_id: 0, + balance_msat: 0, outbound_capacity_msat, inbound_capacity_msat: 42, unspendable_punishment_reserve: None, @@ -4055,7 +4064,105 @@ mod tests { 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_fixed_penalty(0); + let payee = Payee::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: u16::max_value(), + 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: u16::max_value(), + 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 << 8) | 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 << 8) | 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, &payee, &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] @@ -4549,24 +4656,35 @@ mod tests { short_channel_id: u64, } - impl routing::Score for BadChannelScorer { - fn channel_penalty_msat(&self, short_channel_id: u64, _source: &NodeId, _target: &NodeId) -> u64 { + #[cfg(c_bindings)] + impl Writeable for BadChannelScorer { + fn write(&self, _w: &mut W) -> Result<(), ::io::Error> { unimplemented!() } + } + impl Score for BadChannelScorer { + fn channel_penalty_msat(&self, short_channel_id: u64, _send_amt: u64, _chan_amt: Option, _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, } - impl routing::Score for BadNodeScorer { - fn channel_penalty_msat(&self, _short_channel_id: u64, _source: &NodeId, target: &NodeId) -> u64 { + #[cfg(c_bindings)] + impl Writeable for BadNodeScorer { + fn write(&self, _w: &mut W) -> Result<(), ::io::Error> { unimplemented!() } + } + + impl Score for BadNodeScorer { + fn channel_penalty_msat(&self, _short_channel_id: u64, _send_amt: u64, _chan_amt: Option, _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] @@ -4787,7 +4905,7 @@ pub(crate) mod test_utils { #[cfg(all(test, feature = "unstable", not(feature = "no-std")))] mod benches { use super::*; - use routing::scorer::Scorer; + use routing::scoring::Scorer; use util::logger::{Logger, Record}; use test::Bencher;