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

            
7
use crate::pow::v1::{
8
    err::SolutionErrorV1, types::Effort, types::Instance, types::NONCE_LEN, types::Nonce,
9
    types::SEED_LEN, types::Seed,
10
};
11
use arrayvec::{ArrayVec, CapacityError};
12
use 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.
19
const P_STRING: &[u8] = b"Tor hs intro v1\0";
20

            
21
/// Length of the personalization string, in bytes
22
const P_STRING_LEN: usize = 16;
23

            
24
/// Length of the HsBlindId
25
const ID_LEN: usize = 32;
26

            
27
/// Location of the [`Seed`] within a [`Challenge`]
28
const SEED_OFFSET: usize = P_STRING_LEN + ID_LEN;
29

            
30
/// Location of the [`Nonce`] within a [`Challenge`]
31
const NONCE_OFFSET: usize = SEED_OFFSET + SEED_LEN;
32

            
33
/// Location of the [`Effort`] within a [`Challenge`]
34
const EFFORT_OFFSET: usize = NONCE_OFFSET + NONCE_LEN;
35

            
36
/// Packed length of an [`Effort`], in bytes
37
const EFFORT_LEN: usize = 4;
38

            
39
/// Total length of our Equi-X challenge string
40
const 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)]
47
pub(super) struct Challenge([u8; CHALLENGE_LEN]);
48

            
49
impl Challenge {
50
    /// Build a new [`Challenge`].
51
    ///
52
    /// Copies [`Instance`], [`Effort`], and [`Nonce`] values into
53
    /// a new byte array.
54
1128
    pub(super) fn new(instance: &Instance, effort: Effort, nonce: &Nonce) -> Self {
55
1128
        let mut result = ArrayVec::<u8, CHALLENGE_LEN>::new();
56
1128
        (|| -> Result<(), CapacityError> {
57
1128
            result.try_extend_from_slice(P_STRING)?;
58
1128
            result.try_extend_from_slice(instance.service().as_ref())?;
59
1128
            assert_eq!(result.len(), SEED_OFFSET);
60
1128
            result.try_extend_from_slice(instance.seed().as_ref())?;
61
1128
            assert_eq!(result.len(), NONCE_OFFSET);
62
1128
            result.try_extend_from_slice(nonce.as_ref())?;
63
1128
            assert_eq!(result.len(), EFFORT_OFFSET);
64
1128
            result.try_extend_from_slice(&effort.as_ref().to_be_bytes())
65
        })()
66
1128
        .expect("CHALLENGE_LEN holds a full challenge string");
67
1128
        Self(
68
1128
            result
69
1128
                .into_inner()
70
1128
                .expect("challenge buffer is fully written"),
71
1128
        )
72
1128
    }
73

            
74
    /// Clone the [`Seed`] portion of this challenge.
75
480
    pub(super) fn seed(&self) -> Seed {
76
480
        let array: [u8; SEED_LEN] = self.0[SEED_OFFSET..(SEED_OFFSET + SEED_LEN)]
77
480
            .try_into()
78
480
            .expect("slice length correct");
79
480
        array.into()
80
480
    }
81

            
82
    /// Clone the [`Nonce`] portion of this challenge.
83
480
    pub(super) fn nonce(&self) -> Nonce {
84
480
        let array: [u8; NONCE_LEN] = self.0[NONCE_OFFSET..(NONCE_OFFSET + NONCE_LEN)]
85
480
            .try_into()
86
480
            .expect("slice length correct");
87
480
        array.into()
88
480
    }
89

            
90
    /// Return the [`Effort`] used in this challenge.
91
3120
    pub(super) fn effort(&self) -> Effort {
92
3120
        u32::from_be_bytes(
93
3120
            self.0[EFFORT_OFFSET..(EFFORT_OFFSET + EFFORT_LEN)]
94
3120
                .try_into()
95
3120
                .expect("slice length correct"),
96
        )
97
3120
        .into()
98
3120
    }
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
552
    pub(super) fn increment_nonce(&mut self) {
107
        /// Wrapping increment for a serialized little endian value of arbitrary width.
108
552
        fn inc_le_bytes(slice: &mut [u8]) {
109
1320
            for byte in slice {
110
1272
                let (value, overflow) = (*byte).overflowing_add(1);
111
1272
                *byte = value;
112
1272
                if !overflow {
113
504
                    break;
114
768
                }
115
            }
116
552
        }
117
552
        inc_le_bytes(&mut self.0[NONCE_OFFSET..(NONCE_OFFSET + NONCE_LEN)]);
118
552
    }
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
2640
    pub(super) fn check_effort(
128
2640
        &self,
129
2640
        proof: &equix::SolutionByteArray,
130
2640
    ) -> Result<(), SolutionErrorV1> {
131
2640
        let mut hasher = Blake2b::<U4>::new();
132
2640
        hasher.update(self.as_ref());
133
2640
        hasher.update(proof.as_ref());
134
2640
        let value = u32::from_be_bytes(hasher.finalize().into());
135
2640
        match value.checked_mul(*self.effort().as_ref()) {
136
1056
            Some(_) => Ok(()),
137
1584
            None => Err(SolutionErrorV1::Effort),
138
        }
139
2640
    }
140
}