Lines
95.11 %
Functions
56.89 %
Branches
100 %
#![cfg_attr(docsrs, feature(doc_auto_cfg, doc_cfg))]
#![doc = include_str!("../README.md")]
// @@ begin lint list maintained by maint/add_warning @@
#![allow(renamed_and_removed_lints)] // @@REMOVE_WHEN(ci_arti_stable)
#![allow(unknown_lints)] // @@REMOVE_WHEN(ci_arti_nightly)
#![warn(missing_docs)]
#![warn(noop_method_call)]
#![warn(unreachable_pub)]
#![warn(clippy::all)]
#![deny(clippy::await_holding_lock)]
#![deny(clippy::cargo_common_metadata)]
#![deny(clippy::cast_lossless)]
#![deny(clippy::checked_conversions)]
#![warn(clippy::cognitive_complexity)]
#![deny(clippy::debug_assert_with_mut_call)]
#![deny(clippy::exhaustive_enums)]
#![deny(clippy::exhaustive_structs)]
#![deny(clippy::expl_impl_clone_on_copy)]
#![deny(clippy::fallible_impl_from)]
#![deny(clippy::implicit_clone)]
#![deny(clippy::large_stack_arrays)]
#![warn(clippy::manual_ok_or)]
#![deny(clippy::missing_docs_in_private_items)]
#![warn(clippy::needless_borrow)]
#![warn(clippy::needless_pass_by_value)]
#![warn(clippy::option_option)]
#![deny(clippy::print_stderr)]
#![deny(clippy::print_stdout)]
#![warn(clippy::rc_buffer)]
#![deny(clippy::ref_option_ref)]
#![warn(clippy::semicolon_if_nothing_returned)]
#![warn(clippy::trait_duplication_in_bounds)]
#![deny(clippy::unchecked_duration_subtraction)]
#![deny(clippy::unnecessary_wraps)]
#![warn(clippy::unseparated_literal_suffix)]
#![deny(clippy::unwrap_used)]
#![allow(clippy::let_unit_value)] // This can reasonably be done for explicitness
#![allow(clippy::uninlined_format_args)]
#![allow(clippy::significant_drop_in_scrutinee)] // arti/-/merge_requests/588/#note_2812945
#![allow(clippy::result_large_err)] // temporary workaround for arti#587
#![allow(clippy::needless_raw_string_hashes)] // complained-about code is fine, often best
//! <!-- @@ end lint list maintained by maint/add_warning @@ -->
pub mod details;
mod err;
#[cfg(feature = "hs-common")]
mod hsdir_params;
mod hsdir_ring;
pub mod params;
mod weight;
#[cfg(any(test, feature = "testing"))]
pub mod testnet;
#[cfg(feature = "testing")]
pub mod testprovider;
#[cfg(feature = "hs-service")]
use itertools::chain;
use static_assertions::const_assert;
use tor_linkspec::{
ChanTarget, DirectChanMethodsHelper, HasAddrs, HasRelayIds, RelayIdRef, RelayIdType,
};
use tor_llcrypto as ll;
use tor_llcrypto::pk::{ed25519::Ed25519Identity, rsa::RsaIdentity};
use tor_netdoc::doc::microdesc::{MdDigest, Microdesc};
use tor_netdoc::doc::netstatus::{self, MdConsensus, MdConsensusRouterStatus, RouterStatus};
use {hsdir_ring::HsDirRing, std::iter};
use derive_more::{From, Into};
use futures::stream::BoxStream;
use num_enum::{IntoPrimitive, TryFromPrimitive};
use rand::seq::SliceRandom;
use serde::Deserialize;
use std::collections::HashMap;
use std::net::IpAddr;
use std::ops::Deref;
use std::sync::Arc;
use strum::{EnumCount, EnumIter};
use tracing::warn;
use typed_index_collections::{TiSlice, TiVec};
use {
itertools::Itertools,
std::collections::HashSet,
tor_error::{internal, Bug},
tor_hscrypto::{pk::HsBlindId, time::TimePeriod},
pub use err::Error;
pub use weight::WeightRole;
/// A Result using the Error type from the tor-netdir crate
pub type Result<T> = std::result::Result<T, Error>;
pub use err::OnionDirLookupError;
use params::NetParameters;
#[cfg(feature = "geoip")]
use tor_geoip::{CountryCode, GeoipDb, HasCountryCode};
#[cfg_attr(docsrs, doc(cfg(feature = "hs-common")))]
pub use hsdir_params::HsDirParams;
/// Index into the consensus relays
///
/// This is an index into the list of relays returned by
/// [`.c_relays()`](ConsensusRelays::c_relays)
/// (on the corresponding consensus or netdir).
/// This is just a `usize` inside, but using a newtype prevents getting a relay index
/// confused with other kinds of slice indices or counts.
/// If you are in a part of the code which needs to work with multiple consensuses,
/// the typechecking cannot tell if you try to index into the wrong consensus.
#[derive(Debug, From, Into, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
pub(crate) struct RouterStatusIdx(usize);
/// Extension trait to provide index-type-safe `.c_relays()` method
//
// TODO: Really it would be better to have MdConsensns::relays() return TiSlice,
// but that would be an API break there.
pub(crate) trait ConsensusRelays {
/// Obtain the list of relays in the consensus
fn c_relays(&self) -> &TiSlice<RouterStatusIdx, MdConsensusRouterStatus>;
}
impl ConsensusRelays for MdConsensus {
fn c_relays(&self) -> &TiSlice<RouterStatusIdx, MdConsensusRouterStatus> {
TiSlice::from_ref(MdConsensus::relays(self))
impl ConsensusRelays for NetDir {
self.consensus.c_relays()
/// Configuration for determining when two relays have addresses "too close" in
/// the network.
/// Used by [`Relay::low_level_details().in_same_subnet()`].
#[derive(Deserialize, Debug, Clone, Copy, Eq, PartialEq)]
#[serde(deny_unknown_fields)]
pub struct SubnetConfig {
/// Consider IPv4 nodes in the same /x to be the same family.
/// If this value is 0, all nodes with IPv4 addresses will be in the
/// same family. If this value is above 32, then no nodes will be
/// placed im the same family based on their IPv4 addresses.
subnets_family_v4: u8,
/// Consider IPv6 nodes in the same /x to be the same family.
/// If this value is 0, all nodes with IPv6 addresses will be in the
/// same family. If this value is above 128, then no nodes will be
/// placed im the same family based on their IPv6 addresses.
subnets_family_v6: u8,
impl Default for SubnetConfig {
fn default() -> Self {
Self::new(16, 32)
impl SubnetConfig {
/// Construct a new SubnetConfig from a pair of bit prefix lengths.
/// The values are clamped to the appropriate ranges if they are
/// out-of-bounds.
pub fn new(subnets_family_v4: u8, subnets_family_v6: u8) -> Self {
Self {
subnets_family_v4,
subnets_family_v6,
/// Construct a new SubnetConfig such that addresses are not in the same
/// family with anything--not even with themselves.
pub fn no_addresses_match() -> SubnetConfig {
SubnetConfig {
subnets_family_v4: 33,
subnets_family_v6: 129,
/// Return true if the two addresses in the same subnet, according to this
/// configuration.
pub fn addrs_in_same_subnet(&self, a: &IpAddr, b: &IpAddr) -> bool {
match (a, b) {
(IpAddr::V4(a), IpAddr::V4(b)) => {
let bits = self.subnets_family_v4;
if bits > 32 {
return false;
let a = u32::from_be_bytes(a.octets());
let b = u32::from_be_bytes(b.octets());
(a >> (32 - bits)) == (b >> (32 - bits))
(IpAddr::V6(a), IpAddr::V6(b)) => {
let bits = self.subnets_family_v6;
if bits > 128 {
let a = u128::from_be_bytes(a.octets());
let b = u128::from_be_bytes(b.octets());
(a >> (128 - bits)) == (b >> (128 - bits))
_ => false,
/// Return true if any of the addresses in `a` shares a subnet with any of
/// the addresses in `b`, according to this configuration.
pub fn any_addrs_in_same_subnet<T, U>(&self, a: &T, b: &U) -> bool
where
T: tor_linkspec::HasAddrs,
U: tor_linkspec::HasAddrs,
{
a.addrs().iter().any(|aa| {
b.addrs()
.iter()
.any(|bb| self.addrs_in_same_subnet(&aa.ip(), &bb.ip()))
})
/// Return a new subnet configuration that is the union of `self` and
/// `other`.
/// That is, return a subnet configuration that puts all addresses in the
/// same subnet if and only if at least one of `self` and `other` would put
/// them in the same subnet.
pub fn union(&self, other: &Self) -> Self {
use std::cmp::min;
subnets_family_v4: min(self.subnets_family_v4, other.subnets_family_v4),
subnets_family_v6: min(self.subnets_family_v6, other.subnets_family_v6),
/// An opaque type representing the weight with which a relay or set of
/// relays will be selected for a given role.
/// Most users should ignore this type, and just use pick_relay instead.
#[derive(
Copy,
Clone,
Debug,
derive_more::Add,
derive_more::Sum,
derive_more::AddAssign,
Eq,
PartialEq,
Ord,
PartialOrd,
)]
pub struct RelayWeight(u64);
impl RelayWeight {
/// Try to divide this weight by `rhs`.
/// Return a ratio on success, or None on division-by-zero.
pub fn checked_div(&self, rhs: RelayWeight) -> Option<f64> {
if rhs.0 == 0 {
None
} else {
Some((self.0 as f64) / (rhs.0 as f64))
/// Compute a ratio `frac` of this weight.
/// Return None if frac is less than zero, since negative weights
/// are impossible.
pub fn ratio(&self, frac: f64) -> Option<RelayWeight> {
let product = (self.0 as f64) * frac;
if product >= 0.0 && product.is_finite() {
Some(RelayWeight(product as u64))
impl From<u64> for RelayWeight {
fn from(val: u64) -> Self {
RelayWeight(val)
/// An operation for which we might be requesting a hidden service directory.
#[derive(Copy, Clone, Debug, PartialEq)]
// TODO: make this pub(crate) once NetDir::hs_dirs is removed
#[non_exhaustive]
pub enum HsDirOp {
/// Uploading an onion service descriptor.
Upload,
/// Downloading an onion service descriptor.
Download,
/// A view of the Tor directory, suitable for use in building circuits.
/// Abstractly, a [`NetDir`] is a set of usable public [`Relay`]s, each of which
/// has its own properties, identity, and correct weighted probability for use
/// under different circumstances.
/// A [`NetDir`] is constructed by making a [`PartialNetDir`] from a consensus
/// document, and then adding enough microdescriptors to that `PartialNetDir` so
/// that it can be used to build paths. (Thus, if you have a NetDir, it is
/// definitely adequate to build paths.)
/// # "Usable" relays
/// Many methods on NetDir are defined in terms of <a name="usable">"Usable"</a> relays. Unless
/// otherwise stated, a relay is "usable" if it is listed in the consensus,
/// if we have full directory information for that relay (including a
/// microdescriptor), and if that relay does not have any flags indicating that
/// we should never use it. (Currently, `NoEdConsensus` is the only such flag.)
/// # Limitations
/// The current NetDir implementation assumes fairly strongly that every relay
/// has an Ed25519 identity and an RSA identity, that the consensus is indexed
/// by RSA identities, and that the Ed25519 identities are stored in
/// microdescriptors.
/// If these assumptions someday change, then we'll have to revise the
/// implementation.
#[derive(Debug, Clone)]
pub struct NetDir {
/// A microdescriptor consensus that lists the members of the network,
/// and maps each one to a 'microdescriptor' that has more information
/// about it
consensus: Arc<MdConsensus>,
/// A map from keys to integer values, distributed in the consensus,
/// and clamped to certain defaults.
params: NetParameters,
/// Map from routerstatus index, to that routerstatus's microdescriptor (if we have one.)
mds: TiVec<RouterStatusIdx, Option<Arc<Microdesc>>>,
/// Map from SHA256 of _missing_ microdescriptors to the index of their
/// corresponding routerstatus.
rsidx_by_missing: HashMap<MdDigest, RouterStatusIdx>,
/// Map from ed25519 identity to index of the routerstatus.
/// Note that we don't know the ed25519 identity of a relay until
/// we get the microdescriptor for it, so this won't be filled in
/// until we get the microdescriptors.
/// # Implementation note
/// For this field, and for `rsidx_by_rsa`,
/// it might be cool to have references instead.
/// But that would make this into a self-referential structure,
/// which isn't possible in safe rust.
rsidx_by_ed: HashMap<Ed25519Identity, RouterStatusIdx>,
/// Map from RSA identity to index of the routerstatus.
/// This is constructed at the same time as the NetDir object, so it
/// can be immutable.
rsidx_by_rsa: Arc<HashMap<RsaIdentity, RouterStatusIdx>>,
/// Hash ring(s) describing the onion service directory.
/// This is empty in a PartialNetDir, and is filled in before the NetDir is
/// built.
// TODO hs: It is ugly to have this exist in a partially constructed state
// in a PartialNetDir.
// Ideally, a PartialNetDir would contain only an HsDirs<HsDirParams>,
// or perhaps nothing at all, here.
hsdir_rings: Arc<HsDirs<HsDirRing>>,
/// Weight values to apply to a given relay when deciding how frequently
/// to choose it for a given role.
weights: weight::WeightSet,
/// Country codes for each router in our consensus.
/// This is indexed by the `RouterStatusIdx` (i.e. a router idx of zero has
/// the country code at position zero in this array).
country_codes: Vec<Option<CountryCode>>,
/// Collection of hidden service directories (or parameters for them)
/// In [`NetDir`] this is used to store the actual hash rings.
/// (But, in a NetDir in a [`PartialNetDir`], it contains [`HsDirRing`]s
/// where only the `params` are populated, and the `ring` is empty.)
/// This same generic type is used as the return type from
/// [`HsDirParams::compute`](HsDirParams::compute),
/// where it contains the *parameters* for the primary and secondary rings.
pub(crate) struct HsDirs<D> {
/// The current ring
/// It corresponds to the time period containing the `valid-after` time in
/// the consensus. Its SRV is whatever SRV was most current at the time when
/// that time period began.
/// This is the hash ring that we should use whenever we are fetching an
/// onion service descriptor.
current: D,
/// Secondary rings (based on the parameters for the previous and next time periods)
/// Onion services upload to positions on these ring as well, based on how
/// far into the current time period this directory is, so that
/// not-synchronized clients can still find their descriptor.
/// Note that with the current (2023) network parameters, with
/// `hsdir_interval = SRV lifetime = 24 hours` at most one of these
/// secondary rings will be active at a time. We have two here in order
/// to conform with a more flexible regime in proposal 342.
// TODO: hs clients never need this; so I've made it not-present for thm.
// But does that risk too much with respect to side channels?
// TODO: Perhaps we should refactor this so that it is clear that these
// are immutable? On the other hand, the documentation for this type
// declares that it is immutable, so we are likely okay.
// TODO: this `Vec` is only ever 0,1,2 elements.
// Maybe it should be an ArrayVec or something.
secondary: Vec<D>,
impl<D> HsDirs<D> {
/// Convert an `HsDirs<D>` to `HsDirs<D2>` by mapping each contained `D`
pub(crate) fn map<D2>(self, mut f: impl FnMut(D) -> D2) -> HsDirs<D2> {
HsDirs {
current: f(self.current),
secondary: self.secondary.into_iter().map(f).collect(),
/// Iterate over some of the contained hsdirs, according to `secondary`
/// The current ring is always included.
/// Secondary rings are included iff `secondary` and the `hs-service` feature is enabled.
fn iter_filter_secondary(&self, secondary: bool) -> impl Iterator<Item = &D> {
let i = iter::once(&self.current);
// With "hs-service" disabled, there are no secondary rings,
// so we don't care.
let _ = secondary;
let i = chain!(i, self.secondary.iter().filter(move |_| secondary));
i
/// Iterate over all the contained hsdirs
pub(crate) fn iter(&self) -> impl Iterator<Item = &D> {
self.iter_filter_secondary(true)
/// Iterate over the hsdirs relevant for `op`
pub(crate) fn iter_for_op(&self, op: HsDirOp) -> impl Iterator<Item = &D> {
self.iter_filter_secondary(match op {
HsDirOp::Upload => true,
HsDirOp::Download => false,
/// An event that a [`NetDirProvider`] can broadcast to indicate that a change in
/// the status of its directory.
Debug, Clone, Copy, PartialEq, Eq, EnumIter, EnumCount, IntoPrimitive, TryFromPrimitive,
#[repr(u16)]
pub enum DirEvent {
/// A new consensus has been received, and has enough information to be
/// used.
/// This event is also broadcast when a new set of consensus parameters is
/// available, even if that set of parameters comes from a configuration
/// change rather than from the latest consensus.
NewConsensus,
/// New descriptors have been received for the current consensus.
/// (This event is _not_ broadcast when receiving new descriptors for a
/// consensus which is not yet ready to replace the current consensus.)
NewDescriptors,
/// How "timely" must a network directory be?
/// This enum is used as an argument when requesting a [`NetDir`] object from
/// [`NetDirProvider`] and other APIs, to specify how recent the information
/// must be in order to be useful.
#[derive(Copy, Clone, Eq, PartialEq, Debug)]
#[allow(clippy::exhaustive_enums)]
pub enum Timeliness {
/// The network directory must be strictly timely.
/// That is, it must be based on a consensus that valid right now, with no
/// tolerance for skew or consensus problems.
/// Avoid using this option if you could use [`Timeliness::Timely`] instead.
Strict,
/// The network directory must be roughly timely.
/// This is, it must be be based on a consensus that is not _too_ far in the
/// future, and not _too_ far in the past.
/// (The tolerances for "too far" will depend on configuration.)
/// This is almost always the option that you want to use.
Timely,
/// Any network directory is permissible, regardless of how untimely.
Unchecked,
/// An object that can provide [`NetDir`]s, as well as inform consumers when
/// they might have changed.
/// It is the responsibility of the implementor of `NetDirProvider`
/// to try to obtain an up-to-date `NetDir`,
/// and continuously to maintain and update it.
/// In usual configurations, Arti uses `tor_dirmgr::DirMgr`
/// as its `NetDirProvider`.
pub trait NetDirProvider: UpcastArcNetDirProvider + Send + Sync {
/// Return a network directory that's live according to the provided
/// `timeliness`.
fn netdir(&self, timeliness: Timeliness) -> Result<Arc<NetDir>>;
/// Return a reasonable netdir for general usage.
/// This is an alias for
/// [`NetDirProvider::netdir`]`(`[`Timeliness::Timely`]`)`.
fn timely_netdir(&self) -> Result<Arc<NetDir>> {
self.netdir(Timeliness::Timely)
/// Return a new asynchronous stream that will receive notification
/// whenever the consensus has changed.
/// Multiple events may be batched up into a single item: each time
/// this stream yields an event, all you can assume is that the event has
/// occurred at least once.
fn events(&self) -> BoxStream<'static, DirEvent>;
/// Return the latest network parameters.
/// If we have no directory, return a reasonable set of defaults.
fn params(&self) -> Arc<dyn AsRef<NetParameters>>;
impl<T> NetDirProvider for Arc<T>
T: NetDirProvider,
fn netdir(&self, timeliness: Timeliness) -> Result<Arc<NetDir>> {
self.deref().netdir(timeliness)
self.deref().timely_netdir()
fn events(&self) -> BoxStream<'static, DirEvent> {
self.deref().events()
fn params(&self) -> Arc<dyn AsRef<NetParameters>> {
self.deref().params()
/// Helper trait: allows any `Arc<X>` to be upcast to a `Arc<dyn
/// NetDirProvider>` if X is an implementation or supertrait of NetDirProvider.
/// This trait exists to work around a limitation in rust: when trait upcasting
/// coercion is stable, this will be unnecessary.
/// The Rust tracking issue is <https://github.com/rust-lang/rust/issues/65991>.
pub trait UpcastArcNetDirProvider {
/// Return a view of this object as an `Arc<dyn NetDirProvider>`
fn upcast_arc<'a>(self: Arc<Self>) -> Arc<dyn NetDirProvider + 'a>
Self: 'a;
impl<T> UpcastArcNetDirProvider for T
T: NetDirProvider + Sized,
Self: 'a,
self
impl AsRef<NetParameters> for NetDir {
fn as_ref(&self) -> &NetParameters {
self.params()
/// A partially build NetDir -- it can't be unwrapped until it has
/// enough information to build safe paths.
pub struct PartialNetDir {
/// The netdir that's under construction.
netdir: NetDir,
/// The previous netdir, if we had one
/// Used as a cache, so we can reuse information
prev_netdir: Option<Arc<NetDir>>,
/// A view of a relay on the Tor network, suitable for building circuits.
// TODO: This should probably be a more specific struct, with a trait
// that implements it.
#[derive(Clone)]
pub struct Relay<'a> {
/// A router descriptor for this relay.
rs: &'a netstatus::MdConsensusRouterStatus,
/// A microdescriptor for this relay.
md: &'a Microdesc,
/// The country code this relay is in, if we know one.
cc: Option<CountryCode>,
/// A relay that we haven't checked for validity or usability in
/// routing.
#[derive(Debug)]
pub struct UncheckedRelay<'a> {
/// A microdescriptor for this relay, if there is one.
md: Option<&'a Microdesc>,
/// 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;
/// Return the number of missing microdescriptors.
fn n_missing(&self) -> usize;
impl PartialNetDir {
/// Create a new PartialNetDir with a given consensus, and no
/// microdescriptors loaded.
/// If `replacement_params` is provided, override network parameters from
/// the consensus with those from `replacement_params`.
pub fn new(
consensus: MdConsensus,
replacement_params: Option<&netstatus::NetParams<i32>>,
) -> Self {
Self::new_inner(
consensus,
replacement_params,
None,
)
/// Create a new PartialNetDir with GeoIP support.
/// This does the same thing as `new()`, except the provided GeoIP database is used to add
/// country codes to relays.
#[cfg_attr(docsrs, doc(cfg(feature = "geoip")))]
pub fn new_with_geoip(
geoip_db: &GeoipDb,
Self::new_inner(consensus, replacement_params, Some(geoip_db))
/// Implementation of the `new()` functions.
fn new_inner(
#[cfg(feature = "geoip")] geoip_db: Option<&GeoipDb>,
let mut params = NetParameters::default();
// (We ignore unrecognized options here, since they come from
// the consensus, and we don't expect to recognize everything
// there.)
let _ = params.saturating_update(consensus.params().iter());
// Now see if the user has any parameters to override.
// (We have to do this now, or else changes won't be reflected in our
// weights.)
if let Some(replacement) = replacement_params {
for u in params.saturating_update(replacement.iter()) {
warn!("Unrecognized option: override_net_params.{}", u);
// Compute the weights we'll want to use for these relays.
let weights = weight::WeightSet::from_consensus(&consensus, ¶ms);
let n_relays = consensus.c_relays().len();
let rsidx_by_missing = consensus
.c_relays()
.iter_enumerated()
.map(|(rsidx, rs)| (*rs.md_digest(), rsidx))
.collect();
let rsidx_by_rsa = consensus
.map(|(rsidx, rs)| (*rs.rsa_identity(), rsidx))
let country_codes = if let Some(db) = geoip_db {
consensus
.map(|rs| {
let ret = db
.lookup_country_code_multi(rs.addrs().iter().map(|x| x.ip()))
.cloned();
ret
.collect()
Default::default()
let hsdir_rings = Arc::new({
let params = HsDirParams::compute(&consensus, ¶ms).expect("Invalid consensus!");
// TODO: It's a bit ugly to use expect above, but this function does
// not return a Result. On the other hand, the error conditions under which
// HsDirParams::compute can return Err are _very_ narrow and hard to
// hit; see documentation in that function. As such, we probably
// don't need to have this return a Result.
params.map(HsDirRing::empty_from_params)
});
let netdir = NetDir {
consensus: Arc::new(consensus),
params,
mds: vec![None; n_relays].into(),
rsidx_by_missing,
rsidx_by_rsa: Arc::new(rsidx_by_rsa),
rsidx_by_ed: HashMap::with_capacity(n_relays),
hsdir_rings,
weights,
country_codes,
PartialNetDir {
netdir,
prev_netdir: None,
/// Return the declared lifetime of this PartialNetDir.
pub fn lifetime(&self) -> &netstatus::Lifetime {
self.netdir.lifetime()
/// Record a previous netdir, which can be used for reusing cached information
// Fills in as many missing microdescriptors as possible in this
// netdir, using the microdescriptors from the previous netdir.
// With HS enabled, stores the netdir for reuse of relay hash ring index values.
#[allow(clippy::needless_pass_by_value)] // prev might, or might not, be stored
pub fn fill_from_previous_netdir(&mut self, prev: Arc<NetDir>) {
for md in prev.mds.iter().flatten() {
self.netdir.add_arc_microdesc(md.clone());
self.prev_netdir = Some(prev);
/// Compute the hash ring(s) for this NetDir
fn compute_rings(&mut self) {
let params = HsDirParams::compute(&self.netdir.consensus, &self.netdir.params)
.expect("Invalid consensus");
// TODO: see TODO by similar expect in new()
self.netdir.hsdir_rings =
Arc::new(params.map(|params| {
HsDirRing::compute(params, &self.netdir, self.prev_netdir.as_deref())
}));
/// Return true if this are enough information in this directory
/// to build multihop paths.
pub fn have_enough_paths(&self) -> bool {
self.netdir.have_enough_paths()
/// If this directory has enough information to build multihop
/// circuits, return it.
pub fn unwrap_if_sufficient(
#[allow(unused_mut)] mut self,
) -> std::result::Result<NetDir, PartialNetDir> {
if self.netdir.have_enough_paths() {
self.compute_rings();
Ok(self.netdir)
Err(self)
impl MdReceiver for PartialNetDir {
fn missing_microdescs(&self) -> Box<dyn Iterator<Item = &MdDigest> + '_> {
self.netdir.missing_microdescs()
fn add_microdesc(&mut self, md: Microdesc) -> bool {
self.netdir.add_microdesc(md)
fn n_missing(&self) -> usize {
self.netdir.n_missing()
impl NetDir {
/// Return the declared lifetime of this NetDir.
self.consensus.lifetime()
/// Add `md` to this NetDir.
/// Return true if we wanted it, and false otherwise.
fn add_arc_microdesc(&mut self, md: Arc<Microdesc>) -> bool {
if let Some(rsidx) = self.rsidx_by_missing.remove(md.digest()) {
assert_eq!(self.c_relays()[rsidx].md_digest(), md.digest());
// There should never be two approved MDs in the same
// consensus listing the same ID... but if there is,
// we'll let the most recent one win.
self.rsidx_by_ed.insert(*md.ed25519_id(), rsidx);
// Happy path: we did indeed want this one.
self.mds[rsidx] = Some(md);
// Save some space in the missing-descriptor list.
if self.rsidx_by_missing.len() < self.rsidx_by_missing.capacity() / 4 {
self.rsidx_by_missing.shrink_to_fit();
return true;
// Either we already had it, or we never wanted it at all.
false
/// Construct a (possibly invalid) Relay object from a routerstatus and its
/// index within the consensus.
fn relay_from_rs_and_rsidx<'a>(
&'a self,
rsidx: RouterStatusIdx,
) -> UncheckedRelay<'a> {
debug_assert_eq!(self.c_relays()[rsidx].rsa_identity(), rs.rsa_identity());
let md = self.mds[rsidx].as_deref();
if let Some(md) = md {
debug_assert_eq!(rs.md_digest(), md.digest());
UncheckedRelay {
rs,
md,
cc: self.country_codes.get(rsidx.0).copied().flatten(),
/// Return the value of the hsdir_n_replicas param.
fn n_replicas(&self) -> u8 {
self.params
.hsdir_n_replicas
.get()
.try_into()
.expect("BoundedInt did not enforce bounds")
/// Return the spread parameter for the specified `op`.
fn spread(&self, op: HsDirOp) -> usize {
let spread = match op {
HsDirOp::Download => self.params.hsdir_spread_fetch,
HsDirOp::Upload => self.params.hsdir_spread_store,
spread
.expect("BoundedInt did not enforce bounds!")
/// Select `spread` hsdir relays for the specified `hsid` from a given `ring`.
/// Algorithm:
/// for idx in 1..=n_replicas:
/// - let H = hsdir_ring::onion_service_index(id, replica, rand,
/// period).
/// - Find the position of H within hsdir_ring.
/// - Take elements from hsdir_ring starting at that position,
/// adding them to Dirs until we have added `spread` new elements
/// that were not there before.
fn select_hsdirs<'h, 'r: 'h>(
&'r self,
hsid: HsBlindId,
ring: &'h HsDirRing,
spread: usize,
) -> impl Iterator<Item = Relay<'r>> + 'h {
let n_replicas = self.n_replicas();
(1..=n_replicas) // 1-indexed !
.flat_map({
let mut selected_nodes = HashSet::new();
move |replica: u8| {
let hsdir_idx = hsdir_ring::service_hsdir_index(&hsid, replica, ring.params());
let items = ring
.ring_items_at(hsdir_idx, spread, |(hsdir_idx, _)| {
// According to rend-spec 2.2.3:
// ... If any of those
// nodes have already been selected for a lower-numbered replica of the
// service, any nodes already chosen are disregarded (i.e. skipped over)
// when choosing a replica's hsdir_spread_store nodes.
selected_nodes.insert(*hsdir_idx)
.collect::<Vec<_>>();
items
.filter_map(move |(_hsdir_idx, rs_idx)| {
// This ought not to be None but let's not panic or bail if it is
self.relay_by_rs_idx(*rs_idx)
/// Replace the overridden parameters in this netdir with `new_replacement`.
/// After this function is done, the netdir's parameters will be those in
/// the consensus, overridden by settings from `new_replacement`. Any
/// settings in the old replacement parameters will be discarded.
pub fn replace_overridden_parameters(&mut self, new_replacement: &netstatus::NetParams<i32>) {
// TODO(nickm): This is largely duplicate code from PartialNetDir::new().
let mut new_params = NetParameters::default();
let _ = new_params.saturating_update(self.consensus.params().iter());
for u in new_params.saturating_update(new_replacement.iter()) {
self.params = new_params;
/// Return an iterator over all Relay objects, including invalid ones
/// that we can't use.
pub fn all_relays(&self) -> impl Iterator<Item = UncheckedRelay<'_>> {
// TODO: I'd like if we could memoize this so we don't have to
// do so many hashtable lookups.
self.c_relays()
.map(move |(rsidx, rs)| self.relay_from_rs_and_rsidx(rs, rsidx))
/// Return an iterator over all [usable](NetDir#usable) Relays.
pub fn relays(&self) -> impl Iterator<Item = Relay<'_>> {
self.all_relays().filter_map(UncheckedRelay::into_relay)
/// Look up a relay's `MicroDesc` by its `RouterStatusIdx`
#[cfg_attr(not(feature = "hs-common"), allow(dead_code))]
pub(crate) fn md_by_rsidx(&self, rsidx: RouterStatusIdx) -> Option<&Microdesc> {
self.mds.get(rsidx)?.as_deref()
/// Return a relay matching a given identity, if we have a
/// _usable_ relay with that key.
/// (Does not return [unusable](NetDir#usable) relays.)
/// Note that a `None` answer is not always permanent: if a microdescriptor
/// is subsequently added for a relay with this ID, the ID may become usable
/// even if it was not usable before.
pub fn by_id<'a, T>(&self, id: T) -> Option<Relay<'_>>
T: Into<RelayIdRef<'a>>,
let id = id.into();
let answer = match id {
RelayIdRef::Ed25519(ed25519) => {
let rsidx = *self.rsidx_by_ed.get(ed25519)?;
let rs = self.c_relays().get(rsidx).expect("Corrupt index");
self.relay_from_rs_and_rsidx(rs, rsidx).into_relay()?
RelayIdRef::Rsa(rsa) => self
.by_rsa_id_unchecked(rsa)
.and_then(UncheckedRelay::into_relay)?,
other_type => self.relays().find(|r| r.has_identity(other_type))?,
assert!(answer.has_identity(id));
Some(answer)
/// Obtain a `Relay` given a `RouterStatusIdx`
/// Differs from `relay_from_rs_and_rsi` as follows:
/// * That function expects the caller to already have an `MdConsensusRouterStatus`;
/// it checks with `debug_assert` that the relay in the netdir matches.
/// * That function panics if the `RouterStatusIdx` is invalid; this one returns `None`.
/// * That function returns an `UncheckedRelay`; this one a `Relay`.
/// `None` could be returned here, even with a valid `rsi`,
/// if `rsi` refers to an [unusable](NetDir#usable) relay.
pub(crate) fn relay_by_rs_idx(&self, rs_idx: RouterStatusIdx) -> Option<Relay<'_>> {
let rs = self.c_relays().get(rs_idx)?;
let md = self.mds.get(rs_idx)?.as_deref();
cc: self.country_codes.get(rs_idx.0).copied().flatten(),
.into_relay()
/// Return a relay with the same identities as those in `target`, if one
/// exists.
/// Does not return [unusable](NetDir#usable) relays.
/// Note that a negative result from this method is not necessarily permanent:
/// it may be the case that a relay exists,
/// but we don't yet have enough information about it to know all of its IDs.
/// To test whether a relay is *definitely* absent,
/// use [`by_ids_detailed`](Self::by_ids_detailed)
/// or [`ids_listed`](Self::ids_listed).
/// This will be very slow if `target` does not have an Ed25519 or RSA
/// identity.
pub fn by_ids<T>(&self, target: &T) -> Option<Relay<'_>>
T: HasRelayIds + ?Sized,
let mut identities = target.identities();
// Don't try if there are no identities.
let first_id = identities.next()?;
// Since there is at most one relay with each given ID type,
// we only need to check the first relay we find.
let candidate = self.by_id(first_id)?;
if identities.all(|wanted_id| candidate.has_identity(wanted_id)) {
Some(candidate)
/// Check whether there is a relay that has at least one identity from
/// `target`, and which _could_ have every identity from `target`.
/// If so, return such a relay.
/// Return `Ok(None)` if we did not find a relay with any identity from `target`.
/// Return `RelayLookupError::Impossible` if we found a relay with at least
/// one identity from `target`, but that relay's other identities contradict
/// what we learned from `target`.
/// (This function is only useful if you need to distinguish the
/// "impossible" case from the "no such relay known" case.)
// TODO HS: This function could use a better name.
// TODO: We could remove the feature restriction here once we think this API is
// stable.
pub fn by_ids_detailed<T>(
&self,
target: &T,
) -> std::result::Result<Option<Relay<'_>>, RelayLookupError>
let candidate = target
.identities()
// Find all the relays that share any identity with this set of identities.
.filter_map(|id| self.by_id(id))
// We might find the same relay more than once under a different
// identity, so we remove the duplicates.
// Since there is at most one relay per rsa identity per consensus,
// this is a true uniqueness check under current construction rules.
.unique_by(|r| r.rs.rsa_identity())
// If we find two or more distinct relays, then have a contradiction.
.at_most_one()
.map_err(|_| RelayLookupError::Impossible)?;
// If we have no candidate, return None early.
let candidate = match candidate {
Some(relay) => relay,
None => return Ok(None),
// Now we know we have a single candidate. Make sure that it does not have any
// identity that does not match the target.
if target
.all(|wanted_id| match candidate.identity(wanted_id.id_type()) {
None => true,
Some(id) => id == wanted_id,
Ok(Some(candidate))
Err(RelayLookupError::Impossible)
/// Return a boolean if this consensus definitely has (or does not have) a
/// relay matching the listed identities.
/// `Some(true)` indicates that the relay exists.
/// `Some(false)` indicates that the relay definitely does not exist.
/// `None` indicates that we can't yet tell whether such a relay exists,
/// due to missing information.
fn id_pair_listed(&self, ed_id: &Ed25519Identity, rsa_id: &RsaIdentity) -> Option<bool> {
let r = self.by_rsa_id_unchecked(rsa_id);
match r {
Some(unchecked) => {
if !unchecked.rs.ed25519_id_is_usable() {
return Some(false);
// If md is present, then it's listed iff we have the right
// ed id. Otherwise we don't know if it's listed.
unchecked.md.map(|md| md.ed25519_id() == ed_id)
None => {
// Definitely not listed.
Some(false)
/// Check whether a relay exists (or may exist)
/// with the same identities as those in `target`.
pub fn ids_listed<T>(&self, target: &T) -> Option<bool>
let rsa_id = target.rsa_identity();
let ed25519_id = target.ed_identity();
// TODO: If we later support more identity key types, this will
// become incorrect. This assertion might help us recognize that case.
const_assert!(RelayIdType::COUNT == 2);
match (rsa_id, ed25519_id) {
(Some(r), Some(e)) => self.id_pair_listed(e, r),
(Some(r), None) => Some(self.rsa_id_is_listed(r)),
(None, Some(e)) => {
if self.rsidx_by_ed.contains_key(e) {
Some(true)
(None, None) => None,
/// Return a (possibly [unusable](NetDir#usable)) relay with a given RSA identity.
/// This API can be used to find information about a relay that is listed in
/// the current consensus, even if we don't yet have enough information
/// (like a microdescriptor) about the relay to use it.
#[cfg_attr(feature = "experimental-api", visibility::make(pub))]
#[cfg_attr(docsrs, doc(cfg(feature = "experimental-api")))]
fn by_rsa_id_unchecked(&self, rsa_id: &RsaIdentity) -> Option<UncheckedRelay<'_>> {
let rsidx = *self.rsidx_by_rsa.get(rsa_id)?;
assert_eq!(rs.rsa_identity(), rsa_id);
Some(self.relay_from_rs_and_rsidx(rs, rsidx))
/// Return the relay with a given RSA identity, if we have one
/// and it is [usable](NetDir#usable).
fn by_rsa_id(&self, rsa_id: &RsaIdentity) -> Option<Relay<'_>> {
self.by_rsa_id_unchecked(rsa_id)?.into_relay()
/// Return true if `rsa_id` is listed in this directory, even if it isn't
/// currently usable.
/// (An "[unusable](NetDir#usable)" relay in this context is one for which we don't have full
/// directory information.)
fn rsa_id_is_listed(&self, rsa_id: &RsaIdentity) -> bool {
self.by_rsa_id_unchecked(rsa_id).is_some()
/// List the hsdirs in this NetDir, that should be in the HSDir rings
/// The results are not returned in any particular order.
fn all_hsdirs(&self) -> impl Iterator<Item = (RouterStatusIdx, Relay<'_>)> {
self.c_relays().iter_enumerated().filter_map(|(rsidx, rs)| {
let relay = self.relay_from_rs_and_rsidx(rs, rsidx);
relay.is_hsdir_for_ring().then_some(())?;
let relay = relay.into_relay()?;
Some((rsidx, relay))
/// Return the parameters from the consensus, clamped to the
/// correct ranges, with defaults filled in.
/// NOTE: that unsupported parameters aren't returned here; only those
/// values configured in the `params` module are available.
pub fn params(&self) -> &NetParameters {
&self.params
/// Return a [`ProtoStatus`](netstatus::ProtoStatus) that lists the
/// network's current requirements and recommendations for the list of
/// protocols that every relay must implement.
// TODO HS: I am not sure this is the right API; other alternatives would be:
// * To expose the _required_ relay protocol list instead (since that's all that
// onion service implementations need).
// * To expose the client protocol list as well (for symmetry).
// * To expose the MdConsensus instead (since that's more general, although
// it restricts the future evolution of this API).
// I think that this is a reasonably good compromise for now, but I'm going
// to put it behind the `hs-common` feature to give us time to consider more.
pub fn relay_protocol_status(&self) -> &netstatus::ProtoStatus {
self.consensus.relay_protocol_status()
/// Return weighted the fraction of relays we can use. We only
/// consider relays that match the predicate `usable`. We weight
/// this bandwidth according to the provided `role`.
/// If _no_ matching relays in the consensus have a nonzero
/// weighted bandwidth value, we fall back to looking at the
/// unweighted fraction of matching relays.
/// If there are no matching relays in the consensus, we return 0.0.
fn frac_for_role<'a, F>(&'a self, role: WeightRole, usable: F) -> f64
F: Fn(&UncheckedRelay<'a>) -> bool,
let mut total_weight = 0_u64;
let mut have_weight = 0_u64;
let mut have_count = 0_usize;
let mut total_count = 0_usize;
for r in self.all_relays() {
if !usable(&r) {
continue;
let w = self.weights.weight_rs_for_role(r.rs, role);
total_weight += w;
total_count += 1;
if r.is_usable() {
have_weight += w;
have_count += 1;
if total_weight > 0 {
// The consensus lists some weighted bandwidth so return the
// fraction of the weighted bandwidth for which we have
// descriptors.
(have_weight as f64) / (total_weight as f64)
} else if total_count > 0 {
// The consensus lists no weighted bandwidth for these relays,
// but at least it does list relays. Return the fraction of
// relays for which it we have descriptors.
(have_count as f64) / (total_count as f64)
// There are no relays of this kind in the consensus. Return
// 0.0, to avoid dividing by zero and giving NaN.
0.0
/// Return the estimated fraction of possible paths that we have
/// enough microdescriptors to build.
fn frac_usable_paths(&self) -> f64 {
// TODO #504, TODO SPEC: We may want to add a set of is_flagged_fast() and/or
// is_flagged_stable() checks here. This will require spec clarification.
let f_g = self.frac_for_role(WeightRole::Guard, |u| {
u.low_level_details().is_suitable_as_guard()
let f_m = self.frac_for_role(WeightRole::Middle, |_| true);
let f_e = if self.all_relays().any(|u| u.rs.is_flagged_exit()) {
self.frac_for_role(WeightRole::Exit, |u| u.rs.is_flagged_exit())
// If there are no exits at all, we use f_m here.
f_m
f_g * f_m * f_e
/// Return true if there is enough information in this NetDir to build
/// multihop circuits.
fn have_enough_paths(&self) -> bool {
// TODO-A001: This should check for our guards as well, and
// make sure that if they're listed in the consensus, we have
// the descriptors for them.
// If we can build a randomly chosen path with at least this
// probability, we know enough information to participate
// on the network.
let min_frac_paths: f64 = self.params().min_circuit_path_threshold.as_fraction();
// What fraction of paths can we build?
let available = self.frac_usable_paths();
available >= min_frac_paths
/// Choose a relay at random.
/// Each relay is chosen with probability proportional to its weight
/// in the role `role`, and is only selected if the predicate `usable`
/// returns true for it.
/// This function returns None if (and only if) there are no relays
/// with nonzero weight where `usable` returned true.
// TODO this API, with the `usable` closure, invites mistakes where we fail to
// check conditions that are implied by the role we have selected for the relay:
// call sites must include a call to `Relay::is_polarity_inverter()` or whatever.
// IMO the `WeightRole` ought to imply a condition (and it should therefore probably
// be renamed.) -Diziet
pub fn pick_relay<'a, R, P>(
rng: &mut R,
role: WeightRole,
usable: P,
) -> Option<Relay<'a>>
R: rand::Rng,
P: FnMut(&Relay<'a>) -> bool,
let relays: Vec<_> = self.relays().filter(usable).collect();
// This algorithm uses rand::distributions::WeightedIndex, and uses
// gives O(n) time and space to build the index, plus O(log n)
// sampling time.
// We might be better off building a WeightedIndex in advance
// for each `role`, and then sampling it repeatedly until we
// get a relay that satisfies `usable`. Or we might not --
// that depends heavily on the actual particulars of our
// inputs. We probably shouldn't make any changes there
// unless profiling tells us that this function is in a hot
// path.
// The C Tor sampling implementation goes through some trouble
// here to try to make its path selection constant-time. I
// believe that there is no actual remotely exploitable
// side-channel here however. It could be worth analyzing in
// the future.
// This code will give the wrong result if the total of all weights
// can exceed u64::MAX. We make sure that can't happen when we
// set up `self.weights`.
relays[..]
.choose_weighted(rng, |r| self.weights.weight_rs_for_role(r.rs, role))
.ok()
.cloned()
/// Choose `n` relay at random.
/// Relays are chosen without replacement: no relay will be
/// returned twice. Therefore, the resulting vector may be smaller
/// than `n` if we happen to have fewer than `n` appropriate relays.
/// This function returns an empty vector if (and only if) there
/// are no relays with nonzero weight where `usable` returned
/// true.
pub fn pick_n_relays<'a, R, P>(
n: usize,
) -> Vec<Relay<'a>>
// NOTE: See discussion in pick_relay().
let mut relays = match relays[..].choose_multiple_weighted(rng, n, |r| {
self.weights.weight_rs_for_role(r.rs, role) as f64
}) {
Err(_) => Vec::new(),
Ok(iter) => iter.map(Relay::clone).collect(),
relays.shuffle(rng);
relays
/// Compute the weight with which `relay` will be selected for a given
/// `role`.
pub fn relay_weight<'a>(&'a self, relay: &Relay<'a>, role: WeightRole) -> RelayWeight {
RelayWeight(self.weights.weight_rs_for_role(relay.rs, role))
/// Compute the total weight with which any relay matching `usable`
/// will be selected for a given `role`.
/// Note: because this function is used to assess the total
/// properties of the consensus, the `usable` predicate takes a
/// [`RouterStatus`] rather than a [`Relay`].
pub fn total_weight<P>(&self, role: WeightRole, usable: P) -> RelayWeight
P: Fn(&UncheckedRelay<'_>) -> bool,
self.all_relays()
.filter_map(|unchecked| {
if usable(&unchecked) {
Some(RelayWeight(
self.weights.weight_rs_for_role(unchecked.rs, role),
))
.sum()
/// Compute the weight with which a relay with ID `rsa_id` would be
/// selected for a given `role`.
/// Note that weight returned by this function assumes that the
/// relay with that ID is actually [usable](NetDir#usable); if it isn't usable,
/// then other weight-related functions will call its weight zero.
pub fn weight_by_rsa_id(&self, rsa_id: &RsaIdentity, role: WeightRole) -> Option<RelayWeight> {
self.by_rsa_id_unchecked(rsa_id)
.map(|unchecked| RelayWeight(self.weights.weight_rs_for_role(unchecked.rs, role)))