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