1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
use std::collections::HashSet;
use wot_network::{Certificate, search::TrustAnchor as WotTrustAnchor};
use crate::types::edges::{Delegation, ReverseEdge, UsedEdge};
#[cfg(doc)]
use crate::types::path::Path;
/// A certificate that acts as a root of trust in a Web of Trust search
#[derive(Debug, Clone, Eq, Hash, PartialEq)]
pub struct TrustAnchor {
pub inner: WotTrustAnchor,
pub used_amount: u8,
}
impl TrustAnchor {
/// Create a new TrustAnchor from a [`wot_network::search::TrustAnchor`].
pub fn new(anchor: WotTrustAnchor) -> Self {
Self {
inner: anchor,
used_amount: 0,
}
}
/// Returns the remaining trust capacity that can be provided by this anchor.
pub fn available_amount(&self) -> u8 {
self.inner.trust_amount.saturating_sub(self.used_amount)
}
}
#[derive(Debug, Clone)]
pub(crate) struct Node {
/// The certificate that this node represents.
pub(crate) id: Certificate,
/// The delegations that point towards this node.
///
/// The list of delegations is static, although each `Delegation`'s value may be adjusted when
/// some trust amount of the delegation is used.
pub(crate) delegations: Vec<Delegation>,
/// The reverse edges that point towards this node.
///
/// At the beginning of the algorithm, this list is empty.
/// [`ReverseEdge`]s are created as paths along [`Delegation`]s are found.
///
/// Ford-Fulkerson creates "reverse edges" whenever flow is allocated in a path.
/// This allows the algorithm to backtrack any allocated flow amounts to find alternative
/// paths.
pub(crate) reverse_edges: Vec<ReverseEdge>,
/// The maximum amount of trust that can be directed through this node.
///
/// This is a static property of this node.
pub(crate) allowed_amount: u8,
/// The amount of trust that has already been directed through this node.
///
/// This variable persists and is updated between steps.
pub(crate) used_amount: u8,
/// BFS path finding related info.
///
/// This field is set to [`EdgeSearchInfo::Some`], whenever a valid path to this `Node` is
/// found during pathfinding and remains [`EdgeSearchInfo::None`] as long as no path is
/// discovered. The data in [`EdgeSearchInfo::Some`] contains information on how to reach
/// the "next" (target) node, when walking through the path, which is being build right
/// now, in forward direction.
/// And from a BFS perspective, which discovers from the end to the beginning, this is the
/// "previous" node on the path that was discovered by the algorithm.
///
/// After every step, this info is reset to [`EdgeSearchInfo::None`].
pub(crate) path_info: EdgeSearchInfo,
}
impl Node {
/// Constructs a new [`Node`] with the specified certificate and associated delegations.
pub fn new(id: Certificate, delegations: Vec<Delegation>) -> Self {
Node {
id,
delegations,
reverse_edges: Vec::new(),
used_amount: 0,
allowed_amount: 120,
path_info: EdgeSearchInfo::None,
}
}
/// Returns the remaining trust capacity that can be directed through this node.
pub fn available_amount(&self) -> u8 {
self.allowed_amount.saturating_sub(self.used_amount)
}
}
/// Holds state related to BFS search on [`Node`]s.
/// See the documentation for [`EdgeSearchInfo::Some`] for details.
#[derive(Debug, Clone)]
pub(crate) enum EdgeSearchInfo {
None,
/// This variant holds all BFS runtime related data for **the current** step.
///
/// See [`Node::path_info`] on where and how this is used.
Some {
/// The maximum trust amount throughput that has been found via a path towards this node
current_amount: u8,
/// `target` saves a reference to the target node along the path.
/// Since we're searching from the target, and we're walking the edges in reverse
/// direction, it's the "previous" node from the BFS perspective, but the "next"
/// node from a graph perspective.
target: Certificate,
/// We need to know which type of edge, and which **exact** edge has been used to reach
/// this node. Due to performing backwards search, the edges are saved on the `target` and
/// not the issuer. When assembling the path, we need to walk forward, which is why we need
/// both the target node and the type+index of edge on that target node.
/// The [`UsedEdge`] type encapsulates this data.
///
/// In natural language, this is used to perform the following operation:
/// "The next node is the one with the id `target` and you can reach `self` from
/// that node by taking the nth edge of type `UsedEdge`. `nth` being the `usize`
/// inside the UsedEdge."
used_edge: UsedEdge,
/// `path_length` is a variable used during pathfinding of the current step.
///
/// It saves the length from the target node to this [`Node`]. Since our BFS ensures that
/// we always prefer the shortest path, `path_length` is the shortest path to the target
/// binding for the current residual network.
path_length: usize,
/// To prevent cycling along the path, we have to keep track of what paths were visited up
/// to this point.
///
/// Due to the nature of reverse edges, path lengths are "reset" due to the simulation of
/// rerouting traffic when using a reverse edge. This can result in backtracking onto a
/// node that was already visited along the current path.
visited_nodes: HashSet<Certificate>,
},
}
impl EdgeSearchInfo {
/// Returns true if this is [`EdgeSearchInfo::Some`].
pub fn is_some(&self) -> bool {
match self {
EdgeSearchInfo::None => false,
EdgeSearchInfo::Some { .. } => true,
}
}
/// Returns the current trust amount if `self` is [`EdgeSearchInfo::Some`].
pub fn current_amount(&self) -> Option<u8> {
match self {
EdgeSearchInfo::None => None,
EdgeSearchInfo::Some { current_amount, .. } => Some(*current_amount),
}
}
/// Returns the current path length if `self` is [`EdgeSearchInfo::Some`].
pub fn path_length(&self) -> Option<usize> {
match self {
EdgeSearchInfo::None => None,
EdgeSearchInfo::Some { path_length, .. } => Some(*path_length),
}
}
}