tor_hscrypto/pow/v1/
challenge.rs

1//! Implement the `v1` scheme's challenge string format
2//!
3//! This is a packed byte-string which encodes our puzzle's parameters
4//! as inputs for Equi-X. We need to construct challenge strings both to
5//! solve and to verify puzzles.
6
7use crate::pow::v1::{
8    err::SolutionErrorV1, types::Effort, types::Instance, types::NONCE_LEN, types::Nonce,
9    types::SEED_LEN, types::Seed,
10};
11use arrayvec::{ArrayVec, CapacityError};
12use blake2::{Blake2b, Digest, digest::consts::U4};
13
14/// Algorithm personalization string (P)
15///
16/// This becomes part of the challenge string, binding a puzzle solution to
17/// this particular algorithm even if other similar protocols exist using
18/// the same building blocks.
19const P_STRING: &[u8] = b"Tor hs intro v1\0";
20
21/// Length of the personalization string, in bytes
22const P_STRING_LEN: usize = 16;
23
24/// Length of the HsBlindId
25const ID_LEN: usize = 32;
26
27/// Location of the [`Seed`] within a [`Challenge`]
28const SEED_OFFSET: usize = P_STRING_LEN + ID_LEN;
29
30/// Location of the [`Nonce`] within a [`Challenge`]
31const NONCE_OFFSET: usize = SEED_OFFSET + SEED_LEN;
32
33/// Location of the [`Effort`] within a [`Challenge`]
34const EFFORT_OFFSET: usize = NONCE_OFFSET + NONCE_LEN;
35
36/// Packed length of an [`Effort`], in bytes
37const EFFORT_LEN: usize = 4;
38
39/// Total length of our Equi-X challenge string
40const CHALLENGE_LEN: usize = EFFORT_OFFSET + EFFORT_LEN;
41
42/// A fully assembled challenge string, with some access to inner fields
43///
44/// This is the combined input to Equi-X. Defined by Proposal 327
45/// as `(P || ID || C || N || INT_32(E))`
46#[derive(derive_more::AsRef, Debug, Clone, Eq, PartialEq)]
47pub(super) struct Challenge([u8; CHALLENGE_LEN]);
48
49impl Challenge {
50    /// Build a new [`Challenge`].
51    ///
52    /// Copies [`Instance`], [`Effort`], and [`Nonce`] values into
53    /// a new byte array.
54    pub(super) fn new(instance: &Instance, effort: Effort, nonce: &Nonce) -> Self {
55        let mut result = ArrayVec::<u8, CHALLENGE_LEN>::new();
56        (|| -> Result<(), CapacityError> {
57            result.try_extend_from_slice(P_STRING)?;
58            result.try_extend_from_slice(instance.service().as_ref())?;
59            assert_eq!(result.len(), SEED_OFFSET);
60            result.try_extend_from_slice(instance.seed().as_ref())?;
61            assert_eq!(result.len(), NONCE_OFFSET);
62            result.try_extend_from_slice(nonce.as_ref())?;
63            assert_eq!(result.len(), EFFORT_OFFSET);
64            result.try_extend_from_slice(&effort.as_ref().to_be_bytes())
65        })()
66        .expect("CHALLENGE_LEN holds a full challenge string");
67        Self(
68            result
69                .into_inner()
70                .expect("challenge buffer is fully written"),
71        )
72    }
73
74    /// Clone the [`Seed`] portion of this challenge.
75    pub(super) fn seed(&self) -> Seed {
76        let array: [u8; SEED_LEN] = self.0[SEED_OFFSET..(SEED_OFFSET + SEED_LEN)]
77            .try_into()
78            .expect("slice length correct");
79        array.into()
80    }
81
82    /// Clone the [`Nonce`] portion of this challenge.
83    pub(super) fn nonce(&self) -> Nonce {
84        let array: [u8; NONCE_LEN] = self.0[NONCE_OFFSET..(NONCE_OFFSET + NONCE_LEN)]
85            .try_into()
86            .expect("slice length correct");
87        array.into()
88    }
89
90    /// Return the [`Effort`] used in this challenge.
91    pub(super) fn effort(&self) -> Effort {
92        u32::from_be_bytes(
93            self.0[EFFORT_OFFSET..(EFFORT_OFFSET + EFFORT_LEN)]
94                .try_into()
95                .expect("slice length correct"),
96        )
97        .into()
98    }
99
100    /// Increment the [`Nonce`] value inside this challenge.
101    ///
102    /// Note that this will take a different amount of time depending on the
103    /// number of bytes affected. There's no timing side channel here: The
104    /// timing variation here is swamped by variation in the solver itself,
105    /// and the nonce is not a secret value.
106    pub(super) fn increment_nonce(&mut self) {
107        /// Wrapping increment for a serialized little endian value of arbitrary width.
108        fn inc_le_bytes(slice: &mut [u8]) {
109            for byte in slice {
110                let (value, overflow) = (*byte).overflowing_add(1);
111                *byte = value;
112                if !overflow {
113                    break;
114                }
115            }
116        }
117        inc_le_bytes(&mut self.0[NONCE_OFFSET..(NONCE_OFFSET + NONCE_LEN)]);
118    }
119
120    /// Verify that a solution proof passes the effort test.
121    ///
122    /// This computes a Blake2b hash of the challenge and the serialized
123    /// Equi-X solution, and tests the result against the effort encoded
124    /// in the challenge string.
125    ///
126    /// Used by both the [`crate::pow::v1::Solver`] and the [`crate::pow::v1::Verifier`].
127    pub(super) fn check_effort(
128        &self,
129        proof: &equix::SolutionByteArray,
130    ) -> Result<(), SolutionErrorV1> {
131        let mut hasher = Blake2b::<U4>::new();
132        hasher.update(self.as_ref());
133        hasher.update(proof.as_ref());
134        let value = u32::from_be_bytes(hasher.finalize().into());
135        match value.checked_mul(*self.effort().as_ref()) {
136            Some(_) => Ok(()),
137            None => Err(SolutionErrorV1::Effort),
138        }
139    }
140}
tor_hscrypto/pow/v1/challenge.rs

tor_hscrypto/pow/v1/
challenge.rs
