+// When an adversarial intermediary node observes a payment, it may be able to infer its
+// destination, if the remaining CLTV expiry delta exactly matches a feasible path in the network
+// graph. In order to improve privacy, this method obfuscates the CLTV expiry deltas along the
+// payment path by adding a randomized 'shadow route' offset to the final hop.
+fn add_random_cltv_offset(route: &mut Route, payment_params: &PaymentParameters,
+ network_graph: &ReadOnlyNetworkGraph, random_seed_bytes: &[u8; 32]
+) {
+ let network_channels = network_graph.channels();
+ let network_nodes = network_graph.nodes();
+
+ for path in route.paths.iter_mut() {
+ let mut shadow_ctlv_expiry_delta_offset: u32 = 0;
+
+ // Remember the last three nodes of the random walk and avoid looping back on them.
+ // Init with the last three nodes from the actual path, if possible.
+ let mut nodes_to_avoid: [NodeId; 3] = [NodeId::from_pubkey(&path.last().unwrap().pubkey),
+ NodeId::from_pubkey(&path.get(path.len().saturating_sub(2)).unwrap().pubkey),
+ NodeId::from_pubkey(&path.get(path.len().saturating_sub(3)).unwrap().pubkey)];
+
+ // Choose the last publicly known node as the starting point for the random walk.
+ let mut cur_hop: Option<NodeId> = None;
+ let mut path_nonce = [0u8; 12];
+ if let Some(starting_hop) = path.iter().rev()
+ .find(|h| network_nodes.contains_key(&NodeId::from_pubkey(&h.pubkey))) {
+ cur_hop = Some(NodeId::from_pubkey(&starting_hop.pubkey));
+ path_nonce.copy_from_slice(&cur_hop.unwrap().as_slice()[..12]);
+ }
+
+ // Init PRNG with the path-dependant nonce, which is static for private paths.
+ let mut prng = ChaCha20::new(random_seed_bytes, &path_nonce);
+ let mut random_path_bytes = [0u8; ::core::mem::size_of::<usize>()];
+
+ // Pick a random path length in [1 .. 3]
+ prng.process_in_place(&mut random_path_bytes);
+ let random_walk_length = usize::from_be_bytes(random_path_bytes).wrapping_rem(3).wrapping_add(1);
+
+ for random_hop in 0..random_walk_length {
+ // If we don't find a suitable offset in the public network graph, we default to
+ // MEDIAN_HOP_CLTV_EXPIRY_DELTA.
+ let mut random_hop_offset = MEDIAN_HOP_CLTV_EXPIRY_DELTA;
+
+ if let Some(cur_node_id) = cur_hop {
+ if let Some(cur_node) = network_nodes.get(&cur_node_id) {
+ // Randomly choose the next unvisited hop.
+ prng.process_in_place(&mut random_path_bytes);
+ if let Some(random_channel) = usize::from_be_bytes(random_path_bytes)
+ .checked_rem(cur_node.channels.len())
+ .and_then(|index| cur_node.channels.get(index))
+ .and_then(|id| network_channels.get(id)) {
+ random_channel.as_directed_from(&cur_node_id).map(|(dir_info, next_id)| {
+ if !nodes_to_avoid.iter().any(|x| x == next_id) {
+ nodes_to_avoid[random_hop] = *next_id;
+ dir_info.direction().map(|channel_update_info| {
+ random_hop_offset = channel_update_info.cltv_expiry_delta.into();
+ cur_hop = Some(*next_id);
+ });
+ }
+ });
+ }
+ }
+ }
+
+ shadow_ctlv_expiry_delta_offset = shadow_ctlv_expiry_delta_offset
+ .checked_add(random_hop_offset)
+ .unwrap_or(shadow_ctlv_expiry_delta_offset);
+ }
+
+ // Limit the total offset to reduce the worst-case locked liquidity timevalue
+ const MAX_SHADOW_CLTV_EXPIRY_DELTA_OFFSET: u32 = 3*144;
+ shadow_ctlv_expiry_delta_offset = cmp::min(shadow_ctlv_expiry_delta_offset, MAX_SHADOW_CLTV_EXPIRY_DELTA_OFFSET);
+
+ // Limit the offset so we never exceed the max_total_cltv_expiry_delta. To improve plausibility,
+ // we choose the limit to be the largest possible multiple of MEDIAN_HOP_CLTV_EXPIRY_DELTA.
+ let path_total_cltv_expiry_delta: u32 = path.iter().map(|h| h.cltv_expiry_delta).sum();
+ let mut max_path_offset = payment_params.max_total_cltv_expiry_delta - path_total_cltv_expiry_delta;
+ max_path_offset = cmp::max(
+ max_path_offset - (max_path_offset % MEDIAN_HOP_CLTV_EXPIRY_DELTA),
+ max_path_offset % MEDIAN_HOP_CLTV_EXPIRY_DELTA);
+ shadow_ctlv_expiry_delta_offset = cmp::min(shadow_ctlv_expiry_delta_offset, max_path_offset);
+
+ // Add 'shadow' CLTV offset to the final hop
+ if let Some(last_hop) = path.last_mut() {
+ last_hop.cltv_expiry_delta = last_hop.cltv_expiry_delta
+ .checked_add(shadow_ctlv_expiry_delta_offset).unwrap_or(last_hop.cltv_expiry_delta);
+ }
+ }
+}
+
+/// Construct a route from us (payer) to the target node (payee) via the given hops (which should
+/// exclude the payer, but include the payee). This may be useful, e.g., for probing the chosen path.
+///
+/// Re-uses logic from `find_route`, so the restrictions described there also apply here.
+pub fn build_route_from_hops<L: Deref>(
+ our_node_pubkey: &PublicKey, hops: &[PublicKey], route_params: &RouteParameters,
+ network_graph: &ReadOnlyNetworkGraph, logger: L, random_seed_bytes: &[u8; 32]
+) -> Result<Route, LightningError>
+where L::Target: Logger {
+ let mut route = build_route_from_hops_internal(
+ our_node_pubkey, hops, &route_params.payment_params, &network_graph,
+ route_params.final_value_msat, route_params.final_cltv_expiry_delta, logger, random_seed_bytes)?;
+ add_random_cltv_offset(&mut route, &route_params.payment_params, &network_graph, random_seed_bytes);
+ Ok(route)
+}
+
+fn build_route_from_hops_internal<L: Deref>(
+ our_node_pubkey: &PublicKey, hops: &[PublicKey], payment_params: &PaymentParameters,
+ network_graph: &ReadOnlyNetworkGraph, final_value_msat: u64, final_cltv_expiry_delta: u32,
+ logger: L, random_seed_bytes: &[u8; 32]
+) -> Result<Route, LightningError> where L::Target: Logger {
+
+ struct HopScorer {
+ our_node_id: NodeId,
+ hop_ids: [Option<NodeId>; MAX_PATH_LENGTH_ESTIMATE as usize],
+ }
+
+ impl Score for HopScorer {
+ fn channel_penalty_msat(&self, _short_channel_id: u64, source: &NodeId, target: &NodeId,
+ _usage: ChannelUsage) -> u64
+ {
+ let mut cur_id = self.our_node_id;
+ for i in 0..self.hop_ids.len() {
+ if let Some(next_id) = self.hop_ids[i] {
+ if cur_id == *source && next_id == *target {
+ return 0;
+ }
+ cur_id = next_id;
+ } else {
+ break;
+ }
+ }
+ u64::max_value()
+ }
+
+ fn payment_path_failed(&mut self, _path: &[&RouteHop], _short_channel_id: u64) {}
+
+ fn payment_path_successful(&mut self, _path: &[&RouteHop]) {}
+ }
+
+ impl<'a> Writeable for HopScorer {
+ #[inline]
+ fn write<W: Writer>(&self, _w: &mut W) -> Result<(), io::Error> {
+ unreachable!();
+ }
+ }
+
+ if hops.len() > MAX_PATH_LENGTH_ESTIMATE.into() {
+ return Err(LightningError{err: "Cannot build a route exceeding the maximum path length.".to_owned(), action: ErrorAction::IgnoreError});
+ }
+
+ let our_node_id = NodeId::from_pubkey(our_node_pubkey);
+ let mut hop_ids = [None; MAX_PATH_LENGTH_ESTIMATE as usize];
+ for i in 0..hops.len() {
+ hop_ids[i] = Some(NodeId::from_pubkey(&hops[i]));
+ }
+
+ let scorer = HopScorer { our_node_id, hop_ids };
+
+ get_route(our_node_pubkey, payment_params, network_graph, None, final_value_msat,
+ final_cltv_expiry_delta, logger, &scorer, random_seed_bytes)
+}
+