equix/
solution.rs

Help
1//! Representation and validation of Equi-X puzzle solutions
2//!
3//! Equi-X uses its own tweaked version of the Equihash algorithm. Solutions
4//! are arrays of [`SolutionItem`]s, each representing one item in a space of
5//! hash outputs. The `SolutionItem`s form a binary tree with constraints
6//! on the sorting order of the items and on the sums of their corresponding
7//! hashes.
8
9use crate::Error;
10use arrayvec::ArrayVec;
11use hashx::HashX;
12use std::{cmp, mem};
13
14/// Equihash N parameter for Equi-X, number of bits used from the hash output
15pub(crate) const EQUIHASH_N: usize = 60;
16
17/// Equihash K parameter for Equi-X, the number of tree layers
18pub(crate) const EQUIHASH_K: usize = 3;
19
20/// One item in the solution
21///
22/// The Equihash paper also calls these "indices", to reference the way they
23/// index into a space of potential hash outputs. They form the leaf nodes in
24/// a binary tree of hashes.
25pub type SolutionItem = u16;
26
27/// One hash value, computed from a [`SolutionItem`]
28///
29/// Must hold [`EQUIHASH_N`] bits.
30pub(crate) type HashValue = u64;
31
32/// Compute a [`HashValue`] from a [`SolutionItem`]
33#[inline(always)]
34pub(crate) fn item_hash(func: &HashX, item: SolutionItem) -> HashValue {
35    func.hash_to_u64(item.into())
36}
37
38/// A bundle of solutions as returned by one invocation of the solver
39///
40/// The actual number of solutions found is random, depending on the number of
41/// collisions that exist. This size is arbitrary, and in the rare case that
42/// the solver finds more solutions they are discarded.
43pub type SolutionArray = ArrayVec<Solution, 8>;
44
45/// A raw Item array which may or may not be a well-formed [`Solution`]
46pub type SolutionItemArray = [SolutionItem; Solution::NUM_ITEMS];
47
48/// A byte array of the right length to convert to/from a [`Solution`]
49pub type SolutionByteArray = [u8; Solution::NUM_BYTES];
50
51/// Potential solution to an EquiX puzzle
52///
53/// The `Solution` type itself verifies the well-formedness of an Equi-X
54/// solution, but not its suitability for a particular challenge string.
55#[derive(Debug, Clone, Eq, PartialEq)]
56pub struct Solution {
57    /// Inner fixed-sized array of SolutionItem
58    items: SolutionItemArray,
59}
60
61impl Solution {
62    /// Number of items (selected hash inputs) in each solution
63    pub const NUM_ITEMS: usize = 1 << EQUIHASH_K;
64
65    /// Number of bytes in the packed representation of a solution
66    pub const NUM_BYTES: usize = Self::NUM_ITEMS * mem::size_of::<SolutionItem>();
67
68    /// Size of each [`SolutionItem`], in bytes
69    const ITEM_SIZE: usize = mem::size_of::<SolutionItem>();
70
71    /// Build a [`Solution`] from an array of items, checking that
72    /// the solution is well-formed.
73    pub fn try_from_array(items: &SolutionItemArray) -> Result<Self, Error> {
74        if check_tree_order(items) {
75            Ok(Self { items: *items })
76        } else {
77            Err(Error::Order)
78        }
79    }
80
81    /// Build a [`Solution`] by sorting a [`SolutionItemArray`] as necessary,
82    /// without the possibility of failure.
83    ///    
84    /// Used by the solver.
85    pub(crate) fn sort_from_array(mut items: SolutionItemArray) -> Self {
86        sort_into_tree_order(&mut items);
87        Self { items }
88    }
89
90    /// Build a [`Solution`] from a fixed size byte array, checking
91    /// that the solution is well-formed.
92    pub fn try_from_bytes(bytes: &SolutionByteArray) -> Result<Self, Error> {
93        let mut array: SolutionItemArray = Default::default();
94        for i in 0..Self::NUM_ITEMS {
95            array[i] = SolutionItem::from_le_bytes(
96                bytes[i * Self::ITEM_SIZE..(i + 1) * Self::ITEM_SIZE]
97                    .try_into()
98                    .expect("slice length matches"),
99            );
100        }
101        Self::try_from_array(&array)
102    }
103
104    /// Return the packed byte representation of this Solution.
105    pub fn to_bytes(&self) -> SolutionByteArray {
106        let mut result: SolutionByteArray = Default::default();
107        for i in 0..Self::NUM_ITEMS {
108            result[i * Self::ITEM_SIZE..(i + 1) * Self::ITEM_SIZE]
109                .copy_from_slice(&self.items[i].to_le_bytes());
110        }
111        result
112    }
113}
114
115impl AsRef<SolutionItemArray> for Solution {
116    fn as_ref(&self) -> &SolutionItemArray {
117        &self.items
118    }
119}
120
121impl From<Solution> for SolutionItemArray {
122    fn from(solution: Solution) -> SolutionItemArray {
123        solution.items
124    }
125}
126
127/// Ordering predicate for each node of the SolutionItem tree
128#[inline(always)]
129fn branches_are_sorted(left: &[SolutionItem], right: &[SolutionItem]) -> bool {
130    matches!(
131        left.iter().rev().cmp(right.iter().rev()),
132        cmp::Ordering::Less | cmp::Ordering::Equal
133    )
134}
135
136/// Check tree ordering recursively.
137///
138/// HashX uses a lexicographic ordering constraint applied at each tree level,
139/// to resolve the ambiguity that would otherwise be present between each pair
140/// of branches in the item tree.
141///
142/// When combined with the hash sum constraints, this fully constrains the order
143/// of the items in a solution. On its own this constraint only partially defines
144/// the order of the entire item array.
145#[inline(always)]
146fn check_tree_order(items: &[SolutionItem]) -> bool {
147    let (left, right) = items.split_at(items.len() / 2);
148    let sorted = branches_are_sorted(left, right);
149    if items.len() == 2 {
150        sorted
151    } else {
152        sorted && check_tree_order(left) && check_tree_order(right)
153    }
154}
155
156/// Sort a solution in-place into tree order.
157#[inline(always)]
158fn sort_into_tree_order(items: &mut [SolutionItem]) {
159    let len = items.len();
160    let (left, right) = items.split_at_mut(items.len() / 2);
161    if len > 2 {
162        sort_into_tree_order(left);
163        sort_into_tree_order(right);
164    }
165    if !branches_are_sorted(left, right) {
166        left.swap_with_slice(right);
167    }
168}
169
170/// Check hash sums recursively.
171///
172/// The main solution constraint in HashX is a partial sum at each tree level.
173/// The overall match required is [`EQUIHASH_N`] bits, and each subsequent tree
174/// level needs a match half this long.
175///
176/// Each recursive invocation returns the entire sum if its layer has the
177/// indicated number of matching bits.
178#[inline(always)]
179fn check_tree_sums(func: &HashX, items: &[SolutionItem], n_bits: usize) -> Result<HashValue, ()> {
180    let sum = if items.len() == 2 {
181        item_hash(func, items[0]).wrapping_add(item_hash(func, items[1]))
182    } else {
183        let (left, right) = items.split_at(items.len() / 2);
184        let left = check_tree_sums(func, left, n_bits / 2)?;
185        let right = check_tree_sums(func, right, n_bits / 2)?;
186        left.wrapping_add(right)
187    };
188    let mask = ((1 as HashValue) << n_bits) - 1;
189    if (sum & mask) == 0 {
190        Ok(sum)
191    } else {
192        Err(())
193    }
194}
195
196/// Check all tree sums, using the full size defined by [`EQUIHASH_N`].
197///
198/// This will recurse at compile-time into
199/// layered tests for 60-, 30-, and 15-bit masks.
200pub(crate) fn check_all_tree_sums(func: &HashX, solution: &Solution) -> Result<(), Error> {
201    match check_tree_sums(func, solution.as_ref(), EQUIHASH_N) {
202        Ok(_unused_bits) => Ok(()),
203        Err(()) => Err(Error::HashSum),
204    }
205}
equix/solution.rs

equix/
solution.rs
