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  #[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  #[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  pub(crate) fn relay_hsdir_index(
 80      kp_relayid_ed: &Ed25519Identity,
 81      params: &HsDirParams,
 82  ) -> HsDirIndex {
 83      // rend-spec-v3 2.2.3 "hsdir_index(node)"
 84      //
 85      // hsdir_index(node) = H("node-idx" | node_identity |
 86      //      shared_random_value |
 87      //      INT_8(period_num) |
 88      //      INT_8(period_length) )
 89      //
 90      // Note that INT_8 means "u64" and H is sha3-256.
 91  
 92      let mut h = Sha3_256::default();
 93      h.update(b"node-idx");
 94      h.update(kp_relayid_ed.as_bytes());
 95      h.update(params.shared_rand.as_ref());
 96      h.update(params.time_period.interval_num().to_be_bytes());
 97      h.update(u64::from(params.time_period.length().as_minutes()).to_be_bytes());
 98      HsDirIndex(h.finalize().into())
 99  }
100  
101  /// Compute the starting [`HsDirIndex`] for a given descriptor replica.
102  pub(crate) fn service_hsdir_index(
103      kp_hs_blind_id: &HsBlindId,
104      replica: u8,
105      params: &HsDirParams,
106  ) -> HsDirIndex {
107      // rend-spec-v3 2.2.3 "hs_index(replicanum)"
108      //
109      // hs_index(replicanum) = H("store-at-idx" |
110      //      blinded_public_key |
111      //      INT_8(replicanum) |
112      //      INT_8(period_length) |
113      //      INT_8(period_num) )
114      //
115      // Note that INT_8 means "u64" and H is sha3-256
116  
117      let mut h = Sha3_256::new();
118      h.update(b"store-at-idx");
119      h.update(kp_hs_blind_id.as_ref());
120      h.update(u64::from(replica).to_be_bytes());
121      h.update(u64::from(params.time_period.length().as_minutes()).to_be_bytes());
122      h.update(params.time_period.interval_num().to_be_bytes());
123      HsDirIndex(h.finalize().into())
124  }
125  
126  impl HsDirRing {
127      /// Return a new empty HsDirRing from a given set of parameters.
128      pub(crate) fn empty_from_params(params: HsDirParams) -> Self {
129          Self {
130              params,
131              ring: TiVec::new(),
132          }
133      }
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      pub(crate) fn compute(
143          new_params: HsDirParams,
144          this_netdir: &NetDir,
145          prev_netdir: Option<&NetDir>,
146      ) -> Self {
147          // TODO: The ring itself can be a bit expensive to compute, so maybe we should
148          // make sure this happens in a separate task or something, and expose a
149          // way to do that?
150          // But: this is being done during netdir ingestion, which is already happening
151          // on the dirmgr task.  So I think this is fine?  -Diziet
152  
153          // We would like to avoid re-computing the hsdir indexes, since they're a hash
154          // each.  Instead, we look to see if our previous netdir contains a hash ring
155          // using the same parameters.  If so, we make a hashmap from relay identities
156          // to hsring_index positions _in the previous netdir_
157          // to reuse.
158          //
159          // TODO: Actually, the relays in the consensus are ordered by their RSA identity.
160          // So we could do a merge join on the previous and last relay lists, and avoid
161          // building this separate hashmap.  (We'd have to *check* that the ed25519 ids
162          // matched, but it would be OK to recompute the index values for relays that
163          // have a different correspondence between ed25519 and RSA ids in subsequent
164          // consensuses, since that's really not supposed to happen.
165          //
166          // However, that would involve tor-netdoc offering the ordering property as a
167          // *guarantee*.  It's also quite subtle.  This algorithm is O(N.log(N)) which
168          // is the same complexity as the (unavoidable) sort by hsdir_index.
169          let reuse_index_values: HashMap<&Ed25519Identity, &HsDirIndex> = (|| {
170              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          })()
185          .unwrap_or_default();
186  
187          let mut new_ring: TiVec<_, _> = this_netdir
188              .all_hsdirs()
189              .map(|(rsidx, relay)| {
190                  let ed_id = relay.md.ed25519_id();
191                  let hsdir_index = reuse_index_values
192                      .get(ed_id)
193                      .cloned()
194                      .cloned()
195                      .unwrap_or_else(|| relay_hsdir_index(ed_id, &new_params));
196                  (hsdir_index, rsidx)
197              })
198              .collect();
199  
200          // rsidx are all different, so no need to think about comparing them
201          new_ring.sort_by_key(|(hsdir_index, _rsidx)| *hsdir_index);
202  
203          HsDirRing {
204              ring: new_ring,
205              params: new_params,
206          }
207      }
208  
209      /// Return the parameters used for this ring
210      pub(crate) fn params(&self) -> &HsDirParams {
211          &self.params
212      }
213  
214      /// Find the location or (notional) insertion point for `hsdir_index` within `ring`.
215      fn find_pos(&self, hsdir_index: HsDirIndex) -> HsDirPos {
216          self.ring
217              .binary_search_by_key(&hsdir_index, |(hsdir_index, _rs_idx)| *hsdir_index)
218              .unwrap_or_else(|pos| pos)
219      }
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      pub(crate) fn ring_items_at(
233          &self,
234          hsdir_index: HsDirIndex,
235          spread: usize,
236          f: impl FnMut(&&(HsDirIndex, RouterStatusIdx)) -> bool,
237      ) -> impl Iterator<Item = &(HsDirIndex, RouterStatusIdx)> {
238          let pos = self.find_pos(hsdir_index);
239          self.ring[pos..]
240              .iter()
241              .chain(&self.ring[..pos])
242              .filter(f)
243              .take(spread)
244      }
245  
246      /// Return the time period for which this ring applies.
247      pub(crate) fn time_period(&self) -> TimePeriod {
248          self.params.time_period
249      }
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::mixed_attributes_style)]
259      #![allow(clippy::print_stderr)]
260      #![allow(clippy::print_stdout)]
261      #![allow(clippy::single_char_pattern)]
262      #![allow(clippy::unwrap_used)]
263      #![allow(clippy::unchecked_duration_subtraction)]
264      #![allow(clippy::useless_vec)]
265      #![allow(clippy::needless_pass_by_value)]
266      //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
267      use super::*;
268  
269      use std::time::Duration;
270  
271      // mirrors C Tor src/test/test_hs_common.c:test_hs_indexes
272      #[test]
273      fn test_hs_indexes() {
274          // C Tor test vector simply has
275          //    uint64_t period_num = 42;
276          let time_period = TimePeriod::new(
277              Duration::from_secs(24 * 3600),
278              // ~43 days from the Unix epoch
279              humantime::parse_rfc3339("1970-02-13T01:00:00Z").unwrap(),
280              Duration::from_secs(12 * 3600),
281          )
282          .unwrap();
283          assert_eq!(time_period.interval_num(), 42);
284  
285          let shared_rand = [0x43; 32].into();
286  
287          let params = HsDirParams {
288              time_period,
289              shared_rand,
290              srv_lifespan: time_period.range().unwrap(),
291          };
292  
293          // service_index AKA hs_index
294          {
295              let kp_hs_blind_id = [0x42; 32].into();
296              let replica = 1;
297              let got = service_hsdir_index(&kp_hs_blind_id, replica, &params);
298              assert_eq!(
299                  hex::encode(got.as_ref()),
300                  "37e5cbbd56a22823714f18f1623ece5983a0d64c78495a8cfab854245e5f9a8a",
301              );
302          }
303  
304          // relay_index AKA hsdir_index
305          {
306              let kp_relayid_ed = [0x42; 32].into();
307              let got = relay_hsdir_index(&kp_relayid_ed, &params);
308              assert_eq!(
309                  hex::encode(got.as_ref()),
310                  "db475361014a09965e7e5e4d4a25b8f8d4b8f16cb1d8a7e95eed50249cc1a2d5",
311              );
312          }
313      }
314  }