1 // This file is Copyright its original authors, visible in version control
4 // This file is licensed under the Apache License, Version 2.0 <LICENSE-APACHE
5 // or http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
6 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your option.
7 // You may not use this file except in accordance with one or both of these
10 //! The top-level routing/network map tracking logic lives here.
12 //! You probably want to create a NetGraphMsgHandler and use that as your RoutingMessageHandler and then
13 //! interrogate it to get routes for your own payments.
15 use bitcoin::secp256k1::key::PublicKey;
17 use ln::channelmanager::ChannelDetails;
18 use ln::features::{ChannelFeatures, NodeFeatures};
19 use ln::msgs::{DecodeError, ErrorAction, LightningError, MAX_VALUE_MSAT};
20 use routing::network_graph::{NetworkGraph, RoutingFees};
21 use util::ser::{Writeable, Readable};
22 use util::logger::Logger;
25 use std::collections::{HashMap, BinaryHeap};
29 #[derive(Clone, PartialEq)]
31 /// The node_id of the node at this hop.
32 pub pubkey: PublicKey,
33 /// The node_announcement features of the node at this hop. For the last hop, these may be
34 /// amended to match the features present in the invoice this node generated.
35 pub node_features: NodeFeatures,
36 /// The channel that should be used from the previous hop to reach this node.
37 pub short_channel_id: u64,
38 /// The channel_announcement features of the channel that should be used from the previous hop
39 /// to reach this node.
40 pub channel_features: ChannelFeatures,
41 /// The fee taken on this hop (for paying for the use of the *next* channel in the path).
42 /// For the last hop, this should be the full value of the payment (might be more than
43 /// requested if we had to match htlc_minimum_msat).
45 /// The CLTV delta added for this hop. For the last hop, this should be the full CLTV value
46 /// expected at the destination, in excess of the current block height.
47 pub cltv_expiry_delta: u32,
50 impl Writeable for Vec<RouteHop> {
51 fn write<W: ::util::ser::Writer>(&self, writer: &mut W) -> Result<(), ::std::io::Error> {
52 (self.len() as u8).write(writer)?;
53 for hop in self.iter() {
54 hop.pubkey.write(writer)?;
55 hop.node_features.write(writer)?;
56 hop.short_channel_id.write(writer)?;
57 hop.channel_features.write(writer)?;
58 hop.fee_msat.write(writer)?;
59 hop.cltv_expiry_delta.write(writer)?;
65 impl Readable for Vec<RouteHop> {
66 fn read<R: ::std::io::Read>(reader: &mut R) -> Result<Vec<RouteHop>, DecodeError> {
67 let hops_count: u8 = Readable::read(reader)?;
68 let mut hops = Vec::with_capacity(hops_count as usize);
69 for _ in 0..hops_count {
71 pubkey: Readable::read(reader)?,
72 node_features: Readable::read(reader)?,
73 short_channel_id: Readable::read(reader)?,
74 channel_features: Readable::read(reader)?,
75 fee_msat: Readable::read(reader)?,
76 cltv_expiry_delta: Readable::read(reader)?,
83 /// A route directs a payment from the sender (us) to the recipient. If the recipient supports MPP,
84 /// it can take multiple paths. Each path is composed of one or more hops through the network.
85 #[derive(Clone, PartialEq)]
87 /// The list of routes taken for a single (potentially-)multi-part payment. The pubkey of the
88 /// last RouteHop in each path must be the same.
89 /// Each entry represents a list of hops, NOT INCLUDING our own, where the last hop is the
90 /// destination. Thus, this must always be at least length one. While the maximum length of any
91 /// given path is variable, keeping the length of any path to less than 20 should currently
92 /// ensure it is viable.
93 pub paths: Vec<Vec<RouteHop>>,
96 impl Writeable for Route {
97 fn write<W: ::util::ser::Writer>(&self, writer: &mut W) -> Result<(), ::std::io::Error> {
98 (self.paths.len() as u64).write(writer)?;
99 for hops in self.paths.iter() {
106 impl Readable for Route {
107 fn read<R: ::std::io::Read>(reader: &mut R) -> Result<Route, DecodeError> {
108 let path_count: u64 = Readable::read(reader)?;
109 let mut paths = Vec::with_capacity(cmp::min(path_count, 128) as usize);
110 for _ in 0..path_count {
111 paths.push(Readable::read(reader)?);
117 /// A channel descriptor which provides a last-hop route to get_route
119 pub struct RouteHint {
120 /// The node_id of the non-target end of the route
121 pub src_node_id: PublicKey,
122 /// The short_channel_id of this channel
123 pub short_channel_id: u64,
124 /// The fees which must be paid to use this channel
125 pub fees: RoutingFees,
126 /// The difference in CLTV values between this node and the next node.
127 pub cltv_expiry_delta: u16,
128 /// The minimum value, in msat, which must be relayed to the next hop.
129 pub htlc_minimum_msat: Option<u64>,
130 /// The maximum value in msat available for routing with a single HTLC.
131 pub htlc_maximum_msat: Option<u64>,
134 #[derive(Eq, PartialEq)]
135 struct RouteGraphNode {
137 lowest_fee_to_peer_through_node: u64,
138 lowest_fee_to_node: u64,
139 // The maximum value a yet-to-be-constructed payment path might flow through this node.
140 // This value is upper-bounded by us by:
141 // - how much is needed for a path being constructed
142 // - how much value can channels following this node (up to the destination) can contribute,
143 // considering their capacity and fees
144 value_contribution_msat: u64
147 impl cmp::Ord for RouteGraphNode {
148 fn cmp(&self, other: &RouteGraphNode) -> cmp::Ordering {
149 other.lowest_fee_to_peer_through_node.cmp(&self.lowest_fee_to_peer_through_node)
150 .then_with(|| other.pubkey.serialize().cmp(&self.pubkey.serialize()))
154 impl cmp::PartialOrd for RouteGraphNode {
155 fn partial_cmp(&self, other: &RouteGraphNode) -> Option<cmp::Ordering> {
156 Some(self.cmp(other))
160 struct DummyDirectionalChannelInfo {
161 cltv_expiry_delta: u32,
162 htlc_minimum_msat: u64,
163 htlc_maximum_msat: Option<u64>,
167 /// It's useful to keep track of the hops associated with the fees required to use them,
168 /// so that we can choose cheaper paths (as per Dijkstra's algorithm).
169 /// Fee values should be updated only in the context of the whole path, see update_value_and_recompute_fees.
170 /// These fee values are useful to choose hops as we traverse the graph "payee-to-payer".
172 struct PathBuildingHop {
173 /// Hop-specific details unrelated to the path during the routing phase,
174 /// but rather relevant to the LN graph.
176 /// Minimal fees required to route to the source node of the current hop via any of its inbound channels.
177 src_lowest_inbound_fees: RoutingFees,
178 /// Fees of the channel used in this hop.
179 channel_fees: RoutingFees,
180 /// All the fees paid *after* this channel on the way to the destination
181 next_hops_fee_msat: u64,
182 /// Fee paid for the use of the current channel (see channel_fees).
183 /// The value will be actually deducted from the counterparty balance on the previous link.
184 hop_use_fee_msat: u64,
185 /// Used to compare channels when choosing the for routing.
186 /// Includes paying for the use of a hop and the following hops, as well as
187 /// an estimated cost of reaching this hop.
188 /// Might get stale when fees are recomputed. Primarily for internal use.
190 /// This is useful for update_value_and_recompute_fees to make sure
191 /// we don't fall below the minimum. Should not be updated manually and
192 /// generally should not be accessed.
193 htlc_minimum_msat: u64,
196 // Instantiated with a list of hops with correct data in them collected during path finding,
197 // an instance of this struct should be further modified only via given methods.
200 hops: Vec<PathBuildingHop>,
205 // TODO: Add a value_msat field to PaymentPath and use it instead of this function.
206 fn get_value_msat(&self) -> u64 {
207 self.hops.last().unwrap().route_hop.fee_msat
210 fn get_total_fee_paid_msat(&self) -> u64 {
211 if self.hops.len() < 1 {
215 // Can't use next_hops_fee_msat because it gets outdated.
216 for (i, hop) in self.hops.iter().enumerate() {
217 if i != self.hops.len() - 1 {
218 result += hop.route_hop.fee_msat;
224 // If the amount transferred by the path is updated, the fees should be adjusted. Any other way
225 // to change fees may result in an inconsistency.
227 // Sometimes we call this function right after constructing a path which has inconsistent
228 // (in terms of reaching htlc_minimum_msat), so that this function puts the fees in order.
229 // In that case we call it on the "same" amount we initially allocated for this path, and which
230 // could have been reduced on the way. In that case, there is also a risk of exceeding
231 // available_liquidity inside this function, because the function is unaware of this bound.
232 // In our specific recomputation cases where we never increase the value the risk is pretty low.
233 // This function, however, does not support arbitrarily increasing the value being transferred,
234 // and the exception will be triggered.
235 fn update_value_and_recompute_fees(&mut self, value_msat: u64) {
236 assert!(value_msat <= self.hops.last().unwrap().route_hop.fee_msat);
238 let mut total_fee_paid_msat = 0 as u64;
239 for i in (0..self.hops.len()).rev() {
240 let last_hop = i == self.hops.len() - 1;
242 // For non-last-hop, this value will represent the fees paid on the current hop. It
243 // will consist of the fees for the use of the next hop, and extra fees to match
244 // htlc_minimum_msat of the current channel. Last hop is handled separately.
245 let mut cur_hop_fees_msat = 0;
247 cur_hop_fees_msat = self.hops.get(i + 1).unwrap().hop_use_fee_msat;
250 let mut cur_hop = self.hops.get_mut(i).unwrap();
251 cur_hop.next_hops_fee_msat = total_fee_paid_msat;
252 // Overpay in fees if we can't save these funds due to htlc_minimum_msat.
253 // We try to account for htlc_minimum_msat in scoring (add_entry!), so that nodes don't
254 // set it too high just to maliciously take more fees by exploiting this
255 // match htlc_minimum_msat logic.
256 let mut cur_hop_transferred_amount_msat = total_fee_paid_msat + value_msat;
257 if let Some(extra_fees_msat) = cur_hop.htlc_minimum_msat.checked_sub(cur_hop_transferred_amount_msat) {
258 // Note that there is a risk that *previous hops* (those closer to us, as we go
259 // payee->our_node here) would exceed their htlc_maximum_msat or available balance.
261 // This might make us end up with a broken route, although this should be super-rare
262 // in practice, both because of how healthy channels look like, and how we pick
263 // channels in add_entry.
264 // Also, this can't be exploited more heavily than *announce a free path and fail
266 cur_hop_transferred_amount_msat += extra_fees_msat;
267 total_fee_paid_msat += extra_fees_msat;
268 cur_hop_fees_msat += extra_fees_msat;
272 // Final hop is a special case: it usually has just value_msat (by design), but also
273 // it still could overpay for the htlc_minimum_msat.
274 cur_hop.route_hop.fee_msat = cur_hop_transferred_amount_msat;
276 // Propagate updated fees for the use of the channels to one hop back, where they
277 // will be actually paid (fee_msat). The last hop is handled above separately.
278 cur_hop.route_hop.fee_msat = cur_hop_fees_msat;
281 // Fee for the use of the current hop which will be deducted on the previous hop.
282 // Irrelevant for the first hop, as it doesn't have the previous hop, and the use of
283 // this channel is free for us.
285 if let Some(new_fee) = compute_fees(cur_hop_transferred_amount_msat, cur_hop.channel_fees) {
286 cur_hop.hop_use_fee_msat = new_fee;
287 total_fee_paid_msat += new_fee;
289 // It should not be possible because this function is called only to reduce the
290 // value. In that case, compute_fee was already called with the same fees for
291 // larger amount and there was no overflow.
299 fn compute_fees(amount_msat: u64, channel_fees: RoutingFees) -> Option<u64> {
300 let proportional_fee_millions =
301 amount_msat.checked_mul(channel_fees.proportional_millionths as u64);
302 if let Some(new_fee) = proportional_fee_millions.and_then(|part| {
303 (channel_fees.base_msat as u64).checked_add(part / 1_000_000) }) {
307 // This function may be (indirectly) called without any verification,
308 // with channel_fees provided by a caller. We should handle it gracefully.
313 /// Gets a route from us (payer) to the given target node (payee).
315 /// Extra routing hops between known nodes and the target will be used if they are included in
318 /// If some channels aren't announced, it may be useful to fill in a first_hops with the
319 /// results from a local ChannelManager::list_usable_channels() call. If it is filled in, our
320 /// view of our local channels (from net_graph_msg_handler) will be ignored, and only those
321 /// in first_hops will be used.
323 /// Panics if first_hops contains channels without short_channel_ids
324 /// (ChannelManager::list_usable_channels will never include such channels).
326 /// The fees on channels from us to next-hops are ignored (as they are assumed to all be
327 /// equal), however the enabled/disabled bit on such channels as well as the
328 /// htlc_minimum_msat/htlc_maximum_msat *are* checked as they may change based on the receiving node.
329 pub fn get_route<L: Deref>(our_node_id: &PublicKey, network: &NetworkGraph, payee: &PublicKey, first_hops: Option<&[&ChannelDetails]>,
330 last_hops: &[&RouteHint], final_value_msat: u64, final_cltv: u32, logger: L) -> Result<Route, LightningError> where L::Target: Logger {
331 // TODO: Obviously *only* using total fee cost sucks. We should consider weighting by
332 // uptime/success in using a node in the past.
333 if *payee == *our_node_id {
334 return Err(LightningError{err: "Cannot generate a route to ourselves".to_owned(), action: ErrorAction::IgnoreError});
337 if final_value_msat > MAX_VALUE_MSAT {
338 return Err(LightningError{err: "Cannot generate a route of more value than all existing satoshis".to_owned(), action: ErrorAction::IgnoreError});
341 if final_value_msat == 0 {
342 return Err(LightningError{err: "Cannot send a payment of 0 msat".to_owned(), action: ErrorAction::IgnoreError});
345 for last_hop in last_hops {
346 if last_hop.src_node_id == *payee {
347 return Err(LightningError{err: "Last hop cannot have a payee as a source.".to_owned(), action: ErrorAction::IgnoreError});
351 // The general routing idea is the following:
352 // 1. Fill first/last hops communicated by the caller.
353 // 2. Attempt to construct a path from payer to payee for transferring
354 // any ~sufficient (described later) value.
355 // If succeed, remember which channels were used and how much liquidity they have available,
356 // so that future paths don't rely on the same liquidity.
357 // 3. Prooceed to the next step if:
358 // - we hit the recommended target value;
359 // - OR if we could not construct a new path. Any next attempt will fail too.
360 // Otherwise, repeat step 2.
361 // 4. See if we managed to collect paths which aggregately are able to transfer target value
362 // (not recommended value). If yes, proceed. If not, fail routing.
363 // 5. Randomly combine paths into routes having enough to fulfill the payment. (TODO: knapsack)
364 // 6. Of all the found paths, select only those with the lowest total fee.
365 // 7. The last path in every selected route is likely to be more than we need.
366 // Reduce its value-to-transfer and recompute fees.
367 // 8. Choose the best route by the lowest total fee.
369 // As for the actual search algorithm,
370 // we do a payee-to-payer Dijkstra's sorting by each node's distance from the payee
371 // plus the minimum per-HTLC fee to get from it to another node (aka "shitty A*").
372 // TODO: There are a few tweaks we could do, including possibly pre-calculating more stuff
373 // to use as the A* heuristic beyond just the cost to get one node further than the current
376 let dummy_directional_info = DummyDirectionalChannelInfo { // used for first_hops routes
377 cltv_expiry_delta: 0,
378 htlc_minimum_msat: 0,
379 htlc_maximum_msat: None,
382 proportional_millionths: 0,
386 let mut targets = BinaryHeap::new(); //TODO: Do we care about switching to eg Fibbonaci heap?
387 let mut dist = HashMap::with_capacity(network.get_nodes().len());
389 // When arranging a route, we select multiple paths so that we can make a multi-path payment.
390 // Don't stop searching for paths when we think they're
391 // sufficient to transfer a given value aggregately.
392 // Search for higher value, so that we collect many more paths,
393 // and then select the best combination among them.
394 const ROUTE_CAPACITY_PROVISION_FACTOR: u64 = 3;
395 let recommended_value_msat = final_value_msat * ROUTE_CAPACITY_PROVISION_FACTOR as u64;
398 // Prepare the data we'll use for payee-to-payer search by
399 // inserting first hops suggested by the caller as targets.
400 // Our search will then attempt to reach them while traversing from the payee node.
401 let mut first_hop_targets = HashMap::with_capacity(if first_hops.is_some() { first_hops.as_ref().unwrap().len() } else { 0 });
402 if let Some(hops) = first_hops {
404 let short_channel_id = chan.short_channel_id.expect("first_hops should be filled in with usable channels, not pending ones");
405 if chan.remote_network_id == *our_node_id {
406 return Err(LightningError{err: "First hop cannot have our_node_id as a destination.".to_owned(), action: ErrorAction::IgnoreError});
408 first_hop_targets.insert(chan.remote_network_id, (short_channel_id, chan.counterparty_features.clone(), chan.outbound_capacity_msat));
410 if first_hop_targets.is_empty() {
411 return Err(LightningError{err: "Cannot route when there are no outbound routes away from us".to_owned(), action: ErrorAction::IgnoreError});
415 // We don't want multiple paths (as per MPP) share liquidity of the same channels.
416 // This map allows paths to be aware of the channel use by other paths in the same call.
417 // This would help to make a better path finding decisions and not "overbook" channels.
418 // It is unaware of the directions (except for `outbound_capacity_msat` in `first_hops`).
419 let mut bookkeeped_channels_liquidity_available_msat = HashMap::new();
421 // Keeping track of how much value we already collected across other paths. Helps to decide:
422 // - how much a new path should be transferring (upper bound);
423 // - whether a channel should be disregarded because
424 // it's available liquidity is too small comparing to how much more we need to collect;
425 // - when we want to stop looking for new paths.
426 let mut already_collected_value_msat = 0;
428 macro_rules! add_entry {
429 // Adds entry which goes from $src_node_id to $dest_node_id
430 // over the channel with id $chan_id with fees described in
431 // $directional_info.
432 // $next_hops_fee_msat represents the fees paid for using all the channel *after* this one,
433 // since that value has to be transferred over this channel.
434 ( $chan_id: expr, $src_node_id: expr, $dest_node_id: expr, $directional_info: expr, $capacity_sats: expr, $chan_features: expr, $next_hops_fee_msat: expr,
435 $next_hops_value_contribution: expr ) => {
436 // Channels to self should not be used. This is more of belt-and-suspenders, because in
437 // practice these cases should be caught earlier:
438 // - for regular channels at channel announcement (TODO)
439 // - for first and last hops early in get_route
440 if $src_node_id != $dest_node_id.clone() {
441 let available_liquidity_msat = bookkeeped_channels_liquidity_available_msat.entry($chan_id.clone()).or_insert_with(|| {
442 let mut initial_liquidity_available_msat = None;
443 if let Some(capacity_sats) = $capacity_sats {
444 initial_liquidity_available_msat = Some(capacity_sats * 1000);
447 if let Some(htlc_maximum_msat) = $directional_info.htlc_maximum_msat {
448 if let Some(available_msat) = initial_liquidity_available_msat {
449 initial_liquidity_available_msat = Some(cmp::min(available_msat, htlc_maximum_msat));
451 initial_liquidity_available_msat = Some(htlc_maximum_msat);
455 match initial_liquidity_available_msat {
456 Some(available_msat) => available_msat,
457 // We assume channels with unknown balance have
458 // a capacity of 0.0025 BTC (or 250_000 sats).
459 None => 250_000 * 1000
463 // It is tricky to substract $next_hops_fee_msat from available liquidity here.
464 // It may be misleading because we might later choose to reduce the value transferred
465 // over these channels, and the channel which was insufficient might become sufficient.
466 // Worst case: we drop a good channel here because it can't cover the high following
467 // fees caused by one expensive channel, but then this channel could have been used
468 // if the amount being transferred over this path is lower.
469 // We do this for now, but this is a subject for removal.
470 if let Some(available_value_contribution_msat) = available_liquidity_msat.checked_sub($next_hops_fee_msat) {
472 // Routing Fragmentation Mitigation heuristic:
474 // Routing fragmentation across many payment paths increases the overall routing
475 // fees as you have irreducible routing fees per-link used (`fee_base_msat`).
476 // Taking too many smaller paths also increases the chance of payment failure.
477 // Thus to avoid this effect, we require from our collected links to provide
478 // at least a minimal contribution to the recommended value yet-to-be-fulfilled.
480 // This requirement is currently 5% of the remaining-to-be-collected value.
481 // This means as we successfully advance in our collection,
482 // the absolute liquidity contribution is lowered,
483 // thus increasing the number of potential channels to be selected.
485 // Derive the minimal liquidity contribution with a ratio of 20 (5%, rounded up).
486 let minimal_value_contribution_msat: u64 = (recommended_value_msat - already_collected_value_msat + 19) / 20;
487 // Verify the liquidity offered by this channel complies to the minimal contribution.
488 let contributes_sufficient_value = available_value_contribution_msat >= minimal_value_contribution_msat;
490 let value_contribution_msat = cmp::min(available_value_contribution_msat, $next_hops_value_contribution);
491 // Includes paying fees for the use of the following channels.
492 let amount_to_transfer_over_msat: u64 = match value_contribution_msat.checked_add($next_hops_fee_msat) {
493 Some(result) => result,
494 // Can't overflow due to how the values were computed right above.
495 None => unreachable!(),
498 // If HTLC minimum is larger than the amount we're going to transfer, we shouldn't
499 // bother considering this channel.
500 // Since we're choosing amount_to_transfer_over_msat as maximum possible, it can
501 // be only reduced later (not increased), so this channel should just be skipped
502 // as not sufficient.
503 // TODO: Explore simply adding fee to hit htlc_minimum_msat
504 if contributes_sufficient_value && amount_to_transfer_over_msat >= $directional_info.htlc_minimum_msat {
505 // Note that low contribution here (limited by available_liquidity_msat)
506 // might violate htlc_minimum_msat on the hops which are next along the
507 // payment path (upstream to the payee). To avoid that, we recompute path
508 // path fees knowing the final path contribution after constructing it.
509 let hm_entry = dist.entry(&$src_node_id);
510 let old_entry = hm_entry.or_insert_with(|| {
511 // If there was previously no known way to access
512 // the source node (recall it goes payee-to-payer) of $chan_id, first add
513 // a semi-dummy record just to compute the fees to reach the source node.
514 // This will affect our decision on selecting $chan_id
515 // as a way to reach the $dest_node_id.
516 let mut fee_base_msat = u32::max_value();
517 let mut fee_proportional_millionths = u32::max_value();
518 if let Some(Some(fees)) = network.get_nodes().get(&$src_node_id).map(|node| node.lowest_inbound_channel_fees) {
519 fee_base_msat = fees.base_msat;
520 fee_proportional_millionths = fees.proportional_millionths;
523 route_hop: RouteHop {
524 pubkey: $dest_node_id.clone(),
525 node_features: NodeFeatures::empty(),
527 channel_features: $chan_features.clone(),
529 cltv_expiry_delta: 0,
531 src_lowest_inbound_fees: RoutingFees {
532 base_msat: fee_base_msat,
533 proportional_millionths: fee_proportional_millionths,
535 channel_fees: $directional_info.fees,
536 next_hops_fee_msat: u64::max_value(),
537 hop_use_fee_msat: u64::max_value(),
538 total_fee_msat: u64::max_value(),
539 htlc_minimum_msat: $directional_info.htlc_minimum_msat,
543 let mut hop_use_fee_msat = 0;
544 let mut total_fee_msat = $next_hops_fee_msat;
546 // Ignore hop_use_fee_msat for channel-from-us as we assume all channels-from-us
547 // will have the same effective-fee
548 if $src_node_id != *our_node_id {
549 match compute_fees(amount_to_transfer_over_msat, $directional_info.fees) {
550 // max_value means we'll always fail
551 // the old_entry.total_fee_msat > total_fee_msat check
552 None => total_fee_msat = u64::max_value(),
554 hop_use_fee_msat = fee_msat;
555 total_fee_msat += hop_use_fee_msat;
556 if let Some(prev_hop_fee_msat) = compute_fees(total_fee_msat + amount_to_transfer_over_msat,
557 old_entry.src_lowest_inbound_fees) {
558 if let Some(incremented_total_fee_msat) = total_fee_msat.checked_add(prev_hop_fee_msat) {
559 total_fee_msat = incremented_total_fee_msat;
562 // max_value means we'll always fail
563 // the old_entry.total_fee_msat > total_fee_msat check
564 total_fee_msat = u64::max_value();
567 // max_value means we'll always fail
568 // the old_entry.total_fee_msat > total_fee_msat check
569 total_fee_msat = u64::max_value();
575 let new_graph_node = RouteGraphNode {
576 pubkey: $src_node_id,
577 lowest_fee_to_peer_through_node: total_fee_msat,
578 lowest_fee_to_node: $next_hops_fee_msat as u64 + hop_use_fee_msat,
579 value_contribution_msat: value_contribution_msat,
582 // Update the way of reaching $src_node_id with the given $chan_id (from $dest_node_id),
583 // if this way is cheaper than the already known
584 // (considering the cost to "reach" this channel from the route destination,
585 // the cost of using this channel,
586 // and the cost of routing to the source node of this channel).
587 // Also, consider that htlc_minimum_msat_difference, because we might end up
588 // paying it. Consider the following exploit:
589 // we use 2 paths to transfer 1.5 BTC. One of them is 0-fee normal 1 BTC path,
590 // and for the other one we picked a 1sat-fee path with htlc_minimum_msat of
591 // 1 BTC. Now, since the latter is more expensive, we gonna try to cut it
592 // by 0.5 BTC, but then match htlc_minimum_msat by paying a fee of 0.5 BTC
594 // TODO: this scoring could be smarter (e.g. 0.5*htlc_minimum_msat here).
595 let mut old_cost = old_entry.total_fee_msat;
596 if let Some(increased_old_cost) = old_cost.checked_add(old_entry.htlc_minimum_msat) {
597 old_cost = increased_old_cost;
599 old_cost = u64::max_value();
602 let mut new_cost = total_fee_msat;
603 if let Some(increased_new_cost) = new_cost.checked_add($directional_info.htlc_minimum_msat) {
604 new_cost = increased_new_cost;
606 new_cost = u64::max_value();
609 if new_cost < old_cost {
610 targets.push(new_graph_node);
611 old_entry.next_hops_fee_msat = $next_hops_fee_msat;
612 old_entry.hop_use_fee_msat = hop_use_fee_msat;
613 old_entry.total_fee_msat = total_fee_msat;
614 old_entry.route_hop = RouteHop {
615 pubkey: $dest_node_id.clone(),
616 node_features: NodeFeatures::empty(),
617 short_channel_id: $chan_id.clone(),
618 channel_features: $chan_features.clone(),
619 fee_msat: 0, // This value will be later filled with hop_use_fee_msat of the following channel
620 cltv_expiry_delta: $directional_info.cltv_expiry_delta as u32,
622 old_entry.channel_fees = $directional_info.fees;
623 // It's probably fine to replace the old entry, because the new one
624 // passed the htlc_minimum-related checks above.
625 old_entry.htlc_minimum_msat = $directional_info.htlc_minimum_msat;
633 // Find ways (channels with destination) to reach a given node and store them
634 // in the corresponding data structures (routing graph etc).
635 // $fee_to_target_msat represents how much it costs to reach to this node from the payee,
636 // meaning how much will be paid in fees after this node (to the best of our knowledge).
637 // This data can later be helpful to optimize routing (pay lower fees).
638 macro_rules! add_entries_to_cheapest_to_target_node {
639 ( $node: expr, $node_id: expr, $fee_to_target_msat: expr, $next_hops_value_contribution: expr ) => {
640 if first_hops.is_some() {
641 if let Some(&(ref first_hop, ref features, ref outbound_capacity_msat)) = first_hop_targets.get(&$node_id) {
642 add_entry!(first_hop, *our_node_id, $node_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), $fee_to_target_msat, $next_hops_value_contribution);
647 if let Some(node_info) = $node.announcement_info.as_ref() {
648 features = node_info.features.clone();
650 features = NodeFeatures::empty();
653 if !features.requires_unknown_bits() {
654 for chan_id in $node.channels.iter() {
655 let chan = network.get_channels().get(chan_id).unwrap();
656 if !chan.features.requires_unknown_bits() {
657 if chan.node_one == *$node_id {
658 // ie $node is one, ie next hop in A* is two, via the two_to_one channel
659 if first_hops.is_none() || chan.node_two != *our_node_id {
660 if let Some(two_to_one) = chan.two_to_one.as_ref() {
661 if two_to_one.enabled {
662 add_entry!(chan_id, chan.node_two, chan.node_one, two_to_one, chan.capacity_sats, chan.features, $fee_to_target_msat, $next_hops_value_contribution);
667 if first_hops.is_none() || chan.node_one != *our_node_id {
668 if let Some(one_to_two) = chan.one_to_two.as_ref() {
669 if one_to_two.enabled {
670 add_entry!(chan_id, chan.node_one, chan.node_two, one_to_two, chan.capacity_sats, chan.features, $fee_to_target_msat, $next_hops_value_contribution);
682 let mut payment_paths = Vec::<PaymentPath>::new();
684 // TODO: diversify by nodes (so that all paths aren't doomed if one node is offline).
685 'paths_collection: loop {
686 // For every new path, start from scratch, except
687 // bookkeeped_channels_liquidity_available_msat, which will improve
688 // the further iterations of path finding. Also don't erase first_hop_targets.
692 // If first hop is a private channel and the only way to reach the payee, this is the only
693 // place where it could be added.
694 if first_hops.is_some() {
695 if let Some(&(ref first_hop, ref features, ref outbound_capacity_msat)) = first_hop_targets.get(&payee) {
696 add_entry!(first_hop, *our_node_id, payee, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, recommended_value_msat);
700 // Add the payee as a target, so that the payee-to-payer
701 // search algorithm knows what to start with.
702 match network.get_nodes().get(payee) {
703 // The payee is not in our network graph, so nothing to add here.
704 // There is still a chance of reaching them via last_hops though,
705 // so don't yet fail the payment here.
706 // If not, targets.pop() will not even let us enter the loop in step 2.
709 add_entries_to_cheapest_to_target_node!(node, payee, 0, recommended_value_msat);
714 // If a caller provided us with last hops, add them to routing targets. Since this happens
715 // earlier than general path finding, they will be somewhat prioritized, although currently
716 // it matters only if the fees are exactly the same.
717 for hop in last_hops.iter() {
718 let have_hop_src_in_graph =
719 if let Some(&(ref first_hop, ref features, ref outbound_capacity_msat)) = first_hop_targets.get(&hop.src_node_id) {
720 // If this hop connects to a node with which we have a direct channel, ignore
721 // the network graph and add both the hop and our direct channel to
722 // the candidate set.
724 // Currently there are no channel-context features defined, so we are a
725 // bit lazy here. In the future, we should pull them out via our
726 // ChannelManager, but there's no reason to waste the space until we
728 add_entry!(first_hop, *our_node_id , hop.src_node_id, dummy_directional_info, Some(outbound_capacity_msat / 1000), features.to_context(), 0, recommended_value_msat);
731 // In any other case, only add the hop if the source is in the regular network
733 network.get_nodes().get(&hop.src_node_id).is_some()
735 if have_hop_src_in_graph {
736 // BOLT 11 doesn't allow inclusion of features for the last hop hints, which
737 // really sucks, cause we're gonna need that eventually.
738 let last_hop_htlc_minimum_msat: u64 = match hop.htlc_minimum_msat {
739 Some(htlc_minimum_msat) => htlc_minimum_msat,
742 let directional_info = DummyDirectionalChannelInfo {
743 cltv_expiry_delta: hop.cltv_expiry_delta as u32,
744 htlc_minimum_msat: last_hop_htlc_minimum_msat,
745 htlc_maximum_msat: hop.htlc_maximum_msat,
748 add_entry!(hop.short_channel_id, hop.src_node_id, payee, directional_info, None::<u64>, ChannelFeatures::empty(), 0, recommended_value_msat);
752 // At this point, targets are filled with the data from first and
753 // last hops communicated by the caller, and the payment receiver.
754 let mut found_new_path = false;
757 // If this loop terminates due the exhaustion of targets, two situations are possible:
758 // - not enough outgoing liquidity:
759 // 0 < already_collected_value_msat < final_value_msat
760 // - enough outgoing liquidity:
761 // final_value_msat <= already_collected_value_msat < recommended_value_msat
762 // Both these cases (and other cases except reaching recommended_value_msat) mean that
763 // paths_collection will be stopped because found_new_path==false.
764 // This is not necessarily a routing failure.
765 'path_construction: while let Some(RouteGraphNode { pubkey, lowest_fee_to_node, value_contribution_msat, .. }) = targets.pop() {
767 // Since we're going payee-to-payer, hitting our node as a target means we should stop
768 // traversing the graph and arrange the path out of what we found.
769 if pubkey == *our_node_id {
770 let mut new_entry = dist.remove(&our_node_id).unwrap();
771 let mut ordered_hops = vec!(new_entry.clone());
774 if let Some(&(_, ref features, _)) = first_hop_targets.get(&ordered_hops.last().unwrap().route_hop.pubkey) {
775 ordered_hops.last_mut().unwrap().route_hop.node_features = features.to_context();
776 } else if let Some(node) = network.get_nodes().get(&ordered_hops.last().unwrap().route_hop.pubkey) {
777 if let Some(node_info) = node.announcement_info.as_ref() {
778 ordered_hops.last_mut().unwrap().route_hop.node_features = node_info.features.clone();
780 ordered_hops.last_mut().unwrap().route_hop.node_features = NodeFeatures::empty();
783 // We should be able to fill in features for everything except the last
784 // hop, if the last hop was provided via a BOLT 11 invoice (though we
785 // should be able to extend it further as BOLT 11 does have feature
786 // flags for the last hop node itself).
787 assert!(ordered_hops.last().unwrap().route_hop.pubkey == *payee);
790 // Means we succesfully traversed from the payer to the payee, now
791 // save this path for the payment route. Also, update the liquidity
792 // remaining on the used hops, so that we take them into account
793 // while looking for more paths.
794 if ordered_hops.last().unwrap().route_hop.pubkey == *payee {
798 new_entry = match dist.remove(&ordered_hops.last().unwrap().route_hop.pubkey) {
799 Some(payment_hop) => payment_hop,
800 // We can't arrive at None because, if we ever add an entry to targets,
801 // we also fill in the entry in dist (see add_entry!).
802 None => unreachable!(),
804 // We "propagate" the fees one hop backward (topologically) here,
805 // so that fees paid for a HTLC forwarding on the current channel are
806 // associated with the previous channel (where they will be subtracted).
807 ordered_hops.last_mut().unwrap().route_hop.fee_msat = new_entry.hop_use_fee_msat;
808 ordered_hops.last_mut().unwrap().route_hop.cltv_expiry_delta = new_entry.route_hop.cltv_expiry_delta;
809 ordered_hops.push(new_entry.clone());
811 ordered_hops.last_mut().unwrap().route_hop.fee_msat = value_contribution_msat;
812 ordered_hops.last_mut().unwrap().hop_use_fee_msat = 0;
813 ordered_hops.last_mut().unwrap().route_hop.cltv_expiry_delta = final_cltv;
815 let mut payment_path = PaymentPath {hops: ordered_hops};
817 // We could have possibly constructed a slightly inconsistent path: since we reduce
818 // value being transferred along the way, we could have violated htlc_minimum_msat
819 // on some channels we already passed (assuming dest->source direction). Here, we
820 // recompute the fees again, so that if that's the case, we match the currently
821 // underpaid htlc_minimum_msat with fees.
822 payment_path.update_value_and_recompute_fees(value_contribution_msat);
824 // Since a path allows to transfer as much value as
825 // the smallest channel it has ("bottleneck"), we should recompute
826 // the fees so sender HTLC don't overpay fees when traversing
827 // larger channels than the bottleneck. This may happen because
828 // when we were selecting those channels we were not aware how much value
829 // this path will transfer, and the relative fee for them
830 // might have been computed considering a larger value.
831 // Remember that we used these channels so that we don't rely
832 // on the same liquidity in future paths.
833 for payment_hop in payment_path.hops.iter() {
834 let channel_liquidity_available_msat = bookkeeped_channels_liquidity_available_msat.get_mut(&payment_hop.route_hop.short_channel_id).unwrap();
835 let mut spent_on_hop_msat = value_contribution_msat;
836 let next_hops_fee_msat = payment_hop.next_hops_fee_msat;
837 spent_on_hop_msat += next_hops_fee_msat;
838 if *channel_liquidity_available_msat < spent_on_hop_msat {
839 // This should not happen because we do recompute fees right before,
840 // trying to avoid cases when a hop is not usable due to the fee situation.
841 break 'path_construction;
843 *channel_liquidity_available_msat -= spent_on_hop_msat;
845 // Track the total amount all our collected paths allow to send so that we:
846 // - know when to stop looking for more paths
847 // - know which of the hops are useless considering how much more sats we need
848 // (contributes_sufficient_value)
849 already_collected_value_msat += value_contribution_msat;
851 payment_paths.push(payment_path);
852 found_new_path = true;
853 break 'path_construction;
856 // Otherwise, since the current target node is not us,
857 // keep "unrolling" the payment graph from payee to payer by
858 // finding a way to reach the current target from the payer side.
859 match network.get_nodes().get(&pubkey) {
862 add_entries_to_cheapest_to_target_node!(node, &pubkey, lowest_fee_to_node, value_contribution_msat);
868 // Stop either when recommended value is reached,
869 // or if during last iteration no new path was found.
870 // In the latter case, making another path finding attempt could not help,
871 // because we deterministically terminate the search due to low liquidity.
872 if already_collected_value_msat >= recommended_value_msat || !found_new_path {
873 break 'paths_collection;
878 if payment_paths.len() == 0 {
879 return Err(LightningError{err: "Failed to find a path to the given destination".to_owned(), action: ErrorAction::IgnoreError});
882 if already_collected_value_msat < final_value_msat {
883 return Err(LightningError{err: "Failed to find a sufficient route to the given destination".to_owned(), action: ErrorAction::IgnoreError});
886 // Sort by total fees and take the best paths.
887 payment_paths.sort_by_key(|path| path.get_total_fee_paid_msat());
888 if payment_paths.len() > 50 {
889 payment_paths.truncate(50);
892 // Draw multiple sufficient routes by randomly combining the selected paths.
893 let mut drawn_routes = Vec::new();
894 for i in 0..payment_paths.len() {
895 let mut cur_route = Vec::<PaymentPath>::new();
896 let mut aggregate_route_value_msat = 0;
899 // TODO: real random shuffle
900 // Currently just starts with i_th and goes up to i-1_th in a looped way.
901 let cur_payment_paths = [&payment_paths[i..], &payment_paths[..i]].concat();
904 for payment_path in cur_payment_paths {
905 cur_route.push(payment_path.clone());
906 aggregate_route_value_msat += payment_path.get_value_msat();
907 if aggregate_route_value_msat > final_value_msat {
908 // Last path likely overpaid. Substract it from the most expensive
909 // (in terms of proportional fee) path in this route and recompute fees.
910 // This might be not the most economically efficient way, but fewer paths
911 // also makes routing more reliable.
912 let mut overpaid_value_msat = aggregate_route_value_msat - final_value_msat;
914 // First, drop some expensive low-value paths entirely if possible.
915 // Sort by value so that we drop many really-low values first, since
916 // fewer paths is better: the payment is less likely to fail.
917 // TODO: this could also be optimized by also sorting by feerate_per_sat_routed,
918 // so that the sender pays less fees overall. And also htlc_minimum_msat.
919 cur_route.sort_by_key(|path| path.get_value_msat());
920 // We should make sure that at least 1 path left.
921 let mut paths_left = cur_route.len();
922 cur_route.retain(|path| {
927 let path_value_msat = path.get_value_msat();
928 if path_value_msat <= overpaid_value_msat {
930 overpaid_value_msat -= path_value_msat;
936 if overpaid_value_msat == 0 {
940 assert!(cur_route.len() > 0);
943 // Now, substract the overpaid value from the most-expensive path.
944 // TODO: this could also be optimized by also sorting by feerate_per_sat_routed,
945 // so that the sender pays less fees overall. And also htlc_minimum_msat.
946 cur_route.sort_by_key(|path| { path.hops.iter().map(|hop| hop.channel_fees.proportional_millionths as u64).sum::<u64>() });
947 let mut expensive_payment_path = cur_route.first_mut().unwrap();
948 // We already dropped all the small channels above, meaning all the
949 // remaining channels are larger than remaining overpaid_value_msat.
950 // Thus, this can't be negative.
951 let expensive_path_new_value_msat = expensive_payment_path.get_value_msat() - overpaid_value_msat;
952 expensive_payment_path.update_value_and_recompute_fees(expensive_path_new_value_msat);
956 drawn_routes.push(cur_route);
960 // Select the best route by lowest total fee.
961 drawn_routes.sort_by_key(|paths| paths.iter().map(|path| path.get_total_fee_paid_msat()).sum::<u64>());
962 let mut selected_paths = Vec::<Vec::<RouteHop>>::new();
963 for payment_path in drawn_routes.first().unwrap() {
964 selected_paths.push(payment_path.hops.iter().map(|payment_hop| payment_hop.route_hop.clone()).collect());
967 let route = Route { paths: selected_paths };
968 log_trace!(logger, "Got route: {}", log_route!(route));
974 use routing::router::{get_route, RouteHint, RoutingFees};
975 use routing::network_graph::{NetworkGraph, NetGraphMsgHandler};
976 use ln::features::{ChannelFeatures, InitFeatures, NodeFeatures};
977 use ln::msgs::{ErrorAction, LightningError, OptionalField, UnsignedChannelAnnouncement, ChannelAnnouncement, RoutingMessageHandler,
978 NodeAnnouncement, UnsignedNodeAnnouncement, ChannelUpdate, UnsignedChannelUpdate};
979 use ln::channelmanager;
980 use util::test_utils;
981 use util::ser::Writeable;
983 use bitcoin::hashes::sha256d::Hash as Sha256dHash;
984 use bitcoin::hashes::Hash;
985 use bitcoin::network::constants::Network;
986 use bitcoin::blockdata::constants::genesis_block;
987 use bitcoin::blockdata::script::Builder;
988 use bitcoin::blockdata::opcodes;
989 use bitcoin::blockdata::transaction::TxOut;
993 use bitcoin::secp256k1::key::{PublicKey,SecretKey};
994 use bitcoin::secp256k1::{Secp256k1, All};
998 // Using the same keys for LN and BTC ids
999 fn add_channel(net_graph_msg_handler: &NetGraphMsgHandler<Arc<test_utils::TestChainSource>, Arc<test_utils::TestLogger>>, secp_ctx: &Secp256k1<All>, node_1_privkey: &SecretKey,
1000 node_2_privkey: &SecretKey, features: ChannelFeatures, short_channel_id: u64) {
1001 let node_id_1 = PublicKey::from_secret_key(&secp_ctx, node_1_privkey);
1002 let node_id_2 = PublicKey::from_secret_key(&secp_ctx, node_2_privkey);
1004 let unsigned_announcement = UnsignedChannelAnnouncement {
1006 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1010 bitcoin_key_1: node_id_1,
1011 bitcoin_key_2: node_id_2,
1012 excess_data: Vec::new(),
1015 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
1016 let valid_announcement = ChannelAnnouncement {
1017 node_signature_1: secp_ctx.sign(&msghash, node_1_privkey),
1018 node_signature_2: secp_ctx.sign(&msghash, node_2_privkey),
1019 bitcoin_signature_1: secp_ctx.sign(&msghash, node_1_privkey),
1020 bitcoin_signature_2: secp_ctx.sign(&msghash, node_2_privkey),
1021 contents: unsigned_announcement.clone(),
1023 match net_graph_msg_handler.handle_channel_announcement(&valid_announcement) {
1024 Ok(res) => assert!(res),
1029 fn update_channel(net_graph_msg_handler: &NetGraphMsgHandler<Arc<test_utils::TestChainSource>, Arc<test_utils::TestLogger>>, secp_ctx: &Secp256k1<All>, node_privkey: &SecretKey, update: UnsignedChannelUpdate) {
1030 let msghash = hash_to_message!(&Sha256dHash::hash(&update.encode()[..])[..]);
1031 let valid_channel_update = ChannelUpdate {
1032 signature: secp_ctx.sign(&msghash, node_privkey),
1033 contents: update.clone()
1036 match net_graph_msg_handler.handle_channel_update(&valid_channel_update) {
1037 Ok(res) => assert!(res),
1042 fn add_or_update_node(net_graph_msg_handler: &NetGraphMsgHandler<Arc<test_utils::TestChainSource>, Arc<test_utils::TestLogger>>, secp_ctx: &Secp256k1<All>, node_privkey: &SecretKey,
1043 features: NodeFeatures, timestamp: u32) {
1044 let node_id = PublicKey::from_secret_key(&secp_ctx, node_privkey);
1045 let unsigned_announcement = UnsignedNodeAnnouncement {
1051 addresses: Vec::new(),
1052 excess_address_data: Vec::new(),
1053 excess_data: Vec::new(),
1055 let msghash = hash_to_message!(&Sha256dHash::hash(&unsigned_announcement.encode()[..])[..]);
1056 let valid_announcement = NodeAnnouncement {
1057 signature: secp_ctx.sign(&msghash, node_privkey),
1058 contents: unsigned_announcement.clone()
1061 match net_graph_msg_handler.handle_node_announcement(&valid_announcement) {
1067 fn get_nodes(secp_ctx: &Secp256k1<All>) -> (SecretKey, PublicKey, Vec<SecretKey>, Vec<PublicKey>) {
1068 let privkeys: Vec<SecretKey> = (2..10).map(|i| {
1069 SecretKey::from_slice(&hex::decode(format!("{:02}", i).repeat(32)).unwrap()[..]).unwrap()
1072 let pubkeys = privkeys.iter().map(|secret| PublicKey::from_secret_key(&secp_ctx, secret)).collect();
1074 let our_privkey = SecretKey::from_slice(&hex::decode("01".repeat(32)).unwrap()[..]).unwrap();
1075 let our_id = PublicKey::from_secret_key(&secp_ctx, &our_privkey);
1077 (our_privkey, our_id, privkeys, pubkeys)
1080 fn id_to_feature_flags(id: u8) -> Vec<u8> {
1081 // Set the feature flags to the id'th odd (ie non-required) feature bit so that we can
1082 // test for it later.
1083 let idx = (id - 1) * 2 + 1;
1085 vec![1 << (idx - 8*3), 0, 0, 0]
1086 } else if idx > 8*2 {
1087 vec![1 << (idx - 8*2), 0, 0]
1088 } else if idx > 8*1 {
1089 vec![1 << (idx - 8*1), 0]
1095 fn build_graph() -> (Secp256k1<All>, NetGraphMsgHandler<std::sync::Arc<test_utils::TestChainSource>, std::sync::Arc<crate::util::test_utils::TestLogger>>, std::sync::Arc<test_utils::TestChainSource>, std::sync::Arc<test_utils::TestLogger>) {
1096 let secp_ctx = Secp256k1::new();
1097 let logger = Arc::new(test_utils::TestLogger::new());
1098 let chain_monitor = Arc::new(test_utils::TestChainSource::new(Network::Testnet));
1099 let net_graph_msg_handler = NetGraphMsgHandler::new(genesis_block(Network::Testnet).header.block_hash(), None, Arc::clone(&logger));
1100 // Build network from our_id to node7:
1102 // -1(1)2- node0 -1(3)2-
1104 // our_id -1(12)2- node7 -1(13)2--- node2
1106 // -1(2)2- node1 -1(4)2-
1109 // chan1 1-to-2: disabled
1110 // chan1 2-to-1: enabled, 0 fee
1112 // chan2 1-to-2: enabled, ignored fee
1113 // chan2 2-to-1: enabled, 0 fee
1115 // chan3 1-to-2: enabled, 0 fee
1116 // chan3 2-to-1: enabled, 100 msat fee
1118 // chan4 1-to-2: enabled, 100% fee
1119 // chan4 2-to-1: enabled, 0 fee
1121 // chan12 1-to-2: enabled, ignored fee
1122 // chan12 2-to-1: enabled, 0 fee
1124 // chan13 1-to-2: enabled, 200% fee
1125 // chan13 2-to-1: enabled, 0 fee
1128 // -1(5)2- node3 -1(8)2--
1132 // node2--1(6)2- node4 -1(9)2--- node6 (not in global route map)
1134 // -1(7)2- node5 -1(10)2-
1136 // chan5 1-to-2: enabled, 100 msat fee
1137 // chan5 2-to-1: enabled, 0 fee
1139 // chan6 1-to-2: enabled, 0 fee
1140 // chan6 2-to-1: enabled, 0 fee
1142 // chan7 1-to-2: enabled, 100% fee
1143 // chan7 2-to-1: enabled, 0 fee
1145 // chan8 1-to-2: enabled, variable fee (0 then 1000 msat)
1146 // chan8 2-to-1: enabled, 0 fee
1148 // chan9 1-to-2: enabled, 1001 msat fee
1149 // chan9 2-to-1: enabled, 0 fee
1151 // chan10 1-to-2: enabled, 0 fee
1152 // chan10 2-to-1: enabled, 0 fee
1154 // chan11 1-to-2: enabled, 0 fee
1155 // chan11 2-to-1: enabled, 0 fee
1157 let (our_privkey, _, privkeys, _) = get_nodes(&secp_ctx);
1159 add_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, &privkeys[0], ChannelFeatures::from_le_bytes(id_to_feature_flags(1)), 1);
1160 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
1161 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1162 short_channel_id: 1,
1165 cltv_expiry_delta: 0,
1166 htlc_minimum_msat: 0,
1167 htlc_maximum_msat: OptionalField::Absent,
1169 fee_proportional_millionths: 0,
1170 excess_data: Vec::new()
1173 add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[0], NodeFeatures::from_le_bytes(id_to_feature_flags(1)), 0);
1175 add_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, &privkeys[1], ChannelFeatures::from_le_bytes(id_to_feature_flags(2)), 2);
1176 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
1177 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1178 short_channel_id: 2,
1181 cltv_expiry_delta: u16::max_value(),
1182 htlc_minimum_msat: 0,
1183 htlc_maximum_msat: OptionalField::Absent,
1184 fee_base_msat: u32::max_value(),
1185 fee_proportional_millionths: u32::max_value(),
1186 excess_data: Vec::new()
1188 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[1], UnsignedChannelUpdate {
1189 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1190 short_channel_id: 2,
1193 cltv_expiry_delta: 0,
1194 htlc_minimum_msat: 0,
1195 htlc_maximum_msat: OptionalField::Absent,
1197 fee_proportional_millionths: 0,
1198 excess_data: Vec::new()
1201 add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[1], NodeFeatures::from_le_bytes(id_to_feature_flags(2)), 0);
1203 add_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, &privkeys[7], ChannelFeatures::from_le_bytes(id_to_feature_flags(12)), 12);
1204 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
1205 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1206 short_channel_id: 12,
1209 cltv_expiry_delta: u16::max_value(),
1210 htlc_minimum_msat: 0,
1211 htlc_maximum_msat: OptionalField::Absent,
1212 fee_base_msat: u32::max_value(),
1213 fee_proportional_millionths: u32::max_value(),
1214 excess_data: Vec::new()
1216 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], UnsignedChannelUpdate {
1217 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1218 short_channel_id: 12,
1221 cltv_expiry_delta: 0,
1222 htlc_minimum_msat: 0,
1223 htlc_maximum_msat: OptionalField::Absent,
1225 fee_proportional_millionths: 0,
1226 excess_data: Vec::new()
1229 add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[7], NodeFeatures::from_le_bytes(id_to_feature_flags(8)), 0);
1231 add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], &privkeys[2], ChannelFeatures::from_le_bytes(id_to_feature_flags(3)), 3);
1232 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
1233 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1234 short_channel_id: 3,
1237 cltv_expiry_delta: (3 << 8) | 1,
1238 htlc_minimum_msat: 0,
1239 htlc_maximum_msat: OptionalField::Absent,
1241 fee_proportional_millionths: 0,
1242 excess_data: Vec::new()
1244 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
1245 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1246 short_channel_id: 3,
1249 cltv_expiry_delta: (3 << 8) | 2,
1250 htlc_minimum_msat: 0,
1251 htlc_maximum_msat: OptionalField::Absent,
1253 fee_proportional_millionths: 0,
1254 excess_data: Vec::new()
1257 add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[1], &privkeys[2], ChannelFeatures::from_le_bytes(id_to_feature_flags(4)), 4);
1258 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[1], UnsignedChannelUpdate {
1259 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1260 short_channel_id: 4,
1263 cltv_expiry_delta: (4 << 8) | 1,
1264 htlc_minimum_msat: 0,
1265 htlc_maximum_msat: OptionalField::Absent,
1267 fee_proportional_millionths: 1000000,
1268 excess_data: Vec::new()
1270 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
1271 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1272 short_channel_id: 4,
1275 cltv_expiry_delta: (4 << 8) | 2,
1276 htlc_minimum_msat: 0,
1277 htlc_maximum_msat: OptionalField::Absent,
1279 fee_proportional_millionths: 0,
1280 excess_data: Vec::new()
1283 add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], &privkeys[2], ChannelFeatures::from_le_bytes(id_to_feature_flags(13)), 13);
1284 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], UnsignedChannelUpdate {
1285 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1286 short_channel_id: 13,
1289 cltv_expiry_delta: (13 << 8) | 1,
1290 htlc_minimum_msat: 0,
1291 htlc_maximum_msat: OptionalField::Absent,
1293 fee_proportional_millionths: 2000000,
1294 excess_data: Vec::new()
1296 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
1297 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1298 short_channel_id: 13,
1301 cltv_expiry_delta: (13 << 8) | 2,
1302 htlc_minimum_msat: 0,
1303 htlc_maximum_msat: OptionalField::Absent,
1305 fee_proportional_millionths: 0,
1306 excess_data: Vec::new()
1309 add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[2], NodeFeatures::from_le_bytes(id_to_feature_flags(3)), 0);
1311 add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], &privkeys[4], ChannelFeatures::from_le_bytes(id_to_feature_flags(6)), 6);
1312 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
1313 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1314 short_channel_id: 6,
1317 cltv_expiry_delta: (6 << 8) | 1,
1318 htlc_minimum_msat: 0,
1319 htlc_maximum_msat: OptionalField::Absent,
1321 fee_proportional_millionths: 0,
1322 excess_data: Vec::new()
1324 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], UnsignedChannelUpdate {
1325 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1326 short_channel_id: 6,
1329 cltv_expiry_delta: (6 << 8) | 2,
1330 htlc_minimum_msat: 0,
1331 htlc_maximum_msat: OptionalField::Absent,
1333 fee_proportional_millionths: 0,
1334 excess_data: Vec::new(),
1337 add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], &privkeys[3], ChannelFeatures::from_le_bytes(id_to_feature_flags(11)), 11);
1338 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], UnsignedChannelUpdate {
1339 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1340 short_channel_id: 11,
1343 cltv_expiry_delta: (11 << 8) | 1,
1344 htlc_minimum_msat: 0,
1345 htlc_maximum_msat: OptionalField::Absent,
1347 fee_proportional_millionths: 0,
1348 excess_data: Vec::new()
1350 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[3], UnsignedChannelUpdate {
1351 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1352 short_channel_id: 11,
1355 cltv_expiry_delta: (11 << 8) | 2,
1356 htlc_minimum_msat: 0,
1357 htlc_maximum_msat: OptionalField::Absent,
1359 fee_proportional_millionths: 0,
1360 excess_data: Vec::new()
1363 add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[4], NodeFeatures::from_le_bytes(id_to_feature_flags(5)), 0);
1365 add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[3], NodeFeatures::from_le_bytes(id_to_feature_flags(4)), 0);
1367 add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], &privkeys[5], ChannelFeatures::from_le_bytes(id_to_feature_flags(7)), 7);
1368 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
1369 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1370 short_channel_id: 7,
1373 cltv_expiry_delta: (7 << 8) | 1,
1374 htlc_minimum_msat: 0,
1375 htlc_maximum_msat: OptionalField::Absent,
1377 fee_proportional_millionths: 1000000,
1378 excess_data: Vec::new()
1380 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[5], UnsignedChannelUpdate {
1381 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1382 short_channel_id: 7,
1385 cltv_expiry_delta: (7 << 8) | 2,
1386 htlc_minimum_msat: 0,
1387 htlc_maximum_msat: OptionalField::Absent,
1389 fee_proportional_millionths: 0,
1390 excess_data: Vec::new()
1393 add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[5], NodeFeatures::from_le_bytes(id_to_feature_flags(6)), 0);
1395 (secp_ctx, net_graph_msg_handler, chain_monitor, logger)
1399 fn simple_route_test() {
1400 let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
1401 let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
1403 // Simple route to 2 via 1
1405 if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 0, 42, Arc::clone(&logger)) {
1406 assert_eq!(err, "Cannot send a payment of 0 msat");
1407 } else { panic!(); }
1409 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
1410 assert_eq!(route.paths[0].len(), 2);
1412 assert_eq!(route.paths[0][0].pubkey, nodes[1]);
1413 assert_eq!(route.paths[0][0].short_channel_id, 2);
1414 assert_eq!(route.paths[0][0].fee_msat, 100);
1415 assert_eq!(route.paths[0][0].cltv_expiry_delta, (4 << 8) | 1);
1416 assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(2));
1417 assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(2));
1419 assert_eq!(route.paths[0][1].pubkey, nodes[2]);
1420 assert_eq!(route.paths[0][1].short_channel_id, 4);
1421 assert_eq!(route.paths[0][1].fee_msat, 100);
1422 assert_eq!(route.paths[0][1].cltv_expiry_delta, 42);
1423 assert_eq!(route.paths[0][1].node_features.le_flags(), &id_to_feature_flags(3));
1424 assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(4));
1428 fn invalid_first_hop_test() {
1429 let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
1430 let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
1432 // Simple route to 2 via 1
1434 let our_chans = vec![channelmanager::ChannelDetails {
1435 channel_id: [0; 32],
1436 short_channel_id: Some(2),
1437 remote_network_id: our_id,
1438 counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
1439 channel_value_satoshis: 100000,
1441 outbound_capacity_msat: 100000,
1442 inbound_capacity_msat: 100000,
1446 if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)) {
1447 assert_eq!(err, "First hop cannot have our_node_id as a destination.");
1448 } else { panic!(); }
1450 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
1451 assert_eq!(route.paths[0].len(), 2);
1455 fn htlc_minimum_test() {
1456 let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
1457 let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
1459 // Simple route to 2 via 1
1461 // Disable other paths
1462 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
1463 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1464 short_channel_id: 12,
1466 flags: 2, // to disable
1467 cltv_expiry_delta: 0,
1468 htlc_minimum_msat: 0,
1469 htlc_maximum_msat: OptionalField::Absent,
1471 fee_proportional_millionths: 0,
1472 excess_data: Vec::new()
1474 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
1475 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1476 short_channel_id: 3,
1478 flags: 2, // to disable
1479 cltv_expiry_delta: 0,
1480 htlc_minimum_msat: 0,
1481 htlc_maximum_msat: OptionalField::Absent,
1483 fee_proportional_millionths: 0,
1484 excess_data: Vec::new()
1486 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], UnsignedChannelUpdate {
1487 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1488 short_channel_id: 13,
1490 flags: 2, // to disable
1491 cltv_expiry_delta: 0,
1492 htlc_minimum_msat: 0,
1493 htlc_maximum_msat: OptionalField::Absent,
1495 fee_proportional_millionths: 0,
1496 excess_data: Vec::new()
1498 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
1499 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1500 short_channel_id: 6,
1502 flags: 2, // to disable
1503 cltv_expiry_delta: 0,
1504 htlc_minimum_msat: 0,
1505 htlc_maximum_msat: OptionalField::Absent,
1507 fee_proportional_millionths: 0,
1508 excess_data: Vec::new()
1510 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
1511 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1512 short_channel_id: 7,
1514 flags: 2, // to disable
1515 cltv_expiry_delta: 0,
1516 htlc_minimum_msat: 0,
1517 htlc_maximum_msat: OptionalField::Absent,
1519 fee_proportional_millionths: 0,
1520 excess_data: Vec::new()
1523 // Check against amount_to_transfer_over_msat.
1524 // Set minimal HTLC of 200_000_000 msat.
1525 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
1526 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1527 short_channel_id: 2,
1530 cltv_expiry_delta: 0,
1531 htlc_minimum_msat: 200_000_000,
1532 htlc_maximum_msat: OptionalField::Absent,
1534 fee_proportional_millionths: 0,
1535 excess_data: Vec::new()
1538 // Second hop only allows to forward 199_999_999 at most, thus not allowing the first hop to
1540 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[1], UnsignedChannelUpdate {
1541 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1542 short_channel_id: 4,
1545 cltv_expiry_delta: 0,
1546 htlc_minimum_msat: 0,
1547 htlc_maximum_msat: OptionalField::Present(199_999_999),
1549 fee_proportional_millionths: 0,
1550 excess_data: Vec::new()
1553 // Not possible to send 199_999_999, because the minimum on channel=2 is 200_000_000.
1554 if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 199_999_999, 42, Arc::clone(&logger)) {
1555 assert_eq!(err, "Failed to find a path to the given destination");
1556 } else { panic!(); }
1558 // Lift the restriction on the first hop.
1559 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
1560 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1561 short_channel_id: 2,
1564 cltv_expiry_delta: 0,
1565 htlc_minimum_msat: 0,
1566 htlc_maximum_msat: OptionalField::Absent,
1568 fee_proportional_millionths: 0,
1569 excess_data: Vec::new()
1572 // A payment above the minimum should pass
1573 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 199_999_999, 42, Arc::clone(&logger)).unwrap();
1574 assert_eq!(route.paths[0].len(), 2);
1578 fn htlc_minimum_overpay_test() {
1579 let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
1580 let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
1582 // A route to node#2 via two paths.
1583 // One path allows transferring 35-40 sats, another one also allows 35-40 sats.
1584 // Thus, they can't send 60 without overpaying.
1585 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
1586 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1587 short_channel_id: 2,
1590 cltv_expiry_delta: 0,
1591 htlc_minimum_msat: 35_000,
1592 htlc_maximum_msat: OptionalField::Present(40_000),
1594 fee_proportional_millionths: 0,
1595 excess_data: Vec::new()
1597 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
1598 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1599 short_channel_id: 12,
1602 cltv_expiry_delta: 0,
1603 htlc_minimum_msat: 35_000,
1604 htlc_maximum_msat: OptionalField::Present(40_000),
1606 fee_proportional_millionths: 0,
1607 excess_data: Vec::new()
1611 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], UnsignedChannelUpdate {
1612 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1613 short_channel_id: 13,
1616 cltv_expiry_delta: 0,
1617 htlc_minimum_msat: 0,
1618 htlc_maximum_msat: OptionalField::Absent,
1620 fee_proportional_millionths: 0,
1621 excess_data: Vec::new()
1623 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[1], UnsignedChannelUpdate {
1624 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1625 short_channel_id: 4,
1628 cltv_expiry_delta: 0,
1629 htlc_minimum_msat: 0,
1630 htlc_maximum_msat: OptionalField::Absent,
1632 fee_proportional_millionths: 0,
1633 excess_data: Vec::new()
1636 // Disable other paths
1637 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
1638 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1639 short_channel_id: 1,
1641 flags: 2, // to disable
1642 cltv_expiry_delta: 0,
1643 htlc_minimum_msat: 0,
1644 htlc_maximum_msat: OptionalField::Absent,
1646 fee_proportional_millionths: 0,
1647 excess_data: Vec::new()
1650 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 60_000, 42, Arc::clone(&logger)).unwrap();
1651 // Overpay fees to hit htlc_minimum_msat.
1652 let overpaid_fees = route.paths[0][0].fee_msat + route.paths[1][0].fee_msat;
1653 // TODO: this could be better balanced to overpay 10k and not 15k.
1654 assert_eq!(overpaid_fees, 15_000);
1656 // Now, test that if there are 2 paths, a "cheaper" by fee path wouldn't be prioritized
1657 // while taking even more fee to match htlc_minimum_msat.
1658 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
1659 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1660 short_channel_id: 12,
1663 cltv_expiry_delta: 0,
1664 htlc_minimum_msat: 65_000,
1665 htlc_maximum_msat: OptionalField::Present(80_000),
1667 fee_proportional_millionths: 0,
1668 excess_data: Vec::new()
1670 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
1671 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1672 short_channel_id: 2,
1675 cltv_expiry_delta: 0,
1676 htlc_minimum_msat: 0,
1677 htlc_maximum_msat: OptionalField::Absent,
1679 fee_proportional_millionths: 0,
1680 excess_data: Vec::new()
1682 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[1], UnsignedChannelUpdate {
1683 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1684 short_channel_id: 4,
1687 cltv_expiry_delta: 0,
1688 htlc_minimum_msat: 0,
1689 htlc_maximum_msat: OptionalField::Absent,
1691 fee_proportional_millionths: 100_000,
1692 excess_data: Vec::new()
1695 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 60_000, 42, Arc::clone(&logger)).unwrap();
1696 // Fine to overpay for htlc_minimum_msat if it allows us to save fee.
1697 assert_eq!(route.paths.len(), 1);
1698 assert_eq!(route.paths[0][0].short_channel_id, 12);
1699 let fees = route.paths[0][0].fee_msat;
1700 assert_eq!(fees, 5_000);
1702 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 50_000, 42, Arc::clone(&logger)).unwrap();
1703 // Not fine to overpay for htlc_minimum_msat if it requires paying more than fee on
1704 // the other channel.
1705 assert_eq!(route.paths.len(), 1);
1706 assert_eq!(route.paths[0][0].short_channel_id, 2);
1707 let fees = route.paths[0][0].fee_msat;
1708 assert_eq!(fees, 5_000);
1712 fn disable_channels_test() {
1713 let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
1714 let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
1716 // // Disable channels 4 and 12 by flags=2
1717 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[1], UnsignedChannelUpdate {
1718 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1719 short_channel_id: 4,
1721 flags: 2, // to disable
1722 cltv_expiry_delta: 0,
1723 htlc_minimum_msat: 0,
1724 htlc_maximum_msat: OptionalField::Absent,
1726 fee_proportional_millionths: 0,
1727 excess_data: Vec::new()
1729 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
1730 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
1731 short_channel_id: 12,
1733 flags: 2, // to disable
1734 cltv_expiry_delta: 0,
1735 htlc_minimum_msat: 0,
1736 htlc_maximum_msat: OptionalField::Absent,
1738 fee_proportional_millionths: 0,
1739 excess_data: Vec::new()
1742 // If all the channels require some features we don't understand, route should fail
1743 if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 100, 42, Arc::clone(&logger)) {
1744 assert_eq!(err, "Failed to find a path to the given destination");
1745 } else { panic!(); }
1747 // If we specify a channel to node7, that overrides our local channel view and that gets used
1748 let our_chans = vec![channelmanager::ChannelDetails {
1749 channel_id: [0; 32],
1750 short_channel_id: Some(42),
1751 remote_network_id: nodes[7].clone(),
1752 counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
1753 channel_value_satoshis: 0,
1755 outbound_capacity_msat: 250_000_000,
1756 inbound_capacity_msat: 0,
1759 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
1760 assert_eq!(route.paths[0].len(), 2);
1762 assert_eq!(route.paths[0][0].pubkey, nodes[7]);
1763 assert_eq!(route.paths[0][0].short_channel_id, 42);
1764 assert_eq!(route.paths[0][0].fee_msat, 200);
1765 assert_eq!(route.paths[0][0].cltv_expiry_delta, (13 << 8) | 1);
1766 assert_eq!(route.paths[0][0].node_features.le_flags(), &vec![0b11]); // it should also override our view of their features
1767 assert_eq!(route.paths[0][0].channel_features.le_flags(), &Vec::<u8>::new()); // No feature flags will meet the relevant-to-channel conversion
1769 assert_eq!(route.paths[0][1].pubkey, nodes[2]);
1770 assert_eq!(route.paths[0][1].short_channel_id, 13);
1771 assert_eq!(route.paths[0][1].fee_msat, 100);
1772 assert_eq!(route.paths[0][1].cltv_expiry_delta, 42);
1773 assert_eq!(route.paths[0][1].node_features.le_flags(), &id_to_feature_flags(3));
1774 assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(13));
1778 fn disable_node_test() {
1779 let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
1780 let (_, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
1782 // Disable nodes 1, 2, and 8 by requiring unknown feature bits
1783 let mut unknown_features = NodeFeatures::known();
1784 unknown_features.set_required_unknown_bits();
1785 add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[0], unknown_features.clone(), 1);
1786 add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[1], unknown_features.clone(), 1);
1787 add_or_update_node(&net_graph_msg_handler, &secp_ctx, &privkeys[7], unknown_features.clone(), 1);
1789 // If all nodes require some features we don't understand, route should fail
1790 if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 100, 42, Arc::clone(&logger)) {
1791 assert_eq!(err, "Failed to find a path to the given destination");
1792 } else { panic!(); }
1794 // If we specify a channel to node7, that overrides our local channel view and that gets used
1795 let our_chans = vec![channelmanager::ChannelDetails {
1796 channel_id: [0; 32],
1797 short_channel_id: Some(42),
1798 remote_network_id: nodes[7].clone(),
1799 counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
1800 channel_value_satoshis: 0,
1802 outbound_capacity_msat: 250_000_000,
1803 inbound_capacity_msat: 0,
1806 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
1807 assert_eq!(route.paths[0].len(), 2);
1809 assert_eq!(route.paths[0][0].pubkey, nodes[7]);
1810 assert_eq!(route.paths[0][0].short_channel_id, 42);
1811 assert_eq!(route.paths[0][0].fee_msat, 200);
1812 assert_eq!(route.paths[0][0].cltv_expiry_delta, (13 << 8) | 1);
1813 assert_eq!(route.paths[0][0].node_features.le_flags(), &vec![0b11]); // it should also override our view of their features
1814 assert_eq!(route.paths[0][0].channel_features.le_flags(), &Vec::<u8>::new()); // No feature flags will meet the relevant-to-channel conversion
1816 assert_eq!(route.paths[0][1].pubkey, nodes[2]);
1817 assert_eq!(route.paths[0][1].short_channel_id, 13);
1818 assert_eq!(route.paths[0][1].fee_msat, 100);
1819 assert_eq!(route.paths[0][1].cltv_expiry_delta, 42);
1820 assert_eq!(route.paths[0][1].node_features.le_flags(), &id_to_feature_flags(3));
1821 assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(13));
1823 // Note that we don't test disabling node 3 and failing to route to it, as we (somewhat
1824 // naively) assume that the user checked the feature bits on the invoice, which override
1825 // the node_announcement.
1829 fn our_chans_test() {
1830 let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
1831 let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
1833 // Route to 1 via 2 and 3 because our channel to 1 is disabled
1834 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[0], None, &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
1835 assert_eq!(route.paths[0].len(), 3);
1837 assert_eq!(route.paths[0][0].pubkey, nodes[1]);
1838 assert_eq!(route.paths[0][0].short_channel_id, 2);
1839 assert_eq!(route.paths[0][0].fee_msat, 200);
1840 assert_eq!(route.paths[0][0].cltv_expiry_delta, (4 << 8) | 1);
1841 assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(2));
1842 assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(2));
1844 assert_eq!(route.paths[0][1].pubkey, nodes[2]);
1845 assert_eq!(route.paths[0][1].short_channel_id, 4);
1846 assert_eq!(route.paths[0][1].fee_msat, 100);
1847 assert_eq!(route.paths[0][1].cltv_expiry_delta, (3 << 8) | 2);
1848 assert_eq!(route.paths[0][1].node_features.le_flags(), &id_to_feature_flags(3));
1849 assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(4));
1851 assert_eq!(route.paths[0][2].pubkey, nodes[0]);
1852 assert_eq!(route.paths[0][2].short_channel_id, 3);
1853 assert_eq!(route.paths[0][2].fee_msat, 100);
1854 assert_eq!(route.paths[0][2].cltv_expiry_delta, 42);
1855 assert_eq!(route.paths[0][2].node_features.le_flags(), &id_to_feature_flags(1));
1856 assert_eq!(route.paths[0][2].channel_features.le_flags(), &id_to_feature_flags(3));
1858 // If we specify a channel to node7, that overrides our local channel view and that gets used
1859 let our_chans = vec![channelmanager::ChannelDetails {
1860 channel_id: [0; 32],
1861 short_channel_id: Some(42),
1862 remote_network_id: nodes[7].clone(),
1863 counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
1864 channel_value_satoshis: 0,
1866 outbound_capacity_msat: 250_000_000,
1867 inbound_capacity_msat: 0,
1870 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 100, 42, Arc::clone(&logger)).unwrap();
1871 assert_eq!(route.paths[0].len(), 2);
1873 assert_eq!(route.paths[0][0].pubkey, nodes[7]);
1874 assert_eq!(route.paths[0][0].short_channel_id, 42);
1875 assert_eq!(route.paths[0][0].fee_msat, 200);
1876 assert_eq!(route.paths[0][0].cltv_expiry_delta, (13 << 8) | 1);
1877 assert_eq!(route.paths[0][0].node_features.le_flags(), &vec![0b11]);
1878 assert_eq!(route.paths[0][0].channel_features.le_flags(), &Vec::<u8>::new()); // No feature flags will meet the relevant-to-channel conversion
1880 assert_eq!(route.paths[0][1].pubkey, nodes[2]);
1881 assert_eq!(route.paths[0][1].short_channel_id, 13);
1882 assert_eq!(route.paths[0][1].fee_msat, 100);
1883 assert_eq!(route.paths[0][1].cltv_expiry_delta, 42);
1884 assert_eq!(route.paths[0][1].node_features.le_flags(), &id_to_feature_flags(3));
1885 assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(13));
1888 fn last_hops(nodes: &Vec<PublicKey>) -> Vec<RouteHint> {
1889 let zero_fees = RoutingFees {
1891 proportional_millionths: 0,
1894 src_node_id: nodes[3].clone(),
1895 short_channel_id: 8,
1897 cltv_expiry_delta: (8 << 8) | 1,
1898 htlc_minimum_msat: None,
1899 htlc_maximum_msat: None,
1901 src_node_id: nodes[4].clone(),
1902 short_channel_id: 9,
1905 proportional_millionths: 0,
1907 cltv_expiry_delta: (9 << 8) | 1,
1908 htlc_minimum_msat: None,
1909 htlc_maximum_msat: None,
1911 src_node_id: nodes[5].clone(),
1912 short_channel_id: 10,
1914 cltv_expiry_delta: (10 << 8) | 1,
1915 htlc_minimum_msat: None,
1916 htlc_maximum_msat: None,
1921 fn last_hops_test() {
1922 let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
1923 let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
1925 // Simple test across 2, 3, 5, and 4 via a last_hop channel
1927 // First check that lst hop can't have its source as the payee.
1928 let invalid_last_hop = RouteHint {
1929 src_node_id: nodes[6],
1930 short_channel_id: 8,
1933 proportional_millionths: 0,
1935 cltv_expiry_delta: (8 << 8) | 1,
1936 htlc_minimum_msat: None,
1937 htlc_maximum_msat: None,
1940 let mut invalid_last_hops = last_hops(&nodes);
1941 invalid_last_hops.push(invalid_last_hop);
1943 if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, &invalid_last_hops.iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)) {
1944 assert_eq!(err, "Last hop cannot have a payee as a source.");
1945 } else { panic!(); }
1948 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, &last_hops(&nodes).iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)).unwrap();
1949 assert_eq!(route.paths[0].len(), 5);
1951 assert_eq!(route.paths[0][0].pubkey, nodes[1]);
1952 assert_eq!(route.paths[0][0].short_channel_id, 2);
1953 assert_eq!(route.paths[0][0].fee_msat, 100);
1954 assert_eq!(route.paths[0][0].cltv_expiry_delta, (4 << 8) | 1);
1955 assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(2));
1956 assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(2));
1958 assert_eq!(route.paths[0][1].pubkey, nodes[2]);
1959 assert_eq!(route.paths[0][1].short_channel_id, 4);
1960 assert_eq!(route.paths[0][1].fee_msat, 0);
1961 assert_eq!(route.paths[0][1].cltv_expiry_delta, (6 << 8) | 1);
1962 assert_eq!(route.paths[0][1].node_features.le_flags(), &id_to_feature_flags(3));
1963 assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(4));
1965 assert_eq!(route.paths[0][2].pubkey, nodes[4]);
1966 assert_eq!(route.paths[0][2].short_channel_id, 6);
1967 assert_eq!(route.paths[0][2].fee_msat, 0);
1968 assert_eq!(route.paths[0][2].cltv_expiry_delta, (11 << 8) | 1);
1969 assert_eq!(route.paths[0][2].node_features.le_flags(), &id_to_feature_flags(5));
1970 assert_eq!(route.paths[0][2].channel_features.le_flags(), &id_to_feature_flags(6));
1972 assert_eq!(route.paths[0][3].pubkey, nodes[3]);
1973 assert_eq!(route.paths[0][3].short_channel_id, 11);
1974 assert_eq!(route.paths[0][3].fee_msat, 0);
1975 assert_eq!(route.paths[0][3].cltv_expiry_delta, (8 << 8) | 1);
1976 // If we have a peer in the node map, we'll use their features here since we don't have
1977 // a way of figuring out their features from the invoice:
1978 assert_eq!(route.paths[0][3].node_features.le_flags(), &id_to_feature_flags(4));
1979 assert_eq!(route.paths[0][3].channel_features.le_flags(), &id_to_feature_flags(11));
1981 assert_eq!(route.paths[0][4].pubkey, nodes[6]);
1982 assert_eq!(route.paths[0][4].short_channel_id, 8);
1983 assert_eq!(route.paths[0][4].fee_msat, 100);
1984 assert_eq!(route.paths[0][4].cltv_expiry_delta, 42);
1985 assert_eq!(route.paths[0][4].node_features.le_flags(), &Vec::<u8>::new()); // We dont pass flags in from invoices yet
1986 assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
1990 fn our_chans_last_hop_connect_test() {
1991 let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
1992 let (_, our_id, _, nodes) = get_nodes(&secp_ctx);
1994 // Simple test with outbound channel to 4 to test that last_hops and first_hops connect
1995 let our_chans = vec![channelmanager::ChannelDetails {
1996 channel_id: [0; 32],
1997 short_channel_id: Some(42),
1998 remote_network_id: nodes[3].clone(),
1999 counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
2000 channel_value_satoshis: 0,
2002 outbound_capacity_msat: 250_000_000,
2003 inbound_capacity_msat: 0,
2006 let mut last_hops = last_hops(&nodes);
2007 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], Some(&our_chans.iter().collect::<Vec<_>>()), &last_hops.iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)).unwrap();
2008 assert_eq!(route.paths[0].len(), 2);
2010 assert_eq!(route.paths[0][0].pubkey, nodes[3]);
2011 assert_eq!(route.paths[0][0].short_channel_id, 42);
2012 assert_eq!(route.paths[0][0].fee_msat, 0);
2013 assert_eq!(route.paths[0][0].cltv_expiry_delta, (8 << 8) | 1);
2014 assert_eq!(route.paths[0][0].node_features.le_flags(), &vec![0b11]);
2015 assert_eq!(route.paths[0][0].channel_features.le_flags(), &Vec::<u8>::new()); // No feature flags will meet the relevant-to-channel conversion
2017 assert_eq!(route.paths[0][1].pubkey, nodes[6]);
2018 assert_eq!(route.paths[0][1].short_channel_id, 8);
2019 assert_eq!(route.paths[0][1].fee_msat, 100);
2020 assert_eq!(route.paths[0][1].cltv_expiry_delta, 42);
2021 assert_eq!(route.paths[0][1].node_features.le_flags(), &Vec::<u8>::new()); // We dont pass flags in from invoices yet
2022 assert_eq!(route.paths[0][1].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
2024 last_hops[0].fees.base_msat = 1000;
2026 // Revert to via 6 as the fee on 8 goes up
2027 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, &last_hops.iter().collect::<Vec<_>>(), 100, 42, Arc::clone(&logger)).unwrap();
2028 assert_eq!(route.paths[0].len(), 4);
2030 assert_eq!(route.paths[0][0].pubkey, nodes[1]);
2031 assert_eq!(route.paths[0][0].short_channel_id, 2);
2032 assert_eq!(route.paths[0][0].fee_msat, 200); // fee increased as its % of value transferred across node
2033 assert_eq!(route.paths[0][0].cltv_expiry_delta, (4 << 8) | 1);
2034 assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(2));
2035 assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(2));
2037 assert_eq!(route.paths[0][1].pubkey, nodes[2]);
2038 assert_eq!(route.paths[0][1].short_channel_id, 4);
2039 assert_eq!(route.paths[0][1].fee_msat, 100);
2040 assert_eq!(route.paths[0][1].cltv_expiry_delta, (7 << 8) | 1);
2041 assert_eq!(route.paths[0][1].node_features.le_flags(), &id_to_feature_flags(3));
2042 assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(4));
2044 assert_eq!(route.paths[0][2].pubkey, nodes[5]);
2045 assert_eq!(route.paths[0][2].short_channel_id, 7);
2046 assert_eq!(route.paths[0][2].fee_msat, 0);
2047 assert_eq!(route.paths[0][2].cltv_expiry_delta, (10 << 8) | 1);
2048 // If we have a peer in the node map, we'll use their features here since we don't have
2049 // a way of figuring out their features from the invoice:
2050 assert_eq!(route.paths[0][2].node_features.le_flags(), &id_to_feature_flags(6));
2051 assert_eq!(route.paths[0][2].channel_features.le_flags(), &id_to_feature_flags(7));
2053 assert_eq!(route.paths[0][3].pubkey, nodes[6]);
2054 assert_eq!(route.paths[0][3].short_channel_id, 10);
2055 assert_eq!(route.paths[0][3].fee_msat, 100);
2056 assert_eq!(route.paths[0][3].cltv_expiry_delta, 42);
2057 assert_eq!(route.paths[0][3].node_features.le_flags(), &Vec::<u8>::new()); // We dont pass flags in from invoices yet
2058 assert_eq!(route.paths[0][3].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
2060 // ...but still use 8 for larger payments as 6 has a variable feerate
2061 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[6], None, &last_hops.iter().collect::<Vec<_>>(), 2000, 42, Arc::clone(&logger)).unwrap();
2062 assert_eq!(route.paths[0].len(), 5);
2064 assert_eq!(route.paths[0][0].pubkey, nodes[1]);
2065 assert_eq!(route.paths[0][0].short_channel_id, 2);
2066 assert_eq!(route.paths[0][0].fee_msat, 3000);
2067 assert_eq!(route.paths[0][0].cltv_expiry_delta, (4 << 8) | 1);
2068 assert_eq!(route.paths[0][0].node_features.le_flags(), &id_to_feature_flags(2));
2069 assert_eq!(route.paths[0][0].channel_features.le_flags(), &id_to_feature_flags(2));
2071 assert_eq!(route.paths[0][1].pubkey, nodes[2]);
2072 assert_eq!(route.paths[0][1].short_channel_id, 4);
2073 assert_eq!(route.paths[0][1].fee_msat, 0);
2074 assert_eq!(route.paths[0][1].cltv_expiry_delta, (6 << 8) | 1);
2075 assert_eq!(route.paths[0][1].node_features.le_flags(), &id_to_feature_flags(3));
2076 assert_eq!(route.paths[0][1].channel_features.le_flags(), &id_to_feature_flags(4));
2078 assert_eq!(route.paths[0][2].pubkey, nodes[4]);
2079 assert_eq!(route.paths[0][2].short_channel_id, 6);
2080 assert_eq!(route.paths[0][2].fee_msat, 0);
2081 assert_eq!(route.paths[0][2].cltv_expiry_delta, (11 << 8) | 1);
2082 assert_eq!(route.paths[0][2].node_features.le_flags(), &id_to_feature_flags(5));
2083 assert_eq!(route.paths[0][2].channel_features.le_flags(), &id_to_feature_flags(6));
2085 assert_eq!(route.paths[0][3].pubkey, nodes[3]);
2086 assert_eq!(route.paths[0][3].short_channel_id, 11);
2087 assert_eq!(route.paths[0][3].fee_msat, 1000);
2088 assert_eq!(route.paths[0][3].cltv_expiry_delta, (8 << 8) | 1);
2089 // If we have a peer in the node map, we'll use their features here since we don't have
2090 // a way of figuring out their features from the invoice:
2091 assert_eq!(route.paths[0][3].node_features.le_flags(), &id_to_feature_flags(4));
2092 assert_eq!(route.paths[0][3].channel_features.le_flags(), &id_to_feature_flags(11));
2094 assert_eq!(route.paths[0][4].pubkey, nodes[6]);
2095 assert_eq!(route.paths[0][4].short_channel_id, 8);
2096 assert_eq!(route.paths[0][4].fee_msat, 2000);
2097 assert_eq!(route.paths[0][4].cltv_expiry_delta, 42);
2098 assert_eq!(route.paths[0][4].node_features.le_flags(), &Vec::<u8>::new()); // We dont pass flags in from invoices yet
2099 assert_eq!(route.paths[0][4].channel_features.le_flags(), &Vec::<u8>::new()); // We can't learn any flags from invoices, sadly
2103 fn unannounced_path_test() {
2104 // We should be able to send a payment to a destination without any help of a routing graph
2105 // if we have a channel with a common counterparty that appears in the first and last hop
2107 let source_node_id = PublicKey::from_secret_key(&Secp256k1::new(), &SecretKey::from_slice(&hex::decode(format!("{:02}", 41).repeat(32)).unwrap()[..]).unwrap());
2108 let middle_node_id = PublicKey::from_secret_key(&Secp256k1::new(), &SecretKey::from_slice(&hex::decode(format!("{:02}", 42).repeat(32)).unwrap()[..]).unwrap());
2109 let target_node_id = PublicKey::from_secret_key(&Secp256k1::new(), &SecretKey::from_slice(&hex::decode(format!("{:02}", 43).repeat(32)).unwrap()[..]).unwrap());
2111 // If we specify a channel to a middle hop, that overrides our local channel view and that gets used
2112 let last_hops = vec![RouteHint {
2113 src_node_id: middle_node_id,
2114 short_channel_id: 8,
2117 proportional_millionths: 0,
2119 cltv_expiry_delta: (8 << 8) | 1,
2120 htlc_minimum_msat: None,
2121 htlc_maximum_msat: None,
2123 let our_chans = vec![channelmanager::ChannelDetails {
2124 channel_id: [0; 32],
2125 short_channel_id: Some(42),
2126 remote_network_id: middle_node_id,
2127 counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
2128 channel_value_satoshis: 100000,
2130 outbound_capacity_msat: 100000,
2131 inbound_capacity_msat: 100000,
2134 let route = get_route(&source_node_id, &NetworkGraph::new(genesis_block(Network::Testnet).header.block_hash()), &target_node_id, Some(&our_chans.iter().collect::<Vec<_>>()), &last_hops.iter().collect::<Vec<_>>(), 100, 42, Arc::new(test_utils::TestLogger::new())).unwrap();
2136 assert_eq!(route.paths[0].len(), 2);
2138 assert_eq!(route.paths[0][0].pubkey, middle_node_id);
2139 assert_eq!(route.paths[0][0].short_channel_id, 42);
2140 assert_eq!(route.paths[0][0].fee_msat, 1000);
2141 assert_eq!(route.paths[0][0].cltv_expiry_delta, (8 << 8) | 1);
2142 assert_eq!(route.paths[0][0].node_features.le_flags(), &[0b11]);
2143 assert_eq!(route.paths[0][0].channel_features.le_flags(), &[0; 0]); // We can't learn any flags from invoices, sadly
2145 assert_eq!(route.paths[0][1].pubkey, target_node_id);
2146 assert_eq!(route.paths[0][1].short_channel_id, 8);
2147 assert_eq!(route.paths[0][1].fee_msat, 100);
2148 assert_eq!(route.paths[0][1].cltv_expiry_delta, 42);
2149 assert_eq!(route.paths[0][1].node_features.le_flags(), &[0; 0]); // We dont pass flags in from invoices yet
2150 assert_eq!(route.paths[0][1].channel_features.le_flags(), &[0; 0]); // We can't learn any flags from invoices, sadly
2154 fn available_amount_while_routing_test() {
2155 // Tests whether we choose the correct available channel amount while routing.
2157 let (secp_ctx, mut net_graph_msg_handler, chain_monitor, logger) = build_graph();
2158 let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
2160 // We will use a simple single-path route from
2161 // our node to node2 via node0: channels {1, 3}.
2163 // First disable all other paths.
2164 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
2165 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2166 short_channel_id: 2,
2169 cltv_expiry_delta: 0,
2170 htlc_minimum_msat: 0,
2171 htlc_maximum_msat: OptionalField::Present(100_000),
2173 fee_proportional_millionths: 0,
2174 excess_data: Vec::new()
2176 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
2177 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2178 short_channel_id: 12,
2181 cltv_expiry_delta: 0,
2182 htlc_minimum_msat: 0,
2183 htlc_maximum_msat: OptionalField::Present(100_000),
2185 fee_proportional_millionths: 0,
2186 excess_data: Vec::new()
2189 // Make the first channel (#1) very permissive,
2190 // and we will be testing all limits on the second channel.
2191 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
2192 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2193 short_channel_id: 1,
2196 cltv_expiry_delta: 0,
2197 htlc_minimum_msat: 0,
2198 htlc_maximum_msat: OptionalField::Present(1_000_000_000),
2200 fee_proportional_millionths: 0,
2201 excess_data: Vec::new()
2204 // First, let's see if routing works if we have absolutely no idea about the available amount.
2205 // In this case, it should be set to 250_000 sats.
2206 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
2207 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2208 short_channel_id: 3,
2211 cltv_expiry_delta: 0,
2212 htlc_minimum_msat: 0,
2213 htlc_maximum_msat: OptionalField::Absent,
2215 fee_proportional_millionths: 0,
2216 excess_data: Vec::new()
2220 // Attempt to route more than available results in a failure.
2221 if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 250_000_001, 42, Arc::clone(&logger)) {
2222 assert_eq!(err, "Failed to find a sufficient route to the given destination");
2223 } else { panic!(); }
2227 // Now, attempt to route an exact amount we have should be fine.
2228 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 250_000_000, 42, Arc::clone(&logger)).unwrap();
2229 assert_eq!(route.paths.len(), 1);
2230 let path = route.paths.last().unwrap();
2231 assert_eq!(path.len(), 2);
2232 assert_eq!(path.last().unwrap().pubkey, nodes[2]);
2233 assert_eq!(path.last().unwrap().fee_msat, 250_000_000);
2236 // Check that setting outbound_capacity_msat in first_hops limits the channels.
2237 // Disable channel #1 and use another first hop.
2238 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
2239 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2240 short_channel_id: 1,
2243 cltv_expiry_delta: 0,
2244 htlc_minimum_msat: 0,
2245 htlc_maximum_msat: OptionalField::Present(1_000_000_000),
2247 fee_proportional_millionths: 0,
2248 excess_data: Vec::new()
2251 // Now, limit the first_hop by the outbound_capacity_msat of 200_000 sats.
2252 let our_chans = vec![channelmanager::ChannelDetails {
2253 channel_id: [0; 32],
2254 short_channel_id: Some(42),
2255 remote_network_id: nodes[0].clone(),
2256 counterparty_features: InitFeatures::from_le_bytes(vec![0b11]),
2257 channel_value_satoshis: 0,
2259 outbound_capacity_msat: 200_000_000,
2260 inbound_capacity_msat: 0,
2265 // Attempt to route more than available results in a failure.
2266 if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 200_000_001, 42, Arc::clone(&logger)) {
2267 assert_eq!(err, "Failed to find a sufficient route to the given destination");
2268 } else { panic!(); }
2272 // Now, attempt to route an exact amount we have should be fine.
2273 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], Some(&our_chans.iter().collect::<Vec<_>>()), &Vec::new(), 200_000_000, 42, Arc::clone(&logger)).unwrap();
2274 assert_eq!(route.paths.len(), 1);
2275 let path = route.paths.last().unwrap();
2276 assert_eq!(path.len(), 2);
2277 assert_eq!(path.last().unwrap().pubkey, nodes[2]);
2278 assert_eq!(path.last().unwrap().fee_msat, 200_000_000);
2281 // Enable channel #1 back.
2282 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
2283 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2284 short_channel_id: 1,
2287 cltv_expiry_delta: 0,
2288 htlc_minimum_msat: 0,
2289 htlc_maximum_msat: OptionalField::Present(1_000_000_000),
2291 fee_proportional_millionths: 0,
2292 excess_data: Vec::new()
2296 // Now let's see if routing works if we know only htlc_maximum_msat.
2297 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
2298 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2299 short_channel_id: 3,
2302 cltv_expiry_delta: 0,
2303 htlc_minimum_msat: 0,
2304 htlc_maximum_msat: OptionalField::Present(15_000),
2306 fee_proportional_millionths: 0,
2307 excess_data: Vec::new()
2311 // Attempt to route more than available results in a failure.
2312 if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 15_001, 42, Arc::clone(&logger)) {
2313 assert_eq!(err, "Failed to find a sufficient route to the given destination");
2314 } else { panic!(); }
2318 // Now, attempt to route an exact amount we have should be fine.
2319 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 15_000, 42, Arc::clone(&logger)).unwrap();
2320 assert_eq!(route.paths.len(), 1);
2321 let path = route.paths.last().unwrap();
2322 assert_eq!(path.len(), 2);
2323 assert_eq!(path.last().unwrap().pubkey, nodes[2]);
2324 assert_eq!(path.last().unwrap().fee_msat, 15_000);
2327 // Now let's see if routing works if we know only capacity from the UTXO.
2329 // We can't change UTXO capacity on the fly, so we'll disable
2330 // the existing channel and add another one with the capacity we need.
2331 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
2332 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2333 short_channel_id: 3,
2336 cltv_expiry_delta: 0,
2337 htlc_minimum_msat: 0,
2338 htlc_maximum_msat: OptionalField::Absent,
2340 fee_proportional_millionths: 0,
2341 excess_data: Vec::new()
2344 let good_script = Builder::new().push_opcode(opcodes::all::OP_PUSHNUM_2)
2345 .push_slice(&PublicKey::from_secret_key(&secp_ctx, &privkeys[0]).serialize())
2346 .push_slice(&PublicKey::from_secret_key(&secp_ctx, &privkeys[2]).serialize())
2347 .push_opcode(opcodes::all::OP_PUSHNUM_2)
2348 .push_opcode(opcodes::all::OP_CHECKMULTISIG).into_script().to_v0_p2wsh();
2350 *chain_monitor.utxo_ret.lock().unwrap() = Ok(TxOut { value: 15, script_pubkey: good_script.clone() });
2351 net_graph_msg_handler.add_chain_access(Some(chain_monitor));
2353 add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], &privkeys[2], ChannelFeatures::from_le_bytes(id_to_feature_flags(3)), 333);
2354 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
2355 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2356 short_channel_id: 333,
2359 cltv_expiry_delta: (3 << 8) | 1,
2360 htlc_minimum_msat: 0,
2361 htlc_maximum_msat: OptionalField::Absent,
2363 fee_proportional_millionths: 0,
2364 excess_data: Vec::new()
2366 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
2367 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2368 short_channel_id: 333,
2371 cltv_expiry_delta: (3 << 8) | 2,
2372 htlc_minimum_msat: 0,
2373 htlc_maximum_msat: OptionalField::Absent,
2375 fee_proportional_millionths: 0,
2376 excess_data: Vec::new()
2380 // Attempt to route more than available results in a failure.
2381 if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 15_001, 42, Arc::clone(&logger)) {
2382 assert_eq!(err, "Failed to find a sufficient route to the given destination");
2383 } else { panic!(); }
2387 // Now, attempt to route an exact amount we have should be fine.
2388 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 15_000, 42, Arc::clone(&logger)).unwrap();
2389 assert_eq!(route.paths.len(), 1);
2390 let path = route.paths.last().unwrap();
2391 assert_eq!(path.len(), 2);
2392 assert_eq!(path.last().unwrap().pubkey, nodes[2]);
2393 assert_eq!(path.last().unwrap().fee_msat, 15_000);
2396 // Now let's see if routing chooses htlc_maximum_msat over UTXO capacity.
2397 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
2398 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2399 short_channel_id: 333,
2402 cltv_expiry_delta: 0,
2403 htlc_minimum_msat: 0,
2404 htlc_maximum_msat: OptionalField::Present(10_000),
2406 fee_proportional_millionths: 0,
2407 excess_data: Vec::new()
2411 // Attempt to route more than available results in a failure.
2412 if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 10_001, 42, Arc::clone(&logger)) {
2413 assert_eq!(err, "Failed to find a sufficient route to the given destination");
2414 } else { panic!(); }
2418 // Now, attempt to route an exact amount we have should be fine.
2419 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 10_000, 42, Arc::clone(&logger)).unwrap();
2420 assert_eq!(route.paths.len(), 1);
2421 let path = route.paths.last().unwrap();
2422 assert_eq!(path.len(), 2);
2423 assert_eq!(path.last().unwrap().pubkey, nodes[2]);
2424 assert_eq!(path.last().unwrap().fee_msat, 10_000);
2429 fn available_liquidity_last_hop_test() {
2430 // Check that available liquidity properly limits the path even when only
2431 // one of the latter hops is limited.
2432 let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
2433 let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
2435 // Path via {node7, node2, node4} is channels {12, 13, 6, 11}.
2436 // {12, 13, 11} have the capacities of 100, {6} has a capacity of 50.
2437 // Total capacity: 50 sats.
2439 // Disable other potential paths.
2440 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
2441 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2442 short_channel_id: 2,
2445 cltv_expiry_delta: 0,
2446 htlc_minimum_msat: 0,
2447 htlc_maximum_msat: OptionalField::Present(100_000),
2449 fee_proportional_millionths: 0,
2450 excess_data: Vec::new()
2452 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
2453 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2454 short_channel_id: 7,
2457 cltv_expiry_delta: 0,
2458 htlc_minimum_msat: 0,
2459 htlc_maximum_msat: OptionalField::Present(100_000),
2461 fee_proportional_millionths: 0,
2462 excess_data: Vec::new()
2467 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
2468 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2469 short_channel_id: 12,
2472 cltv_expiry_delta: 0,
2473 htlc_minimum_msat: 0,
2474 htlc_maximum_msat: OptionalField::Present(100_000),
2476 fee_proportional_millionths: 0,
2477 excess_data: Vec::new()
2479 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], UnsignedChannelUpdate {
2480 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2481 short_channel_id: 13,
2484 cltv_expiry_delta: 0,
2485 htlc_minimum_msat: 0,
2486 htlc_maximum_msat: OptionalField::Present(100_000),
2488 fee_proportional_millionths: 0,
2489 excess_data: Vec::new()
2492 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
2493 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2494 short_channel_id: 6,
2497 cltv_expiry_delta: 0,
2498 htlc_minimum_msat: 0,
2499 htlc_maximum_msat: OptionalField::Present(50_000),
2501 fee_proportional_millionths: 0,
2502 excess_data: Vec::new()
2504 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], UnsignedChannelUpdate {
2505 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2506 short_channel_id: 11,
2509 cltv_expiry_delta: 0,
2510 htlc_minimum_msat: 0,
2511 htlc_maximum_msat: OptionalField::Present(100_000),
2513 fee_proportional_millionths: 0,
2514 excess_data: Vec::new()
2517 // Attempt to route more than available results in a failure.
2518 if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 60_000, 42, Arc::clone(&logger)) {
2519 assert_eq!(err, "Failed to find a sufficient route to the given destination");
2520 } else { panic!(); }
2524 // Now, attempt to route 49 sats (just a bit below the capacity).
2525 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 49_000, 42, Arc::clone(&logger)).unwrap();
2526 assert_eq!(route.paths.len(), 1);
2527 let mut total_amount_paid_msat = 0;
2528 for path in &route.paths {
2529 assert_eq!(path.len(), 4);
2530 assert_eq!(path.last().unwrap().pubkey, nodes[3]);
2531 total_amount_paid_msat += path.last().unwrap().fee_msat;
2533 assert_eq!(total_amount_paid_msat, 49_000);
2537 // Attempt to route an exact amount is also fine
2538 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 50_000, 42, Arc::clone(&logger)).unwrap();
2539 assert_eq!(route.paths.len(), 1);
2540 let mut total_amount_paid_msat = 0;
2541 for path in &route.paths {
2542 assert_eq!(path.len(), 4);
2543 assert_eq!(path.last().unwrap().pubkey, nodes[3]);
2544 total_amount_paid_msat += path.last().unwrap().fee_msat;
2546 assert_eq!(total_amount_paid_msat, 50_000);
2551 fn ignore_fee_first_hop_test() {
2552 let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
2553 let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
2555 // Path via node0 is channels {1, 3}. Limit them to 100 and 50 sats (total limit 50).
2556 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
2557 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2558 short_channel_id: 1,
2561 cltv_expiry_delta: 0,
2562 htlc_minimum_msat: 0,
2563 htlc_maximum_msat: OptionalField::Present(100_000),
2564 fee_base_msat: 1_000_000,
2565 fee_proportional_millionths: 0,
2566 excess_data: Vec::new()
2568 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
2569 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2570 short_channel_id: 3,
2573 cltv_expiry_delta: 0,
2574 htlc_minimum_msat: 0,
2575 htlc_maximum_msat: OptionalField::Present(50_000),
2577 fee_proportional_millionths: 0,
2578 excess_data: Vec::new()
2582 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 50_000, 42, Arc::clone(&logger)).unwrap();
2583 assert_eq!(route.paths.len(), 1);
2584 let mut total_amount_paid_msat = 0;
2585 for path in &route.paths {
2586 assert_eq!(path.len(), 2);
2587 assert_eq!(path.last().unwrap().pubkey, nodes[2]);
2588 total_amount_paid_msat += path.last().unwrap().fee_msat;
2590 assert_eq!(total_amount_paid_msat, 50_000);
2595 fn simple_mpp_route_test() {
2596 let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
2597 let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
2599 // We need a route consisting of 3 paths:
2600 // From our node to node2 via node0, node7, node1 (three paths one hop each).
2601 // To achieve this, the amount being transferred should be around
2602 // the total capacity of these 3 paths.
2604 // First, we set limits on these (previously unlimited) channels.
2605 // Their aggregate capacity will be 50 + 60 + 180 = 290 sats.
2607 // Path via node0 is channels {1, 3}. Limit them to 100 and 50 sats (total limit 50).
2608 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
2609 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2610 short_channel_id: 1,
2613 cltv_expiry_delta: 0,
2614 htlc_minimum_msat: 0,
2615 htlc_maximum_msat: OptionalField::Present(100_000),
2617 fee_proportional_millionths: 0,
2618 excess_data: Vec::new()
2620 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
2621 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2622 short_channel_id: 3,
2625 cltv_expiry_delta: 0,
2626 htlc_minimum_msat: 0,
2627 htlc_maximum_msat: OptionalField::Present(50_000),
2629 fee_proportional_millionths: 0,
2630 excess_data: Vec::new()
2633 // Path via node7 is channels {12, 13}. Limit them to 60 and 60 sats
2634 // (total limit 60).
2635 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
2636 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2637 short_channel_id: 12,
2640 cltv_expiry_delta: 0,
2641 htlc_minimum_msat: 0,
2642 htlc_maximum_msat: OptionalField::Present(60_000),
2644 fee_proportional_millionths: 0,
2645 excess_data: Vec::new()
2647 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], UnsignedChannelUpdate {
2648 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2649 short_channel_id: 13,
2652 cltv_expiry_delta: 0,
2653 htlc_minimum_msat: 0,
2654 htlc_maximum_msat: OptionalField::Present(60_000),
2656 fee_proportional_millionths: 0,
2657 excess_data: Vec::new()
2660 // Path via node1 is channels {2, 4}. Limit them to 200 and 180 sats
2661 // (total capacity 180 sats).
2662 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
2663 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2664 short_channel_id: 2,
2667 cltv_expiry_delta: 0,
2668 htlc_minimum_msat: 0,
2669 htlc_maximum_msat: OptionalField::Present(200_000),
2671 fee_proportional_millionths: 0,
2672 excess_data: Vec::new()
2674 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[1], UnsignedChannelUpdate {
2675 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2676 short_channel_id: 4,
2679 cltv_expiry_delta: 0,
2680 htlc_minimum_msat: 0,
2681 htlc_maximum_msat: OptionalField::Present(180_000),
2683 fee_proportional_millionths: 0,
2684 excess_data: Vec::new()
2688 // Attempt to route more than available results in a failure.
2689 if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 300_000, 42, Arc::clone(&logger)) {
2690 assert_eq!(err, "Failed to find a sufficient route to the given destination");
2691 } else { panic!(); }
2695 // Now, attempt to route 250 sats (just a bit below the capacity).
2696 // Our algorithm should provide us with these 3 paths.
2697 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 250_000, 42, Arc::clone(&logger)).unwrap();
2698 assert_eq!(route.paths.len(), 3);
2699 let mut total_amount_paid_msat = 0;
2700 for path in &route.paths {
2701 assert_eq!(path.len(), 2);
2702 assert_eq!(path.last().unwrap().pubkey, nodes[2]);
2703 total_amount_paid_msat += path.last().unwrap().fee_msat;
2705 assert_eq!(total_amount_paid_msat, 250_000);
2709 // Attempt to route an exact amount is also fine
2710 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 290_000, 42, Arc::clone(&logger)).unwrap();
2711 assert_eq!(route.paths.len(), 3);
2712 let mut total_amount_paid_msat = 0;
2713 for path in &route.paths {
2714 assert_eq!(path.len(), 2);
2715 assert_eq!(path.last().unwrap().pubkey, nodes[2]);
2716 total_amount_paid_msat += path.last().unwrap().fee_msat;
2718 assert_eq!(total_amount_paid_msat, 290_000);
2723 fn long_mpp_route_test() {
2724 let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
2725 let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
2727 // We need a route consisting of 3 paths:
2728 // From our node to node3 via {node0, node2}, {node7, node2, node4} and {node7, node2}.
2729 // Note that these paths overlap (channels 5, 12, 13).
2730 // We will route 300 sats.
2731 // Each path will have 100 sats capacity, those channels which
2732 // are used twice will have 200 sats capacity.
2734 // Disable other potential paths.
2735 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
2736 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2737 short_channel_id: 2,
2740 cltv_expiry_delta: 0,
2741 htlc_minimum_msat: 0,
2742 htlc_maximum_msat: OptionalField::Present(100_000),
2744 fee_proportional_millionths: 0,
2745 excess_data: Vec::new()
2747 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
2748 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2749 short_channel_id: 7,
2752 cltv_expiry_delta: 0,
2753 htlc_minimum_msat: 0,
2754 htlc_maximum_msat: OptionalField::Present(100_000),
2756 fee_proportional_millionths: 0,
2757 excess_data: Vec::new()
2760 // Path via {node0, node2} is channels {1, 3, 5}.
2761 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
2762 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2763 short_channel_id: 1,
2766 cltv_expiry_delta: 0,
2767 htlc_minimum_msat: 0,
2768 htlc_maximum_msat: OptionalField::Present(100_000),
2770 fee_proportional_millionths: 0,
2771 excess_data: Vec::new()
2773 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
2774 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2775 short_channel_id: 3,
2778 cltv_expiry_delta: 0,
2779 htlc_minimum_msat: 0,
2780 htlc_maximum_msat: OptionalField::Present(100_000),
2782 fee_proportional_millionths: 0,
2783 excess_data: Vec::new()
2786 // Capacity of 200 sats because this channel will be used by 3rd path as well.
2787 add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], &privkeys[3], ChannelFeatures::from_le_bytes(id_to_feature_flags(5)), 5);
2788 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
2789 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2790 short_channel_id: 5,
2793 cltv_expiry_delta: 0,
2794 htlc_minimum_msat: 0,
2795 htlc_maximum_msat: OptionalField::Present(200_000),
2797 fee_proportional_millionths: 0,
2798 excess_data: Vec::new()
2801 // Path via {node7, node2, node4} is channels {12, 13, 6, 11}.
2802 // Add 100 sats to the capacities of {12, 13}, because these channels
2803 // are also used for 3rd path. 100 sats for the rest. Total capacity: 100 sats.
2804 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
2805 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2806 short_channel_id: 12,
2809 cltv_expiry_delta: 0,
2810 htlc_minimum_msat: 0,
2811 htlc_maximum_msat: OptionalField::Present(200_000),
2813 fee_proportional_millionths: 0,
2814 excess_data: Vec::new()
2816 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], UnsignedChannelUpdate {
2817 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2818 short_channel_id: 13,
2821 cltv_expiry_delta: 0,
2822 htlc_minimum_msat: 0,
2823 htlc_maximum_msat: OptionalField::Present(200_000),
2825 fee_proportional_millionths: 0,
2826 excess_data: Vec::new()
2829 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
2830 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2831 short_channel_id: 6,
2834 cltv_expiry_delta: 0,
2835 htlc_minimum_msat: 0,
2836 htlc_maximum_msat: OptionalField::Present(100_000),
2838 fee_proportional_millionths: 0,
2839 excess_data: Vec::new()
2841 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], UnsignedChannelUpdate {
2842 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2843 short_channel_id: 11,
2846 cltv_expiry_delta: 0,
2847 htlc_minimum_msat: 0,
2848 htlc_maximum_msat: OptionalField::Present(100_000),
2850 fee_proportional_millionths: 0,
2851 excess_data: Vec::new()
2854 // Path via {node7, node2} is channels {12, 13, 5}.
2855 // We already limited them to 200 sats (they are used twice for 100 sats).
2856 // Nothing to do here.
2859 // Attempt to route more than available results in a failure.
2860 if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 350_000, 42, Arc::clone(&logger)) {
2861 assert_eq!(err, "Failed to find a sufficient route to the given destination");
2862 } else { panic!(); }
2866 // Now, attempt to route 300 sats (exact amount we can route).
2867 // Our algorithm should provide us with these 3 paths, 100 sats each.
2868 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 300_000, 42, Arc::clone(&logger)).unwrap();
2869 assert_eq!(route.paths.len(), 3);
2871 let mut total_amount_paid_msat = 0;
2872 for path in &route.paths {
2873 assert_eq!(path.last().unwrap().pubkey, nodes[3]);
2874 total_amount_paid_msat += path.last().unwrap().fee_msat;
2876 assert_eq!(total_amount_paid_msat, 300_000);
2882 fn mpp_cheaper_route_test() {
2883 let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
2884 let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
2886 // This test checks that if we have two cheaper paths and one more expensive path,
2887 // so that liquidity-wise any 2 of 3 combination is sufficient,
2888 // two cheaper paths will be taken.
2889 // These paths have equal available liquidity.
2891 // We need a combination of 3 paths:
2892 // From our node to node3 via {node0, node2}, {node7, node2, node4} and {node7, node2}.
2893 // Note that these paths overlap (channels 5, 12, 13).
2894 // Each path will have 100 sats capacity, those channels which
2895 // are used twice will have 200 sats capacity.
2897 // Disable other potential paths.
2898 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
2899 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2900 short_channel_id: 2,
2903 cltv_expiry_delta: 0,
2904 htlc_minimum_msat: 0,
2905 htlc_maximum_msat: OptionalField::Present(100_000),
2907 fee_proportional_millionths: 0,
2908 excess_data: Vec::new()
2910 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
2911 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2912 short_channel_id: 7,
2915 cltv_expiry_delta: 0,
2916 htlc_minimum_msat: 0,
2917 htlc_maximum_msat: OptionalField::Present(100_000),
2919 fee_proportional_millionths: 0,
2920 excess_data: Vec::new()
2923 // Path via {node0, node2} is channels {1, 3, 5}.
2924 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
2925 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2926 short_channel_id: 1,
2929 cltv_expiry_delta: 0,
2930 htlc_minimum_msat: 0,
2931 htlc_maximum_msat: OptionalField::Present(100_000),
2933 fee_proportional_millionths: 0,
2934 excess_data: Vec::new()
2936 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
2937 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2938 short_channel_id: 3,
2941 cltv_expiry_delta: 0,
2942 htlc_minimum_msat: 0,
2943 htlc_maximum_msat: OptionalField::Present(100_000),
2945 fee_proportional_millionths: 0,
2946 excess_data: Vec::new()
2949 // Capacity of 200 sats because this channel will be used by 3rd path as well.
2950 add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], &privkeys[3], ChannelFeatures::from_le_bytes(id_to_feature_flags(5)), 5);
2951 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
2952 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2953 short_channel_id: 5,
2956 cltv_expiry_delta: 0,
2957 htlc_minimum_msat: 0,
2958 htlc_maximum_msat: OptionalField::Present(200_000),
2960 fee_proportional_millionths: 0,
2961 excess_data: Vec::new()
2964 // Path via {node7, node2, node4} is channels {12, 13, 6, 11}.
2965 // Add 100 sats to the capacities of {12, 13}, because these channels
2966 // are also used for 3rd path. 100 sats for the rest. Total capacity: 100 sats.
2967 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
2968 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2969 short_channel_id: 12,
2972 cltv_expiry_delta: 0,
2973 htlc_minimum_msat: 0,
2974 htlc_maximum_msat: OptionalField::Present(200_000),
2976 fee_proportional_millionths: 0,
2977 excess_data: Vec::new()
2979 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], UnsignedChannelUpdate {
2980 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2981 short_channel_id: 13,
2984 cltv_expiry_delta: 0,
2985 htlc_minimum_msat: 0,
2986 htlc_maximum_msat: OptionalField::Present(200_000),
2988 fee_proportional_millionths: 0,
2989 excess_data: Vec::new()
2992 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
2993 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
2994 short_channel_id: 6,
2997 cltv_expiry_delta: 0,
2998 htlc_minimum_msat: 0,
2999 htlc_maximum_msat: OptionalField::Present(100_000),
3000 fee_base_msat: 1_000,
3001 fee_proportional_millionths: 0,
3002 excess_data: Vec::new()
3004 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], UnsignedChannelUpdate {
3005 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
3006 short_channel_id: 11,
3009 cltv_expiry_delta: 0,
3010 htlc_minimum_msat: 0,
3011 htlc_maximum_msat: OptionalField::Present(100_000),
3013 fee_proportional_millionths: 0,
3014 excess_data: Vec::new()
3017 // Path via {node7, node2} is channels {12, 13, 5}.
3018 // We already limited them to 200 sats (they are used twice for 100 sats).
3019 // Nothing to do here.
3022 // Now, attempt to route 180 sats.
3023 // Our algorithm should provide us with these 2 paths.
3024 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 180_000, 42, Arc::clone(&logger)).unwrap();
3025 assert_eq!(route.paths.len(), 2);
3027 let mut total_value_transferred_msat = 0;
3028 let mut total_paid_msat = 0;
3029 for path in &route.paths {
3030 assert_eq!(path.last().unwrap().pubkey, nodes[3]);
3031 total_value_transferred_msat += path.last().unwrap().fee_msat;
3033 total_paid_msat += hop.fee_msat;
3036 // If we paid fee, this would be higher.
3037 assert_eq!(total_value_transferred_msat, 180_000);
3038 let total_fees_paid = total_paid_msat - total_value_transferred_msat;
3039 assert_eq!(total_fees_paid, 0);
3044 fn fees_on_mpp_route_test() {
3045 // This test makes sure that MPP algorithm properly takes into account
3046 // fees charged on the channels, by making the fees impactful:
3047 // if the fee is not properly accounted for, the behavior is different.
3048 let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
3049 let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
3051 // We need a route consisting of 2 paths:
3052 // From our node to node3 via {node0, node2} and {node7, node2, node4}.
3053 // We will route 200 sats, Each path will have 100 sats capacity.
3055 // This test is not particularly stable: e.g.,
3056 // there's a way to route via {node0, node2, node4}.
3057 // It works while pathfinding is deterministic, but can be broken otherwise.
3058 // It's fine to ignore this concern for now.
3060 // Disable other potential paths.
3061 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
3062 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
3063 short_channel_id: 2,
3066 cltv_expiry_delta: 0,
3067 htlc_minimum_msat: 0,
3068 htlc_maximum_msat: OptionalField::Present(100_000),
3070 fee_proportional_millionths: 0,
3071 excess_data: Vec::new()
3074 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
3075 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
3076 short_channel_id: 7,
3079 cltv_expiry_delta: 0,
3080 htlc_minimum_msat: 0,
3081 htlc_maximum_msat: OptionalField::Present(100_000),
3083 fee_proportional_millionths: 0,
3084 excess_data: Vec::new()
3087 // Path via {node0, node2} is channels {1, 3, 5}.
3088 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
3089 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
3090 short_channel_id: 1,
3093 cltv_expiry_delta: 0,
3094 htlc_minimum_msat: 0,
3095 htlc_maximum_msat: OptionalField::Present(100_000),
3097 fee_proportional_millionths: 0,
3098 excess_data: Vec::new()
3100 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
3101 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
3102 short_channel_id: 3,
3105 cltv_expiry_delta: 0,
3106 htlc_minimum_msat: 0,
3107 htlc_maximum_msat: OptionalField::Present(100_000),
3109 fee_proportional_millionths: 0,
3110 excess_data: Vec::new()
3113 add_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], &privkeys[3], ChannelFeatures::from_le_bytes(id_to_feature_flags(5)), 5);
3114 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
3115 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
3116 short_channel_id: 5,
3119 cltv_expiry_delta: 0,
3120 htlc_minimum_msat: 0,
3121 htlc_maximum_msat: OptionalField::Present(100_000),
3123 fee_proportional_millionths: 0,
3124 excess_data: Vec::new()
3127 // Path via {node7, node2, node4} is channels {12, 13, 6, 11}.
3128 // All channels should be 100 sats capacity. But for the fee experiment,
3129 // we'll add absolute fee of 150 sats paid for the use channel 6 (paid to node2 on channel 13).
3130 // Since channel 12 allows to deliver only 250 sats to channel 13, channel 13 can transfer only
3131 // 100 sats (and pay 150 sats in fees for the use of channel 6),
3132 // so no matter how large are other channels,
3133 // the whole path will be limited by 100 sats with just these 2 conditions:
3134 // - channel 12 capacity is 250 sats
3135 // - fee for channel 6 is 150 sats
3136 // Let's test this by enforcing these 2 conditions and removing other limits.
3137 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
3138 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
3139 short_channel_id: 12,
3142 cltv_expiry_delta: 0,
3143 htlc_minimum_msat: 0,
3144 htlc_maximum_msat: OptionalField::Present(250_000),
3146 fee_proportional_millionths: 0,
3147 excess_data: Vec::new()
3149 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], UnsignedChannelUpdate {
3150 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
3151 short_channel_id: 13,
3154 cltv_expiry_delta: 0,
3155 htlc_minimum_msat: 0,
3156 htlc_maximum_msat: OptionalField::Absent,
3158 fee_proportional_millionths: 0,
3159 excess_data: Vec::new()
3162 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[2], UnsignedChannelUpdate {
3163 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
3164 short_channel_id: 6,
3167 cltv_expiry_delta: 0,
3168 htlc_minimum_msat: 0,
3169 htlc_maximum_msat: OptionalField::Absent,
3170 fee_base_msat: 150_000,
3171 fee_proportional_millionths: 0,
3172 excess_data: Vec::new()
3174 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[4], UnsignedChannelUpdate {
3175 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
3176 short_channel_id: 11,
3179 cltv_expiry_delta: 0,
3180 htlc_minimum_msat: 0,
3181 htlc_maximum_msat: OptionalField::Absent,
3183 fee_proportional_millionths: 0,
3184 excess_data: Vec::new()
3188 // Attempt to route more than available results in a failure.
3189 if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 210_000, 42, Arc::clone(&logger)) {
3190 assert_eq!(err, "Failed to find a sufficient route to the given destination");
3191 } else { panic!(); }
3195 // Now, attempt to route 200 sats (exact amount we can route).
3196 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[3], None, &Vec::new(), 200_000, 42, Arc::clone(&logger)).unwrap();
3197 assert_eq!(route.paths.len(), 2);
3199 let mut total_amount_paid_msat = 0;
3200 for path in &route.paths {
3201 assert_eq!(path.last().unwrap().pubkey, nodes[3]);
3202 total_amount_paid_msat += path.last().unwrap().fee_msat;
3204 assert_eq!(total_amount_paid_msat, 200_000);
3210 fn drop_lowest_channel_mpp_route_test() {
3211 // This test checks that low-capacity channel is dropped when after
3212 // path finding we realize that we found more capacity than we need.
3213 let (secp_ctx, net_graph_msg_handler, _, logger) = build_graph();
3214 let (our_privkey, our_id, privkeys, nodes) = get_nodes(&secp_ctx);
3216 // We need a route consisting of 3 paths:
3217 // From our node to node2 via node0, node7, node1 (three paths one hop each).
3219 // The first and the second paths should be sufficient, but the third should be
3220 // cheaper, so that we select it but drop later.
3222 // First, we set limits on these (previously unlimited) channels.
3223 // Their aggregate capacity will be 50 + 60 + 20 = 130 sats.
3225 // Path via node0 is channels {1, 3}. Limit them to 100 and 50 sats (total limit 50);
3226 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
3227 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
3228 short_channel_id: 1,
3231 cltv_expiry_delta: 0,
3232 htlc_minimum_msat: 0,
3233 htlc_maximum_msat: OptionalField::Present(100_000),
3235 fee_proportional_millionths: 0,
3236 excess_data: Vec::new()
3238 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[0], UnsignedChannelUpdate {
3239 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
3240 short_channel_id: 3,
3243 cltv_expiry_delta: 0,
3244 htlc_minimum_msat: 0,
3245 htlc_maximum_msat: OptionalField::Present(50_000),
3247 fee_proportional_millionths: 0,
3248 excess_data: Vec::new()
3251 // Path via node7 is channels {12, 13}. Limit them to 60 and 60 sats (total limit 60);
3252 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
3253 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
3254 short_channel_id: 12,
3257 cltv_expiry_delta: 0,
3258 htlc_minimum_msat: 0,
3259 htlc_maximum_msat: OptionalField::Present(60_000),
3261 fee_proportional_millionths: 0,
3262 excess_data: Vec::new()
3264 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[7], UnsignedChannelUpdate {
3265 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
3266 short_channel_id: 13,
3269 cltv_expiry_delta: 0,
3270 htlc_minimum_msat: 0,
3271 htlc_maximum_msat: OptionalField::Present(60_000),
3273 fee_proportional_millionths: 0,
3274 excess_data: Vec::new()
3277 // Path via node1 is channels {2, 4}. Limit them to 20 and 20 sats (total capacity 20 sats).
3278 update_channel(&net_graph_msg_handler, &secp_ctx, &our_privkey, UnsignedChannelUpdate {
3279 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
3280 short_channel_id: 2,
3283 cltv_expiry_delta: 0,
3284 htlc_minimum_msat: 0,
3285 htlc_maximum_msat: OptionalField::Present(20_000),
3287 fee_proportional_millionths: 0,
3288 excess_data: Vec::new()
3290 update_channel(&net_graph_msg_handler, &secp_ctx, &privkeys[1], UnsignedChannelUpdate {
3291 chain_hash: genesis_block(Network::Testnet).header.block_hash(),
3292 short_channel_id: 4,
3295 cltv_expiry_delta: 0,
3296 htlc_minimum_msat: 0,
3297 htlc_maximum_msat: OptionalField::Present(20_000),
3299 fee_proportional_millionths: 0,
3300 excess_data: Vec::new()
3304 // Attempt to route more than available results in a failure.
3305 if let Err(LightningError{err, action: ErrorAction::IgnoreError}) = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 150_000, 42, Arc::clone(&logger)) {
3306 assert_eq!(err, "Failed to find a sufficient route to the given destination");
3307 } else { panic!(); }
3311 // Now, attempt to route 125 sats (just a bit below the capacity of 3 channels).
3312 // Our algorithm should provide us with these 3 paths.
3313 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 125_000, 42, Arc::clone(&logger)).unwrap();
3314 assert_eq!(route.paths.len(), 3);
3315 let mut total_amount_paid_msat = 0;
3316 for path in &route.paths {
3317 assert_eq!(path.len(), 2);
3318 assert_eq!(path.last().unwrap().pubkey, nodes[2]);
3319 total_amount_paid_msat += path.last().unwrap().fee_msat;
3321 assert_eq!(total_amount_paid_msat, 125_000);
3325 // Attempt to route without the last small cheap channel
3326 let route = get_route(&our_id, &net_graph_msg_handler.network_graph.read().unwrap(), &nodes[2], None, &Vec::new(), 90_000, 42, Arc::clone(&logger)).unwrap();
3327 assert_eq!(route.paths.len(), 2);
3328 let mut total_amount_paid_msat = 0;
3329 for path in &route.paths {
3330 assert_eq!(path.len(), 2);
3331 assert_eq!(path.last().unwrap().pubkey, nodes[2]);
3332 total_amount_paid_msat += path.last().unwrap().fee_msat;
3334 assert_eq!(total_amount_paid_msat, 90_000);