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