stealth_lib/hash/
mimc.rs

1//! MiMC-Feistel sponge hash function.
2//!
3//! MiMC (Minimal Multiplicative Complexity) is a hash function designed for
4//! efficient evaluation inside arithmetic circuits, particularly in ZK-SNARKs.
5//!
6//! # Algorithm
7//!
8//! This implementation uses the MiMC-Feistel-Sponge construction with:
9//! - Feistel network structure for the permutation
10//! - Sponge construction for variable-length input
11//! - Exponent of 5 (x^5) for the round function
12//!
13//! # Constants
14//!
15//! The round constants are derived deterministically. The default configuration
16//! uses constants compatible with circomlib/Tornado Cash implementations.
17//!
18//! # References
19//!
20//! - [MiMC Paper](https://eprint.iacr.org/2016/492.pdf)
21//! - [circomlib implementation](https://github.com/iden3/circomlib/blob/master/circuits/mimcsponge.circom)
22//!
23//! # Example
24//!
25//! ```
26//! use stealth_lib::hash::MimcHasher;
27//!
28//! let hasher = MimcHasher::default();
29//! let hash = hasher.hash(123, 456);
30//! println!("MiMC hash: {}", hash);
31//! ```
32//!
33//! # Security Note
34//!
35//! This implementation is designed for use in ZK circuits. It is:
36//! - **NOT constant-time** (do not use where timing attacks are a concern)
37//! - **NOT suitable for password hashing** (use argon2, bcrypt, or scrypt instead)
38
39/// MiMC round constants.
40///
41/// These constants are derived deterministically and are compatible with
42/// the circomlib/Tornado Cash MiMC implementation.
43///
44/// The constants are computed as: `keccak256("mimcsponge" || i)` truncated to
45/// fit the field, where `i` is the round index.
46const MIMC_CONSTANTS: [u128; 20] = [
47    0,
48    25823191961023811529686723375255045,
49    48376936063113800887806988124358800,
50    75580405153655082660116863095114839,
51    66651710483985382365580181188706173,
52    45887003413921204775397977044284378,
53    14399999722617037892747232478295923,
54    29376176727758177809204424209125257,
55    13768859312518298840937540532277016,
56    54749662990362840569021981534456448,
57    25161436470718351277017231215227846,
58    90370030464179443930112165274275271,
59    92014788260850167582827910417652439,
60    40376490640073034398204558905403523,
61    90379224439153137712327643289289624,
62    11220341520269979188892857030918685,
63    11480168113674888067906254878279274,
64    11144081894867681653997893051446803,
65    64965960071752809090438003157362764,
66    98428510787134995495896453413714864,
67];
68
69/// Default field prime (2^128 - 1).
70///
71/// This is the maximum value for u128, used as the modulus for field arithmetic.
72const DEFAULT_FIELD_PRIME: u128 = 340282366920938463463374607431768211455;
73
74/// Default number of rounds for MiMC-Feistel.
75const DEFAULT_ROUNDS: usize = 10;
76
77/// MiMC-Feistel sponge hasher.
78///
79/// This struct provides the MiMC hash function with configurable parameters.
80/// For most use cases, use [`MimcHasher::default()`] which provides parameters
81/// compatible with Tornado Cash / circomlib.
82///
83/// # Example
84///
85/// ```
86/// use stealth_lib::hash::MimcHasher;
87///
88/// // Use default parameters (compatible with Tornado Cash)
89/// let hasher = MimcHasher::default();
90/// let hash = hasher.hash(123, 456);
91///
92/// // Hash is deterministic
93/// assert_eq!(hasher.hash(123, 456), hasher.hash(123, 456));
94///
95/// // Different inputs produce different outputs
96/// assert_ne!(hasher.hash(123, 456), hasher.hash(123, 789));
97/// ```
98#[derive(Debug, Clone)]
99pub struct MimcHasher {
100    /// Field prime (modulus for all arithmetic operations).
101    field_prime: u128,
102    /// Number of rounds in the Feistel network.
103    num_rounds: usize,
104    /// Round constants.
105    constants: Vec<u128>,
106}
107
108impl Default for MimcHasher {
109    /// Creates a MimcHasher with default parameters compatible with Tornado Cash.
110    ///
111    /// - Field prime: 2^128 - 1
112    /// - Rounds: 10
113    /// - Constants: circomlib-compatible
114    fn default() -> Self {
115        MimcHasher {
116            field_prime: DEFAULT_FIELD_PRIME,
117            num_rounds: DEFAULT_ROUNDS,
118            constants: MIMC_CONSTANTS.to_vec(),
119        }
120    }
121}
122
123impl MimcHasher {
124    /// Creates a new MimcHasher with custom parameters.
125    ///
126    /// # Arguments
127    ///
128    /// * `field_prime` - The field modulus for arithmetic operations
129    /// * `num_rounds` - Number of Feistel rounds
130    /// * `constants` - Round constants (must have at least `num_rounds * 2` elements)
131    ///
132    /// # Example
133    ///
134    /// ```
135    /// use stealth_lib::hash::MimcHasher;
136    ///
137    /// let constants = vec![0u128; 20];
138    /// let hasher = MimcHasher::new(
139    ///     340282366920938463463374607431768211455, // 2^128 - 1
140    ///     10,
141    ///     constants,
142    /// );
143    /// ```
144    pub fn new(field_prime: u128, num_rounds: usize, constants: Vec<u128>) -> Self {
145        MimcHasher {
146            field_prime,
147            num_rounds,
148            constants,
149        }
150    }
151
152    /// Returns the field prime used by this hasher.
153    #[inline]
154    pub fn field_prime(&self) -> u128 {
155        self.field_prime
156    }
157
158    /// Returns the number of rounds used by this hasher.
159    #[inline]
160    pub fn num_rounds(&self) -> usize {
161        self.num_rounds
162    }
163
164    /// MiMC-Feistel permutation.
165    ///
166    /// Applies the Feistel network to the input pair (left, right) with the given key.
167    ///
168    /// # Arguments
169    ///
170    /// * `left` - Left input value
171    /// * `right` - Right input value
172    /// * `key` - Permutation key
173    ///
174    /// # Returns
175    ///
176    /// A tuple `(new_left, new_right)` after applying the Feistel permutation.
177    fn mimc_feistel(&self, left: u128, right: u128, key: u128) -> (u128, u128) {
178        let mut last_l = left;
179        let mut last_r = right;
180
181        for i in 0..self.num_rounds {
182            // mask = (right + key + c[i]) mod p
183            let mask = last_r
184                .wrapping_add(key)
185                .wrapping_rem(self.field_prime)
186                .wrapping_add(self.constants[i])
187                .wrapping_rem(self.field_prime);
188
189            // mask^5 mod p (using square-and-multiply)
190            let mask2 = mask.wrapping_mul(mask).wrapping_rem(self.field_prime);
191            let mask4 = mask2.wrapping_mul(mask2).wrapping_rem(self.field_prime);
192            let mask5 = mask4.wrapping_mul(mask).wrapping_rem(self.field_prime);
193
194            // Feistel swap
195            let temp = last_r;
196            last_r = last_l.wrapping_add(mask5).wrapping_rem(self.field_prime);
197            last_l = temp;
198        }
199
200        (last_l, last_r)
201    }
202
203    /// MiMC sponge hash function.
204    ///
205    /// Computes the MiMC-Feistel-Sponge hash of two input values.
206    /// This is the primary hash function used for Merkle tree construction.
207    ///
208    /// # Arguments
209    ///
210    /// * `left` - First input value
211    /// * `right` - Second input value
212    ///
213    /// # Returns
214    ///
215    /// The hash output as a `u128`.
216    ///
217    /// # Example
218    ///
219    /// ```
220    /// use stealth_lib::hash::MimcHasher;
221    ///
222    /// let hasher = MimcHasher::default();
223    ///
224    /// // Hash two values
225    /// let hash = hasher.hash(123, 456);
226    ///
227    /// // Hash is deterministic
228    /// assert_eq!(hash, hasher.hash(123, 456));
229    /// ```
230    pub fn hash(&self, left: u128, right: u128) -> u128 {
231        self.mimc_sponge(left, right, self.field_prime)
232    }
233
234    /// MiMC sponge with explicit key parameter.
235    ///
236    /// Lower-level function that allows specifying a custom key.
237    /// Most users should use [`hash`](Self::hash) instead.
238    ///
239    /// # Arguments
240    ///
241    /// * `left` - First input value
242    /// * `right` - Second input value  
243    /// * `key` - Sponge key
244    ///
245    /// # Returns
246    ///
247    /// The hash output as a `u128`.
248    pub fn mimc_sponge(&self, left: u128, right: u128, key: u128) -> u128 {
249        let mut last_r = left;
250        let mut last_l = right;
251
252        for _ in 0..self.num_rounds {
253            let (new_last_r, new_last_l) = self.mimc_feistel(last_r, last_l, key);
254
255            last_r = new_last_r.wrapping_add(1).wrapping_rem(self.field_prime);
256            last_l = new_last_l;
257        }
258
259        last_r
260    }
261
262    /// Hash a single value.
263    ///
264    /// Convenience method to hash a single input by pairing it with zero.
265    ///
266    /// # Arguments
267    ///
268    /// * `input` - The value to hash
269    ///
270    /// # Returns
271    ///
272    /// The hash output as a `u128`.
273    ///
274    /// # Example
275    ///
276    /// ```
277    /// use stealth_lib::hash::MimcHasher;
278    ///
279    /// let hasher = MimcHasher::default();
280    /// let hash = hasher.hash_single(12345);
281    /// ```
282    pub fn hash_single(&self, input: u128) -> u128 {
283        self.hash(input, 0)
284    }
285}
286
287// Legacy API support - these functions maintain backwards compatibility
288// with the original Hasher struct API.
289
290/// Legacy Hasher struct for backwards compatibility.
291///
292/// # Deprecated
293///
294/// This struct is provided for backwards compatibility only.
295/// New code should use [`MimcHasher`] instead.
296#[deprecated(since = "1.0.0", note = "Use MimcHasher instead")]
297pub struct Hasher;
298
299#[allow(deprecated)]
300impl Hasher {
301    /// MiMC sponge hash (legacy API).
302    ///
303    /// # Deprecated
304    ///
305    /// Use [`MimcHasher::mimc_sponge`] instead.
306    #[deprecated(since = "1.0.0", note = "Use MimcHasher::mimc_sponge instead")]
307    pub fn mimc_sponge(left: u128, right: u128, k: u128) -> u128 {
308        MimcHasher::default().mimc_sponge(left, right, k)
309    }
310}
311
312#[cfg(test)]
313mod tests {
314    use super::*;
315
316    #[test]
317    fn test_mimc_hash_deterministic() {
318        let hasher = MimcHasher::default();
319        let hash1 = hasher.hash(123, 456);
320        let hash2 = hasher.hash(123, 456);
321        assert_eq!(hash1, hash2);
322    }
323
324    #[test]
325    fn test_mimc_hash_different_inputs() {
326        let hasher = MimcHasher::default();
327        let hash1 = hasher.hash(123, 456);
328        let hash2 = hasher.hash(123, 789);
329        let hash3 = hasher.hash(456, 123);
330        assert_ne!(hash1, hash2);
331        assert_ne!(hash1, hash3);
332    }
333
334    #[test]
335    fn test_mimc_sponge_with_zero() {
336        let hasher = MimcHasher::default();
337        let hash1 = hasher.hash(0, 0);
338        let hash2 = hasher.hash(0, 1);
339        assert_ne!(hash1, hash2);
340    }
341
342    #[test]
343    fn test_mimc_hash_single() {
344        let hasher = MimcHasher::default();
345        let hash1 = hasher.hash_single(12345);
346        let hash2 = hasher.hash(12345, 0);
347        assert_eq!(hash1, hash2);
348    }
349
350    #[test]
351    fn test_mimc_feistel_permutation() {
352        let hasher = MimcHasher::default();
353        let (l1, r1) = hasher.mimc_feistel(100, 200, hasher.field_prime);
354        let (l2, r2) = hasher.mimc_feistel(100, 200, hasher.field_prime);
355        assert_eq!((l1, r1), (l2, r2));
356    }
357
358    #[test]
359    fn test_default_hasher_params() {
360        let hasher = MimcHasher::default();
361        assert_eq!(hasher.field_prime(), DEFAULT_FIELD_PRIME);
362        assert_eq!(hasher.num_rounds(), DEFAULT_ROUNDS);
363    }
364
365    #[test]
366    fn test_custom_hasher() {
367        let constants = vec![0u128; 20];
368        let hasher = MimcHasher::new(1000, 5, constants);
369        assert_eq!(hasher.field_prime(), 1000);
370        assert_eq!(hasher.num_rounds(), 5);
371    }
372
373    // Legacy API tests
374    #[test]
375    #[allow(deprecated)]
376    fn test_legacy_hasher_compatibility() {
377        let legacy_hash = Hasher::mimc_sponge(123, 456, DEFAULT_FIELD_PRIME);
378        let new_hash = MimcHasher::default().mimc_sponge(123, 456, DEFAULT_FIELD_PRIME);
379        assert_eq!(legacy_hash, new_hash);
380    }
381}
stealth_lib/hash/mimc.rs

stealth_lib/hash/
mimc.rs
