lib.rs 11 KB
Newer Older
1
//! Represents a clients'-eye view of the Tor network.
2
3
4
//!
//! The tor-netdir crate wraps objects from tor-netdoc, and combines
//! them to provide a unified view of the relays on the network.
5
6
//! It is responsible for representing a client's knowledge of the
//! network's state and who is on it.
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//!
//! # Limitations
//!
//! Right now, this code doesn't fetch network information: instead,
//! it looks in a local Tor cache directory.
//!
//! Only modern consensus methods and microdescriptor consensuses are
//! supported.
//!
//! TODO: Eventually, there should be the ability to download
//! directory information and store it, but that should probably be
//! another module.

#![deny(missing_docs)]
21
22
#![deny(clippy::missing_docs_in_private_items)]

23
mod err;
24
pub mod fallback;
25
mod pick;
26

27
28
29
use ll::pk::rsa::RSAIdentity;
use tor_llcrypto as ll;
use tor_netdoc::doc::microdesc::{MDDigest, Microdesc};
30
use tor_netdoc::doc::netstatus::{self, MDConsensus};
31
32
33
34

use std::collections::HashMap;

pub use err::Error;
35
/// A Result using the Error type from the tor-netdir crate
36
37
pub type Result<T> = std::result::Result<T, Error>;

38
39
40
/// Internal: how should we find the base weight of each relay?  This
/// value is global over a whole directory, and depends on the bandwidth
/// weights in the consensus.
41
#[derive(Copy, Clone, Debug)]
42
enum WeightFn {
43
44
    /// There are no weights at all in the consensus: weight every
    /// relay as 1.
Nick Mathewson's avatar
Nick Mathewson committed
45
    Uniform,
46
47
    /// There are no measured weights in the consensus: count
    /// unmeasured weights as the weights for relays.
Nick Mathewson's avatar
Nick Mathewson committed
48
    IncludeUnmeasured,
49
    /// There are measured relays in the consensus; only use those.
Nick Mathewson's avatar
Nick Mathewson committed
50
    MeasuredOnly,
51
52
}

53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
impl WeightFn {
    /// Apply this weight function to the measured or unmeasured bandwidth
    /// of a single router.
    fn apply(&self, w: &netstatus::RouterWeight) -> u32 {
        use netstatus::RouterWeight::*;
        use WeightFn::*;
        match (self, w) {
            (Uniform, _) => 1,
            (IncludeUnmeasured, Unmeasured(u)) => *u,
            (IncludeUnmeasured, Measured(u)) => *u,
            (MeasuredOnly, Unmeasured(_)) => 0,
            (MeasuredOnly, Measured(u)) => *u,
        }
    }
}

69
70
71
72
73
74
75
76
77
78
79
/// Internal type: wraps Option<Microdesc> to prevent confusion.
///
/// (Having an Option type be the value of a HashMap makes things a
/// bit confused IMO.)
#[derive(Clone, Debug, Default)]
struct MDEntry {
    /// The microdescriptor in this entry, or None if a microdescriptor
    /// is wanted but not present.
    md: Option<Microdesc>,
}

80
81
/// A view of the Tor directory, suitable for use in building
/// circuits.
82
#[derive(Debug, Clone)]
83
pub struct NetDir {
84
85
86
    /// A microdescriptor consensus that lists the members of the network,
    /// and maps each one to a 'microdescriptor' that has more information
    /// about it
87
    consensus: MDConsensus,
88
    /// Map from SHA256 digest of microdescriptors to the
89
90
    /// microdescriptors themselves.
    mds: HashMap<MDDigest, MDEntry>,
91
92
    /// Value describing how to find the weight to use when picking a
    /// router by weight.
93
    weight_fn: WeightFn,
94
}
95

96
97
/// A partially build NetDir -- it can't be unwrapped until it has
/// enough information to build safe paths.
98
#[derive(Debug, Clone)]
99
100
101
102
103
pub struct PartialNetDir {
    /// The netdir that's under construction.
    netdir: NetDir,
}

104
/// A view of a relay on the Tor network, suitable for building circuits.
Nick Mathewson's avatar
Nick Mathewson committed
105
106
107
108
// TODO: This should probably be a more specific struct, with a trait
// that implements it.
#[allow(unused)]
pub struct Relay<'a> {
109
    /// A router descriptor for this relay.
Nick Mathewson's avatar
Nick Mathewson committed
110
    rs: &'a netstatus::MDConsensusRouterStatus,
111
    /// A microdescriptor for this relay.
112
113
114
115
116
117
118
119
120
    md: &'a Microdesc,
}

/// A relay that we haven't checked for validity or usability in
/// routing.
struct UncheckedRelay<'a> {
    /// A router descriptor for this relay.
    rs: &'a netstatus::MDConsensusRouterStatus,
    /// A microdescriptor for this relay, if there is one.
Nick Mathewson's avatar
Nick Mathewson committed
121
122
123
    md: Option<&'a Microdesc>,
}

124
125
126
127
128
129
130
131
132
133
134
135
/// A partial or full network directory that we can download
/// microdescriptors for.
pub trait MDReceiver {
    /// Return an iterator over the digests for all of the microdescriptors
    /// that this netdir is missing.
    fn missing_microdescs(&self) -> Box<dyn Iterator<Item = &MDDigest> + '_>;
    /// Add a microdescriptor to this netdir, if it was wanted.
    ///
    /// Return true if it was indeed wanted.
    fn add_microdesc(&mut self, md: Microdesc) -> bool;
}

136
impl PartialNetDir {
137
138
    /// Create a new PartialNetDir with a given consensus, and no
    /// microdecriptors loaded.
139
    pub fn new(consensus: MDConsensus) -> Self {
140
141
142
143
144
145
146
147
148
149
150
151
        let weight_fn = pick_weight_fn(&consensus);
        let mut netdir = NetDir {
            consensus,
            mds: HashMap::new(),
            weight_fn,
        };

        for rs in netdir.consensus.routers().iter() {
            netdir.mds.insert(*rs.md_digest(), MDEntry::default());
        }
        PartialNetDir { netdir }
    }
152
153
    /// If this directory has enough information to build multihop
    /// circuits, return it.
154
    pub fn unwrap_if_sufficient(self) -> std::result::Result<NetDir, PartialNetDir> {
155
156
157
        if self.netdir.have_enough_paths() {
            Ok(self.netdir)
        } else {
158
            Err(self)
159
160
        }
    }
161
162
163
164
}

impl MDReceiver for PartialNetDir {
    fn missing_microdescs(&self) -> Box<dyn Iterator<Item = &MDDigest> + '_> {
165
166
        self.netdir.missing_microdescs()
    }
167
    fn add_microdesc(&mut self, md: Microdesc) -> bool {
168
169
        self.netdir.add_microdesc(md)
    }
170
171
}

Nick Mathewson's avatar
Nick Mathewson committed
172
impl NetDir {
173
174
    /// Construct a (possibly invalid) Relay object from a routerstatus and its
    /// microdescriptor (if any).
175
176
177
178
    fn relay_from_rs<'a>(
        &'a self,
        rs: &'a netstatus::MDConsensusRouterStatus,
    ) -> UncheckedRelay<'a> {
179
180
181
182
        let md = match self.mds.get(rs.md_digest()) {
            Some(MDEntry { md: Some(md) }) => Some(md),
            _ => None,
        };
183
        UncheckedRelay { rs, md }
Nick Mathewson's avatar
Nick Mathewson committed
184
    }
185
186
    /// Return an iterator over all Relay objects, including invalid ones
    /// that we can't use.
187
    fn all_relays(&self) -> impl Iterator<Item = UncheckedRelay<'_>> {
Nick Mathewson's avatar
Nick Mathewson committed
188
        self.consensus
189
            .routers()
Nick Mathewson's avatar
Nick Mathewson committed
190
191
192
            .iter()
            .map(move |rs| self.relay_from_rs(rs))
    }
193
    /// Return an iterator over all usable Relays.
Nick Mathewson's avatar
Nick Mathewson committed
194
    pub fn relays(&self) -> impl Iterator<Item = Relay<'_>> {
195
        self.all_relays().filter_map(UncheckedRelay::into_relay)
Nick Mathewson's avatar
Nick Mathewson committed
196
    }
197
198
199
200
201
202
203
    /// Return true if there is enough information in this NetDir to build
    /// multihop circuits.
    fn have_enough_paths(&self) -> bool {
        // TODO: Implement the real path-based algorithm.
        let mut total_bw = 0_u64;
        let mut have_bw = 0_u64;
        for r in self.all_relays() {
204
            let w = self.weight_fn.apply(r.rs.weight());
205
206
207
208
209
210
211
212
213
            total_bw += w as u64;
            if r.is_usable() {
                have_bw += w as u64;
            }
        }

        // TODO: Do a real calculation here.
        have_bw > (total_bw / 2)
    }
214
215
216
217
218
219
220
221
222
    /// Chose a relay at random.
    ///
    /// Each relay is chosen with probability proportional to a function
    /// `reweight` of the relay and its weight in the consensus.
    ///
    /// This function returns None if (and only if) there are no relays
    /// with nonzero weight.
    //
    // TODO: This API is powerful but tricky; there should be wrappers.
223
224
225
226
227
228
    pub fn pick_relay<'a, R, F>(&'a self, rng: &mut R, reweight: F) -> Option<Relay<'a>>
    where
        R: rand::Rng,
        F: Fn(&Relay<'a>, u32) -> u32,
    {
        pick::pick_weighted(rng, self.relays(), |r| {
229
            reweight(r, r.weight(self.weight_fn)) as u64
230
231
        })
    }
Nick Mathewson's avatar
Nick Mathewson committed
232
233
}

234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
impl MDReceiver for NetDir {
    fn missing_microdescs(&self) -> Box<dyn Iterator<Item = &MDDigest> + '_> {
        Box::new(self.consensus.routers().iter().filter_map(move |rs| {
            let d = rs.md_digest();
            match self.mds.get(d) {
                Some(MDEntry { md: Some(_) }) => None,
                _ => Some(d),
            }
        }))
    }
    fn add_microdesc(&mut self, md: Microdesc) -> bool {
        if let Some(entry) = self.mds.get_mut(md.digest()) {
            entry.md = Some(md);
            true
        } else {
            false
        }
    }
}

254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
/// Helper: Calculate the function we should use to find
/// initial relay weights.
fn pick_weight_fn(consensus: &MDConsensus) -> WeightFn {
    let routers = consensus.routers();
    let has_measured = routers.iter().any(|rs| rs.weight().is_measured());
    let has_nonzero = routers.iter().any(|rs| rs.weight().is_nonzero());
    if !has_nonzero {
        WeightFn::Uniform
    } else if !has_measured {
        WeightFn::IncludeUnmeasured
    } else {
        WeightFn::MeasuredOnly
    }
}

269
impl<'a> UncheckedRelay<'a> {
270
271
272
273
274
    /// Return true if this relay is valid and usable.
    ///
    /// This function should return `true` for every Relay we expose
    /// to the user.
    fn is_usable(&self) -> bool {
275
        // No need to check for 'valid' or 'running': they are implicit.
276
        self.md.is_some() && self.rs.ed25519_id_is_usable()
Nick Mathewson's avatar
Nick Mathewson committed
277
    }
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
    /// If this is usable, return a corresponding Relay object.
    fn into_relay(self) -> Option<Relay<'a>> {
        if self.is_usable() {
            Some(Relay {
                rs: self.rs,
                md: self.md.unwrap(),
            })
        } else {
            None
        }
    }
}

impl<'a> Relay<'a> {
    /// Return the Ed25519 ID for this relay.
    pub fn id(&self) -> &ll::pk::ed25519::Ed25519Identity {
        self.md.ed25519_id()
Nick Mathewson's avatar
Nick Mathewson committed
295
    }
296
    /// Return the RSAIdentity for this relay.
297
    pub fn rsa_id(&self) -> &RSAIdentity {
298
        self.rs.rsa_identity()
Nick Mathewson's avatar
Nick Mathewson committed
299
    }
300
301
302
    /// Return true if this relay and `other` seem to be the same relay.
    ///
    /// (Two relays are the same if they have the same identity.)
303
    pub fn same_relay<'b>(&self, other: &Relay<'b>) -> bool {
304
        self.id() == other.id() && self.rsa_id() == other.rsa_id()
305
    }
306
    /// Return true if this relay allows exiting to `port` on IPv4.
307
308
    // XXXX ipv4/ipv6
    pub fn supports_exit_port(&self, port: u16) -> bool {
309
310
311
312
313
314
315
316
317
318
319
        !self.rs.is_flagged_bad_exit() && self.md.ipv4_policy().allows_port(port)
    }
    /// Return true if this relay is suitable for use as a directory
    /// cache.
    pub fn is_dir_cache(&self) -> bool {
        use tor_protover::ProtoKind;
        self.rs.is_flagged_v2dir()
            && self
                .rs
                .protovers()
                .supports_known_subver(ProtoKind::DirCache, 2)
320
    }
321
    /// Return the weight of this Relay, according to `wf`.
322
    fn weight(&self, wf: WeightFn) -> u32 {
323
        wf.apply(self.rs.weight())
324
    }
Nick Mathewson's avatar
Nick Mathewson committed
325
}
326
327

impl<'a> tor_linkspec::ChanTarget for Relay<'a> {
328
329
    fn addrs(&self) -> &[std::net::SocketAddr] {
        self.rs.addrs()
330
    }
331
332
    fn ed_identity(&self) -> &ll::pk::ed25519::Ed25519Identity {
        self.id()
333
    }
334
    fn rsa_identity(&self) -> &RSAIdentity {
335
        self.rsa_id()
336
337
338
    }
}

339
impl<'a> tor_linkspec::CircTarget for Relay<'a> {
340
    fn ntor_onion_key(&self) -> &ll::pk::curve25519::PublicKey {
341
        self.md.ntor_key()
342
    }
343
    fn protovers(&self) -> &tor_protover::Protocols {
344
        self.rs.protovers()
345
346
    }
}