miden-crypto/src/hash/rescue/rpo/digest.rs
src/hash/rescue/rpo/digest.rsRaw
1use alloc::string::String;
2use core::{cmp::Ordering, fmt::Display, ops::Deref};
3
4use super::{Digest, Felt, StarkField, DIGEST_BYTES, DIGEST_SIZE, ZERO};
5use crate::{
6 rand::Randomizable,
7 utils::{
8 bytes_to_hex_string, hex_to_bytes, ByteReader, ByteWriter, Deserializable,
9 DeserializationError, HexParseError, Serializable,
10 },
11};
12
13// DIGEST TRAIT IMPLEMENTATIONS
14// ================================================================================================
15
16#[derive(Debug, Default, Copy, Clone, Eq, PartialEq)]
17#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
18#[cfg_attr(feature = "serde", serde(into = "String", try_from = "&str"))]
19pub struct RpoDigest([Felt; DIGEST_SIZE]);
20
21impl RpoDigest {
22 /// The serialized size of the digest in bytes.
23 pub const SERIALIZED_SIZE: usize = DIGEST_BYTES;
24
25 pub const fn new(value: [Felt; DIGEST_SIZE]) -> Self {
26 Self(value)
27 }
28
29 pub fn as_elements(&self) -> &[Felt] {
30 self.as_ref()
31 }
32
33 pub fn as_bytes(&self) -> [u8; DIGEST_BYTES] {
34 <Self as Digest>::as_bytes(self)
35 }
36
37 pub fn digests_as_elements<'a, I>(digests: I) -> impl Iterator<Item = &'a Felt>
38 where
39 I: Iterator<Item = &'a Self>,
40 {
41 digests.flat_map(|d| d.0.iter())
42 }
43
44 /// Returns hexadecimal representation of this digest prefixed with `0x`.
45 pub fn to_hex(&self) -> String {
46 bytes_to_hex_string(self.as_bytes())
47 }
48}
49
50impl Digest for RpoDigest {
51 fn as_bytes(&self) -> [u8; DIGEST_BYTES] {
52 let mut result = [0; DIGEST_BYTES];
53
54 result[..8].copy_from_slice(&self.0[0].as_int().to_le_bytes());
55 result[8..16].copy_from_slice(&self.0[1].as_int().to_le_bytes());
56 result[16..24].copy_from_slice(&self.0[2].as_int().to_le_bytes());
57 result[24..].copy_from_slice(&self.0[3].as_int().to_le_bytes());
58
59 result
60 }
61}
62
63impl Deref for RpoDigest {
64 type Target = [Felt; DIGEST_SIZE];
65
66 fn deref(&self) -> &Self::Target {
67 &self.0
68 }
69}
70
71impl Ord for RpoDigest {
72 fn cmp(&self, other: &Self) -> Ordering {
73 // compare the inner u64 of both elements.
74 //
75 // it will iterate the elements and will return the first computation different than
76 // `Equal`. Otherwise, the ordering is equal.
77 //
78 // the endianness is irrelevant here because since, this being a cryptographically secure
79 // hash computation, the digest shouldn't have any ordered property of its input.
80 //
81 // finally, we use `Felt::inner` instead of `Felt::as_int` so we avoid performing a
82 // montgomery reduction for every limb. that is safe because every inner element of the
83 // digest is guaranteed to be in its canonical form (that is, `x in [0,p)`).
84 self.0.iter().map(Felt::inner).zip(other.0.iter().map(Felt::inner)).fold(
85 Ordering::Equal,
86 |ord, (a, b)| match ord {
87 Ordering::Equal => a.cmp(&b),
88 _ => ord,
89 },
90 )
91 }
92}
93
94impl PartialOrd for RpoDigest {
95 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
96 Some(self.cmp(other))
97 }
98}
99
100impl Display for RpoDigest {
101 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
102 let encoded: String = self.into();
103 write!(f, "{}", encoded)?;
104 Ok(())
105 }
106}
107
108impl Randomizable for RpoDigest {
109 const VALUE_SIZE: usize = DIGEST_BYTES;
110
111 fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
112 let bytes_array: Option<[u8; 32]> = bytes.try_into().ok();
113 if let Some(bytes_array) = bytes_array {
114 Self::try_from(bytes_array).ok()
115 } else {
116 None
117 }
118 }
119}
120
121// CONVERSIONS: FROM RPO DIGEST
122// ================================================================================================
123
124#[derive(Copy, Clone, Debug)]
125pub enum RpoDigestError {
126 InvalidInteger,
127}
128
129impl TryFrom<&RpoDigest> for [bool; DIGEST_SIZE] {
130 type Error = RpoDigestError;
131
132 fn try_from(value: &RpoDigest) -> Result<Self, Self::Error> {
133 (*value).try_into()
134 }
135}
136
137impl TryFrom<RpoDigest> for [bool; DIGEST_SIZE] {
138 type Error = RpoDigestError;
139
140 fn try_from(value: RpoDigest) -> Result<Self, Self::Error> {
141 fn to_bool(v: u64) -> Option<bool> {
142 if v <= 1 {
143 Some(v == 1)
144 } else {
145 None
146 }
147 }
148
149 Ok([
150 to_bool(value.0[0].as_int()).ok_or(RpoDigestError::InvalidInteger)?,
151 to_bool(value.0[1].as_int()).ok_or(RpoDigestError::InvalidInteger)?,
152 to_bool(value.0[2].as_int()).ok_or(RpoDigestError::InvalidInteger)?,
153 to_bool(value.0[3].as_int()).ok_or(RpoDigestError::InvalidInteger)?,
154 ])
155 }
156}
157
158impl TryFrom<&RpoDigest> for [u8; DIGEST_SIZE] {
159 type Error = RpoDigestError;
160
161 fn try_from(value: &RpoDigest) -> Result<Self, Self::Error> {
162 (*value).try_into()
163 }
164}
165
166impl TryFrom<RpoDigest> for [u8; DIGEST_SIZE] {
167 type Error = RpoDigestError;
168
169 fn try_from(value: RpoDigest) -> Result<Self, Self::Error> {
170 Ok([
171 value.0[0].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
172 value.0[1].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
173 value.0[2].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
174 value.0[3].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
175 ])
176 }
177}
178
179impl TryFrom<&RpoDigest> for [u16; DIGEST_SIZE] {
180 type Error = RpoDigestError;
181
182 fn try_from(value: &RpoDigest) -> Result<Self, Self::Error> {
183 (*value).try_into()
184 }
185}
186
187impl TryFrom<RpoDigest> for [u16; DIGEST_SIZE] {
188 type Error = RpoDigestError;
189
190 fn try_from(value: RpoDigest) -> Result<Self, Self::Error> {
191 Ok([
192 value.0[0].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
193 value.0[1].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
194 value.0[2].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
195 value.0[3].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
196 ])
197 }
198}
199
200impl TryFrom<&RpoDigest> for [u32; DIGEST_SIZE] {
201 type Error = RpoDigestError;
202
203 fn try_from(value: &RpoDigest) -> Result<Self, Self::Error> {
204 (*value).try_into()
205 }
206}
207
208impl TryFrom<RpoDigest> for [u32; DIGEST_SIZE] {
209 type Error = RpoDigestError;
210
211 fn try_from(value: RpoDigest) -> Result<Self, Self::Error> {
212 Ok([
213 value.0[0].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
214 value.0[1].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
215 value.0[2].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
216 value.0[3].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
217 ])
218 }
219}
220
221impl From<&RpoDigest> for [u64; DIGEST_SIZE] {
222 fn from(value: &RpoDigest) -> Self {
223 (*value).into()
224 }
225}
226
227impl From<RpoDigest> for [u64; DIGEST_SIZE] {
228 fn from(value: RpoDigest) -> Self {
229 [
230 value.0[0].as_int(),
231 value.0[1].as_int(),
232 value.0[2].as_int(),
233 value.0[3].as_int(),
234 ]
235 }
236}
237
238impl From<&RpoDigest> for [Felt; DIGEST_SIZE] {
239 fn from(value: &RpoDigest) -> Self {
240 (*value).into()
241 }
242}
243
244impl From<RpoDigest> for [Felt; DIGEST_SIZE] {
245 fn from(value: RpoDigest) -> Self {
246 value.0
247 }
248}
249
250impl From<&RpoDigest> for [u8; DIGEST_BYTES] {
251 fn from(value: &RpoDigest) -> Self {
252 (*value).into()
253 }
254}
255
256impl From<RpoDigest> for [u8; DIGEST_BYTES] {
257 fn from(value: RpoDigest) -> Self {
258 value.as_bytes()
259 }
260}
261
262impl From<&RpoDigest> for String {
263 /// The returned string starts with `0x`.
264 fn from(value: &RpoDigest) -> Self {
265 (*value).into()
266 }
267}
268
269impl From<RpoDigest> for String {
270 /// The returned string starts with `0x`.
271 fn from(value: RpoDigest) -> Self {
272 value.to_hex()
273 }
274}
275
276// CONVERSIONS: TO RPO DIGEST
277// ================================================================================================
278
279impl From<&[bool; DIGEST_SIZE]> for RpoDigest {
280 fn from(value: &[bool; DIGEST_SIZE]) -> Self {
281 (*value).into()
282 }
283}
284
285impl From<[bool; DIGEST_SIZE]> for RpoDigest {
286 fn from(value: [bool; DIGEST_SIZE]) -> Self {
287 [value[0] as u32, value[1] as u32, value[2] as u32, value[3] as u32].into()
288 }
289}
290
291impl From<&[u8; DIGEST_SIZE]> for RpoDigest {
292 fn from(value: &[u8; DIGEST_SIZE]) -> Self {
293 (*value).into()
294 }
295}
296
297impl From<[u8; DIGEST_SIZE]> for RpoDigest {
298 fn from(value: [u8; DIGEST_SIZE]) -> Self {
299 Self([value[0].into(), value[1].into(), value[2].into(), value[3].into()])
300 }
301}
302
303impl From<&[u16; DIGEST_SIZE]> for RpoDigest {
304 fn from(value: &[u16; DIGEST_SIZE]) -> Self {
305 (*value).into()
306 }
307}
308
309impl From<[u16; DIGEST_SIZE]> for RpoDigest {
310 fn from(value: [u16; DIGEST_SIZE]) -> Self {
311 Self([value[0].into(), value[1].into(), value[2].into(), value[3].into()])
312 }
313}
314
315impl From<&[u32; DIGEST_SIZE]> for RpoDigest {
316 fn from(value: &[u32; DIGEST_SIZE]) -> Self {
317 (*value).into()
318 }
319}
320
321impl From<[u32; DIGEST_SIZE]> for RpoDigest {
322 fn from(value: [u32; DIGEST_SIZE]) -> Self {
323 Self([value[0].into(), value[1].into(), value[2].into(), value[3].into()])
324 }
325}
326
327impl TryFrom<&[u64; DIGEST_SIZE]> for RpoDigest {
328 type Error = RpoDigestError;
329
330 fn try_from(value: &[u64; DIGEST_SIZE]) -> Result<Self, RpoDigestError> {
331 (*value).try_into()
332 }
333}
334
335impl TryFrom<[u64; DIGEST_SIZE]> for RpoDigest {
336 type Error = RpoDigestError;
337
338 fn try_from(value: [u64; DIGEST_SIZE]) -> Result<Self, RpoDigestError> {
339 Ok(Self([
340 value[0].try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
341 value[1].try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
342 value[2].try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
343 value[3].try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
344 ]))
345 }
346}
347
348impl From<&[Felt; DIGEST_SIZE]> for RpoDigest {
349 fn from(value: &[Felt; DIGEST_SIZE]) -> Self {
350 Self(*value)
351 }
352}
353
354impl From<[Felt; DIGEST_SIZE]> for RpoDigest {
355 fn from(value: [Felt; DIGEST_SIZE]) -> Self {
356 Self(value)
357 }
358}
359
360impl TryFrom<&[u8; DIGEST_BYTES]> for RpoDigest {
361 type Error = HexParseError;
362
363 fn try_from(value: &[u8; DIGEST_BYTES]) -> Result<Self, Self::Error> {
364 (*value).try_into()
365 }
366}
367
368impl TryFrom<[u8; DIGEST_BYTES]> for RpoDigest {
369 type Error = HexParseError;
370
371 fn try_from(value: [u8; DIGEST_BYTES]) -> Result<Self, Self::Error> {
372 // Note: the input length is known, the conversion from slice to array must succeed so the
373 // `unwrap`s below are safe
374 let a = u64::from_le_bytes(value[0..8].try_into().unwrap());
375 let b = u64::from_le_bytes(value[8..16].try_into().unwrap());
376 let c = u64::from_le_bytes(value[16..24].try_into().unwrap());
377 let d = u64::from_le_bytes(value[24..32].try_into().unwrap());
378
379 if [a, b, c, d].iter().any(|v| *v >= Felt::MODULUS) {
380 return Err(HexParseError::OutOfRange);
381 }
382
383 Ok(RpoDigest([Felt::new(a), Felt::new(b), Felt::new(c), Felt::new(d)]))
384 }
385}
386
387impl TryFrom<&[u8]> for RpoDigest {
388 type Error = HexParseError;
389
390 fn try_from(value: &[u8]) -> Result<Self, Self::Error> {
391 (*value).try_into()
392 }
393}
394
395impl TryFrom<&str> for RpoDigest {
396 type Error = HexParseError;
397
398 /// Expects the string to start with `0x`.
399 fn try_from(value: &str) -> Result<Self, Self::Error> {
400 hex_to_bytes::<DIGEST_BYTES>(value).and_then(RpoDigest::try_from)
401 }
402}
403
404impl TryFrom<String> for RpoDigest {
405 type Error = HexParseError;
406
407 /// Expects the string to start with `0x`.
408 fn try_from(value: String) -> Result<Self, Self::Error> {
409 value.as_str().try_into()
410 }
411}
412
413impl TryFrom<&String> for RpoDigest {
414 type Error = HexParseError;
415
416 /// Expects the string to start with `0x`.
417 fn try_from(value: &String) -> Result<Self, Self::Error> {
418 value.as_str().try_into()
419 }
420}
421
422// SERIALIZATION / DESERIALIZATION
423// ================================================================================================
424
425impl Serializable for RpoDigest {
426 fn write_into<W: ByteWriter>(&self, target: &mut W) {
427 target.write_bytes(&self.as_bytes());
428 }
429
430 fn get_size_hint(&self) -> usize {
431 Self::SERIALIZED_SIZE
432 }
433}
434
435impl Deserializable for RpoDigest {
436 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
437 let mut inner: [Felt; DIGEST_SIZE] = [ZERO; DIGEST_SIZE];
438 for inner in inner.iter_mut() {
439 let e = source.read_u64()?;
440 if e >= Felt::MODULUS {
441 return Err(DeserializationError::InvalidValue(String::from(
442 "Value not in the appropriate range",
443 )));
444 }
445 *inner = Felt::new(e);
446 }
447
448 Ok(Self(inner))
449 }
450}
451
452// ITERATORS
453// ================================================================================================
454impl IntoIterator for RpoDigest {
455 type Item = Felt;
456 type IntoIter = <[Felt; 4] as IntoIterator>::IntoIter;
457
458 fn into_iter(self) -> Self::IntoIter {
459 self.0.into_iter()
460 }
461}
462
463// TESTS
464// ================================================================================================
465
466#[cfg(test)]
467mod tests {
468 use alloc::string::String;
469 use rand_utils::rand_value;
470
471 use super::{Deserializable, Felt, RpoDigest, Serializable, DIGEST_BYTES, DIGEST_SIZE};
472 use crate::utils::SliceReader;
473
474 #[test]
475 fn digest_serialization() {
476 let e1 = Felt::new(rand_value());
477 let e2 = Felt::new(rand_value());
478 let e3 = Felt::new(rand_value());
479 let e4 = Felt::new(rand_value());
480
481 let d1 = RpoDigest([e1, e2, e3, e4]);
482
483 let mut bytes = vec![];
484 d1.write_into(&mut bytes);
485 assert_eq!(DIGEST_BYTES, bytes.len());
486 assert_eq!(bytes.len(), d1.get_size_hint());
487
488 let mut reader = SliceReader::new(&bytes);
489 let d2 = RpoDigest::read_from(&mut reader).unwrap();
490
491 assert_eq!(d1, d2);
492 }
493
494 #[test]
495 fn digest_encoding() {
496 let digest = RpoDigest([
497 Felt::new(rand_value()),
498 Felt::new(rand_value()),
499 Felt::new(rand_value()),
500 Felt::new(rand_value()),
501 ]);
502
503 let string: String = digest.into();
504 let round_trip: RpoDigest = string.try_into().expect("decoding failed");
505
506 assert_eq!(digest, round_trip);
507 }
508
509 #[test]
510 fn test_conversions() {
511 let digest = RpoDigest([
512 Felt::new(rand_value()),
513 Felt::new(rand_value()),
514 Felt::new(rand_value()),
515 Felt::new(rand_value()),
516 ]);
517
518 // BY VALUE
519 // ----------------------------------------------------------------------------------------
520 let v: [bool; DIGEST_SIZE] = [true, false, true, true];
521 let v2: RpoDigest = v.into();
522 assert_eq!(v, <[bool; DIGEST_SIZE]>::try_from(v2).unwrap());
523
524 let v: [u8; DIGEST_SIZE] = [0_u8, 1_u8, 2_u8, 3_u8];
525 let v2: RpoDigest = v.into();
526 assert_eq!(v, <[u8; DIGEST_SIZE]>::try_from(v2).unwrap());
527
528 let v: [u16; DIGEST_SIZE] = [0_u16, 1_u16, 2_u16, 3_u16];
529 let v2: RpoDigest = v.into();
530 assert_eq!(v, <[u16; DIGEST_SIZE]>::try_from(v2).unwrap());
531
532 let v: [u32; DIGEST_SIZE] = [0_u32, 1_u32, 2_u32, 3_u32];
533 let v2: RpoDigest = v.into();
534 assert_eq!(v, <[u32; DIGEST_SIZE]>::try_from(v2).unwrap());
535
536 let v: [u64; DIGEST_SIZE] = digest.into();
537 let v2: RpoDigest = v.try_into().unwrap();
538 assert_eq!(digest, v2);
539
540 let v: [Felt; DIGEST_SIZE] = digest.into();
541 let v2: RpoDigest = v.into();
542 assert_eq!(digest, v2);
543
544 let v: [u8; DIGEST_BYTES] = digest.into();
545 let v2: RpoDigest = v.try_into().unwrap();
546 assert_eq!(digest, v2);
547
548 let v: String = digest.into();
549 let v2: RpoDigest = v.try_into().unwrap();
550 assert_eq!(digest, v2);
551
552 // BY REF
553 // ----------------------------------------------------------------------------------------
554 let v: [bool; DIGEST_SIZE] = [true, false, true, true];
555 let v2: RpoDigest = (&v).into();
556 assert_eq!(v, <[bool; DIGEST_SIZE]>::try_from(&v2).unwrap());
557
558 let v: [u8; DIGEST_SIZE] = [0_u8, 1_u8, 2_u8, 3_u8];
559 let v2: RpoDigest = (&v).into();
560 assert_eq!(v, <[u8; DIGEST_SIZE]>::try_from(&v2).unwrap());
561
562 let v: [u16; DIGEST_SIZE] = [0_u16, 1_u16, 2_u16, 3_u16];
563 let v2: RpoDigest = (&v).into();
564 assert_eq!(v, <[u16; DIGEST_SIZE]>::try_from(&v2).unwrap());
565
566 let v: [u32; DIGEST_SIZE] = [0_u32, 1_u32, 2_u32, 3_u32];
567 let v2: RpoDigest = (&v).into();
568 assert_eq!(v, <[u32; DIGEST_SIZE]>::try_from(&v2).unwrap());
569
570 let v: [u64; DIGEST_SIZE] = (&digest).into();
571 let v2: RpoDigest = (&v).try_into().unwrap();
572 assert_eq!(digest, v2);
573
574 let v: [Felt; DIGEST_SIZE] = (&digest).into();
575 let v2: RpoDigest = (&v).into();
576 assert_eq!(digest, v2);
577
578 let v: [u8; DIGEST_BYTES] = (&digest).into();
579 let v2: RpoDigest = (&v).try_into().unwrap();
580 assert_eq!(digest, v2);
581
582 let v: String = (&digest).into();
583 let v2: RpoDigest = (&v).try_into().unwrap();
584 assert_eq!(digest, v2);
585 }
586}