Use APIError::ChannelUnavailable a bit more for consistency
[rust-lightning] / src / ln / router.rs
index 0ee6450fa42718deef66dc7666d71e4d75740ced..4a55df88c6f90fd30d309e506377d819a7720a02 100644 (file)
@@ -1,27 +1,40 @@
+//! The top-level routing/network map tracking logic lives here.
+//!
+//! You probably want to create a Router and use that as your RoutingMessageHandler and then
+//! interrogate it to get routes for your own payments.
+
 use secp256k1::key::PublicKey;
 use secp256k1::{Secp256k1,Message};
+use secp256k1;
 
 use bitcoin::util::hash::Sha256dHash;
+use bitcoin::blockdata::script::Builder;
+use bitcoin::blockdata::opcodes;
 
+use chain::chaininterface::{ChainError, ChainWatchInterface};
 use ln::channelmanager;
-use ln::msgs::{ErrorAction,HandleError,RoutingMessageHandler,MsgEncodable,NetAddress,GlobalFeatures};
+use ln::msgs::{ErrorAction,HandleError,RoutingMessageHandler,NetAddress,GlobalFeatures};
 use ln::msgs;
+use util::ser::Writeable;
+use util::logger::Logger;
 
 use std::cmp;
-use std::sync::RwLock;
+use std::sync::{RwLock,Arc};
 use std::collections::{HashMap,BinaryHeap};
 use std::collections::hash_map::Entry;
+use std;
 
 /// A hop in a route
 #[derive(Clone)]
 pub struct RouteHop {
+       /// The node_id of the node at this hop.
        pub pubkey: PublicKey,
        /// The channel that should be used from the previous hop to reach this node.
        pub short_channel_id: u64,
        /// The fee taken on this hop. For the last hop, this should be the full value of the payment.
        pub fee_msat: u64,
        /// The CLTV delta added for this hop. For the last hop, this should be the full CLTV value
-       /// expected at the destination, NOT a delta.
+       /// expected at the destination, in excess of the current block height.
        pub cltv_expiry_delta: u32,
 }
 
@@ -44,12 +57,26 @@ struct DirectionalChannelInfo {
        fee_proportional_millionths: u32,
 }
 
+impl std::fmt::Display for DirectionalChannelInfo {
+       fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
+               write!(f, "src_node_id {}, last_update {}, enabled {}, cltv_expiry_delta {}, htlc_minimum_msat {}, fee_base_msat {}, fee_proportional_millionths {}", log_pubkey!(self.src_node_id), self.last_update, self.enabled, self.cltv_expiry_delta, self.htlc_minimum_msat, self.fee_base_msat, self.fee_proportional_millionths)?;
+               Ok(())
+       }
+}
+
 struct ChannelInfo {
        features: GlobalFeatures,
        one_to_two: DirectionalChannelInfo,
        two_to_one: DirectionalChannelInfo,
 }
 
+impl std::fmt::Display for ChannelInfo {
+       fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
+               write!(f, "features: {}, one_to_two: {}, two_to_one: {}", log_bytes!(self.features.encode()), self.one_to_two, self.two_to_one)?;
+               Ok(())
+       }
+}
+
 struct NodeInfo {
        #[cfg(feature = "non_bitcoin_chain_hash_routing")]
        channels: Vec<(u64, Sha256dHash)>,
@@ -66,6 +93,13 @@ struct NodeInfo {
        addresses: Vec<NetAddress>,
 }
 
+impl std::fmt::Display for NodeInfo {
+       fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
+               write!(f, "features: {}, last_update: {}, lowest_inbound_channel_fee_base_msat: {}, lowest_inbound_channel_fee_proportional_millionths: {}, channels: {:?}", log_bytes!(self.features.encode()), self.last_update, self.lowest_inbound_channel_fee_base_msat, self.lowest_inbound_channel_fee_proportional_millionths, &self.channels[..])?;
+               Ok(())
+       }
+}
+
 struct NetworkMap {
        #[cfg(feature = "non_bitcoin_chain_hash_routing")]
        channels: HashMap<(u64, Sha256dHash), ChannelInfo>,
@@ -75,6 +109,34 @@ struct NetworkMap {
        our_node_id: PublicKey,
        nodes: HashMap<PublicKey, NodeInfo>,
 }
+struct MutNetworkMap<'a> {
+       #[cfg(feature = "non_bitcoin_chain_hash_routing")]
+       channels: &'a mut HashMap<(u64, Sha256dHash), ChannelInfo>,
+       #[cfg(not(feature = "non_bitcoin_chain_hash_routing"))]
+       channels: &'a mut HashMap<u64, ChannelInfo>,
+       nodes: &'a mut HashMap<PublicKey, NodeInfo>,
+}
+impl NetworkMap {
+       fn borrow_parts(&mut self) -> MutNetworkMap {
+               MutNetworkMap {
+                       channels: &mut self.channels,
+                       nodes: &mut self.nodes,
+               }
+       }
+}
+impl std::fmt::Display for NetworkMap {
+       fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
+               write!(f, "Node id {} network map\n[Channels]\n", log_pubkey!(self.our_node_id))?;
+               for (key, val) in self.channels.iter() {
+                       write!(f, " {}: {}\n", key, val)?;
+               }
+               write!(f, "[Nodes]\n")?;
+               for (key, val) in self.nodes.iter() {
+                       write!(f, " {}: {}\n", log_pubkey!(key), val)?;
+               }
+               Ok(())
+       }
+}
 
 impl NetworkMap {
        #[cfg(feature = "non_bitcoin_chain_hash_routing")]
@@ -88,23 +150,44 @@ impl NetworkMap {
        fn get_key(short_channel_id: u64, _: Sha256dHash) -> u64 {
                short_channel_id
        }
+
+       #[cfg(feature = "non_bitcoin_chain_hash_routing")]
+       #[inline]
+       fn get_short_id(id: &(u64, Sha256dHash)) -> &u64 {
+               &id.0
+       }
+
+       #[cfg(not(feature = "non_bitcoin_chain_hash_routing"))]
+       #[inline]
+       fn get_short_id(id: &u64) -> &u64 {
+               id
+       }
 }
 
 /// A channel descriptor which provides a last-hop route to get_route
 pub struct RouteHint {
+       /// The node_id of the non-target end of the route
        pub src_node_id: PublicKey,
+       /// The short_channel_id of this channel
        pub short_channel_id: u64,
-       pub fee_base_msat: u64,
+       /// The static msat-denominated fee which must be paid to use this channel
+       pub fee_base_msat: u32,
+       /// The dynamic proportional fee which must be paid to use this channel, denominated in
+       /// millionths of the value being forwarded to the next hop.
        pub fee_proportional_millionths: u32,
+       /// The difference in CLTV values between this node and the next node.
        pub cltv_expiry_delta: u16,
+       /// The minimum value, in msat, which must be relayed to the next hop.
        pub htlc_minimum_msat: u64,
 }
 
 /// Tracks a view of the network, receiving updates from peers and generating Routes to
 /// payment destinations.
 pub struct Router {
-       secp_ctx: Secp256k1,
+       secp_ctx: Secp256k1<secp256k1::VerifyOnly>,
        network_map: RwLock<NetworkMap>,
+       chain_monitor: Arc<ChainWatchInterface>,
+       logger: Arc<Logger>,
 }
 
 macro_rules! secp_verify_sig {
@@ -117,10 +200,14 @@ macro_rules! secp_verify_sig {
 }
 
 impl RoutingMessageHandler for Router {
-       fn handle_node_announcement(&self, msg: &msgs::NodeAnnouncement) -> Result<(), HandleError> {
+       fn handle_node_announcement(&self, msg: &msgs::NodeAnnouncement) -> Result<bool, HandleError> {
                let msg_hash = Message::from_slice(&Sha256dHash::from_data(&msg.contents.encode()[..])[..]).unwrap();
                secp_verify_sig!(self.secp_ctx, &msg_hash, &msg.signature, &msg.contents.node_id);
 
+               if msg.contents.features.requires_unknown_bits() {
+                       panic!("Unknown-required-features NodeAnnouncements should never deserialize!");
+               }
+
                let mut network = self.network_map.write().unwrap();
                match network.nodes.get_mut(&msg.contents.node_id) {
                        None => Err(HandleError{err: "No existing channels for node_announcement", action: Some(ErrorAction::IgnoreError)}),
@@ -134,56 +221,98 @@ impl RoutingMessageHandler for Router {
                                node.rgb = msg.contents.rgb;
                                node.alias = msg.contents.alias;
                                node.addresses = msg.contents.addresses.clone();
-                               Ok(())
+                               Ok(msg.contents.excess_data.is_empty() && msg.contents.excess_address_data.is_empty() && !msg.contents.features.supports_unknown_bits())
                        }
                }
        }
 
        fn handle_channel_announcement(&self, msg: &msgs::ChannelAnnouncement) -> Result<bool, HandleError> {
+               if msg.contents.node_id_1 == msg.contents.node_id_2 || msg.contents.bitcoin_key_1 == msg.contents.bitcoin_key_2 {
+                       return Err(HandleError{err: "Channel announcement node had a channel with itself", action: Some(ErrorAction::IgnoreError)});
+               }
+
                let msg_hash = Message::from_slice(&Sha256dHash::from_data(&msg.contents.encode()[..])[..]).unwrap();
                secp_verify_sig!(self.secp_ctx, &msg_hash, &msg.node_signature_1, &msg.contents.node_id_1);
                secp_verify_sig!(self.secp_ctx, &msg_hash, &msg.node_signature_2, &msg.contents.node_id_2);
                secp_verify_sig!(self.secp_ctx, &msg_hash, &msg.bitcoin_signature_1, &msg.contents.bitcoin_key_1);
                secp_verify_sig!(self.secp_ctx, &msg_hash, &msg.bitcoin_signature_2, &msg.contents.bitcoin_key_2);
 
-               //TODO: Call blockchain thing to ask if the short_channel_id is valid
-               //TODO: Only allow bitcoin chain_hash
-
                if msg.contents.features.requires_unknown_bits() {
-                       return Err(HandleError{err: "Channel announcement required unknown feature flags", action: None});
+                       panic!("Unknown-required-features ChannelAnnouncements should never deserialize!");
                }
 
-               let mut network = self.network_map.write().unwrap();
+               let checked_utxo = match self.chain_monitor.get_chain_utxo(msg.contents.chain_hash, msg.contents.short_channel_id) {
+                       Ok((script_pubkey, _value)) => {
+                               let expected_script = Builder::new().push_opcode(opcodes::All::OP_PUSHNUM_2)
+                                                                   .push_slice(&msg.contents.bitcoin_key_1.serialize())
+                                                                   .push_slice(&msg.contents.bitcoin_key_2.serialize())
+                                                                   .push_opcode(opcodes::All::OP_PUSHNUM_2).push_opcode(opcodes::All::OP_CHECKMULTISIG).into_script().to_v0_p2wsh();
+                               if script_pubkey != expected_script {
+                                       return Err(HandleError{err: "Channel announcement keys didn't match on-chain script", action: Some(ErrorAction::IgnoreError)});
+                               }
+                               //TODO: Check if value is worth storing, use it to inform routing, and compare it
+                               //to the new HTLC max field in channel_update
+                               true
+                       },
+                       Err(ChainError::NotSupported) => {
+                               // Tentatively accept, potentially exposing us to DoS attacks
+                               false
+                       },
+                       Err(ChainError::NotWatched) => {
+                               return Err(HandleError{err: "Channel announced on an unknown chain", action: Some(ErrorAction::IgnoreError)});
+                       },
+                       Err(ChainError::UnknownTx) => {
+                               return Err(HandleError{err: "Channel announced without corresponding UTXO entry", action: Some(ErrorAction::IgnoreError)});
+                       },
+               };
+
+               let mut network_lock = self.network_map.write().unwrap();
+               let network = network_lock.borrow_parts();
+
+               let chan_info = ChannelInfo {
+                               features: msg.contents.features.clone(),
+                               one_to_two: DirectionalChannelInfo {
+                                       src_node_id: msg.contents.node_id_1.clone(),
+                                       last_update: 0,
+                                       enabled: false,
+                                       cltv_expiry_delta: u16::max_value(),
+                                       htlc_minimum_msat: u64::max_value(),
+                                       fee_base_msat: u32::max_value(),
+                                       fee_proportional_millionths: u32::max_value(),
+                               },
+                               two_to_one: DirectionalChannelInfo {
+                                       src_node_id: msg.contents.node_id_2.clone(),
+                                       last_update: 0,
+                                       enabled: false,
+                                       cltv_expiry_delta: u16::max_value(),
+                                       htlc_minimum_msat: u64::max_value(),
+                                       fee_base_msat: u32::max_value(),
+                                       fee_proportional_millionths: u32::max_value(),
+                               }
+                       };
 
                match network.channels.entry(NetworkMap::get_key(msg.contents.short_channel_id, msg.contents.chain_hash)) {
-                       Entry::Occupied(_) => {
+                       Entry::Occupied(mut entry) => {
                                //TODO: because asking the blockchain if short_channel_id is valid is only optional
                                //in the blockchain API, we need to handle it smartly here, though its unclear
                                //exactly how...
-                               return Err(HandleError{err: "Already have knowledge of channel", action: Some(ErrorAction::IgnoreError)})
+                               if checked_utxo {
+                                       // Either our UTXO provider is busted, there was a reorg, or the UTXO provider
+                                       // only sometimes returns results. In any case remove the previous entry. Note
+                                       // that the spec expects us to "blacklist" the node_ids involved, but we can't
+                                       // do that because
+                                       // a) we don't *require* a UTXO provider that always returns results.
+                                       // b) we don't track UTXOs of channels we know about and remove them if they
+                                       //    get reorg'd out.
+                                       // c) it's unclear how to do so without exposing ourselves to massive DoS risk.
+                                       Self::remove_channel_in_nodes(network.nodes, &entry.get(), msg.contents.short_channel_id);
+                                       *entry.get_mut() = chan_info;
+                               } else {
+                                       return Err(HandleError{err: "Already have knowledge of channel", action: Some(ErrorAction::IgnoreError)})
+                               }
                        },
                        Entry::Vacant(entry) => {
-                               entry.insert(ChannelInfo {
-                                       features: msg.contents.features.clone(),
-                                       one_to_two: DirectionalChannelInfo {
-                                               src_node_id: msg.contents.node_id_1.clone(),
-                                               last_update: 0,
-                                               enabled: false,
-                                               cltv_expiry_delta: u16::max_value(),
-                                               htlc_minimum_msat: u64::max_value(),
-                                               fee_base_msat: u32::max_value(),
-                                               fee_proportional_millionths: u32::max_value(),
-                                       },
-                                       two_to_one: DirectionalChannelInfo {
-                                               src_node_id: msg.contents.node_id_2.clone(),
-                                               last_update: 0,
-                                               enabled: false,
-                                               cltv_expiry_delta: u16::max_value(),
-                                               htlc_minimum_msat: u64::max_value(),
-                                               fee_base_msat: u32::max_value(),
-                                               fee_proportional_millionths: u32::max_value(),
-                                       }
-                               });
+                               entry.insert(chan_info);
                        }
                };
 
@@ -212,7 +341,7 @@ impl RoutingMessageHandler for Router {
                add_channel_to_node!(msg.contents.node_id_1);
                add_channel_to_node!(msg.contents.node_id_2);
 
-               Ok(!msg.contents.features.supports_unknown_bits())
+               Ok(msg.contents.excess_data.is_empty() && !msg.contents.features.supports_unknown_bits())
        }
 
        fn handle_htlc_fail_channel_update(&self, update: &msgs::HTLCFailChannelUpdate) {
@@ -222,12 +351,14 @@ impl RoutingMessageHandler for Router {
                        },
                        &msgs::HTLCFailChannelUpdate::ChannelClosed { ref short_channel_id } => {
                                let mut network = self.network_map.write().unwrap();
-                               network.channels.remove(short_channel_id);
+                               if let Some(chan) = network.channels.remove(short_channel_id) {
+                                       Self::remove_channel_in_nodes(&mut network.nodes, &chan, *short_channel_id);
+                               }
                        },
                }
        }
 
-       fn handle_channel_update(&self, msg: &msgs::ChannelUpdate) -> Result<(), HandleError> {
+       fn handle_channel_update(&self, msg: &msgs::ChannelUpdate) -> Result<bool, HandleError> {
                let mut network = self.network_map.write().unwrap();
                let dest_node_id;
                let chan_enabled = msg.contents.flags & (1 << 1) != (1 << 1);
@@ -293,7 +424,7 @@ impl RoutingMessageHandler for Router {
                        mut_node.lowest_inbound_channel_fee_proportional_millionths = lowest_inbound_channel_fee_proportional_millionths;
                }
 
-               Ok(())
+               Ok(msg.contents.excess_data.is_empty())
        }
 }
 
@@ -301,6 +432,7 @@ impl RoutingMessageHandler for Router {
 struct RouteGraphNode {
        pubkey: PublicKey,
        lowest_fee_to_peer_through_node: u64,
+       lowest_fee_to_node: u64,
 }
 
 impl cmp::Ord for RouteGraphNode {
@@ -325,7 +457,8 @@ struct DummyDirectionalChannelInfo {
 }
 
 impl Router {
-       pub fn new(our_pubkey: PublicKey) -> Router {
+       /// Creates a new router with the given node_id to be used as the source for get_route()
+       pub fn new(our_pubkey: PublicKey, chain_monitor: Arc<ChainWatchInterface>, logger: Arc<Logger>) -> Router {
                let mut nodes = HashMap::new();
                nodes.insert(our_pubkey.clone(), NodeInfo {
                        channels: Vec::new(),
@@ -338,15 +471,23 @@ impl Router {
                        addresses: Vec::new(),
                });
                Router {
-                       secp_ctx: Secp256k1::new(),
+                       secp_ctx: Secp256k1::verification_only(),
                        network_map: RwLock::new(NetworkMap {
                                channels: HashMap::new(),
                                our_node_id: our_pubkey,
                                nodes: nodes,
                        }),
+                       chain_monitor,
+                       logger,
                }
        }
 
+       /// Dumps the entire network view of this Router to the logger provided in the constructor at
+       /// level Trace
+       pub fn trace_state(&self) {
+               log_trace!(self, "{}", self.network_map.read().unwrap());
+       }
+
        /// Get network addresses by node id
        pub fn get_addresses(&self, pubkey: &PublicKey) -> Option<Vec<NetAddress>> {
                let network = self.network_map.read().unwrap();
@@ -363,14 +504,38 @@ impl Router {
                unimplemented!();
        }
 
+       fn remove_channel_in_nodes(nodes: &mut HashMap<PublicKey, NodeInfo>, chan: &ChannelInfo, short_channel_id: u64) {
+               macro_rules! remove_from_node {
+                       ($node_id: expr) => {
+                               if let Entry::Occupied(mut entry) = nodes.entry($node_id) {
+                                       entry.get_mut().channels.retain(|chan_id| {
+                                               short_channel_id != *NetworkMap::get_short_id(chan_id)
+                                       });
+                                       if entry.get().channels.is_empty() {
+                                               entry.remove_entry();
+                                       }
+                               } else {
+                                       panic!("Had channel that pointed to unknown node (ie inconsistent network map)!");
+                               }
+                       }
+               }
+               remove_from_node!(chan.one_to_two.src_node_id);
+               remove_from_node!(chan.two_to_one.src_node_id);
+       }
+
        /// Gets a route from us to the given target node.
+       ///
        /// Extra routing hops between known nodes and the target will be used if they are included in
        /// last_hops.
+       ///
        /// If some channels aren't announced, it may be useful to fill in a first_hops with the
        /// results from a local ChannelManager::list_usable_channels() call. If it is filled in, our
        /// (this Router's) view of our local channels will be ignored, and only those in first_hops
-       /// will be used. Panics if first_hops contains channels without short_channel_ids
+       /// will be used.
+       ///
+       /// Panics if first_hops contains channels without short_channel_ids
        /// (ChannelManager::list_usable_channels will never include such channels).
+       ///
        /// The fees on channels from us to next-hops are ignored (as they are assumed to all be
        /// equal), however the enabled/disabled bit on such channels as well as the htlc_minimum_msat
        /// *is* checked as they may change based on the receiving node.
@@ -383,6 +548,10 @@ impl Router {
                        return Err(HandleError{err: "Cannot generate a route to ourselves", action: None});
                }
 
+               if final_value_msat > 21_000_000 * 1_0000_0000 * 1000 {
+                       return Err(HandleError{err: "Cannot generate a route of more value than all existing satoshis", action: None});
+               }
+
                // We do a dest-to-source Dijkstra's sorting by each node's distance from the destination
                // plus the minimum per-HTLC fee to get from it to another node (aka "shitty A*").
                // TODO: There are a few tweaks we could do, including possibly pre-calculating more stuff
@@ -428,39 +597,49 @@ impl Router {
                        ( $chan_id: expr, $dest_node_id: expr, $directional_info: expr, $starting_fee_msat: expr ) => {
                                //TODO: Explore simply adding fee to hit htlc_minimum_msat
                                if $starting_fee_msat as u64 + final_value_msat > $directional_info.htlc_minimum_msat {
-                                       let new_fee = $directional_info.fee_base_msat as u64 + ($starting_fee_msat + final_value_msat) * ($directional_info.fee_proportional_millionths as u64) / 1000000;
-                                       let mut total_fee = $starting_fee_msat as u64;
-                                       let mut hm_entry = dist.entry(&$directional_info.src_node_id);
-                                       let old_entry = hm_entry.or_insert_with(|| {
-                                               let node = network.nodes.get(&$directional_info.src_node_id).unwrap();
-                                               (u64::max_value(),
-                                                       node.lowest_inbound_channel_fee_base_msat as u64,
-                                                       node.lowest_inbound_channel_fee_proportional_millionths as u64,
-                                                       RouteHop {
-                                                               pubkey: PublicKey::new(),
-                                                               short_channel_id: 0,
-                                                               fee_msat: 0,
-                                                               cltv_expiry_delta: 0,
-                                               })
-                                       });
-                                       if $directional_info.src_node_id != network.our_node_id {
-                                               // Ignore new_fee for channel-from-us as we assume all channels-from-us
-                                               // will have the same effective-fee
-                                               total_fee += new_fee;
-                                               total_fee += old_entry.2 * (final_value_msat + total_fee) / 1000000 + old_entry.1;
-                                       }
-                                       let new_graph_node = RouteGraphNode {
-                                               pubkey: $directional_info.src_node_id,
-                                               lowest_fee_to_peer_through_node: total_fee,
-                                       };
-                                       if old_entry.0 > total_fee {
-                                               targets.push(new_graph_node);
-                                               old_entry.0 = total_fee;
-                                               old_entry.3 = RouteHop {
-                                                       pubkey: $dest_node_id.clone(),
-                                                       short_channel_id: $chan_id.clone(),
-                                                       fee_msat: new_fee, // This field is ignored on the last-hop anyway
-                                                       cltv_expiry_delta: $directional_info.cltv_expiry_delta as u32,
+                                       let proportional_fee_millions = ($starting_fee_msat + final_value_msat).checked_mul($directional_info.fee_proportional_millionths as u64);
+                                       if let Some(new_fee) = proportional_fee_millions.and_then(|part| {
+                                                       ($directional_info.fee_base_msat as u64).checked_add(part / 1000000) })
+                                       {
+                                               let mut total_fee = $starting_fee_msat as u64;
+                                               let hm_entry = dist.entry(&$directional_info.src_node_id);
+                                               let old_entry = hm_entry.or_insert_with(|| {
+                                                       let node = network.nodes.get(&$directional_info.src_node_id).unwrap();
+                                                       (u64::max_value(),
+                                                               node.lowest_inbound_channel_fee_base_msat,
+                                                               node.lowest_inbound_channel_fee_proportional_millionths,
+                                                               RouteHop {
+                                                                       pubkey: $dest_node_id.clone(),
+                                                                       short_channel_id: 0,
+                                                                       fee_msat: 0,
+                                                                       cltv_expiry_delta: 0,
+                                                       })
+                                               });
+                                               if $directional_info.src_node_id != network.our_node_id {
+                                                       // Ignore new_fee for channel-from-us as we assume all channels-from-us
+                                                       // will have the same effective-fee
+                                                       total_fee += new_fee;
+                                                       if let Some(fee_inc) = final_value_msat.checked_add(total_fee).and_then(|inc| { (old_entry.2 as u64).checked_mul(inc) }) {
+                                                               total_fee += fee_inc / 1000000 + (old_entry.1 as u64);
+                                                       } else {
+                                                               // max_value means we'll always fail the old_entry.0 > total_fee check
+                                                               total_fee = u64::max_value();
+                                                       }
+                                               }
+                                               let new_graph_node = RouteGraphNode {
+                                                       pubkey: $directional_info.src_node_id,
+                                                       lowest_fee_to_peer_through_node: total_fee,
+                                                       lowest_fee_to_node: $starting_fee_msat as u64 + new_fee,
+                                               };
+                                               if old_entry.0 > total_fee {
+                                                       targets.push(new_graph_node);
+                                                       old_entry.0 = total_fee;
+                                                       old_entry.3 = RouteHop {
+                                                               pubkey: $dest_node_id.clone(),
+                                                               short_channel_id: $chan_id.clone(),
+                                                               fee_msat: new_fee, // This field is ignored on the last-hop anyway
+                                                               cltv_expiry_delta: $directional_info.cltv_expiry_delta as u32,
+                                                       }
                                                }
                                        }
                                }
@@ -515,28 +694,29 @@ impl Router {
                        }
                }
 
-               while let Some(RouteGraphNode { pubkey, lowest_fee_to_peer_through_node }) = targets.pop() {
+               while let Some(RouteGraphNode { pubkey, lowest_fee_to_node, .. }) = targets.pop() {
                        if pubkey == network.our_node_id {
                                let mut res = vec!(dist.remove(&network.our_node_id).unwrap().3);
                                while res.last().unwrap().pubkey != *target {
-                                       let new_entry = dist.remove(&res.last().unwrap().pubkey).unwrap().3;
+                                       let new_entry = match dist.remove(&res.last().unwrap().pubkey) {
+                                               Some(hop) => hop.3,
+                                               None => return Err(HandleError{err: "Failed to find a non-fee-overflowing path to the given destination", action: None}),
+                                       };
                                        res.last_mut().unwrap().fee_msat = new_entry.fee_msat;
                                        res.last_mut().unwrap().cltv_expiry_delta = new_entry.cltv_expiry_delta;
                                        res.push(new_entry);
                                }
                                res.last_mut().unwrap().fee_msat = final_value_msat;
                                res.last_mut().unwrap().cltv_expiry_delta = final_cltv;
-                               return Ok(Route {
-                                       hops: res
-                               });
+                               let route = Route { hops: res };
+                               log_trace!(self, "Got route: {}", log_route!(route));
+                               return Ok(route);
                        }
 
                        match network.nodes.get(&pubkey) {
                                None => {},
                                Some(node) => {
-                                       let mut fee = lowest_fee_to_peer_through_node - node.lowest_inbound_channel_fee_base_msat as u64;
-                                       fee -= node.lowest_inbound_channel_fee_proportional_millionths as u64 * (fee + final_value_msat) / 1000000;
-                                       add_entries_to_cheapest_to_target_node!(node, &pubkey, fee);
+                                       add_entries_to_cheapest_to_target_node!(node, &pubkey, lowest_fee_to_node);
                                },
                        }
                }
@@ -547,21 +727,30 @@ impl Router {
 
 #[cfg(test)]
 mod tests {
+       use chain::chaininterface;
        use ln::channelmanager;
        use ln::router::{Router,NodeInfo,NetworkMap,ChannelInfo,DirectionalChannelInfo,RouteHint};
        use ln::msgs::GlobalFeatures;
+       use util::test_utils;
+       use util::logger::Logger;
 
-       use bitcoin::util::misc::hex_bytes;
        use bitcoin::util::hash::Sha256dHash;
+       use bitcoin::network::constants::Network;
+
+       use hex;
 
        use secp256k1::key::{PublicKey,SecretKey};
        use secp256k1::Secp256k1;
 
+       use std::sync::Arc;
+
        #[test]
        fn route_test() {
                let secp_ctx = Secp256k1::new();
-               let our_id = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex_bytes("0101010101010101010101010101010101010101010101010101010101010101").unwrap()[..]).unwrap()).unwrap();
-               let router = Router::new(our_id);
+               let our_id = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex::decode("0101010101010101010101010101010101010101010101010101010101010101").unwrap()[..]).unwrap());
+               let logger: Arc<Logger> = Arc::new(test_utils::TestLogger::new());
+               let chain_monitor = Arc::new(chaininterface::ChainWatchInterfaceUtil::new(Network::Testnet, Arc::clone(&logger)));
+               let router = Router::new(our_id, chain_monitor, Arc::clone(&logger));
 
                // Build network from our_id to node8:
                //
@@ -620,14 +809,14 @@ mod tests {
                // chan11 1-to-2: enabled, 0 fee
                // chan11 2-to-1: enabled, 0 fee
 
-               let node1 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex_bytes("0202020202020202020202020202020202020202020202020202020202020202").unwrap()[..]).unwrap()).unwrap();
-               let node2 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex_bytes("0303030303030303030303030303030303030303030303030303030303030303").unwrap()[..]).unwrap()).unwrap();
-               let node3 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex_bytes("0404040404040404040404040404040404040404040404040404040404040404").unwrap()[..]).unwrap()).unwrap();
-               let node4 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex_bytes("0505050505050505050505050505050505050505050505050505050505050505").unwrap()[..]).unwrap()).unwrap();
-               let node5 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex_bytes("0606060606060606060606060606060606060606060606060606060606060606").unwrap()[..]).unwrap()).unwrap();
-               let node6 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex_bytes("0707070707070707070707070707070707070707070707070707070707070707").unwrap()[..]).unwrap()).unwrap();
-               let node7 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex_bytes("0808080808080808080808080808080808080808080808080808080808080808").unwrap()[..]).unwrap()).unwrap();
-               let node8 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex_bytes("0909090909090909090909090909090909090909090909090909090909090909").unwrap()[..]).unwrap()).unwrap();
+               let node1 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex::decode("0202020202020202020202020202020202020202020202020202020202020202").unwrap()[..]).unwrap());
+               let node2 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex::decode("0303030303030303030303030303030303030303030303030303030303030303").unwrap()[..]).unwrap());
+               let node3 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex::decode("0404040404040404040404040404040404040404040404040404040404040404").unwrap()[..]).unwrap());
+               let node4 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex::decode("0505050505050505050505050505050505050505050505050505050505050505").unwrap()[..]).unwrap());
+               let node5 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex::decode("0606060606060606060606060606060606060606060606060606060606060606").unwrap()[..]).unwrap());
+               let node6 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex::decode("0707070707070707070707070707070707070707070707070707070707070707").unwrap()[..]).unwrap());
+               let node7 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex::decode("0808080808080808080808080808080808080808080808080808080808080808").unwrap()[..]).unwrap());
+               let node8 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex::decode("0909090909090909090909090909090909090909090909090909090909090909").unwrap()[..]).unwrap());
 
                let zero_hash = Sha256dHash::from_data(&[0; 32]);