X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Fnetwork_graph.rs;h=a26b549b43d45de4d96cc91ddf3d32921c241f3b;hb=1a24dcc3e91240e5b1d1df24bfde063e84da1472;hp=7f9f5c3292d901ed235b843c3e0ef1a2e4493284;hpb=11d644824efc78624330a7acbc96eabf9d481e89;p=rust-lightning diff --git a/lightning/src/routing/network_graph.rs b/lightning/src/routing/network_graph.rs index 7f9f5c32..a26b549b 100644 --- a/lightning/src/routing/network_graph.rs +++ b/lightning/src/routing/network_graph.rs @@ -43,6 +43,13 @@ use sync::Mutex; use core::ops::Deref; use bitcoin::hashes::hex::ToHex; +#[cfg(feature = "std")] +use std::time::{SystemTime, UNIX_EPOCH}; + +/// We remove stale channel directional info two weeks after the last update, per BOLT 7's +/// suggestion. +const STALE_CHANNEL_UPDATE_AGE_LIMIT_SECS: u64 = 60 * 60 * 24 * 14; + /// The maximum number of extra bytes which we do not understand in a gossip message before we will /// refuse to relay the message. const MAX_EXCESS_BYTES_FOR_RELAY: usize = 1024; @@ -242,6 +249,14 @@ where C::Target: chain::Access, L::Target: Logger self.chain_access = chain_access; } + /// Gets a reference to the underlying [`NetworkGraph`] which was provided in + /// [`NetGraphMsgHandler::new`]. + /// + /// (C-not exported) as bindings don't support a reference-to-a-reference yet + pub fn network_graph(&self) -> &G { + &self.network_graph + } + /// Returns true when a full routing table sync should be performed with a peer. fn should_request_full_sync(&self, _node_id: &PublicKey) -> bool { //TODO: Determine whether to request a full sync based on the network map. @@ -279,10 +294,21 @@ where C::Target: chain::Access, L::Target: Logger } macro_rules! secp_verify_sig { - ( $secp_ctx: expr, $msg: expr, $sig: expr, $pubkey: expr ) => { + ( $secp_ctx: expr, $msg: expr, $sig: expr, $pubkey: expr, $msg_type: expr ) => { match $secp_ctx.verify($msg, $sig, $pubkey) { Ok(_) => {}, - Err(_) => return Err(LightningError{err: "Invalid signature from remote node".to_owned(), action: ErrorAction::IgnoreError}), + Err(_) => { + return Err(LightningError { + err: format!("Invalid signature on {} message", $msg_type), + action: ErrorAction::SendWarningMessage { + msg: msgs::WarningMessage { + channel_id: [0; 32], + data: format!("Invalid signature on {} message", $msg_type), + }, + log_level: Level::Trace, + }, + }); + }, } }; } @@ -628,6 +654,10 @@ pub struct ChannelInfo { /// Everything else is useful only for sending out for initial routing sync. /// Not stored if contains excess data to prevent DoS. pub announcement_message: Option, + /// The timestamp when we received the announcement, if we are running with feature = "std" + /// (which we can probably assume we are - no-std environments probably won't have a full + /// network graph in memory!). + announcement_received_time: u64, } impl fmt::Display for ChannelInfo { @@ -640,6 +670,7 @@ impl fmt::Display for ChannelInfo { impl_writeable_tlv_based!(ChannelInfo, { (0, features, required), + (1, announcement_received_time, (default_value, 0)), (2, node_one, required), (4, one_to_two, required), (6, node_two, required), @@ -830,7 +861,7 @@ impl NetworkGraph { /// routing messages from a source using a protocol other than the lightning P2P protocol. pub fn update_node_from_announcement(&self, msg: &msgs::NodeAnnouncement, secp_ctx: &Secp256k1) -> Result<(), LightningError> { let msg_hash = hash_to_message!(&Sha256dHash::hash(&msg.contents.encode()[..])[..]); - secp_verify_sig!(secp_ctx, &msg_hash, &msg.signature, &msg.contents.node_id); + secp_verify_sig!(secp_ctx, &msg_hash, &msg.signature, &msg.contents.node_id, "node_announcement"); self.update_node_from_announcement_intern(&msg.contents, Some(&msg)) } @@ -890,10 +921,10 @@ impl NetworkGraph { C::Target: chain::Access, { let msg_hash = hash_to_message!(&Sha256dHash::hash(&msg.contents.encode()[..])[..]); - secp_verify_sig!(secp_ctx, &msg_hash, &msg.node_signature_1, &msg.contents.node_id_1); - secp_verify_sig!(secp_ctx, &msg_hash, &msg.node_signature_2, &msg.contents.node_id_2); - secp_verify_sig!(secp_ctx, &msg_hash, &msg.bitcoin_signature_1, &msg.contents.bitcoin_key_1); - secp_verify_sig!(secp_ctx, &msg_hash, &msg.bitcoin_signature_2, &msg.contents.bitcoin_key_2); + secp_verify_sig!(secp_ctx, &msg_hash, &msg.node_signature_1, &msg.contents.node_id_1, "channel_announcement"); + secp_verify_sig!(secp_ctx, &msg_hash, &msg.node_signature_2, &msg.contents.node_id_2, "channel_announcement"); + secp_verify_sig!(secp_ctx, &msg_hash, &msg.bitcoin_signature_1, &msg.contents.bitcoin_key_1, "channel_announcement"); + secp_verify_sig!(secp_ctx, &msg_hash, &msg.bitcoin_signature_2, &msg.contents.bitcoin_key_2, "channel_announcement"); self.update_channel_from_unsigned_announcement_intern(&msg.contents, Some(msg), chain_access) } @@ -952,6 +983,13 @@ impl NetworkGraph { }, }; + #[allow(unused_mut, unused_assignments)] + let mut announcement_received_time = 0; + #[cfg(feature = "std")] + { + announcement_received_time = SystemTime::now().duration_since(UNIX_EPOCH).expect("Time must be > 1970").as_secs(); + } + let chan_info = ChannelInfo { features: msg.features.clone(), node_one: NodeId::from_pubkey(&msg.node_id_1), @@ -961,6 +999,7 @@ impl NetworkGraph { capacity_sats: utxo_value, announcement_message: if msg.excess_data.len() <= MAX_EXCESS_BYTES_FOR_RELAY { full_msg.cloned() } else { None }, + announcement_received_time, }; let mut channels = self.channels.write().unwrap(); @@ -1045,12 +1084,78 @@ impl NetworkGraph { } } + #[cfg(feature = "std")] + /// Removes information about channels that we haven't heard any updates about in some time. + /// This can be used regularly to prune the network graph of channels that likely no longer + /// exist. + /// + /// While there is no formal requirement that nodes regularly re-broadcast their channel + /// updates every two weeks, the non-normative section of BOLT 7 currently suggests that + /// pruning occur for updates which are at least two weeks old, which we implement here. + /// + /// Note that for users of the `lightning-background-processor` crate this method may be + /// automatically called regularly for you. + /// + /// This method is only available with the `std` feature. See + /// [`NetworkGraph::remove_stale_channels_with_time`] for `no-std` use. + pub fn remove_stale_channels(&self) { + let time = SystemTime::now().duration_since(UNIX_EPOCH).expect("Time must be > 1970").as_secs(); + self.remove_stale_channels_with_time(time); + } + + /// Removes information about channels that we haven't heard any updates about in some time. + /// This can be used regularly to prune the network graph of channels that likely no longer + /// exist. + /// + /// While there is no formal requirement that nodes regularly re-broadcast their channel + /// updates every two weeks, the non-normative section of BOLT 7 currently suggests that + /// pruning occur for updates which are at least two weeks old, which we implement here. + /// + /// This function takes the current unix time as an argument. For users with the `std` feature + /// enabled, [`NetworkGraph::remove_stale_channels`] may be preferable. + pub fn remove_stale_channels_with_time(&self, current_time_unix: u64) { + let mut channels = self.channels.write().unwrap(); + // Time out if we haven't received an update in at least 14 days. + if current_time_unix > u32::max_value() as u64 { return; } // Remove by 2106 + if current_time_unix < STALE_CHANNEL_UPDATE_AGE_LIMIT_SECS { return; } + let min_time_unix: u32 = (current_time_unix - STALE_CHANNEL_UPDATE_AGE_LIMIT_SECS) as u32; + // Sadly BTreeMap::retain was only stabilized in 1.53 so we can't switch to it for some + // time. + let mut scids_to_remove = Vec::new(); + for (scid, info) in channels.iter_mut() { + if info.one_to_two.is_some() && info.one_to_two.as_ref().unwrap().last_update < min_time_unix { + info.one_to_two = None; + } + if info.two_to_one.is_some() && info.two_to_one.as_ref().unwrap().last_update < min_time_unix { + info.two_to_one = None; + } + if info.one_to_two.is_none() && info.two_to_one.is_none() { + // We check the announcement_received_time here to ensure we don't drop + // announcements that we just received and are just waiting for our peer to send a + // channel_update for. + if info.announcement_received_time < min_time_unix as u64 { + scids_to_remove.push(*scid); + } + } + } + if !scids_to_remove.is_empty() { + let mut nodes = self.nodes.write().unwrap(); + for scid in scids_to_remove { + let info = channels.remove(&scid).expect("We just accessed this scid, it should be present"); + Self::remove_channel_in_nodes(&mut nodes, &info, scid); + } + } + } + /// For an already known (from announcement) channel, update info about one of the directions /// of the channel. /// /// You probably don't want to call this directly, instead relying on a NetGraphMsgHandler's /// RoutingMessageHandler implementation to call it indirectly. This may be useful to accept /// routing messages from a source using a protocol other than the lightning P2P protocol. + /// + /// If built with `no-std`, any updates with a timestamp more than two weeks in the past or + /// materially in the future will be rejected. pub fn update_channel(&self, msg: &msgs::ChannelUpdate, secp_ctx: &Secp256k1) -> Result<(), LightningError> { self.update_channel_intern(&msg.contents, Some(&msg), Some((&msg.signature, secp_ctx))) } @@ -1058,6 +1163,9 @@ impl NetworkGraph { /// For an already known (from announcement) channel, update info about one of the directions /// of the channel without verifying the associated signatures. Because we aren't given the /// associated signatures here we cannot relay the channel update to any of our peers. + /// + /// If built with `no-std`, any updates with a timestamp more than two weeks in the past or + /// materially in the future will be rejected. pub fn update_channel_unsigned(&self, msg: &msgs::UnsignedChannelUpdate) -> Result<(), LightningError> { self.update_channel_intern(msg, None, None::<(&secp256k1::Signature, &Secp256k1)>) } @@ -1067,6 +1175,19 @@ impl NetworkGraph { let chan_enabled = msg.flags & (1 << 1) != (1 << 1); let chan_was_enabled; + #[cfg(all(feature = "std", not(test), not(feature = "_test_utils")))] + { + // Note that many tests rely on being able to set arbitrarily old timestamps, thus we + // disable this check during tests! + let time = SystemTime::now().duration_since(UNIX_EPOCH).expect("Time must be > 1970").as_secs(); + if (msg.timestamp as u64) < time - STALE_CHANNEL_UPDATE_AGE_LIMIT_SECS { + return Err(LightningError{err: "channel_update is older than two weeks old".to_owned(), action: ErrorAction::IgnoreAndLog(Level::Gossip)}); + } + if msg.timestamp as u64 > time + 60 * 60 * 24 { + return Err(LightningError{err: "channel_update has a timestamp more than a day in the future".to_owned(), action: ErrorAction::IgnoreAndLog(Level::Gossip)}); + } + } + let mut channels = self.channels.write().unwrap(); match channels.get_mut(&msg.short_channel_id) { None => return Err(LightningError{err: "Couldn't find channel for update".to_owned(), action: ErrorAction::IgnoreError}), @@ -1129,7 +1250,7 @@ impl NetworkGraph { secp_verify_sig!(ctx, &msg_hash, &sig, &PublicKey::from_slice(channel.node_two.as_slice()).map_err(|_| LightningError{ err: "Couldn't parse source node pubkey".to_owned(), action: ErrorAction::IgnoreAndLog(Level::Debug) - })?); + })?, "channel_update"); } maybe_update_channel_info!(channel.two_to_one, channel.node_two); } else { @@ -1138,7 +1259,7 @@ impl NetworkGraph { secp_verify_sig!(ctx, &msg_hash, &sig, &PublicKey::from_slice(channel.node_one.as_slice()).map_err(|_| LightningError{ err: "Couldn't parse destination node pubkey".to_owned(), action: ErrorAction::IgnoreAndLog(Level::Debug) - })?); + })?, "channel_update"); } maybe_update_channel_info!(channel.one_to_two, channel.node_one); } @@ -1250,6 +1371,8 @@ mod tests { use util::events::{Event, EventHandler, MessageSendEvent, MessageSendEventsProvider}; use util::scid_utils::scid_from_parts; + use super::STALE_CHANNEL_UPDATE_AGE_LIMIT_SECS; + use bitcoin::hashes::sha256d::Hash as Sha256dHash; use bitcoin::hashes::Hash; use bitcoin::network::constants::Network; @@ -1410,7 +1533,7 @@ mod tests { contents: valid_announcement.contents.clone() }) { Ok(_) => panic!(), - Err(e) => assert_eq!(e.err, "Invalid signature from remote node") + Err(e) => assert_eq!(e.err, "Invalid signature on node_announcement message") }; let announcement_with_data = get_signed_node_announcement(|unsigned_announcement| { @@ -1539,7 +1662,7 @@ mod tests { invalid_sig_announcement.contents.excess_data = Vec::new(); match net_graph_msg_handler.handle_channel_announcement(&invalid_sig_announcement) { Ok(_) => panic!(), - Err(e) => assert_eq!(e.err, "Invalid signature from remote node") + Err(e) => assert_eq!(e.err, "Invalid signature on channel_announcement message") }; let channel_to_itself_announcement = get_signed_channel_announcement(|_| {}, node_1_privkey, node_1_privkey, &secp_ctx); @@ -1648,7 +1771,7 @@ mod tests { invalid_sig_channel_update.signature = secp_ctx.sign(&fake_msghash, node_1_privkey); match net_graph_msg_handler.handle_channel_update(&invalid_sig_channel_update) { Ok(_) => panic!(), - Err(e) => assert_eq!(e.err, "Invalid signature from remote node") + Err(e) => assert_eq!(e.err, "Invalid signature on channel_update message") }; } @@ -1733,28 +1856,73 @@ mod tests { } // Permanent closing deletes a channel + net_graph_msg_handler.handle_event(&Event::PaymentPathFailed { + payment_id: None, + payment_hash: PaymentHash([0; 32]), + rejected_by_dest: false, + all_paths_failed: true, + path: vec![], + network_update: Some(NetworkUpdate::ChannelClosed { + short_channel_id, + is_permanent: true, + }), + short_channel_id: None, + retry: None, + error_code: None, + error_data: None, + }); + + assert_eq!(network_graph.read_only().channels().len(), 0); + // Nodes are also deleted because there are no associated channels anymore + assert_eq!(network_graph.read_only().nodes().len(), 0); + // TODO: Test NetworkUpdate::NodeFailure, which is not implemented yet. + } + + #[test] + fn test_channel_timeouts() { + // Test the removal of channels with `remove_stale_channels`. + let logger = test_utils::TestLogger::new(); + let chain_source = Arc::new(test_utils::TestChainSource::new(Network::Testnet)); + let genesis_hash = genesis_block(Network::Testnet).header.block_hash(); + let network_graph = NetworkGraph::new(genesis_hash); + let net_graph_msg_handler = NetGraphMsgHandler::new(&network_graph, Some(chain_source.clone()), &logger); + let secp_ctx = Secp256k1::new(); + + let node_1_privkey = &SecretKey::from_slice(&[42; 32]).unwrap(); + let node_2_privkey = &SecretKey::from_slice(&[41; 32]).unwrap(); + + let valid_channel_announcement = get_signed_channel_announcement(|_| {}, node_1_privkey, node_2_privkey, &secp_ctx); + let short_channel_id = valid_channel_announcement.contents.short_channel_id; + let chain_source: Option<&test_utils::TestChainSource> = None; + assert!(network_graph.update_channel_from_announcement(&valid_channel_announcement, &chain_source, &secp_ctx).is_ok()); + assert!(network_graph.read_only().channels().get(&short_channel_id).is_some()); + + let valid_channel_update = get_signed_channel_update(|_| {}, node_1_privkey, &secp_ctx); + assert!(net_graph_msg_handler.handle_channel_update(&valid_channel_update).is_ok()); + assert!(network_graph.read_only().channels().get(&short_channel_id).unwrap().one_to_two.is_some()); + + network_graph.remove_stale_channels_with_time(100 + STALE_CHANNEL_UPDATE_AGE_LIMIT_SECS); + assert_eq!(network_graph.read_only().channels().len(), 1); + assert_eq!(network_graph.read_only().nodes().len(), 2); + + network_graph.remove_stale_channels_with_time(101 + STALE_CHANNEL_UPDATE_AGE_LIMIT_SECS); + #[cfg(feature = "std")] { - net_graph_msg_handler.handle_event(&Event::PaymentPathFailed { - payment_id: None, - payment_hash: PaymentHash([0; 32]), - rejected_by_dest: false, - all_paths_failed: true, - path: vec![], - network_update: Some(NetworkUpdate::ChannelClosed { - short_channel_id, - is_permanent: true, - }), - short_channel_id: None, - retry: None, - error_code: None, - error_data: None, - }); + // In std mode, a further check is performed before fully removing the channel - + // the channel_announcement must have been received at least two weeks ago. We + // fudge that here by indicating the time has jumped two weeks. Note that the + // directional channel information will have been removed already.. + assert_eq!(network_graph.read_only().channels().len(), 1); + assert_eq!(network_graph.read_only().nodes().len(), 2); + assert!(network_graph.read_only().channels().get(&short_channel_id).unwrap().one_to_two.is_none()); - assert_eq!(network_graph.read_only().channels().len(), 0); - // Nodes are also deleted because there are no associated channels anymore - assert_eq!(network_graph.read_only().nodes().len(), 0); + use std::time::{SystemTime, UNIX_EPOCH}; + let announcement_time = SystemTime::now().duration_since(UNIX_EPOCH).expect("Time must be > 1970").as_secs(); + network_graph.remove_stale_channels_with_time(announcement_time + 1 + STALE_CHANNEL_UPDATE_AGE_LIMIT_SECS); } - // TODO: Test NetworkUpdate::NodeFailure, which is not implemented yet. + + assert_eq!(network_graph.read_only().channels().len(), 0); + assert_eq!(network_graph.read_only().nodes().len(), 0); } #[test]