Merge pull request #1057 from TheBlueMatt/2021-08-invoice-fails
[rust-lightning] / lightning / src / routing / router.rs
index 06bf581c5457acc594805393d444c5b0d98dac44..5030f6aaacbf9569a0ff5e2d26a20a31104c0c9b 100644 (file)
@@ -21,13 +21,14 @@ use routing::network_graph::{NetworkGraph, RoutingFees};
 use util::ser::{Writeable, Readable};
 use util::logger::Logger;
 
+use io;
 use prelude::*;
 use alloc::collections::BinaryHeap;
 use core::cmp;
 use core::ops::Deref;
 
 /// A hop in a route
-#[derive(Clone, PartialEq)]
+#[derive(Clone, Hash, PartialEq, Eq)]
 pub struct RouteHop {
        /// The node_id of the node at this hop.
        pub pubkey: PublicKey,
@@ -49,17 +50,17 @@ pub struct RouteHop {
 }
 
 impl_writeable_tlv_based!(RouteHop, {
-       (0, pubkey),
-       (2, node_features),
-       (4, short_channel_id),
-       (6, channel_features),
-       (8, fee_msat),
-       (10, cltv_expiry_delta),
-}, {}, {});
+       (0, pubkey, required),
+       (2, node_features, required),
+       (4, short_channel_id, required),
+       (6, channel_features, required),
+       (8, fee_msat, required),
+       (10, cltv_expiry_delta, required),
+});
 
 /// A route directs a payment from the sender (us) to the recipient. If the recipient supports MPP,
 /// it can take multiple paths. Each path is composed of one or more hops through the network.
-#[derive(Clone, PartialEq)]
+#[derive(Clone, Hash, PartialEq, Eq)]
 pub struct Route {
        /// The list of routes taken for a single (potentially-)multi-part payment. The pubkey of the
        /// last RouteHop in each path must be the same.
@@ -74,7 +75,7 @@ const SERIALIZATION_VERSION: u8 = 1;
 const MIN_SERIALIZATION_VERSION: u8 = 1;
 
 impl Writeable for Route {
-       fn write<W: ::util::ser::Writer>(&self, writer: &mut W) -> Result<(), ::std::io::Error> {
+       fn write<W: ::util::ser::Writer>(&self, writer: &mut W) -> Result<(), io::Error> {
                write_ver_prefix!(writer, SERIALIZATION_VERSION, MIN_SERIALIZATION_VERSION);
                (self.paths.len() as u64).write(writer)?;
                for hops in self.paths.iter() {
@@ -83,13 +84,13 @@ impl Writeable for Route {
                                hop.write(writer)?;
                        }
                }
-               write_tlv_fields!(writer, {}, {});
+               write_tlv_fields!(writer, {});
                Ok(())
        }
 }
 
 impl Readable for Route {
-       fn read<R: ::std::io::Read>(reader: &mut R) -> Result<Route, DecodeError> {
+       fn read<R: io::Read>(reader: &mut R) -> Result<Route, DecodeError> {
                let _ver = read_ver_prefix!(reader, SERIALIZATION_VERSION);
                let path_count: u64 = Readable::read(reader)?;
                let mut paths = Vec::with_capacity(cmp::min(path_count, 128) as usize);
@@ -101,17 +102,17 @@ impl Readable for Route {
                        }
                        paths.push(hops);
                }
-               read_tlv_fields!(reader, {}, {});
+               read_tlv_fields!(reader, {});
                Ok(Route { paths })
        }
 }
 
 /// A list of hops along a payment path terminating with a channel to the recipient.
-#[derive(Eq, PartialEq, Debug, Clone)]
+#[derive(Clone, Debug, Hash, Eq, PartialEq)]
 pub struct RouteHint(pub Vec<RouteHintHop>);
 
 /// A channel descriptor for a hop along a payment path.
-#[derive(Eq, PartialEq, Debug, Clone)]
+#[derive(Clone, Debug, Hash, Eq, PartialEq)]
 pub struct RouteHintHop {
        /// The node_id of the non-target end of the route
        pub src_node_id: PublicKey,
@@ -327,6 +328,18 @@ fn compute_fees(amount_msat: u64, channel_fees: RoutingFees) -> Option<u64> {
        }
 }
 
+/// Gets a keysend route from us (payer) to the given target node (payee). This is needed because
+/// keysend payments do not have an invoice from which to pull the payee's supported features, which
+/// makes it tricky to otherwise supply the `payee_features` parameter of `get_route`.
+pub fn get_keysend_route<L: Deref>(our_node_id: &PublicKey, network: &NetworkGraph, payee:
+                       &PublicKey, first_hops: Option<&[&ChannelDetails]>, last_hops: &[&RouteHint],
+                       final_value_msat: u64, final_cltv: u32, logger: L) -> Result<Route,
+                       LightningError> where L::Target: Logger {
+       let invoice_features = InvoiceFeatures::for_keysend();
+       get_route(our_node_id, network, payee, Some(invoice_features), first_hops, last_hops,
+            final_value_msat, final_cltv, logger)
+}
+
 /// Gets a route from us (payer) to the given target node (payee).
 ///
 /// If the payee provided features in their invoice, they should be provided via payee_features.
@@ -362,10 +375,11 @@ pub fn get_route<L: Deref>(our_node_id: &PublicKey, network: &NetworkGraph, paye
                return Err(LightningError{err: "Cannot send a payment of 0 msat".to_owned(), action: ErrorAction::IgnoreError});
        }
 
-       let last_hops = last_hops.iter().filter_map(|hops| hops.0.last()).collect::<Vec<_>>();
-       for last_hop in last_hops.iter() {
-               if last_hop.src_node_id == *payee {
-                       return Err(LightningError{err: "Last hop cannot have a payee as a source.".to_owned(), action: ErrorAction::IgnoreError});
+       for route in last_hops.iter() {
+               for hop in &route.0 {
+                       if hop.src_node_id == *payee {
+                               return Err(LightningError{err: "Last hop cannot have a payee as a source.".to_owned(), action: ErrorAction::IgnoreError});
+                       }
                }
        }
 
@@ -459,10 +473,10 @@ pub fn get_route<L: Deref>(our_node_id: &PublicKey, network: &NetworkGraph, paye
        if let Some(hops) = first_hops {
                for chan in hops {
                        let short_channel_id = chan.short_channel_id.expect("first_hops should be filled in with usable channels, not pending ones");
-                       if chan.remote_network_id == *our_node_id {
+                       if chan.counterparty.node_id == *our_node_id {
                                return Err(LightningError{err: "First hop cannot have our_node_id as a destination.".to_owned(), action: ErrorAction::IgnoreError});
                        }
-                       first_hop_targets.insert(chan.remote_network_id, (short_channel_id, chan.counterparty_features.to_context(), chan.outbound_capacity_msat, chan.counterparty_features.to_context()));
+                       first_hop_targets.insert(chan.counterparty.node_id, (short_channel_id, chan.counterparty.features.to_context(), chan.outbound_capacity_msat, chan.counterparty.features.to_context()));
                }
                if first_hop_targets.is_empty() {
                        return Err(LightningError{err: "Cannot route when there are no outbound routes away from us".to_owned(), action: ErrorAction::IgnoreError});
@@ -514,8 +528,11 @@ pub fn get_route<L: Deref>(our_node_id: &PublicKey, network: &NetworkGraph, paye
                // $directional_info.
                // $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.
+               // Returns whether this channel caused an update to `targets`.
                ( $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_path_htlc_minimum_msat: expr ) => {
+                  $next_hops_value_contribution: expr, $next_hops_path_htlc_minimum_msat: expr ) => { {
+                       // We "return" whether we updated the path at the end, via this:
+                       let mut did_add_update_path_to_src_node = false;
                        // 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)
@@ -727,6 +744,7 @@ pub fn get_route<L: Deref>(our_node_id: &PublicKey, network: &NetworkGraph, paye
                                                                {
                                                                        old_entry.value_contribution_msat = value_contribution_msat;
                                                                }
+                                                               did_add_update_path_to_src_node = true;
                                                        } else if old_entry.was_processed && new_cost < old_cost {
                                                                #[cfg(any(test, feature = "fuzztarget"))]
                                                                {
@@ -757,7 +775,8 @@ pub fn get_route<L: Deref>(our_node_id: &PublicKey, network: &NetworkGraph, paye
                                        }
                                }
                        }
-               };
+                       did_add_update_path_to_src_node
+               } }
        }
 
        let empty_node_features = NodeFeatures::empty();
@@ -858,38 +877,91 @@ pub fn get_route<L: Deref>(our_node_id: &PublicKey, network: &NetworkGraph, paye
                // If a caller provided us with last hops, add them to routing targets. Since this happens
                // earlier than general path finding, they will be somewhat prioritized, although currently
                // it matters only if the fees are exactly the same.
-               for hop in last_hops.iter() {
+               for route in last_hops.iter().filter(|route| !route.0.is_empty()) {
+                       let first_hop_in_route = &(route.0)[0];
                        let have_hop_src_in_graph =
-                               if let Some(&(ref first_hop, ref features, ref outbound_capacity_msat, _)) = first_hop_targets.get(&hop.src_node_id) {
-                                       // If this hop connects to a node with which we have a direct channel, ignore
-                                       // the network graph and add both the hop and our direct channel to
-                                       // the candidate set.
-                                       //
-                                       // Currently there are no channel-context features defined, so we are a
-                                       // 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, 0, path_value_msat, 0);
-                                       true
-                               } else {
-                                       // In any other case, only add the hop if the source is in the regular network
-                                       // graph:
-                                       network.get_nodes().get(&hop.src_node_id).is_some()
-                               };
+                               // Only add the hops in this route to our candidate set if either
+                               // we have a direct channel to the first hop or the first hop is
+                               // in the regular network graph.
+                               first_hop_targets.get(&first_hop_in_route.src_node_id).is_some() ||
+                               network.get_nodes().get(&first_hop_in_route.src_node_id).is_some();
                        if have_hop_src_in_graph {
-                               // BOLT 11 doesn't allow inclusion of features for the last hop hints, which
-                               // really sucks, cause we're gonna need that eventually.
-                               let last_hop_htlc_minimum_msat: u64 = match hop.htlc_minimum_msat {
-                                       Some(htlc_minimum_msat) => htlc_minimum_msat,
-                                       None => 0
-                               };
-                               let directional_info = DummyDirectionalChannelInfo {
-                                       cltv_expiry_delta: hop.cltv_expiry_delta as u32,
-                                       htlc_minimum_msat: last_hop_htlc_minimum_msat,
-                                       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>, &empty_channel_features, 0, path_value_msat, 0);
+                               // We start building the path from reverse, i.e., from payee
+                               // to the first RouteHintHop in the path.
+                               let hop_iter = route.0.iter().rev();
+                               let prev_hop_iter = core::iter::once(payee).chain(
+                                       route.0.iter().skip(1).rev().map(|hop| &hop.src_node_id));
+                               let mut hop_used = true;
+                               let mut aggregate_next_hops_fee_msat: u64 = 0;
+                               let mut aggregate_next_hops_path_htlc_minimum_msat: u64 = 0;
+
+                               for (idx, (hop, prev_hop_id)) in hop_iter.zip(prev_hop_iter).enumerate() {
+                                       // BOLT 11 doesn't allow inclusion of features for the last hop hints, which
+                                       // really sucks, cause we're gonna need that eventually.
+                                       let hop_htlc_minimum_msat: u64 = hop.htlc_minimum_msat.unwrap_or(0);
+
+                                       let directional_info = DummyDirectionalChannelInfo {
+                                               cltv_expiry_delta: hop.cltv_expiry_delta as u32,
+                                               htlc_minimum_msat: hop_htlc_minimum_msat,
+                                               htlc_maximum_msat: hop.htlc_maximum_msat,
+                                               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 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, hop.src_node_id, prev_hop_id, directional_info, reqd_channel_cap, &empty_channel_features, aggregate_next_hops_fee_msat, path_value_msat, aggregate_next_hops_path_htlc_minimum_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
+                                               hop_used = false;
+                                       }
+
+                                       // Searching for a direct channel between last checked hop and first_hop_targets
+                                       if let Some(&(ref first_hop, ref features, ref outbound_capacity_msat, _)) = first_hop_targets.get(&prev_hop_id) {
+                                               add_entry!(first_hop, *our_node_id , prev_hop_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features, aggregate_next_hops_fee_msat, path_value_msat, aggregate_next_hops_path_htlc_minimum_msat);
+                                       }
+
+                                       if !hop_used {
+                                               break;
+                                       }
+
+                                       // In the next values of the iterator, the aggregate fees already reflects
+                                       // the sum of value sent from payer (final_value_msat) and routing fees
+                                       // for the last node in the RouteHint. We need to just add the fees to
+                                       // route through the current node so that the preceeding node (next iteration)
+                                       // can use it.
+                                       let hops_fee = compute_fees(aggregate_next_hops_fee_msat + final_value_msat, hop.fees)
+                                               .map_or(None, |inc| inc.checked_add(aggregate_next_hops_fee_msat));
+                                       aggregate_next_hops_fee_msat = if let Some(val) = hops_fee { val } else { break; };
+
+                                       let hop_htlc_minimum_msat_inc = if let Some(val) = compute_fees(aggregate_next_hops_path_htlc_minimum_msat, hop.fees) { val } else { break; };
+                                       let hops_path_htlc_minimum = aggregate_next_hops_path_htlc_minimum_msat
+                                               .checked_add(hop_htlc_minimum_msat_inc);
+                                       aggregate_next_hops_path_htlc_minimum_msat = if let Some(val) = hops_path_htlc_minimum { cmp::max(hop_htlc_minimum_msat, val) } else { break; };
+
+                                       if idx == route.0.len() - 1 {
+                                               // The last hop in this iterator is the first hop in
+                                               // overall RouteHint.
+                                               // If this hop connects to a node with which we have a direct channel,
+                                               // ignore the network graph and, if the last hop was added, add our
+                                               // direct channel to the candidate set.
+                                               //
+                                               // Note that we *must* check if the last hop was added as `add_entry`
+                                               // always assumes that the third argument is a node to which we have a
+                                               // path.
+                                               if let Some(&(ref first_hop, ref features, ref outbound_capacity_msat, _)) = first_hop_targets.get(&hop.src_node_id) {
+                                                       add_entry!(first_hop, *our_node_id , hop.src_node_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features, aggregate_next_hops_fee_msat, path_value_msat, aggregate_next_hops_path_htlc_minimum_msat);
+                                               }
+                                       }
+                               }
                        }
                }
 
@@ -1170,7 +1242,7 @@ pub fn get_route<L: Deref>(our_node_id: &PublicKey, network: &NetworkGraph, paye
 
 #[cfg(test)]
 mod tests {
-       use routing::router::{get_route, RouteHint, RouteHintHop, RoutingFees};
+       use routing::router::{get_route, Route, RouteHint, RouteHintHop, RoutingFees};
        use routing::network_graph::{NetworkGraph, NetGraphMsgHandler};
        use chain::transaction::OutPoint;
        use ln::features::{ChannelFeatures, InitFeatures, InvoiceFeatures, NodeFeatures};
@@ -1194,7 +1266,31 @@ mod tests {
        use bitcoin::secp256k1::{Secp256k1, All};
 
        use prelude::*;
-       use std::sync::Arc;
+       use sync::{self, Arc};
+
+       fn get_channel_details(short_channel_id: Option<u64>, node_id: PublicKey,
+                       features: InitFeatures, outbound_capacity_msat: u64) -> channelmanager::ChannelDetails {
+               channelmanager::ChannelDetails {
+                       channel_id: [0; 32],
+                       counterparty: channelmanager::ChannelCounterparty {
+                               features,
+                               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,
+                       channel_value_satoshis: 0,
+                       user_id: 0,
+                       outbound_capacity_msat,
+                       inbound_capacity_msat: 42,
+                       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,
+               }
+       }
 
        // Using the same keys for LN and BTC ids
        fn add_channel(net_graph_msg_handler: &NetGraphMsgHandler<Arc<test_utils::TestChainSource>, Arc<test_utils::TestLogger>>, secp_ctx: &Secp256k1<All>, node_1_privkey: &SecretKey,
@@ -1293,12 +1389,12 @@ mod tests {
                }
        }
 
-       fn build_graph() -> (Secp256k1<All>, NetGraphMsgHandler<std::sync::Arc<test_utils::TestChainSource>, std::sync::Arc<crate::util::test_utils::TestLogger>>, std::sync::Arc<test_utils::TestChainSource>, std::sync::Arc<test_utils::TestLogger>) {
+       fn build_graph() -> (Secp256k1<All>, NetGraphMsgHandler<sync::Arc<test_utils::TestChainSource>, sync::Arc<crate::util::test_utils::TestLogger>>, sync::Arc<test_utils::TestChainSource>, sync::Arc<test_utils::TestLogger>) {
                let secp_ctx = Secp256k1::new();
                let logger = Arc::new(test_utils::TestLogger::new());
                let chain_monitor = Arc::new(test_utils::TestChainSource::new(Network::Testnet));
                let net_graph_msg_handler = NetGraphMsgHandler::new(genesis_block(Network::Testnet).header.block_hash(), None, Arc::clone(&logger));
-               // Build network from our_id to node7:
+               // Build network from our_id to node6:
                //
                //        -1(1)2-  node0  -1(3)2-
                //       /                       \
@@ -1334,6 +1430,8 @@ mod tests {
                //      \                      /
                //       -1(7)2- node5 -1(10)2-
                //
+               // Channels 5, 8, 9 and 10 are private channels.
+               //
                // chan5  1-to-2: enabled, 100 msat fee
                // chan5  2-to-1: enabled, 0 fee
                //
@@ -1632,20 +1730,7 @@ mod tests {
 
                // Simple route to 2 via 1
 
-               let our_chans = vec![channelmanager::ChannelDetails {
-                       channel_id: [0; 32],
-                       funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
-                       short_channel_id: Some(2),
-                       remote_network_id: our_id,
-                       counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
-                       channel_value_satoshis: 100000,
-                       user_id: 0,
-                       outbound_capacity_msat: 100000,
-                       inbound_capacity_msat: 100000,
-                       is_outbound: true, is_funding_locked: true,
-                       is_usable: true, is_public: true,
-                       counterparty_forwarding_info: None,
-               }];
+               let our_chans = vec![get_channel_details(Some(2), our_id, InitFeatures::from_le_bytes(vec![0b11]), 100000)];
 
                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)) {
                        assert_eq!(err, "First hop cannot have our_node_id as a destination.");
@@ -1952,20 +2037,7 @@ mod tests {
                } else { panic!(); }
 
                // If we specify a channel to node7, that overrides our local channel view and that gets used
-               let our_chans = vec![channelmanager::ChannelDetails {
-                       channel_id: [0; 32],
-                       funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
-                       short_channel_id: Some(42),
-                       remote_network_id: nodes[7].clone(),
-                       counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
-                       channel_value_satoshis: 0,
-                       user_id: 0,
-                       outbound_capacity_msat: 250_000_000,
-                       inbound_capacity_msat: 0,
-                       is_outbound: true, is_funding_locked: true,
-                       is_usable: true, is_public: true,
-                       counterparty_forwarding_info: None,
-               }];
+               let our_chans = vec![get_channel_details(Some(42), nodes[7].clone(), InitFeatures::from_le_bytes(vec![0b11]), 250_000_000)];
                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);
 
@@ -1990,8 +2062,7 @@ mod tests {
                let (_, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
 
                // Disable nodes 1, 2, and 8 by requiring unknown feature bits
-               let mut unknown_features = NodeFeatures::known();
-               unknown_features.set_required_unknown_bits();
+               let unknown_features = NodeFeatures::known().set_unknown_feature_required();
                add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[0], unknown_features.clone(), 1);
                add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[1], unknown_features.clone(), 1);
                add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[7], unknown_features.clone(), 1);
@@ -2002,20 +2073,7 @@ mod tests {
                } else { panic!(); }
 
                // If we specify a channel to node7, that overrides our local channel view and that gets used
-               let our_chans = vec![channelmanager::ChannelDetails {
-                       channel_id: [0; 32],
-                       funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
-                       short_channel_id: Some(42),
-                       remote_network_id: nodes[7].clone(),
-                       counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
-                       channel_value_satoshis: 0,
-                       user_id: 0,
-                       outbound_capacity_msat: 250_000_000,
-                       inbound_capacity_msat: 0,
-                       is_outbound: true, is_funding_locked: true,
-                       is_usable: true, is_public: true,
-                       counterparty_forwarding_info: None,
-               }];
+               let our_chans = vec![get_channel_details(Some(42), nodes[7].clone(), InitFeatures::from_le_bytes(vec![0b11]), 250_000_000)];
                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);
 
@@ -2069,20 +2127,7 @@ mod tests {
                assert_eq!(route.paths[0][2].channel_features.le_flags(), &id_to_feature_flags(3));
 
                // If we specify a channel to node7, that overrides our local channel view and that gets used
-               let our_chans = vec![channelmanager::ChannelDetails {
-                       channel_id: [0; 32],
-                       funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
-                       short_channel_id: Some(42),
-                       remote_network_id: nodes[7].clone(),
-                       counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
-                       channel_value_satoshis: 0,
-                       user_id: 0,
-                       outbound_capacity_msat: 250_000_000,
-                       inbound_capacity_msat: 0,
-                       is_outbound: true, is_funding_locked: true,
-                       is_usable: true, is_public: true,
-                       counterparty_forwarding_info: None,
-               }];
+               let our_chans = vec![get_channel_details(Some(42), nodes[7].clone(), InitFeatures::from_le_bytes(vec![0b11]), 250_000_000)];
                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);
 
@@ -2113,7 +2158,51 @@ mod tests {
                        cltv_expiry_delta: (8 << 8) | 1,
                        htlc_minimum_msat: None,
                        htlc_maximum_msat: None,
+               }
+               ]), RouteHint(vec![RouteHintHop {
+                       src_node_id: nodes[4].clone(),
+                       short_channel_id: 9,
+                       fees: RoutingFees {
+                               base_msat: 1001,
+                               proportional_millionths: 0,
+                       },
+                       cltv_expiry_delta: (9 << 8) | 1,
+                       htlc_minimum_msat: None,
+                       htlc_maximum_msat: None,
                }]), RouteHint(vec![RouteHintHop {
+                       src_node_id: nodes[5].clone(),
+                       short_channel_id: 10,
+                       fees: zero_fees,
+                       cltv_expiry_delta: (10 << 8) | 1,
+                       htlc_minimum_msat: None,
+                       htlc_maximum_msat: None,
+               }])]
+       }
+
+       fn last_hops_multi_private_channels(nodes: &Vec<PublicKey>) -> Vec<RouteHint> {
+               let zero_fees = RoutingFees {
+                       base_msat: 0,
+                       proportional_millionths: 0,
+               };
+               vec![RouteHint(vec![RouteHintHop {
+                       src_node_id: nodes[2].clone(),
+                       short_channel_id: 5,
+                       fees: RoutingFees {
+                               base_msat: 100,
+                               proportional_millionths: 0,
+                       },
+                       cltv_expiry_delta: (5 << 8) | 1,
+                       htlc_minimum_msat: None,
+                       htlc_maximum_msat: None,
+               }, RouteHintHop {
+                       src_node_id: nodes[3].clone(),
+                       short_channel_id: 8,
+                       fees: zero_fees,
+                       cltv_expiry_delta: (8 << 8) | 1,
+                       htlc_minimum_msat: None,
+                       htlc_maximum_msat: None,
+               }
+               ]), RouteHint(vec![RouteHintHop {
                        src_node_id: nodes[4].clone(),
                        short_channel_id: 9,
                        fees: RoutingFees {
@@ -2134,11 +2223,13 @@ mod tests {
        }
 
        #[test]
-       fn last_hops_test() {
+       fn partial_route_hint_test() {
                let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
                let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
 
                // Simple test across 2, 3, 5, and 4 via a last_hop channel
+               // Tests the behaviour when the RouteHint contains a suboptimal hop.
+               // RouteHint may be partially used by the algo to build the best path.
 
                // First check that last hop can't have its source as the payee.
                let invalid_last_hop = RouteHint(vec![RouteHintHop {
@@ -2153,7 +2244,7 @@ mod tests {
                        htlc_maximum_msat: None,
                }]);
 
-               let mut invalid_last_hops = last_hops(&nodes);
+               let mut invalid_last_hops = last_hops_multi_private_channels(&nodes);
                invalid_last_hops.push(invalid_last_hop);
                {
                        if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, None, &invalid_last_hops.iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)) {
@@ -2161,7 +2252,7 @@ mod tests {
                        } else { panic!(); }
                }
 
-               let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, None, &last_hops(&nodes).iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)).unwrap();
+               let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, None, &last_hops_multi_private_channels(&nodes).iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)).unwrap();
                assert_eq!(route.paths[0].len(), 5);
 
                assert_eq!(route.paths[0][0].pubkey, nodes[1]);
@@ -2202,26 +2293,269 @@ mod tests {
                assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
        }
 
+       fn empty_last_hop(nodes: &Vec<PublicKey>) -> Vec<RouteHint> {
+               let zero_fees = RoutingFees {
+                       base_msat: 0,
+                       proportional_millionths: 0,
+               };
+               vec![RouteHint(vec![RouteHintHop {
+                       src_node_id: nodes[3].clone(),
+                       short_channel_id: 8,
+                       fees: zero_fees,
+                       cltv_expiry_delta: (8 << 8) | 1,
+                       htlc_minimum_msat: None,
+                       htlc_maximum_msat: None,
+               }]), RouteHint(vec![
+
+               ]), RouteHint(vec![RouteHintHop {
+                       src_node_id: nodes[5].clone(),
+                       short_channel_id: 10,
+                       fees: zero_fees,
+                       cltv_expiry_delta: (10 << 8) | 1,
+                       htlc_minimum_msat: None,
+                       htlc_maximum_msat: None,
+               }])]
+       }
+
+       #[test]
+       fn ignores_empty_last_hops_test() {
+               let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
+               let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
+
+               // Test handling of an empty RouteHint passed in Invoice.
+
+               let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, None, &empty_last_hop(&nodes).iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)).unwrap();
+               assert_eq!(route.paths[0].len(), 5);
+
+               assert_eq!(route.paths[0][0].pubkey, nodes[1]);
+               assert_eq!(route.paths[0][0].short_channel_id, 2);
+               assert_eq!(route.paths[0][0].fee_msat, 100);
+               assert_eq!(route.paths[0][0].cltv_expiry_delta, (4 << 8) | 1);
+               assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(2));
+               assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(2));
+
+               assert_eq!(route.paths[0][1].pubkey, nodes[2]);
+               assert_eq!(route.paths[0][1].short_channel_id, 4);
+               assert_eq!(route.paths[0][1].fee_msat, 0);
+               assert_eq!(route.paths[0][1].cltv_expiry_delta, (6 << 8) | 1);
+               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(4));
+
+               assert_eq!(route.paths[0][2].pubkey, nodes[4]);
+               assert_eq!(route.paths[0][2].short_channel_id, 6);
+               assert_eq!(route.paths[0][2].fee_msat, 0);
+               assert_eq!(route.paths[0][2].cltv_expiry_delta, (11 << 8) | 1);
+               assert_eq!(route.paths[0][2].node_features.le_flags(), &id_to_feature_flags(5));
+               assert_eq!(route.paths[0][2].channel_features.le_flags(), &id_to_feature_flags(6));
+
+               assert_eq!(route.paths[0][3].pubkey, nodes[3]);
+               assert_eq!(route.paths[0][3].short_channel_id, 11);
+               assert_eq!(route.paths[0][3].fee_msat, 0);
+               assert_eq!(route.paths[0][3].cltv_expiry_delta, (8 << 8) | 1);
+               // If we have a peer in the node map, we'll use their features here since we don't have
+               // a way of figuring out their features from the invoice:
+               assert_eq!(route.paths[0][3].node_features.le_flags(), &id_to_feature_flags(4));
+               assert_eq!(route.paths[0][3].channel_features.le_flags(), &id_to_feature_flags(11));
+
+               assert_eq!(route.paths[0][4].pubkey, nodes[6]);
+               assert_eq!(route.paths[0][4].short_channel_id, 8);
+               assert_eq!(route.paths[0][4].fee_msat, 100);
+               assert_eq!(route.paths[0][4].cltv_expiry_delta, 42);
+               assert_eq!(route.paths[0][4].node_features.le_flags(), &Vec::<u8>::new()); // We dont pass flags in from invoices yet
+               assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
+       }
+
+       fn multi_hint_last_hops(nodes: &Vec<PublicKey>) -> Vec<RouteHint> {
+               let zero_fees = RoutingFees {
+                       base_msat: 0,
+                       proportional_millionths: 0,
+               };
+               vec![RouteHint(vec![RouteHintHop {
+                       src_node_id: nodes[2].clone(),
+                       short_channel_id: 5,
+                       fees: RoutingFees {
+                               base_msat: 100,
+                               proportional_millionths: 0,
+                       },
+                       cltv_expiry_delta: (5 << 8) | 1,
+                       htlc_minimum_msat: None,
+                       htlc_maximum_msat: None,
+               }, RouteHintHop {
+                       src_node_id: nodes[3].clone(),
+                       short_channel_id: 8,
+                       fees: zero_fees,
+                       cltv_expiry_delta: (8 << 8) | 1,
+                       htlc_minimum_msat: None,
+                       htlc_maximum_msat: None,
+               }]), RouteHint(vec![RouteHintHop {
+                       src_node_id: nodes[5].clone(),
+                       short_channel_id: 10,
+                       fees: zero_fees,
+                       cltv_expiry_delta: (10 << 8) | 1,
+                       htlc_minimum_msat: None,
+                       htlc_maximum_msat: None,
+               }])]
+       }
+
+       #[test]
+       fn multi_hint_last_hops_test() {
+               let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
+               let (_, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
+               // Test through channels 2, 3, 5, 8.
+               // Test shows that multiple hop hints are considered.
+
+               // Disabling channels 6 & 7 by flags=2
+               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: 2, // to disable
+                       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: 7,
+                       timestamp: 2,
+                       flags: 2, // to disable
+                       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 route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, None, &multi_hint_last_hops(&nodes).iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)).unwrap();
+               assert_eq!(route.paths[0].len(), 4);
+
+               assert_eq!(route.paths[0][0].pubkey, nodes[1]);
+               assert_eq!(route.paths[0][0].short_channel_id, 2);
+               assert_eq!(route.paths[0][0].fee_msat, 200);
+               assert_eq!(route.paths[0][0].cltv_expiry_delta, 1025);
+               assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(2));
+               assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(2));
+
+               assert_eq!(route.paths[0][1].pubkey, nodes[2]);
+               assert_eq!(route.paths[0][1].short_channel_id, 4);
+               assert_eq!(route.paths[0][1].fee_msat, 100);
+               assert_eq!(route.paths[0][1].cltv_expiry_delta, 1281);
+               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(4));
+
+               assert_eq!(route.paths[0][2].pubkey, nodes[3]);
+               assert_eq!(route.paths[0][2].short_channel_id, 5);
+               assert_eq!(route.paths[0][2].fee_msat, 0);
+               assert_eq!(route.paths[0][2].cltv_expiry_delta, 2049);
+               assert_eq!(route.paths[0][2].node_features.le_flags(), &id_to_feature_flags(4));
+               assert_eq!(route.paths[0][2].channel_features.le_flags(), &Vec::<u8>::new());
+
+               assert_eq!(route.paths[0][3].pubkey, nodes[6]);
+               assert_eq!(route.paths[0][3].short_channel_id, 8);
+               assert_eq!(route.paths[0][3].fee_msat, 100);
+               assert_eq!(route.paths[0][3].cltv_expiry_delta, 42);
+               assert_eq!(route.paths[0][3].node_features.le_flags(), &Vec::<u8>::new()); // We dont pass flags in from invoices yet
+               assert_eq!(route.paths[0][3].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
+       }
+
+       fn last_hops_with_public_channel(nodes: &Vec<PublicKey>) -> Vec<RouteHint> {
+               let zero_fees = RoutingFees {
+                       base_msat: 0,
+                       proportional_millionths: 0,
+               };
+               vec![RouteHint(vec![RouteHintHop {
+                       src_node_id: nodes[4].clone(),
+                       short_channel_id: 11,
+                       fees: zero_fees,
+                       cltv_expiry_delta: (11 << 8) | 1,
+                       htlc_minimum_msat: None,
+                       htlc_maximum_msat: None,
+               }, RouteHintHop {
+                       src_node_id: nodes[3].clone(),
+                       short_channel_id: 8,
+                       fees: zero_fees,
+                       cltv_expiry_delta: (8 << 8) | 1,
+                       htlc_minimum_msat: None,
+                       htlc_maximum_msat: None,
+               }]), RouteHint(vec![RouteHintHop {
+                       src_node_id: nodes[4].clone(),
+                       short_channel_id: 9,
+                       fees: RoutingFees {
+                               base_msat: 1001,
+                               proportional_millionths: 0,
+                       },
+                       cltv_expiry_delta: (9 << 8) | 1,
+                       htlc_minimum_msat: None,
+                       htlc_maximum_msat: None,
+               }]), RouteHint(vec![RouteHintHop {
+                       src_node_id: nodes[5].clone(),
+                       short_channel_id: 10,
+                       fees: zero_fees,
+                       cltv_expiry_delta: (10 << 8) | 1,
+                       htlc_minimum_msat: None,
+                       htlc_maximum_msat: None,
+               }])]
+       }
+
+       #[test]
+       fn last_hops_with_public_channel_test() {
+               let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
+               let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
+               // This test shows that public routes can be present in the invoice
+               // which would be handled in the same manner.
+
+               let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, None, &last_hops_with_public_channel(&nodes).iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)).unwrap();
+               assert_eq!(route.paths[0].len(), 5);
+
+               assert_eq!(route.paths[0][0].pubkey, nodes[1]);
+               assert_eq!(route.paths[0][0].short_channel_id, 2);
+               assert_eq!(route.paths[0][0].fee_msat, 100);
+               assert_eq!(route.paths[0][0].cltv_expiry_delta, (4 << 8) | 1);
+               assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(2));
+               assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(2));
+
+               assert_eq!(route.paths[0][1].pubkey, nodes[2]);
+               assert_eq!(route.paths[0][1].short_channel_id, 4);
+               assert_eq!(route.paths[0][1].fee_msat, 0);
+               assert_eq!(route.paths[0][1].cltv_expiry_delta, (6 << 8) | 1);
+               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(4));
+
+               assert_eq!(route.paths[0][2].pubkey, nodes[4]);
+               assert_eq!(route.paths[0][2].short_channel_id, 6);
+               assert_eq!(route.paths[0][2].fee_msat, 0);
+               assert_eq!(route.paths[0][2].cltv_expiry_delta, (11 << 8) | 1);
+               assert_eq!(route.paths[0][2].node_features.le_flags(), &id_to_feature_flags(5));
+               assert_eq!(route.paths[0][2].channel_features.le_flags(), &id_to_feature_flags(6));
+
+               assert_eq!(route.paths[0][3].pubkey, nodes[3]);
+               assert_eq!(route.paths[0][3].short_channel_id, 11);
+               assert_eq!(route.paths[0][3].fee_msat, 0);
+               assert_eq!(route.paths[0][3].cltv_expiry_delta, (8 << 8) | 1);
+               // If we have a peer in the node map, we'll use their features here since we don't have
+               // a way of figuring out their features from the invoice:
+               assert_eq!(route.paths[0][3].node_features.le_flags(), &id_to_feature_flags(4));
+               assert_eq!(route.paths[0][3].channel_features.le_flags(), &Vec::<u8>::new());
+
+               assert_eq!(route.paths[0][4].pubkey, nodes[6]);
+               assert_eq!(route.paths[0][4].short_channel_id, 8);
+               assert_eq!(route.paths[0][4].fee_msat, 100);
+               assert_eq!(route.paths[0][4].cltv_expiry_delta, 42);
+               assert_eq!(route.paths[0][4].node_features.le_flags(), &Vec::<u8>::new()); // We dont pass flags in from invoices yet
+               assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
+       }
+
        #[test]
        fn our_chans_last_hop_connect_test() {
                let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
                let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
 
                // Simple test with outbound channel to 4 to test that last_hops and first_hops connect
-               let our_chans = vec![channelmanager::ChannelDetails {
-                       channel_id: [0; 32],
-                       funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
-                       short_channel_id: Some(42),
-                       remote_network_id: nodes[3].clone(),
-                       counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
-                       channel_value_satoshis: 0,
-                       user_id: 0,
-                       outbound_capacity_msat: 250_000_000,
-                       inbound_capacity_msat: 0,
-                       is_outbound: true, is_funding_locked: true,
-                       is_usable: true, is_public: true,
-                       counterparty_forwarding_info: None,
-               }];
+               let our_chans = vec![get_channel_details(Some(42), nodes[3].clone(), InitFeatures::from_le_bytes(vec![0b11]), 250_000_000)];
                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();
                assert_eq!(route.paths[0].len(), 2);
@@ -2318,11 +2652,7 @@ mod tests {
                assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
        }
 
-       #[test]
-       fn unannounced_path_test() {
-               // We should be able to send a payment to a destination without any help of a routing graph
-               // if we have a channel with a common counterparty that appears in the first and last hop
-               // hints.
+       fn do_unannounced_path_test(last_hop_htlc_max: Option<u64>, last_hop_fee_prop: u32, outbound_capacity_msat: u64, route_val: u64) -> Result<Route, LightningError> {
                let source_node_id = PublicKey::from_secret_key(&Secp256k1::new(), &SecretKey::from_slice(&hex::decode(format!("{:02}", 41).repeat(32)).unwrap()[..]).unwrap());
                let middle_node_id = PublicKey::from_secret_key(&Secp256k1::new(), &SecretKey::from_slice(&hex::decode(format!("{:02}", 42).repeat(32)).unwrap()[..]).unwrap());
                let target_node_id = PublicKey::from_secret_key(&Secp256k1::new(), &SecretKey::from_slice(&hex::decode(format!("{:02}", 43).repeat(32)).unwrap()[..]).unwrap());
@@ -2333,45 +2663,60 @@ mod tests {
                        short_channel_id: 8,
                        fees: RoutingFees {
                                base_msat: 1000,
-                               proportional_millionths: 0,
+                               proportional_millionths: last_hop_fee_prop,
                        },
                        cltv_expiry_delta: (8 << 8) | 1,
                        htlc_minimum_msat: None,
-                       htlc_maximum_msat: None,
+                       htlc_maximum_msat: last_hop_htlc_max,
                }]);
-               let our_chans = vec![channelmanager::ChannelDetails {
-                       channel_id: [0; 32],
-                       funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
-                       short_channel_id: Some(42),
-                       remote_network_id: middle_node_id,
-                       counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
-                       channel_value_satoshis: 100000,
-                       user_id: 0,
-                       outbound_capacity_msat: 100000,
-                       inbound_capacity_msat: 100000,
-                       is_outbound: true, is_funding_locked: true,
-                       is_usable: true, is_public: 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<_>>()), &vec![&last_hops], 100, 42, Arc::new(test_utils::TestLogger::new())).unwrap();
+               let our_chans = vec![get_channel_details(Some(42), middle_node_id, InitFeatures::from_le_bytes(vec![0b11]), outbound_capacity_msat)];
+               get_route(&source_node_id, &NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash()), &target_node_id, None, Some(&our_chans.iter().collect::<Vec<_>>()), &vec![&last_hops], route_val, 42, Arc::new(test_utils::TestLogger::new()))
+       }
 
+       #[test]
+       fn unannounced_path_test() {
+               // We should be able to send a payment to a destination without any help of a routing graph
+               // if we have a channel with a common counterparty that appears in the first and last hop
+               // hints.
+               let route = do_unannounced_path_test(None, 1, 2000000, 1000000).unwrap();
+
+               let middle_node_id = PublicKey::from_secret_key(&Secp256k1::new(), &SecretKey::from_slice(&hex::decode(format!("{:02}", 42).repeat(32)).unwrap()[..]).unwrap());
+               let target_node_id = PublicKey::from_secret_key(&Secp256k1::new(), &SecretKey::from_slice(&hex::decode(format!("{:02}", 43).repeat(32)).unwrap()[..]).unwrap());
                assert_eq!(route.paths[0].len(), 2);
 
                assert_eq!(route.paths[0][0].pubkey, middle_node_id);
                assert_eq!(route.paths[0][0].short_channel_id, 42);
-               assert_eq!(route.paths[0][0].fee_msat, 1000);
+               assert_eq!(route.paths[0][0].fee_msat, 1001);
                assert_eq!(route.paths[0][0].cltv_expiry_delta, (8 << 8) | 1);
                assert_eq!(route.paths[0][0].node_features.le_flags(), &[0b11]);
                assert_eq!(route.paths[0][0].channel_features.le_flags(), &[0; 0]); // We can't learn any flags from invoices, sadly
 
                assert_eq!(route.paths[0][1].pubkey, target_node_id);
                assert_eq!(route.paths[0][1].short_channel_id, 8);
-               assert_eq!(route.paths[0][1].fee_msat, 100);
+               assert_eq!(route.paths[0][1].fee_msat, 1000000);
                assert_eq!(route.paths[0][1].cltv_expiry_delta, 42);
                assert_eq!(route.paths[0][1].node_features.le_flags(), &[0; 0]); // We dont pass flags in from invoices yet
                assert_eq!(route.paths[0][1].channel_features.le_flags(), &[0; 0]); // We can't learn any flags from invoices, sadly
        }
 
+       #[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.
@@ -2473,20 +2818,7 @@ mod tests {
                });
 
                // Now, limit the first_hop by the outbound_capacity_msat of 200_000 sats.
-               let our_chans = vec![channelmanager::ChannelDetails {
-                       channel_id: [0; 32],
-                       funding_txo: Some(OutPoint { txid: bitcoin::Txid::from_slice(&[0; 32]).unwrap(), index: 0 }),
-                       short_channel_id: Some(42),
-                       remote_network_id: nodes[0].clone(),
-                       counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
-                       channel_value_satoshis: 0,
-                       user_id: 0,
-                       outbound_capacity_msat: 200_000_000,
-                       inbound_capacity_msat: 0,
-                       is_outbound: true, is_funding_locked: true,
-                       is_usable: true, is_public: true,
-                       counterparty_forwarding_info: None,
-               }];
+               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.
@@ -3854,7 +4186,7 @@ mod tests {
                }
        }
 
-       #[cfg(not(feature = "no_std"))]
+       #[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};
@@ -3862,11 +4194,11 @@ mod tests {
                println!("Using seed of {}", seed);
                seed
        }
-       #[cfg(not(feature = "no_std"))]
+       #[cfg(not(feature = "no-std"))]
        use util::ser::Readable;
 
        #[test]
-       #[cfg(not(feature = "no_std"))]
+       #[cfg(not(feature = "no-std"))]
        fn generate_routes() {
                let mut d = match super::test_utils::get_route_file() {
                        Ok(f) => f,
@@ -3894,7 +4226,7 @@ mod tests {
        }
 
        #[test]
-       #[cfg(not(feature = "no_std"))]
+       #[cfg(not(feature = "no-std"))]
        fn generate_routes_mpp() {
                let mut d = match super::test_utils::get_route_file() {
                        Ok(f) => f,
@@ -3922,7 +4254,7 @@ mod tests {
        }
 }
 
-#[cfg(all(test, not(feature = "no_std")))]
+#[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.
@@ -3949,7 +4281,7 @@ pub(crate) mod test_utils {
        }
 }
 
-#[cfg(all(test, feature = "unstable", not(feature = "no_std")))]
+#[cfg(all(test, feature = "unstable", not(feature = "no-std")))]
 mod benches {
        use super::*;
        use util::logger::{Logger, Record};