miden-crypto/src/hash/rescue/rpo/digest.rs
src/hash/rescue/rpo/digest.rsRaw
1use core::{cmp::Ordering, fmt::Display, ops::Deref};
2
3use super::{Digest, Felt, StarkField, DIGEST_BYTES, DIGEST_SIZE, ZERO};
4use crate::{
5 rand::Randomizable,
6 utils::{
7 bytes_to_hex_string, hex_to_bytes, string::*, ByteReader, ByteWriter, Deserializable,
8 DeserializationError, HexParseError, Serializable,
9 },
10};
11
12// DIGEST TRAIT IMPLEMENTATIONS
13// ================================================================================================
14
15#[derive(Debug, Default, Copy, Clone, Eq, PartialEq)]
16#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
17#[cfg_attr(feature = "serde", serde(into = "String", try_from = "&str"))]
18pub struct RpoDigest([Felt; DIGEST_SIZE]);
19
20impl RpoDigest {
21 pub const fn new(value: [Felt; DIGEST_SIZE]) -> Self {
22 Self(value)
23 }
24
25 pub fn as_elements(&self) -> &[Felt] {
26 self.as_ref()
27 }
28
29 pub fn as_bytes(&self) -> [u8; DIGEST_BYTES] {
30 <Self as Digest>::as_bytes(self)
31 }
32
33 pub fn digests_as_elements<'a, I>(digests: I) -> impl Iterator<Item = &'a Felt>
34 where
35 I: Iterator<Item = &'a Self>,
36 {
37 digests.flat_map(|d| d.0.iter())
38 }
39
40 /// Returns hexadecimal representation of this digest prefixed with `0x`.
41 pub fn to_hex(&self) -> String {
42 bytes_to_hex_string(self.as_bytes())
43 }
44}
45
46impl Digest for RpoDigest {
47 fn as_bytes(&self) -> [u8; DIGEST_BYTES] {
48 let mut result = [0; DIGEST_BYTES];
49
50 result[..8].copy_from_slice(&self.0[0].as_int().to_le_bytes());
51 result[8..16].copy_from_slice(&self.0[1].as_int().to_le_bytes());
52 result[16..24].copy_from_slice(&self.0[2].as_int().to_le_bytes());
53 result[24..].copy_from_slice(&self.0[3].as_int().to_le_bytes());
54
55 result
56 }
57}
58
59impl Deref for RpoDigest {
60 type Target = [Felt; DIGEST_SIZE];
61
62 fn deref(&self) -> &Self::Target {
63 &self.0
64 }
65}
66
67impl Ord for RpoDigest {
68 fn cmp(&self, other: &Self) -> Ordering {
69 // compare the inner u64 of both elements.
70 //
71 // it will iterate the elements and will return the first computation different than
72 // `Equal`. Otherwise, the ordering is equal.
73 //
74 // the endianness is irrelevant here because since, this being a cryptographically secure
75 // hash computation, the digest shouldn't have any ordered property of its input.
76 //
77 // finally, we use `Felt::inner` instead of `Felt::as_int` so we avoid performing a
78 // montgomery reduction for every limb. that is safe because every inner element of the
79 // digest is guaranteed to be in its canonical form (that is, `x in [0,p)`).
80 self.0.iter().map(Felt::inner).zip(other.0.iter().map(Felt::inner)).fold(
81 Ordering::Equal,
82 |ord, (a, b)| match ord {
83 Ordering::Equal => a.cmp(&b),
84 _ => ord,
85 },
86 )
87 }
88}
89
90impl PartialOrd for RpoDigest {
91 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
92 Some(self.cmp(other))
93 }
94}
95
96impl Display for RpoDigest {
97 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
98 let encoded: String = self.into();
99 write!(f, "{}", encoded)?;
100 Ok(())
101 }
102}
103
104impl Randomizable for RpoDigest {
105 const VALUE_SIZE: usize = DIGEST_BYTES;
106
107 fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
108 let bytes_array: Option<[u8; 32]> = bytes.try_into().ok();
109 if let Some(bytes_array) = bytes_array {
110 Self::try_from(bytes_array).ok()
111 } else {
112 None
113 }
114 }
115}
116
117// CONVERSIONS: FROM RPO DIGEST
118// ================================================================================================
119
120impl From<&RpoDigest> for [Felt; DIGEST_SIZE] {
121 fn from(value: &RpoDigest) -> Self {
122 value.0
123 }
124}
125
126impl From<RpoDigest> for [Felt; DIGEST_SIZE] {
127 fn from(value: RpoDigest) -> Self {
128 value.0
129 }
130}
131
132impl From<&RpoDigest> for [u64; DIGEST_SIZE] {
133 fn from(value: &RpoDigest) -> Self {
134 [
135 value.0[0].as_int(),
136 value.0[1].as_int(),
137 value.0[2].as_int(),
138 value.0[3].as_int(),
139 ]
140 }
141}
142
143impl From<RpoDigest> for [u64; DIGEST_SIZE] {
144 fn from(value: RpoDigest) -> Self {
145 [
146 value.0[0].as_int(),
147 value.0[1].as_int(),
148 value.0[2].as_int(),
149 value.0[3].as_int(),
150 ]
151 }
152}
153
154impl From<&RpoDigest> for [u8; DIGEST_BYTES] {
155 fn from(value: &RpoDigest) -> Self {
156 value.as_bytes()
157 }
158}
159
160impl From<RpoDigest> for [u8; DIGEST_BYTES] {
161 fn from(value: RpoDigest) -> Self {
162 value.as_bytes()
163 }
164}
165
166impl From<RpoDigest> for String {
167 /// The returned string starts with `0x`.
168 fn from(value: RpoDigest) -> Self {
169 value.to_hex()
170 }
171}
172
173impl From<&RpoDigest> for String {
174 /// The returned string starts with `0x`.
175 fn from(value: &RpoDigest) -> Self {
176 (*value).into()
177 }
178}
179
180// CONVERSIONS: TO RPO DIGEST
181// ================================================================================================
182
183#[derive(Copy, Clone, Debug)]
184pub enum RpoDigestError {
185 /// The provided u64 integer does not fit in the field's moduli.
186 InvalidInteger,
187}
188
189impl From<&[Felt; DIGEST_SIZE]> for RpoDigest {
190 fn from(value: &[Felt; DIGEST_SIZE]) -> Self {
191 Self(*value)
192 }
193}
194
195impl From<[Felt; DIGEST_SIZE]> for RpoDigest {
196 fn from(value: [Felt; DIGEST_SIZE]) -> Self {
197 Self(value)
198 }
199}
200
201impl TryFrom<[u8; DIGEST_BYTES]> for RpoDigest {
202 type Error = HexParseError;
203
204 fn try_from(value: [u8; DIGEST_BYTES]) -> Result<Self, Self::Error> {
205 // Note: the input length is known, the conversion from slice to array must succeed so the
206 // `unwrap`s below are safe
207 let a = u64::from_le_bytes(value[0..8].try_into().unwrap());
208 let b = u64::from_le_bytes(value[8..16].try_into().unwrap());
209 let c = u64::from_le_bytes(value[16..24].try_into().unwrap());
210 let d = u64::from_le_bytes(value[24..32].try_into().unwrap());
211
212 if [a, b, c, d].iter().any(|v| *v >= Felt::MODULUS) {
213 return Err(HexParseError::OutOfRange);
214 }
215
216 Ok(RpoDigest([Felt::new(a), Felt::new(b), Felt::new(c), Felt::new(d)]))
217 }
218}
219
220impl TryFrom<&[u8; DIGEST_BYTES]> for RpoDigest {
221 type Error = HexParseError;
222
223 fn try_from(value: &[u8; DIGEST_BYTES]) -> Result<Self, Self::Error> {
224 (*value).try_into()
225 }
226}
227
228impl TryFrom<&[u8]> for RpoDigest {
229 type Error = HexParseError;
230
231 fn try_from(value: &[u8]) -> Result<Self, Self::Error> {
232 (*value).try_into()
233 }
234}
235
236impl TryFrom<[u64; DIGEST_SIZE]> for RpoDigest {
237 type Error = RpoDigestError;
238
239 fn try_from(value: [u64; DIGEST_SIZE]) -> Result<Self, RpoDigestError> {
240 Ok(Self([
241 value[0].try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
242 value[1].try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
243 value[2].try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
244 value[3].try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
245 ]))
246 }
247}
248
249impl TryFrom<&[u64; DIGEST_SIZE]> for RpoDigest {
250 type Error = RpoDigestError;
251
252 fn try_from(value: &[u64; DIGEST_SIZE]) -> Result<Self, RpoDigestError> {
253 (*value).try_into()
254 }
255}
256
257impl TryFrom<&str> for RpoDigest {
258 type Error = HexParseError;
259
260 /// Expects the string to start with `0x`.
261 fn try_from(value: &str) -> Result<Self, Self::Error> {
262 hex_to_bytes(value).and_then(|v| v.try_into())
263 }
264}
265
266impl TryFrom<String> for RpoDigest {
267 type Error = HexParseError;
268
269 /// Expects the string to start with `0x`.
270 fn try_from(value: String) -> Result<Self, Self::Error> {
271 value.as_str().try_into()
272 }
273}
274
275impl TryFrom<&String> for RpoDigest {
276 type Error = HexParseError;
277
278 /// Expects the string to start with `0x`.
279 fn try_from(value: &String) -> Result<Self, Self::Error> {
280 value.as_str().try_into()
281 }
282}
283
284// SERIALIZATION / DESERIALIZATION
285// ================================================================================================
286
287impl Serializable for RpoDigest {
288 fn write_into<W: ByteWriter>(&self, target: &mut W) {
289 target.write_bytes(&self.as_bytes());
290 }
291}
292
293impl Deserializable for RpoDigest {
294 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
295 let mut inner: [Felt; DIGEST_SIZE] = [ZERO; DIGEST_SIZE];
296 for inner in inner.iter_mut() {
297 let e = source.read_u64()?;
298 if e >= Felt::MODULUS {
299 return Err(DeserializationError::InvalidValue(String::from(
300 "Value not in the appropriate range",
301 )));
302 }
303 *inner = Felt::new(e);
304 }
305
306 Ok(Self(inner))
307 }
308}
309
310// ITERATORS
311// ================================================================================================
312impl IntoIterator for RpoDigest {
313 type Item = Felt;
314 type IntoIter = <[Felt; 4] as IntoIterator>::IntoIter;
315
316 fn into_iter(self) -> Self::IntoIter {
317 self.0.into_iter()
318 }
319}
320
321// TESTS
322// ================================================================================================
323
324#[cfg(test)]
325mod tests {
326 use rand_utils::rand_value;
327
328 use super::{Deserializable, Felt, RpoDigest, Serializable, DIGEST_BYTES, DIGEST_SIZE};
329 use crate::utils::{string::*, SliceReader};
330
331 #[test]
332 fn digest_serialization() {
333 let e1 = Felt::new(rand_value());
334 let e2 = Felt::new(rand_value());
335 let e3 = Felt::new(rand_value());
336 let e4 = Felt::new(rand_value());
337
338 let d1 = RpoDigest([e1, e2, e3, e4]);
339
340 let mut bytes = vec![];
341 d1.write_into(&mut bytes);
342 assert_eq!(DIGEST_BYTES, bytes.len());
343
344 let mut reader = SliceReader::new(&bytes);
345 let d2 = RpoDigest::read_from(&mut reader).unwrap();
346
347 assert_eq!(d1, d2);
348 }
349
350 #[test]
351 fn digest_encoding() {
352 let digest = RpoDigest([
353 Felt::new(rand_value()),
354 Felt::new(rand_value()),
355 Felt::new(rand_value()),
356 Felt::new(rand_value()),
357 ]);
358
359 let string: String = digest.into();
360 let round_trip: RpoDigest = string.try_into().expect("decoding failed");
361
362 assert_eq!(digest, round_trip);
363 }
364
365 #[test]
366 fn test_conversions() {
367 let digest = RpoDigest([
368 Felt::new(rand_value()),
369 Felt::new(rand_value()),
370 Felt::new(rand_value()),
371 Felt::new(rand_value()),
372 ]);
373
374 let v: [Felt; DIGEST_SIZE] = digest.into();
375 let v2: RpoDigest = v.into();
376 assert_eq!(digest, v2);
377
378 let v: [Felt; DIGEST_SIZE] = (&digest).into();
379 let v2: RpoDigest = v.into();
380 assert_eq!(digest, v2);
381
382 let v: [u64; DIGEST_SIZE] = digest.into();
383 let v2: RpoDigest = v.try_into().unwrap();
384 assert_eq!(digest, v2);
385
386 let v: [u64; DIGEST_SIZE] = (&digest).into();
387 let v2: RpoDigest = v.try_into().unwrap();
388 assert_eq!(digest, v2);
389
390 let v: [u8; DIGEST_BYTES] = digest.into();
391 let v2: RpoDigest = v.try_into().unwrap();
392 assert_eq!(digest, v2);
393
394 let v: [u8; DIGEST_BYTES] = (&digest).into();
395 let v2: RpoDigest = v.try_into().unwrap();
396 assert_eq!(digest, v2);
397
398 let v: String = digest.into();
399 let v2: RpoDigest = v.try_into().unwrap();
400 assert_eq!(digest, v2);
401
402 let v: String = (&digest).into();
403 let v2: RpoDigest = v.try_into().unwrap();
404 assert_eq!(digest, v2);
405
406 let v: [u8; DIGEST_BYTES] = digest.into();
407 let v2: RpoDigest = (&v).try_into().unwrap();
408 assert_eq!(digest, v2);
409
410 let v: [u8; DIGEST_BYTES] = (&digest).into();
411 let v2: RpoDigest = (&v).try_into().unwrap();
412 assert_eq!(digest, v2);
413 }
414}