1
//! Basic types used by the v1 client puzzle
2

            
3
use crate::pk::HsBlindId;
4
use crate::pow::v1::err::SolutionErrorV1;
5
use rand::prelude::*;
6
use serde::{Deserialize, Serialize};
7
use tor_bytes::{EncodeResult, Readable, Reader, Writeable, Writer};
8

            
9
/// Effort setting, a u32 value with linear scale
10
///
11
/// The numerical value is roughly the expected number of times we will
12
/// need to invoke the underlying solver (Equi-X) for the v1 proof-of-work
13
/// protocol to find a solution.
14
#[derive(derive_more::AsRef, derive_more::From, derive_more::Into)] //
15
#[derive(Serialize, Deserialize)] //
16
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq, Ord, PartialOrd)]
17
pub struct Effort(u32);
18

            
19
impl Effort {
20
    /// Const constructor for `Effort` from any u32
21
    ///
22
    /// `Effort` can also be constructed using into() conversions,
23
    /// but those are not available in const expressions.
24
    ///
25
66
    pub const fn new(value: u32) -> Self {
26
66
        Self(value)
27
66
    }
28

            
29
    /// Const constructor for zero effort
30
    ///
31
    /// Zero effort is used in suggested effort to mean the puzzle is
32
    /// available but shouldn't be used on a first connection attempt.
33
    ///
34
    /// If zero is actually used for solve and verify, it will have equivalent
35
    /// performance to an effort of 1.
36
    ///
37
449064
    pub const fn zero() -> Self {
38
449064
        Self(0)
39
449064
    }
40

            
41
    /// Multiply this effort by an integer of the same size, saturating on overflow
42
    pub const fn saturating_mul_u32(&self, rhs: u32) -> Self {
43
        Self(self.0.saturating_mul(rhs))
44
    }
45

            
46
    /// Multiply this effort by a float, with saturating cast back to Effort
47
    pub fn saturating_mul_f32(&self, rhs: f32) -> Self {
48
        // 'as' cast from float to int saturates, and NaN becomes 0.
49
        Self((self.0 as f32 * rhs) as u32)
50
    }
51
}
52

            
53
/// Length of the random seed generated by servers and included in HsDir
54
pub const SEED_LEN: usize = 32;
55

            
56
/// The random portion of a challenge, distributed through HsDir
57
#[derive(
58
    derive_more::AsRef, derive_more::From, Deserialize, Serialize, Debug, Clone, Eq, PartialEq,
59
)]
60
pub struct Seed([u8; SEED_LEN]);
61

            
62
impl Seed {
63
    /// Generate a new, random seed.
64
    ///
65
    /// If old_seed is given, avoid generating a seed that shares a seed head.
66
8
    pub fn new<R: Rng + CryptoRng>(rng: &mut R, old_seed: Option<&Seed>) -> Self {
67
8
        let mut new = Seed(rng.random());
68
8
        while Some(new.head()) == old_seed.as_ref().map(|seed| seed.head()) {
69
            new = Seed(rng.random());
70
        }
71
8
        new
72
8
    }
73

            
74
    /// Make a new [`SeedHead`] from a prefix of this seed
75
6345
    pub fn head(&self) -> SeedHead {
76
6345
        SeedHead(
77
6345
            self.0[..SEED_HEAD_LEN]
78
6345
                .try_into()
79
6345
                .expect("slice length correct"),
80
6345
        )
81
6345
    }
82
}
83

            
84
impl std::fmt::Display for Seed {
85
264
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
86
264
        write!(f, "{}", hex::encode(self.0))
87
264
    }
88
}
89

            
90
/// Error when converting a string to a [`Seed`].
91
#[non_exhaustive]
92
pub enum ParseSeedError {
93
    /// The string was not a valid hex string.
94
    InvalidHex(hex::FromHexError),
95
    /// The string was not the correct length for a [`Seed`].
96
    InvalidLength,
97
}
98

            
99
impl std::str::FromStr for Seed {
100
    type Err = ParseSeedError;
101

            
102
    fn from_str(s: &str) -> Result<Self, Self::Err> {
103
        let bytes = hex::decode(s).map_err(ParseSeedError::InvalidHex)?;
104
        Ok(Seed(
105
            bytes
106
                .try_into()
107
                .map_err(|_| ParseSeedError::InvalidLength)?,
108
        ))
109
    }
110
}
111

            
112
/// Length of a seed prefix used to identify the entire seed
113
pub const SEED_HEAD_LEN: usize = 4;
114

            
115
/// A short seed prefix used in solutions to reference the complete seed
116
#[derive(derive_more::AsRef, derive_more::From, Debug, Clone, Copy, Eq, PartialEq, Hash)]
117
pub struct SeedHead([u8; SEED_HEAD_LEN]);
118

            
119
/// Length of the nonce value generated by clients and included in the solution
120
pub const NONCE_LEN: usize = 16;
121

            
122
/// Generated randomly by solvers and included in the solution
123
#[derive(derive_more::AsRef, derive_more::From, Debug, Clone, Eq, PartialEq)]
124
pub struct Nonce([u8; NONCE_LEN]);
125

            
126
/// Generate [`Readable`] and [`Writeable`] implementations for trivial newtype wrappers
127
macro_rules! impl_readable_writeable_newtype {
128
    ($t:ty) => {
129
        impl Readable for $t {
130
            fn take_from(b: &mut Reader<'_>) -> tor_bytes::Result<Self> {
131
                Ok(Self(Readable::take_from(b)?))
132
            }
133
        }
134
        impl Writeable for $t {
135
1
            fn write_onto<B: Writer + ?Sized>(&self, b: &mut B) -> EncodeResult<()> {
136
1
                self.0.write_onto(b)
137
1
            }
138
        }
139
    };
140
}
141

            
142
impl_readable_writeable_newtype!(Effort);
143
impl_readable_writeable_newtype!(Seed);
144
impl_readable_writeable_newtype!(SeedHead);
145
impl_readable_writeable_newtype!(Nonce);
146

            
147
/// One instance of this proof-of-work puzzle
148
///
149
/// Identified uniquely by the combination of onion service blinded Id key
150
/// plus a rotating seed chosen by the service.
151
#[derive(Debug, Clone)]
152
pub struct Instance {
153
    /// Blinded public Id key, binding this puzzle to a specific onion service
154
    service: HsBlindId,
155
    /// Seed value distributed in the HsDir by that service
156
    seed: Seed,
157
}
158

            
159
impl Instance {
160
    /// A new puzzle instance, wrapping a service Id and service-chosen seed
161
2112
    pub fn new(service: HsBlindId, seed: Seed) -> Self {
162
2112
        Self { service, seed }
163
2112
    }
164

            
165
    /// Get the [`HsBlindId`] identifying the service this puzzle is for.
166
3102
    pub fn service(&self) -> &HsBlindId {
167
3102
        &self.service
168
3102
    }
169

            
170
    /// Get the rotating random [`Seed`] used in this puzzle instance.
171
7590
    pub fn seed(&self) -> &Seed {
172
7590
        &self.seed
173
7590
    }
174
}
175

            
176
/// One potential solution to some puzzle [`Instance`]
177
///
178
/// The existence of a [`Solution`] guarantees that the solution is well formed
179
/// (for example, the correct length, the correct order  in the Equi-X solution)
180
/// but it makes no guarantee to actually solve any specific puzzle instance.
181
#[derive(Debug, Clone, Eq, PartialEq)]
182
pub struct Solution {
183
    /// Arbitrary value chosen by the solver to reach a valid solution
184
    ///
185
    /// Services are responsible for remembering used values to prevent replay.
186
    nonce: Nonce,
187

            
188
    /// The effort chosen by the client
189
    ///
190
    /// This is validated against the actual effort spent by the client using
191
    /// a combination of two checks:
192
    ///
193
    /// - We can ensure the effort value here was chosen prior to successfully
194
    ///   solving the Equi-X puzzle just by verifying the Equi-X proof.
195
    ///   Effort values are part of the [`crate::pow::v1::challenge::Challenge`]
196
    ///   string the puzzle is constructed around.
197
    ///
198
    /// - We can ensure, on average, that the proper proportion of Equi-X
199
    ///   solutions have been discarded. The proof and challenge are hashed,
200
    ///   and the resulting digest is effectively a random variable that must
201
    ///   fit within a range inversely proportional to the effort. This test
202
    ///   happens in [`crate::pow::v1::challenge::Challenge::check_effort`].
203
    effort: Effort,
204

            
205
    /// Prefix of the [`Seed`] used in this puzzle Instance
206
    ///
207
    /// A service will normally have two active [`Seed`] values at once.
208
    /// This prefix is sufficient to distinguish between them. (Services
209
    /// skip seeds which would have the same prefix as the last seed.)
210
    seed_head: SeedHead,
211

            
212
    /// Equi-X solution which claims to prove the above effort choice
213
    proof: equix::Solution,
214
}
215

            
216
impl Solution {
217
    /// Construct a new Solution around a well-formed [`equix::Solution`] proof.
218
3168
    pub fn new(nonce: Nonce, effort: Effort, seed_head: SeedHead, proof: equix::Solution) -> Self {
219
3168
        Solution {
220
3168
            nonce,
221
3168
            effort,
222
3168
            seed_head,
223
3168
            proof,
224
3168
        }
225
3168
    }
226

            
227
    /// Try to build a [`Solution`] from an unvalidated [`equix::SolutionByteArray`].
228
    ///
229
    /// This will either return a [`Solution`] or a [`SolutionErrorV1::Order`].
230
1848
    pub fn try_from_bytes(
231
1848
        nonce: Nonce,
232
1848
        effort: Effort,
233
1848
        seed_head: SeedHead,
234
1848
        bytes: &equix::SolutionByteArray,
235
1848
    ) -> Result<Self, SolutionErrorV1> {
236
1848
        Ok(Self::new(
237
1848
            nonce,
238
1848
            effort,
239
1848
            seed_head,
240
1848
            equix::Solution::try_from_bytes(bytes).map_err(|_| SolutionErrorV1::Order)?,
241
        ))
242
1848
    }
243

            
244
    /// Get the winning [`Nonce`] value used in this solution
245
3102
    pub fn nonce(&self) -> &Nonce {
246
3102
        &self.nonce
247
3102
    }
248

            
249
    /// Get the client-chosen and provable [`Effort`] value used in this solution
250
3102
    pub fn effort(&self) -> Effort {
251
3102
        self.effort
252
3102
    }
253

            
254
    /// Get the [`SeedHead`] value identifying the puzzle this solution is for
255
3168
    pub fn seed_head(&self) -> SeedHead {
256
3168
        self.seed_head
257
3168
    }
258

            
259
    /// Reference the [`equix::Solution`] backing the proof portion
260
1584
    pub fn proof(&self) -> &equix::Solution {
261
1584
        &self.proof
262
1584
    }
263

            
264
    /// Clone the proof portion of the solution in its canonical byte string format
265
3102
    pub fn proof_to_bytes(&self) -> equix::SolutionByteArray {
266
3102
        self.proof.to_bytes()
267
3102
    }
268
}
269

            
270
#[cfg(test)]
271
mod tests {
272
    use super::*;
273

            
274
    #[test]
275
    fn new_seed_head_collision() {
276
        use tor_basic_utils::test_rng::Config;
277

            
278
        let mut rng = Config::Seeded([
279
            191, 169, 93, 126, 223, 128, 184, 217, 105, 3, 80, 87, 181, 242, 206, 38, 152, 149,
280
            116, 71, 249, 142, 6, 196, 188, 141, 20, 139, 97, 45, 230, 55,
281
        ])
282
        .into_rng();
283

            
284
        let seed_1 = Seed::new(&mut rng, None);
285
        let seed_2_shared_head = Seed::new(&mut rng, None);
286

            
287
        // Verify that this RNG seed does actually result in a collision.
288
        // If the code to generate the seed is changed, we may need to find a new RNG seed to
289
        // generate this collision.
290
        assert_eq!(seed_1.head(), seed_2_shared_head.head());
291

            
292
        let mut rng = Config::Seeded([0x00; 32]).into_rng();
293

            
294
        let seed_1 = Seed::new(&mut rng, None);
295
        let seed_2 = Seed::new(&mut rng, Some(&seed_1));
296

            
297
        assert_ne!(seed_1.head(), seed_2.head());
298
    }
299
}