1
#![cfg_attr(docsrs, feature(doc_auto_cfg, doc_cfg))]
2
#![doc = include_str!("../README.md")]
3
// @@ begin lint list maintained by maint/add_warning @@
4
#![allow(renamed_and_removed_lints)] // @@REMOVE_WHEN(ci_arti_stable)
5
#![allow(unknown_lints)] // @@REMOVE_WHEN(ci_arti_nightly)
6
#![warn(missing_docs)]
7
#![warn(noop_method_call)]
8
#![warn(unreachable_pub)]
9
#![warn(clippy::all)]
10
#![deny(clippy::await_holding_lock)]
11
#![deny(clippy::cargo_common_metadata)]
12
#![deny(clippy::cast_lossless)]
13
#![deny(clippy::checked_conversions)]
14
#![warn(clippy::cognitive_complexity)]
15
#![deny(clippy::debug_assert_with_mut_call)]
16
#![deny(clippy::exhaustive_enums)]
17
#![deny(clippy::exhaustive_structs)]
18
#![deny(clippy::expl_impl_clone_on_copy)]
19
#![deny(clippy::fallible_impl_from)]
20
#![deny(clippy::implicit_clone)]
21
#![deny(clippy::large_stack_arrays)]
22
#![warn(clippy::manual_ok_or)]
23
#![deny(clippy::missing_docs_in_private_items)]
24
#![warn(clippy::needless_borrow)]
25
#![warn(clippy::needless_pass_by_value)]
26
#![warn(clippy::option_option)]
27
#![deny(clippy::print_stderr)]
28
#![deny(clippy::print_stdout)]
29
#![warn(clippy::rc_buffer)]
30
#![deny(clippy::ref_option_ref)]
31
#![warn(clippy::semicolon_if_nothing_returned)]
32
#![warn(clippy::trait_duplication_in_bounds)]
33
#![deny(clippy::unchecked_duration_subtraction)]
34
#![deny(clippy::unnecessary_wraps)]
35
#![warn(clippy::unseparated_literal_suffix)]
36
#![deny(clippy::unwrap_used)]
37
#![deny(clippy::mod_module_files)]
38
#![allow(clippy::let_unit_value)] // This can reasonably be done for explicitness
39
#![allow(clippy::uninlined_format_args)]
40
#![allow(clippy::significant_drop_in_scrutinee)] // arti/-/merge_requests/588/#note_2812945
41
#![allow(clippy::result_large_err)] // temporary workaround for arti#587
42
#![allow(clippy::needless_raw_string_hashes)] // complained-about code is fine, often best
43
#![allow(clippy::needless_lifetimes)] // See arti#1765
44
#![allow(mismatched_lifetime_syntaxes)] // temporary workaround for arti#2060
45
//! <!-- @@ end lint list maintained by maint/add_warning @@ -->
46

            
47
mod bucket_array;
48
mod collision;
49
mod err;
50
mod solution;
51
mod solver;
52

            
53
// Export bucket_array::mem API only to the fuzzer.
54
// (This is not stable; you should not use it except for testing.)
55
#[cfg(feature = "bucket-array")]
56
pub use bucket_array::mem::{BucketArray, BucketArrayMemory, BucketArrayPair, Count, Uninit};
57

            
58
use hashx::{HashX, HashXBuilder};
59

            
60
pub use hashx::{Runtime, RuntimeOption};
61

            
62
pub use err::{Error, HashError};
63
pub use solution::{Solution, SolutionArray, SolutionByteArray, SolutionItem, SolutionItemArray};
64
pub use solver::SolverMemory;
65

            
66
/// One Equi-X instance, customized for a challenge string
67
///
68
/// This includes pre-computed state that depends on the
69
/// puzzle's challenge as well as any options set via [`EquiXBuilder`].
70
#[derive(Debug)]
71
pub struct EquiX {
72
    /// HashX instance generated for this puzzle's challenge string
73
    hash: HashX,
74
}
75

            
76
impl EquiX {
77
    /// Make a new [`EquiX`] instance with a challenge string and
78
    /// default options.
79
    ///
80
    /// It's normal for this to fail with a [`HashError::ProgramConstraints`]
81
    /// for a small fraction of challenge values. Those challenges must be
82
    /// skipped by solvers and rejected by verifiers.
83
1125
    pub fn new(challenge: &[u8]) -> Result<Self, Error> {
84
1125
        EquiXBuilder::new().build(challenge)
85
1125
    }
86

            
87
    /// Check which actual program runtime is in effect.
88
    ///
89
    /// By default we try to generate machine code at runtime to accelerate the
90
    /// hash function, but we fall back to an interpreter if this fails. The
91
    /// compiler can be disabled entirely using [`RuntimeOption::InterpretOnly`]
92
    /// and [`EquiXBuilder`].
93
    pub fn runtime(&self) -> Runtime {
94
        self.hash.runtime()
95
    }
96

            
97
    /// Check a [`Solution`] against this particular challenge.
98
    ///
99
    /// Having a [`Solution`] instance guarantees that the order of items
100
    /// has already been checked. This only needs to check hash tree sums.
101
    /// Returns either `Ok` or [`Error::HashSum`].
102
9550
    pub fn verify(&self, solution: &Solution) -> Result<(), Error> {
103
9550
        solution::check_all_tree_sums(&self.hash, solution)
104
9550
    }
105

            
106
    /// Search for solutions using this particular challenge.
107
    ///
108
    /// Returns a buffer with a variable number of solutions.
109
    /// Memory for the solver is allocated dynamically and not reused.
110
800
    pub fn solve(&self) -> SolutionArray {
111
800
        let mut mem = SolverMemory::new();
112
800
        self.solve_with_memory(&mut mem)
113
800
    }
114

            
115
    /// Search for solutions, using the provided [`SolverMemory`].
116
    ///
117
    /// Returns a buffer with a variable number of solutions.
118
    ///
119
    /// Allows reuse of solver memory. Preferred for callers which may perform
120
    /// several solve operations in rapid succession, such as in the common case
121
    /// of layering an effort adjustment protocol above Equi-X.
122
1875
    pub fn solve_with_memory(&self, mem: &mut SolverMemory) -> SolutionArray {
123
1875
        let mut result = Default::default();
124
1875
        solver::find_solutions(&self.hash, mem, &mut result);
125
1875
        result
126
1875
    }
127
}
128

            
129
/// Builder for creating [`EquiX`] instances with custom settings
130
#[derive(Debug, Clone, Eq, PartialEq)]
131
pub struct EquiXBuilder {
132
    /// Inner [`HashXBuilder`] for options related to our hash function
133
    hash: HashXBuilder,
134
}
135

            
136
impl EquiXBuilder {
137
    /// Create a new [`EquiXBuilder`] with default settings.
138
    ///
139
    /// Immediately calling [`Self::build()`] would be equivalent to using
140
    /// [`EquiX::new()`].
141
2325
    pub fn new() -> Self {
142
2325
        Self {
143
2325
            hash: HashXBuilder::new(),
144
2325
        }
145
2325
    }
146

            
147
    /// Select a new [`RuntimeOption`].
148
    pub fn runtime(&mut self, runtime: RuntimeOption) -> &mut Self {
149
        self.hash.runtime(runtime);
150
        self
151
    }
152

            
153
    /// Build an [`EquiX`] instance with a challenge string and the
154
    /// selected options.
155
    ///
156
    /// It's normal for this to fail with a [`HashError::ProgramConstraints`]
157
    /// for a small fraction of challenge values. Those challenges must be
158
    /// skipped by solvers and rejected by verifiers.
159
2800
    pub fn build(&self, challenge: &[u8]) -> Result<EquiX, Error> {
160
2800
        match self.hash.build(challenge) {
161
150
            Err(e) => Err(Error::Hash(e)),
162
2650
            Ok(hash) => Ok(EquiX { hash }),
163
        }
164
2800
    }
165

            
166
    /// Search for solutions to a particular challenge.
167
    ///
168
    /// Each solve invocation returns zero or more solutions.
169
    /// Memory for the solver is allocated dynamically and not reused.
170
    ///
171
    /// It's normal for this to fail with a [`HashError::ProgramConstraints`]
172
    /// for a small fraction of challenge values. Those challenges must be
173
    /// skipped by solvers and rejected by verifiers.
174
    pub fn solve(&self, challenge: &[u8]) -> Result<SolutionArray, Error> {
175
        Ok(self.build(challenge)?.solve())
176
    }
177

            
178
    /// Check a [`Solution`] against a particular challenge string.
179
    ///
180
    /// Having a [`Solution`] instance guarantees that the order of items
181
    /// has already been checked. This only needs to check hash tree sums.
182
    /// Returns either `Ok` or [`Error::HashSum`].
183
600
    pub fn verify(&self, challenge: &[u8], solution: &Solution) -> Result<(), Error> {
184
600
        self.build(challenge)?.verify(solution)
185
600
    }
186

            
187
    /// Check a [`SolutionItemArray`].
188
    ///
189
    /// Returns an error if the array is not a well formed [`Solution`] or it's
190
    /// not suitable for the given challenge.
191
    pub fn verify_array(&self, challenge: &[u8], array: &SolutionItemArray) -> Result<(), Error> {
192
        // Check Solution validity before we even construct the instance
193
        self.verify(challenge, &Solution::try_from_array(array)?)
194
    }
195

            
196
    /// Check a [`SolutionByteArray`].
197
    ///
198
    /// Returns an error if the array is not a well formed [`Solution`] or it's
199
    /// not suitable for the given challenge.
200
    pub fn verify_bytes(&self, challenge: &[u8], array: &SolutionByteArray) -> Result<(), Error> {
201
        self.verify(challenge, &Solution::try_from_bytes(array)?)
202
    }
203
}
204

            
205
impl Default for EquiXBuilder {
206
1200
    fn default() -> Self {
207
1200
        Self::new()
208
1200
    }
209
}
210

            
211
/// Search for solutions, using default [`EquiXBuilder`] options.
212
///
213
/// Each solve invocation returns zero or more solutions.
214
/// Memory for the solver is allocated dynamically and not reused.
215
///
216
/// It's normal for this to fail with a [`HashError::ProgramConstraints`] for
217
/// a small fraction of challenge values. Those challenges must be skipped
218
/// by solvers and rejected by verifiers.
219
pub fn solve(challenge: &[u8]) -> Result<SolutionArray, Error> {
220
    Ok(EquiX::new(challenge)?.solve())
221
}
222

            
223
/// Check a [`Solution`] against a particular challenge.
224
///
225
/// Having a [`Solution`] instance guarantees that the order of items
226
/// has already been checked. This only needs to check hash tree sums.
227
/// Returns either `Ok` or [`Error::HashSum`].
228
///
229
/// Uses default [`EquiXBuilder`] options.
230
75
pub fn verify(challenge: &[u8], solution: &Solution) -> Result<(), Error> {
231
75
    EquiX::new(challenge)?.verify(solution)
232
75
}
233

            
234
/// Check a [`SolutionItemArray`].
235
///
236
/// Returns an error if the array is not a well formed [`Solution`] or it's
237
/// not suitable for the given challenge.
238
///
239
/// Uses default [`EquiXBuilder`] options.
240
100
pub fn verify_array(challenge: &[u8], array: &SolutionItemArray) -> Result<(), Error> {
241
100
    // Check Solution validity before we even construct the instance
242
100
    verify(challenge, &Solution::try_from_array(array)?)
243
100
}
244

            
245
/// Check a [`SolutionByteArray`].
246
///
247
/// Returns an error if the array is not a well formed [`Solution`] or it's
248
/// not suitable for the given challenge.
249
///
250
/// Uses default [`EquiXBuilder`] options.
251
pub fn verify_bytes(challenge: &[u8], array: &SolutionByteArray) -> Result<(), Error> {
252
    // Check Solution validity before we even construct the instance
253
    verify(challenge, &Solution::try_from_bytes(array)?)
254
}