X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Frouter.rs;h=46fe93e779962f4be80a1873a4884228921f6a72;hb=f61676ea15915c3b682b930d2b2e34cb74aaa554;hp=dc51b58ee01df5fbe808a9180d188e5447ede9ff;hpb=4c754372628ed155f4babf9f443e05f13481b0f7;p=rust-lightning diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index dc51b58e..46fe93e7 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -21,9 +21,11 @@ use routing::network_graph::{NetworkGraph, RoutingFees}; use util::ser::{Writeable, Readable}; use util::logger::Logger; -use std::cmp; -use std::collections::{HashMap, BinaryHeap}; -use std::ops::Deref; +use prelude::*; +use alloc::collections::BinaryHeap; +use core::cmp; +use std::collections::HashMap; +use core::ops::Deref; /// A hop in a route #[derive(Clone, PartialEq)] @@ -95,30 +97,37 @@ pub struct Route { pub paths: Vec>, } +const SERIALIZATION_VERSION: u8 = 1; +const MIN_SERIALIZATION_VERSION: u8 = 1; + impl Writeable for Route { fn write(&self, writer: &mut W) -> Result<(), ::std::io::Error> { + write_ver_prefix!(writer, SERIALIZATION_VERSION, MIN_SERIALIZATION_VERSION); (self.paths.len() as u64).write(writer)?; for hops in self.paths.iter() { hops.write(writer)?; } + write_tlv_fields!(writer, {}, {}); Ok(()) } } impl Readable for Route { fn read(reader: &mut R) -> Result { + 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); for _ in 0..path_count { paths.push(Readable::read(reader)?); } + read_tlv_fields!(reader, {}, {}); Ok(Route { paths }) } } /// A channel descriptor which provides a last-hop route to get_route -#[derive(Clone)] -pub struct RouteHint { +#[derive(Eq, PartialEq, Debug, Clone)] +pub struct RouteHintHop { /// The node_id of the non-target end of the route pub src_node_id: PublicKey, /// The short_channel_id of this channel @@ -176,7 +185,7 @@ struct DummyDirectionalChannelInfo { /// These fee values are useful to choose hops as we traverse the graph "payee-to-payer". #[derive(Clone)] struct PathBuildingHop<'a> { - // The RouteHint fields which will eventually be used if this hop is used in a final Route. + // The RouteHintHop fields which will eventually be used if this hop is used in a final Route. // Note that node_features is calculated separately after our initial graph walk. pubkey: PublicKey, short_channel_id: u64, @@ -249,14 +258,12 @@ impl<'a> PaymentPath<'a> { // If the amount transferred by the path is updated, the fees should be adjusted. Any other way // to change fees may result in an inconsistency. // - // Sometimes we call this function right after constructing a path which has inconsistent - // (in terms of reaching htlc_minimum_msat), so that this function puts the fees in order. - // In that case we call it on the "same" amount we initially allocated for this path, and which - // could have been reduced on the way. In that case, there is also a risk of exceeding - // available_liquidity inside this function, because the function is unaware of this bound. - // In our specific recomputation cases where we never increase the value the risk is pretty low. - // This function, however, does not support arbitrarily increasing the value being transferred, - // and the exception will be triggered. + // Sometimes we call this function right after constructing a path which is inconsistent in + // that it the value being transferred has decreased while we were doing path finding, leading + // to the fees being paid not lining up with the actual limits. + // + // Note that this function is not aware of the available_liquidity limit, and thus does not + // support increasing the value being transferred. fn update_value_and_recompute_fees(&mut self, value_msat: u64) { assert!(value_msat <= self.hops.last().unwrap().0.fee_msat); @@ -355,7 +362,7 @@ fn compute_fees(amount_msat: u64, channel_fees: RoutingFees) -> Option { /// equal), however the enabled/disabled bit on such channels as well as the /// htlc_minimum_msat/htlc_maximum_msat *are* checked as they may change based on the receiving node. pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, payee: &PublicKey, payee_features: Option, first_hops: Option<&[&ChannelDetails]>, - last_hops: &[&RouteHint], final_value_msat: u64, final_cltv: u32, logger: L) -> Result where L::Target: Logger { + last_hops: &[&RouteHintHop], final_value_msat: u64, final_cltv: u32, logger: L) -> Result where L::Target: Logger { // TODO: Obviously *only* using total fee cost sucks. We should consider weighting by // uptime/success in using a node in the past. if *payee == *our_node_id { @@ -478,7 +485,13 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye let empty_channel_features = ChannelFeatures::empty(); - let mut targets = BinaryHeap::new(); //TODO: Do we care about switching to eg Fibbonaci heap? + // The main heap containing all candidate next-hops sorted by their score (max(A* fee, + // htlc_minimum)). Ideally this would be a heap which allowed cheap score reduction instead of + // adding duplicate entries when we find a better path to a given node. + let mut targets = BinaryHeap::new(); + + // Map from node_id to information about the best current path to that node, including feerate + // information. let mut dist = HashMap::with_capacity(network.get_nodes().len()); // During routing, if we ignore a path due to an htlc_minimum_msat limit, we set this, @@ -979,11 +992,6 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye let mut spent_on_hop_msat = value_contribution_msat; let next_hops_fee_msat = payment_hop.next_hops_fee_msat; spent_on_hop_msat += next_hops_fee_msat; - if *channel_liquidity_available_msat < spent_on_hop_msat { - // This should not happen because we do recompute fees right before, - // trying to avoid cases when a hop is not usable due to the fee situation. - break 'path_construction; - } if spent_on_hop_msat == *channel_liquidity_available_msat { // If this path used all of this channel's available liquidity, we know // this path will not be selected again in the next loop iteration. @@ -1164,8 +1172,9 @@ pub fn get_route(our_node_id: &PublicKey, network: &NetworkGraph, paye #[cfg(test)] mod tests { - use routing::router::{get_route, RouteHint, RoutingFees}; + use routing::router::{get_route, RouteHintHop, RoutingFees}; use routing::network_graph::{NetworkGraph, NetGraphMsgHandler}; + use chain::transaction::OutPoint; use ln::features::{ChannelFeatures, InitFeatures, InvoiceFeatures, NodeFeatures}; use ln::msgs::{ErrorAction, LightningError, OptionalField, UnsignedChannelAnnouncement, ChannelAnnouncement, RoutingMessageHandler, NodeAnnouncement, UnsignedNodeAnnouncement, ChannelUpdate, UnsignedChannelUpdate}; @@ -1186,6 +1195,7 @@ mod tests { use bitcoin::secp256k1::key::{PublicKey,SecretKey}; use bitcoin::secp256k1::{Secp256k1, All}; + use prelude::*; use std::sync::Arc; // Using the same keys for LN and BTC ids @@ -1626,6 +1636,7 @@ mod tests { 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]), @@ -1633,7 +1644,8 @@ mod tests { user_id: 0, outbound_capacity_msat: 100000, inbound_capacity_msat: 100000, - is_live: true, + is_outbound: true, is_funding_locked: true, + is_usable: true, is_public: true, counterparty_forwarding_info: None, }]; @@ -1944,6 +1956,7 @@ mod tests { // 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]), @@ -1951,7 +1964,8 @@ mod tests { user_id: 0, outbound_capacity_msat: 250_000_000, inbound_capacity_msat: 0, - is_live: true, + is_outbound: true, is_funding_locked: true, + is_usable: true, is_public: true, counterparty_forwarding_info: None, }]; let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap(); @@ -1992,6 +2006,7 @@ mod tests { // 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]), @@ -1999,7 +2014,8 @@ mod tests { user_id: 0, outbound_capacity_msat: 250_000_000, inbound_capacity_msat: 0, - is_live: true, + is_outbound: true, is_funding_locked: true, + is_usable: true, is_public: true, counterparty_forwarding_info: None, }]; let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap(); @@ -2057,6 +2073,7 @@ mod tests { // 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]), @@ -2064,7 +2081,8 @@ mod tests { user_id: 0, outbound_capacity_msat: 250_000_000, inbound_capacity_msat: 0, - is_live: true, + is_outbound: true, is_funding_locked: true, + is_usable: true, is_public: true, counterparty_forwarding_info: None, }]; let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, Some(&our_chans.iter().collect::>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap(); @@ -2085,19 +2103,19 @@ mod tests { assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(13)); } - fn last_hops(nodes: &Vec) -> Vec { + fn last_hops(nodes: &Vec) -> Vec { 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 { + }, RouteHintHop { src_node_id: nodes[4].clone(), short_channel_id: 9, fees: RoutingFees { @@ -2107,7 +2125,7 @@ mod tests { cltv_expiry_delta: (9 << 8) | 1, htlc_minimum_msat: None, htlc_maximum_msat: None, - }, RouteHint { + }, RouteHintHop { src_node_id: nodes[5].clone(), short_channel_id: 10, fees: zero_fees, @@ -2125,7 +2143,7 @@ mod tests { // Simple test across 2, 3, 5, and 4 via a last_hop channel // First check that lst hop can't have its source as the payee. - let invalid_last_hop = RouteHint { + let invalid_last_hop = RouteHintHop { src_node_id: nodes[6], short_channel_id: 8, fees: RoutingFees { @@ -2194,6 +2212,7 @@ mod tests { // 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]), @@ -2201,7 +2220,8 @@ mod tests { user_id: 0, outbound_capacity_msat: 250_000_000, inbound_capacity_msat: 0, - is_live: true, + is_outbound: true, is_funding_locked: true, + is_usable: true, is_public: true, counterparty_forwarding_info: None, }]; let mut last_hops = last_hops(&nodes); @@ -2310,7 +2330,7 @@ mod tests { let target_node_id = PublicKey::from_secret_key(&Secp256k1::new(), &SecretKey::from_slice(&hex::decode(format!("{:02}", 43).repeat(32)).unwrap()[..]).unwrap()); // If we specify a channel to a middle hop, that overrides our local channel view and that gets used - let last_hops = vec![RouteHint { + let last_hops = vec![RouteHintHop { src_node_id: middle_node_id, short_channel_id: 8, fees: RoutingFees { @@ -2323,6 +2343,7 @@ mod tests { }]; 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]), @@ -2330,7 +2351,8 @@ mod tests { user_id: 0, outbound_capacity_msat: 100000, inbound_capacity_msat: 100000, - is_live: true, + 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::>()), &last_hops.iter().collect::>(), 100, 42, Arc::new(test_utils::TestLogger::new())).unwrap(); @@ -2455,6 +2477,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]), @@ -2462,7 +2485,8 @@ mod tests { user_id: 0, outbound_capacity_msat: 200_000_000, inbound_capacity_msat: 0, - is_live: true, + is_outbound: true, is_funding_locked: true, + is_usable: true, is_public: true, counterparty_forwarding_info: None, }]; @@ -3836,8 +3860,8 @@ mod tests { use util::ser::Readable; /// Tries to open a network graph file, or panics with a URL to fetch it. pub(super) fn get_route_file() -> Result { - let res = File::open("net_graph-2021-02-12.bin") // By default we're run in RL/lightning - .or_else(|_| File::open("lightning/net_graph-2021-02-12.bin")) // We may be run manually in RL/ + let res = File::open("net_graph-2021-05-27.bin") // By default we're run in RL/lightning + .or_else(|_| File::open("lightning/net_graph-2021-05-27.bin")) // We may be run manually in RL/ .or_else(|_| { // Fall back to guessing based on the binary location // path is likely something like .../rust-lightning/target/debug/deps/lightning-... let mut path = std::env::current_exe().unwrap(); @@ -3846,18 +3870,19 @@ mod tests { path.pop(); // debug path.pop(); // target path.push("lightning"); - path.push("net_graph-2021-02-12.bin"); + path.push("net_graph-2021-05-27.bin"); eprintln!("{}", path.to_str().unwrap()); File::open(path) }); #[cfg(require_route_graph_test)] return Ok(res.expect("Didn't have route graph and was configured to require it")); - res + #[cfg(not(require_route_graph_test))] + return res; } 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 std::hash::{BuildHasher, Hasher}; + use core::hash::{BuildHasher, Hasher}; let seed = std::collections::hash_map::RandomState::new().build_hasher().finish(); println!("Using seed of {}", seed); seed @@ -3868,7 +3893,7 @@ mod tests { let mut d = match get_route_file() { Ok(f) => f, Err(_) => { - eprintln!("Please fetch https://bitcoin.ninja/ldk-net_graph-879e309c128-2020-02-12.bin and place it at lightning/net_graph-2021-02-12.bin"); + eprintln!("Please fetch https://bitcoin.ninja/ldk-net_graph-45d86ead641d-2021-05-27.bin and place it at lightning/net_graph-2021-05-27.bin"); return; }, }; @@ -3895,7 +3920,7 @@ mod tests { let mut d = match get_route_file() { Ok(f) => f, Err(_) => { - eprintln!("Please fetch https://bitcoin.ninja/ldk-net_graph-879e309c128-2020-02-12.bin and place it at lightning/net_graph-2021-02-12.bin"); + eprintln!("Please fetch https://bitcoin.ninja/ldk-net_graph-45d86ead641d-2021-05-27.bin and place it at lightning/net_graph-2021-05-27.bin"); return; }, }; @@ -3923,7 +3948,7 @@ mod benches { use super::*; use util::logger::{Logger, Record}; - use std::fs::File; + use prelude::*; use test::Bencher; struct DummyLogger {} @@ -3934,7 +3959,7 @@ mod benches { #[bench] fn generate_routes(bench: &mut Bencher) { let mut d = tests::get_route_file() - .expect("Please fetch https://bitcoin.ninja/ldk-net_graph-879e309c128-2020-02-12.bin and place it at lightning/net_graph-2021-02-12.bin"); + .expect("Please fetch https://bitcoin.ninja/ldk-net_graph-45d86ead641d-2021-05-27.bin and place it at lightning/net_graph-2021-05-27.bin"); let graph = NetworkGraph::read(&mut d).unwrap(); // First, get 100 (source, destination) pairs for which route-getting actually succeeds... @@ -3966,7 +3991,7 @@ mod benches { #[bench] fn generate_mpp_routes(bench: &mut Bencher) { let mut d = tests::get_route_file() - .expect("Please fetch https://bitcoin.ninja/ldk-net_graph-879e309c128-2020-02-12.bin and place it at lightning/net_graph-2021-02-12.bin"); + .expect("Please fetch https://bitcoin.ninja/ldk-net_graph-45d86ead641d-2021-05-27.bin and place it at lightning/net_graph-2021-05-27.bin"); let graph = NetworkGraph::read(&mut d).unwrap(); // First, get 100 (source, destination) pairs for which route-getting actually succeeds...