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, types::Seed,
9
    types::NONCE_LEN, types::SEED_LEN,
10
};
11
use arrayvec::{ArrayVec, CapacityError};
12
use blake2::{digest::consts::U4, Blake2b, Digest};
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
1034
    pub(super) fn new(instance: &Instance, effort: Effort, nonce: &Nonce) -> Self {
55
1034
        let mut result = ArrayVec::<u8, CHALLENGE_LEN>::new();
56
1034
        (|| -> Result<(), CapacityError> {
57
1034
            result.try_extend_from_slice(P_STRING)?;
58
1034
            result.try_extend_from_slice(instance.service().as_ref())?;
59
1034
            assert_eq!(result.len(), SEED_OFFSET);
60
1034
            result.try_extend_from_slice(instance.seed().as_ref())?;
61
1034
            assert_eq!(result.len(), NONCE_OFFSET);
62
1034
            result.try_extend_from_slice(nonce.as_ref())?;
63
1034
            assert_eq!(result.len(), EFFORT_OFFSET);
64
1034
            result.try_extend_from_slice(&effort.as_ref().to_be_bytes())
65
1034
        })()
66
1034
        .expect("CHALLENGE_LEN holds a full challenge string");
67
1034
        Self(
68
1034
            result
69
1034
                .into_inner()
70
1034
                .expect("challenge buffer is fully written"),
71
1034
        )
72
1034
    }
73

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

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

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