1use std::{cmp::Ordering, sync::Arc};
2
3use hopr_api::{
4 OffchainPublicKey,
5 graph::{
6 NetworkGraphTraverse, NetworkGraphView,
7 function::{BasicValueFn, EdgeValueFn},
8 traits::{
9 EdgeImmediateProtocolObservable, EdgeLinkObservable, EdgeObservableRead, EdgeProtocolObservable, ValueFn,
10 },
11 },
12 types::internal::errors::PathError,
13};
14
15use super::{
16 errors::{PathPlannerError, Result},
17 traits::{PathSelector, PathWithMetrics},
18};
19use crate::observer::{PathDirection, PhaseCounts, TransportEvent, TransportObserver};
20
21#[derive(Clone, Debug)]
26struct PathCostWithMetrics {
27 cost: f64,
28 total_latency_ms: Option<u32>,
29 min_probe_success_rate: Option<f64>,
30 min_ack_rate: Option<f64>,
31 fundable_tickets_floor: Option<u128>,
32}
33
34impl PartialOrd for PathCostWithMetrics {
35 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
36 self.cost.partial_cmp(&other.cost)
37 }
38}
39
40impl PartialEq for PathCostWithMetrics {
41 fn eq(&self, other: &Self) -> bool {
42 self.cost == other.cost
43 }
44}
45
46impl From<(PathCostWithMetrics, Vec<OffchainPublicKey>)> for PathWithMetrics {
47 fn from((metrics, path): (PathCostWithMetrics, Vec<OffchainPublicKey>)) -> Self {
48 PathWithMetrics {
49 path,
50 cost: metrics.cost,
51 total_latency_ms: metrics.total_latency_ms,
52 min_probe_success_rate: metrics.min_probe_success_rate,
53 min_ack_rate: metrics.min_ack_rate,
54 fundable_tickets_floor: metrics.fundable_tickets_floor,
55 }
56 }
57}
58
59fn opt_min<T: PartialOrd>(a: Option<T>, b: Option<T>) -> Option<T> {
61 match (a, b) {
62 (Some(x), Some(y)) => Some(if x <= y { x } else { y }),
63 (x, y) => x.or(y),
64 }
65}
66
67struct MetricsValueFn<W: EdgeObservableRead> {
74 inner: EdgeValueFn<f64, W>,
75 ticket_face_value: Option<hopr_api::graph::traits::Balance>,
81}
82
83impl<W> ValueFn for MetricsValueFn<W>
84where
85 W: EdgeObservableRead + Send + 'static,
86{
87 type Value = PathCostWithMetrics;
88 type Weight = W;
89
90 fn initial_value(&self) -> Self::Value {
91 PathCostWithMetrics {
92 cost: self.inner.initial_value(),
93 total_latency_ms: Some(0),
94 min_probe_success_rate: None,
95 min_ack_rate: None,
96 fundable_tickets_floor: None,
97 }
98 }
99
100 fn min_value(&self) -> Option<Self::Value> {
101 self.inner.min_value().map(|c| PathCostWithMetrics {
102 cost: c,
103 total_latency_ms: None,
104 min_probe_success_rate: None,
105 min_ack_rate: None,
106 fundable_tickets_floor: None,
107 })
108 }
109
110 fn into_value_fn(self) -> BasicValueFn<Self::Value, Self::Weight> {
111 let inner = self.inner.into_value_fn();
112 let ticket_face_value = self.ticket_face_value;
113 Arc::new(move |prev: PathCostWithMetrics, observed: &W, idx: usize| {
114 let cost = inner(prev.cost, observed, idx);
115
116 let edge_lat = observed
117 .immediate_qos()
118 .and_then(|m| m.average_latency())
119 .or_else(|| observed.intermediate_qos().and_then(|m| m.average_latency()));
120 let total_latency_ms = match (prev.total_latency_ms, edge_lat) {
121 (Some(acc), Some(lat)) => Some(((acc as u128 + lat.as_millis()).min(u32::MAX as u128)) as u32),
122 _ => None,
123 };
124
125 let edge_probe = observed
130 .immediate_qos()
131 .and_then(|m| m.average_probe_rate())
132 .into_iter()
133 .chain(observed.intermediate_qos().and_then(|m| m.average_probe_rate()))
134 .reduce(f64::min);
135 let min_probe_success_rate = opt_min(prev.min_probe_success_rate, edge_probe);
136
137 let edge_ack = observed.immediate_qos().and_then(|m| m.ack_rate());
138 let min_ack_rate = opt_min(prev.min_ack_rate, edge_ack);
139
140 let edge_tickets = observed
149 .intermediate_qos()
150 .and_then(|m| m.balance())
151 .zip(ticket_face_value)
152 .map(|(balance, face_value)| {
153 let tickets = if face_value.is_zero() {
154 hopr_api::graph::traits::Balance::zero()
155 } else {
156 balance / face_value
157 };
158 if tickets > hopr_api::graph::traits::Balance::from(u128::MAX) {
159 u128::MAX
160 } else {
161 tickets.low_u128()
162 }
163 });
164 let fundable_tickets_floor = opt_min(prev.fundable_tickets_floor, edge_tickets);
165
166 PathCostWithMetrics {
167 cost,
168 total_latency_ms,
169 min_probe_success_rate,
170 min_ack_rate,
171 fundable_tickets_floor,
172 }
173 })
174 }
175}
176
177pub fn prune_for_consistency(candidates: Vec<PathWithMetrics>, floor: usize, hops: usize) -> Vec<PathWithMetrics> {
193 if floor == 0 || candidates.len() <= floor {
195 return candidates;
196 }
197
198 let fully_measured =
199 |p: &PathWithMetrics| p.total_latency_ms.is_some() && (hops == 0 || p.fundable_tickets_floor.is_some());
200
201 let (mut populated, unpopulated): (Vec<_>, Vec<_>) = candidates.into_iter().partition(|p| fully_measured(p));
202
203 populated.sort_by_key(|p| p.total_latency_ms.unwrap_or(u32::MAX));
205
206 let target_populated = populated.len().min(floor);
211 let populated = take_relayer_diverse(populated, target_populated);
212 let remaining = floor - target_populated;
213
214 let mut result = populated;
215 result.extend(unpopulated.into_iter().take(remaining));
216
217 result
218}
219
220const MIDDLE_HOP_SHARE: usize = 3;
232
233fn take_relayer_diverse(sorted: Vec<PathWithMetrics>, n: usize) -> Vec<PathWithMetrics> {
244 if sorted.len() <= n {
245 return sorted;
246 }
247
248 let cap = n.div_ceil(MIDDLE_HOP_SHARE).max(1);
249 let mut seen: Vec<OffchainPublicKey> = Vec::with_capacity(n);
250 let mut per_relayer: std::collections::HashMap<OffchainPublicKey, usize> = Default::default();
251 let mut taken = vec![false; sorted.len()];
252 let mut count = 0;
253
254 let later_relayers = |p: &PathWithMetrics| {
256 p.path
257 .iter()
258 .skip(1)
259 .take(p.path.len().saturating_sub(2))
260 .copied()
261 .collect::<Vec<_>>()
262 };
263
264 let take = |i: usize,
265 p: &PathWithMetrics,
266 taken: &mut Vec<bool>,
267 per_relayer: &mut std::collections::HashMap<OffchainPublicKey, usize>| {
268 taken[i] = true;
269 for relayer in later_relayers(p) {
270 *per_relayer.entry(relayer).or_default() += 1;
271 }
272 };
273
274 for (i, p) in sorted.iter().enumerate() {
277 if count == n {
278 break;
279 }
280 let Some(first) = p.path.first() else { continue };
281 let under_cap = later_relayers(p)
282 .into_iter()
283 .all(|relayer| per_relayer.get(&relayer).copied().unwrap_or(0) < cap);
284 if !seen.contains(first) && under_cap {
285 seen.push(*first);
286 take(i, p, &mut taken, &mut per_relayer);
287 count += 1;
288 }
289 }
290
291 for (i, p) in sorted.iter().enumerate() {
293 if count == n {
294 break;
295 }
296 if taken[i] {
297 continue;
298 }
299 let under_cap = later_relayers(p)
300 .into_iter()
301 .all(|relayer| per_relayer.get(&relayer).copied().unwrap_or(0) < cap);
302 if under_cap {
303 if let Some(first) = p.path.first()
304 && !seen.contains(first)
305 {
306 seen.push(*first);
307 }
308 take(i, p, &mut taken, &mut per_relayer);
309 count += 1;
310 }
311 }
312
313 for (i, p) in sorted.iter().enumerate() {
317 if count == n {
318 break;
319 }
320 if taken[i] {
321 continue;
322 }
323 let Some(first) = p.path.first() else { continue };
324 if !seen.contains(first) {
325 seen.push(*first);
326 take(i, p, &mut taken, &mut per_relayer);
327 count += 1;
328 }
329 }
330
331 for slot in taken.iter_mut() {
333 if count == n {
334 break;
335 }
336 if !*slot {
337 *slot = true;
338 count += 1;
339 }
340 }
341
342 sorted
343 .into_iter()
344 .zip(taken)
345 .filter_map(|(p, keep)| keep.then_some(p))
346 .collect()
347}
348
349pub(crate) fn distinct_first_relayers(paths: &[PathWithMetrics]) -> usize {
356 paths
357 .iter()
358 .filter_map(|p| p.path.first())
359 .collect::<std::collections::HashSet<_>>()
360 .len()
361}
362
363fn compute_paths<G, W>(
370 graph: &G,
371 src: &OffchainPublicKey,
372 dest: &OffchainPublicKey,
373 length: std::num::NonZeroUsize,
374 take: usize,
375 value_fn: MetricsValueFn<W>,
376) -> (Vec<PathWithMetrics>, usize)
377where
378 G: NetworkGraphTraverse<NodeId = OffchainPublicKey, Observed = W>,
379 W: EdgeObservableRead + Send + 'static,
380{
381 let raw = graph.simple_paths(src, dest, length.get(), Some(take), value_fn);
382
383 let returned = raw.len();
384 let paths = raw
385 .into_iter()
386 .filter_map(|(path, _, metrics)| {
387 tracing::trace!(?path, cost = metrics.cost, "evaluating candidate path");
388 if metrics.cost > 0.0 {
389 let mut path = path;
390 path.push(*dest);
391 Some(PathWithMetrics::from((metrics, path)))
392 } else {
393 None
394 }
395 })
396 .collect();
397 (paths, returned)
398}
399
400struct ContinuedValueFn<V, W> {
407 value_fn: BasicValueFn<V, W>,
408 initial: V,
409 min: Option<V>,
410 offset: usize,
411}
412
413impl<V, W> ValueFn for ContinuedValueFn<V, W>
414where
415 V: Clone + PartialOrd + Send + Sync + 'static,
416 W: EdgeObservableRead + Send + 'static,
417{
418 type Value = V;
419 type Weight = W;
420
421 fn initial_value(&self) -> Self::Value {
422 self.initial.clone()
423 }
424
425 fn min_value(&self) -> Option<Self::Value> {
426 self.min.clone()
427 }
428
429 fn into_value_fn(self) -> BasicValueFn<Self::Value, Self::Weight> {
430 let (value_fn, offset) = (self.value_fn, self.offset);
431 Arc::new(move |value, observed, index| value_fn(value, observed, index + offset))
432 }
433}
434
435const SHARE_SEARCHES: u32 = 4;
440
441fn search_share<P>(share: usize, unusable: impl Fn(&P) -> bool, mut search: impl FnMut(usize) -> Vec<P>) -> Vec<P> {
454 let mut limit = share;
455 let mut searches = 1;
456 loop {
457 let found = search(limit);
458 let usable = found.iter().filter(|path| !unusable(path)).count();
459 if found.len() < limit || usable >= share {
460 return found;
461 }
462 if searches == SHARE_SEARCHES {
463 tracing::debug!(share, limit, usable, "share left short: most continuations unusable");
464 return found;
465 }
466 searches += 1;
467 limit = limit.saturating_mul(2);
468 }
469}
470
471fn compute_paths_spread<G, W>(
487 graph: &G,
488 src: &OffchainPublicKey,
489 dest: &OffchainPublicKey,
490 length: std::num::NonZeroUsize,
491 take: usize,
492 value_fn: MetricsValueFn<W>,
493) -> (Vec<PathWithMetrics>, usize)
494where
495 G: NetworkGraphTraverse<NodeId = OffchainPublicKey, Observed = W>,
496 W: EdgeObservableRead + Send + 'static,
497{
498 if length.get() < 2 {
500 return compute_paths(graph, src, dest, length, take, value_fn);
501 }
502
503 let initial = value_fn.initial_value();
504 let min = value_fn.min_value();
505 let value_fn = value_fn.into_value_fn();
506
507 let firsts = graph
510 .simple_paths_from(
511 src,
512 1,
513 None,
514 ContinuedValueFn {
515 value_fn: value_fn.clone(),
516 initial,
517 min: min.clone(),
518 offset: 0,
519 },
520 )
521 .into_iter()
522 .filter_map(|(nodes, _, after_first)| match nodes.as_slice() {
523 [first] if first != dest && first != src => Some((*first, after_first)),
524 _ => None,
525 })
526 .collect::<Vec<_>>();
527
528 if firsts.is_empty() {
529 return (Vec::new(), 0);
530 }
531
532 let share = take.div_ceil(firsts.len()).max(1);
533 let mut returned = 0;
534 let mut per_first = firsts
535 .into_iter()
536 .map(|(first, after_first)| {
537 let continuations = |limit| {
538 let found = graph.simple_paths(
539 &first,
540 dest,
541 length.get() - 1,
542 Some(limit),
543 ContinuedValueFn {
544 value_fn: value_fn.clone(),
545 initial: after_first.clone(),
546 min: min.clone(),
547 offset: 1,
548 },
549 );
550 returned += found.len();
551 found
552 };
553 let unusable = |(rest, _, metrics): &(Vec<OffchainPublicKey>, _, PathCostWithMetrics)| {
556 metrics.cost <= 0.0 || rest.contains(src)
557 };
558 search_share(share, unusable, continuations)
559 .into_iter()
560 .filter_map(move |continuation| {
561 if unusable(&continuation) {
562 return None;
563 }
564 let (rest, _, metrics) = continuation;
565 let mut path = Vec::with_capacity(rest.len() + 2);
566 path.push(first);
567 path.extend(rest);
568 path.push(*dest);
569 tracing::trace!(?path, cost = metrics.cost, "evaluating candidate path");
570 Some(PathWithMetrics::from((metrics, path)))
571 })
572 .take(share)
573 .collect::<Vec<_>>()
574 .into_iter()
575 })
576 .collect::<Vec<_>>();
577
578 let found = per_first.iter().map(|paths| paths.len()).sum::<usize>();
580 let mut spread = Vec::with_capacity(take.min(found));
581 while spread.len() < take {
582 let before = spread.len();
583 for paths in per_first.iter_mut() {
584 if spread.len() == take {
585 break;
586 }
587 spread.extend(paths.next());
588 }
589 if spread.len() == before {
590 break;
591 }
592 }
593 (spread, returned)
594}
595
596#[derive(Clone)]
608pub struct HoprGraphPathSelector<G> {
609 me: OffchainPublicKey,
610 graph: G,
611 max_paths: usize,
612 edge_penalty: f64,
613 min_ack_rate: f64,
614 anonymity_floor: usize,
615 observer: Option<TransportObserver>,
616}
617
618impl<G> HoprGraphPathSelector<G>
619where
620 G: NetworkGraphTraverse<NodeId = OffchainPublicKey>
621 + NetworkGraphView<NodeId = OffchainPublicKey>
622 + Clone
623 + Send
624 + Sync
625 + 'static,
626 <G as NetworkGraphTraverse>::Observed: EdgeObservableRead + Send + 'static,
627{
628 pub fn new(
637 me: OffchainPublicKey,
638 graph: G,
639 max_paths: usize,
640 edge_penalty: f64,
641 min_ack_rate: f64,
642 anonymity_floor: usize,
643 ) -> Self {
644 Self {
645 me,
646 graph,
647 max_paths,
648 edge_penalty,
649 min_ack_rate,
650 anonymity_floor,
651 observer: None,
652 }
653 }
654
655 pub fn with_observer(mut self, observer: TransportObserver) -> Self {
657 self.observer = Some(observer);
658 self
659 }
660
661 fn compute_extended_forward_paths(
671 &self,
672 src: &OffchainPublicKey,
673 dest: &OffchainPublicKey,
674 shorter_length: std::num::NonZeroUsize,
675 take: usize,
676 existing: &[PathWithMetrics],
677 ticket_face_value: Option<hopr_api::graph::traits::Balance>,
679 ) -> (Vec<PathWithMetrics>, usize) {
680 let finished_length = shorter_length.saturating_add(1);
687 let value_fn = MetricsValueFn {
688 inner: EdgeValueFn::forward_without_self_loopback(
689 finished_length,
690 self.edge_penalty,
691 self.min_ack_rate,
692 ticket_face_value,
693 ),
694 ticket_face_value,
695 };
696 let raw = self
697 .graph
698 .simple_paths_from(src, shorter_length.get(), Some(take), value_fn);
699
700 let returned = raw.len();
701 let paths = raw
702 .into_iter()
703 .filter_map(|(path, _, metrics)| {
704 if metrics.cost <= 0.0 {
705 return None;
706 }
707
708 if path.contains(dest) {
712 return None;
713 }
714 let mut candidate = path;
715 candidate.push(*dest);
716
717 if let [.., relay, _] = candidate.as_slice()
722 && self.graph.edge(relay, dest).and_then(|obs| obs.score()) == Some(0.0)
723 {
724 return None;
725 }
726
727 if existing.iter().any(|pwm| pwm.path == candidate) {
728 return None;
729 }
730
731 tracing::trace!(?candidate, cost = metrics.cost, "extended forward path candidate");
732 Some(PathWithMetrics::from((metrics, candidate)))
733 })
734 .take(take)
735 .collect();
736 (paths, returned)
737 }
738}
739
740impl<G> PathSelector for HoprGraphPathSelector<G>
741where
742 G: NetworkGraphTraverse<NodeId = OffchainPublicKey>
743 + NetworkGraphView<NodeId = OffchainPublicKey>
744 + Clone
745 + Send
746 + Sync
747 + 'static,
748 <G as NetworkGraphTraverse>::Observed: EdgeObservableRead + Send + 'static,
749{
750 #[tracing::instrument(
762 name = "selector.select_paths", level = "trace", skip_all,
763 fields(src = %src, dest = %dest, hops = hops, direction = if src == self.me { "forward" } else { "return" }),
764 ret, err(level = "trace")
765 )]
766 fn select_path(
767 &self,
768 src: OffchainPublicKey,
769 dest: OffchainPublicKey,
770 hops: usize,
771 ) -> Result<Vec<PathWithMetrics>> {
772 let direction = if src == self.me { "forward" } else { "return" };
773 tracing::trace!(%src, %dest, hops, direction, "computing paths from graph");
774
775 let length = std::num::NonZeroUsize::new(hops + 1)
776 .expect("can never fail, it is physically at least 1 after the addition");
777
778 let ticket_face_value = self.graph.ticket_face_value();
782
783 let phase1;
784 let mut phase2 = None;
785 let paths = if src == self.me {
786 let (mut found, returned) = compute_paths_spread(
788 &self.graph,
789 &src,
790 &dest,
791 length,
792 self.max_paths,
793 MetricsValueFn {
794 inner: EdgeValueFn::forward(length, self.edge_penalty, self.min_ack_rate, ticket_face_value),
795 ticket_face_value,
796 },
797 );
798 phase1 = PhaseCounts {
799 returned: returned as u64,
800 eligible: found.len() as u64,
801 };
802 tracing::trace!(
803 direction,
804 phase = 1,
805 count = found.len(),
806 "[forward] phase 1 candidates"
807 );
808
809 if found.len() < self.max_paths
812 && let Some(shorter) = std::num::NonZeroUsize::new(length.get() - 1)
813 {
814 let remaining = self.max_paths - found.len();
815 let (extended, returned) =
816 self.compute_extended_forward_paths(&src, &dest, shorter, remaining, &found, ticket_face_value);
817 phase2 = Some(PhaseCounts {
818 returned: returned as u64,
819 eligible: extended.len() as u64,
820 });
821 tracing::trace!(
822 direction,
823 phase = 2,
824 count = extended.len(),
825 "[forward] phase 2 extended candidates"
826 );
827 found.extend(extended);
828 }
829
830 found
831 } else {
832 let (found, returned) = compute_paths_spread(
833 &self.graph,
834 &src,
835 &dest,
836 length,
837 self.max_paths,
838 MetricsValueFn {
839 inner: EdgeValueFn::returning(length, self.edge_penalty, self.min_ack_rate, ticket_face_value),
840 ticket_face_value,
841 },
842 );
843 phase1 = PhaseCounts {
844 returned: returned as u64,
845 eligible: found.len() as u64,
846 };
847 tracing::trace!(direction, count = found.len(), "[return] candidates");
848 found
849 };
850
851 for (i, pwm) in paths.iter().enumerate() {
852 tracing::trace!(
853 direction,
854 index = i,
855 path = ?pwm.path,
856 cost = pwm.cost,
857 total_latency_ms = ?pwm.total_latency_ms,
858 "[{direction}] candidate path"
859 );
860 }
861
862 let pruned = prune_for_consistency(paths, self.anonymity_floor, hops);
863 if let Some(observer) = &self.observer {
864 let (direction, destination) = if src == self.me {
865 (PathDirection::Forward, dest)
866 } else {
867 (PathDirection::Return, src)
868 };
869 observer(TransportEvent::PathSearched {
870 direction,
871 destination: hopr_api::types::internal::NodeId::Offchain(destination),
872 phase1,
873 phase2,
874 retained: pruned.len() as u64,
875 });
876 }
877 if pruned.is_empty() {
878 return Err(PathPlannerError::Path(PathError::PathNotFound(
879 hops,
880 src.to_string(),
881 dest.to_string(),
882 )));
883 }
884 if tracing::enabled!(tracing::Level::TRACE) {
885 let relayer_set = pruned
886 .iter()
887 .filter_map(|p| p.path.first())
888 .collect::<std::collections::HashSet<_>>();
889 tracing::trace!(
890 %src,
891 %dest,
892 hops,
893 direction,
894 survived = pruned.len(),
895 distinct_relayers = relayer_set.len(),
896 first_relayers = ?relayer_set,
897 "pruned candidate paths",
898 );
899 }
900 Ok(pruned)
901 }
902}
903
904#[cfg(test)]
905mod tests {
906 use std::time::Duration;
907
908 use anyhow::Context;
909 use hex_literal::hex;
910 use hopr_api::{
911 graph::{
912 NetworkGraphUpdate, NetworkGraphWrite,
913 traits::{EdgeObservableWrite, EdgeWeightType},
914 },
915 types::{
916 crypto::prelude::{Keypair, OffchainKeypair},
917 internal::routing::RoutingOptions,
918 },
919 };
920 use hopr_network_graph::ChannelGraph;
921
922 use super::*;
923 use crate::path::{PathPlannerConfig, traits::PathSelector};
924
925 fn test_selector(
926 me: OffchainPublicKey,
927 graph: ChannelGraph,
928 max_paths: usize,
929 ) -> HoprGraphPathSelector<ChannelGraph> {
930 let cfg = PathPlannerConfig::default();
931 HoprGraphPathSelector::new(
932 me,
933 graph,
934 max_paths,
935 cfg.edge_penalty,
936 cfg.min_ack_rate,
937 cfg.min_paths_anonymity_floor,
938 )
939 }
940
941 const SECRET_0: [u8; 32] = hex!("60741b83b99e36aa0c1331578156e16b8e21166d01834abb6c64b103f885734d");
942 const SECRET_1: [u8; 32] = hex!("71bf1f42ebbfcd89c3e197a3fd7cda79b92499e509b6fefa0fe44d02821d146a");
943 const SECRET_2: [u8; 32] = hex!("c24bd833704dd2abdae3933fcc9962c2ac404f84132224c474147382d4db2299");
944 const SECRET_3: [u8; 32] = hex!("e0bf93e9c916104da00b1850adc4608bd7e9087bbd3f805451f4556aa6b3fd6e");
945 const SECRET_4: [u8; 32] = hex!("cfc66f718ec66fb822391775d749d7a0d66b690927673634816b63339bc12a3c");
946
947 const MAX_PATHS: usize = 4;
948
949 fn pubkey(secret: &[u8; 32]) -> OffchainPublicKey {
950 *OffchainKeypair::from_secret(secret).expect("valid secret").public()
951 }
952
953 fn mark_edge_full(graph: &ChannelGraph, src: &OffchainPublicKey, dst: &OffchainPublicKey) {
955 graph.upsert_edge(src, dst, |obs| {
956 obs.record(EdgeWeightType::Connected(true));
957 obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(50))));
958 obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(50))));
959 obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
960 1000u64,
961 ))));
962 });
963 }
964
965 fn mark_edge_unlooped(graph: &ChannelGraph, src: &OffchainPublicKey, dst: &OffchainPublicKey) {
967 graph.upsert_edge(src, dst, |obs| {
968 obs.record(EdgeWeightType::Connected(true));
969 obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(50))));
970 obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
971 1000u64,
972 ))));
973 });
974 }
975
976 fn two_hop_graph() -> (OffchainPublicKey, OffchainPublicKey, OffchainPublicKey, ChannelGraph) {
978 let me = pubkey(&SECRET_0);
979 let hop = pubkey(&SECRET_1);
980 let dest = pubkey(&SECRET_2);
981 let graph = ChannelGraph::new(me);
982 graph.add_node(hop);
983 graph.add_node(dest);
984 graph.add_edge(&me, &hop).unwrap();
986 graph.add_edge(&hop, &dest).unwrap();
987 mark_edge_full(&graph, &me, &hop);
988 mark_edge_full(&graph, &hop, &dest);
989 graph.add_edge(&dest, &hop).unwrap();
991 graph.add_edge(&hop, &me).unwrap();
992 mark_edge_full(&graph, &dest, &hop);
993 mark_edge_full(&graph, &hop, &me);
994 (me, hop, dest, graph)
995 }
996
997 #[tokio::test]
1001 async fn the_floor_should_not_bring_back_a_relay_whose_edge_into_the_destination_is_dead() -> anyhow::Result<()> {
1002 let me = pubkey(&SECRET_0);
1003 let good = pubkey(&SECRET_1);
1004 let bad1 = pubkey(&SECRET_2);
1005 let bad2 = pubkey(&SECRET_3);
1006 let dest = pubkey(&hex!(
1007 "b1c3ec2e9a3b1d5b7f0b5c3a8f3e0d6c4a2b1e0f9d8c7b6a59483726150f4e3d"
1008 ));
1009
1010 let graph = ChannelGraph::new(me);
1011 for node in [good, bad1, bad2, dest] {
1012 graph.add_node(node);
1013 }
1014 graph.set_ticket_face_value(hopr_api::graph::traits::Balance::one());
1015 for relay in [good, bad1, bad2] {
1016 graph.add_edge(&me, &relay)?;
1017 mark_edge_full(&graph, &me, &relay);
1018 graph.add_edge(&relay, &dest)?;
1019 }
1020 mark_edge_full(&graph, &good, &dest);
1021 for bad in [bad1, bad2] {
1022 mark_edge_unlooped(&graph, &bad, &dest);
1023 }
1024 for _ in 0..5 {
1026 graph.upsert_edge(&good, &dest, |obs| {
1027 obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(30))));
1028 });
1029 for bad in [bad1, bad2] {
1030 graph.upsert_edge(&bad, &dest, |obs| {
1031 obs.record(EdgeWeightType::Intermediate(Err(())));
1032 });
1033 }
1034 }
1035
1036 let selector = test_selector(me, graph.clone(), 8);
1038 let paths = selector.select_path(me, dest, 1).context("forward path")?;
1039
1040 assert!(
1041 paths.iter().any(|pwm| pwm.path.contains(&good)),
1042 "the healthy relay must stay a candidate"
1043 );
1044 assert!(
1045 !paths
1046 .iter()
1047 .any(|pwm| pwm.path.contains(&bad1) || pwm.path.contains(&bad2)),
1048 "a relay whose edge into the destination is dead must not be added to fill the floor, got {} candidates",
1049 paths.len()
1050 );
1051 Ok(())
1052 }
1053
1054 #[tokio::test]
1057 async fn a_first_relay_whose_loopbacks_never_return_should_be_excluded_for_one_to_three_hops() -> anyhow::Result<()>
1058 {
1059 let me = pubkey(&SECRET_0);
1060 let good = pubkey(&SECRET_1);
1061 let bad = pubkey(&SECRET_2);
1062 let m1 = pubkey(&SECRET_3);
1063 let m2 = pubkey(&SECRET_4);
1064 let dest = pubkey(&hex!(
1065 "b1c3ec2e9a3b1d5b7f0b5c3a8f3e0d6c4a2b1e0f9d8c7b6a59483726150f4e3d"
1066 ));
1067
1068 let graph = ChannelGraph::new(me);
1069 for node in [good, bad, m1, m2, dest] {
1070 graph.add_node(node);
1071 }
1072 for (src, dst) in [
1074 (good, dest),
1075 (bad, dest),
1076 (good, m1),
1077 (bad, m1),
1078 (m1, dest),
1079 (m1, m2),
1080 (m2, dest),
1081 (me, good),
1082 ] {
1083 graph.add_edge(&src, &dst)?;
1084 mark_edge_full(&graph, &src, &dst);
1085 }
1086 graph.add_edge(&me, &bad)?;
1087 mark_edge_unlooped(&graph, &me, &bad);
1088
1089 let selector = test_selector(me, graph.clone(), 50);
1090 let costs = |hops: usize| -> anyhow::Result<(Vec<f64>, Vec<f64>)> {
1091 let paths = selector.select_path(me, dest, hops).context("forward path")?;
1092 let (through, around): (Vec<_>, Vec<_>) = paths.into_iter().partition(|pwm| pwm.path.contains(&bad));
1093 Ok((
1094 through.into_iter().map(|pwm| pwm.cost).collect(),
1095 around.into_iter().map(|pwm| pwm.cost).collect(),
1096 ))
1097 };
1098
1099 for hops in 1..=3 {
1100 let (through, around) = costs(hops)?;
1101 assert!(
1102 !through.is_empty() && !around.is_empty(),
1103 "{hops} hop(s): both relays must be candidates before any loop is seen"
1104 );
1105 }
1106
1107 graph.upsert_edge(&me, &bad, |obs| {
1109 for _ in 0..5 {
1110 obs.record(EdgeWeightType::Intermediate(Err(())));
1111 }
1112 });
1113
1114 for hops in 1..=3 {
1116 let (through, around) = costs(hops)?;
1117 assert!(
1118 through.is_empty(),
1119 "{hops} hop(s): a relay whose loops never return must not be a candidate, got {through:?}"
1120 );
1121 assert!(
1122 !around.is_empty() && around.iter().all(|cost| *cost > 0.0),
1123 "{hops} hop(s): the honest relay must stay routable"
1124 );
1125 }
1126 Ok(())
1127 }
1128
1129 #[tokio::test]
1132 async fn a_return_relay_should_be_excluded_when_loopbacks_fail_on_the_edge_into_it() -> anyhow::Result<()> {
1133 let me = pubkey(&SECRET_0);
1134 let good = pubkey(&SECRET_1);
1135 let bad = pubkey(&SECRET_2);
1136 let dest = pubkey(&hex!(
1137 "b1c3ec2e9a3b1d5b7f0b5c3a8f3e0d6c4a2b1e0f9d8c7b6a59483726150f4e3d"
1138 ));
1139
1140 let costs = |failed: (OffchainPublicKey, OffchainPublicKey)| -> anyhow::Result<(Vec<f64>, Vec<f64>)> {
1142 let graph = ChannelGraph::new(me);
1143 for node in [good, bad, dest] {
1144 graph.add_node(node);
1145 }
1146 for (src, dst) in [(dest, good), (good, me), (dest, bad), (bad, me)] {
1147 graph.add_edge(&src, &dst)?;
1148 if (src, dst) == failed {
1149 mark_edge_unlooped(&graph, &src, &dst);
1151 } else {
1152 mark_edge_full(&graph, &src, &dst);
1153 }
1154 }
1155 graph.upsert_edge(&failed.0, &failed.1, |obs| {
1156 for _ in 0..5 {
1157 obs.record(EdgeWeightType::Intermediate(Err(())));
1158 }
1159 });
1160 let paths = test_selector(me, graph, 50)
1161 .select_path(dest, me, 1)
1162 .context("return path")?;
1163 let (through, around): (Vec<_>, Vec<_>) = paths.into_iter().partition(|pwm| pwm.path.contains(&bad));
1164 Ok((
1165 through.into_iter().map(|pwm| pwm.cost).collect(),
1166 around.into_iter().map(|pwm| pwm.cost).collect(),
1167 ))
1168 };
1169
1170 let (through, around) = costs((dest, bad))?;
1172 assert!(
1173 through.is_empty(),
1174 "a failed edge into the relay must exclude it, got {through:?}"
1175 );
1176 assert!(
1177 !around.is_empty() && around.iter().all(|cost| *cost > 0.0),
1178 "the honest relay must stay routable"
1179 );
1180 Ok(())
1181 }
1182
1183 #[tokio::test]
1188 async fn a_fast_dead_relay_should_not_keep_a_slot_after_pruning_for_zero_to_three_hops_in_both_directions()
1189 -> anyhow::Result<()> {
1190 const FLOOR: usize = 2;
1191 let me = pubkey(&[1; 32]);
1192 let dest = pubkey(&[2; 32]);
1193 let relay = |layer: usize, index: usize| pubkey(&[10 + (layer * 3 + index) as u8; 32]);
1194
1195 for direction in ["forward", "return"] {
1197 let graph = ChannelGraph::new(me);
1198 graph.add_node(dest);
1199 let (src, dst) = if direction == "forward" { (me, dest) } else { (dest, me) };
1200 graph.add_edge(&src, &dst)?;
1201 mark_edge_full(&graph, &src, &dst);
1202 let paths = test_selector(me, graph, 50)
1203 .select_path(src, dst, 0)
1204 .context("direct path")?;
1205 assert_eq!(paths.len(), 1, "{direction}, 0 hops: the direct route must stay");
1206 }
1207
1208 let mut failures = Vec::new();
1209 for direction in ["forward", "return"] {
1210 for hops in 1..=3usize {
1211 for position in 1..=hops {
1212 let graph = ChannelGraph::new(me);
1213 graph.set_ticket_face_value(hopr_api::graph::traits::Balance::one());
1215 graph.add_node(dest);
1216 for layer in 1..=hops {
1217 for index in 0..3 {
1218 graph.add_node(relay(layer, index));
1219 }
1220 }
1221 let (sender, receiver) = if direction == "forward" { (me, dest) } else { (dest, me) };
1223 let dead = relay(position, 0);
1224 let node = |layer: usize, index: usize| match layer {
1225 0 => sender,
1226 l if l == hops + 1 => receiver,
1227 l => relay(l, index),
1228 };
1229 for layer in 0..=hops {
1230 for from in 0..if layer == 0 { 1 } else { 3 } {
1231 for to in 0..if layer == hops { 1 } else { 3 } {
1232 let (src, dst) = (node(layer, from), node(layer + 1, to));
1233 graph.add_edge(&src, &dst)?;
1234 if dst == dead {
1235 mark_edge_unlooped(&graph, &src, &dst);
1236 } else {
1237 mark_edge_full(&graph, &src, &dst);
1238 }
1239 }
1240 }
1241 }
1242 for from in 0..if position == 1 { 1 } else { 3 } {
1244 graph.upsert_edge(&node(position - 1, from), &dead, |obs| {
1245 obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(5))));
1246 for _ in 0..5 {
1247 obs.record(EdgeWeightType::Intermediate(Err(())));
1248 }
1249 });
1250 }
1251
1252 let selector = HoprGraphPathSelector::new(
1253 me,
1254 graph,
1255 50,
1256 PathPlannerConfig::default().edge_penalty,
1257 PathPlannerConfig::default().min_ack_rate,
1258 FLOOR,
1259 );
1260 let kept = selector.select_path(sender, receiver, hops).context("pruned paths")?;
1261 let through_dead = kept.iter().filter(|pwm| pwm.path.contains(&dead)).count();
1262 if kept.is_empty() || through_dead > 0 {
1263 failures.push(format!(
1264 "{direction}, {hops} hop(s), dead relay in position {position}: {through_dead} of {} kept \
1265 paths run through the dead relay",
1266 kept.len()
1267 ));
1268 }
1269 }
1270 }
1271 }
1272 assert!(failures.is_empty(), "{}", failures.join("\n"));
1273 Ok(())
1274 }
1275
1276 #[tokio::test]
1277 async fn unreachable_dest_should_return_error() -> anyhow::Result<()> {
1278 let me = pubkey(&SECRET_0);
1279 let unreachable = pubkey(&SECRET_1);
1280 let graph = ChannelGraph::new(me);
1281 let selector = test_selector(me, graph, MAX_PATHS);
1283
1284 let fwd = selector.select_path(me, unreachable, 1);
1285 assert!(fwd.is_err(), "forward: should error when destination is unreachable");
1286 assert!(matches!(
1287 fwd.unwrap_err(),
1288 PathPlannerError::Path(PathError::PathNotFound(..))
1289 ));
1290
1291 let rev = selector.select_path(unreachable, me, 1);
1292 assert!(rev.is_err(), "reverse: should error when destination is unreachable");
1293 assert!(matches!(
1294 rev.unwrap_err(),
1295 PathPlannerError::Path(PathError::PathNotFound(..))
1296 ));
1297
1298 Ok(())
1299 }
1300
1301 #[tokio::test]
1302 async fn path_should_exclude_source() -> anyhow::Result<()> {
1303 let (me, _hop, dest, graph) = two_hop_graph();
1304 let selector = test_selector(me, graph, MAX_PATHS);
1305
1306 let fwd = selector.select_path(me, dest, 1).context("forward path")?;
1307 assert!(!fwd.is_empty());
1308 for pwm in &fwd {
1309 assert!(!pwm.path.contains(&me), "forward path must not contain the source");
1310 assert!(pwm.cost > 0.0, "cost must be positive");
1311 }
1312
1313 let rev = selector.select_path(dest, me, 1).context("reverse path")?;
1314 assert!(!rev.is_empty());
1315 for pwm in &rev {
1316 assert!(!pwm.path.contains(&dest), "reverse path must not contain the source");
1317 assert!(pwm.cost > 0.0, "cost must be positive");
1318 }
1319
1320 Ok(())
1321 }
1322
1323 #[tokio::test]
1324 async fn multi_hop_path_should_have_correct_length() -> anyhow::Result<()> {
1325 let me = pubkey(&SECRET_0);
1327 let a = pubkey(&SECRET_1);
1328 let b = pubkey(&SECRET_2);
1329 let dest = pubkey(&SECRET_3);
1330 let graph = ChannelGraph::new(me);
1331 for n in [a, b, dest] {
1332 graph.add_node(n);
1333 }
1334 graph.add_edge(&me, &a).unwrap();
1336 graph.add_edge(&a, &b).unwrap();
1337 graph.add_edge(&b, &dest).unwrap();
1338 mark_edge_full(&graph, &me, &a);
1339 mark_edge_full(&graph, &a, &b);
1340 mark_edge_full(&graph, &b, &dest);
1341 graph.add_edge(&dest, &b).unwrap();
1343 graph.add_edge(&b, &a).unwrap();
1344 graph.add_edge(&a, &me).unwrap();
1345 mark_edge_full(&graph, &dest, &b);
1346 mark_edge_full(&graph, &b, &a);
1347 mark_edge_full(&graph, &a, &me);
1348
1349 let selector = test_selector(me, graph, MAX_PATHS);
1350
1351 let fwd = selector.select_path(me, dest, 2).context("forward 2-hop path")?;
1352 assert!(!fwd.is_empty());
1353 for pwm in &fwd {
1354 assert_eq!(pwm.path.len(), 3, "forward 2-hop path: [A, B, dest]");
1355 assert_eq!(pwm.path.last(), Some(&dest));
1356 }
1357
1358 let rev = selector.select_path(dest, me, 2).context("reverse 2-hop path")?;
1359 assert!(!rev.is_empty());
1360 for pwm in &rev {
1361 assert_eq!(pwm.path.len(), 3, "reverse 2-hop path: [B, A, me]");
1362 assert_eq!(pwm.path.last(), Some(&me));
1363 }
1364
1365 Ok(())
1366 }
1367
1368 #[tokio::test]
1369 async fn one_hop_path_should_include_relay_and_destination() -> anyhow::Result<()> {
1370 let (me, relay, dest, graph) = two_hop_graph();
1372 let selector = test_selector(me, graph, MAX_PATHS);
1373
1374 let fwd = selector.select_path(me, dest, 1).context("forward 1-hop path")?;
1375 assert!(!fwd.is_empty());
1376 for pwm in &fwd {
1377 assert_eq!(pwm.path.len(), 2, "forward: [relay, dest]");
1378 assert_eq!(pwm.path.last(), Some(&dest));
1379 assert!(!pwm.path.contains(&me));
1380 }
1381
1382 let rev = selector.select_path(dest, me, 1).context("reverse 1-hop path")?;
1383 assert!(!rev.is_empty());
1384 for pwm in &rev {
1385 assert_eq!(pwm.path.len(), 2, "reverse: [relay, me]");
1386 assert_eq!(pwm.path.last(), Some(&me));
1387 assert!(!pwm.path.contains(&dest));
1388 }
1389
1390 let _ = relay;
1391 Ok(())
1392 }
1393
1394 #[tokio::test]
1395 async fn diamond_topology_should_return_multiple_paths() -> anyhow::Result<()> {
1396 let me = pubkey(&SECRET_0);
1398 let a = pubkey(&SECRET_1);
1399 let b = pubkey(&SECRET_2);
1400 let dest = pubkey(&SECRET_3);
1401 let graph = ChannelGraph::new(me);
1402 for n in [a, b, dest] {
1403 graph.add_node(n);
1404 }
1405 graph.add_edge(&me, &a).unwrap();
1407 graph.add_edge(&me, &b).unwrap();
1408 graph.add_edge(&a, &dest).unwrap();
1409 graph.add_edge(&b, &dest).unwrap();
1410 mark_edge_full(&graph, &me, &a);
1411 mark_edge_full(&graph, &me, &b);
1412 mark_edge_full(&graph, &a, &dest);
1413 mark_edge_full(&graph, &b, &dest);
1414 graph.add_edge(&dest, &a).unwrap();
1416 graph.add_edge(&dest, &b).unwrap();
1417 graph.add_edge(&a, &me).unwrap();
1418 graph.add_edge(&b, &me).unwrap();
1419 mark_edge_full(&graph, &dest, &a);
1420 mark_edge_full(&graph, &dest, &b);
1421 mark_edge_full(&graph, &a, &me);
1422 mark_edge_full(&graph, &b, &me);
1423
1424 let selector = test_selector(me, graph, MAX_PATHS);
1425
1426 let fwd = selector.select_path(me, dest, 1).context("forward path")?;
1427 assert_eq!(fwd.len(), 2, "forward: both paths via a and b should be returned");
1428 for pwm in &fwd {
1429 assert_eq!(pwm.path.last(), Some(&dest));
1430 }
1431
1432 let rev = selector.select_path(dest, me, 1).context("reverse path")?;
1433 assert_eq!(rev.len(), 2, "reverse: both paths via a and b should be returned");
1434 for pwm in &rev {
1435 assert_eq!(pwm.path.last(), Some(&me));
1436 }
1437
1438 Ok(())
1439 }
1440
1441 #[tokio::test]
1442 async fn zero_cost_paths_should_return_error() -> anyhow::Result<()> {
1443 let me = pubkey(&SECRET_0);
1445 let dest = pubkey(&SECRET_1);
1446 let graph = ChannelGraph::new(me);
1447 graph.add_node(dest);
1448 graph.add_edge(&me, &dest).unwrap();
1449 graph.add_edge(&dest, &me).unwrap();
1450 let selector = test_selector(me, graph, MAX_PATHS);
1453 assert!(
1454 selector.select_path(me, dest, 1).is_err(),
1455 "forward: edge with no observations should produce no valid path"
1456 );
1457 assert!(
1458 selector.select_path(dest, me, 1).is_err(),
1459 "reverse: edge with no observations should produce no valid path"
1460 );
1461 Ok(())
1462 }
1463
1464 #[tokio::test]
1465 async fn no_path_at_requested_hop_count_should_return_error() -> anyhow::Result<()> {
1466 let me = pubkey(&SECRET_0);
1468 let dest = pubkey(&SECRET_1);
1469 let graph = ChannelGraph::new(me);
1470 graph.add_node(dest);
1471 graph.add_edge(&me, &dest).unwrap();
1472 graph.add_edge(&dest, &me).unwrap();
1473 mark_edge_full(&graph, &me, &dest);
1474 mark_edge_full(&graph, &dest, &me);
1475
1476 let selector = test_selector(me, graph, MAX_PATHS);
1477 assert!(
1478 selector.select_path(me, dest, 2).is_err(),
1479 "forward: no 2-hop path should exist for a direct edge"
1480 );
1481 assert!(
1482 selector.select_path(dest, me, 2).is_err(),
1483 "reverse: no 2-hop path should exist for a direct edge"
1484 );
1485 Ok(())
1486 }
1487
1488 #[tokio::test]
1489 async fn forward_path_should_work_without_last_edge() -> anyhow::Result<()> {
1490 let me = pubkey(&SECRET_0);
1494 let relay = pubkey(&SECRET_1);
1495 let dest = pubkey(&SECRET_2);
1496 let graph = ChannelGraph::new(me);
1497 graph.add_node(relay);
1498 graph.add_node(dest);
1499 graph.add_edge(&me, &relay).unwrap();
1501 mark_edge_full(&graph, &me, &relay);
1502 graph.add_edge(&dest, &relay).unwrap();
1504 graph.add_edge(&relay, &me).unwrap();
1505 mark_edge_full(&graph, &dest, &relay);
1506 mark_edge_full(&graph, &relay, &me);
1507
1508 let selector = test_selector(me, graph, MAX_PATHS);
1509
1510 let fwd = selector
1512 .select_path(me, dest, 1)
1513 .context("forward path with virtual last hop")?;
1514 assert!(!fwd.is_empty(), "forward path should find at least one route");
1515 for pwm in &fwd {
1516 assert_eq!(pwm.path.len(), 2, "forward: [relay, dest]");
1517 assert_eq!(pwm.path[0], relay);
1518 assert_eq!(pwm.path[1], dest);
1519 }
1520
1521 let rev = selector.select_path(dest, me, 1).context("return path")?;
1523 assert!(!rev.is_empty(), "return path should find at least one route");
1524 for pwm in &rev {
1525 assert_eq!(pwm.path.len(), 2, "return: [relay, me]");
1526 assert_eq!(pwm.path.last(), Some(&me));
1527 }
1528
1529 Ok(())
1530 }
1531
1532 #[tokio::test]
1533 async fn five_node_chain_should_support_max_hops() -> anyhow::Result<()> {
1534 let me = pubkey(&SECRET_0);
1536 let a = pubkey(&SECRET_1);
1537 let b = pubkey(&SECRET_2);
1538 let c = pubkey(&SECRET_3);
1539 let dest = pubkey(&SECRET_4);
1540 let graph = ChannelGraph::new(me);
1541 for n in [a, b, c, dest] {
1542 graph.add_node(n);
1543 }
1544 graph.add_edge(&me, &a).unwrap();
1546 graph.add_edge(&a, &b).unwrap();
1547 graph.add_edge(&b, &c).unwrap();
1548 graph.add_edge(&c, &dest).unwrap();
1549 mark_edge_full(&graph, &me, &a);
1550 mark_edge_full(&graph, &a, &b);
1551 mark_edge_full(&graph, &b, &c);
1552 mark_edge_full(&graph, &c, &dest);
1553 graph.add_edge(&dest, &c).unwrap();
1555 graph.add_edge(&c, &b).unwrap();
1556 graph.add_edge(&b, &a).unwrap();
1557 graph.add_edge(&a, &me).unwrap();
1558 mark_edge_full(&graph, &dest, &c);
1559 mark_edge_full(&graph, &c, &b);
1560 mark_edge_full(&graph, &b, &a);
1561 mark_edge_full(&graph, &a, &me);
1562
1563 let selector = test_selector(me, graph, MAX_PATHS);
1564
1565 let fwd = selector
1566 .select_path(me, dest, RoutingOptions::MAX_INTERMEDIATE_HOPS)
1567 .context("forward 3-hop path")?;
1568 assert!(!fwd.is_empty());
1569 for pwm in &fwd {
1570 assert_eq!(pwm.path.len(), 4, "forward: [a, b, c, dest]");
1571 assert_eq!(pwm.path.last(), Some(&dest));
1572 assert!(!pwm.path.contains(&me));
1573 }
1574
1575 let rev = selector
1576 .select_path(dest, me, RoutingOptions::MAX_INTERMEDIATE_HOPS)
1577 .context("reverse 3-hop path")?;
1578 assert!(!rev.is_empty());
1579 for pwm in &rev {
1580 assert_eq!(pwm.path.len(), 4, "reverse: [c, b, a, me]");
1581 assert_eq!(pwm.path.last(), Some(&me));
1582 assert!(!pwm.path.contains(&dest));
1583 }
1584
1585 Ok(())
1586 }
1587
1588 #[tokio::test]
1589 async fn selector_should_reject_extended_path_containing_destination() -> anyhow::Result<()> {
1590 let me = pubkey(&SECRET_0);
1595 let relay = pubkey(&SECRET_1);
1596 let dest = pubkey(&SECRET_2);
1597 let graph = ChannelGraph::new(me);
1598 graph.add_node(relay);
1599 graph.add_node(dest);
1600 graph.add_edge(&me, &dest).unwrap();
1602 mark_edge_full(&graph, &me, &dest);
1603 graph.add_edge(&me, &relay).unwrap();
1605 mark_edge_full(&graph, &me, &relay);
1606 graph.add_edge(&dest, &relay).unwrap();
1608 graph.add_edge(&relay, &me).unwrap();
1609 mark_edge_full(&graph, &dest, &relay);
1610 mark_edge_full(&graph, &relay, &me);
1611
1612 let selector = test_selector(me, graph, MAX_PATHS);
1613
1614 let fwd = selector
1615 .select_path(me, dest, 1)
1616 .context("forward path with dest as direct neighbor")?;
1617 assert!(!fwd.is_empty(), "should find at least one path via relay");
1618 for pwm in &fwd {
1619 assert_eq!(pwm.path.len(), 2, "path must be [relay, dest]");
1620 assert_eq!(pwm.path[0], relay, "first node must be relay, not dest");
1621 assert_eq!(pwm.path[1], dest);
1622 }
1623 Ok(())
1624 }
1625
1626 #[tokio::test]
1627 async fn selector_should_reject_one_hop_path_where_relay_equals_destination() -> anyhow::Result<()> {
1628 let me = pubkey(&SECRET_0);
1631 let relay = pubkey(&SECRET_1);
1632 let dest = pubkey(&SECRET_2);
1633 let graph = ChannelGraph::new(me);
1634 graph.add_node(relay);
1635 graph.add_node(dest);
1636 graph.add_edge(&me, &dest).unwrap();
1638 mark_edge_full(&graph, &me, &dest);
1639 graph.add_edge(&me, &relay).unwrap();
1641 mark_edge_full(&graph, &me, &relay);
1642 graph.add_edge(&dest, &relay).unwrap();
1644 graph.add_edge(&relay, &me).unwrap();
1645 mark_edge_full(&graph, &dest, &relay);
1646 mark_edge_full(&graph, &relay, &me);
1647
1648 let selector = test_selector(me, graph, MAX_PATHS);
1649
1650 let fwd = selector
1651 .select_path(me, dest, 1)
1652 .context("forward path — dest is direct neighbor, relay is intermediate")?;
1653 assert!(!fwd.is_empty(), "should find path via relay (virtual last hop)");
1654 for pwm in &fwd {
1655 assert_eq!(pwm.path[0], relay, "intermediate must be relay, not dest");
1656 assert_ne!(pwm.path[0], dest, "dest must not appear as intermediate");
1657 }
1658 Ok(())
1659 }
1660
1661 #[tokio::test]
1662 async fn selector_should_skip_zero_cost_paths() -> anyhow::Result<()> {
1663 let me = pubkey(&SECRET_0);
1665 let hop = pubkey(&SECRET_1);
1666 let dest = pubkey(&SECRET_2);
1667 let graph = ChannelGraph::new(me);
1668 graph.add_node(hop);
1669 graph.add_node(dest);
1670 graph.add_edge(&me, &hop).context("adding edge me -> hop")?;
1671 graph.add_edge(&hop, &dest).context("adding edge hop -> dest")?;
1672 let selector = test_selector(me, graph, MAX_PATHS);
1675
1676 let err = selector
1677 .select_path(me, dest, 1)
1678 .expect_err("zero-cost paths should be filtered out");
1679 anyhow::ensure!(
1680 matches!(err, PathPlannerError::Path(PathError::PathNotFound(..))),
1681 "expected PathNotFound, got: {err}"
1682 );
1683 Ok(())
1684 }
1685
1686 fn make_path_with_latency(latency_ms: Option<u32>) -> PathWithMetrics {
1689 PathWithMetrics {
1690 path: vec![],
1691 cost: 1.0,
1692 total_latency_ms: latency_ms,
1693 min_probe_success_rate: None,
1694 min_ack_rate: None,
1695 fundable_tickets_floor: None,
1696 }
1697 }
1698
1699 fn make_path_with_tickets(latency_ms: Option<u32>, fundable_tickets_floor: Option<u128>) -> PathWithMetrics {
1700 PathWithMetrics {
1701 path: vec![],
1702 cost: 1.0,
1703 total_latency_ms: latency_ms,
1704 min_probe_success_rate: None,
1705 min_ack_rate: None,
1706 fundable_tickets_floor,
1707 }
1708 }
1709
1710 fn make_path_via(relayer_idx: u8, latency_ms: u32) -> PathWithMetrics {
1712 let mut secret = [1u8; 32];
1713 secret[0] = relayer_idx.max(1);
1714 let relayer = *OffchainKeypair::from_secret(&secret).expect("valid secret").public();
1715 PathWithMetrics {
1716 path: vec![relayer],
1717 cost: 1.0,
1718 total_latency_ms: Some(latency_ms),
1719 min_probe_success_rate: None,
1720 min_ack_rate: None,
1721 fundable_tickets_floor: Some(1000),
1722 }
1723 }
1724
1725 #[test]
1726 fn prune_should_prefer_distinct_first_relayers_over_pure_latency_order() {
1727 let candidates = vec![
1730 make_path_via(1, 10),
1731 make_path_via(1, 11),
1732 make_path_via(1, 12),
1733 make_path_via(1, 13),
1734 make_path_via(2, 50),
1735 make_path_via(3, 60),
1736 make_path_via(4, 70),
1737 ];
1738
1739 let result = prune_for_consistency(candidates, 3, 1);
1740 assert_eq!(3, result.len());
1741
1742 let relayers: Vec<String> = result
1743 .iter()
1744 .map(|p| hopr_api::types::primitive::traits::ToHex::to_hex(p.path.first().expect("non-empty")))
1745 .collect();
1746 let mut distinct = relayers.clone();
1747 distinct.sort();
1748 distinct.dedup();
1749 assert_eq!(3, distinct.len(), "the floor must be filled with distinct relayers");
1750
1751 assert_eq!(Some(10), result[0].total_latency_ms, "still latency-ordered");
1754 }
1755
1756 fn make_path_through(first_idx: u8, middle_idx: u8, latency_ms: u32) -> PathWithMetrics {
1758 let key = |tag: u8, idx: u8| {
1759 let mut secret = [1u8; 32];
1760 secret[0] = idx.max(1);
1761 secret[2] = tag;
1762 *OffchainKeypair::from_secret(&secret).expect("valid secret").public()
1763 };
1764 PathWithMetrics {
1765 path: vec![key(1, first_idx), key(2, middle_idx), key(3, 1)],
1766 cost: 1.0,
1767 total_latency_ms: Some(latency_ms),
1768 min_probe_success_rate: None,
1769 min_ack_rate: None,
1770 fundable_tickets_floor: Some(1000),
1771 }
1772 }
1773
1774 #[test]
1778 fn prune_should_bound_how_often_a_relayer_recurs_in_a_middle_position() {
1779 let hub = 9u8;
1780 let mut candidates = Vec::new();
1781 for first in 1..=8u8 {
1782 candidates.push(make_path_through(first, hub, 10 + u32::from(first)));
1783 candidates.push(make_path_through(first, first, 50 + u32::from(first)));
1784 }
1785
1786 let result = prune_for_consistency(candidates, 8, 2);
1787 assert_eq!(8, result.len());
1788
1789 let hub_key = make_path_through(1, hub, 0).path[1];
1790 let through_hub = result.iter().filter(|p| p.path[1] == hub_key).count();
1791 assert_eq!(
1792 3, through_hub,
1793 "the hub sits in the middle of at most ceil(8 / 3) candidates"
1794 );
1795
1796 let firsts: std::collections::HashSet<_> = result.iter().map(|p| p.path[0]).collect();
1797 assert_eq!(8, firsts.len(), "every first relayer is still represented");
1798 assert_eq!(
1799 Some(11),
1800 result[0].total_latency_ms,
1801 "the fastest path is still kept, and the order is still by latency"
1802 );
1803 }
1804
1805 #[test]
1810 fn prune_should_keep_distinct_first_relayers_when_the_cap_runs_out() {
1811 let hub = 9u8;
1812 let candidates = vec![
1813 make_path_through(1, hub, 10),
1814 make_path_through(1, hub, 11),
1815 make_path_through(2, hub, 12),
1816 make_path_through(2, hub, 13),
1817 make_path_through(3, hub, 14),
1818 make_path_through(4, hub, 15),
1819 ];
1820 let result = prune_for_consistency(candidates, 4, 2);
1821 assert_eq!(4, result.len());
1822 let firsts: std::collections::HashSet<_> = result.iter().map(|p| p.path[0]).collect();
1823 assert_eq!(4, firsts.len(), "four first relayers, not two kept twice each");
1824 }
1825
1826 fn make_three_hop_path(first: u8, second: u8, third: u8, latency_ms: u32) -> PathWithMetrics {
1829 let relayer = |idx: u8| {
1830 let mut secret = [1u8; 32];
1831 secret[0] = idx.max(1);
1832 secret[2] = 7;
1833 *OffchainKeypair::from_secret(&secret).expect("valid secret").public()
1834 };
1835 let mut destination = [1u8; 32];
1836 destination[2] = 3;
1837 PathWithMetrics {
1838 path: vec![
1839 relayer(first),
1840 relayer(second),
1841 relayer(third),
1842 *OffchainKeypair::from_secret(&destination)
1843 .expect("valid secret")
1844 .public(),
1845 ],
1846 cost: 1.0,
1847 total_latency_ms: Some(latency_ms),
1848 min_probe_success_rate: None,
1849 min_ack_rate: None,
1850 fundable_tickets_floor: Some(1000),
1851 }
1852 }
1853
1854 #[test]
1858 fn prune_should_bound_a_relayer_over_all_later_positions_together() {
1859 let hub = 30u8;
1860 let mut candidates = Vec::new();
1861 for first in 1..=3u8 {
1862 candidates.push(make_three_hop_path(first, hub, 10 + first, u32::from(first)));
1863 }
1864 for first in 4..=6u8 {
1865 candidates.push(make_three_hop_path(first, 10 + first, hub, u32::from(first)));
1866 }
1867 for first in 1..=6u8 {
1868 candidates.push(make_three_hop_path(
1869 first,
1870 20 + first,
1871 40 + first,
1872 100 + u32::from(first),
1873 ));
1874 }
1875
1876 let result = prune_for_consistency(candidates, 6, 3);
1877 assert_eq!(6, result.len());
1878 let hub_key = make_three_hop_path(1, hub, 2, 0).path[1];
1879 let through_hub = result.iter().filter(|p| p.path[1..3].contains(&hub_key)).count();
1880 assert_eq!(
1881 2, through_hub,
1882 "the hub sits past the first position in at most ceil(6 / 3) candidates"
1883 );
1884 let firsts: std::collections::HashSet<_> = result.iter().map(|p| p.path[0]).collect();
1885 assert_eq!(6, firsts.len(), "every first relayer is still represented");
1886 }
1887
1888 #[test]
1891 fn prune_should_fill_the_floor_through_a_hub_when_nothing_else_is_left() {
1892 let candidates = (1..=6u8)
1893 .map(|first| make_path_through(first, 9, 10 + u32::from(first)))
1894 .collect();
1895 let result = prune_for_consistency(candidates, 4, 2);
1896 assert_eq!(4, result.len(), "four of six through the only middle relayer there is");
1897 }
1898
1899 #[test]
1900 fn distinct_first_relayers_counts_unique_first_hops() {
1901 let paths = vec![
1904 make_path_via(1, 10),
1905 make_path_via(1, 20),
1906 make_path_via(2, 30),
1907 make_path_with_latency(Some(40)), ];
1909 assert_eq!(2, distinct_first_relayers(&paths));
1910 }
1911
1912 #[test]
1913 fn floor_zero_keeps_all_distinct_relayers_unlike_a_small_cap() {
1914 let candidates: Vec<_> = (1..=10u8).map(|i| make_path_via(i, i as u32 * 10)).collect();
1919
1920 let uncapped = prune_for_consistency(candidates.clone(), 0, 1);
1921 assert_eq!(10, uncapped.len(), "floor = 0 disables pruning: all candidates survive");
1922 assert_eq!(10, distinct_first_relayers(&uncapped), "all ten relayers kept");
1923
1924 let capped = prune_for_consistency(candidates, 2, 1);
1925 assert_eq!(2, capped.len(), "floor = 2 caps survivors at two");
1926 assert_eq!(2, distinct_first_relayers(&capped));
1927 }
1928
1929 #[test]
1930 fn prune_should_fall_back_to_latency_order_once_relayers_are_exhausted() {
1931 let candidates = vec![
1934 make_path_via(1, 10),
1935 make_path_via(2, 20),
1936 make_path_via(1, 30),
1937 make_path_via(2, 40),
1938 make_path_via(1, 50),
1939 ];
1940
1941 let result = prune_for_consistency(candidates, 4, 1);
1942 assert_eq!(4, result.len());
1943 assert_eq!(
1944 vec![Some(10), Some(20), Some(30), Some(40)],
1945 result.iter().map(|p| p.total_latency_ms).collect::<Vec<_>>()
1946 );
1947 }
1948
1949 #[test]
1950 fn prune_keeps_all_when_below_floor() {
1951 let candidates: Vec<_> = (0..5).map(|i| make_path_with_latency(Some(i * 10))).collect();
1952 let result = prune_for_consistency(candidates, 8, 1);
1953 assert_eq!(result.len(), 5, "below floor: nothing should be dropped");
1954 }
1955
1956 #[test]
1957 fn prune_drops_high_latency_first() {
1958 let candidates: Vec<_> = (0..30u32)
1960 .map(|i| make_path_with_tickets(Some(i * 10), Some(1_000_000)))
1961 .collect();
1962 let result = prune_for_consistency(candidates, 8, 1);
1963 assert_eq!(result.len(), 8);
1964 for p in &result {
1965 assert!(p.total_latency_ms.unwrap() < 80, "only the 8 lowest should survive");
1966 }
1967 }
1968
1969 #[test]
1970 fn prune_preserves_populated_paths_over_unpopulated() {
1971 let mut candidates: Vec<_> = vec![
1975 make_path_with_tickets(Some(10), Some(1_000)),
1976 make_path_with_tickets(Some(30), Some(1_000)),
1977 make_path_with_tickets(Some(20), Some(1_000)),
1978 ];
1979 candidates.extend((0..6).map(|_| make_path_with_latency(None)));
1980 let result = prune_for_consistency(candidates, 8, 1);
1981 assert_eq!(result.len(), 8);
1982 let populated: Vec<_> = result.iter().filter(|p| p.total_latency_ms.is_some()).collect();
1984 assert_eq!(populated.len(), 3);
1985 assert!(populated.iter().any(|p| p.total_latency_ms == Some(10)));
1986 assert!(populated.iter().any(|p| p.total_latency_ms == Some(20)));
1987 assert!(populated.iter().any(|p| p.total_latency_ms == Some(30)));
1988 }
1989
1990 #[test]
1991 fn prune_drops_unpopulated_when_all_populated_exhausted() {
1992 let candidates: Vec<_> = (0..20).map(|_| make_path_with_latency(None)).collect();
1994 let result = prune_for_consistency(candidates, 8, 1);
1995 assert_eq!(result.len(), 8);
1996 }
1997
1998 #[test]
1999 fn prune_keeps_populated_when_unpopulated_exceeds_floor() {
2000 let mut candidates: Vec<_> = vec![
2004 make_path_with_tickets(Some(10), Some(1_000)),
2005 make_path_with_tickets(Some(20), Some(1_000)),
2006 ];
2007 candidates.extend((0..10).map(|_| make_path_with_latency(None)));
2008 let result = prune_for_consistency(candidates, 8, 1);
2009 assert_eq!(result.len(), 8);
2010 let populated: Vec<_> = result.iter().filter(|p| p.total_latency_ms.is_some()).collect();
2011 assert_eq!(populated.len(), 2, "both measured paths must survive");
2012 assert!(populated.iter().any(|p| p.total_latency_ms == Some(10)));
2013 assert!(populated.iter().any(|p| p.total_latency_ms == Some(20)));
2014 }
2015
2016 #[test]
2017 fn prune_exact_floor_is_unchanged() {
2018 let candidates: Vec<_> = (0..8)
2019 .map(|i| make_path_with_tickets(Some(i * 10), Some(1_000)))
2020 .collect();
2021 let result = prune_for_consistency(candidates, 8, 1);
2022 assert_eq!(result.len(), 8);
2023 }
2024
2025 #[test]
2026 fn prune_0_hop_with_measured_latency_and_no_capacity_is_populated() {
2027 let mut candidates: Vec<_> = vec![
2030 make_path_with_tickets(Some(50), None), ];
2032 candidates.extend((0..10).map(|_| make_path_with_latency(None)));
2033 let result = prune_for_consistency(candidates, 8, 0);
2034 assert_eq!(result.len(), 8);
2035 let has_0_hop = result.iter().any(|p| p.total_latency_ms == Some(50));
2037 assert!(has_0_hop, "0-hop path with measured latency must survive pruning");
2038 }
2039
2040 #[test]
2041 fn prune_multi_hop_without_fundable_tickets_floor_is_unpopulated() {
2042 let candidates: Vec<_> = vec![
2045 make_path_with_tickets(Some(50), Some(1_000)), make_path_with_tickets(Some(50), Some(1_000)), make_path_with_tickets(Some(50), Some(1_000)), make_path_with_tickets(Some(50), Some(1_000)), make_path_with_tickets(Some(50), Some(1_000)), make_path_with_tickets(Some(50), Some(1_000)), make_path_with_tickets(Some(50), Some(1_000)), make_path_with_tickets(Some(50), Some(1_000)), make_path_with_tickets(Some(40), None), ];
2055 let result = prune_for_consistency(candidates, 8, 1);
2056 assert_eq!(result.len(), 8);
2057 let has_missing_balance = result.iter().any(|p| p.fundable_tickets_floor.is_none());
2060 assert!(
2061 !has_missing_balance,
2062 "path without capacity floor must be pruned when fully-measured paths fill the floor"
2063 );
2064 }
2065
2066 #[test]
2067 fn prune_for_consistency_floor_zero_returns_all() {
2068 let candidates = vec![
2070 make_path_with_tickets(Some(10), Some(1_000)),
2071 make_path_with_tickets(Some(20), None),
2072 make_path_with_tickets(None, None),
2073 ];
2074 let result = prune_for_consistency(candidates, 0, 1);
2075 assert_eq!(result.len(), 3, "floor=0 must return all candidates");
2076 }
2077
2078 #[tokio::test]
2081 async fn path_metrics_aggregate_latency_correctly() -> anyhow::Result<()> {
2082 let me = pubkey(&SECRET_0);
2085 let a = pubkey(&SECRET_1);
2086 let b = pubkey(&SECRET_2);
2087 let dest = pubkey(&SECRET_3);
2088 let graph = ChannelGraph::new(me);
2089 for n in [a, b, dest] {
2090 graph.add_node(n);
2091 }
2092
2093 let make_edge = |src: &OffchainPublicKey, dst: &OffchainPublicKey, lat_ms: u64| {
2094 graph.upsert_edge(src, dst, |obs| {
2095 obs.record(EdgeWeightType::Connected(true));
2096 obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(lat_ms))));
2097 obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2098 1000u64,
2099 ))));
2100 });
2101 };
2102
2103 for _ in 0..20 {
2105 make_edge(&me, &a, 30);
2106 make_edge(&a, &b, 40);
2107 make_edge(&b, &dest, 50);
2108 }
2109
2110 graph.add_edge(&me, &a).unwrap();
2112 graph.add_edge(&a, &b).unwrap();
2113 graph.add_edge(&b, &dest).unwrap();
2114
2115 let selector = test_selector(me, graph, MAX_PATHS);
2116 let paths = selector.select_path(me, dest, 2).context("forward 2-hop path")?;
2117 assert!(!paths.is_empty());
2118
2119 let total = paths[0].total_latency_ms.expect("latency must be Some");
2120 assert!(
2121 (100..=130).contains(&total),
2122 "expected ~120ms total latency, got {total}ms"
2123 );
2124 Ok(())
2125 }
2126
2127 #[tokio::test]
2128 async fn path_metrics_fundable_tickets_floor_is_min() -> anyhow::Result<()> {
2129 let me = pubkey(&SECRET_0);
2130 let hop = pubkey(&SECRET_1);
2131 let dest = pubkey(&SECRET_2);
2132 let graph = ChannelGraph::new(me);
2133 graph.add_node(hop);
2134 graph.add_node(dest);
2135
2136 graph.set_ticket_face_value(hopr_api::graph::traits::Balance::one());
2140
2141 graph.upsert_edge(&me, &hop, |obs| {
2142 obs.record(EdgeWeightType::Connected(true));
2143 obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(50))));
2144 obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2145 500u64,
2146 ))));
2147 });
2148 graph.upsert_edge(&hop, &dest, |obs| {
2149 obs.record(EdgeWeightType::Connected(true));
2150 obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(50))));
2151 obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2152 200u64,
2153 ))));
2154 });
2155 graph.add_edge(&me, &hop).unwrap();
2156 graph.add_edge(&hop, &dest).unwrap();
2157
2158 let selector = test_selector(me, graph, MAX_PATHS);
2159 let paths = selector.select_path(me, dest, 1).context("1-hop path")?;
2160 assert!(!paths.is_empty());
2161 assert_eq!(
2162 paths[0].fundable_tickets_floor,
2163 Some(200),
2164 "floor must be the smaller of 500 and 200"
2165 );
2166 Ok(())
2167 }
2168
2169 #[tokio::test]
2170 async fn starved_first_hop_channel_must_not_be_selected() -> anyhow::Result<()> {
2171 let me = pubkey(&SECRET_0);
2179 let relay = pubkey(&SECRET_1);
2180 let dest = pubkey(&SECRET_2);
2181
2182 let face = hopr_api::graph::traits::Balance::from(100u64);
2184
2185 let build = |first_hop_balance: u64| {
2186 let graph = ChannelGraph::new(me);
2187 graph.add_node(relay);
2188 graph.add_node(dest);
2189 graph.set_ticket_face_value(face);
2190 graph.upsert_edge(&me, &relay, |obs| {
2192 obs.record(EdgeWeightType::Connected(true));
2193 obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(50))));
2194 obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(50))));
2195 obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2196 first_hop_balance,
2197 ))));
2198 });
2199 mark_edge_full(&graph, &relay, &dest);
2201 graph.add_edge(&me, &relay).unwrap();
2202 graph.add_edge(&relay, &dest).unwrap();
2203 graph
2204 };
2205
2206 let funded = test_selector(me, build(10_000), MAX_PATHS);
2209 let healthy = funded.select_path(me, dest, 1).context("funded first hop must route")?;
2210 assert!(!healthy.is_empty(), "a funded first hop must be selectable");
2211 assert_eq!(healthy[0].path.first(), Some(&relay), "route must go via the relay");
2212
2213 let starved = test_selector(me, build(50), MAX_PATHS);
2215 let result = starved.select_path(me, dest, 1);
2216 assert!(
2217 matches!(result, Err(PathPlannerError::Path(PathError::PathNotFound(..)))),
2218 "a first hop that cannot fund a single ticket must not be selected, got: {result:?}"
2219 );
2220 Ok(())
2221 }
2222
2223 #[tokio::test]
2224 async fn first_hop_funded_for_one_ticket_is_selectable() -> anyhow::Result<()> {
2225 let me = pubkey(&SECRET_0);
2230 let relay = pubkey(&SECRET_1);
2231 let dest = pubkey(&SECRET_2);
2232
2233 let face = hopr_api::graph::traits::Balance::from(100u64);
2236 let graph = ChannelGraph::new(me);
2237 graph.add_node(relay);
2238 graph.add_node(dest);
2239 graph.set_ticket_face_value(face);
2240 graph.upsert_edge(&me, &relay, |obs| {
2241 obs.record(EdgeWeightType::Connected(true));
2242 obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(50))));
2243 obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(50))));
2244 obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2245 150u64,
2246 ))));
2247 });
2248 mark_edge_full(&graph, &relay, &dest);
2249 graph.add_edge(&me, &relay).unwrap();
2250 graph.add_edge(&relay, &dest).unwrap();
2251
2252 let selector = test_selector(me, graph, MAX_PATHS);
2253 let paths = selector
2254 .select_path(me, dest, 1)
2255 .context("a first hop funded for one winning ticket must route")?;
2256 assert!(
2257 !paths.is_empty(),
2258 "a first hop funded for one winning ticket must be selectable"
2259 );
2260 assert_eq!(paths[0].path.first(), Some(&relay), "route must go via the relay");
2261 Ok(())
2262 }
2263
2264 #[tokio::test]
2265 async fn starved_intermediate_hop_via_extended_search_must_not_be_selected() -> anyhow::Result<()> {
2266 let me = pubkey(&SECRET_0);
2272 let a = pubkey(&SECRET_1);
2273 let b = pubkey(&SECRET_2);
2274 let dest = pubkey(&SECRET_3);
2275
2276 let face = hopr_api::graph::traits::Balance::from(100u64);
2277
2278 let build = |second_hop_balance: u64| {
2279 let graph = ChannelGraph::new(me);
2280 for n in [a, b, dest] {
2281 graph.add_node(n);
2282 }
2283 graph.set_ticket_face_value(face);
2284 graph.upsert_edge(&me, &a, |obs| {
2286 obs.record(EdgeWeightType::Connected(true));
2287 obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(50))));
2288 obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(50))));
2289 obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2290 10_000u64,
2291 ))));
2292 });
2293 graph.upsert_edge(&a, &b, |obs| {
2295 obs.record(EdgeWeightType::Connected(true));
2296 obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(50))));
2297 obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(50))));
2298 obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2299 second_hop_balance,
2300 ))));
2301 });
2302 graph.add_edge(&me, &a).unwrap();
2304 graph.add_edge(&a, &b).unwrap();
2305 graph
2306 };
2307
2308 let funded = test_selector(me, build(10_000), MAX_PATHS);
2310 let healthy = funded
2311 .select_path(me, dest, 2)
2312 .context("funded second hop must route")?;
2313 assert!(!healthy.is_empty(), "a funded second hop must be selectable");
2314 assert_eq!(healthy[0].path.first(), Some(&a), "route must start at the first relay");
2315
2316 let starved = test_selector(me, build(50), MAX_PATHS);
2318 let result = starved.select_path(me, dest, 2);
2319 assert!(
2320 matches!(result, Err(PathPlannerError::Path(PathError::PathNotFound(..)))),
2321 "a monetized intermediate hop that cannot fund a ticket must not be selected, got: {result:?}"
2322 );
2323 Ok(())
2324 }
2325
2326 #[test]
2331 fn path_cost_equality_ignores_quality_metadata() {
2333 let cost = PathCostWithMetrics {
2334 cost: 0.5,
2335 total_latency_ms: None,
2336 min_probe_success_rate: None,
2337 min_ack_rate: None,
2338 fundable_tickets_floor: None,
2339 };
2340 let measured = PathCostWithMetrics {
2341 total_latency_ms: Some(100),
2342 min_probe_success_rate: Some(0.9),
2343 min_ack_rate: Some(0.8),
2344 fundable_tickets_floor: Some(3),
2345 ..cost.clone()
2346 };
2347 assert_eq!(cost, measured);
2348 assert_ne!(cost, PathCostWithMetrics { cost: 0.6, ..measured });
2349 }
2350
2351 #[test]
2352 fn trace_diagnostics_preserve_the_selected_candidates() -> anyhow::Result<()> {
2354 let (me, _, dest, graph) = two_hop_graph();
2355 let selector = test_selector(me, graph, MAX_PATHS);
2356 let expected = selector.select_path(me, dest, 1)?;
2357 let subscriber = test_log::tracing_subscriber::fmt()
2358 .with_max_level(tracing::Level::TRACE)
2359 .with_writer(std::io::sink)
2360 .finish();
2361 let actual = tracing::subscriber::with_default(subscriber, || selector.select_path(me, dest, 1))?;
2362 assert_eq!(actual.len(), expected.len());
2363 assert_eq!(actual[0].path, expected[0].path);
2364 assert_eq!(actual[0].cost, expected[0].cost);
2365 Ok(())
2366 }
2367
2368 #[test]
2369 fn observer_sees_real_search_phases_and_empty_searches() -> anyhow::Result<()> {
2371 let (me, _, dest, graph) = two_hop_graph();
2372 let events = Arc::new(parking_lot::Mutex::new(Vec::new()));
2373 let selector = HoprGraphPathSelector::new(me, graph, MAX_PATHS, 0.5, 0.5, 0).with_observer(Arc::new({
2374 let events = events.clone();
2375 move |event| events.lock().push(event)
2376 }));
2377 selector.select_path(me, dest, 1)?;
2378 assert!(selector.select_path(pubkey(&SECRET_4), me, 1).is_err());
2379
2380 let events = events.lock();
2381 assert_eq!(events.len(), 2, "one event per search, and no resolve is invented");
2382 let searches: Vec<_> = events
2383 .iter()
2384 .filter_map(|event| match event {
2385 TransportEvent::PathSearched {
2386 phase1,
2387 phase2,
2388 retained,
2389 ..
2390 } => Some((*phase1, *phase2, *retained)),
2391 _ => None,
2392 })
2393 .collect();
2394 assert_eq!(searches.len(), 2);
2395 assert_eq!(1, searches.iter().filter(|(_, _, retained)| *retained == 0).count());
2396 assert!(searches.iter().any(|(phase1, ..)| phase1.returned > 0));
2397 assert!(searches.iter().any(|(_, phase2, _)| phase2.is_some()));
2398 Ok(())
2399 }
2400
2401 fn mesh_graph(
2407 relayers: usize,
2408 tickets: impl Fn(u64) -> u64,
2409 ) -> (
2410 OffchainPublicKey,
2411 OffchainPublicKey,
2412 Vec<OffchainPublicKey>,
2413 ChannelGraph,
2414 ) {
2415 const FACE_VALUE: u64 = 100;
2416 let me = pubkey(&SECRET_0);
2417 let dest = pubkey(&SECRET_1);
2418 let relays = (0..relayers)
2419 .map(|_| *OffchainKeypair::random().public())
2420 .collect::<Vec<_>>();
2421 let graph = ChannelGraph::new(me);
2422 graph.set_ticket_face_value(hopr_api::graph::traits::Balance::from(FACE_VALUE));
2423 graph.add_node(dest);
2424 relays.iter().for_each(|r| graph.add_node(*r));
2425
2426 let mut n = 0u64;
2427 let mut link = |a: &OffchainPublicKey, b: &OffchainPublicKey| {
2428 n += 1;
2429 graph.add_edge(a, b).unwrap();
2430 graph.upsert_edge(a, b, |obs| {
2431 obs.record(EdgeWeightType::Connected(true));
2432 obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(10 + n % 7 * 13))));
2433 obs.record(EdgeWeightType::Intermediate(Ok(Duration::from_millis(20 + n % 5 * 17))));
2434 obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2435 tickets(n.wrapping_mul(2_654_435_761) >> 7) * FACE_VALUE,
2436 ))));
2437 });
2438 };
2439 for r in &relays {
2440 link(&me, r);
2441 link(r, &me);
2442 link(&dest, r);
2443 link(r, &dest);
2444 for s in relays.iter().filter(|s| *s != r) {
2445 link(r, s);
2446 }
2447 }
2448 (me, dest, relays, graph)
2449 }
2450
2451 fn metrics_fn(
2452 graph: &ChannelGraph,
2453 length: std::num::NonZeroUsize,
2454 forward: bool,
2455 ) -> MetricsValueFn<<ChannelGraph as NetworkGraphTraverse>::Observed> {
2456 let cfg = PathPlannerConfig::default();
2457 let face = graph.ticket_face_value();
2458 MetricsValueFn {
2459 inner: if forward {
2460 EdgeValueFn::forward(length, cfg.edge_penalty, cfg.min_ack_rate, face)
2461 } else {
2462 EdgeValueFn::returning(length, cfg.edge_penalty, cfg.min_ack_rate, face)
2463 },
2464 ticket_face_value: face,
2465 }
2466 }
2467
2468 fn first_relayers(paths: &[PathWithMetrics]) -> std::collections::HashSet<OffchainPublicKey> {
2469 paths.iter().filter_map(|p| p.path.first().copied()).collect()
2470 }
2471
2472 #[rstest::rstest]
2474 #[case::forward(true)]
2475 #[case::returning(false)]
2476 fn observer_counts_spread_candidates_before_the_pool_limit(#[case] forward: bool) -> anyhow::Result<()> {
2477 let (me, dest, relays, graph) = mesh_graph(7, |_| 1000);
2478 let (src, dst) = if forward { (me, dest) } else { (dest, me) };
2479 let events = Arc::new(parking_lot::Mutex::new(Vec::new()));
2480 let cfg = PathPlannerConfig::default();
2481 let selector =
2482 HoprGraphPathSelector::new(me, graph, 4, cfg.edge_penalty, cfg.min_ack_rate, 0).with_observer(Arc::new({
2483 let events = events.clone();
2484 move |event| events.lock().push(event)
2485 }));
2486
2487 let paths = selector.select_path(src, dst, 1)?;
2488 assert_eq!(paths.len(), 4);
2489 assert_eq!(distinct_first_relayers(&paths), 4);
2490 let events = events.lock();
2491 assert_eq!(events.len(), 1);
2492 let TransportEvent::PathSearched {
2493 direction,
2494 phase1,
2495 phase2,
2496 retained,
2497 ..
2498 } = &events[0]
2499 else {
2500 anyhow::bail!("expected a path search event");
2501 };
2502 assert_eq!(
2503 *direction,
2504 if forward {
2505 PathDirection::Forward
2506 } else {
2507 PathDirection::Return
2508 }
2509 );
2510 assert_eq!(phase1.returned, relays.len() as u64);
2511 assert_eq!(phase1.eligible, paths.len() as u64);
2512 assert!(phase2.is_none());
2513 assert_eq!(*retained, paths.len() as u64);
2514 Ok(())
2515 }
2516
2517 #[rstest::rstest]
2520 #[case::forward(true)]
2521 #[case::returning(false)]
2522 fn a_spread_pool_should_name_every_first_relayer_where_one_traversal_named_two(
2523 #[case] forward: bool,
2524 ) -> anyhow::Result<()> {
2525 let (me, dest, relays, graph) = mesh_graph(7, |_| 1000);
2526 let (src, dst) = if forward { (me, dest) } else { (dest, me) };
2527 let length = std::num::NonZeroUsize::new(4).context("non-zero")?;
2528
2529 let (single, _) = compute_paths(&graph, &src, &dst, length, 50, metrics_fn(&graph, length, forward));
2530 assert!(
2531 first_relayers(&single).len() <= 2,
2532 "30 paths per first relayer, cut at 50"
2533 );
2534
2535 let (spread, _) = compute_paths_spread(&graph, &src, &dst, length, 50, metrics_fn(&graph, length, forward));
2536 assert!(spread.len() <= 50);
2537 assert_eq!(relays.len(), first_relayers(&spread).len());
2538 for p in &spread {
2539 assert_eq!(4, p.path.len());
2540 assert_eq!(Some(&dst), p.path.last());
2541 assert!(
2542 !p.path.contains(&src),
2543 "a path must not run back through its source: {:?}",
2544 p.path
2545 );
2546 let distinct = p.path.iter().collect::<std::collections::HashSet<_>>();
2547 assert_eq!(p.path.len(), distinct.len(), "a path must be simple: {:?}", p.path);
2548 }
2549 Ok(())
2550 }
2551
2552 #[rstest::rstest]
2556 #[case::forward(true)]
2557 #[case::returning(false)]
2558 fn a_spread_pool_should_value_each_path_as_one_traversal_does(#[case] forward: bool) -> anyhow::Result<()> {
2559 let (me, dest, _, graph) = mesh_graph(5, |n| 1 + n % 4);
2560 let (src, dst) = if forward { (me, dest) } else { (dest, me) };
2561
2562 for hops in 1..=3 {
2563 let length = std::num::NonZeroUsize::new(hops + 1).context("non-zero")?;
2564 let key = |p: &PathWithMetrics| {
2565 format!(
2566 "{:?} {} {:?} {:?} {:?} {:?}",
2567 p.path,
2568 p.cost,
2569 p.total_latency_ms,
2570 p.min_probe_success_rate,
2571 p.min_ack_rate,
2572 p.fundable_tickets_floor
2573 )
2574 };
2575 let mut all = compute_paths(
2576 &graph,
2577 &src,
2578 &dst,
2579 length,
2580 usize::MAX,
2581 metrics_fn(&graph, length, forward),
2582 )
2583 .0
2584 .iter()
2585 .map(key)
2586 .collect::<Vec<_>>();
2587 let mut spread =
2588 compute_paths_spread(&graph, &src, &dst, length, 10_000, metrics_fn(&graph, length, forward))
2589 .0
2590 .iter()
2591 .map(key)
2592 .collect::<Vec<_>>();
2593 all.sort();
2594 spread.sort();
2595 assert!(!all.is_empty(), "{hops} hops: the mesh must route");
2596 let simple_paths = (5 - hops + 1..=5).product::<usize>();
2598 if hops > 1 {
2599 assert!(all.len() < simple_paths, "{hops} hops: funding must reject some paths");
2600 }
2601 assert_eq!(all, spread, "{hops} hops");
2602 }
2603 Ok(())
2604 }
2605
2606 #[test]
2608 fn a_spread_pool_cut_short_should_keep_distinct_first_relayers() -> anyhow::Result<()> {
2609 let (me, dest, _, graph) = mesh_graph(7, |_| 1000);
2610 let length = std::num::NonZeroUsize::new(3).context("non-zero")?;
2611
2612 let (spread, _) = compute_paths_spread(&graph, &dest, &me, length, 4, metrics_fn(&graph, length, false));
2613 assert_eq!(4, spread.len());
2614 assert_eq!(4, first_relayers(&spread).len());
2615 Ok(())
2616 }
2617
2618 #[rstest::rstest]
2623 #[case::forward(true)]
2624 #[case::returning(false)]
2625 fn a_spread_pool_should_fill_each_share_with_paths_that_avoid_the_source(
2626 #[case] forward: bool,
2627 ) -> anyhow::Result<()> {
2628 let (me, dest, relays, graph) = mesh_graph(7, |_| 1000);
2629 let (src, dst) = if forward { (me, dest) } else { (dest, me) };
2630 let length = std::num::NonZeroUsize::new(4).context("non-zero")?;
2631
2632 let per_relayer = 2;
2633 let take = per_relayer * relays.len();
2634 let (spread, _) = compute_paths_spread(&graph, &src, &dst, length, take, metrics_fn(&graph, length, forward));
2635 assert!(
2636 spread.iter().all(|p| !p.path.contains(&src)),
2637 "a path must not run back through its source"
2638 );
2639 assert_eq!(
2640 take,
2641 spread.len(),
2642 "every share filled with paths that avoid the source"
2643 );
2644 for relayer in &relays {
2645 assert_eq!(
2646 per_relayer,
2647 spread.iter().filter(|p| p.path.first() == Some(relayer)).count(),
2648 "each first relayer keeps its whole share"
2649 );
2650 }
2651
2652 let (cut_short, _) = compute_paths_spread(&graph, &src, &dst, length, 4, metrics_fn(&graph, length, forward));
2654 assert_eq!(4, cut_short.len());
2655 assert_eq!(4, first_relayers(&cut_short).len());
2656 Ok(())
2657 }
2658
2659 #[test]
2662 fn a_share_search_should_stop_after_its_last_doubling() {
2663 let mut limits = Vec::new();
2664 let found = search_share(
2665 3,
2666 |unusable: &bool| *unusable,
2667 |limit| {
2668 limits.push(limit);
2669 vec![true; limit]
2670 },
2671 );
2672 assert_eq!(vec![3, 6, 12, 24], limits);
2673 assert!(found.iter().all(|unusable| *unusable), "nothing to keep");
2674 }
2675
2676 #[test]
2679 fn a_share_search_should_stop_once_enough_are_usable_or_the_subtree_runs_out() {
2680 let mut limits = Vec::new();
2682 let found = search_share(
2683 4,
2684 |unusable: &bool| *unusable,
2685 |limit| {
2686 limits.push(limit);
2687 (0..limit).map(|i| i % 2 == 0).collect()
2688 },
2689 );
2690 assert_eq!(vec![4, 8], limits);
2691 assert_eq!(4, found.iter().filter(|unusable| !**unusable).count());
2692
2693 let subtree = [true, false, true, false, true];
2695 let mut limits = Vec::new();
2696 let found = search_share(
2697 4,
2698 |unusable: &bool| *unusable,
2699 |limit| {
2700 limits.push(limit);
2701 subtree.iter().copied().take(limit).collect()
2702 },
2703 );
2704 assert_eq!(vec![4, 8], limits);
2705 assert_eq!(subtree.to_vec(), found);
2706 }
2707
2708 #[rstest::rstest]
2714 #[case::forward(true)]
2715 #[case::returning(false)]
2716 fn a_spread_pool_should_fill_each_share_with_paths_of_value(#[case] forward: bool) -> anyhow::Result<()> {
2717 let (me, dest, relays, graph) = mesh_graph(7, |_| 1000);
2718 for r in &relays {
2721 for (a, b) in [(me, *r), (*r, me)] {
2722 graph.upsert_edge(&a, &b, |obs| {
2723 obs.record(EdgeWeightType::ImmediateProtocolConformance {
2724 num_packets: 100,
2725 num_acks: 100,
2726 });
2727 });
2728 }
2729 }
2730 for _ in 0..6 {
2731 let unprobed = *OffchainKeypair::random().public();
2732 graph.add_node(unprobed);
2733 for r in &relays {
2735 graph.add_edge(r, &unprobed)?;
2736 graph.upsert_edge(r, &unprobed, |obs| {
2737 obs.record(EdgeWeightType::Connected(true));
2738 obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
2739 1000 * 100,
2740 ))));
2741 });
2742 }
2743 graph.add_edge(&unprobed, &dest)?;
2745 graph.add_edge(&unprobed, &me)?;
2746 graph.upsert_edge(&unprobed, &me, |obs| obs.record(EdgeWeightType::Connected(true)));
2747 }
2748 let (src, dst) = if forward { (me, dest) } else { (dest, me) };
2749 let length = std::num::NonZeroUsize::new(3).context("non-zero")?;
2750 let no_penalty = || {
2751 let (cfg, face) = (PathPlannerConfig::default(), graph.ticket_face_value());
2752 MetricsValueFn {
2753 inner: if forward {
2754 EdgeValueFn::forward(length, 0.0, cfg.min_ack_rate, face)
2755 } else {
2756 EdgeValueFn::returning(length, 0.0, cfg.min_ack_rate, face)
2757 },
2758 ticket_face_value: face,
2759 }
2760 };
2761 let take = 6 * relays.len();
2762 let (of_value, of_no_value): (Vec<_>, Vec<_>) = graph
2763 .simple_paths(&src, &dst, length.get(), None, no_penalty())
2764 .into_iter()
2765 .partition(|(.., metrics)| metrics.cost > 0.0);
2766 assert_eq!(
2767 take,
2768 of_value.len(),
2769 "the probed relayers carry 6 paths of value per first relayer"
2770 );
2771 assert_eq!(
2772 take,
2773 of_no_value.len(),
2774 "the unprobed relayers carry as many of no value"
2775 );
2776
2777 let (spread, returned) = compute_paths_spread(&graph, &src, &dst, length, take, no_penalty());
2778 assert!(spread.iter().all(|p| p.cost > 0.0), "a path of no value is dropped");
2779 assert_eq!(take, spread.len(), "every share filled with paths of value");
2780 assert!(returned > spread.len(), "diagnostics also count unusable continuations");
2781 Ok(())
2782 }
2783
2784 #[tokio::test]
2787 async fn a_three_hop_pool_should_name_every_first_relayer_in_both_directions() -> anyhow::Result<()> {
2788 let (me, dest, relays, graph) = mesh_graph(7, |_| 1000);
2789 let cfg = PathPlannerConfig::default();
2790 let selector =
2791 HoprGraphPathSelector::new(me, graph, cfg.max_cached_paths, cfg.edge_penalty, cfg.min_ack_rate, 0);
2792
2793 let forward = selector.select_path(me, dest, 3).context("forward pool")?;
2794 assert_eq!(relays.len(), distinct_first_relayers(&forward));
2795 let returning = selector.select_path(dest, me, 3).context("return pool")?;
2796 assert_eq!(relays.len(), distinct_first_relayers(&returning));
2797 Ok(())
2798 }
2799}