1 use secp256k1::key::PublicKey;
2 use secp256k1::{Secp256k1,Message};
4 use bitcoin::util::hash::Sha256dHash;
6 use ln::msgs::{HandleError,RoutingMessageHandler,MsgEncodable,NetAddress,GlobalFeatures};
10 use std::sync::RwLock;
11 use std::collections::{HashMap,BinaryHeap};
12 use std::collections::hash_map::Entry;
17 pub pubkey: PublicKey,
18 /// The channel that should be used from the previous hop to reach this node.
19 pub short_channel_id: u64,
20 /// The fee taken on this hop. For the last hop, this should be the full value of the payment.
22 /// The CLTV delta added for this hop. For the last hop, this should be the full CLTV value
23 /// expected at the destination, NOT a delta.
24 pub cltv_expiry_delta: u32,
27 /// A route from us through the network to a destination
30 /// The list of hops, NOT INCLUDING our own, where the last hop is the destination. Thus, this
31 /// must always be at least length one. By protocol rules, this may not currently exceed 20 in
33 pub hops: Vec<RouteHop>,
36 struct DirectionalChannelInfo {
37 src_node_id: PublicKey,
40 cltv_expiry_delta: u16,
41 htlc_minimum_msat: u64,
43 fee_proportional_millionths: u32,
47 features: GlobalFeatures,
48 one_to_two: DirectionalChannelInfo,
49 two_to_one: DirectionalChannelInfo,
53 #[cfg(feature = "non_bitcoin_chain_hash_routing")]
54 channels: Vec<(u64, Sha256dHash)>,
55 #[cfg(not(feature = "non_bitcoin_chain_hash_routing"))]
58 lowest_inbound_channel_fee_base_msat: u32,
59 lowest_inbound_channel_fee_proportional_millionths: u32,
61 features: GlobalFeatures,
65 addresses: Vec<NetAddress>,
69 #[cfg(feature = "non_bitcoin_chain_hash_routing")]
70 channels: HashMap<(u64, Sha256dHash), ChannelInfo>,
71 #[cfg(not(feature = "non_bitcoin_chain_hash_routing"))]
72 channels: HashMap<u64, ChannelInfo>,
74 our_node_id: PublicKey,
75 nodes: HashMap<PublicKey, NodeInfo>,
79 #[cfg(feature = "non_bitcoin_chain_hash_routing")]
81 fn get_key(short_channel_id: u64, chain_hash: Sha256dHash) -> (u64, Sha256dHash) {
82 (short_channel_id, chain_hash)
85 #[cfg(not(feature = "non_bitcoin_chain_hash_routing"))]
87 fn get_key(short_channel_id: u64, _: Sha256dHash) -> u64 {
92 /// A channel descriptor which provides a last-hop route to get_route
93 pub struct RouteHint {
94 pub src_node_id: PublicKey,
95 pub short_channel_id: u64,
96 pub fee_base_msat: u64,
97 pub fee_proportional_millionths: u32,
98 pub cltv_expiry_delta: u16,
99 pub htlc_minimum_msat: u64,
102 /// Tracks a view of the network, receiving updates from peers and generating Routes to
103 /// payment destinations.
106 network_map: RwLock<NetworkMap>,
109 macro_rules! secp_verify_sig {
110 ( $secp_ctx: expr, $msg: expr, $sig: expr, $pubkey: expr ) => {
111 match $secp_ctx.verify($msg, $sig, $pubkey) {
113 Err(_) => return Err(HandleError{err: "Invalid signature from remote node", msg: None}),
118 impl RoutingMessageHandler for Router {
119 fn handle_node_announcement(&self, msg: &msgs::NodeAnnouncement) -> Result<(), HandleError> {
120 let msg_hash = Message::from_slice(&Sha256dHash::from_data(&msg.contents.encode()[..])[..]).unwrap();
121 secp_verify_sig!(self.secp_ctx, &msg_hash, &msg.signature, &msg.contents.node_id);
123 let mut network = self.network_map.write().unwrap();
124 match network.nodes.get_mut(&msg.contents.node_id) {
125 None => Err(HandleError{err: "No existing channels for node_announcement", msg: None}),
127 if node.last_update >= msg.contents.timestamp {
128 return Err(HandleError{err: "Update older than last processed update", msg: None});
131 node.features = msg.contents.features.clone();
132 node.last_update = msg.contents.timestamp;
133 node.rgb = msg.contents.rgb;
134 node.alias = msg.contents.alias;
135 node.addresses = msg.contents.addresses.clone();
141 fn handle_channel_announcement(&self, msg: &msgs::ChannelAnnouncement) -> Result<bool, HandleError> {
142 let msg_hash = Message::from_slice(&Sha256dHash::from_data(&msg.contents.encode()[..])[..]).unwrap();
143 secp_verify_sig!(self.secp_ctx, &msg_hash, &msg.node_signature_1, &msg.contents.node_id_1);
144 secp_verify_sig!(self.secp_ctx, &msg_hash, &msg.node_signature_2, &msg.contents.node_id_2);
145 secp_verify_sig!(self.secp_ctx, &msg_hash, &msg.bitcoin_signature_1, &msg.contents.bitcoin_key_1);
146 secp_verify_sig!(self.secp_ctx, &msg_hash, &msg.bitcoin_signature_2, &msg.contents.bitcoin_key_2);
148 //TODO: Call blockchain thing to ask if the short_channel_id is valid
149 //TODO: Only allow bitcoin chain_hash
151 if msg.contents.features.requires_unknown_bits() {
152 return Err(HandleError{err: "Channel announcement required unknown feature flags", msg: None});
155 let mut network = self.network_map.write().unwrap();
157 match network.channels.entry(NetworkMap::get_key(msg.contents.short_channel_id, msg.contents.chain_hash)) {
158 Entry::Occupied(_) => {
159 //TODO: because asking the blockchain if short_channel_id is valid is only optional
160 //in the blockchain API, we need to handle it smartly here, though its unclear
162 return Err(HandleError{err: "Already have knowledge of channel", msg: None})
164 Entry::Vacant(entry) => {
165 entry.insert(ChannelInfo {
166 features: msg.contents.features.clone(),
167 one_to_two: DirectionalChannelInfo {
168 src_node_id: msg.contents.node_id_1.clone(),
171 cltv_expiry_delta: u16::max_value(),
172 htlc_minimum_msat: u64::max_value(),
173 fee_base_msat: u32::max_value(),
174 fee_proportional_millionths: u32::max_value(),
176 two_to_one: DirectionalChannelInfo {
177 src_node_id: msg.contents.node_id_2.clone(),
180 cltv_expiry_delta: u16::max_value(),
181 htlc_minimum_msat: u64::max_value(),
182 fee_base_msat: u32::max_value(),
183 fee_proportional_millionths: u32::max_value(),
189 macro_rules! add_channel_to_node {
190 ( $node_id: expr ) => {
191 match network.nodes.entry($node_id) {
192 Entry::Occupied(node_entry) => {
193 node_entry.into_mut().channels.push(NetworkMap::get_key(msg.contents.short_channel_id, msg.contents.chain_hash));
195 Entry::Vacant(node_entry) => {
196 node_entry.insert(NodeInfo {
197 channels: vec!(NetworkMap::get_key(msg.contents.short_channel_id, msg.contents.chain_hash)),
198 lowest_inbound_channel_fee_base_msat: u32::max_value(),
199 lowest_inbound_channel_fee_proportional_millionths: u32::max_value(),
200 features: GlobalFeatures::new(),
204 addresses: Vec::new(),
211 add_channel_to_node!(msg.contents.node_id_1);
212 add_channel_to_node!(msg.contents.node_id_2);
214 Ok(!msg.contents.features.supports_unknown_bits())
217 fn handle_htlc_fail_channel_update(&self, update: &msgs::HTLCFailChannelUpdate) {
219 &msgs::HTLCFailChannelUpdate::ChannelUpdateMessage { ref msg } => {
220 let _ = self.handle_channel_update(msg);
222 &msgs::HTLCFailChannelUpdate::ChannelClosed { ref short_channel_id } => {
223 let mut network = self.network_map.write().unwrap();
224 network.channels.remove(short_channel_id);
229 fn handle_channel_update(&self, msg: &msgs::ChannelUpdate) -> Result<(), HandleError> {
230 let mut network = self.network_map.write().unwrap();
232 let chan_enabled = msg.contents.flags & (1 << 1) != (1 << 1);
233 let chan_was_enabled;
235 match network.channels.get_mut(&NetworkMap::get_key(msg.contents.short_channel_id, msg.contents.chain_hash)) {
236 None => return Err(HandleError{err: "Couldn't find channel for update", msg: None}),
238 macro_rules! maybe_update_channel_info {
239 ( $target: expr) => {
240 if $target.last_update >= msg.contents.timestamp {
241 return Err(HandleError{err: "Update older than last processed update", msg: None});
243 chan_was_enabled = $target.enabled;
244 $target.last_update = msg.contents.timestamp;
245 $target.enabled = chan_enabled;
246 $target.cltv_expiry_delta = msg.contents.cltv_expiry_delta;
247 $target.htlc_minimum_msat = msg.contents.htlc_minimum_msat;
248 $target.fee_base_msat = msg.contents.fee_base_msat;
249 $target.fee_proportional_millionths = msg.contents.fee_proportional_millionths;
253 let msg_hash = Message::from_slice(&Sha256dHash::from_data(&msg.contents.encode()[..])[..]).unwrap();
254 if msg.contents.flags & 1 == 1 {
255 dest_node_id = channel.one_to_two.src_node_id.clone();
256 secp_verify_sig!(self.secp_ctx, &msg_hash, &msg.signature, &channel.two_to_one.src_node_id);
257 maybe_update_channel_info!(channel.two_to_one);
259 dest_node_id = channel.two_to_one.src_node_id.clone();
260 secp_verify_sig!(self.secp_ctx, &msg_hash, &msg.signature, &channel.one_to_two.src_node_id);
261 maybe_update_channel_info!(channel.one_to_two);
267 let node = network.nodes.get_mut(&dest_node_id).unwrap();
268 node.lowest_inbound_channel_fee_base_msat = cmp::min(node.lowest_inbound_channel_fee_base_msat, msg.contents.fee_base_msat);
269 node.lowest_inbound_channel_fee_proportional_millionths = cmp::min(node.lowest_inbound_channel_fee_proportional_millionths, msg.contents.fee_proportional_millionths);
270 } else if chan_was_enabled {
271 let mut lowest_inbound_channel_fee_base_msat = u32::max_value();
272 let mut lowest_inbound_channel_fee_proportional_millionths = u32::max_value();
275 let node = network.nodes.get(&dest_node_id).unwrap();
277 for chan_id in node.channels.iter() {
278 let chan = network.channels.get(chan_id).unwrap();
279 if chan.one_to_two.src_node_id == dest_node_id {
280 lowest_inbound_channel_fee_base_msat = cmp::min(lowest_inbound_channel_fee_base_msat, chan.two_to_one.fee_base_msat);
281 lowest_inbound_channel_fee_proportional_millionths = cmp::min(lowest_inbound_channel_fee_proportional_millionths, chan.two_to_one.fee_proportional_millionths);
283 lowest_inbound_channel_fee_base_msat = cmp::min(lowest_inbound_channel_fee_base_msat, chan.one_to_two.fee_base_msat);
284 lowest_inbound_channel_fee_proportional_millionths = cmp::min(lowest_inbound_channel_fee_proportional_millionths, chan.one_to_two.fee_proportional_millionths);
289 //TODO: satisfy the borrow-checker without a double-map-lookup :(
290 let mut_node = network.nodes.get_mut(&dest_node_id).unwrap();
291 mut_node.lowest_inbound_channel_fee_base_msat = lowest_inbound_channel_fee_base_msat;
292 mut_node.lowest_inbound_channel_fee_proportional_millionths = lowest_inbound_channel_fee_proportional_millionths;
299 #[derive(Eq, PartialEq)]
300 struct RouteGraphNode {
302 lowest_fee_to_peer_through_node: u64,
305 impl cmp::Ord for RouteGraphNode {
306 fn cmp(&self, other: &RouteGraphNode) -> cmp::Ordering {
307 other.lowest_fee_to_peer_through_node.cmp(&self.lowest_fee_to_peer_through_node)
308 .then_with(|| other.pubkey.serialize().cmp(&self.pubkey.serialize()))
312 impl cmp::PartialOrd for RouteGraphNode {
313 fn partial_cmp(&self, other: &RouteGraphNode) -> Option<cmp::Ordering> {
314 Some(self.cmp(other))
319 pub fn new(our_pubkey: PublicKey) -> Router {
320 let mut nodes = HashMap::new();
321 nodes.insert(our_pubkey.clone(), NodeInfo {
322 channels: Vec::new(),
323 lowest_inbound_channel_fee_base_msat: u32::max_value(),
324 lowest_inbound_channel_fee_proportional_millionths: u32::max_value(),
325 features: GlobalFeatures::new(),
329 addresses: Vec::new(),
332 secp_ctx: Secp256k1::new(),
333 network_map: RwLock::new(NetworkMap {
334 channels: HashMap::new(),
335 our_node_id: our_pubkey,
341 /// Marks a node as having failed a route. This will avoid re-using the node in routes for now,
342 /// with an expotnential decay in node "badness". Note that there is deliberately no
343 /// mark_channel_bad as a node may simply lie and suggest that an upstream channel from it is
344 /// what failed the route and not the node itself. Instead, setting the blamed_upstream_node
345 /// boolean will reduce the penalty, returning the node to usability faster. If the node is
346 /// behaving correctly, it will disable the failing channel and we will use it again next time.
347 pub fn mark_node_bad(&self, _node_id: &PublicKey, _blamed_upstream_node: bool) {
351 /// Gets a route from us to the given target node.
352 /// Extra routing hops between known nodes and the target will be used if they are included in
354 /// The fees on channels from us to next-hops are ignored (as they are assumed to all be
355 /// equal), however the enabled/disabled bit on such channels as well as the htlc_minimum_msat
356 /// *is* checked as they may change based on the receiving node.
357 pub fn get_route(&self, target: &PublicKey, last_hops: &Vec<RouteHint>, final_value_msat: u64, final_cltv: u32) -> Result<Route, HandleError> {
358 // TODO: Obviously *only* using total fee cost sucks. We should consider weighting by
359 // uptime/success in using a node in the past.
360 let network = self.network_map.read().unwrap();
362 if *target == network.our_node_id {
363 return Err(HandleError{err: "Cannot generate a route to ourselves", msg: None});
366 // We do a dest-to-source Dijkstra's sorting by each node's distance from the destination
367 // plus the minimum per-HTLC fee to get from it to another node (aka "shitty A*").
368 // TODO: There are a few tweaks we could do, including possibly pre-calculating more stuff
369 // to use as the A* heuristic beyond just the cost to get one node further than the current
372 let mut targets = BinaryHeap::new(); //TODO: Do we care about switching to eg Fibbonaci heap?
373 let mut dist = HashMap::with_capacity(network.nodes.len());
374 for (key, node) in network.nodes.iter() {
375 dist.insert(key.clone(), (u64::max_value(),
376 node.lowest_inbound_channel_fee_base_msat as u64,
377 node.lowest_inbound_channel_fee_proportional_millionths as u64,
379 pubkey: PublicKey::new(),
382 cltv_expiry_delta: 0,
386 macro_rules! add_entry {
387 // Adds entry which goes from the node pointed to by $directional_info to
388 // $dest_node_id over the channel with id $chan_id with fees described in
389 // $directional_info.
390 ( $chan_id: expr, $dest_node_id: expr, $directional_info: expr, $starting_fee_msat: expr ) => {
391 //TODO: Explore simply adding fee to hit htlc_minimum_msat
392 if $starting_fee_msat as u64 + final_value_msat > $directional_info.htlc_minimum_msat {
393 let new_fee = $directional_info.fee_base_msat as u64 + ($starting_fee_msat + final_value_msat) * ($directional_info.fee_proportional_millionths as u64) / 1000000;
394 let mut total_fee = $starting_fee_msat as u64;
395 let old_entry = dist.get_mut(&$directional_info.src_node_id).unwrap();
396 if $directional_info.src_node_id != network.our_node_id {
397 // Ignore new_fee for channel-from-us as we assume all channels-from-us
398 // will have the same effective-fee
399 total_fee += new_fee;
400 total_fee += old_entry.2 * (final_value_msat + total_fee) / 1000000 + old_entry.1;
402 let new_graph_node = RouteGraphNode {
403 pubkey: $directional_info.src_node_id,
404 lowest_fee_to_peer_through_node: total_fee,
406 if old_entry.0 > total_fee {
407 targets.push(new_graph_node);
408 old_entry.0 = total_fee;
409 old_entry.3 = RouteHop {
410 pubkey: $dest_node_id.clone(),
411 short_channel_id: $chan_id.clone(),
412 fee_msat: new_fee, // This field is ignored on the last-hop anyway
413 cltv_expiry_delta: $directional_info.cltv_expiry_delta as u32,
420 macro_rules! add_entries_to_cheapest_to_target_node {
421 ( $node: expr, $node_id: expr, $fee_to_target_msat: expr ) => {
422 for chan_id in $node.channels.iter() {
423 let chan = network.channels.get(chan_id).unwrap();
424 if chan.one_to_two.src_node_id == *$node_id {
425 // ie $node is one, ie next hop in A* is two, via the two_to_one channel
426 if chan.two_to_one.enabled {
427 add_entry!(chan_id, chan.one_to_two.src_node_id, chan.two_to_one, $fee_to_target_msat);
430 if chan.one_to_two.enabled {
431 add_entry!(chan_id, chan.two_to_one.src_node_id, chan.one_to_two, $fee_to_target_msat);
438 match network.nodes.get(target) {
441 add_entries_to_cheapest_to_target_node!(node, target, 0);
445 for hop in last_hops.iter() {
446 if network.nodes.get(&hop.src_node_id).is_some() {
447 add_entry!(hop.short_channel_id, target, hop, 0);
451 while let Some(RouteGraphNode { pubkey, lowest_fee_to_peer_through_node }) = targets.pop() {
452 if pubkey == network.our_node_id {
453 let mut res = vec!(dist.remove(&network.our_node_id).unwrap().3);
454 while res.last().unwrap().pubkey != *target {
455 let new_entry = dist.remove(&res.last().unwrap().pubkey).unwrap().3;
456 res.last_mut().unwrap().fee_msat = new_entry.fee_msat;
457 res.last_mut().unwrap().cltv_expiry_delta = new_entry.cltv_expiry_delta;
460 res.last_mut().unwrap().fee_msat = final_value_msat;
461 res.last_mut().unwrap().cltv_expiry_delta = final_cltv;
467 match network.nodes.get(&pubkey) {
470 let mut fee = lowest_fee_to_peer_through_node - node.lowest_inbound_channel_fee_base_msat as u64;
471 fee -= node.lowest_inbound_channel_fee_proportional_millionths as u64 * (fee + final_value_msat) / 1000000;
472 add_entries_to_cheapest_to_target_node!(node, &pubkey, fee);
477 Err(HandleError{err: "Failed to find a path to the given destination", msg: None})
483 use ln::router::{Router,NodeInfo,NetworkMap,ChannelInfo,DirectionalChannelInfo,RouteHint};
484 use ln::msgs::GlobalFeatures;
486 use bitcoin::util::misc::hex_bytes;
487 use bitcoin::util::hash::Sha256dHash;
489 use secp256k1::key::{PublicKey,SecretKey};
490 use secp256k1::Secp256k1;
494 let secp_ctx = Secp256k1::new();
495 let our_id = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex_bytes("0101010101010101010101010101010101010101010101010101010101010101").unwrap()[..]).unwrap()).unwrap();
496 let router = Router::new(our_id);
498 // Build network from our_id to node8:
500 // -1(1)2- node1 -1(3)2-
504 // -1(2)2- node2 -1(4)2-
507 // chan1 1-to-2: disabled
508 // chan1 2-to-1: enabled, 0 fee
510 // chan2 1-to-2: enabled, ignored fee
511 // chan2 2-to-1: enabled, 0 fee
513 // chan3 1-to-2: enabled, 0 fee
514 // chan3 2-to-1: enabled, 100 msat fee
516 // chan4 1-to-2: enabled, 100% fee
517 // chan4 2-to-1: enabled, 0 fee
521 // -1(5)2- node4 -1(8)2--
525 // node3--1(6)2- node5 -1(9)2--- node7 (not in global route map)
527 // -1(7)2- node6 -1(10)2-
529 // chan5 1-to-2: enabled, 100 msat fee
530 // chan5 2-to-1: enabled, 0 fee
532 // chan6 1-to-2: enabled, 0 fee
533 // chan6 2-to-1: enabled, 0 fee
535 // chan7 1-to-2: enabled, 100% fee
536 // chan7 2-to-1: enabled, 0 fee
538 // chan8 1-to-2: enabled, variable fee (0 then 1000 msat)
539 // chan8 2-to-1: enabled, 0 fee
541 // chan9 1-to-2: enabled, 1001 msat fee
542 // chan9 2-to-1: enabled, 0 fee
544 // chan10 1-to-2: enabled, 0 fee
545 // chan10 2-to-1: enabled, 0 fee
547 // chan11 1-to-2: enabled, 0 fee
548 // chan11 2-to-1: enabled, 0 fee
550 let node1 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex_bytes("0202020202020202020202020202020202020202020202020202020202020202").unwrap()[..]).unwrap()).unwrap();
551 let node2 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex_bytes("0303030303030303030303030303030303030303030303030303030303030303").unwrap()[..]).unwrap()).unwrap();
552 let node3 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex_bytes("0404040404040404040404040404040404040404040404040404040404040404").unwrap()[..]).unwrap()).unwrap();
553 let node4 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex_bytes("0505050505050505050505050505050505050505050505050505050505050505").unwrap()[..]).unwrap()).unwrap();
554 let node5 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex_bytes("0606060606060606060606060606060606060606060606060606060606060606").unwrap()[..]).unwrap()).unwrap();
555 let node6 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex_bytes("0707070707070707070707070707070707070707070707070707070707070707").unwrap()[..]).unwrap()).unwrap();
556 let node7 = PublicKey::from_secret_key(&secp_ctx, &SecretKey::from_slice(&secp_ctx, &hex_bytes("0808080808080808080808080808080808080808080808080808080808080808").unwrap()[..]).unwrap()).unwrap();
558 let zero_hash = Sha256dHash::from_data(&[0; 32]);
561 let mut network = router.network_map.write().unwrap();
563 network.nodes.insert(node1.clone(), NodeInfo {
564 channels: vec!(NetworkMap::get_key(1, zero_hash.clone()), NetworkMap::get_key(3, zero_hash.clone())),
565 lowest_inbound_channel_fee_base_msat: 100,
566 lowest_inbound_channel_fee_proportional_millionths: 0,
567 features: GlobalFeatures::new(),
571 addresses: Vec::new(),
573 network.channels.insert(NetworkMap::get_key(1, zero_hash.clone()), ChannelInfo {
574 features: GlobalFeatures::new(),
575 one_to_two: DirectionalChannelInfo {
576 src_node_id: our_id.clone(),
579 cltv_expiry_delta: u16::max_value(), // This value should be ignored
580 htlc_minimum_msat: 0,
581 fee_base_msat: u32::max_value(), // This value should be ignored
582 fee_proportional_millionths: u32::max_value(), // This value should be ignored
583 }, two_to_one: DirectionalChannelInfo {
584 src_node_id: node1.clone(),
587 cltv_expiry_delta: 0,
588 htlc_minimum_msat: 0,
590 fee_proportional_millionths: 0,
593 network.nodes.insert(node2.clone(), NodeInfo {
594 channels: vec!(NetworkMap::get_key(2, zero_hash.clone()), NetworkMap::get_key(4, zero_hash.clone())),
595 lowest_inbound_channel_fee_base_msat: 0,
596 lowest_inbound_channel_fee_proportional_millionths: 0,
597 features: GlobalFeatures::new(),
601 addresses: Vec::new(),
603 network.channels.insert(NetworkMap::get_key(2, zero_hash.clone()), ChannelInfo {
604 features: GlobalFeatures::new(),
605 one_to_two: DirectionalChannelInfo {
606 src_node_id: our_id.clone(),
609 cltv_expiry_delta: u16::max_value(), // This value should be ignored
610 htlc_minimum_msat: 0,
611 fee_base_msat: u32::max_value(), // This value should be ignored
612 fee_proportional_millionths: u32::max_value(), // This value should be ignored
613 }, two_to_one: DirectionalChannelInfo {
614 src_node_id: node2.clone(),
617 cltv_expiry_delta: 0,
618 htlc_minimum_msat: 0,
620 fee_proportional_millionths: 0,
623 network.nodes.insert(node3.clone(), NodeInfo {
625 NetworkMap::get_key(3, zero_hash.clone()),
626 NetworkMap::get_key(4, zero_hash.clone()),
627 NetworkMap::get_key(5, zero_hash.clone()),
628 NetworkMap::get_key(6, zero_hash.clone()),
629 NetworkMap::get_key(7, zero_hash.clone())),
630 lowest_inbound_channel_fee_base_msat: 0,
631 lowest_inbound_channel_fee_proportional_millionths: 0,
632 features: GlobalFeatures::new(),
636 addresses: Vec::new(),
638 network.channels.insert(NetworkMap::get_key(3, zero_hash.clone()), ChannelInfo {
639 features: GlobalFeatures::new(),
640 one_to_two: DirectionalChannelInfo {
641 src_node_id: node1.clone(),
644 cltv_expiry_delta: (3 << 8) | 1,
645 htlc_minimum_msat: 0,
647 fee_proportional_millionths: 0,
648 }, two_to_one: DirectionalChannelInfo {
649 src_node_id: node3.clone(),
652 cltv_expiry_delta: (3 << 8) | 2,
653 htlc_minimum_msat: 0,
655 fee_proportional_millionths: 0,
658 network.channels.insert(NetworkMap::get_key(4, zero_hash.clone()), ChannelInfo {
659 features: GlobalFeatures::new(),
660 one_to_two: DirectionalChannelInfo {
661 src_node_id: node2.clone(),
664 cltv_expiry_delta: (4 << 8) | 1,
665 htlc_minimum_msat: 0,
667 fee_proportional_millionths: 1000000,
668 }, two_to_one: DirectionalChannelInfo {
669 src_node_id: node3.clone(),
672 cltv_expiry_delta: (4 << 8) | 2,
673 htlc_minimum_msat: 0,
675 fee_proportional_millionths: 0,
678 network.nodes.insert(node4.clone(), NodeInfo {
679 channels: vec!(NetworkMap::get_key(5, zero_hash.clone()), NetworkMap::get_key(11, zero_hash.clone())),
680 lowest_inbound_channel_fee_base_msat: 0,
681 lowest_inbound_channel_fee_proportional_millionths: 0,
682 features: GlobalFeatures::new(),
686 addresses: Vec::new(),
688 network.channels.insert(NetworkMap::get_key(5, zero_hash.clone()), ChannelInfo {
689 features: GlobalFeatures::new(),
690 one_to_two: DirectionalChannelInfo {
691 src_node_id: node3.clone(),
694 cltv_expiry_delta: (5 << 8) | 1,
695 htlc_minimum_msat: 0,
697 fee_proportional_millionths: 0,
698 }, two_to_one: DirectionalChannelInfo {
699 src_node_id: node4.clone(),
702 cltv_expiry_delta: (5 << 8) | 2,
703 htlc_minimum_msat: 0,
705 fee_proportional_millionths: 0,
708 network.nodes.insert(node5.clone(), NodeInfo {
709 channels: vec!(NetworkMap::get_key(6, zero_hash.clone()), NetworkMap::get_key(11, zero_hash.clone())),
710 lowest_inbound_channel_fee_base_msat: 0,
711 lowest_inbound_channel_fee_proportional_millionths: 0,
712 features: GlobalFeatures::new(),
716 addresses: Vec::new(),
718 network.channels.insert(NetworkMap::get_key(6, zero_hash.clone()), ChannelInfo {
719 features: GlobalFeatures::new(),
720 one_to_two: DirectionalChannelInfo {
721 src_node_id: node3.clone(),
724 cltv_expiry_delta: (6 << 8) | 1,
725 htlc_minimum_msat: 0,
727 fee_proportional_millionths: 0,
728 }, two_to_one: DirectionalChannelInfo {
729 src_node_id: node5.clone(),
732 cltv_expiry_delta: (6 << 8) | 2,
733 htlc_minimum_msat: 0,
735 fee_proportional_millionths: 0,
738 network.channels.insert(NetworkMap::get_key(11, zero_hash.clone()), ChannelInfo {
739 features: GlobalFeatures::new(),
740 one_to_two: DirectionalChannelInfo {
741 src_node_id: node5.clone(),
744 cltv_expiry_delta: (11 << 8) | 1,
745 htlc_minimum_msat: 0,
747 fee_proportional_millionths: 0,
748 }, two_to_one: DirectionalChannelInfo {
749 src_node_id: node4.clone(),
752 cltv_expiry_delta: (11 << 8) | 2,
753 htlc_minimum_msat: 0,
755 fee_proportional_millionths: 0,
758 network.nodes.insert(node6.clone(), NodeInfo {
759 channels: vec!(NetworkMap::get_key(7, zero_hash.clone())),
760 lowest_inbound_channel_fee_base_msat: 0,
761 lowest_inbound_channel_fee_proportional_millionths: 0,
762 features: GlobalFeatures::new(),
766 addresses: Vec::new(),
768 network.channels.insert(NetworkMap::get_key(7, zero_hash.clone()), ChannelInfo {
769 features: GlobalFeatures::new(),
770 one_to_two: DirectionalChannelInfo {
771 src_node_id: node3.clone(),
774 cltv_expiry_delta: (7 << 8) | 1,
775 htlc_minimum_msat: 0,
777 fee_proportional_millionths: 1000000,
778 }, two_to_one: DirectionalChannelInfo {
779 src_node_id: node6.clone(),
782 cltv_expiry_delta: (7 << 8) | 2,
783 htlc_minimum_msat: 0,
785 fee_proportional_millionths: 0,
790 { // Simple route to 3 via 2
791 let route = router.get_route(&node3, &Vec::new(), 100, 42).unwrap();
792 assert_eq!(route.hops.len(), 2);
794 assert_eq!(route.hops[0].pubkey, node2);
795 assert_eq!(route.hops[0].short_channel_id, 2);
796 assert_eq!(route.hops[0].fee_msat, 100);
797 assert_eq!(route.hops[0].cltv_expiry_delta, (4 << 8) | 1);
799 assert_eq!(route.hops[1].pubkey, node3);
800 assert_eq!(route.hops[1].short_channel_id, 4);
801 assert_eq!(route.hops[1].fee_msat, 100);
802 assert_eq!(route.hops[1].cltv_expiry_delta, 42);
805 { // Route to 1 via 2 and 3 because our channel to 1 is disabled
806 let route = router.get_route(&node1, &Vec::new(), 100, 42).unwrap();
807 assert_eq!(route.hops.len(), 3);
809 assert_eq!(route.hops[0].pubkey, node2);
810 assert_eq!(route.hops[0].short_channel_id, 2);
811 assert_eq!(route.hops[0].fee_msat, 200);
812 assert_eq!(route.hops[0].cltv_expiry_delta, (4 << 8) | 1);
814 assert_eq!(route.hops[1].pubkey, node3);
815 assert_eq!(route.hops[1].short_channel_id, 4);
816 assert_eq!(route.hops[1].fee_msat, 100);
817 assert_eq!(route.hops[1].cltv_expiry_delta, (3 << 8) | 2);
819 assert_eq!(route.hops[2].pubkey, node1);
820 assert_eq!(route.hops[2].short_channel_id, 3);
821 assert_eq!(route.hops[2].fee_msat, 100);
822 assert_eq!(route.hops[2].cltv_expiry_delta, 42);
825 let mut last_hops = vec!(RouteHint {
826 src_node_id: node4.clone(),
829 fee_proportional_millionths: 0,
830 cltv_expiry_delta: (8 << 8) | 1,
831 htlc_minimum_msat: 0,
833 src_node_id: node5.clone(),
836 fee_proportional_millionths: 0,
837 cltv_expiry_delta: (9 << 8) | 1,
838 htlc_minimum_msat: 0,
840 src_node_id: node6.clone(),
841 short_channel_id: 10,
843 fee_proportional_millionths: 0,
844 cltv_expiry_delta: (10 << 8) | 1,
845 htlc_minimum_msat: 0,
848 { // Simple test across 2, 3, 5, and 4 via a last_hop channel
849 let route = router.get_route(&node7, &last_hops, 100, 42).unwrap();
850 assert_eq!(route.hops.len(), 5);
852 assert_eq!(route.hops[0].pubkey, node2);
853 assert_eq!(route.hops[0].short_channel_id, 2);
854 assert_eq!(route.hops[0].fee_msat, 100);
855 assert_eq!(route.hops[0].cltv_expiry_delta, (4 << 8) | 1);
857 assert_eq!(route.hops[1].pubkey, node3);
858 assert_eq!(route.hops[1].short_channel_id, 4);
859 assert_eq!(route.hops[1].fee_msat, 0);
860 assert_eq!(route.hops[1].cltv_expiry_delta, (6 << 8) | 1);
862 assert_eq!(route.hops[2].pubkey, node5);
863 assert_eq!(route.hops[2].short_channel_id, 6);
864 assert_eq!(route.hops[2].fee_msat, 0);
865 assert_eq!(route.hops[2].cltv_expiry_delta, (11 << 8) | 1);
867 assert_eq!(route.hops[3].pubkey, node4);
868 assert_eq!(route.hops[3].short_channel_id, 11);
869 assert_eq!(route.hops[3].fee_msat, 0);
870 assert_eq!(route.hops[3].cltv_expiry_delta, (8 << 8) | 1);
872 assert_eq!(route.hops[4].pubkey, node7);
873 assert_eq!(route.hops[4].short_channel_id, 8);
874 assert_eq!(route.hops[4].fee_msat, 100);
875 assert_eq!(route.hops[4].cltv_expiry_delta, 42);
878 last_hops[0].fee_base_msat = 1000;
880 { // Revert to via 6 as the fee on 8 goes up
881 let route = router.get_route(&node7, &last_hops, 100, 42).unwrap();
882 assert_eq!(route.hops.len(), 4);
884 assert_eq!(route.hops[0].pubkey, node2);
885 assert_eq!(route.hops[0].short_channel_id, 2);
886 assert_eq!(route.hops[0].fee_msat, 200); // fee increased as its % of value transferred across node
887 assert_eq!(route.hops[0].cltv_expiry_delta, (4 << 8) | 1);
889 assert_eq!(route.hops[1].pubkey, node3);
890 assert_eq!(route.hops[1].short_channel_id, 4);
891 assert_eq!(route.hops[1].fee_msat, 100);
892 assert_eq!(route.hops[1].cltv_expiry_delta, (7 << 8) | 1);
894 assert_eq!(route.hops[2].pubkey, node6);
895 assert_eq!(route.hops[2].short_channel_id, 7);
896 assert_eq!(route.hops[2].fee_msat, 0);
897 assert_eq!(route.hops[2].cltv_expiry_delta, (10 << 8) | 1);
899 assert_eq!(route.hops[3].pubkey, node7);
900 assert_eq!(route.hops[3].short_channel_id, 10);
901 assert_eq!(route.hops[3].fee_msat, 100);
902 assert_eq!(route.hops[3].cltv_expiry_delta, 42);
905 { // ...but still use 8 for larger payments as 6 has a variable feerate
906 let route = router.get_route(&node7, &last_hops, 2000, 42).unwrap();
907 assert_eq!(route.hops.len(), 5);
909 assert_eq!(route.hops[0].pubkey, node2);
910 assert_eq!(route.hops[0].short_channel_id, 2);
911 assert_eq!(route.hops[0].fee_msat, 3000);
912 assert_eq!(route.hops[0].cltv_expiry_delta, (4 << 8) | 1);
914 assert_eq!(route.hops[1].pubkey, node3);
915 assert_eq!(route.hops[1].short_channel_id, 4);
916 assert_eq!(route.hops[1].fee_msat, 0);
917 assert_eq!(route.hops[1].cltv_expiry_delta, (6 << 8) | 1);
919 assert_eq!(route.hops[2].pubkey, node5);
920 assert_eq!(route.hops[2].short_channel_id, 6);
921 assert_eq!(route.hops[2].fee_msat, 0);
922 assert_eq!(route.hops[2].cltv_expiry_delta, (11 << 8) | 1);
924 assert_eq!(route.hops[3].pubkey, node4);
925 assert_eq!(route.hops[3].short_channel_id, 11);
926 assert_eq!(route.hops[3].fee_msat, 1000);
927 assert_eq!(route.hops[3].cltv_expiry_delta, (8 << 8) | 1);
929 assert_eq!(route.hops[4].pubkey, node7);
930 assert_eq!(route.hops[4].short_channel_id, 8);
931 assert_eq!(route.hops[4].fee_msat, 2000);
932 assert_eq!(route.hops[4].cltv_expiry_delta, 42);