1
//! Functions and type for implementing the onion service directory ring.
2
//!
3
//! The onion service directory ring is an ordered ring of the all of relays in
4
//! the consensus with the HsDir flag. The HSDirs change their position in this
5
//! index every [`TimePeriod`], and every time that the shared random value in
6
//! the consensus changes.  (These events are typically synchronized, for
7
//! reasonable network configurations.)
8
//!
9
//! Each onion service is also (semi-privately) associated with "N" positions on
10
//! the ring based on its blinded ID and the current time period. When upload or
11
//! downloading an onion service descriptor descriptor, we look at the ring at
12
//! each of these positions, and consider the "S" relays that fall at that
13
//! position or later. ("N" is a "number of replicas" parameter, and "S" is a
14
//! "Spread" parameter.)
15

            
16
use std::collections::HashMap;
17
use std::fmt::Debug;
18

            
19
use derive_more::{AsRef, From, Into};
20
use digest::Digest;
21
use typed_index_collections::TiVec;
22

            
23
use tor_basic_utils::impl_debug_hex;
24
use tor_hscrypto::{pk::HsBlindId, time::TimePeriod};
25
use tor_llcrypto::d::Sha3_256;
26
use tor_llcrypto::pk::ed25519::Ed25519Identity;
27

            
28
use crate::hsdir_params::HsDirParams;
29
use crate::{NetDir, RouterStatusIdx};
30

            
31
/// A sort key determining a position in the onion service directory ring.
32
///
33
/// This is either the sort key of a given relay at a given time period, or the
34
/// sort key for a probing position for a given onion service id at a given
35
/// time.
36
///
37
/// The specification calls this an "index" but `HsDirIndex` is a key-length
38
/// sized, apparently-random, value, which determines the ordering of relays on
39
/// the ring. It is not the position number (ie, not a dense index starting at
40
/// 0).
41
///
42
/// Note that this is _not_ an index into any array; it is instead an index into
43
/// a space of possible values in a (virtual!) ring of 2^256 elements.
44
82375
#[derive(Copy, Clone, Eq, Hash, PartialEq, Ord, PartialOrd, AsRef)]
45
pub(crate) struct HsDirIndex(#[as_ref] [u8; 32]);
46

            
47
impl_debug_hex! { HsDirIndex .0 }
48

            
49
/// Position in the hsdir hash ring
50
///
51
/// This an "index" in the sense that you can use it to index `HsDirRing.ring`,
52
/// but in the spec, in the context of the hsdir,
53
/// "index" is used to the sort key - here, [`HsDirIndex`].
54
732
#[derive(Debug, From, Into, Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
55
pub(crate) struct HsDirPos(usize);
56

            
57
/// A hash ring as used in `NetDir`.
58
///
59
/// This type is immutable once constructed: entries cannot be added, changed,
60
/// or removed.  It can be interpreted only in the context of a given consensus
61
/// document.
62
#[derive(Clone, Debug)]
63
pub(crate) struct HsDirRing {
64
    /// The parameters (time period and shared random value)
65
    params: HsDirParams,
66

            
67
    /// The ring itself.
68
    ///
69
    /// The first element of each tuple is a 32-byte hash representing a
70
    /// position on the ring; the second is the index for the corresponding
71
    /// relay within self.consensus.relays().
72
    ///
73
    /// This vector is empty in a partial netdir; it is filled in when we
74
    /// convert to a complete netdir.
75
    ring: TiVec<HsDirPos, (HsDirIndex, RouterStatusIdx)>,
76
}
77

            
78
/// Compute the [`HsDirIndex`] for a given relay.
79
31670
pub(crate) fn relay_hsdir_index(
80
31670
    kp_relayid_ed: &Ed25519Identity,
81
31670
    params: &HsDirParams,
82
31670
) -> HsDirIndex {
83
31670
    // rend-spec-v3 2.2.3 "hsdir_index(node)"
84
31670
    //
85
31670
    // hsdir_index(node) = H("node-idx" | node_identity |
86
31670
    //      shared_random_value |
87
31670
    //      INT_8(period_num) |
88
31670
    //      INT_8(period_length) )
89
31670
    //
90
31670
    // Note that INT_8 means "u64" and H is sha3-256.
91
31670

            
92
31670
    let mut h = Sha3_256::default();
93
31670
    h.update(b"node-idx");
94
31670
    h.update(kp_relayid_ed.as_bytes());
95
31670
    h.update(params.shared_rand.as_ref());
96
31670
    h.update(params.time_period.interval_num().to_be_bytes());
97
31670
    h.update(u64::from(params.time_period.length().as_minutes()).to_be_bytes());
98
31670
    HsDirIndex(h.finalize().into())
99
31670
}
100

            
101
/// Compute the starting [`HsDirIndex`] for a given descriptor replica.
102
676
pub(crate) fn service_hsdir_index(
103
676
    kp_hs_blind_id: &HsBlindId,
104
676
    replica: u8,
105
676
    params: &HsDirParams,
106
676
) -> HsDirIndex {
107
676
    // rend-spec-v3 2.2.3 "hs_index(replicanum)"
108
676
    //
109
676
    // hs_index(replicanum) = H("store-at-idx" |
110
676
    //      blinded_public_key |
111
676
    //      INT_8(replicanum) |
112
676
    //      INT_8(period_length) |
113
676
    //      INT_8(period_num) )
114
676
    //
115
676
    // Note that INT_8 means "u64" and H is sha3-256
116
676

            
117
676
    let mut h = Sha3_256::new();
118
676
    h.update(b"store-at-idx");
119
676
    h.update(kp_hs_blind_id.as_ref());
120
676
    h.update(u64::from(replica).to_be_bytes());
121
676
    h.update(u64::from(params.time_period.length().as_minutes()).to_be_bytes());
122
676
    h.update(params.time_period.interval_num().to_be_bytes());
123
676
    HsDirIndex(h.finalize().into())
124
676
}
125

            
126
impl HsDirRing {
127
    /// Return a new empty HsDirRing from a given set of parameters.
128
3278
    pub(crate) fn empty_from_params(params: HsDirParams) -> Self {
129
3278
        Self {
130
3278
            params,
131
3278
            ring: TiVec::new(),
132
3278
        }
133
3278
    }
134

            
135
    /// Compute the HsDirRing
136
    ///
137
    /// Reuses existing hash calculations from a previous netdir, if available.
138
    ///
139
    /// `this_netdir.hsdir_rings` is not used; the return values from this function
140
    /// will be stored there by
141
    /// [`PartialNetDir::compute_rings`](super::PartialNetDir::compute_rings).
142
3194
    pub(crate) fn compute(
143
3194
        new_params: HsDirParams,
144
3194
        this_netdir: &NetDir,
145
3194
        prev_netdir: Option<&NetDir>,
146
3194
    ) -> Self {
147
3194
        // TODO: The ring itself can be a bit expensive to compute, so maybe we should
148
3194
        // make sure this happens in a separate task or something, and expose a
149
3194
        // way to do that?
150
3194
        // But: this is being done during netdir ingestion, which is already happening
151
3194
        // on the dirmgr task.  So I think this is fine?  -Diziet
152
3194

            
153
3194
        // We would like to avoid re-computing the hsdir indexes, since they're a hash
154
3194
        // each.  Instead, we look to see if our previous netdir contains a hash ring
155
3194
        // using the same parameters.  If so, we make a hashmap from relay identities
156
3194
        // to hsring_index positions _in the previous netdir_
157
3194
        // to reuse.
158
3194
        //
159
3194
        // TODO: Actually, the relays in the consensus are ordered by their RSA identity.
160
3194
        // So we could do a merge join on the previous and last relay lists, and avoid
161
3194
        // building this separate hashmap.  (We'd have to *check* that the ed25519 ids
162
3194
        // matched, but it would be OK to recompute the index values for relays that
163
3194
        // have a different correspondence between ed25519 and RSA ids in subsequent
164
3194
        // consensuses, since that's really not supposed to happen.
165
3194
        //
166
3194
        // However, that would involve tor-netdoc offering the ordering property as a
167
3194
        // *guarantee*.  It's also quite subtle.  This algorithm is O(N.log(N)) which
168
3194
        // is the same complexity as the (unavoidable) sort by hsdir_index.
169
3294
        let reuse_index_values: HashMap<&Ed25519Identity, &HsDirIndex> = (|| {
170
3194
            let prev_netdir = prev_netdir?;
171
            let prev_ring = prev_netdir
172
                .hsdir_rings
173
                .iter()
174
                .find(|prev_ring| prev_ring.params == new_params)?;
175

            
176
            let reuse_index_values = prev_ring
177
                .ring
178
                .iter()
179
                .filter_map(|(hsdir_index, rsidx)| {
180
                    Some((prev_netdir.md_by_rsidx(*rsidx)?.ed25519_id(), hsdir_index))
181
                })
182
                .collect();
183
            Some(reuse_index_values)
184
3194
        })()
185
3194
        .unwrap_or_default();
186
3194

            
187
3194
        let mut new_ring: TiVec<_, _> = this_netdir
188
3194
            .all_hsdirs()
189
31768
            .map(|(rsidx, relay)| {
190
31668
                let ed_id = relay.md.ed25519_id();
191
31668
                let hsdir_index = reuse_index_values
192
31668
                    .get(ed_id)
193
31668
                    .cloned()
194
31668
                    .cloned()
195
31668
                    .unwrap_or_else(|| relay_hsdir_index(ed_id, &new_params));
196
31668
                (hsdir_index, rsidx)
197
31768
            })
198
3194
            .collect();
199
3194

            
200
3194
        // rsidx are all different, so no need to think about comparing them
201
164384
        new_ring.sort_by_key(|(hsdir_index, _rsidx)| *hsdir_index);
202
3194

            
203
3194
        HsDirRing {
204
3194
            ring: new_ring,
205
3194
            params: new_params,
206
3194
        }
207
3194
    }
208

            
209
    /// Return the parameters used for this ring
210
1451
    pub(crate) fn params(&self) -> &HsDirParams {
211
1451
        &self.params
212
1451
    }
213

            
214
    /// Find the location or (notional) insertion point for `hsdir_index` within `ring`.
215
674
    fn find_pos(&self, hsdir_index: HsDirIndex) -> HsDirPos {
216
674
        self.ring
217
2451
            .binary_search_by_key(&hsdir_index, |(hsdir_index, _rs_idx)| *hsdir_index)
218
696
            .unwrap_or_else(|pos| pos)
219
674
    }
220

            
221
    /// Yield `spread` items from `ring` that satisfy the specified filter, starting with
222
    /// `hsdir_index`.
223
    ///
224
    /// Wraps around once when we reach the end.
225
    ///
226
    /// The specified filter function `f` is applied to each item, and determines whether the item
227
    /// should be yielded or not. This filtering functionality is used by [`NetDir::hs_dirs`] to
228
    /// prevent nodes that have already been selected for a lowered-numbered replica to be
229
    /// considered again when choosing `spread` nodes for a higher-numbered replicas.
230
    ///
231
    /// Yields no element more than once, even if the ring is smaller than `spread`.
232
44
    pub(crate) fn ring_items_at(
233
44
        &self,
234
44
        hsdir_index: HsDirIndex,
235
44
        spread: usize,
236
44
        f: impl FnMut(&&(HsDirIndex, RouterStatusIdx)) -> bool,
237
44
    ) -> impl Iterator<Item = &(HsDirIndex, RouterStatusIdx)> {
238
44
        let pos = self.find_pos(hsdir_index);
239
44
        self.ring[pos..]
240
44
            .iter()
241
44
            .chain(&self.ring[..pos])
242
44
            .filter(f)
243
44
            .take(spread)
244
44
    }
245

            
246
    /// Return the time period for which this ring applies.
247
407
    pub(crate) fn time_period(&self) -> TimePeriod {
248
407
        self.params.time_period
249
407
    }
250
}
251

            
252
#[cfg(test)]
253
mod test {
254
    // @@ begin test lint list maintained by maint/add_warning @@
255
    #![allow(clippy::bool_assert_comparison)]
256
    #![allow(clippy::clone_on_copy)]
257
    #![allow(clippy::dbg_macro)]
258
    #![allow(clippy::print_stderr)]
259
    #![allow(clippy::print_stdout)]
260
    #![allow(clippy::single_char_pattern)]
261
    #![allow(clippy::unwrap_used)]
262
    #![allow(clippy::unchecked_duration_subtraction)]
263
    #![allow(clippy::useless_vec)]
264
    #![allow(clippy::needless_pass_by_value)]
265
    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
266
    use super::*;
267

            
268
    use std::time::Duration;
269

            
270
    // mirrors C Tor src/test/test_hs_common.c:test_hs_indexes
271
    #[test]
272
    fn test_hs_indexes() {
273
        // C Tor test vector simply has
274
        //    uint64_t period_num = 42;
275
        let time_period = TimePeriod::new(
276
            Duration::from_secs(24 * 3600),
277
            // ~43 days from the Unix epoch
278
            humantime::parse_rfc3339("1970-02-13T01:00:00Z").unwrap(),
279
            Duration::from_secs(12 * 3600),
280
        )
281
        .unwrap();
282
        assert_eq!(time_period.interval_num(), 42);
283

            
284
        let shared_rand = [0x43; 32].into();
285

            
286
        let params = HsDirParams {
287
            time_period,
288
            shared_rand,
289
            srv_lifespan: time_period.range().unwrap(),
290
        };
291

            
292
        // service_index AKA hs_index
293
        {
294
            let kp_hs_blind_id = [0x42; 32].into();
295
            let replica = 1;
296
            let got = service_hsdir_index(&kp_hs_blind_id, replica, &params);
297
            assert_eq!(
298
                hex::encode(got.as_ref()),
299
                "37e5cbbd56a22823714f18f1623ece5983a0d64c78495a8cfab854245e5f9a8a",
300
            );
301
        }
302

            
303
        // relay_index AKA hsdir_index
304
        {
305
            let kp_relayid_ed = [0x42; 32].into();
306
            let got = relay_hsdir_index(&kp_relayid_ed, &params);
307
            assert_eq!(
308
                hex::encode(got.as_ref()),
309
                "db475361014a09965e7e5e4d4a25b8f8d4b8f16cb1d8a7e95eed50249cc1a2d5",
310
            );
311
        }
312
    }
313
}