Skip to main content

tor_hsservice/pow/
v1.rs

1//! Code implementing version 1 proof-of-work for onion service hosts.
2//!
3//! Spec links:
4//! * <https://spec.torproject.org/hspow-spec/common-protocol.html>
5//! * <https://spec.torproject.org/hspow-spec/v1-equix.html>
6
7use std::{
8    collections::{BTreeSet, HashMap, VecDeque},
9    sync::{Arc, Mutex, RwLock},
10    task::Waker,
11};
12
13use arrayvec::ArrayVec;
14use equix::EquiXBuilder;
15use futures::{SinkExt, StreamExt};
16use futures::{Stream, channel::mpsc};
17use num_traits::FromPrimitive;
18use rand::CryptoRng;
19use serde::{Deserialize, Serialize};
20use thiserror::Error;
21use tor_basic_utils::RngExt as _;
22use tor_cell::relaycell::hs::pow::{ProofOfWork, v1::ProofOfWorkV1};
23use tor_checkable::timed::TimeRangeBound;
24use tor_error::warn_report;
25use tor_hscrypto::{
26    pk::HsBlindIdKey,
27    pow::v1::{
28        Effort, Instance, RuntimeOption, Seed, SeedHead, Solution, SolutionErrorV1, Verifier,
29    },
30    time::TimePeriod,
31};
32use tor_keymgr::KeyMgr;
33use tor_netdir::{NetDirProvider, NetdirProviderShutdown, params::NetParameters};
34use tor_netdoc::doc::hsdesc::pow::{PowParams, v1::PowParamsV1};
35use tor_persist::{
36    hsnickname::HsNickname,
37    state_dir::{InstanceRawSubdir, StorageHandle},
38};
39use tor_rtcompat::Runtime;
40use tor_rtcompat::SpawnExt;
41use web_time_compat::{Duration, Instant, InstantExt, SystemTime, SystemTimeExt};
42
43use crate::{
44    BlindIdPublicKeySpecifier, OnionServiceConfig, RendRequest, ReplayError, StartupError,
45    rend_handshake,
46    replay::{OpenReplayLogError, PowNonceReplayLog},
47    status::{PowManagerStatusSender, Problem, State as PowManagerState},
48};
49
50use super::NewPowManager;
51
52/// Proof-of-Work manager type alias for production, using concrete [`RendRequest`].
53pub(crate) type PowManager<R> = PowManagerGeneric<R, RendRequest>;
54
55/// This is responsible for rotating Proof-of-Work seeds and doing verification of PoW solves.
56pub(crate) struct PowManagerGeneric<R, Q>(RwLock<State<R, Q>>);
57
58/// Internal state for [`PowManagerGeneric`].
59struct State<R, Q> {
60    /// The [`Seed`]s for a given [`TimePeriod`]
61    ///
62    /// The [`ArrayVec`] contains the current and previous seed, and the [`SystemTime`] is when the
63    /// current seed will expire.
64    seeds: HashMap<TimePeriod, SeedsForTimePeriod>,
65
66    /// Verifiers for all the seeds that exist in `seeds`.
67    verifiers: HashMap<SeedHead, (Verifier, Mutex<PowNonceReplayLog>)>,
68
69    /// The nickname for this hidden service.
70    ///
71    /// We need this so we can get the blinded keys from the [`KeyMgr`].
72    nickname: HsNickname,
73
74    /// Directory used to store nonce replay log.
75    instance_dir: InstanceRawSubdir,
76
77    /// Key manager.
78    keymgr: Arc<KeyMgr>,
79
80    /// Current suggested effort that we publish in the pow-params line.
81    ///
82    /// This is only read by the PowManagerGeneric, and is written to by the [`RendRequestReceiver`].
83    suggested_effort: Arc<Mutex<Effort>>,
84
85    /// Runtime
86    runtime: R,
87
88    /// Handle for storing state we need to persist to disk.
89    storage_handle: StorageHandle<PowManagerStateRecord>,
90
91    /// Queue to tell the publisher to re-upload a descriptor for a given TP, since we've rotated
92    /// that seed.
93    publisher_update_tx: mpsc::Sender<TimePeriod>,
94
95    /// The [`RendRequestReceiver`], which contains the queue of [`RendRequest`]s.
96    ///
97    /// We need a reference to this in order to tell it when to update the suggested_effort value.
98    rend_request_rx: RendRequestReceiver<R, Q>,
99
100    /// [`NetDirProvider`], used for getting consensus parameters for configuration values.
101    netdir_provider: Arc<dyn NetDirProvider>,
102
103    /// Sender for reporting back onion service status.
104    status_tx: PowManagerStatusSender,
105
106    /// Receiver for the current configuration.
107    config_rx: postage::watch::Receiver<Arc<OnionServiceConfig>>,
108}
109
110#[derive(Serialize, Deserialize, Debug, Clone)]
111/// Information about the current and previous [`Seed`] for a given [`TimePeriod`].
112struct SeedsForTimePeriod {
113    /// The previous and current [`Seed`].
114    ///
115    /// The last element in this array is the current seed.
116    seeds: ArrayVec<Seed, 2>,
117
118    /// When the current seed will expire.
119    next_expiration_time: SystemTime,
120}
121
122#[derive(Debug)]
123#[allow(unused)]
124/// A PoW solve was invalid.
125///
126/// While this contains the reason for the failure, we probably just want to use that for
127/// debugging, we shouldn't make any logical decisions based on what the particular error was.
128pub(crate) enum PowSolveError {
129    /// Seed head was not recognized, it may be expired.
130    InvalidSeedHead,
131    /// We have already seen a solve with this nonce
132    NonceReplay(ReplayError),
133    /// The bytes given as a solution do not form a valid Equi-X puzzle
134    InvalidEquixSolution(SolutionErrorV1),
135    /// The solution given was invalid.
136    InvalidSolve(tor_hscrypto::pow::Error),
137}
138
139/// On-disk record of [`PowManagerGeneric`] state.
140#[derive(Serialize, Deserialize, Debug, Default)]
141pub(crate) struct PowManagerStateRecord {
142    /// Seeds for each time period.
143    ///
144    /// Conceptually, this is a map between TimePeriod and SeedsForTimePeriod, but since TimePeriod
145    /// can't be serialized to a string, it's not very simple to use serde to serialize it like
146    /// that, so we instead store it as a list of tuples, and convert it to/from the map when
147    /// saving/loading.
148    seeds: Vec<(TimePeriod, SeedsForTimePeriod)>,
149
150    /// Most recently published suggested_effort value.
151    #[serde(default)]
152    suggested_effort: Effort,
153    // We don't persist any per-period state. While it might be sort of nice to, it's complex to
154    // decide when to write the state out to disk. The disadvantage to not storing it is that when
155    // we restart the process, we may be up to 5 minutes slower to update the suggested effort to a
156    // new value, which isn't particularly bad. The only case it would be bad is if a attacker has
157    // a way to cause the Arti process to restart (in which case they could do that just before the
158    // update period to pin the suggested effort value at a specific value), but if they have that,
159    // they have a much more valuable attack (including as a DoS vector) than just a PoW bypass.
160}
161
162impl<R: Runtime, Q> State<R, Q> {
163    /// Make a [`PowManagerStateRecord`] for this state.
164    pub(crate) fn to_record(&self) -> PowManagerStateRecord {
165        PowManagerStateRecord {
166            seeds: self.seeds.clone().into_iter().collect(),
167            suggested_effort: *self.suggested_effort.lock().expect("Lock poisoned"),
168        }
169    }
170
171    /// Remove a verifier and delete the backing file.
172    fn remove_verifier(&mut self, seed: &SeedHead) {
173        if let Some((_, replay_log)) = self.verifiers.remove(seed) {
174            let _ = replay_log.into_inner().expect("Lock poisoned").delete();
175        }
176    }
177}
178
179/// How frequently the suggested effort should be recalculated.
180const HS_UPDATE_PERIOD: Duration = Duration::from_secs(300);
181
182/// When the suggested effort has changed by less than this much, we don't republish it.
183///
184/// Specified as "15 percent" in <https://spec.torproject.org/hspow-spec/common-protocol.html>
185///
186/// However, we may want to make this configurable in the future.
187const SUGGESTED_EFFORT_DEADZONE: f64 = 0.15;
188
189/// How soon before a seed's expiration time we should rotate it and publish a new seed.
190const SEED_EARLY_ROTATION_TIME: Duration = Duration::from_secs(60 * 5);
191
192/// Minimum seed expiration time in minutes. See:
193/// <https://spec.torproject.org/hspow-spec/v1-equix.html#parameter-descriptor>
194const EXPIRATION_TIME_MINS_MIN: u64 = 105;
195
196/// Maximum seed expiration time in minutes. See:
197/// <https://spec.torproject.org/hspow-spec/v1-equix.html#parameter-descriptor>
198const EXPIRATION_TIME_MINS_MAX: u64 = 120;
199
200/// Enforce that early rotation time is less than or equal to min expiration time.
201const _: () = assert!(
202    SEED_EARLY_ROTATION_TIME.as_secs() <= EXPIRATION_TIME_MINS_MIN * 60,
203    "Early rotation time must be less than minimum expiration time"
204);
205
206/// Enforce that min expiration time is less than or equal to max.
207const _: () = assert!(
208    EXPIRATION_TIME_MINS_MIN <= EXPIRATION_TIME_MINS_MAX,
209    "Minimum expiration time must be less than or equal to max"
210);
211
212/// Depth of the queue used to signal the publisher that it needs to update a given time period.
213///
214/// 32 is likely way larger than we need but the messages are tiny so we might as well.
215const PUBLISHER_UPDATE_QUEUE_DEPTH: usize = 32;
216
217#[derive(Error, Debug, Clone)]
218#[allow(dead_code)] // We want to show fields in Debug even if we don't use them.
219#[non_exhaustive]
220/// Error within the PoW subsystem.
221pub enum PowError {
222    /// We don't have a key that is needed.
223    #[error("Missing required key.")]
224    MissingKey,
225    /// Error in the underlying storage layer.
226    #[error(transparent)]
227    StorageError(#[from] tor_persist::Error),
228    /// Error from the ReplayLog.
229    #[error(transparent)]
230    OpenReplayLog(#[from] OpenReplayLogError),
231    /// NetDirProvider has shut down
232    #[error(transparent)]
233    NetdirProviderShutdown(#[from] NetdirProviderShutdown),
234}
235
236impl<R: Runtime, Q: MockableRendRequest + Send + 'static> PowManagerGeneric<R, Q> {
237    /// Create a new [`PowManagerGeneric`].
238    #[allow(clippy::new_ret_no_self, clippy::too_many_arguments)]
239    pub(crate) fn new(
240        runtime: R,
241        nickname: HsNickname,
242        instance_dir: InstanceRawSubdir,
243        keymgr: Arc<KeyMgr>,
244        storage_handle: StorageHandle<PowManagerStateRecord>,
245        netdir_provider: Arc<dyn NetDirProvider>,
246        status_tx: PowManagerStatusSender,
247        config_rx: postage::watch::Receiver<Arc<OnionServiceConfig>>,
248    ) -> Result<NewPowManager<R>, StartupError> {
249        let on_disk_state = storage_handle
250            .load()
251            .map_err(StartupError::LoadState)?
252            .unwrap_or_else(PowManagerStateRecord::default);
253
254        let seeds: HashMap<TimePeriod, SeedsForTimePeriod> =
255            on_disk_state.seeds.into_iter().collect();
256        let suggested_effort = Arc::new(Mutex::new(on_disk_state.suggested_effort));
257
258        let mut verifiers = HashMap::new();
259        for (tp, seeds_for_tp) in seeds.clone().into_iter() {
260            for seed in seeds_for_tp.seeds {
261                let verifier = match Self::make_verifier(
262                    &keymgr,
263                    nickname.clone(),
264                    tp,
265                    seed.clone(),
266                    &config_rx.borrow(),
267                ) {
268                    Some(verifier) => verifier,
269                    None => {
270                        tracing::warn!(
271                            "Couldn't construct verifier (key not available?). We will continue without this key, but this may prevent clients from connecting..."
272                        );
273                        continue;
274                    }
275                };
276                let replay_log = match PowNonceReplayLog::new_logged(&instance_dir, &seed) {
277                    Ok(replay_log) => replay_log,
278                    Err(err) => {
279                        warn_report!(
280                            err,
281                            "Error constructing replay log. We will continue without the log, but be aware that this may allow attackers to bypass PoW defenses..."
282                        );
283                        continue;
284                    }
285                };
286                verifiers.insert(seed.head(), (verifier, Mutex::new(replay_log)));
287            }
288        }
289
290        // This queue is extremely small, and we only make one of it per onion service, so it's
291        // fine to not use memquota tracking.
292        let (publisher_update_tx, publisher_update_rx) =
293            crate::mpsc_channel_no_memquota(PUBLISHER_UPDATE_QUEUE_DEPTH);
294
295        let (rend_req_tx, rend_req_rx_channel) = super::make_rend_queue();
296        let rend_req_rx = RendRequestReceiver::new(
297            runtime.clone(),
298            nickname.clone(),
299            suggested_effort.clone(),
300            netdir_provider.clone(),
301            status_tx.clone(),
302            config_rx.clone(),
303        );
304
305        let state = State {
306            seeds,
307            nickname,
308            instance_dir,
309            keymgr,
310            publisher_update_tx,
311            verifiers,
312            suggested_effort: suggested_effort.clone(),
313            runtime: runtime.clone(),
314            storage_handle,
315            rend_request_rx: rend_req_rx.clone(),
316            netdir_provider,
317            status_tx,
318            config_rx,
319        };
320        let pow_manager = Arc::new(PowManagerGeneric(RwLock::new(state)));
321
322        rend_req_rx.start_accept_thread(runtime, pow_manager.clone(), rend_req_rx_channel);
323
324        Ok(NewPowManager {
325            pow_manager,
326            rend_req_tx,
327            rend_req_rx: Box::pin(rend_req_rx),
328            publisher_update_rx,
329        })
330    }
331
332    /// Launch background task to rotate seeds.
333    pub(crate) fn launch(self: &Arc<Self>) -> Result<(), StartupError> {
334        let pow_manager = self.clone();
335        let runtime = pow_manager.0.read().expect("Lock poisoned").runtime.clone();
336
337        runtime
338            .spawn(pow_manager.main_loop_error_wrapper())
339            .map_err(|cause| StartupError::Spawn {
340                spawning: "pow manager",
341                cause: cause.into(),
342            })?;
343
344        self.0
345            .write()
346            .expect("Lock poisoned")
347            .status_tx
348            .send(PowManagerState::Running, None);
349        Ok(())
350    }
351
352    /// Run [`Self::main_loop_task`], reporting any errors.
353    async fn main_loop_error_wrapper(self: Arc<Self>) {
354        if let Err(err) = self.clone().main_loop_task().await {
355            self.0
356                .write()
357                .expect("Lock poisoned")
358                .status_tx
359                .send_broken(Problem::Pow(err));
360        }
361    }
362
363    /// Main loop for rotating seeds.
364    async fn main_loop_task(self: Arc<Self>) -> Result<(), PowError> {
365        let runtime = self.0.write().expect("Lock poisoned").runtime.clone();
366
367        let mut last_suggested_effort_update = runtime.now();
368        let last_published_suggested_effort: u32 = (*self
369            .0
370            .read()
371            .expect("Lock poisoned")
372            .suggested_effort
373            .lock()
374            .expect("Lock poisoned"))
375        .into();
376        // Deal with effort values as i64 in this part of the code
377        // to allow for subtracting them without worring about underflow.
378        let mut last_published_suggested_effort: i64 = last_published_suggested_effort.into();
379
380        let netdir_provider = self
381            .0
382            .read()
383            .expect("Lock poisoned")
384            .netdir_provider
385            .clone();
386        let net_params = netdir_provider
387            .wait_for_netdir(tor_netdir::Timeliness::Timely)
388            .await?
389            .params()
390            .clone();
391
392        loop {
393            let next_update_time = self.rotate_seeds_if_expiring().await;
394
395            // Update the suggested effort, if needed
396            if runtime.now() - last_suggested_effort_update >= HS_UPDATE_PERIOD {
397                let (tps_to_update, mut publisher_update_tx) = {
398                    let mut tps_to_update = vec![];
399
400                    let inner = self.0.read().expect("Lock poisoned");
401
402                    inner.rend_request_rx.update_suggested_effort(&net_params);
403                    last_suggested_effort_update = runtime.now();
404                    let new_suggested_effort: u32 =
405                        (*inner.suggested_effort.lock().expect("Lock poisoned")).into();
406                    let new_suggested_effort: i64 = new_suggested_effort.into();
407
408                    let percent_change = (new_suggested_effort - last_published_suggested_effort)
409                        as f64
410                        / last_published_suggested_effort as f64;
411                    if percent_change.abs() >= SUGGESTED_EFFORT_DEADZONE {
412                        last_published_suggested_effort = new_suggested_effort;
413
414                        tps_to_update = inner.seeds.iter().map(|x| *x.0).collect();
415                    }
416
417                    let publisher_update_tx = inner.publisher_update_tx.clone();
418                    (tps_to_update, publisher_update_tx)
419                };
420
421                for time_period in tps_to_update {
422                    let _ = publisher_update_tx.send(time_period).await;
423                }
424            }
425
426            let suggested_effort_update_delay = HS_UPDATE_PERIOD.saturating_sub(
427                runtime
428                    .now()
429                    .saturating_duration_since(last_suggested_effort_update),
430            );
431
432            // A new TimePeriod that we don't know about (and thus that isn't in next_update_time)
433            // might get added at any point. Making sure that our maximum delay is the minimum
434            // amount of time that it might take for a seed to expire means that we can be sure
435            // that we will rotate newly-added seeds properly.
436            const MAX_DELAY: Duration = Duration::from_secs(EXPIRATION_TIME_MINS_MIN * 60)
437                .checked_sub(SEED_EARLY_ROTATION_TIME)
438                .expect("SEED_EARLY_ROTATION_TIME too high, or EXPIRATION_TIME_MINS_MIN too low.");
439            let delay = next_update_time
440                .map(|x| x.duration_since(SystemTime::get()).unwrap_or(MAX_DELAY))
441                .unwrap_or(MAX_DELAY)
442                .min(MAX_DELAY)
443                .min(suggested_effort_update_delay);
444
445            tracing::debug!(next_wakeup = ?delay, "Recalculated PoW seeds.");
446
447            runtime.sleep(delay).await;
448        }
449    }
450
451    /// Make a randomized seed expiration time.
452    fn make_next_expiration_time<Rng: rand::Rng + CryptoRng>(rng: &mut Rng) -> SystemTime {
453        SystemTime::get()
454            + Duration::from_secs(
455                60 * rng
456                    .gen_range_checked(EXPIRATION_TIME_MINS_MIN..=EXPIRATION_TIME_MINS_MAX)
457                    .expect("Can't generate expiration_time"),
458            )
459    }
460
461    /// Make a ner [`Verifier`] for a given [`TimePeriod`] and [`Seed`].
462    ///
463    /// If a key is not available for this TP, returns None.
464    ///
465    /// This takes individual arguments instead of `&self` to avoid getting into any trouble with
466    /// locking.
467    fn make_verifier(
468        keymgr: &Arc<KeyMgr>,
469        nickname: HsNickname,
470        time_period: TimePeriod,
471        seed: Seed,
472        config: &OnionServiceConfig,
473    ) -> Option<Verifier> {
474        let blind_id_spec = BlindIdPublicKeySpecifier::new(nickname, time_period);
475        let blind_id_key = match keymgr.get::<HsBlindIdKey>(&blind_id_spec) {
476            Ok(blind_id_key) => blind_id_key,
477            Err(err) => {
478                warn_report!(err, "KeyMgr error when getting blinded ID key for PoW");
479                None
480            }
481        };
482        let instance = Instance::new(blind_id_key?.id(), seed);
483        let mut equix = EquiXBuilder::default();
484        if *config.disable_pow_compilation() {
485            equix.runtime(RuntimeOption::InterpretOnly);
486        }
487        Some(Verifier::new_with_equix(instance, equix))
488    }
489
490    /// Calculate a time when we want to rotate a seed, slightly before it expires, in order to
491    /// ensure that clients don't ever download a seed that is already out of date.
492    fn calculate_early_rotation_time(expiration_time: SystemTime) -> SystemTime {
493        // Underflow cannot happen because:
494        //
495        // * We set the expiration time to the current time plus at least the minimum
496        //   expiration time
497        // * We know (backed up by a compile-time assertion) that SEED_EARLY_ROTATION_TIME is
498        //   less than the minimum expiration time.
499        //
500        // Thus, the only way this subtraction can underflow is if the system time at the
501        // moment we set the expiration time was before the epoch, which is not possible on
502        // reasonable platforms.
503        expiration_time
504            .checked_sub(SEED_EARLY_ROTATION_TIME)
505            .expect("PoW seed expiration underflow")
506    }
507
508    /// Rotate any seeds that will expire soon.
509    ///
510    /// This also pokes the publisher when needed to cause rotated seeds to be published.
511    ///
512    /// Returns the next time this function should be called again.
513    async fn rotate_seeds_if_expiring(&self) -> Option<SystemTime> {
514        let mut expired_verifiers = vec![];
515        let mut new_verifiers = vec![];
516
517        let mut update_times = vec![];
518        let mut updated_tps = vec![];
519        let mut expired_tps = vec![];
520
521        let mut publisher_update_tx = {
522            let mut state = self.0.write().expect("Lock poisoned");
523
524            let config = state.config_rx.borrow().clone();
525            let keymgr = state.keymgr.clone();
526            let nickname = state.nickname.clone();
527
528            for (time_period, info) in state.seeds.iter_mut() {
529                let rotation_time = Self::calculate_early_rotation_time(info.next_expiration_time);
530                update_times.push(rotation_time);
531
532                if rotation_time <= SystemTime::get() {
533                    // This does not allow for easy testing, but because we're in a async function, it's
534                    // non-trivial to pass in a Rng from the outside world. If we end up writing tests that
535                    // require that, we can take a function to generate a Rng, but for now, just using the
536                    // thread rng is fine.
537                    let mut rng = rand::rng();
538
539                    let seed = Seed::new(&mut rng, None);
540                    let verifier = match Self::make_verifier(
541                        &keymgr,
542                        nickname.clone(),
543                        *time_period,
544                        seed.clone(),
545                        &config,
546                    ) {
547                        Some(verifier) => verifier,
548                        None => {
549                            // We use not having a key for a given TP as the signal that we should
550                            // stop keeping track of seeds for that TP.
551                            expired_tps.push(*time_period);
552                            continue;
553                        }
554                    };
555
556                    let expired_seed = if info.seeds.is_full() {
557                        info.seeds.pop_at(0)
558                    } else {
559                        None
560                    };
561                    // .push() is safe, since we just made space above.
562                    info.seeds.push(seed.clone());
563                    info.next_expiration_time = Self::make_next_expiration_time(&mut rng);
564                    update_times.push(info.next_expiration_time);
565
566                    // Make a note to add the new verifier and remove the old one.
567                    new_verifiers.push((seed, verifier));
568                    if let Some(expired_seed) = expired_seed {
569                        expired_verifiers.push(expired_seed.head());
570                    }
571
572                    // Tell the publisher to update this TP
573                    updated_tps.push(*time_period);
574
575                    tracing::debug!(time_period = ?time_period, "Rotated PoW seed");
576                }
577            }
578
579            for time_period in expired_tps {
580                if let Some(seeds) = state.seeds.remove(&time_period) {
581                    for seed in seeds.seeds {
582                        state.remove_verifier(&seed.head());
583                    }
584                }
585            }
586
587            for (seed, verifier) in new_verifiers {
588                let replay_log = Mutex::new(
589                    PowNonceReplayLog::new_logged(&state.instance_dir, &seed)
590                        .expect("Couldn't make ReplayLog."),
591                );
592                state.verifiers.insert(seed.head(), (verifier, replay_log));
593            }
594
595            for seed_head in expired_verifiers {
596                state.remove_verifier(&seed_head);
597            }
598
599            let record = state.to_record();
600            if let Err(err) = state.storage_handle.store(&record) {
601                warn_report!(err, "Error saving PoW state");
602            }
603
604            state.publisher_update_tx.clone()
605        };
606
607        for time_period in updated_tps {
608            if let Err(err) = publisher_update_tx.send(time_period).await {
609                warn_report!(err, "Couldn't send update message to publisher");
610            }
611        }
612
613        update_times.iter().min().cloned()
614    }
615
616    /// Get [`PowParams`] for a given [`TimePeriod`].
617    ///
618    /// If we don't have any [`Seed`]s for the requested period, generate them. This is the only
619    /// way that [`PowManagerGeneric`] learns about new [`TimePeriod`]s.
620    pub(crate) fn get_pow_params<Rng: rand::Rng + CryptoRng>(
621        self: &Arc<Self>,
622        time_period: TimePeriod,
623        rng: &mut Rng,
624    ) -> Result<PowParams, PowError> {
625        let (seed_and_expiration, suggested_effort) = {
626            let state = self.0.read().expect("Lock poisoned");
627            let seed = state
628                .seeds
629                .get(&time_period)
630                .and_then(|x| Some((x.seeds.last()?.clone(), x.next_expiration_time)));
631            let suggested_effort = *state.suggested_effort.lock().expect("Lock poisoned");
632            (seed, suggested_effort)
633        };
634
635        let (seed, expiration) = match seed_and_expiration {
636            Some(seed) => seed,
637            None => {
638                // We don't have a seed for this time period, so we need to generate one.
639
640                let seed = Seed::new(rng, None);
641                let next_expiration_time = Self::make_next_expiration_time(rng);
642
643                let mut seeds = ArrayVec::new();
644                seeds.push(seed.clone());
645
646                let mut state = self.0.write().expect("Lock poisoned");
647
648                state.seeds.insert(
649                    time_period,
650                    SeedsForTimePeriod {
651                        seeds,
652                        next_expiration_time,
653                    },
654                );
655
656                let verifier = Self::make_verifier(
657                    &state.keymgr,
658                    state.nickname.clone(),
659                    time_period,
660                    seed.clone(),
661                    &state.config_rx.borrow(),
662                )
663                .ok_or(PowError::MissingKey)?;
664
665                let replay_log =
666                    Mutex::new(PowNonceReplayLog::new_logged(&state.instance_dir, &seed)?);
667                state.verifiers.insert(seed.head(), (verifier, replay_log));
668
669                let record = state.to_record();
670                state.storage_handle.store(&record)?;
671
672                (seed, next_expiration_time)
673            }
674        };
675
676        Ok(PowParams::V1(PowParamsV1::new(
677            TimeRangeBound::new(seed, ..expiration),
678            suggested_effort,
679        )))
680    }
681
682    /// Verify a PoW solve.
683    fn check_solve(self: &Arc<Self>, solve: &ProofOfWorkV1) -> Result<(), PowSolveError> {
684        // Note that we put the nonce into the replay log before we check the solve. While this
685        // might not be ideal, it's not a problem and is probably the most reasonable thing to do.
686        // See commit bc5b313028 for a more full explanation.
687        {
688            let state = self.0.write().expect("Lock poisoned");
689            let mut replay_log = match state.verifiers.get(&solve.seed_head()) {
690                Some((_, replay_log)) => replay_log.lock().expect("Lock poisoned"),
691                None => return Err(PowSolveError::InvalidSeedHead),
692            };
693            replay_log
694                .check_for_replay(solve.nonce())
695                .map_err(PowSolveError::NonceReplay)?;
696        }
697
698        // TODO: Once RwLock::downgrade is stabilized, it would make sense to use it here...
699
700        let state = self.0.read().expect("Lock poisoned");
701        let verifier = match state.verifiers.get(&solve.seed_head()) {
702            Some((verifier, _)) => verifier,
703            None => return Err(PowSolveError::InvalidSeedHead),
704        };
705
706        let solution = match Solution::try_from_bytes(
707            solve.nonce().clone(),
708            solve.effort(),
709            solve.seed_head(),
710            solve.solution(),
711        ) {
712            Ok(solution) => solution,
713            Err(err) => return Err(PowSolveError::InvalidEquixSolution(err)),
714        };
715
716        match verifier.check(&solution) {
717            Ok(()) => Ok(()),
718            Err(err) => Err(PowSolveError::InvalidSolve(err)),
719        }
720    }
721}
722
723/// Trait to allow mocking PowManagerGeneric in tests.
724trait MockablePowManager {
725    /// Verify a PoW solve.
726    fn check_solve(self: &Arc<Self>, solve: &ProofOfWorkV1) -> Result<(), PowSolveError>;
727}
728
729impl<R: Runtime> MockablePowManager for PowManager<R> {
730    fn check_solve(self: &Arc<Self>, solve: &ProofOfWorkV1) -> Result<(), PowSolveError> {
731        PowManager::check_solve(self, solve)
732    }
733}
734
735/// Trait to allow mocking RendRequest in tests.
736pub(crate) trait MockableRendRequest {
737    /// Get the proof-of-work extension associated with this request.
738    fn proof_of_work(&self) -> Result<Option<&ProofOfWork>, rend_handshake::IntroRequestError>;
739}
740
741impl MockableRendRequest for RendRequest {
742    fn proof_of_work(&self) -> Result<Option<&ProofOfWork>, rend_handshake::IntroRequestError> {
743        Ok(self
744            .intro_request()?
745            .intro_payload()
746            .proof_of_work_extension())
747    }
748}
749
750/// Wrapper around [`RendRequest`] that implements [`std::cmp::Ord`] to sort by [`Effort`] and time.
751#[derive(Debug)]
752struct RendRequestOrdByEffort<Q> {
753    /// The underlying request.
754    request: Q,
755    /// The proof-of-work options, if given.
756    pow: Option<ProofOfWorkV1>,
757    /// The maximum effort allowed. If the effort of this request is higher than this, it will be
758    /// treated as though it is this value.
759    max_effort: Effort,
760    /// When this request was received, used for ordreing if the effort values are the same.
761    recv_time: Instant,
762    /// Unique number for this request, which is used for ordering among requests with the same
763    /// timestamp.
764    ///
765    /// This is intended to be monotonically increasing, although it may overflow. Overflows are
766    /// not handled in any special way, given that they are a edge case of an edge case, and
767    /// ordering among requests that came in at the same instant is not important.
768    request_num: u64,
769}
770
771impl<Q: MockableRendRequest> RendRequestOrdByEffort<Q> {
772    /// Create a new [`RendRequestOrdByEffort`].
773    fn new(
774        request: Q,
775        max_effort: Effort,
776        request_num: u64,
777    ) -> Result<Self, rend_handshake::IntroRequestError> {
778        let pow = match request.proof_of_work()?.cloned() {
779            Some(ProofOfWork::V1(pow)) => Some(pow),
780            None | Some(_) => None,
781        };
782
783        Ok(Self {
784            request,
785            pow,
786            max_effort,
787            recv_time: Instant::get(),
788            request_num,
789        })
790    }
791}
792
793impl<Q: MockableRendRequest> Ord for RendRequestOrdByEffort<Q> {
794    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
795        let self_effort = self.pow.as_ref().map_or(Effort::zero(), |pow| {
796            Effort::min(pow.effort(), self.max_effort)
797        });
798        let other_effort = other.pow.as_ref().map_or(Effort::zero(), |pow| {
799            Effort::min(pow.effort(), other.max_effort)
800        });
801        match self_effort.cmp(&other_effort) {
802            std::cmp::Ordering::Equal => {
803                // Flip ordering, since we want the oldest ones to be handled first.
804                match other.recv_time.cmp(&self.recv_time) {
805                    // Use request_num as a final tiebreaker, also flipping ordering (since
806                    // lower-numbered requests should be older and thus come first)
807                    std::cmp::Ordering::Equal => other.request_num.cmp(&self.request_num),
808                    not_equal => not_equal,
809                }
810            }
811            not_equal => not_equal,
812        }
813    }
814}
815
816impl<Q: MockableRendRequest> PartialOrd for RendRequestOrdByEffort<Q> {
817    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
818        Some(self.cmp(other))
819    }
820}
821
822impl<Q: MockableRendRequest> PartialEq for RendRequestOrdByEffort<Q> {
823    fn eq(&self, other: &Self) -> bool {
824        let self_effort = self.pow.as_ref().map_or(Effort::zero(), |pow| {
825            Effort::min(pow.effort(), self.max_effort)
826        });
827        let other_effort = other.pow.as_ref().map_or(Effort::zero(), |pow| {
828            Effort::min(pow.effort(), other.max_effort)
829        });
830        self_effort == other_effort && self.recv_time == other.recv_time
831    }
832}
833
834impl<Q: MockableRendRequest> Eq for RendRequestOrdByEffort<Q> {}
835
836/// Implements [`Stream`] for incoming [`RendRequest`]s, using a priority queue system to dequeue
837/// high-[`Effort`] requests first.
838///
839/// This is implemented on top of a [`mpsc::Receiver`]. There is a thread that dequeues from the
840/// [`mpsc::Receiver`], checks the PoW solve, and if it is correct, adds it to a [`BTreeSet`],
841/// which the [`Stream`] implementation reads from.
842///
843/// This is not particularly optimized — queueing and dequeuing use a [`Mutex`], so there may be
844/// some contention there. It's possible there may be some fancy lockless (or more optimized)
845/// priority queue that we could use, but we should properly benchmark things before trying to make
846/// a optimization like that.
847pub(crate) struct RendRequestReceiver<R, Q>(Arc<Mutex<RendRequestReceiverInner<R, Q>>>);
848
849impl<R, Q> Clone for RendRequestReceiver<R, Q> {
850    fn clone(&self) -> Self {
851        Self(self.0.clone())
852    }
853}
854
855/// Inner implementation for [`RendRequestReceiver`].
856struct RendRequestReceiverInner<R, Q> {
857    /// Internal priority queue of requests.
858    queue: BTreeSet<RendRequestOrdByEffort<Q>>,
859
860    /// Internal FIFO queue of requests used when PoW is disabled.
861    ///
862    /// We have this here to support switching back and forth between PoW enabled and disabled at
863    /// runtime, although that isn't currently supported.
864    queue_pow_disabled: VecDeque<Q>,
865
866    /// Waker to inform async readers when there is a new message on the queue.
867    waker: Option<Waker>,
868
869    /// Runtime, used to get current time in a testable way.
870    runtime: R,
871
872    /// Nickname, use when reporting metrics.
873    nickname: HsNickname,
874
875    /// [`NetDirProvider`], for getting configuration values in consensus parameters.
876    netdir_provider: Arc<dyn NetDirProvider>,
877
878    /// Current configuration, used to see whether PoW is enabled or not.
879    config_rx: postage::watch::Receiver<Arc<OnionServiceConfig>>,
880
881    /// When the current update period started.
882    update_period_start: Instant,
883    /// Number of requests that were enqueued during the current update period, and had an effort
884    /// greater than or equal to the suggested effort.
885    num_enqueued_gte_suggested: usize,
886    /// Number of requests that were dequeued during the current update period.
887    num_dequeued: u32,
888    /// Amount of time during the current update period that we spent with no requests in the
889    /// queue.
890    idle_time: Duration,
891    /// Time that the queue last went from having items in it to not having items in it, or vice
892    /// versa. This is used to update idle_time.
893    last_transition: Instant,
894    /// Sum of all effort values that were validated and enqueued during the current update period.
895    total_effort: u64,
896
897    /// Most recent published suggested effort value.
898    ///
899    /// We write to this, which is then published in the pow-params line by [`PowManagerGeneric`].
900    suggested_effort: Arc<Mutex<Effort>>,
901
902    /// Sender for reporting back onion service status.
903    status_tx: PowManagerStatusSender,
904}
905
906impl<R: Runtime, Q: MockableRendRequest + Send + 'static> RendRequestReceiver<R, Q> {
907    /// Create a new [`RendRequestReceiver`].
908    fn new(
909        runtime: R,
910        nickname: HsNickname,
911        suggested_effort: Arc<Mutex<Effort>>,
912        netdir_provider: Arc<dyn NetDirProvider>,
913        status_tx: PowManagerStatusSender,
914        config_rx: postage::watch::Receiver<Arc<OnionServiceConfig>>,
915    ) -> Self {
916        let now = runtime.now();
917        RendRequestReceiver(Arc::new(Mutex::new(RendRequestReceiverInner {
918            queue: BTreeSet::new(),
919            queue_pow_disabled: VecDeque::new(),
920            waker: None,
921            runtime,
922            nickname,
923            netdir_provider,
924            config_rx,
925            update_period_start: now,
926            num_enqueued_gte_suggested: 0,
927            num_dequeued: 0,
928            idle_time: Duration::new(0, 0),
929            last_transition: now,
930            total_effort: 0,
931            suggested_effort,
932            status_tx,
933        })))
934    }
935
936    // spawn_blocking executes immediately, but some of our abstractions make clippy not
937    // realize this.
938    #[allow(clippy::let_underscore_future)]
939    /// Start helper thread to accept and validate [`RendRequest`]s.
940    fn start_accept_thread<P: MockablePowManager + Send + Sync + 'static>(
941        &self,
942        runtime: R,
943        pow_manager: Arc<P>,
944        inner_receiver: mpsc::Receiver<Q>,
945    ) {
946        let receiver = self.clone();
947        let runtime_clone = runtime.clone();
948        let _ = runtime.clone().spawn_blocking(move || {
949            if let Err(err) =
950                receiver
951                    .clone()
952                    .accept_loop(&runtime_clone, &pow_manager, inner_receiver)
953            {
954                warn_report!(err, "PoW accept loop error!");
955                receiver
956                    .0
957                    .lock()
958                    .expect("Lock poisoned")
959                    .status_tx
960                    .send_broken(Problem::Pow(err));
961            }
962        });
963
964        let receiver = self.clone();
965        let _ = runtime.clone().spawn_blocking(move || {
966            if let Err(err) = receiver.clone().expire_old_requests_loop(&runtime) {
967                warn_report!(err, "PoW request expiration loop error!");
968                receiver
969                    .0
970                    .lock()
971                    .expect("Lock poisoned")
972                    .status_tx
973                    .send_broken(Problem::Pow(err));
974            }
975        });
976    }
977
978    /// Update the suggested effort value, as per the algorithm in prop362
979    fn update_suggested_effort(&self, net_params: &NetParameters) {
980        let mut inner = self.0.lock().expect("Lock poisoned");
981
982        let decay_adjustment_fraction = net_params.hs_pow_v1_default_decay_adjustment.as_fraction();
983
984        let update_period_duration = inner.runtime.now() - inner.update_period_start;
985        if inner.num_dequeued != 0 && update_period_duration.as_millis() != 0 {
986            let avg_request_duration = update_period_duration / inner.num_dequeued;
987            let num_dequeued = f64::from(inner.num_dequeued);
988            if inner.queue.is_empty() {
989                let now = inner.runtime.now();
990                let last_transition = inner.last_transition;
991                inner.idle_time += now - last_transition;
992            }
993            let adjusted_idle_time = Duration::saturating_sub(
994                inner.idle_time,
995                avg_request_duration * inner.queue.len().try_into().expect("Queue too large."),
996            );
997            // TODO: use as_millis_f64 when stable
998            let idle_fraction = f64::from_u128(adjusted_idle_time.as_millis())
999                .expect("Conversion error")
1000                / f64::from_u128(update_period_duration.as_millis()).expect("Conversion error");
1001            let busy_fraction = 1.0 - idle_fraction;
1002
1003            let mut suggested_effort = inner.suggested_effort.lock().expect("Lock poisoned");
1004            let suggested_effort_inner: u32 = (*suggested_effort).into();
1005            let suggested_effort_inner_f64 = f64::from(suggested_effort_inner);
1006
1007            if busy_fraction == 0.0 {
1008                // Infallible, this takes the previous suggested effort and
1009                // reduces it, so overflow is not possible, since the netdir
1010                // code enforces that it's in the range of 0.0 - 0.99.
1011                debug_assert!(decay_adjustment_fraction < 1.0);
1012                let new_suggested_effort =
1013                    u32::from_f64(suggested_effort_inner_f64 * decay_adjustment_fraction)
1014                        .expect("Conversion error");
1015                *suggested_effort = Effort::from(new_suggested_effort);
1016            } else {
1017                // The rust `as` operator is used here to provide saturating conversions,
1018                // to avoid panicking if the effort calculation would be lossy due to extremely
1019                // large values. In practice, the values should be low enough that this shouldn't
1020                // come up, but it is worth being defensive.
1021                let theoretical_num_dequeued = num_dequeued * (1.0 / busy_fraction);
1022                let num_enqueued_gte_suggested_f64 = inner.num_enqueued_gte_suggested as f64;
1023
1024                if num_enqueued_gte_suggested_f64 >= theoretical_num_dequeued {
1025                    let effort_per_dequeued = (inner.total_effort as f64 / num_dequeued) as u32;
1026                    *suggested_effort = Effort::from(std::cmp::max(
1027                        effort_per_dequeued,
1028                        suggested_effort_inner + 1,
1029                    ));
1030                } else {
1031                    let decay = num_enqueued_gte_suggested_f64 / theoretical_num_dequeued;
1032                    let adjusted_decay = decay + ((1.0 - decay) * decay_adjustment_fraction);
1033                    let new_suggested_effort = (suggested_effort_inner_f64 * adjusted_decay) as u32;
1034                    *suggested_effort = Effort::from(new_suggested_effort);
1035                }
1036            }
1037
1038            drop(suggested_effort);
1039        }
1040
1041        let now = inner.runtime.now();
1042
1043        inner.update_period_start = now;
1044        inner.num_enqueued_gte_suggested = 0;
1045        inner.num_dequeued = 0;
1046        inner.idle_time = Duration::new(0, 0);
1047        inner.last_transition = now;
1048        inner.total_effort = 0;
1049    }
1050
1051    /// Loop to accept message from the wrapped [`mpsc::Receiver`], validate PoW solves, and
1052    /// enqueue onto the priority queue.
1053    fn accept_loop<P: MockablePowManager>(
1054        self,
1055        runtime: &R,
1056        pow_manager: &Arc<P>,
1057        mut receiver: mpsc::Receiver<Q>,
1058    ) -> Result<(), PowError> {
1059        let mut request_num = 0;
1060
1061        let netdir_provider = self
1062            .0
1063            .lock()
1064            .expect("Lock poisoned")
1065            .netdir_provider
1066            .clone();
1067        let net_params = runtime
1068            .reenter_block_on(netdir_provider.wait_for_netdir(tor_netdir::Timeliness::Timely))?
1069            .params()
1070            .clone();
1071
1072        let max_effort: u32 = net_params
1073            .hs_pow_v1_max_effort
1074            .get()
1075            .try_into()
1076            .expect("Bounded i32 not in range of u32?!");
1077        let max_effort = Effort::from(max_effort);
1078
1079        let config_rx = self.0.lock().expect("Lock poisoned").config_rx.clone();
1080
1081        let nickname = self.0.lock().expect("Lock poisoned").nickname.to_string();
1082
1083        cfg_if::cfg_if! {
1084            if #[cfg(feature = "metrics")] {
1085                let counter_rendrequest_error_total = metrics::counter!(
1086                    description: "Number of errors processing rendezvous requests in the PoW subsystem.",
1087                    unit: metrics::Unit::Count,
1088                    "arti_hss_pow_rendrequest_error_total",
1089                    "nickname" => nickname.clone()
1090                );
1091                let counter_rendrequest_verification_failure = metrics::counter!(
1092                    description: "Number of PoW verification failures.",
1093                    unit: metrics::Unit::Count,
1094                    "arti_hss_pow_rendrequest_verification_failure_total",
1095                    "nickname" => nickname.clone()
1096                );
1097                let counter_rend_queue_overflow = metrics::counter!(
1098                    description: "Number of times the PoW rendezvous request queue overflowed, leading to dropped requests.",
1099                    unit: metrics::Unit::Count,
1100                    "arti_hss_pow_rend_queue_overflow_total",
1101                    "nickname" => nickname.clone()
1102                );
1103                let counter_rendrequest_enqueued = metrics::counter!(
1104                    description: "Number of rendezvous requests enqueued in the PoW subsystem.",
1105                    unit: metrics::Unit::Count,
1106                    "arti_hss_pow_rendrequest_enqueued_total",
1107                    "nickname" => nickname.clone()
1108                );
1109                let histogram_rendrequest_effort = metrics::histogram!(
1110                    description: "Histogram of effort values seen for incoming PoW requests.",
1111                    "arti_hss_pow_rendrequest_effort_hist",
1112                    "nickname" => nickname.clone()
1113                );
1114            }
1115        }
1116
1117        loop {
1118            let rend_request = if let Some(rend_request) = runtime.reenter_block_on(receiver.next())
1119            {
1120                rend_request
1121            } else {
1122                self.0
1123                    .lock()
1124                    .expect("Lock poisoned")
1125                    .status_tx
1126                    .send_shutdown();
1127                return Ok(());
1128            };
1129
1130            if config_rx.borrow().enable_pow {
1131                let rend_request =
1132                    match RendRequestOrdByEffort::new(rend_request, max_effort, request_num) {
1133                        Ok(rend_request) => rend_request,
1134                        Err(err) => {
1135                            #[cfg(feature = "metrics")]
1136                            counter_rendrequest_error_total.increment(1);
1137                            tracing::trace!(?err, "Error processing RendRequest");
1138                            continue;
1139                        }
1140                    };
1141
1142                request_num = request_num.wrapping_add(1);
1143
1144                if let Some(ref pow) = rend_request.pow {
1145                    if let Err(err) = pow_manager.check_solve(pow) {
1146                        tracing::debug!(?err, "PoW verification failed");
1147                        #[cfg(feature = "metrics")]
1148                        counter_rendrequest_verification_failure.increment(1);
1149                        continue;
1150                    } else {
1151                        #[cfg(feature = "metrics")]
1152                        {
1153                            let effort: u32 = pow.effort().into();
1154                            histogram_rendrequest_effort.record(effort);
1155                        }
1156                    }
1157                }
1158
1159                let mut inner = self.0.lock().expect("Lock poisoned");
1160                if inner.queue.is_empty() {
1161                    let now = runtime.now();
1162                    let last_transition = inner.last_transition;
1163                    inner.idle_time += now - last_transition;
1164                    inner.last_transition = now;
1165                }
1166                if let Some(ref request_pow) = rend_request.pow {
1167                    if request_pow.effort()
1168                        >= *inner.suggested_effort.lock().expect("Lock poisoned")
1169                    {
1170                        inner.num_enqueued_gte_suggested += 1;
1171                        let effort: u32 = request_pow.effort().into();
1172                        if let Some(total_effort) = inner.total_effort.checked_add(effort.into()) {
1173                            inner.total_effort = total_effort;
1174                        } else {
1175                            tracing::warn!(
1176                                "PoW total_effort would overflow. The total effort has been capped, but this is not expected to happen - please file a bug report with logs and information about the circumstances under which this occurred."
1177                            );
1178                            inner.total_effort = u64::MAX;
1179                        }
1180                    }
1181                }
1182                if inner.queue.len() >= config_rx.borrow().pow_rend_queue_depth {
1183                    let dropped_request = inner.queue.pop_first();
1184                    #[cfg(feature = "metrics")]
1185                    counter_rend_queue_overflow.increment(1);
1186                    tracing::debug!(
1187                        dropped_effort = ?dropped_request.map(|x| x.pow.map(|x| x.effort())),
1188                        "RendRequest queue full, dropping request."
1189                    );
1190                }
1191                inner.queue.insert(rend_request);
1192                #[cfg(feature = "metrics")]
1193                counter_rendrequest_enqueued.increment(1);
1194                if let Some(waker) = &inner.waker {
1195                    waker.wake_by_ref();
1196                }
1197            } else {
1198                // TODO (#2082): when allowing enable_pow to be toggled at runtime, we will need to
1199                // do bookkeeping here, as above. Perhaps it can be refactored nicely so the
1200                // bookkeeping code can be the same in both cases.
1201                let mut inner = self.0.lock().expect("Lock poisoned");
1202                inner.queue_pow_disabled.push_back(rend_request);
1203                #[cfg(feature = "metrics")]
1204                counter_rendrequest_enqueued.increment(1);
1205                if let Some(waker) = &inner.waker {
1206                    waker.wake_by_ref();
1207                }
1208            }
1209        }
1210    }
1211
1212    /// Loop to check for messages that are older than our timeout and remove them from the queue.
1213    fn expire_old_requests_loop(self, runtime: &R) -> Result<(), PowError> {
1214        let netdir_provider = self
1215            .0
1216            .lock()
1217            .expect("Lock poisoned")
1218            .netdir_provider
1219            .clone();
1220        let net_params = runtime
1221            .reenter_block_on(netdir_provider.wait_for_netdir(tor_netdir::Timeliness::Timely))?
1222            .params()
1223            .clone();
1224
1225        let max_age: Duration = net_params
1226            .hs_pow_v1_service_intro_timeout
1227            .try_into()
1228            .expect(
1229                "Couldn't convert HiddenServiceProofOfWorkV1ServiceIntroTimeoutSeconds to Duration",
1230            );
1231
1232        let nickname = self.0.lock().expect("Lock poisoned").nickname.to_string();
1233        #[cfg(feature = "metrics")]
1234        let counter_rendrequest_expired = metrics::counter!("arti_hss_pow_rendrequest_expired_total", "nickname" => nickname.clone());
1235
1236        loop {
1237            let inner = self.0.lock().expect("Lock poisoned");
1238            // Wake up when the oldest request will reach the expiration age, or, if there are no
1239            // items currently in the queue, wait for the maximum age.
1240            let wait_time = inner
1241                .queue
1242                .first()
1243                .map(|r| {
1244                    max_age.saturating_sub(runtime.now().saturating_duration_since(r.recv_time))
1245                })
1246                .unwrap_or(max_age);
1247            drop(inner);
1248
1249            runtime.reenter_block_on(runtime.sleep(wait_time));
1250
1251            let mut inner = self.0.lock().expect("Lock poisoned");
1252            let now = runtime.now();
1253            let prev_len = inner.queue.len();
1254            inner.queue.retain(|r| now - r.recv_time < max_age);
1255            let dropped = prev_len - inner.queue.len();
1256            tracing::trace!(dropped, "Expired timed out RendRequests");
1257            #[cfg(feature = "metrics")]
1258            counter_rendrequest_expired
1259                .increment(dropped.try_into().expect("usize overflowed u64!"));
1260        }
1261    }
1262}
1263
1264impl<R: Runtime, Q: MockableRendRequest> Stream for RendRequestReceiver<R, Q> {
1265    type Item = Q;
1266
1267    fn poll_next(
1268        self: std::pin::Pin<&mut Self>,
1269        cx: &mut std::task::Context<'_>,
1270    ) -> std::task::Poll<Option<Self::Item>> {
1271        let mut inner = self.get_mut().0.lock().expect("Lock poisoned");
1272        if inner.config_rx.borrow().enable_pow {
1273            match inner.queue.pop_last() {
1274                Some(item) => {
1275                    inner.num_dequeued += 1;
1276                    if inner.queue.is_empty() {
1277                        inner.last_transition = inner.runtime.now();
1278                    }
1279                    std::task::Poll::Ready(Some(item.request))
1280                }
1281                None => {
1282                    inner.waker = Some(cx.waker().clone());
1283                    std::task::Poll::Pending
1284                }
1285            }
1286        } else if let Some(request) = inner.queue_pow_disabled.pop_front() {
1287            // TODO (#2082): when we allow changing enable_pow at runtime, we will need to do
1288            // bookkeeping here.
1289            std::task::Poll::Ready(Some(request))
1290        } else {
1291            inner.waker = Some(cx.waker().clone());
1292            std::task::Poll::Pending
1293        }
1294    }
1295}
1296
1297#[cfg(test)]
1298mod test {
1299    #![allow(clippy::unwrap_used)]
1300    use crate::config::OnionServiceConfigBuilder;
1301    use crate::status::{OnionServiceStatus, StatusSender};
1302
1303    use super::*;
1304    use futures::FutureExt;
1305    use tor_hscrypto::pow::v1::{Nonce, SolutionByteArray};
1306    use tor_netdir::{testnet, testprovider::TestNetDirProvider};
1307    use tor_rtmock::MockRuntime;
1308
1309    struct MockPowManager;
1310
1311    #[derive(Debug)]
1312    struct MockRendRequest {
1313        id: usize,
1314        pow: Option<ProofOfWork>,
1315    }
1316
1317    impl MockablePowManager for MockPowManager {
1318        fn check_solve(self: &Arc<Self>, solve: &ProofOfWorkV1) -> Result<(), PowSolveError> {
1319            // For testing, treat all zeros as the only valid solve. Error is chosen arbitrarily.
1320            if solve.solution() == &[0; 16] {
1321                Ok(())
1322            } else {
1323                Err(PowSolveError::InvalidSeedHead)
1324            }
1325        }
1326    }
1327
1328    impl MockableRendRequest for MockRendRequest {
1329        fn proof_of_work(&self) -> Result<Option<&ProofOfWork>, rend_handshake::IntroRequestError> {
1330            Ok(self.pow.as_ref())
1331        }
1332    }
1333
1334    fn make_req(id: usize, effort: Option<u32>) -> MockRendRequest {
1335        MockRendRequest {
1336            id,
1337            pow: effort.map(|e| {
1338                ProofOfWork::V1(ProofOfWorkV1::new(
1339                    Nonce::from([0; 16]),
1340                    Effort::from(e),
1341                    SeedHead::from([0; 4]),
1342                    SolutionByteArray::from([0; 16]),
1343                ))
1344            }),
1345        }
1346    }
1347
1348    fn make_req_invalid(id: usize, effort: u32) -> MockRendRequest {
1349        MockRendRequest {
1350            id,
1351            pow: Some(ProofOfWork::V1(ProofOfWorkV1::new(
1352                Nonce::from([0; 16]),
1353                Effort::from(effort),
1354                SeedHead::from([0; 4]),
1355                SolutionByteArray::from([1; 16]),
1356            ))),
1357        }
1358    }
1359
1360    #[allow(clippy::type_complexity)]
1361    fn make_test_receiver(
1362        runtime: &MockRuntime,
1363        netdir_params: Vec<(String, i32)>,
1364        config: Option<OnionServiceConfig>,
1365    ) -> (
1366        RendRequestReceiver<MockRuntime, MockRendRequest>,
1367        mpsc::Sender<MockRendRequest>,
1368        Arc<Mutex<Effort>>,
1369        NetParameters,
1370        postage::watch::Sender<Arc<OnionServiceConfig>>,
1371    ) {
1372        let pow_manager = Arc::new(MockPowManager);
1373        let suggested_effort = Arc::new(Mutex::new(Effort::zero()));
1374        let netdir = testnet::construct_custom_netdir_with_params(
1375            testnet::simple_net_func,
1376            netdir_params,
1377            None,
1378        )
1379        .unwrap()
1380        .unwrap_if_sufficient()
1381        .unwrap();
1382        let net_params = netdir.params().clone();
1383        let netdir_provider: Arc<TestNetDirProvider> = Arc::new(netdir.into());
1384        let status_tx = StatusSender::new(OnionServiceStatus::new_shutdown()).into();
1385        let nickname = HsNickname::new("test-hs".to_string()).unwrap();
1386        let (config_tx, config_rx) =
1387            postage::watch::channel_with(Arc::new(config.unwrap_or_else(|| {
1388                OnionServiceConfigBuilder::default()
1389                    .nickname(nickname.clone())
1390                    .enable_pow(true)
1391                    .build()
1392                    .unwrap()
1393            })));
1394        let receiver: RendRequestReceiver<_, MockRendRequest> = RendRequestReceiver::new(
1395            runtime.clone(),
1396            nickname.clone(),
1397            suggested_effort.clone(),
1398            netdir_provider,
1399            status_tx,
1400            config_rx,
1401        );
1402        let (tx, rx) = mpsc::channel(32);
1403        receiver.start_accept_thread(runtime.clone(), pow_manager, rx);
1404
1405        (receiver, tx, suggested_effort, net_params, config_tx)
1406    }
1407
1408    #[test]
1409    fn test_basic_pow_ordering() {
1410        MockRuntime::test_with_various(|runtime| async move {
1411            let (mut receiver, mut tx, _suggested_effort, _net_params, _config_tx) =
1412                make_test_receiver(&runtime, vec![], None);
1413
1414            // Request with no PoW
1415            tx.send(make_req(0, None)).await.unwrap();
1416            assert_eq!(receiver.next().await.unwrap().id, 0);
1417
1418            // Request with PoW
1419            tx.send(make_req(1, Some(0))).await.unwrap();
1420            assert_eq!(receiver.next().await.unwrap().id, 1);
1421
1422            // Request with effort is before request with zero effort
1423            tx.send(make_req(2, Some(0))).await.unwrap();
1424            tx.send(make_req(3, Some(16))).await.unwrap();
1425            runtime.progress_until_stalled().await;
1426            assert_eq!(receiver.next().await.unwrap().id, 3);
1427            assert_eq!(receiver.next().await.unwrap().id, 2);
1428
1429            // Invalid solves are dropped
1430            tx.send(make_req_invalid(4, 32)).await.unwrap();
1431            tx.send(make_req(5, Some(16))).await.unwrap();
1432            runtime.progress_until_stalled().await;
1433            assert_eq!(receiver.next().await.unwrap().id, 5);
1434            assert_eq!(receiver.0.lock().unwrap().queue.len(), 0);
1435        });
1436    }
1437
1438    #[test]
1439    fn test_suggested_effort_increase() {
1440        MockRuntime::test_with_various(|runtime| async move {
1441            let (mut receiver, mut tx, suggested_effort, net_params, _config_tx) =
1442                make_test_receiver(
1443                    &runtime,
1444                    vec![(
1445                        "HiddenServiceProofOfWorkV1ServiceIntroTimeoutSeconds".to_string(),
1446                        60000,
1447                    )],
1448                    None,
1449                );
1450
1451            // Get through all the requests in plenty of time, no increase
1452
1453            for n in 0..128 {
1454                tx.send(make_req(n, Some(0))).await.unwrap();
1455            }
1456
1457            runtime.advance_by(HS_UPDATE_PERIOD / 2).await;
1458
1459            for _ in 0..128 {
1460                receiver.next().await.unwrap();
1461            }
1462
1463            runtime.advance_by(HS_UPDATE_PERIOD / 2).await;
1464            receiver.update_suggested_effort(&net_params);
1465
1466            assert_eq!(suggested_effort.lock().unwrap().clone(), Effort::zero());
1467
1468            // Requests left in the queue with zero suggested effort, suggested effort should
1469            // increase
1470
1471            for n in 0..128 {
1472                tx.send(make_req(n, Some(0))).await.unwrap();
1473            }
1474
1475            runtime.advance_by(HS_UPDATE_PERIOD / 2).await;
1476
1477            for _ in 0..64 {
1478                receiver.next().await.unwrap();
1479            }
1480
1481            runtime.advance_by(HS_UPDATE_PERIOD / 2).await;
1482            receiver.update_suggested_effort(&net_params);
1483
1484            let mut new_suggested_effort = *suggested_effort.lock().unwrap();
1485            assert!(new_suggested_effort > Effort::zero());
1486
1487            // We keep on being behind, effort should increase again.
1488
1489            for n in 0..64 {
1490                tx.send(make_req(n, Some(new_suggested_effort.into())))
1491                    .await
1492                    .unwrap();
1493            }
1494
1495            receiver.next().await.unwrap();
1496            runtime.advance_by(HS_UPDATE_PERIOD).await;
1497            receiver.update_suggested_effort(&net_params);
1498
1499            let mut old_suggested_effort = new_suggested_effort;
1500            new_suggested_effort = *suggested_effort.lock().unwrap();
1501            assert!(new_suggested_effort > old_suggested_effort);
1502
1503            // We catch up now, effort should start dropping, but not be zero immediately.
1504
1505            for n in 0..32 {
1506                tx.send(make_req(n, Some(new_suggested_effort.into())))
1507                    .await
1508                    .unwrap();
1509            }
1510
1511            runtime.advance_by(HS_UPDATE_PERIOD / 16 * 15).await;
1512
1513            while receiver.next().now_or_never().is_some() {
1514                // Keep going...
1515            }
1516
1517            runtime.advance_by(HS_UPDATE_PERIOD / 16).await;
1518            receiver.update_suggested_effort(&net_params);
1519
1520            old_suggested_effort = new_suggested_effort;
1521            new_suggested_effort = *suggested_effort.lock().unwrap();
1522            assert!(new_suggested_effort < old_suggested_effort);
1523            assert!(new_suggested_effort > Effort::zero());
1524
1525            // Effort will drop to zero eventually
1526
1527            let mut num_loops = 0;
1528            loop {
1529                tx.send(make_req(0, Some(new_suggested_effort.into())))
1530                    .await
1531                    .unwrap();
1532                runtime.advance_by(HS_UPDATE_PERIOD / 2).await;
1533
1534                while receiver.next().now_or_never().is_some() {
1535                    // Keep going...
1536                }
1537
1538                runtime.advance_by(HS_UPDATE_PERIOD / 2).await;
1539                receiver.update_suggested_effort(&net_params);
1540
1541                old_suggested_effort = new_suggested_effort;
1542                new_suggested_effort = *suggested_effort.lock().unwrap();
1543
1544                assert!(new_suggested_effort < old_suggested_effort);
1545
1546                if new_suggested_effort == Effort::zero() {
1547                    break;
1548                }
1549
1550                num_loops += 1;
1551
1552                if num_loops > 5 {
1553                    panic!("Took too long for suggested effort to fall!");
1554                }
1555            }
1556        });
1557    }
1558
1559    #[test]
1560    fn test_rendrequest_timeout() {
1561        MockRuntime::test_with_various(|runtime| async move {
1562            let (receiver, mut tx, _suggested_effort, net_params, _config_tx) =
1563                make_test_receiver(&runtime, vec![], None);
1564
1565            let r0 = MockRendRequest { id: 0, pow: None };
1566            tx.send(r0).await.unwrap();
1567
1568            let max_age: Duration = net_params
1569                .hs_pow_v1_service_intro_timeout
1570                .try_into()
1571                .unwrap();
1572            runtime.advance_by(max_age * 2).await;
1573
1574            // Waited too long, request has been dropped
1575            assert_eq!(receiver.0.lock().unwrap().queue.len(), 0);
1576        });
1577    }
1578
1579    #[test]
1580    fn test_pow_disabled() {
1581        MockRuntime::test_with_various(|runtime| async move {
1582            let (mut receiver, mut tx, _suggested_effort, _net_params, _config_tx) =
1583                make_test_receiver(
1584                    &runtime,
1585                    vec![],
1586                    Some(
1587                        OnionServiceConfigBuilder::default()
1588                            .nickname(HsNickname::new("test-hs".to_string()).unwrap())
1589                            .enable_pow(false)
1590                            .build()
1591                            .unwrap(),
1592                    ),
1593                );
1594
1595            // Request with no PoW
1596            tx.send(make_req(0, None)).await.unwrap();
1597            tx.send(make_req(1, Some(0))).await.unwrap();
1598            tx.send(make_req(2, Some(20))).await.unwrap();
1599            tx.send(make_req(3, Some(10))).await.unwrap();
1600
1601            runtime.progress_until_stalled().await;
1602
1603            // Requests are FIFO, since PoW is disabled
1604            assert_eq!(receiver.next().await.unwrap().id, 0);
1605            assert_eq!(receiver.next().await.unwrap().id, 1);
1606            assert_eq!(receiver.next().await.unwrap().id, 2);
1607            assert_eq!(receiver.next().await.unwrap().id, 3);
1608        });
1609    }
1610
1611    #[test]
1612    fn test_rend_queue_max_depth() {
1613        MockRuntime::test_with_various(|runtime| async move {
1614            let (mut receiver, mut tx, _suggested_effort, _net_params, mut config_tx) =
1615                make_test_receiver(
1616                    &runtime,
1617                    vec![],
1618                    Some(
1619                        OnionServiceConfigBuilder::default()
1620                            .nickname(HsNickname::new("test-hs".to_string()).unwrap())
1621                            .enable_pow(true)
1622                            .pow_rend_queue_depth(2)
1623                            .build()
1624                            .unwrap(),
1625                    ),
1626                );
1627
1628            tx.send(make_req(0, None)).await.unwrap();
1629            tx.send(make_req(1, None)).await.unwrap();
1630            tx.send(make_req(2, None)).await.unwrap();
1631
1632            runtime.progress_until_stalled().await;
1633
1634            assert!(receiver.next().await.is_some());
1635            assert!(receiver.next().await.is_some());
1636            assert_eq!(receiver.0.lock().unwrap().queue.len(), 0);
1637
1638            // Check that increasing queue size at runtime works...
1639
1640            config_tx
1641                .send(Arc::new(
1642                    OnionServiceConfigBuilder::default()
1643                        .nickname(HsNickname::new("test-hs".to_string()).unwrap())
1644                        .enable_pow(true)
1645                        .pow_rend_queue_depth(8)
1646                        .build()
1647                        .unwrap(),
1648                ))
1649                .await
1650                .unwrap();
1651
1652            tx.send(make_req(0, None)).await.unwrap();
1653            tx.send(make_req(1, None)).await.unwrap();
1654            tx.send(make_req(2, None)).await.unwrap();
1655
1656            runtime.progress_until_stalled().await;
1657
1658            assert!(receiver.next().await.is_some());
1659            assert!(receiver.next().await.is_some());
1660            assert!(receiver.next().await.is_some());
1661        });
1662    }
1663}