equix/
lib.rs

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
47mod bucket_array;
48mod collision;
49mod err;
50mod solution;
51mod 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")]
56pub use bucket_array::mem::{BucketArray, BucketArrayMemory, BucketArrayPair, Count, Uninit};
57
58use hashx::{HashX, HashXBuilder};
59
60pub use hashx::{Runtime, RuntimeOption};
61
62pub use err::{Error, HashError};
63pub use solution::{Solution, SolutionArray, SolutionByteArray, SolutionItem, SolutionItemArray};
64pub 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)]
71pub struct EquiX {
72    /// HashX instance generated for this puzzle's challenge string
73    hash: HashX,
74}
75
76impl 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    pub fn new(challenge: &[u8]) -> Result<Self, Error> {
84        EquiXBuilder::new().build(challenge)
85    }
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    pub fn verify(&self, solution: &Solution) -> Result<(), Error> {
103        solution::check_all_tree_sums(&self.hash, solution)
104    }
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    pub fn solve(&self) -> SolutionArray {
111        let mut mem = SolverMemory::new();
112        self.solve_with_memory(&mut mem)
113    }
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    pub fn solve_with_memory(&self, mem: &mut SolverMemory) -> SolutionArray {
123        let mut result = Default::default();
124        solver::find_solutions(&self.hash, mem, &mut result);
125        result
126    }
127}
128
129/// Builder for creating [`EquiX`] instances with custom settings
130#[derive(Debug, Clone, Eq, PartialEq)]
131pub struct EquiXBuilder {
132    /// Inner [`HashXBuilder`] for options related to our hash function
133    hash: HashXBuilder,
134}
135
136impl EquiXBuilder {
137    /// Create a new [`EquiXBuilder`] with default settings.
138    ///
139    /// Immediately calling [`Self::build()`] would be equivalent to using
140    /// [`EquiX::new()`].
141    pub fn new() -> Self {
142        Self {
143            hash: HashXBuilder::new(),
144        }
145    }
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    pub fn build(&self, challenge: &[u8]) -> Result<EquiX, Error> {
160        match self.hash.build(challenge) {
161            Err(e) => Err(Error::Hash(e)),
162            Ok(hash) => Ok(EquiX { hash }),
163        }
164    }
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    pub fn verify(&self, challenge: &[u8], solution: &Solution) -> Result<(), Error> {
184        self.build(challenge)?.verify(solution)
185    }
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
205impl Default for EquiXBuilder {
206    fn default() -> Self {
207        Self::new()
208    }
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.
219pub 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.
230pub fn verify(challenge: &[u8], solution: &Solution) -> Result<(), Error> {
231    EquiX::new(challenge)?.verify(solution)
232}
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.
240pub fn verify_array(challenge: &[u8], array: &SolutionItemArray) -> Result<(), Error> {
241    // Check Solution validity before we even construct the instance
242    verify(challenge, &Solution::try_from_array(array)?)
243}
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.
251pub 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}