//! Code implementing version 1 proof-of-work for onion service hosts.

//!

//! Spec links:

//! * <https://spec.torproject.org/hspow-spec/common-protocol.html>

//! * <https://spec.torproject.org/hspow-spec/v1-equix.html>

use std::{

    collections::{BTreeSet, HashMap, VecDeque},

    sync::{Arc, Mutex, RwLock},

    task::Waker,

    time::{Duration, Instant, SystemTime},

};

use arrayvec::ArrayVec;

use equix::EquiXBuilder;

use futures::{SinkExt, StreamExt};

use futures::{Stream, channel::mpsc};

use num_traits::FromPrimitive;

use rand::{CryptoRng, RngCore};

use serde::{Deserialize, Serialize};

use thiserror::Error;

use tor_basic_utils::RngExt as _;

use tor_cell::relaycell::hs::pow::{ProofOfWork, v1::ProofOfWorkV1};

use tor_checkable::timed::TimerangeBound;

use tor_error::warn_report;

use tor_hscrypto::{

    pk::HsBlindIdKey,

    pow::v1::{

        Effort, Instance, RuntimeOption, Seed, SeedHead, Solution, SolutionErrorV1, Verifier,

    },

    time::TimePeriod,

};

use tor_keymgr::KeyMgr;

use tor_netdir::{NetDirProvider, NetdirProviderShutdown, params::NetParameters};

use tor_netdoc::doc::hsdesc::pow::{PowParams, v1::PowParamsV1};

use tor_persist::{

    hsnickname::HsNickname,

    state_dir::{InstanceRawSubdir, StorageHandle},

};

use tor_rtcompat::Runtime;

use tor_rtcompat::SpawnExt;

use crate::{

    BlindIdPublicKeySpecifier, OnionServiceConfig, RendRequest, ReplayError, StartupError,

    rend_handshake,

    replay::{OpenReplayLogError, PowNonceReplayLog},

    status::{PowManagerStatusSender, Problem, State as PowManagerState},

};

use super::NewPowManager;

/// Proof-of-Work manager type alias for production, using concrete [`RendRequest`].

pub(crate) type PowManager<R> = PowManagerGeneric<R, RendRequest>;

/// This is responsible for rotating Proof-of-Work seeds and doing verification of PoW solves.

pub(crate) struct PowManagerGeneric<R, Q>(RwLock<State<R, Q>>);

/// Internal state for [`PowManagerGeneric`].

struct State<R, Q> {

    /// The [`Seed`]s for a given [`TimePeriod`]

    ///

    /// The [`ArrayVec`] contains the current and previous seed, and the [`SystemTime`] is when the

    /// current seed will expire.

    seeds: HashMap<TimePeriod, SeedsForTimePeriod>,

    /// Verifiers for all the seeds that exist in `seeds`.

    verifiers: HashMap<SeedHead, (Verifier, Mutex<PowNonceReplayLog>)>,

    /// The nickname for this hidden service.

    ///

    /// We need this so we can get the blinded keys from the [`KeyMgr`].

    nickname: HsNickname,

    /// Directory used to store nonce replay log.

    instance_dir: InstanceRawSubdir,

    /// Key manager.

    keymgr: Arc<KeyMgr>,

    /// Current suggested effort that we publish in the pow-params line.

    ///

    /// This is only read by the PowManagerGeneric, and is written to by the [`RendRequestReceiver`].

    suggested_effort: Arc<Mutex<Effort>>,

    /// Runtime

    runtime: R,

    /// Handle for storing state we need to persist to disk.

    storage_handle: StorageHandle<PowManagerStateRecord>,

    /// Queue to tell the publisher to re-upload a descriptor for a given TP, since we've rotated

    /// that seed.

    publisher_update_tx: mpsc::Sender<TimePeriod>,

    /// The [`RendRequestReceiver`], which contains the queue of [`RendRequest`]s.

    ///

    /// We need a reference to this in order to tell it when to update the suggested_effort value.

    rend_request_rx: RendRequestReceiver<R, Q>,

    /// [`NetDirProvider`], used for getting consensus parameters for configuration values.

    netdir_provider: Arc<dyn NetDirProvider>,

    /// Sender for reporting back onion service status.

    status_tx: PowManagerStatusSender,

    /// Receiver for the current configuration.

    config_rx: postage::watch::Receiver<Arc<OnionServiceConfig>>,

}

#[derive(Serialize, Deserialize, Debug, Clone)]

/// Information about the current and previous [`Seed`] for a given [`TimePeriod`].

struct SeedsForTimePeriod {

    /// The previous and current [`Seed`].

    ///

    /// The last element in this array is the current seed.

    seeds: ArrayVec<Seed, 2>,

    /// When the current seed will expire.

    next_expiration_time: SystemTime,

}

#[derive(Debug)]

#[allow(unused)]

/// A PoW solve was invalid.

///

/// While this contains the reason for the failure, we probably just want to use that for

/// debugging, we shouldn't make any logical decisions based on what the particular error was.

pub(crate) enum PowSolveError {

    /// Seed head was not recognized, it may be expired.

    InvalidSeedHead,

    /// We have already seen a solve with this nonce

    NonceReplay(ReplayError),

    /// The bytes given as a solution do not form a valid Equi-X puzzle

    InvalidEquixSolution(SolutionErrorV1),

    /// The solution given was invalid.

    InvalidSolve(tor_hscrypto::pow::Error),

}

/// On-disk record of [`PowManagerGeneric`] state.

#[derive(Serialize, Deserialize, Debug, Default)]

pub(crate) struct PowManagerStateRecord {

    /// Seeds for each time period.

    ///

    /// Conceptually, this is a map between TimePeriod and SeedsForTimePeriod, but since TimePeriod

    /// can't be serialized to a string, it's not very simple to use serde to serialize it like

    /// that, so we instead store it as a list of tuples, and convert it to/from the map when

    /// saving/loading.

    seeds: Vec<(TimePeriod, SeedsForTimePeriod)>,

    /// Most recently published suggested_effort value.

    #[serde(default)]

    suggested_effort: Effort,

    // We don't persist any per-period state. While it might be sort of nice to, it's complex to

    // decide when to write the state out to disk. The disadvantage to not storing it is that when

    // we restart the process, we may be up to 5 minutes slower to update the suggested effort to a

    // new value, which isn't particularly bad. The only case it would be bad is if a attacker has

    // a way to cause the Arti process to restart (in which case they could do that just before the

    // update period to pin the suggested effort value at a specific value), but if they have that,

    // they have a much more valuable attack (including as a DoS vector) than just a PoW bypass.

}

impl<R: Runtime, Q> State<R, Q> {

    /// Make a [`PowManagerStateRecord`] for this state.

}

/// How frequently the suggested effort should be recalculated.

const HS_UPDATE_PERIOD: Duration = Duration::from_secs(300);

/// When the suggested effort has changed by less than this much, we don't republish it.

///

/// Specified as "15 percent" in <https://spec.torproject.org/hspow-spec/common-protocol.html>

///

/// However, we may want to make this configurable in the future.

const SUGGESTED_EFFORT_DEADZONE: f64 = 0.15;

/// How soon before a seed's expiration time we should rotate it and publish a new seed.

const SEED_EARLY_ROTATION_TIME: Duration = Duration::from_secs(60 * 5);

/// Minimum seed expiration time in minutes. See:

/// <https://spec.torproject.org/hspow-spec/v1-equix.html#parameter-descriptor>

const EXPIRATION_TIME_MINS_MIN: u64 = 105;

/// Maximum seed expiration time in minutes. See:

/// <https://spec.torproject.org/hspow-spec/v1-equix.html#parameter-descriptor>

const EXPIRATION_TIME_MINS_MAX: u64 = 120;

/// Enforce that early rotation time is less than or equal to min expiration time.

const _: () = assert!(

    SEED_EARLY_ROTATION_TIME.as_secs() <= EXPIRATION_TIME_MINS_MIN * 60,

    "Early rotation time must be less than minimum expiration time"

);

/// Enforce that min expiration time is less than or equal to max.

const _: () = assert!(

    EXPIRATION_TIME_MINS_MIN <= EXPIRATION_TIME_MINS_MAX,

    "Minimum expiration time must be less than or equal to max"

);

/// Depth of the queue used to signal the publisher that it needs to update a given time period.

///

/// 32 is likely way larger than we need but the messages are tiny so we might as well.

const PUBLISHER_UPDATE_QUEUE_DEPTH: usize = 32;

#[derive(Error, Debug, Clone)]

#[allow(dead_code)] // We want to show fields in Debug even if we don't use them.

#[non_exhaustive]

/// Error within the PoW subsystem.

pub enum PowError {

    /// We don't have a key that is needed.

    #[error("Missing required key.")]

    MissingKey,

    /// Error in the underlying storage layer.

    #[error(transparent)]

    StorageError(#[from] tor_persist::Error),

    /// Error from the ReplayLog.

    #[error(transparent)]

    OpenReplayLog(#[from] OpenReplayLogError),

    /// NetDirProvider has shut down

    #[error(transparent)]

    NetdirProviderShutdown(#[from] NetdirProviderShutdown),

}

impl<R: Runtime, Q: MockableRendRequest + Send + 'static> PowManagerGeneric<R, Q> {

    /// Create a new [`PowManagerGeneric`].

    #[allow(clippy::new_ret_no_self, clippy::too_many_arguments)]

                    None => {

                        );

                    }

                };

                            err,

                        );

                    }

                };

            }

        }

        // This queue is extremely small, and we only make one of it per onion service, so it's

        // fine to not use memquota tracking.

        );

    /// Launch background task to rotate seeds.

                spawning: "pow manager",

    /// Run [`Self::main_loop_task`], reporting any errors.

    /// Main loop for rotating seeds.

        loop {

            // Update the suggested effort, if needed

                };

                }

            );

            // A new TimePeriod that we don't know about (and thus that isn't in next_update_time)

            // might get added at any point. Making sure that our maximum delay is the minimum

            // amount of time that it might take for a seed to expire means that we can be sure

            // that we will rotate newly-added seeds properly.

            const MAX_DELAY: Duration = Duration::from_secs(EXPIRATION_TIME_MINS_MIN * 60)

                .checked_sub(SEED_EARLY_ROTATION_TIME)

                .expect("SEED_EARLY_ROTATION_TIME too high, or EXPIRATION_TIME_MINS_MIN too low.");

        }

    /// Make a randomized seed expiration time.

    /// Make a ner [`Verifier`] for a given [`TimePeriod`] and [`Seed`].

    ///

    /// If a key is not available for this TP, returns None.

    ///

    /// This takes individual arguments instead of `&self` to avoid getting into any trouble with

    /// locking.

            }

        };

    /// Calculate a time when we want to rotate a seed, slightly before it expires, in order to

    /// ensure that clients don't ever download a seed that is already out of date.

        // Underflow cannot happen because:

        //

        // * We set the expiration time to the current time plus at least the minimum

        //   expiration time

        // * We know (backed up by a compile-time assertion) that SEED_EARLY_ROTATION_TIME is

        //   less than the minimum expiration time.

        //

        // Thus, the only way this subtraction can underflow is if the system time at the

        // moment we set the expiration time was before the epoch, which is not possible on

        // reasonable platforms.

    /// Rotate any seeds that will expire soon.

    ///

    /// This also pokes the publisher when needed to cause rotated seeds to be published.

    ///

    /// Returns the next time this function should be called again.

    #[allow(clippy::cognitive_complexity)]

                    // This does not allow for easy testing, but because we're in a async function, it's

                    // non-trivial to pass in a Rng from the outside world. If we end up writing tests that

                    // require that, we can take a function to generate a Rng, but for now, just using the

                    // thread rng is fine.

                        None => {

                            // We use not having a key for a given TP as the signal that we should

                            // stop keeping track of seeds for that TP.

                        }

                    };

                    } else {

                    };

                    // .push() is safe, since we just made space above.

                    // Make a note to add the new verifier and remove the old one.

                    // Tell the publisher to update this TP

            }

            }

        };

        }

    /// Get [`PowParams`] for a given [`TimePeriod`].

    ///

    /// If we don't have any [`Seed`]s for the requested period, generate them. This is the only

    /// way that [`PowManagerGeneric`] learns about new [`TimePeriod`]s.

        };

            None => {

                // We don't have a seed for this time period, so we need to generate one.

                );

                )

            }

        };

    /// Verify a PoW solve.

        // Note that we put the nonce into the replay log before we check the solve. While this

        // might not be ideal, it's not a problem and is probably the most reasonable thing to do.

        // See commit bc5b313028 for a more full explaination.

        {

            };

        }

        // TODO: Once RwLock::downgrade is stabilized, it would make sense to use it here...

        };

        };

        }

}

/// Trait to allow mocking PowManagerGeneric in tests.

trait MockablePowManager {

    /// Verify a PoW solve.

    fn check_solve(self: &Arc<Self>, solve: &ProofOfWorkV1) -> Result<(), PowSolveError>;

}

impl<R: Runtime> MockablePowManager for PowManager<R> {

}

/// Trait to allow mocking RendRequest in tests.

pub(crate) trait MockableRendRequest {

    /// Get the proof-of-work extension associated with this request.

    fn proof_of_work(&self) -> Result<Option<&ProofOfWork>, rend_handshake::IntroRequestError>;

}

impl MockableRendRequest for RendRequest {

}

/// Wrapper around [`RendRequest`] that implements [`std::cmp::Ord`] to sort by [`Effort`] and time.

#[derive(Debug)]

struct RendRequestOrdByEffort<Q> {

    /// The underlying request.

    request: Q,

    /// The proof-of-work options, if given.

    pow: Option<ProofOfWorkV1>,

    /// The maximum effort allowed. If the effort of this request is higher than this, it will be

    /// treated as though it is this value.

    max_effort: Effort,

    /// When this request was received, used for ordreing if the effort values are the same.

    recv_time: Instant,

    /// Unique number for this request, which is used for ordering among requests with the same

    /// timestamp.

    ///

    /// This is intended to be monotonically increasing, although it may overflow. Overflows are

    /// not handled in any special way, given that they are a edge case of an edge case, and

    /// ordering among requests that came in at the same instant is not important.

    request_num: u64,

}

impl<Q: MockableRendRequest> RendRequestOrdByEffort<Q> {

    /// Create a new [`RendRequestOrdByEffort`].

        };

}

impl<Q: MockableRendRequest> Ord for RendRequestOrdByEffort<Q> {

            std::cmp::Ordering::Equal => {

                // Flip ordering, since we want the oldest ones to be handled first.

                    // Use request_num as a final tiebreaker, also flipping ordering (since

                    // lower-numbered requests should be older and thus come first)

                }

            }

        }

}

impl<Q: MockableRendRequest> PartialOrd for RendRequestOrdByEffort<Q> {

}

impl<Q: MockableRendRequest> PartialEq for RendRequestOrdByEffort<Q> {

}

impl<Q: MockableRendRequest> Eq for RendRequestOrdByEffort<Q> {}

/// Implements [`Stream`] for incoming [`RendRequest`]s, using a priority queue system to dequeue

/// high-[`Effort`] requests first.

///

/// This is implemented on top of a [`mpsc::Receiver`]. There is a thread that dequeues from the

/// [`mpsc::Receiver`], checks the PoW solve, and if it is correct, adds it to a [`BTreeSet`],

/// which the [`Stream`] implementation reads from.

///

/// This is not particularly optimized — queueing and dequeuing use a [`Mutex`], so there may be

/// some contention there. It's possible there may be some fancy lockless (or more optimized)

/// priority queue that we could use, but we should properly benchmark things before trying to make

/// a optimization like that.

pub(crate) struct RendRequestReceiver<R, Q>(Arc<Mutex<RendRequestReceiverInner<R, Q>>>);

impl<R, Q> Clone for RendRequestReceiver<R, Q> {

}

/// Inner implementation for [`RendRequestReceiver`].

struct RendRequestReceiverInner<R, Q> {

    /// Internal priority queue of requests.

    queue: BTreeSet<RendRequestOrdByEffort<Q>>,

    /// Internal FIFO queue of requests used when PoW is disabled.

    ///

    /// We have this here to support switching back and forth between PoW enabled and disabled at

    /// runtime, although that isn't currently supported.

    queue_pow_disabled: VecDeque<Q>,

    /// Waker to inform async readers when there is a new message on the queue.

    waker: Option<Waker>,

    /// Runtime, used to get current time in a testable way.

    runtime: R,

    /// Nickname, use when reporting metrics.

    nickname: HsNickname,

    /// [`NetDirProvider`], for getting configuration values in consensus parameters.

    netdir_provider: Arc<dyn NetDirProvider>,

    /// Current configuration, used to see whether PoW is enabled or not.

    config_rx: postage::watch::Receiver<Arc<OnionServiceConfig>>,

    /// When the current update period started.

    update_period_start: Instant,

    /// Number of requests that were enqueued during the current update period, and had an effort

    /// greater than or equal to the suggested effort.

    num_enqueued_gte_suggested: usize,

    /// Number of requests that were dequeued during the current update period.

    num_dequeued: u32,

    /// Amount of time during the current update period that we spent with no requests in the

    /// queue.

    idle_time: Duration,

    /// Time that the queue last went from having items in it to not having items in it, or vice

    /// versa. This is used to update idle_time.

    last_transition: Instant,

    /// Sum of all effort values that were validated and enqueued during the current update period.

    total_effort: u64,

    /// Most recent published suggested effort value.

    ///

    /// We write to this, which is then published in the pow-params line by [`PowManagerGeneric`].

    suggested_effort: Arc<Mutex<Effort>>,

    /// Sender for reporting back onion service status.

    status_tx: PowManagerStatusSender,

}

impl<R: Runtime, Q: MockableRendRequest + Send + 'static> RendRequestReceiver<R, Q> {

    /// Create a new [`RendRequestReceiver`].

    // spawn_blocking executes immediately, but some of our abstractions make clippy not

    // realize this.

    #[allow(clippy::let_underscore_future)]

    /// Start helper thread to accept and validate [`RendRequest`]s.

            {

    /// Update the suggested effort value, as per the algorithm in prop362

            );

            // TODO: use as_millis_f64 when stable

            }

    /// Loop to accept message from the wrapped [`mpsc::Receiver`], validate PoW sovles, and

    /// enqueue onto the priority queue.

    #[allow(clippy::cognitive_complexity)]

        cfg_if::cfg_if! {

            if #[cfg(feature = "metrics")] {

            }

        }

        loop {

            {

            } else {

            };

                            #[cfg(feature = "metrics")]

                        }

                    };

                        #[cfg(feature = "metrics")]

                    } else {

                        #[cfg(feature = "metrics")]

                    }

                    {

                            );

                        }

                    #[cfg(feature = "metrics")]

                    );

                #[cfg(feature = "metrics")]

            } else {

                // TODO (#2082): when allowing enable_pow to be toggled at runtime, we will need to

                // do bookkeeping here, as above. Perhaps it can be refactored nicely so the

                // bookkeeping code can be the same in both cases.

                #[cfg(feature = "metrics")]

            }

        }

    /// Loop to check for messages that are older than our timeout and remove them from the queue.

            );

        #[cfg(feature = "metrics")]

        loop {

            // Wake up when the oldest request will reach the expiration age, or, if there are no

            // items currently in the queue, wait for the maximum age.

            #[cfg(feature = "metrics")]

        }

}

impl<R: Runtime, Q: MockableRendRequest> Stream for RendRequestReceiver<R, Q> {

    type Item = Q;

                }

                None => {

                }

            }

            // TODO (#2082): when we allow changing enable_pow at runtime, we will need to do

            // bookkeeping here.

        } else {

        }

}

#[cfg(test)]

mod test {

    #![allow(clippy::unwrap_used)]

    use crate::config::OnionServiceConfigBuilder;

    use crate::status::{OnionServiceStatus, StatusSender};

    use super::*;

    use futures::FutureExt;

    use tor_hscrypto::pow::v1::{Nonce, SolutionByteArray};

    use tor_netdir::{testnet, testprovider::TestNetDirProvider};

    use tor_rtmock::MockRuntime;

    struct MockPowManager;

    #[derive(Debug)]

    struct MockRendRequest {

        id: usize,

        pow: Option<ProofOfWork>,

    }

    impl MockablePowManager for MockPowManager {

        fn check_solve(self: &Arc<Self>, solve: &ProofOfWorkV1) -> Result<(), PowSolveError> {

            // For testing, treat all zeros as the only valid solve. Error is chosen arbitrarily.

            if solve.solution() == &[0; 16] {

                Ok(())

            } else {

                Err(PowSolveError::InvalidSeedHead)

            }

        }

    }

    impl MockableRendRequest for MockRendRequest {

        fn proof_of_work(&self) -> Result<Option<&ProofOfWork>, rend_handshake::IntroRequestError> {

            Ok(self.pow.as_ref())

        }

    }

    fn make_req(id: usize, effort: Option<u32>) -> MockRendRequest {

        MockRendRequest {

            id,

            pow: effort.map(|e| {

                ProofOfWork::V1(ProofOfWorkV1::new(

                    Nonce::from([0; 16]),

                    Effort::from(e),

                    SeedHead::from([0; 4]),

                    SolutionByteArray::from([0; 16]),

                ))

            }),

        }

    }

    fn make_req_invalid(id: usize, effort: u32) -> MockRendRequest {

        MockRendRequest {

            id,

            pow: Some(ProofOfWork::V1(ProofOfWorkV1::new(

                Nonce::from([0; 16]),

                Effort::from(effort),

                SeedHead::from([0; 4]),

                SolutionByteArray::from([1; 16]),

            ))),

        }

    }

    #[allow(clippy::type_complexity)]

    fn make_test_receiver(

        runtime: &MockRuntime,

        netdir_params: Vec<(String, i32)>,

        config: Option<OnionServiceConfig>,

    ) -> (

        RendRequestReceiver<MockRuntime, MockRendRequest>,

        mpsc::Sender<MockRendRequest>,