miden_crypto/hash/rescue/rpx/
digest.rs

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

miden_crypto/hash/rescue/rpx/
digest.rs
